~ initialization plugin in tests
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/pipeline/convertToIr.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/pipeline/convertToIr.kt index 3de2d42..c736e0a 100644 --- a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/pipeline/convertToIr.kt +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/fir/pipeline/convertToIr.kt
@@ -27,6 +27,9 @@ import org.jetbrains.kotlin.fir.lazy.Fir2IrLazyClass import org.jetbrains.kotlin.fir.moduleData import org.jetbrains.kotlin.fir.resolve.ScopeSession +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationChecker +import org.jetbrains.kotlin.initialization.plugin.logic.DefaultFunctionParametersCollector +import org.jetbrains.kotlin.initialization.plugin.logic.OverridingCallablesCollector import org.jetbrains.kotlin.ir.IrBuiltIns import org.jetbrains.kotlin.ir.IrElement import org.jetbrains.kotlin.ir.IrStatement @@ -278,7 +281,12 @@ removeGeneratedBuiltinsDeclarationsIfNeeded() hasIrValidationErrorFromFrontend = pluginContext.runMandatoryIrValidation(extension = null, mainIrFragment) - pluginContext.applyIrGenerationExtensions(mainIrFragment, irGeneratorExtensions) + pluginContext.applyIrGenerationExtensions( + mainIrFragment, + irGeneratorExtensions + listOf( + OverridingCallablesCollector, DefaultFunctionParametersCollector, StaticInitializationChecker + ) + ) return Fir2IrActualizedResult(mainIrFragment, componentsStorage, pluginContext, actualizationResult, irBuiltIns, symbolTable) }
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/FirStaticInitializationExtensionRegistrar.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/FirStaticInitializationExtensionRegistrar.kt new file mode 100644 index 0000000..5cf89ba --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/FirStaticInitializationExtensionRegistrar.kt
@@ -0,0 +1,11 @@ +package org.jetbrains.kotlin.initialization.plugin + +import org.jetbrains.kotlin.fir.extensions.FirExtensionRegistrar +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics + +class FirStaticInitializationExtensionRegistrar : FirExtensionRegistrar() { + + override fun ExtensionRegistrarContext.configurePlugin() { + registerDiagnosticContainers(StaticInitializationDiagnostics) + } +} \ No newline at end of file
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/UseBeforeStaticInitializationPluginRegistrar.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/UseBeforeStaticInitializationPluginRegistrar.kt new file mode 100644 index 0000000..e2b83d9 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/UseBeforeStaticInitializationPluginRegistrar.kt
@@ -0,0 +1,24 @@ +package org.jetbrains.kotlin.initialization.plugin + +import org.jetbrains.kotlin.backend.common.extensions.IrGenerationExtension +import org.jetbrains.kotlin.compiler.plugin.CompilerPluginRegistrar +import org.jetbrains.kotlin.compiler.plugin.ExperimentalCompilerApi +import org.jetbrains.kotlin.compiler.plugin.registerExtension +import org.jetbrains.kotlin.config.CompilerConfiguration +import org.jetbrains.kotlin.fir.extensions.FirExtensionRegistrar +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationChecker +import org.jetbrains.kotlin.initialization.plugin.logic.DefaultFunctionParametersCollector +import org.jetbrains.kotlin.initialization.plugin.logic.OverridingCallablesCollector + +@OptIn(ExperimentalCompilerApi::class) +class UseBeforeStaticInitializationPluginRegistrar : CompilerPluginRegistrar() { + override val pluginId: String get() = "org.jetbrains.kotlin.initialization.plugin" + override val supportsK2: Boolean get() = true + + override fun ExtensionStorage.registerExtensions(configuration: CompilerConfiguration) { + IrGenerationExtension.registerExtension(OverridingCallablesCollector) + IrGenerationExtension.registerExtension(DefaultFunctionParametersCollector) + IrGenerationExtension.registerExtension(StaticInitializationChecker) + FirExtensionRegistrar.registerExtension(FirStaticInitializationExtensionRegistrar()) + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/checker/StaticInitializationChecker.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/checker/StaticInitializationChecker.kt new file mode 100644 index 0000000..faadfa9 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/checker/StaticInitializationChecker.kt
@@ -0,0 +1,185 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.checker + +import org.jetbrains.kotlin.KtOffsetsOnlySourceElement +import org.jetbrains.kotlin.initialization.plugin.model.AnonymousInitializerIndex +import org.jetbrains.kotlin.initialization.plugin.model.ClinitIndex +import org.jetbrains.kotlin.initialization.plugin.model.DependencyGraph +import org.jetbrains.kotlin.initialization.plugin.model.EnumEntryIndex +import org.jetbrains.kotlin.initialization.plugin.model.FunctionIndex +import org.jetbrains.kotlin.initialization.plugin.model.InitializationCycleAccessResult +import org.jetbrains.kotlin.initialization.plugin.model.PropertyIndex +import org.jetbrains.kotlin.initialization.plugin.model.QualifierIndex +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.ACCESSING_DECLARATION_OF_POSSIBLY_INACCESSIBLE_CLASS +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.ACCESSING_POSSIBLY_INACCESSIBLE_OBJECT_REFERENCE +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.ACCESSING_POSSIBLY_UNINITIALIZED_ENUM_ENTRY +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.ACCESSING_POSSIBLY_UNINITIALIZED_PROPERTY +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.CONSTRUCTING_POSSIBLY_DEADLOCKING_CLASS +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.POSSIBLE_CYCLIC_ACCESS +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.POSSIBLE_INITIALIZATION_DEADLOCK +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.POSSIBLY_UNINITIALIZED_ENUM_ENTRY +import org.jetbrains.kotlin.initialization.plugin.checker.StaticInitializationDiagnostics.POSSIBLY_UNINITIALIZED_PROPERTY +import org.jetbrains.kotlin.initialization.plugin.logic.DependencyGraphResolver +import org.jetbrains.kotlin.initialization.plugin.model.AnalysisResult +import org.jetbrains.kotlin.initialization.plugin.model.DependencyGraphAnalyzer +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.parentEnclosingEntityOrSelf +import org.jetbrains.kotlin.backend.common.extensions.IrGenerationExtension +import org.jetbrains.kotlin.backend.common.extensions.IrPluginContext +import org.jetbrains.kotlin.ir.IrDiagnosticReporter +import org.jetbrains.kotlin.ir.IrElement +import org.jetbrains.kotlin.ir.declarations.IrClass +import org.jetbrains.kotlin.ir.declarations.IrFile +import org.jetbrains.kotlin.ir.declarations.IrModuleFragment +import org.jetbrains.kotlin.ir.declarations.IrParameterKind +import org.jetbrains.kotlin.ir.expressions.IrFunctionAccessExpression +import org.jetbrains.kotlin.ir.expressions.IrMemberAccessExpression +import org.jetbrains.kotlin.ir.util.callableId +import org.jetbrains.kotlin.name.CallableId +import kotlin.sequences.forEach + +object StaticInitializationChecker : IrGenerationExtension { + + override fun generate(moduleFragment: IrModuleFragment, pluginContext: IrPluginContext) { + val graph = DependencyGraph(moduleFragment) + val resolver = DependencyGraphResolver(graph) + val analyzer = DependencyGraphAnalyzer(graph) + moduleFragment.files.forEach { file -> + context(pluginContext.diagnosticReporter, file) { + resolver.collectDependencies(file).forEach { node -> + when (node) { + is ClinitIndex -> analyzer.checkDeadlocks(node.enclosingEntity) + is QualifierIndex -> { + analyzer.checkObjectConstructor(node.enclosingEntity) + analyzer.checkDeadlocks(node.enclosingEntity) + } + is EnumEntryIndex -> analyzer.checkEnumEntry(node.enclosingEntity) + is PropertyIndex -> analyzer.checkProperty(node) + is AnonymousInitializerIndex -> analyzer.checkAccessesInInitializer(node) + else -> {} + } + } + } + } + } + + private fun IrElement.sourceElement(): KtOffsetsOnlySourceElement? = when (this) { + is IrFunctionAccessExpression -> { + fun IrElement.actualStartOffset(): Int = when (this) { + is IrFunctionAccessExpression -> (symbol.owner.parameters.find { it.kind == IrParameterKind.ExtensionReceiver } + ?.let(arguments::get) ?: dispatchReceiver)?.actualStartOffset() ?: startOffset + is IrMemberAccessExpression<*> -> dispatchReceiver?.actualStartOffset() ?: startOffset + else -> startOffset + } + + val startOffset = actualStartOffset() + if (startOffset >= 0) KtOffsetsOnlySourceElement(startOffset, endOffset) else null + } + else -> if (startOffset >= 0) KtOffsetsOnlySourceElement(startOffset, endOffset) else null + } + + context(reporter: IrDiagnosticReporter, containingFile: IrFile) + private fun reportResultAndPossibleUninitialization(result: AnalysisResult, reportDeadlocks: Boolean = true): Boolean { + val [type, accesses] = result + when (type) { + is InitializationCycleAccessResult.UninitializedPropertyAccess -> accesses.forEach { + reporter.at(it.sourceElement(), it, containingFile).report(ACCESSING_POSSIBLY_UNINITIALIZED_PROPERTY, type.node.name) + } + is InitializationCycleAccessResult.UninitializedEnumEntryAccess -> accesses.forEach { + reporter.at(it.sourceElement(), it, containingFile).report(ACCESSING_POSSIBLY_UNINITIALIZED_ENUM_ENTRY, type.node.enclosingEntity.symbol) + } + is InitializationCycleAccessResult.CyclicAccess -> accesses.forEach { + reporter.at(it.sourceElement(), it, containingFile).report(POSSIBLE_CYCLIC_ACCESS, type.node.symbol) + } + is InitializationCycleAccessResult.InaccessibleEntityAccess -> + when (val node = type.node) { + is QualifierIndex -> accesses.forEach { + reporter.at(it.sourceElement(), it, containingFile).report(ACCESSING_POSSIBLY_INACCESSIBLE_OBJECT_REFERENCE, type.entity.name) + } + is EnumEntryIndex -> { + val enumClass = node.enclosingEntity.parentEnclosingEntity + accesses.forEach { + reporter.at(it.sourceElement(), it, containingFile) + .report(ACCESSING_DECLARATION_OF_POSSIBLY_INACCESSIBLE_CLASS, enumClass.name, node.enclosingEntity.symbol) + } + } + is FunctionIndex<*> -> { + val parent = type.entity.parentEnclosingEntityOrSelf + accesses.forEach { + reporter.at(it.sourceElement(), it, containingFile) + .report(ACCESSING_DECLARATION_OF_POSSIBLY_INACCESSIBLE_CLASS, parent.name, node.symbol) + } + } + is PropertyIndex -> { + val parent = type.entity.parentEnclosingEntityOrSelf + accesses.forEach { + reporter.at(it.sourceElement(), it, containingFile) + .report(ACCESSING_DECLARATION_OF_POSSIBLY_INACCESSIBLE_CLASS, parent.name, node.symbol) + } + } + } + is InitializationCycleAccessResult.DeadlockInducingConstructorCall if reportDeadlocks -> accesses.forEach { + reporter.at(it.sourceElement(), it, containingFile).report( + CONSTRUCTING_POSSIBLY_DEADLOCKING_CLASS, + type.node.symbol.owner.callableId.classId?.relativeClassName ?: CallableId(type.node.symbol.owner.name).asSingleFqName() + ) + } + else -> {} + } + return type.poisonsInitializers + } + + context(reporter: IrDiagnosticReporter, containingFile: IrFile) + private fun DependencyGraphAnalyzer.checkDeadlocks(enclosingEntity: EnclosingEntity<IrClass>) { + if (enclosingEntity.symbol.owner.isCompanion) return + val deadlockingEntities = mutuallyDependentEntities(enclosingEntity).toList() + if (deadlockingEntities.isNotEmpty()) { + reporter.at(enclosingEntity.symbol.owner, containingFile).report( + POSSIBLE_INITIALIZATION_DEADLOCK, + deadlockingEntities.map(EnclosingEntity<*>::name) + ) + } + } + + context(reporter: IrDiagnosticReporter, containingFile: IrFile) + private fun DependencyGraphAnalyzer.checkObjectConstructor(enclosingEntity: EnclosingEntity.Object) = + analyze(enclosingEntity.beginInitializationIndex).forEach { reportResultAndPossibleUninitialization(it, false) } + + context(reporter: IrDiagnosticReporter, containingFile: IrFile) + private fun DependencyGraphAnalyzer.checkAccessesInInitializer(initializerNode: AnonymousInitializerIndex) = + analyze(initializerNode).forEach { reportResultAndPossibleUninitialization(it) } + + context(reporter: IrDiagnosticReporter, containingFile: IrFile) + private fun DependencyGraphAnalyzer.checkEnumEntry(enclosingEntity: EnclosingEntity.EnumEntry) { + val isPossiblyUninitialized = analyze(enclosingEntity.beginInitializationIndex).fold(false) { isUninitialized, result -> + isUninitialized || reportResultAndPossibleUninitialization(result) + } + if (isPossiblyUninitialized) { + reporter.at(enclosingEntity.symbol.owner, containingFile).report( + POSSIBLY_UNINITIALIZED_ENUM_ENTRY, + enclosingEntity.symbol, + mutuallyDependentEntities(enclosingEntity).mapTo(mutableListOf(), EnclosingEntity<*>::name) + ) + } + } + + context(reporter: IrDiagnosticReporter, containingFile: IrFile) + fun DependencyGraphAnalyzer.checkProperty(propertyNode: PropertyIndex) { + val isPossiblyUninitialized = analyze(propertyNode).fold(false) { isUninitialized, result -> + isUninitialized || reportResultAndPossibleUninitialization(result) + } + if (isPossiblyUninitialized) { + reporter.at(propertyNode.symbol.owner, containingFile).report( + POSSIBLY_UNINITIALIZED_PROPERTY, + propertyNode.name, + propertyNode.enclosingEntity?.let { + mutuallyDependentEntities(it).mapTo(mutableListOf(), EnclosingEntity<*>::name) + } ?: emptyList() + ) + } + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/checker/StaticInitializationDiagnostics.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/checker/StaticInitializationDiagnostics.kt new file mode 100644 index 0000000..047a5f5 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/checker/StaticInitializationDiagnostics.kt
@@ -0,0 +1,92 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.checker + +import com.intellij.psi.PsiElement +import org.jetbrains.kotlin.diagnostics.KtDiagnosticFactoryToRendererMap +import org.jetbrains.kotlin.diagnostics.KtDiagnosticsContainer +import org.jetbrains.kotlin.diagnostics.rendering.BaseDiagnosticRendererFactory +import org.jetbrains.kotlin.diagnostics.rendering.Renderer +import org.jetbrains.kotlin.diagnostics.warning1 +import org.jetbrains.kotlin.diagnostics.warning2 +import org.jetbrains.kotlin.ir.declarations.IrDeclaration +import org.jetbrains.kotlin.ir.declarations.IrDeclarationWithName +import org.jetbrains.kotlin.ir.symbols.IrBindableSymbol +import org.jetbrains.kotlin.ir.symbols.IrEnumEntrySymbol +import org.jetbrains.kotlin.name.FqName +import kotlin.getValue + +object StaticInitializationDiagnostics : KtDiagnosticsContainer() { + val POSSIBLE_INITIALIZATION_DEADLOCK by warning1<PsiElement, List<FqName>>() + val POSSIBLY_UNINITIALIZED_PROPERTY by warning2<PsiElement, FqName, List<FqName>>() + val POSSIBLY_UNINITIALIZED_ENUM_ENTRY by warning2<PsiElement, IrEnumEntrySymbol, List<FqName>>() + val ACCESSING_POSSIBLY_UNINITIALIZED_PROPERTY by warning1<PsiElement, FqName>() + val ACCESSING_POSSIBLY_UNINITIALIZED_ENUM_ENTRY by warning1<PsiElement, IrEnumEntrySymbol>() + val POSSIBLE_CYCLIC_ACCESS by warning1<PsiElement, IrBindableSymbol<*, out IrDeclaration>>() + val ACCESSING_POSSIBLY_INACCESSIBLE_OBJECT_REFERENCE by warning1<PsiElement, FqName>() + val ACCESSING_DECLARATION_OF_POSSIBLY_INACCESSIBLE_CLASS by warning2<PsiElement, FqName, IrBindableSymbol<*, out IrDeclarationWithName>>() + val CONSTRUCTING_POSSIBLY_DEADLOCKING_CLASS by warning1<PsiElement, FqName>() + + + override fun getRendererFactory(): BaseDiagnosticRendererFactory = object : BaseDiagnosticRendererFactory() { + override val MAP by KtDiagnosticFactoryToRendererMap("Static Initialization") { + it.put( + POSSIBLE_INITIALIZATION_DEADLOCK, + "Possible initialization deadlock with ''{0}''.", + Renderer { classes -> classes.joinToString(transform = FqName::asString) }, + ) + it.put( + POSSIBLY_UNINITIALIZED_PROPERTY, + "Possibly uninitialized property ''{0}'' due to mutually dependent (direct or indirect) accesses ''{1}''.", + Renderer(FqName::asString), + Renderer { classes -> + if (classes.isEmpty()) "between the declarations of its containing class" + else classes.joinToString(prefix = "in ", transform = FqName::asString) + }, + ) + it.put( + POSSIBLY_UNINITIALIZED_ENUM_ENTRY, + "Possibly uninitialized enum entry ''{0}'' due to mutually dependent (direct or indirect) accesses ''{1}''.", + Renderer { enumEntrySymbol -> enumEntrySymbol.owner.name.asString() }, + Renderer { classes -> + if (classes.isEmpty()) "between the declarations of its containing class" + else classes.joinToString(prefix = "in ", transform = FqName::asString) + }, + ) + it.put( + ACCESSING_POSSIBLY_UNINITIALIZED_PROPERTY, + "The expression accesses (either directly or indirectly) the property ''{0}'' when it is possibly uninitialized.", + Renderer(FqName::asString), + ) + it.put( + ACCESSING_POSSIBLY_UNINITIALIZED_ENUM_ENTRY, + "The expression accesses (either directly or indirectly) the enum entry ''{0}'' when it is possibly uninitialized.", + Renderer { enumEntrySymbol -> enumEntrySymbol.owner.name.asString() }, + ) + it.put( + POSSIBLE_CYCLIC_ACCESS, + "The expression accesses (either directly or indirectly) the declaration ''{0}'' that is possibly uninitialized due to cyclic access in its own initializer.", + Renderer { declSymbol -> (declSymbol.owner as? IrDeclarationWithName)?.name?.asString() ?: "???" }, + ) + it.put( + ACCESSING_POSSIBLY_INACCESSIBLE_OBJECT_REFERENCE, + "The expression accesses (either directly or indirectly) the object ''{0}'' when it is not fully (statically) initialized (due to mutual static dependencies), any static access to its declarations may cause an NPE.", + Renderer(FqName::asString), + ) + it.put( + ACCESSING_DECLARATION_OF_POSSIBLY_INACCESSIBLE_CLASS, + "The expression accesses (either directly or indirectly) the declaration ''{1}'' of a class ''{0}'' when it is not fully statically initialized (due to mutual static dependencies), any static access to its declarations may cause an NPE.", + Renderer(FqName::asString), + Renderer { declSymbol -> declSymbol.owner.name.asString() }, + ) + it.put( + CONSTRUCTING_POSSIBLY_DEADLOCKING_CLASS, + "The constructor call creates possible static initialization deadlock due to mutual static dependencies of its constructing class ''{0}''.", + Renderer(FqName::asString), + ) + } + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/dsl/DependencyNodeBuilder.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/dsl/DependencyNodeBuilder.kt new file mode 100644 index 0000000..d8b5c3a --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/dsl/DependencyNodeBuilder.kt
@@ -0,0 +1,296 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.dsl + +import org.jetbrains.kotlin.initialization.plugin.model.AccessibleIndex +import org.jetbrains.kotlin.initialization.plugin.model.AnonymousInitializerIndex +import org.jetbrains.kotlin.initialization.plugin.model.BeginInstanceInitializationIndex +import org.jetbrains.kotlin.initialization.plugin.model.BeginStaticInitializationIndex +import org.jetbrains.kotlin.initialization.plugin.model.DependencyEdge +import org.jetbrains.kotlin.initialization.plugin.model.DependencyGraph +import org.jetbrains.kotlin.initialization.plugin.model.DependencyGraph.Companion.condenseCycles +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNode +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNodeIndex +import org.jetbrains.kotlin.initialization.plugin.model.EndInstanceInitializationIndex +import org.jetbrains.kotlin.initialization.plugin.model.EndStaticInitializationIndex +import org.jetbrains.kotlin.initialization.plugin.model.FunctionIndex +import org.jetbrains.kotlin.initialization.plugin.model.IsCalledBy +import org.jetbrains.kotlin.initialization.plugin.model.IsReferencedBy +import org.jetbrains.kotlin.initialization.plugin.model.MayHappenBefore +import org.jetbrains.kotlin.initialization.plugin.model.MustHappenBefore +import org.jetbrains.kotlin.initialization.plugin.model.PropertyIndex +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asFileEntity +import org.jetbrains.kotlin.initialization.plugin.util.beginInitializationIndex +import org.jetbrains.kotlin.ir.declarations.IrClass +import org.jetbrains.kotlin.ir.declarations.IrDeclaration +import org.jetbrains.kotlin.ir.declarations.IrEnumEntry +import org.jetbrains.kotlin.ir.declarations.IrFile +import org.jetbrains.kotlin.ir.declarations.IrSymbolOwner +import org.jetbrains.kotlin.ir.expressions.IrExpression +import org.jetbrains.kotlin.ir.symbols.IrBindableSymbol +import org.jetbrains.kotlin.ir.symbols.IrClassSymbol +import org.jetbrains.kotlin.ir.util.fileOrNull +import org.jetbrains.kotlin.ir.util.parentClassOrNull +import java.util.Deque +import java.util.LinkedList +import kotlin.sequences.forEach + +@DslMarker +annotation class DependencyGraphBuilderDsl + +inline fun DependencyGraph.buildGraph(worklist: Deque<DependencyNodeIndex>, init: DependencyGraphBuilder.() -> Unit) { + DependencyGraphBuilder(this, worklist).apply(init) +} + +class DependencyGraphBuilderContext(val dependencyGraph: DependencyGraph, val worklist: Deque<DependencyNodeIndex>) { + internal val dirtyNodes: MutableSet<DependencyNodeIndex> = mutableSetOf() + + fun reset() { + dirtyNodes.clear() + } +} + +@DependencyGraphBuilderDsl +sealed class DependencyNodeBuilder(internal val context: DependencyGraphBuilderContext) { + + val dependencyGraph: DependencyGraph get() = context.dependencyGraph + + val worklist: Deque<DependencyNodeIndex> get() = context.worklist + + fun DependencyNodeIndex.buildNode() { + context.dependencyGraph.getOrCreate(this) { + context.dirtyNodes += this + context.worklist.add(this) + } + } + + fun <D : IrDeclaration> IrBindableSymbol<*, D>.postponeFileEntity() { + val enclosingEntity = owner.fileOrNull?.asFileEntity() ?: return + worklist.add(enclosingEntity.beginInitializationIndex) + } + + fun IrClassSymbol.postponeInitSubgraph() { + worklist.add(beginInitializationIndex) + postponeFileEntity() + } + + fun IrClass.postponeInitSubgraph() = symbol.postponeInitSubgraph() + + private fun addEdge(edge: DependencyEdge): Boolean { + val addedFrom = context.dependencyGraph[edge.from]?.insertOutgoingEdge(edge) ?: false + val addedTo = context.dependencyGraph[edge.to]?.insertIncomingEdge(edge) ?: false + if (addedFrom) context.dirtyNodes += edge.from + if (addedTo) context.dirtyNodes += edge.to + return addedFrom || addedTo + } + + context(at: IrExpression?) + infix fun DependencyNodeIndex.calls(from: FunctionIndex<*>): Boolean = let { index -> + when { + from != index && from in context.dependencyGraph && index in context.dependencyGraph -> + addEdge(IsCalledBy(from, index, at)) + else -> false + } + } + + context(at: IrExpression?) + infix fun DependencyNodeIndex.references(from: AccessibleIndex): Boolean = let { index -> + when { + from != index && from in context.dependencyGraph && index in context.dependencyGraph -> + addEdge(IsReferencedBy(from, index, at)) + else -> false + } + } + + infix fun DependencyNodeIndex.mustHappenBefore(to: DependencyNodeIndex): Boolean = let { index -> + when { + index != to && index in context.dependencyGraph && to in context.dependencyGraph -> { + addEdge(MustHappenBefore(index, to)) + } + else -> false + } + } + + infix fun DependencyNodeIndex.mayHappenBefore(to: DependencyNodeIndex): Boolean = let { index -> + when { + index != to && index in context.dependencyGraph && to in context.dependencyGraph -> { + addEdge(MayHappenBefore(index, to)) + } + else -> false + } + } +} + +@DependencyGraphBuilderDsl +class DependencyGraphBuilder( + dependencyGraph: DependencyGraph, + worklist: Deque<DependencyNodeIndex> +) : DependencyNodeBuilder(DependencyGraphBuilderContext(dependencyGraph, worklist)) { + + inline fun <D : IrSymbolOwner, E : EnclosingEntity<D>> E.buildClinitSubgraph(crossinline init: StaticInitializationSubgraphBuilder<D, E>.() -> Unit = {}) { + // Build the subgraph using the initializer + StaticInitializationSubgraphBuilder(this@DependencyGraphBuilder, this).apply { + beginInitializationIndex.buildSubgraphNode() + init() + endInitializationIndex.buildSubgraphNode() + } + } + + inline fun IrClassSymbol.buildInitSubgraph(crossinline init: InstanceInitializationSubgraphBuilder.() -> Unit = {}) { + InstanceInitializationSubgraphBuilder(this@DependencyGraphBuilder, this).apply { + BeginInstanceInitializationIndex(this@buildInitSubgraph).buildSubgraphNode() + init() + EndInstanceInitializationIndex(this@buildInitSubgraph).buildSubgraphNode() + } + } + + /** + * Condenses the graph by removing multi-node strongly connected components and replacing them with composite nodes + */ + fun condenseGraph() { + if (context.dirtyNodes.isEmpty()) return + val queue = LinkedList<DependencyNode>() + + context(context.dependencyGraph) { + // Collect all forward reachable nodes from the marked dirty nodes + context.dirtyNodes.asSequence().mapNotNull(context.dependencyGraph::get).forEach(queue::add) + val forwardReachable = linkedSetOf<DependencyNode>() + while (queue.isNotEmpty()) { + val first = queue.pop() + if (forwardReachable.add(first)) { + first.happenAfter.forEach(queue::add) + } + } + + // Collect all backwards reachable nodes from the marked dirty nodes + context.dirtyNodes.asSequence().mapNotNull(context.dependencyGraph::get).forEach(queue::add) + val backwardReachable = linkedSetOf<DependencyNode>() + while (queue.isNotEmpty()) { + val first = queue.pop() + if (backwardReachable.add(first)) { + first.happenBefore.forEach(queue::add) + } + } + + // Consider only nodes that are reachable from both directions (dirtyNodes are subsumed by this), + // and condense any cycles that are formed + forwardReachable.intersect(backwardReachable).condenseCycles() + } + + // Clear the dirty nodes + context.reset() + } +} + +@DependencyGraphBuilderDsl +sealed class DependencySubgraphBuilder( + delegate: DependencyNodeBuilder, + startWith: DependencyNodeIndex +) : DependencyNodeBuilder(delegate.context) { + + private val outerSubgraphBuilder: DependencySubgraphBuilder? = delegate as? DependencySubgraphBuilder + var lastConstructedNode: DependencyNodeIndex = startWith + private set(value) { + field mustHappenBefore value + field = value + outerSubgraphBuilder?.lastConstructedNode = value + } + + protected fun buildSubgraphNode(node: DependencyNodeIndex) { + node.buildNode() + lastConstructedNode = node + } +} + +@DependencyGraphBuilderDsl +class StaticInitializationSubgraphBuilder<D : IrSymbolOwner, E : EnclosingEntity<D>>( + delegate: DependencyNodeBuilder, + val enclosingEntity: E +) : DependencySubgraphBuilder(delegate, enclosingEntity.beginInitializationIndex) { + + fun BeginStaticInitializationIndex<D>.buildSubgraphNode() { + require(enclosingEntity == this@StaticInitializationSubgraphBuilder.enclosingEntity) { + "The begin static initialization node $this must be constructed in the context of its enclosing entity ($enclosingEntity) and not ${this@StaticInitializationSubgraphBuilder.enclosingEntity}!" + } + buildSubgraphNode(this) + } + + fun EndStaticInitializationIndex<D>.buildSubgraphNode() { + require(enclosingEntity == this@StaticInitializationSubgraphBuilder.enclosingEntity) { + "The begin static initialization node $this must be constructed in the context of its enclosing entity ($enclosingEntity) and not ${this@StaticInitializationSubgraphBuilder.enclosingEntity}!" + } + buildSubgraphNode(this) + } + + fun PropertyIndex.buildSubgraphNode() { + require(enclosingEntity == this@StaticInitializationSubgraphBuilder.enclosingEntity) { + "The static property node $this must be constructed in the context of its enclosing entity ($enclosingEntity) and not ${this@StaticInitializationSubgraphBuilder.enclosingEntity}!" + } + buildSubgraphNode(this) + } + + fun AnonymousInitializerIndex.buildSubgraphNode() { + require(enclosingEntity == this@StaticInitializationSubgraphBuilder.enclosingEntity) { + "The static initializer node $this must be constructed in the context of its enclosing entity ($enclosingEntity) and not ${this@StaticInitializationSubgraphBuilder.enclosingEntity}!" + } + buildSubgraphNode(this) + } + + inline fun <D : IrSymbolOwner, E : EnclosingEntity<D>> E.buildNestedSubgraph(crossinline init: StaticInitializationSubgraphBuilder<D, E>.() -> Unit = {}) { + require(enclosingEntity == parentEnclosingEntity) { + "The given enclosing entity ($this) must directly nested under the outer entity ($enclosingEntity)!" + } + // Construct the subgraph's begin node already here, as it needs to be connected to the lastConstructedNode + StaticInitializationSubgraphBuilder(this@StaticInitializationSubgraphBuilder, this).apply { + beginInitializationIndex.buildSubgraphNode() + init() + endInitializationIndex.buildSubgraphNode() + } + } +} + +@DependencyGraphBuilderDsl +class InstanceInitializationSubgraphBuilder( + delegate: DependencyNodeBuilder, + val symbol: IrClassSymbol +) : DependencySubgraphBuilder(delegate, symbol.beginInitializationIndex) { + + fun BeginInstanceInitializationIndex.buildSubgraphNode() { + require(symbol == this@InstanceInitializationSubgraphBuilder.symbol) { + "The begin instance initialization node $this must be constructed in the context of its class ($symbol) and not ${this@InstanceInitializationSubgraphBuilder.symbol}!" + } + buildSubgraphNode(this) + } + + fun EndInstanceInitializationIndex.buildSubgraphNode() { + require(symbol == this@InstanceInitializationSubgraphBuilder.symbol) { + "The begin instance initialization node $this must be constructed in the context of its class ($symbol) and not ${this@InstanceInitializationSubgraphBuilder.symbol}!" + } + buildSubgraphNode(this) + } + + fun PropertyIndex.buildSubgraphNode() { + val containingClass = symbol.owner.parentClassOrNull?.symbol + require(containingClass == this@InstanceInitializationSubgraphBuilder.symbol) { + "The instance property node $this must be constructed in the context of its class ($containingClass) and not ${this@InstanceInitializationSubgraphBuilder.symbol}!" + } + buildSubgraphNode(this) + } + + fun AnonymousInitializerIndex.buildSubgraphNode() { + val containingClass = symbol.owner.parentClassOrNull?.symbol + require(containingClass == this@InstanceInitializationSubgraphBuilder.symbol) { + "The instance initializer node $this must be constructed in the context of its class ($containingClass) and not ${this@InstanceInitializationSubgraphBuilder.symbol}!" + } + buildSubgraphNode(this) + } +} + +typealias ClassSubgraphBuilder = StaticInitializationSubgraphBuilder<IrClass, EnclosingEntity.Class> +typealias ObjectSubgraphBuilder = StaticInitializationSubgraphBuilder<IrClass, EnclosingEntity.Object> +typealias EnumEntrySubgraphBuilder = StaticInitializationSubgraphBuilder<IrEnumEntry, EnclosingEntity.EnumEntry> +typealias FileSubgraphBuilder = StaticInitializationSubgraphBuilder<IrFile, EnclosingEntity.File>
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/CallSiteVisitor.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/CallSiteVisitor.kt new file mode 100644 index 0000000..dd53ab6 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/CallSiteVisitor.kt
@@ -0,0 +1,477 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.logic + +import org.jetbrains.kotlin.initialization.plugin.model.AccessibleIndex +import org.jetbrains.kotlin.initialization.plugin.model.DefaultedFunctionIndex +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNodeIndex +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNodeIndex.Companion.enclosingEntity +import org.jetbrains.kotlin.initialization.plugin.model.FunctionIndex +import org.jetbrains.kotlin.initialization.plugin.model.PropertyIndex +import org.jetbrains.kotlin.initialization.plugin.dsl.DependencyGraphBuilder +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asClassEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asEnumEntryEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asFileEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asObjectEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.isNotPrivate +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.parentEnclosingEntityOrSelf +import org.jetbrains.kotlin.initialization.plugin.util.contains +import org.jetbrains.kotlin.initialization.plugin.util.endInitializationIndex +import org.jetbrains.kotlin.ir.IrElement +import org.jetbrains.kotlin.ir.declarations.IrAnonymousInitializer +import org.jetbrains.kotlin.ir.declarations.IrConstructor +import org.jetbrains.kotlin.ir.declarations.IrDeclaration +import org.jetbrains.kotlin.ir.declarations.IrDeclarationOrigin +import org.jetbrains.kotlin.ir.declarations.IrField +import org.jetbrains.kotlin.ir.declarations.IrFunction +import org.jetbrains.kotlin.ir.declarations.IrModuleFragment +import org.jetbrains.kotlin.ir.declarations.IrOverridableDeclaration +import org.jetbrains.kotlin.ir.declarations.IrParameterKind +import org.jetbrains.kotlin.ir.declarations.IrProperty +import org.jetbrains.kotlin.ir.declarations.IrSimpleFunction +import org.jetbrains.kotlin.ir.expressions.IrBlock +import org.jetbrains.kotlin.ir.expressions.IrBlockBody +import org.jetbrains.kotlin.ir.expressions.IrBranch +import org.jetbrains.kotlin.ir.expressions.IrCall +import org.jetbrains.kotlin.ir.expressions.IrCatch +import org.jetbrains.kotlin.ir.expressions.IrConstructorCall +import org.jetbrains.kotlin.ir.expressions.IrDeclarationReference +import org.jetbrains.kotlin.ir.expressions.IrDelegatingConstructorCall +import org.jetbrains.kotlin.ir.expressions.IrEnumConstructorCall +import org.jetbrains.kotlin.ir.expressions.IrExpression +import org.jetbrains.kotlin.ir.expressions.IrExpressionBody +import org.jetbrains.kotlin.ir.expressions.IrFieldAccessExpression +import org.jetbrains.kotlin.ir.expressions.IrFunctionAccessExpression +import org.jetbrains.kotlin.ir.expressions.IrFunctionExpression +import org.jetbrains.kotlin.ir.expressions.IrGetEnumValue +import org.jetbrains.kotlin.ir.expressions.IrGetObjectValue +import org.jetbrains.kotlin.ir.expressions.IrGetValue +import org.jetbrains.kotlin.ir.expressions.IrLoop +import org.jetbrains.kotlin.ir.expressions.IrReturn +import org.jetbrains.kotlin.ir.expressions.IrSpreadElement +import org.jetbrains.kotlin.ir.expressions.IrStatementOrigin +import org.jetbrains.kotlin.ir.expressions.IrSuspendableExpression +import org.jetbrains.kotlin.ir.expressions.IrSuspensionPoint +import org.jetbrains.kotlin.ir.expressions.IrThrow +import org.jetbrains.kotlin.ir.expressions.IrTry +import org.jetbrains.kotlin.ir.expressions.IrTypeOperatorCall +import org.jetbrains.kotlin.ir.expressions.IrVararg +import org.jetbrains.kotlin.ir.expressions.IrWhen +import org.jetbrains.kotlin.ir.symbols.IrBindableSymbol +import org.jetbrains.kotlin.ir.symbols.IrClassSymbol +import org.jetbrains.kotlin.ir.symbols.IrFileSymbol +import org.jetbrains.kotlin.ir.symbols.IrFunctionSymbol +import org.jetbrains.kotlin.ir.symbols.IrValueParameterSymbol +import org.jetbrains.kotlin.ir.util.constructedClass +import org.jetbrains.kotlin.ir.util.fileOrNull +import org.jetbrains.kotlin.ir.util.isFunctionOrKFunction +import org.jetbrains.kotlin.ir.util.isFunctionalTypeInvoke +import org.jetbrains.kotlin.ir.util.isGetter +import org.jetbrains.kotlin.ir.util.isInlineParameter +import org.jetbrains.kotlin.ir.util.isTopLevel +import org.jetbrains.kotlin.ir.util.parentClassOrNull +import org.jetbrains.kotlin.ir.util.statements +import org.jetbrains.kotlin.ir.visitors.IrVisitor +import kotlin.collections.forEach +import kotlin.let + +internal class CallSiteVisitor( + private val module: IrModuleFragment, + private val visitedFiles: Set<IrFileSymbol>, + private val graphBuilder: DependencyGraphBuilder, +) : IrVisitor<Unit, CallSiteVisitor.CallSiteVisitContext>() { + + data class CallSiteVisitContext( + val accessingNode: DependencyNodeIndex, + val accessingEntity: EnclosingEntity<*>? = accessingNode.enclosingEntity, + val materializeOnlyConstructorArguments: Boolean = false + ) + + override fun visitElement(element: IrElement, data: CallSiteVisitContext): Unit = Unit + + private inline fun <D : IrDeclaration> D.visit( + data: CallSiteVisitContext, + crossinline symbolSupplier: (D) -> IrBindableSymbol<*, D>, + crossinline block: context(CallSiteVisitContext, D) DependencyGraphBuilder.() -> Unit + ) = when { + symbolSupplier(this) in module -> context(data, this@visit) { graphBuilder.block() } + else -> {} + } + + private inline fun <E : IrElement> E.visit( + data: CallSiteVisitContext, + crossinline block: context(CallSiteVisitContext, E) DependencyGraphBuilder.() -> Unit + ) = context(data, this@visit) { graphBuilder.block() } + + context(context: CallSiteVisitContext) + private fun IrElement.visitRecursively() = accept(this@CallSiteVisitor, context) + + private val <D : IrDeclaration> IrBindableSymbol<*, D>.inVisitedFiles: Boolean + get() = owner.fileOrNull?.let { it.symbol in visitedFiles } ?: false + + context(context: CallSiteVisitContext, reference: IrExpression?) + private fun DependencyGraphBuilder.referenceNode(node: AccessibleIndex) { + node.buildNode() + context.accessingNode references node + val possiblyInitializedEndNode = node.lazilyInitialized?.endInitializationIndex ?: return + if (context.accessingEntity?.parentEnclosingEntityOrSelf?.let { it != possiblyInitializedEndNode.enclosingEntity } ?: true) { + possiblyInitializedEndNode.buildNode() + possiblyInitializedEndNode mayHappenBefore context.accessingNode + } + } + + context(context: CallSiteVisitContext, callSite: IrExpression?) + private fun DependencyGraphBuilder.callNode(node: FunctionIndex<*>) { + node.buildNode() + if (!node.symbol.inVisitedFiles) node.symbol.postponeFileEntity() + context.accessingNode calls node + if (node !is FunctionIndex.Constructor) { + val enclosingEntity = node.lazilyInitialized?.parentEnclosingEntityOrSelf ?: return + val possiblyInitializedEndNode = enclosingEntity.endInitializationIndex + possiblyInitializedEndNode mayHappenBefore node + } + } + + override fun visitProperty(declaration: IrProperty, data: CallSiteVisitContext): Unit = declaration.visit(data) { + // Visit only the initializer + declaration.backingField?.visitRecursively() + } + + override fun visitField(declaration: IrField, data: CallSiteVisitContext): Unit = declaration.visit(data, IrField::symbol) { + declaration.initializer?.visitRecursively() + } + + override fun visitBlock(expression: IrBlock, data: CallSiteVisitContext): Unit = expression.visit(data) { + expression.statements.forEach { stmt -> stmt.visitRecursively() } + } + + override fun visitBlockBody(body: IrBlockBody, data: CallSiteVisitContext): Unit = body.visit(data) { + body.statements.forEach { it.visitRecursively() } + } + + override fun visitExpressionBody(body: IrExpressionBody, data: CallSiteVisitContext): Unit = body.visit(data) { + body.expression.visitRecursively() + } + + context(context: CallSiteVisitContext) + private val <D : IrFunction> IrBindableSymbol<*, D>.defaultParametersIfAny: Pair<DefaultedFunctionIndex<*>, List<IrValueParameterSymbol>>? + get() = when { + context.accessingNode is DefaultedFunctionIndex<*> && context.accessingNode.functionIndex.symbol == this -> + context.accessingNode to context.accessingNode.defaultParameters.mapNotNull { it.closestOverriddenDefaultParameter } + else -> null + } + + override fun visitFunction(declaration: IrFunction, data: CallSiteVisitContext): Unit = Unit + + override fun visitSimpleFunction(declaration: IrSimpleFunction, data: CallSiteVisitContext): Unit = + declaration.visit(data, IrSimpleFunction::symbol) { + val symbol = declaration.symbol + symbol.defaultParametersIfAny?.let { [defaultedIndex, defaultParameters] -> + // Add the known default values for missing parameters to the mapping + defaultParameters.forEach { it.owner.defaultValue?.visitRecursively() } + // Build the original function (with a non-existent call-site) + context(null) { callNode(defaultedIndex.functionIndex) } + } ?: declaration.body?.visitRecursively() + } + + override fun visitAnonymousInitializer(declaration: IrAnonymousInitializer, data: CallSiteVisitContext): Unit = + declaration.visit(data, IrAnonymousInitializer::symbol) { declaration.body.visitRecursively() } + + override fun visitConstructor(declaration: IrConstructor, data: CallSiteVisitContext): Unit = + declaration.visit(data, IrConstructor::symbol) { + declaration.symbol.defaultParametersIfAny?.let { [defaultedNode, defaultParameters] -> + defaultParameters.forEach { it.owner.defaultValue?.visitRecursively() } + context(null) { callNode(defaultedNode.functionIndex) } + return@visit + } + if (declaration.isPrimary && !data.materializeOnlyConstructorArguments) { + declaration.parentClassOrNull?.asClassEntity()?.let { classEntity -> + classEntity.endInitializationIndex mayHappenBefore data.accessingNode + } + } + val materializeEverythingContext = CallSiteVisitContext(data.accessingNode) + declaration.body?.statements?.forEach { statement -> + when (statement) { + is IrDelegatingConstructorCall -> statement.visitRecursively() + is IrBlock -> { + context(materializeEverythingContext) { + statement.statements.dropLast(1).forEach { it.visitRecursively() } + } + when (val last = statement.statements.lastOrNull()) { + null -> {} + is IrDelegatingConstructorCall -> last.visitRecursively() + else -> context(materializeEverythingContext) { last.visitRecursively() } + } + } + else -> context(materializeEverythingContext) { statement.visitRecursively() } + } + } + } + + context(context: CallSiteVisitContext, access: A) + private inline fun <D : IrOverridableDeclaration<S>, S : IrBindableSymbol<*, D>, A : IrDeclarationReference> DependencyGraphBuilder.accessNode( + symbol: S, + dispatchReceiverSupplier: D.(A) -> IrExpression? = { null }, + extensionReceiverSupplier: D.(A) -> IrExpression? = { null }, + superQualifierSupplier: (A) -> IrClassSymbol?, + crossinline staticAccess: context(CallSiteVisitContext, A) DependencyGraphBuilder.(S, EnclosingEntity<*>) -> Unit, + crossinline instanceAccess: context(CallSiteVisitContext, A) DependencyGraphBuilder.(S) -> Unit, + ) { + val realSymbols = when { + symbol.owner.isFakeOverride -> symbol.owner.overriddenSymbols.asSequence().flatMap { it.realOverridden() }.distinct() + else -> sequenceOf(symbol) + } + + realSymbols.forEach { symbol -> + // If the callable is an extension, visit the extension receiver for dependencies + symbol.owner.extensionReceiverSupplier(access)?.visitRecursively() + + // Compute the node to this callable based on the access' dispatch receiver + when (val receiver = symbol.owner.dispatchReceiverSupplier(access)) { + // `super.` access + null if superQualifierSupplier(access) != null -> + context.accessingEntity?.let { staticAccess(symbol, it) } ?: instanceAccess(symbol) + // top-level access + null if symbol.owner.isTopLevel -> symbol.owner.fileOrNull?.asFileEntity()?.let { staticAccess(symbol, it) } + // `this.` access (implicit or otherwise) + is IrGetValue if (receiver.symbol.owner.origin == IrDeclarationOrigin.INSTANCE_RECEIVER || receiver.origin == IrStatementOrigin.IMPLICIT_ARGUMENT) -> + context.accessingEntity?.let { staticAccess(symbol, it) } ?: instanceAccess(symbol) + // `A.` qualifier access + is IrGetObjectValue -> { + val enclosingEntity = receiver.symbol.asObjectEntity() ?: return + staticAccess(symbol, enclosingEntity) + } + // `E.ENTRY.` enum entry access + is IrGetEnumValue -> staticAccess(symbol, receiver.symbol.asEnumEntryEntity()) + // `e.` arbitrary access + is IrDeclarationReference -> { + // Receiver dependencies must be connected to the accessing node first + receiver.visitRecursively() + instanceAccess(symbol) + } + else -> return + } + } + } + + override fun visitGetObjectValue(expression: IrGetObjectValue, data: CallSiteVisitContext): Unit = expression.visit(data) { + if (expression.symbol !in module) return@visit + val objectEntity = expression.symbol.asObjectEntity() ?: return@visit + if (objectEntity.isNotPrivate) referenceNode(objectEntity.beginInitializationIndex) + if (!objectEntity.symbol.inVisitedFiles) objectEntity.symbol.postponeFileEntity() + } + + override fun visitGetEnumValue(expression: IrGetEnumValue, data: CallSiteVisitContext): Unit = expression.visit(data) { + if (expression.symbol !in module) return@visit + val enumEntryEntity = expression.symbol.asEnumEntryEntity() + referenceNode(enumEntryEntity.beginInitializationIndex) + if (enumEntryEntity.symbol.inVisitedFiles) enumEntryEntity.symbol.postponeFileEntity() + } + + private fun FunctionIndex<*>.defaultedOrSelf(parameters: Set<IrValueParameterSymbol>): FunctionIndex<*> = when (this) { + is DefaultedFunctionIndex -> this // ignore the input parameters for safety + else -> if (parameters.isNotEmpty()) DefaultedFunctionIndex(this, parameters) else this + } + + /** + * Visits arguments of the given function call + */ + context(context: CallSiteVisitContext, functionCall: T) + private fun <T : IrFunctionAccessExpression> DependencyGraphBuilder.visitArguments(symbol: IrFunctionSymbol) { + symbol.owner.parameters.zip(functionCall.arguments) { parameter, argument -> + if (parameter.kind == IrParameterKind.DispatchReceiver || parameter.kind == IrParameterKind.ExtensionReceiver) return@zip + if (parameter.isInlineParameter() && argument is IrFunctionExpression) { + callNode(FunctionIndex.Closure(argument.function.symbol)) + } else { + argument?.visitRecursively() + } + } + } + + private fun IrCall.propertyAccessFromReceiver(): Pair<IrField, IrFieldAccessExpression>? { + val receiver = (symbol.owner.parameters.find { it.kind == IrParameterKind.ExtensionReceiver }?.let(arguments::get) + ?: dispatchReceiver) as? IrFieldAccessExpression + ?: return null + return receiver.symbol.owner to receiver + } + + override fun visitCall(expression: IrCall, data: CallSiteVisitContext): Unit = + expression.visit(data) { + val symbol = expression.symbol + visitArguments(symbol) + if (symbol !in module) return@visit + if (symbol.isFunctionalTypeInvoke) { + expression.propertyAccessFromReceiver()?.let { [field, access] -> + // Consider only property-based fields + val property = field.correspondingPropertySymbol?.owner ?: return@let + // Consider only vals and fields with functional return type + if (property.isVar || property.getter?.returnType?.isFunctionOrKFunction() != true) return@let + accessNode( + symbol = property.symbol, + dispatchReceiverSupplier = { access.receiver }, + superQualifierSupplier = { access.superQualifierSymbol }, + staticAccess = staticAccess@{ propertySymbol, receiverEntity -> + val propertyNode = PropertyIndex(propertySymbol, receiverEntity) + val closure = propertyNode.initializedClosure ?: return@staticAccess + callNode(closure) + }, + instanceAccess = instanceAccess@{ propertySymbol -> + val propertyNode = PropertyIndex(propertySymbol) + val closure = propertyNode.initializedClosure ?: return@instanceAccess + // Here the property is directly accessed and it is immediately invoked, so no aliasing + val constructedClass = propertySymbol.owner.parentClassOrNull?.symbol ?: return@instanceAccess + constructedClass.postponeInitSubgraph() + val endNode = constructedClass.endInitializationIndex + endNode.buildNode() + callNode(closure) + endNode mayHappenBefore closure + } + ) + return@visit + } + } + + val defaultParameters = symbol.owner.parameters.zip(expression.arguments) { parameter, argument -> + if (argument == null) parameter.symbol else null + }.filterNotNull().toSet() + if (symbol.owner.correspondingPropertySymbol?.owner?.let { it.isVar || !symbol.owner.isGetter && defaultParameters.isNotEmpty() } == true) return@visit + accessNode( + symbol = symbol, + dispatchReceiverSupplier = { it.dispatchReceiver }, + extensionReceiverSupplier = { access -> + parameters.find { it.kind == IrParameterKind.ExtensionReceiver }?.indexInParameters?.let(access.arguments::get) + }, + superQualifierSupplier = IrCall::superQualifierSymbol, + staticAccess = staticAccess@{ functionSymbol, receiverEntity -> + functionSymbol.owner.correspondingPropertySymbol?.owner?.let { property -> + val propertyNode = PropertyIndex(property.symbol, receiverEntity) + when { + functionSymbol.owner.origin == IrDeclarationOrigin.DEFAULT_PROPERTY_ACCESSOR && propertyNode.hasInitializer -> + referenceNode(propertyNode) + else -> propertyNode.getter?.let { callNode(it) } + } + } ?: callNode(FunctionIndex.MemberFunction(functionSymbol, receiverEntity).defaultedOrSelf(defaultParameters)) + }, + instanceAccess = instanceAccess@{ functionSymbol -> + val constructedClass = functionSymbol.owner.parentClassOrNull?.symbol ?: return@instanceAccess + constructedClass.postponeInitSubgraph() + val endNode = constructedClass.endInitializationIndex + endNode.buildNode() + functionSymbol.owner.correspondingPropertySymbol?.owner?.let { property -> + val propertyNode = PropertyIndex(property.symbol) + when { + functionSymbol.owner.origin == IrDeclarationOrigin.DEFAULT_PROPERTY_ACCESSOR && propertyNode.hasInitializer -> { + referenceNode(propertyNode) + endNode mayHappenBefore contextOf<CallSiteVisitContext>().accessingNode + } + else -> propertyNode.getter?.let { + callNode(it) + endNode mayHappenBefore it + } + } + } ?: run { + val functionNode = FunctionIndex.MemberFunction(functionSymbol).defaultedOrSelf(defaultParameters) + callNode(functionNode) + endNode mayHappenBefore functionNode + } + } + ) + if (!symbol.inVisitedFiles) symbol.postponeFileEntity() + } + + override fun visitConstructorCall(expression: IrConstructorCall, data: CallSiteVisitContext): Unit = expression.visit(data) { + val symbol = expression.symbol + visitArguments(symbol) + if (symbol !in module) return@visit + // Prevent from creating dependencies for nested enclosing entities that extend their outer class, since it creates unwanted cycles + if (symbol.owner.constructedClass.asClassEntity() == data.accessingEntity?.parentEnclosingEntity) return@visit + val defaultParameters = symbol.owner.parameters.zip(expression.arguments) { parameter, argument -> + if (argument == null) parameter.symbol else null + }.filterNotNull().toSet() + callNode(FunctionIndex.Constructor(symbol).defaultedOrSelf(defaultParameters)) + if (!symbol.inVisitedFiles) symbol.postponeFileEntity() + } + + override fun visitDelegatingConstructorCall(expression: IrDelegatingConstructorCall, data: CallSiteVisitContext): Unit = + expression.visit(data) { + val symbol = expression.symbol + visitArguments(symbol) + if (symbol !in module) return@visit + val defaultParameters = symbol.owner.parameters.zip(expression.arguments) { parameter, argument -> + if (argument == null) parameter.symbol else null + }.filterNotNull().toSet() + if (data.materializeOnlyConstructorArguments) { + // Default parameters are independent expressions + context(CallSiteVisitContext(data.accessingNode)) { + defaultParameters.forEach { it.closestOverriddenDefaultParameter?.owner?.defaultValue?.visitRecursively() } + } + // The only way to properly materialize the edges to the accessing node is to fully recurse into the construction call chain + symbol.owner.visitRecursively() + } else { + callNode(FunctionIndex.Constructor(symbol).defaultedOrSelf(defaultParameters)) + } + } + + override fun visitEnumConstructorCall(expression: IrEnumConstructorCall, data: CallSiteVisitContext) = expression.visit(data) { + visitArguments(expression.symbol) + } + + override fun visitCatch(aCatch: IrCatch, data: CallSiteVisitContext): Unit = aCatch.visit(data) { + aCatch.result.visitRecursively() + } + + override fun visitBranch(branch: IrBranch, data: CallSiteVisitContext): Unit = branch.visit(data) { + branch.condition.visitRecursively() + branch.result.visitRecursively() + } + + override fun visitLoop(loop: IrLoop, data: CallSiteVisitContext): Unit = loop.visit(data) { + loop.condition.visitRecursively() + loop.body?.visitRecursively() + } + + override fun visitTypeOperator(expression: IrTypeOperatorCall, data: CallSiteVisitContext): Unit = expression.visit(data) { + expression.argument.visitRecursively() + } + + override fun visitVararg(expression: IrVararg, data: CallSiteVisitContext): Unit = expression.visit(data) { + expression.elements.forEach { it.visitRecursively() } + } + + override fun visitReturn(expression: IrReturn, data: CallSiteVisitContext): Unit = expression.visit(data) { + expression.value.visitRecursively() + } + + override fun visitSpreadElement(spread: IrSpreadElement, data: CallSiteVisitContext): Unit = spread.visit(data) { + spread.expression.visitRecursively() + } + + override fun visitSuspendableExpression(expression: IrSuspendableExpression, data: CallSiteVisitContext): Unit = + expression.visit(data) { + expression.suspensionPointId.visitRecursively() + expression.result.visitRecursively() + } + + override fun visitSuspensionPoint(expression: IrSuspensionPoint, data: CallSiteVisitContext): Unit = expression.visit(data) { + expression.result.visitRecursively() + expression.resumeResult.visitRecursively() + } + + override fun visitThrow(expression: IrThrow, data: CallSiteVisitContext): Unit = expression.visit(data) { + expression.value.visitRecursively() + } + + override fun visitTry(aTry: IrTry, data: CallSiteVisitContext): Unit = aTry.visit(data) { + aTry.tryResult.visitRecursively() + aTry.catches.forEach { it.visitRecursively() } + aTry.finallyExpression?.visitRecursively() + } + + override fun visitWhen(expression: IrWhen, data: CallSiteVisitContext): Unit = expression.visit(data) { + expression.branches.forEach { it.visitRecursively() } + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/DefaultFunctionParametersCollector.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/DefaultFunctionParametersCollector.kt new file mode 100644 index 0000000..e4074c4 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/DefaultFunctionParametersCollector.kt
@@ -0,0 +1,69 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.logic + +import org.jetbrains.kotlin.backend.common.extensions.IrGenerationExtension +import org.jetbrains.kotlin.backend.common.extensions.IrPluginContext +import org.jetbrains.kotlin.initialization.plugin.util.PathCompressingAncestorMap +import org.jetbrains.kotlin.ir.IrElement +import org.jetbrains.kotlin.ir.declarations.IrConstructor +import org.jetbrains.kotlin.ir.declarations.IrFile +import org.jetbrains.kotlin.ir.declarations.IrModuleFragment +import org.jetbrains.kotlin.ir.declarations.IrSimpleFunction +import org.jetbrains.kotlin.ir.declarations.IrValueParameter +import org.jetbrains.kotlin.ir.irAttribute +import org.jetbrains.kotlin.ir.symbols.IrSimpleFunctionSymbol +import org.jetbrains.kotlin.ir.symbols.IrValueParameterSymbol +import org.jetbrains.kotlin.ir.visitors.IrVisitorVoid +import org.jetbrains.kotlin.ir.visitors.acceptChildrenVoid +import org.jetbrains.kotlin.ir.visitors.acceptVoid + +private var IrValueParameter.closestOverriddenDefaultParameter: IrValueParameterSymbol? by irAttribute(copyByDefault = false) + +val IrValueParameterSymbol.closestOverriddenDefaultParameter: IrValueParameterSymbol? get() = owner.closestOverriddenDefaultParameter + +object DefaultFunctionParametersCollector : IrGenerationExtension { + override fun generate(moduleFragment: IrModuleFragment, pluginContext: IrPluginContext) { + moduleFragment.files.forEach { file -> + file.acceptVoid(object : IrVisitorVoid() { + + private val rootOverriddenFunctionFinder = PathCompressingAncestorMap<IrSimpleFunctionSymbol> { element -> + element.owner.overriddenSymbols.asSequence().flatMap { it.realOverridden() }.distinct() + } + + private val IrSimpleFunction.rootOverriddenFunctions: Set<IrSimpleFunctionSymbol> + get() = rootOverriddenFunctionFinder[symbol] + + private fun IrSimpleFunctionSymbol.propagateDefaultParameters(parameterMap: MutableMap<Int, IrValueParameterSymbol> = mutableMapOf()) { + owner.parameters.forEachIndexed { index, parameter -> + if (parameter.defaultValue != null) parameterMap[index] = parameter.symbol + if (index in parameterMap) parameter.closestOverriddenDefaultParameter = parameterMap[index] + } + overridingFunctions?.forEach { it.propagateDefaultParameters(parameterMap.toMutableMap()) } + } + + override fun visitElement(element: IrElement): Unit = element.acceptChildrenVoid(this) + + override fun visitFile(declaration: IrFile) { + super.visitFile(declaration) + rootOverriddenFunctionFinder.reset() + } + + override fun visitSimpleFunction(declaration: IrSimpleFunction) { + val rootFunctions = declaration.rootOverriddenFunctions + rootFunctions.forEach { it.propagateDefaultParameters() } + } + + override fun visitConstructor(declaration: IrConstructor) { + // Constructors cannot be overridden, so the default parameters can only come from the actual declaration itself + declaration.parameters.forEach { + if (it.defaultValue != null) it.closestOverriddenDefaultParameter = it.symbol + } + } + }) + } + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/DependencyGraphResolver.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/DependencyGraphResolver.kt new file mode 100644 index 0000000..7f7777f --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/DependencyGraphResolver.kt
@@ -0,0 +1,333 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.logic + +import org.jetbrains.kotlin.initialization.plugin.model.AnonymousInitializerIndex +import org.jetbrains.kotlin.initialization.plugin.model.BeginInstanceInitializationIndex +import org.jetbrains.kotlin.initialization.plugin.model.ClinitIndex +import org.jetbrains.kotlin.initialization.plugin.model.DeclarationIndex +import org.jetbrains.kotlin.initialization.plugin.model.DependencyGraph +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNodeIndex +import org.jetbrains.kotlin.initialization.plugin.model.EnumEntryIndex +import org.jetbrains.kotlin.initialization.plugin.model.PropertyIndex +import org.jetbrains.kotlin.initialization.plugin.model.QualifierIndex +import org.jetbrains.kotlin.initialization.plugin.model.TopLevelIndex +import org.jetbrains.kotlin.initialization.plugin.dsl.ClassSubgraphBuilder +import org.jetbrains.kotlin.initialization.plugin.dsl.DependencyGraphBuilder +import org.jetbrains.kotlin.initialization.plugin.dsl.DependencyNodeBuilder +import org.jetbrains.kotlin.initialization.plugin.dsl.ObjectSubgraphBuilder +import org.jetbrains.kotlin.initialization.plugin.dsl.StaticInitializationSubgraphBuilder +import org.jetbrains.kotlin.initialization.plugin.dsl.buildGraph +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asClassEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asEnumEntryEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asFileEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asObjectEntity +import org.jetbrains.kotlin.initialization.plugin.util.contains +import org.jetbrains.kotlin.initialization.plugin.util.endInitializationIndex +import org.jetbrains.kotlin.initialization.plugin.util.isInitializedBySupertypes +import org.jetbrains.kotlin.descriptors.ClassKind +import org.jetbrains.kotlin.descriptors.isObject +import org.jetbrains.kotlin.fir.util.BaseMultimap +import org.jetbrains.kotlin.ir.declarations.IrAnonymousInitializer +import org.jetbrains.kotlin.ir.declarations.IrClass +import org.jetbrains.kotlin.ir.declarations.IrDeclaration +import org.jetbrains.kotlin.ir.declarations.IrEnumEntry +import org.jetbrains.kotlin.ir.declarations.IrFile +import org.jetbrains.kotlin.ir.declarations.IrProperty +import org.jetbrains.kotlin.ir.expressions.IrSyntheticBody +import org.jetbrains.kotlin.ir.symbols.IrClassSymbol +import org.jetbrains.kotlin.ir.symbols.IrFileSymbol +import org.jetbrains.kotlin.ir.types.classOrNull +import org.jetbrains.kotlin.ir.util.fileOrNull +import org.jetbrains.kotlin.ir.util.isLocal +import org.jetbrains.kotlin.ir.util.isTopLevel +import org.jetbrains.kotlin.ir.util.parentClassOrNull +import org.jetbrains.kotlin.ir.util.primaryConstructor +import org.jetbrains.kotlin.ir.util.superClass +import java.util.LinkedList +import kotlin.collections.forEach +import kotlin.sequences.forEach + +class DependencyGraphResolver(val dependencyGraph: DependencyGraph) { + + private val module get() = dependencyGraph.module + + private val visitedFiles = mutableSetOf<IrFileSymbol>() + + private val worklist = LinkedList<DependencyNodeIndex>() + + private val processed = mutableSetOf<DependencyNodeIndex>() + + private val pendingNodes = + object : BaseMultimap<IrFileSymbol, DependencyNodeIndex, List<DependencyNodeIndex>, MutableList<DependencyNodeIndex>>() { + override fun createContainer(): MutableList<DependencyNodeIndex> = LinkedList() + override fun createEmptyContainer(): List<DependencyNodeIndex> = emptyList() + } + + /** + * Connects the subgraph of this entity (at its begin node) with an incoming happens-before edge to the subgraphs of its supertypes + * + * The supertypes connected to this entity are those which are directly initialized due to initialization of this entity, i.e., + * classes and interfaces with default methods. In cases where the supertype has no static declarations, we recurse into its supertypes + * to and connect to those instead + */ + private fun StaticInitializationSubgraphBuilder<*, *>.initializeDirectSupertypes(classSymbol: IrClassSymbol) { + classSymbol.owner.superTypes.forEach { superType -> + val symbol = superType.classOrNull ?: return@forEach + // Skip library supertypes, as they cannot have mutual dependencies with the source types, interface types without + // default methods, and types which are declared outside the current module + if (symbol !in module || !symbol.isInitializedBySupertypes) return@forEach + val supertypeEntity = symbol.asClassEntity() + // We do not need to visit the supertype here, as it was either already visited + // or will be visited later (in this file or in a subseqently visited one) + val endNode = supertypeEntity.endInitializationIndex + endNode.buildNode() + endNode mustHappenBefore enclosingEntity.beginInitializationIndex + } + } + + /** + * Retrieves all declarations that are initialized in order of declaration and in the order of initialization of the given class' + * supertypes. + * + * For the sake of optimization, the resulting sequence excludes all library declarations that have been overridden by the given + * class (or transitively by its supertypes) + */ + private fun IrClassSymbol.collectInitializedDeclarations(): Sequence<IrDeclaration> = sequence { + // Prevent visiting classes that belong to a library, belong to a different module, are interfaces, or are annotation classes + if (this@collectInitializedDeclarations !in dependencyGraph.module || owner.kind == ClassKind.INTERFACE || owner.kind == ClassKind.ANNOTATION_CLASS) return@sequence + + // Populate the declared declarations (properties and init blocks), and overridden properties + // The declarations are collected recursively, respecting JVM's initialization rules + // JVMS25 (5.5.7): + // ... if C is a class rather than an interface, then let SC be its superclass and let SI1, ..., SIn be all superinterfaces of C + // (whether direct or indirect) that declare at least one non-abstract, non-static method. The order of superinterfaces is given + // by a recursive enumeration over the superinterface hierarchy of each interface directly implemented by C. For each interface I + // directly implemented by C (in the order of the interfaces array of C), the enumeration recurs on I's superinterfaces (in the + // order of the interfaces array of I) before returning I. ... + + // We do not need to enumerate the supertype hierarchy recursively because it is equivalent as recursively calling the cache + // on each directly implemented supertype + owner.superClass?.let { yieldAll(it.symbol.collectInitializedDeclarations()) } + + yieldAll(owner.declarations.asSequence().filter { + it is IrProperty && it.backingField?.initializer != null || it is IrAnonymousInitializer + }) + } + + private fun DependencyNodeBuilder.postponeClassEntity(classSymbol: IrClassSymbol) { + val enclosingEntity = when { + classSymbol.owner.kind.isObject -> classSymbol.asObjectEntity() + else -> classSymbol.asClassEntity() + } ?: return + worklist.add(enclosingEntity.beginInitializationIndex) + } + + private fun DependencyNodeBuilder.postponeClassEntity(classDeclaration: IrClass) = + postponeClassEntity(classDeclaration.symbol) + + fun collectDependencies(file: IrFile): List<DependencyNodeIndex> { + // Skip files outside the current module and already visited files + if (file !in dependencyGraph.module || !visitedFiles.add(file.symbol)) return pendingNodes.removeKey(file.symbol) + + dependencyGraph.buildGraph(worklist) { + val callSiteVisitor = CallSiteVisitor( + module = dependencyGraph.module, + visitedFiles = visitedFiles, + graphBuilder = this + ) + + // Collect reachable roots from the given file + buildFileEntity(file) + + while (worklist.isNotEmpty()) { + val current = worklist.removeFirst() + if (processed.add(current)) { + when (current) { + is TopLevelIndex if visitedFiles.add(current.enclosingEntity.symbol) -> + buildFileEntity(current.enclosingEntity.symbol.owner) + is ClinitIndex -> { + buildClassEntity(current.enclosingEntity) + val containingFile = current.containingFile ?: continue + pendingNodes.put(containingFile.symbol, current) + } + is QualifierIndex -> { + buildObjectEntity(current.enclosingEntity) + val constructor = current.enclosingEntity.symbol.owner.primaryConstructor ?: continue + constructor.accept(callSiteVisitor, CallSiteVisitor.CallSiteVisitContext(current, null, true)) + val containingFile = current.containingFile ?: continue + pendingNodes.put(containingFile.symbol, current) + } + is EnumEntryIndex -> { + val constructor = current.enclosingEntity.symbol.owner.correspondingClass?.primaryConstructor ?: continue + constructor.accept( + callSiteVisitor, + CallSiteVisitor.CallSiteVisitContext(current, current.enclosingEntity, true) + ) + val containingFile = current.containingFile ?: continue + pendingNodes.put(containingFile.symbol, current) + } + is PropertyIndex -> { + val propertySymbol = current.symbol + propertySymbol.owner.accept( + callSiteVisitor, + CallSiteVisitor.CallSiteVisitContext(current, current.enclosingEntity) + ) + val containingDeclaration = propertySymbol.owner.let { + when { + propertySymbol.owner.isTopLevel -> it.fileOrNull?.symbol + else -> it.parentClassOrNull?.symbol + } + } + if (containingDeclaration == current.enclosingEntity?.symbol) { + val containingFile = current.containingFile ?: continue + pendingNodes.put(containingFile.symbol, current) + } + } + is AnonymousInitializerIndex -> { + val initializedSymbol = current.symbol + initializedSymbol.owner.accept( + callSiteVisitor, + CallSiteVisitor.CallSiteVisitContext(current, current.enclosingEntity) + ) + val containingClass = current.symbol.owner.parentClassOrNull?.symbol ?: continue + if (containingClass == current.enclosingEntity?.symbol) { + val containingFile = current.containingFile ?: continue + pendingNodes.put(containingFile.symbol, current) + } + } + is DeclarationIndex<*> -> { + current.symbol.owner.accept(callSiteVisitor, CallSiteVisitor.CallSiteVisitContext(current)) + } + is BeginInstanceInitializationIndex -> { + current.symbol.buildInitSubgraph { + symbol.owner.superClass?.takeIf { it in module }?.symbol?.let { superClass -> + val endNode = superClass.endInitializationIndex + endNode.buildNode() + endNode mustHappenBefore lastConstructedNode + superClass.postponeInitSubgraph() + } + // Find "relatively" static initialized declarations of the instance class, + // i.e., the declarations which have the same value for each instance + symbol.owner.declarations.forEach { + when (it) { + is IrProperty if it.backingField?.initializer != null -> PropertyIndex(it.symbol).buildSubgraphNode() + is IrAnonymousInitializer -> AnonymousInitializerIndex(it.symbol).buildSubgraphNode() + } + } + } + } + else -> {} + } + } + } + + // Condense the graph + condenseGraph() + } + + return pendingNodes.removeKey(file.symbol) + } + + private fun DependencyGraphBuilder.buildFileEntity(file: IrFile) { + val enclosingEntity = file.symbol.asFileEntity() + enclosingEntity.buildClinitSubgraph { + file.declarations.forEach { decl -> + when (decl) { + is IrProperty -> buildProperty(decl) + // JVM initialization of the file's class does not initialize the classes declared inside it. + // Hence, they will not be connected to the file's happens-before subgraph + is IrClass -> postponeClassEntity(decl) + else -> {} + } + } + } + } + + private fun ObjectSubgraphBuilder.buildObjectSubgraphNodes() { + val objectSymbol = enclosingEntity.symbol + initializeDirectSupertypes(objectSymbol) + // Build all initialized declarations (declared or inherited) + objectSymbol.collectInitializedDeclarations().forEach { + when (it) { + is IrProperty -> buildProperty(it) + is IrAnonymousInitializer -> buildAnonymousInitializer(it) + else -> {} + } + } + // Find entities declared inside it + objectSymbol.owner.declarations.forEach { decl -> + when (decl) { + is IrClass -> postponeClassEntity(decl) + else -> {} + } + } + } + + private fun DependencyGraphBuilder.buildObjectEntity(enclosingEntity: EnclosingEntity.Object) = enclosingEntity.buildClinitSubgraph { + buildObjectSubgraphNodes() + } + + private fun ClassSubgraphBuilder.buildCompanionObjectEntity(companionObject: EnclosingEntity.Object) = + companionObject.buildNestedSubgraph { + buildObjectSubgraphNodes() + } + + private fun DependencyGraphBuilder.buildClassEntity(enclosingEntity: EnclosingEntity.Class) { + val classSymbol = enclosingEntity.symbol + enclosingEntity.buildClinitSubgraph { + initializeDirectSupertypes(classSymbol) + // Store the companion object declaration just in case it appears in the declaration list before enum entries, due to serialization + var companionObjectEntity: EnclosingEntity.Object? = null + enclosingEntity.symbol.owner.declarations.forEach { decl -> + when (decl) { + is IrProperty if decl.getter?.body is IrSyntheticBody -> buildProperty(decl) + is IrEnumEntry -> buildEnumEntryEntity(decl.asEnumEntryEntity()) + // Only companion objects will connect to this happens-before subgraph + is IrClass if decl.kind.isObject && decl.isCompanion -> + companionObjectEntity = decl.asObjectEntity() + is IrClass -> postponeClassEntity(decl) + else -> {} + } + } + // Build the companion object subgraph according to the declaration order of Kotlin's JVM compilation + companionObjectEntity?.let { buildCompanionObjectEntity(it) } + } + } + + private fun ClassSubgraphBuilder.buildEnumEntryEntity(enclosingEntity: EnclosingEntity.EnumEntry) { + require(enclosingEntity.parentEnclosingEntity == this@buildEnumEntryEntity.enclosingEntity) { "The provided outer entity must match the enum entry's parent!" } + enclosingEntity.buildNestedSubgraph { + val symbol = enclosingEntity.symbol.owner.correspondingClass?.symbol ?: enclosingEntity.parentEnclosingEntity.symbol + symbol.collectInitializedDeclarations().forEach { + when (it) { + is IrProperty -> buildProperty(it) + is IrAnonymousInitializer -> buildAnonymousInitializer(it) + // NOTE: no classifiers should be accessible from an enum entry's anonymous object, as the enum entry + // has the type of its (parent) enum class + else -> {} + } + } + } + } + + private fun StaticInitializationSubgraphBuilder<*, *>.buildProperty(property: IrProperty) { + if (!property.isLocal && !property.isVar && property.backingField?.initializer != null) { + PropertyIndex(property.symbol, enclosingEntity).buildSubgraphNode() + } + } + + private fun StaticInitializationSubgraphBuilder<*, *>.buildAnonymousInitializer(initializer: IrAnonymousInitializer) = + AnonymousInitializerIndex(initializer.symbol, enclosingEntity).buildSubgraphNode() + + fun clear() { + visitedFiles.clear() + processed.clear() + } +} + +
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/OverridingCallablesCollector.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/OverridingCallablesCollector.kt new file mode 100644 index 0000000..6272806 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/logic/OverridingCallablesCollector.kt
@@ -0,0 +1,77 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.logic + +import org.jetbrains.kotlin.backend.common.extensions.IrGenerationExtension +import org.jetbrains.kotlin.backend.common.extensions.IrPluginContext +import org.jetbrains.kotlin.descriptors.Modality +import org.jetbrains.kotlin.initialization.plugin.util.traversal +import org.jetbrains.kotlin.ir.IrElement +import org.jetbrains.kotlin.ir.declarations.IrModuleFragment +import org.jetbrains.kotlin.ir.declarations.IrOverridableDeclaration +import org.jetbrains.kotlin.ir.declarations.IrProperty +import org.jetbrains.kotlin.ir.declarations.IrSimpleFunction +import org.jetbrains.kotlin.ir.irAttribute +import org.jetbrains.kotlin.ir.symbols.IrBindableSymbol +import org.jetbrains.kotlin.ir.symbols.IrPropertySymbol +import org.jetbrains.kotlin.ir.symbols.IrSimpleFunctionSymbol +import org.jetbrains.kotlin.ir.visitors.IrVisitorVoid +import org.jetbrains.kotlin.ir.visitors.acceptChildrenVoid +import org.jetbrains.kotlin.ir.visitors.acceptVoid + +private var <S : IrBindableSymbol<*, D>, D : IrOverridableDeclaration<S>> D.overridingCallables: MutableSet<S>? by irAttribute(copyByDefault = false) + +val <S : IrBindableSymbol<*, D>, D : IrOverridableDeclaration<S>> S.overridingCallables: Set<S>? get() = owner.overridingCallables + +val IrPropertySymbol.overridingProperties: Set<IrPropertySymbol>? get() = overridingCallables + +val IrSimpleFunctionSymbol.overridingFunctions: Set<IrSimpleFunctionSymbol>? get() = overridingCallables + +fun <S : IrBindableSymbol<*, D>, D : IrOverridableDeclaration<S>> D.realOverridden(): Sequence<S> = + traversal(this) { decl -> + if (!decl.isFakeOverride) emit(decl.symbol) + else decl.overriddenSymbols.forEach { traverseFor(it.owner) } + } + +fun <S : IrBindableSymbol<*, D>, D : IrOverridableDeclaration<S>> S.realOverridden(): Sequence<S> = owner.realOverridden() + +fun <S : IrBindableSymbol<*, D>, D : IrOverridableDeclaration<S>> D.overrides(): Sequence<S> = + if (isFakeOverride) realOverridden().distinct().flatMap { it.owner.overrides() }.distinct() + else traversal(this) { decl -> + decl.overridingCallables?.forEach { + if (it.owner.modality != Modality.ABSTRACT) emit(it) + traverseFor(it.owner) + } + } + +fun <S : IrBindableSymbol<*, D>, D : IrOverridableDeclaration<S>> S.overrides(): Sequence<S> = owner.overrides() + +object OverridingCallablesCollector : IrGenerationExtension { + + private fun <S : IrBindableSymbol<*, D>, D : IrOverridableDeclaration<S>> D.addOverrideToOverriddenCallables() { + if (isFakeOverride) return + else { + overridingCallables = mutableSetOf() + overriddenSymbols.flatMap { it.realOverridden() }.distinct().forEach { overridden -> + overridden.owner.overridingCallables = overridden.owner.overridingCallables?.apply { this += symbol } + ?: mutableSetOf(symbol) + } + } + } + + override fun generate(moduleFragment: IrModuleFragment, pluginContext: IrPluginContext) { + moduleFragment.files.forEach { file -> + file.acceptVoid(object : IrVisitorVoid() { + + override fun visitElement(element: IrElement): Unit = element.acceptChildrenVoid(this) + + override fun visitSimpleFunction(declaration: IrSimpleFunction) = declaration.addOverrideToOverriddenCallables() + + override fun visitProperty(declaration: IrProperty) = declaration.addOverrideToOverriddenCallables() + }) + } + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyEdge.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyEdge.kt new file mode 100644 index 0000000..c9561b1 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyEdge.kt
@@ -0,0 +1,121 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.model + +import org.jetbrains.kotlin.ir.IrElement +import org.jetbrains.kotlin.utils.SmartSet +import org.jetbrains.kotlin.utils.addIfNotNull + +sealed interface DependencyEdge { + + val from: DependencyNodeIndex + + val to: DependencyNodeIndex + + fun merge(other: DependencyEdge): DependencyEdge? + + companion object { + operator fun DependencyEdge.component1(): DependencyNodeIndex = from + operator fun DependencyEdge.component2(): DependencyNodeIndex = to + } +} + +sealed interface InformationEdge : DependencyEdge { + override val from: AccessibleIndex + + val accessSources: Set<IrElement> + + override fun merge(other: DependencyEdge): InformationEdge? + + companion object { + operator fun InformationEdge.component1(): AccessibleIndex = from + operator fun InformationEdge.component3(): Set<IrElement> = accessSources + } +} + +sealed interface HappensBeforeEdge : DependencyEdge { + val holdsInAllExecutions: Boolean get() = false + + override fun merge(other: DependencyEdge): HappensBeforeEdge? +} + +data class IsReferencedBy( + override val from: AccessibleIndex, + override val to: DependencyNodeIndex, + override val accessSources: Set<IrElement> = emptySet(), +) : InformationEdge { + constructor(from: AccessibleIndex, to: DependencyNodeIndex, accessSource: IrElement?) : this( + from = from, + to = to, + accessSources = SmartSet.create<IrElement>().also { it.addIfNotNull(accessSource) } + ) + + override fun merge(other: DependencyEdge): IsReferencedBy? { + if (other !is IsReferencedBy) return null + return when { + from == other.from && to == other.to -> copy(accessSources = SmartSet.create(accessSources + other.accessSources)) + else -> null + } + } +} + +data class IsCalledBy( + override val from: FunctionIndex<*>, + override val to: DependencyNodeIndex, + override val accessSources: Set<IrElement> = emptySet(), +) : InformationEdge, HappensBeforeEdge { + constructor(from: FunctionIndex<*>, to: DependencyNodeIndex, accessSource: IrElement?) : this( + from = from, + to = to, + accessSources = SmartSet.create<IrElement>().also { it.addIfNotNull(accessSource) } + ) + + override fun merge(other: DependencyEdge): IsCalledBy? { + if (other !is IsCalledBy) return null + return when { + from == other.from && to == other.to -> copy(accessSources = SmartSet.create(accessSources + other.accessSources)) + else -> null + } + } +} + +data class MustHappenBefore( + override val from: DependencyNodeIndex, + override val to: DependencyNodeIndex, +) : HappensBeforeEdge { + override val holdsInAllExecutions: Boolean = true + + override fun merge(other: DependencyEdge): MustHappenBefore? { + if (other !is MustHappenBefore) return null + val mergedFrom = when { + from == other.from -> from + else -> CompositeIndex(from.unwrap() + other.from.unwrap()) + } + val mergedTo = when { + to == other.to -> to + else -> CompositeIndex(to.unwrap() + other.to.unwrap()) + } + return MustHappenBefore(mergedFrom, mergedTo) + } +} + +data class MayHappenBefore( + override val from: DependencyNodeIndex, + override val to: DependencyNodeIndex, +) : HappensBeforeEdge { + override fun merge(other: DependencyEdge): MayHappenBefore? { + if (other !is MayHappenBefore) return null + val mergedFrom = when { + from == other.from -> from + else -> CompositeIndex(from.unwrap() + other.from.unwrap()) + } + val mergedTo = when { + to == other.to -> to + else -> CompositeIndex(to.unwrap() + other.to.unwrap()) + } + return MayHappenBefore(mergedFrom, mergedTo) + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyGraph.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyGraph.kt new file mode 100644 index 0000000..6b53224 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyGraph.kt
@@ -0,0 +1,216 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.model + +import org.jetbrains.kotlin.fir.util.SetMultimap +import org.jetbrains.kotlin.fir.util.setMultimapOf +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNode.Companion.happensBeforeAncestors +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNode.Companion.happensBeforeDescendants +import org.jetbrains.kotlin.initialization.plugin.util.TraversalOrder +import org.jetbrains.kotlin.ir.declarations.IrModuleFragment +import java.util.LinkedList +import kotlin.collections.plusAssign +import kotlin.sequences.forEach + +class DependencyGraph(val module: IrModuleFragment) : Set<DependencyNode> { + + private val nodes: MutableSet<DependencyNode> = mutableSetOf() + private val entities: SetMultimap<EnclosingEntity<*>, DependencyNodeIndex> = setMultimapOf() + private val indices: MutableMap<DependencyNodeIndex, DependencyNode> = mutableMapOf() + + override val size: Int get() = nodes.size + + override fun isEmpty(): Boolean = nodes.isEmpty() + + override fun contains(element: DependencyNode): Boolean = element.index in this + + override fun iterator(): Iterator<DependencyNode> = nodes.iterator() + + override fun containsAll(elements: Collection<DependencyNode>): Boolean = elements.all { it in this } + + operator fun get(index: DependencyNodeIndex): DependencyNode? = index.unwrap().firstNotNullOfOrNull { indices[it] } + + operator fun get(enclosingEntity: EnclosingEntity<*>): Sequence<DependencyNodeIndex> = entities[enclosingEntity].asSequence() + + internal inline fun getOrCreate(index: DependencyNodeIndex, init: (UnitNode) -> Unit = {}): DependencyNode = + this[index] ?: UnitNode(index).apply { + nodes.add(this) + indices[index] = this + enclosingEntity?.let { entities.put(it, index) } + init(this) + } + + operator fun contains(index: DependencyNodeIndex): Boolean = index in indices + + operator fun contains(enclosingEntity: EnclosingEntity<*>): Boolean = enclosingEntity in entities + + companion object { + + context(graph: DependencyGraph) + fun Set<DependencyNode>.stronglyConnectedComponents(): List<Set<DependencyNode>> { + val visited = mutableSetOf<DependencyNode>() + val sorted = LinkedList<DependencyNode>() + this@stronglyConnectedComponents.forEach { node -> + node.happensBeforeDescendants(visited, TraversalOrder.PostOrder) { it in this && !it.isComposite } + .forEach(sorted::push) + } + visited.clear() + + val result = LinkedList<Set<DependencyNode>>() + while (sorted.isNotEmpty()) { + val current = sorted.pop() + if (current !in visited) { + val component = mutableSetOf<DependencyNode>() + current.happensBeforeAncestors(visited, TraversalOrder.PostOrder) { it in this && !it.isComposite } + .forEach { component += it } + result += component + } + } + + return result + } + + context(graph: DependencyGraph) + fun Set<DependencyNode>.condenseCycles(): Unit = + this@condenseCycles.stronglyConnectedComponents().forEach { component -> + if (component.size == 1) return@forEach + // Preserve the flat structure of SCCs + val indices = sequence { + component.forEach { + yieldAll(it.index.unwrap()) + } + }.toSet() + val condensed = CompositeNode( + indices = indices, + entities = setMultimapOf<EnclosingEntity<*>, DependencyNodeIndex>().apply { + component.forEach { node -> + when (node) { + is UnitNode -> node.enclosingEntity?.let { put(it, node.index) } + is CompositeNode -> node.enclosingEntities.forEach { entity -> + node[entity].forEach { put(entity, it) } + } + } + } + }, + // Edges between nodes inside SCCs should have only one source and target index + subgraphFlow = setMultimapOf<DependencyNodeIndex, HappensBeforeEdge>().apply { + component.forEach { node -> + when (node) { + is UnitNode -> node.happensAfterFlow.filter { it.holdsInAllExecutions }.forEach { edge -> + edge.to.unwrap().forEach { target -> + put(node.index, MustHappenBefore(node.index, target)) + } + } + is CompositeNode -> node.index.unwrap().forEach { index -> + // Invariant: all subgraph edges have a single source and target index + node.subgraphFlowFrom(index).forEach { put(index, it) } + node.happensAfterFlow.filter { it.holdsInAllExecutions }.forEach { edge -> + val sources = edge.from.unwrap() + val targets = edge.to.unwrap() + sources.forEach { source -> + targets.forEach { target -> + put(source, MustHappenBefore(source, target)) + } + } + } + } + } + } + } + ) + component.mergeFlow(condensed) + } + + context(graph: DependencyGraph) + private fun Set<DependencyNode>.mergeFlow(into: CompositeNode) = let { scc -> + val index = into.index + // Add the node to the graph + graph.nodes.add(into) + // Store this to allow lookups of composite nodes along happens-before paths + index.indices.forEach { graph.indices[it] = into } + // Edges coming INTO the SCC should be merged if their source is the same, such that the target indices are exactly those + // that were directly connected to the source node with the original edge(s) + val incomingMergedMustFlow = mutableMapOf<DependencyNodeIndex, MustHappenBefore>() + val incomingMergedMayFlow = mutableMapOf<DependencyNodeIndex, MayHappenBefore>() + // Edges coming OUT of the SCC should be merged if their target is the same, such that the source indices are exactly those + // that were directly connected to the target node with the original edge(s) + val outgoingMergedMustFlow = mutableMapOf<DependencyNodeIndex, MustHappenBefore>() + val outgoingMergedMayFlow = mutableMapOf<DependencyNodeIndex, MayHappenBefore>() + // IMPORTANT: the equivalent back edges for the nodes inside the SCC that point outside the SCC should be kept, so the + // must-happens-before subgraphs are properly preserved + // For each node in the set that was condensed, ... + scc.forEach { node -> + // For each incoming happens-before edge, ... + node.happensBeforeFlow.forEach { edge -> + when (edge) { + // Insert the call edge to the new condensed node (implicitly handles self-loops) + is IsCalledBy -> into.insertIncomingEdge(edge) + // Merge all incoming happens-before dependencies into the new condensed node and update their targets + is MustHappenBefore -> { + // Skip edges which connect nodes in the SCC + if (edge.from in into) return@forEach + incomingMergedMustFlow[edge.from] = incomingMergedMustFlow[edge.from]?.merge(edge) ?: edge + graph[edge.from]?.removeOutgoingEdge(edge) + } + is MayHappenBefore -> { + // Skip edges which connect nodes in the SCC + if (edge.from in into) return@forEach + // No need to merge, as we try to minimize the amount of may-happen-before edges + incomingMergedMayFlow[edge.from] = MayHappenBefore(edge.from, index) + graph[edge.from]?.removeOutgoingEdge(edge) + } + } + } + // For each outgoing happens-before edge, + node.happensAfterFlow.forEach { edge -> + when (edge) { + // Insert the call edge to the new condensed node (implicitly handles self-loops) + is IsCalledBy -> into.insertOutgoingEdge(edge) + // Merge all incoming happens-before dependencies into the new condensed node and update their targets + is MustHappenBefore -> { + // Skip edges which connect nodes in the SCC + if (edge.to in into) return@forEach + outgoingMergedMustFlow[edge.to] = outgoingMergedMustFlow[edge.to]?.merge(edge) ?: edge + graph[edge.from]?.removeOutgoingEdge(edge) + } + is MayHappenBefore -> { + // Skip edges which connect nodes in the SCC + if (edge.to in into) return@forEach + val actualTo = graph[edge.to]?.index ?: edge.to + // No need to merge, as we try to minimize the amount of may-happen-before edges + outgoingMergedMayFlow[actualTo] = MayHappenBefore(index, edge.to) + graph[edge.from]?.removeOutgoingEdge(edge) + } + } + } + // For each information edges, simply insert them to the condensed node + node.informationFlow.forEach { into.insertIncomingEdge(it) } + // For each merged edge, also insert them to the condensed node and the source/target nodes + incomingMergedMustFlow.forEach { [index, edge] -> + into.insertIncomingEdge(edge) + graph[index]?.insertOutgoingEdge(edge) + } + incomingMergedMayFlow.forEach { [index, edge] -> + into.insertIncomingEdge(edge) + graph[index]?.insertOutgoingEdge(edge) + } + outgoingMergedMustFlow.forEach { [index, edge] -> + into.insertOutgoingEdge(edge) + graph[index]?.insertIncomingEdge(edge) + } + outgoingMergedMayFlow.forEach { [index, edge] -> + into.insertOutgoingEdge(edge) + graph[index]?.insertIncomingEdge(edge) + } + // Composite nodes need to be removed from the dependency graph index + if (node.isComposite) graph.indices.remove(node.index) + // Dispose of the node + node.reset() + graph.nodes.remove(node) + } + } + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyGraphAnalyzer.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyGraphAnalyzer.kt new file mode 100644 index 0000000..896ee99 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyGraphAnalyzer.kt
@@ -0,0 +1,157 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.model + +import org.jetbrains.kotlin.initialization.plugin.model.CompositeNode.Companion.subgraphFlowDescendants +import org.jetbrains.kotlin.initialization.plugin.model.DependencyEdge.Companion.component2 +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNodeIndex.Companion.enclosingEntity +import org.jetbrains.kotlin.initialization.plugin.model.InformationEdge.Companion.component1 +import org.jetbrains.kotlin.initialization.plugin.model.InformationEdge.Companion.component3 +import org.jetbrains.kotlin.initialization.plugin.model.AnalysisResult.Companion.with +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.isNotPrivate +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.parentEnclosingEntityOrSelf +import org.jetbrains.kotlin.descriptors.isInterface +import org.jetbrains.kotlin.ir.IrElement +import kotlin.sequences.forEach + +data class AnalysisResult(val type: InitializationCycleAccessResult, val accesses: Set<IrElement>) { + companion object { + infix fun InitializationCycleAccessResult.with(accesses: Set<IrElement>): AnalysisResult = AnalysisResult(this, accesses) + } +} + +class DependencyGraphAnalyzer(val dependencyGraph: DependencyGraph) { + + context(accessingEntity: EnclosingEntity<*>?, cycle: CompositeNode) + private fun analyzeTransitively( + initial: DependencyNodeIndex, + node: DependencyNodeIndex, + visited: MutableSet<DependencyNodeIndex> = mutableSetOf() + ): Sequence<InitializationCycleAccessResult> = sequence { + if (!visited.add(node)) { + if (node is DeclarationIndex<*> && node !is FunctionIndex<*>) { + yield(InitializationCycleAccessResult.CyclicAccess(node)) + } + return@sequence + } + val informationFlow = cycle.informationFlowInto(node) + for ([from, _, _] in informationFlow) { + accessingUninitializedEntityAt(from, cycle, isTransitive = true)?.let { + yield(it) + continue + } + if (from !in cycle) continue + val inOrderAccess = when { + from.enclosingEntity?.let { it == accessingEntity } ?: false -> + // In-order references must be allowed + from != initial && from.subgraphFlowDescendants().any { it == initial } + else -> false + } + when (val result = from.accessAnalysisResult) { + null -> continue + is InitializationCycleAccessResult.ReportedAndPoisoning if inOrderAccess -> when { + analyzeTransitively(initial, from, visited.toMutableSet()) + .any { it is InitializationCycleAccessResult.ReportedAndPoisoning } -> yield(result) + else -> continue + } + is InitializationCycleAccessResult.ReportedAndPoisoning -> yield(result) + is InitializationCycleAccessResult.Reported -> { + yield(result) + yieldAll(analyzeTransitively(initial, from, visited.toMutableSet())) + } + else -> yieldAll(analyzeTransitively(initial, from, visited.toMutableSet())) + } + } + } + + /** + * Checks whether the [accessedNode] belongs to/is nested under an entity whose (singleton) instance is inaccessible by its recursively + * initialized entities, assuming to the Kotlin's JVM compilation scheme. + * + * In general, `A.foo()` (where A is a (companion) object or the A's qualifier resolves a companion object of A) is an uninitialized + * access iff access to the singleton instance of A (or its resolved object) yields null. If that is the case, such accesses will + * always result in a `ExceptionInInitializerError` reporting an NPE on the singleton. + * + * In JVM terms, when accessing the singleton instance yields null, it is due to the fact that its instance field has not been + * assigned yet, i.e. the access must have happened during the execution of its corresponding class' `<clinit>` and before its instance + * is assigned to an accessible field available at the parent (class) entity (during its own `<clinit>`). This important because when + * a companion object is nested under an interface, the compilation scheme defines a `<clinit>` for the companion object class that + * initializes the singleton object instance but gets invoked BEFORE it is assigned to the field. The same goes for enum entries and + * companion objects in enum classes. + */ + context(accessingEntity: EnclosingEntity<*>?) + private fun accessingUninitializedEntityAt( + accessedNode: AccessibleIndex, + cycle: CompositeNode, + isTransitive: Boolean = false + ): InitializationCycleAccessResult? { + // Even though constructors (may) statically initialize their containing classes, there is no actual access to their (initialized) + // declarations whatsoever + if (accessedNode is FunctionIndex.Constructor) return null + val accessedEntity = accessedNode.enclosingEntity + ?: accessedNode.lazilyInitialized + ?: return null + if (accessedEntity == accessingEntity && !isTransitive) return null + // We consider 2 cases when such accesses might arise: + return when { + // If the accessed entity is nested under an interface... + (accessedEntity.parentEnclosingEntity as? EnclosingEntity.Class)?.let { it in cycle && it.symbol.owner.kind.isInterface } ?: false -> + InitializationCycleAccessResult.InaccessibleEntityAccess(accessedEntity.parentEnclosingEntity!!, accessedNode) + // If the accessed entity's static initialization has a beginning in the happens-before cycle (enum entry and inheritance case)... + accessedEntity.beginInitializationIndex in cycle -> InitializationCycleAccessResult.InaccessibleEntityAccess(accessedEntity, accessedNode) + else -> null + } + } + + fun analyze(node: DependencyNodeIndex): Sequence<AnalysisResult> = (dependencyGraph[node] as? CompositeNode)?.let { cycle -> + val accessingEntity = node.enclosingEntity + context(accessingEntity, cycle) { + val informationFlow = cycle.informationFlowInto(node) + sequence { + for ([from, _, accesses] in informationFlow) { + accessingUninitializedEntityAt(from, cycle)?.let { + yield(it with accesses) + continue + } + if (from !in cycle) continue + val inOrderAccess = when { + from.enclosingEntity?.let { it == accessingEntity } ?: false -> + // In-order references must be allowed + from != node && from.subgraphFlowDescendants().any { it == node } + else -> false + } + when (val result = from.accessAnalysisResult) { + null -> continue + is InitializationCycleAccessResult.ReportedAndPoisoning if inOrderAccess -> when { + analyzeTransitively(node, from, mutableSetOf(node)) + .any { it is InitializationCycleAccessResult.ReportedAndPoisoning } -> yield(result with accesses) + else -> continue + } + is InitializationCycleAccessResult.ReportedAndPoisoning -> yield(result with accesses) + is InitializationCycleAccessResult.Reported -> { + yield(result with accesses) + analyzeTransitively(node, from, mutableSetOf(node)) + .forEach { yield(it with accesses) } + } + else -> analyzeTransitively(node, from, mutableSetOf(node)).forEach { yield(it with accesses) } + } + } + } + } + } ?: emptySequence() + + fun mutuallyDependentEntities(enclosingEntity: EnclosingEntity<*>): Sequence<EnclosingEntity<*>> = + when { + enclosingEntity.isPrivate -> emptySequence() + else -> dependencyGraph[enclosingEntity].mapNotNull(dependencyGraph::get) + .filterIsInstance<CompositeNode>() + .flatMap { node -> + node.enclosingEntities.asSequence() + .map { it.parentEnclosingEntityOrSelf } + .filter { it.isNotPrivate && it != enclosingEntity && it.endInitializationIndex in node } + }.distinct() + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyNode.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyNode.kt new file mode 100644 index 0000000..e057211 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyNode.kt
@@ -0,0 +1,237 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.model + +import org.jetbrains.kotlin.fir.util.SetMultimap +import org.jetbrains.kotlin.initialization.plugin.model.DependencyNodeIndex.Companion.enclosingEntity +import org.jetbrains.kotlin.initialization.plugin.util.TraversalOrder +import kotlin.collections.forEach +import kotlin.collections.set +import kotlin.let + +internal typealias InformationFlowMap = MutableMap<AccessibleIndex, InformationEdge> + +internal fun InformationFlowMap.insertEdge(edge: InformationEdge): Boolean = + this[edge.from]?.let { prev -> + prev.merge(edge)?.let { + this[edge.from] = it + true + } ?: false + } ?: (putIfAbsent(edge.from, edge) == null) + +internal fun InformationFlowMap.removeEdge(edge: InformationEdge): Boolean = remove(edge.from, edge) + +internal typealias HappensBeforeFlowMap = MutableMap<DependencyNodeIndex, HappensBeforeEdge> + +internal inline fun HappensBeforeFlowMap.insertEdge(edge: HappensBeforeEdge, key: (DependencyEdge) -> DependencyNodeIndex): Boolean = + putIfAbsent(key(edge), edge) == null + +internal inline fun HappensBeforeFlowMap.removeEdge(edge: HappensBeforeEdge, key: (DependencyEdge) -> DependencyNodeIndex): Boolean = + remove(key(edge), edge) + +sealed class DependencyNode { + + abstract val index: DependencyNodeIndex + + abstract val isComposite: Boolean + + protected val incomingHappensBeforeFlow: HappensBeforeFlowMap = mutableMapOf() + + protected val outgoingHappensBeforeFlow: HappensBeforeFlowMap = mutableMapOf() + + val happensBeforeFlow: Sequence<HappensBeforeEdge> get() = incomingHappensBeforeFlow.asSequence().map { it.value } + + val happensAfterFlow: Sequence<HappensBeforeEdge> get() = outgoingHappensBeforeFlow.asSequence().map { it.value } + + abstract val informationFlow: Sequence<InformationEdge> + + context(graph: DependencyGraph) + val happenBefore: Sequence<DependencyNode> get() = incomingHappensBeforeFlow.asSequence().mapNotNull { graph[it.key] } + + context(graph: DependencyGraph) + val happenAfter: Sequence<DependencyNode> get() = outgoingHappensBeforeFlow.asSequence().mapNotNull { graph[it.key] } + + open fun insertIncomingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is HappensBeforeEdge -> incomingHappensBeforeFlow.insertEdge(edge, DependencyEdge::from) + else -> false + } + + open fun removeIncomingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is HappensBeforeEdge -> incomingHappensBeforeFlow.removeEdge(edge, DependencyEdge::from) + else -> false + } + + open fun insertOutgoingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is HappensBeforeEdge -> outgoingHappensBeforeFlow.insertEdge(edge, DependencyEdge::to) + else -> false + } + + open fun removeOutgoingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is HappensBeforeEdge -> outgoingHappensBeforeFlow.removeEdge(edge, DependencyEdge::to) + else -> false + } + + open fun reset() { + incomingHappensBeforeFlow.clear() + outgoingHappensBeforeFlow.clear() + } + + companion object { + + context(graph: DependencyGraph) + internal inline fun DependencyNode.happensBeforeAncestors( + visited: MutableSet<DependencyNode> = mutableSetOf(), + traversalOrder: TraversalOrder = TraversalOrder.PreOrder, + crossinline predicate: (DependencyNode) -> Boolean = { true } + ): Sequence<DependencyNode> = + traversalOrder.traverse( + start = this@happensBeforeAncestors, + visited = visited, + predicate = predicate, + neighbours = { it.happenBefore } + ) + + context(graph: DependencyGraph) + internal inline fun DependencyNode.happensBeforeDescendants( + visited: MutableSet<DependencyNode> = mutableSetOf(), + traversalOrder: TraversalOrder = TraversalOrder.PreOrder, + crossinline predicate: (DependencyNode) -> Boolean = { true } + ): Sequence<DependencyNode> = + traversalOrder.traverse( + start = this@happensBeforeDescendants, + visited = visited, + predicate = predicate, + neighbours = { it.happenAfter } + ) + } +} + +data class UnitNode(override val index: DependencyNodeIndex) : DependencyNode() { + val enclosingEntity: EnclosingEntity<*>? = index.enclosingEntity + private val incomingInformationFlow: InformationFlowMap = mutableMapOf() + + override val informationFlow: Sequence<InformationEdge> get() = incomingInformationFlow.asSequence().map { it.value } + + override val isComposite: Boolean = false + + override fun insertIncomingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is IsCalledBy -> { + incomingHappensBeforeFlow.insertEdge(edge, DependencyEdge::from) + incomingInformationFlow.insertEdge(edge) + } + is InformationEdge -> incomingInformationFlow.insertEdge(edge) + else -> super.insertIncomingEdge(edge) + } + + override fun removeIncomingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is IsCalledBy -> { + incomingHappensBeforeFlow.removeEdge(edge, DependencyEdge::from) + incomingInformationFlow.removeEdge(edge) + } + is InformationEdge -> incomingInformationFlow.removeEdge(edge) + else -> super.removeIncomingEdge(edge) + } + + override fun reset() { + super.reset() + incomingInformationFlow.clear() + } +} + +data class CompositeNode( + private val indices: Set<DependencyNodeIndex>, + private val entities: SetMultimap<EnclosingEntity<*>, DependencyNodeIndex>, + private val subgraphFlow: SetMultimap<DependencyNodeIndex, HappensBeforeEdge>, +) : DependencyNode(), Set<DependencyNodeIndex> by indices { + + val enclosingEntities: Set<EnclosingEntity<*>> get() = entities.keys + + private val incomingInformationFlow: MutableMap<DependencyNodeIndex, InformationFlowMap> = mutableMapOf() + + override val informationFlow: Sequence<InformationEdge> get() = asSequence().flatMap { informationFlowInto(it) } + + fun informationFlowInto(index: DependencyNodeIndex): Sequence<InformationEdge> = + incomingInformationFlow[index]?.asSequence()?.map { it.value } ?: emptySequence() + + fun subgraphFlowFrom(index: DependencyNodeIndex): Sequence<HappensBeforeEdge> = subgraphFlow[index].asSequence() + + operator fun get(enclosingEntity: EnclosingEntity<*>): Sequence<DependencyNodeIndex> = entities[enclosingEntity].asSequence() + + operator fun contains(enclosingEntity: EnclosingEntity<*>): Boolean = enclosingEntity in enclosingEntities + + override operator fun contains(element: DependencyNodeIndex): Boolean = + when (element) { + is CompositeIndex -> element.indices.any { it in indices } + else -> element in indices + } + + override val index: CompositeIndex = CompositeIndex(indices) + override val isComposite: Boolean = true + + override fun insertIncomingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is IsCalledBy -> { + if (edge.from !in this) incomingHappensBeforeFlow.insertEdge(edge, DependencyEdge::from) + incomingInformationFlow.getOrPut(edge.to) { mutableMapOf() }.insertEdge(edge) + } + is InformationEdge -> incomingInformationFlow.getOrPut(edge.to) { mutableMapOf() }.insertEdge(edge) + else -> super.insertIncomingEdge(edge) + } + + override fun removeIncomingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is IsCalledBy -> { + if (edge.from !in this) incomingHappensBeforeFlow.removeEdge(edge, DependencyEdge::from) + incomingInformationFlow[edge.from]?.let { + val result = it.removeEdge(edge) + if (it.isEmpty()) incomingInformationFlow.remove(edge.from) + result + } ?: false + } + is InformationEdge -> incomingInformationFlow[edge.from]?.let { + val result = it.removeEdge(edge) + if (it.isEmpty()) incomingInformationFlow.remove(edge.from) + result + } ?: false + else -> super.removeIncomingEdge(edge) + } + + override fun insertOutgoingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is IsCalledBy if edge.to !in this -> outgoingHappensBeforeFlow.insertEdge(edge, DependencyEdge::to) + is HappensBeforeEdge -> outgoingHappensBeforeFlow.insertEdge(edge, DependencyEdge::to) + else -> false + } + + override fun removeOutgoingEdge(edge: DependencyEdge): Boolean = + when (edge) { + is IsCalledBy if edge.to !in this -> outgoingHappensBeforeFlow.removeEdge(edge, DependencyEdge::to) + is HappensBeforeEdge -> outgoingHappensBeforeFlow.removeEdge(edge, DependencyEdge::to) + else -> false + } + + override fun reset() { + super.reset() + incomingInformationFlow.forEach { it.value.clear() } + incomingInformationFlow.clear() + } + + companion object { + context(cycle: CompositeNode) + fun DependencyNodeIndex.subgraphFlowDescendants(): Sequence<DependencyNodeIndex> = + TraversalOrder.PreOrder.traverse( + start = this@subgraphFlowDescendants, + predicate = { it in cycle }, + neighbours = { cycle.subgraphFlowFrom(it).map(DependencyEdge::to) } + ) + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyNodeIndex.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyNodeIndex.kt new file mode 100644 index 0000000..9c32a4b --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/DependencyNodeIndex.kt
@@ -0,0 +1,257 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.model + +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.asEntity +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.isNotPrivate +import org.jetbrains.kotlin.initialization.plugin.model.EnclosingEntity.Companion.parentEnclosingEntityOrSelf +import org.jetbrains.kotlin.initialization.plugin.util.isCustomAccessor +import org.jetbrains.kotlin.initialization.plugin.util.isPrivate +import org.jetbrains.kotlin.ir.declarations.IrAnonymousInitializer +import org.jetbrains.kotlin.ir.declarations.IrClass +import org.jetbrains.kotlin.ir.declarations.IrConstructor +import org.jetbrains.kotlin.ir.declarations.IrDeclaration +import org.jetbrains.kotlin.ir.declarations.IrEnumEntry +import org.jetbrains.kotlin.ir.declarations.IrFile +import org.jetbrains.kotlin.ir.declarations.IrFunction +import org.jetbrains.kotlin.ir.declarations.IrProperty +import org.jetbrains.kotlin.ir.declarations.IrSimpleFunction +import org.jetbrains.kotlin.ir.declarations.IrSymbolOwner +import org.jetbrains.kotlin.ir.expressions.IrFunctionExpression +import org.jetbrains.kotlin.ir.symbols.IrAnonymousInitializerSymbol +import org.jetbrains.kotlin.ir.symbols.IrBindableSymbol +import org.jetbrains.kotlin.ir.symbols.IrClassSymbol +import org.jetbrains.kotlin.ir.symbols.IrConstructorSymbol +import org.jetbrains.kotlin.ir.symbols.IrPropertySymbol +import org.jetbrains.kotlin.ir.symbols.IrSimpleFunctionSymbol +import org.jetbrains.kotlin.ir.symbols.IrValueParameterSymbol +import org.jetbrains.kotlin.ir.util.callableId +import org.jetbrains.kotlin.ir.util.classId +import org.jetbrains.kotlin.ir.util.fileOrNull +import org.jetbrains.kotlin.ir.util.isFunctionOrKFunction +import org.jetbrains.kotlin.ir.util.parentClassOrNull +import org.jetbrains.kotlin.name.FqName + +sealed interface InitializationCycleAccessResult { + val poisonsInitializers: Boolean get() = false + + sealed interface Reported : InitializationCycleAccessResult + + sealed class ReportedAndPoisoning : Reported { + override val poisonsInitializers: Boolean = true + } + + data class UninitializedPropertyAccess(val node: PropertyIndex) : ReportedAndPoisoning() + + data class UninitializedEnumEntryAccess(val node: EnumEntryIndex) : ReportedAndPoisoning() + + data class CyclicAccess(val node: DeclarationIndex<*>) : ReportedAndPoisoning() + + data class InaccessibleEntityAccess(val entity: EnclosingEntity<*>, val node: AccessibleIndex) : ReportedAndPoisoning() + + data class DeadlockInducingConstructorCall(val node: FunctionIndex.Constructor) : Reported + + data object PropagatesTransitiveDependencies : InitializationCycleAccessResult +} + +sealed interface DependencyNodeIndex { + val containingFile: IrFile? get() = null + + fun unwrap(): Set<DependencyNodeIndex> = setOf(this) + + companion object { + val DependencyNodeIndex.enclosingEntity: EnclosingEntity<*>? + get() = when (this) { + is BeginStaticInitializationIndex<*> -> enclosingEntity + is EndStaticInitializationIndex<*> -> enclosingEntity + is PropertyIndex -> enclosingEntity + is AnonymousInitializerIndex -> enclosingEntity + is FunctionIndex.Constructor -> lazilyInitialized + is FunctionIndex<*> -> lazilyInitialized?.parentEnclosingEntityOrSelf + else -> null + } + } +} + +sealed interface AccessibleIndex : DependencyNodeIndex { + val lazilyInitialized: EnclosingEntity<*>? + + context(_: EnclosingEntity<*>?, _: CompositeNode) + val accessAnalysisResult: InitializationCycleAccessResult? get() = null +} + +sealed interface DeclarationIndex<D : IrDeclaration> : DependencyNodeIndex { + val symbol: IrBindableSymbol<*, D> + + override val containingFile: IrFile? get() = symbol.owner.fileOrNull +} + +data class PropertyIndex( + override val symbol: IrPropertySymbol, + val enclosingEntity: EnclosingEntity<*>? = null, +) : DeclarationIndex<IrProperty>, AccessibleIndex { + + val isConst: Boolean get() = symbol.owner.isConst + + val hasInitializer: Boolean get() = symbol.owner.backingField?.initializer != null + + val hasFunctionType: Boolean = symbol.owner.getter?.returnType?.isFunctionOrKFunction() + ?: symbol.owner.backingField?.type?.isFunctionOrKFunction() + ?: false + + override val lazilyInitialized: EnclosingEntity<*>? = enclosingEntity?.parentEnclosingEntityOrSelf + .takeIf { !isConst && !symbol.isPrivate } + + context(_: EnclosingEntity<*>?, _: CompositeNode) + override val accessAnalysisResult: InitializationCycleAccessResult? + get() = when { + !isConst && hasInitializer && !hasFunctionType -> InitializationCycleAccessResult.UninitializedPropertyAccess(this) + else -> null + } + + val getter: FunctionIndex.PropertyAccessor? = symbol.owner.getter?.takeIf { it.isCustomAccessor } + ?.let { FunctionIndex.PropertyAccessor(it.symbol, enclosingEntity) } + + val initializedClosure: FunctionIndex.Closure? = symbol.owner.backingField?.initializer?.expression?.let { + when (it) { + // We cover only simple cases e.g., `val x = { ... }` + is IrFunctionExpression -> FunctionIndex.Closure( + symbol = it.function.symbol, + lazilyInitialized = lazilyInitialized + ) + else -> null + } + } + + val name: FqName + get() = symbol.owner.callableId.classId?.relativeClassName?.child(symbol.owner.name) ?: FqName.topLevel(symbol.owner.name) + + override fun toString(): String = + "${symbol.owner.callableId.classId?.relativeClassName?.asString() ?: ""}.${symbol.owner.name.asString()}" +} + +data class AnonymousInitializerIndex( + override val symbol: IrAnonymousInitializerSymbol, + val enclosingEntity: EnclosingEntity<*>? = null, +) : DeclarationIndex<IrAnonymousInitializer> { + + override fun toString(): String = "${symbol.owner.parentClassOrNull?.classId?.relativeClassName?.let { "$it." } ?: ""}<init_block>" +} + +sealed class FunctionIndex<D : IrFunction> : DeclarationIndex<D>, AccessibleIndex { + abstract override val symbol: IrBindableSymbol<*, D> + + context(_: EnclosingEntity<*>?, _: CompositeNode) + override val accessAnalysisResult: InitializationCycleAccessResult get() = InitializationCycleAccessResult.PropagatesTransitiveDependencies + + override fun toString(): String = + "${symbol.owner.callableId.classId?.relativeClassName?.asString() ?: ""}.${symbol.owner.name.asString()}()" + + data class Closure( + override val symbol: IrSimpleFunctionSymbol, + override val lazilyInitialized: EnclosingEntity<*>? = null, + ) : FunctionIndex<IrSimpleFunction>() + + data class Constructor(override val symbol: IrConstructorSymbol) : FunctionIndex<IrConstructor>() { + + override val lazilyInitialized: EnclosingEntity<*>? = symbol.owner.takeIf { it.isPrimary } + ?.parentClassOrNull?.symbol?.asEntity(true) + + context(accessingEntity: EnclosingEntity<*>?, cycle: CompositeNode) + override val accessAnalysisResult: InitializationCycleAccessResult + get() { + return when { + lazilyInitialized?.let { accessingEntity?.parentEnclosingEntityOrSelf != it && it in cycle && it.isNotPrivate } == true -> { + InitializationCycleAccessResult.DeadlockInducingConstructorCall(this) + } + else -> InitializationCycleAccessResult.PropagatesTransitiveDependencies + } + } + } + + data class MemberFunction( + override val symbol: IrSimpleFunctionSymbol, + override val lazilyInitialized: EnclosingEntity<*>? = null, + ) : FunctionIndex<IrSimpleFunction>() + + data class PropertyAccessor( + override val symbol: IrSimpleFunctionSymbol, + override val lazilyInitialized: EnclosingEntity<*>? = null, + ) : FunctionIndex<IrSimpleFunction>() +} + +data class DefaultedFunctionIndex<D : IrFunction>( + val functionIndex: FunctionIndex<D>, + val defaultParameters: Set<IrValueParameterSymbol> +) : FunctionIndex<D>() { + override val symbol: IrBindableSymbol<*, D> get() = functionIndex.symbol + + // It is redundant to create another edge from the lazily initialized entity of the original function node to this node, + // the cycle is already subsumed by the original function node + override val lazilyInitialized: EnclosingEntity<*>? = null + + context(_: EnclosingEntity<*>?, _: CompositeNode) + override val accessAnalysisResult: InitializationCycleAccessResult get() = functionIndex.accessAnalysisResult +} + +sealed class BeginStaticInitializationIndex<D : IrSymbolOwner> : DependencyNodeIndex { + abstract val enclosingEntity: EnclosingEntity<D> + + override val containingFile: IrFile? get() = enclosingEntity.containingFile + + override fun toString(): String = "Begin $enclosingEntity" +} + +data class EndStaticInitializationIndex<D : IrSymbolOwner>(val enclosingEntity: EnclosingEntity<D>) : DependencyNodeIndex { + + override val containingFile: IrFile? get() = enclosingEntity.containingFile + + override fun toString(): String = "End $enclosingEntity" +} + +data class TopLevelIndex(override val enclosingEntity: EnclosingEntity.File) : BeginStaticInitializationIndex<IrFile>() { + override fun toString(): String = "<$enclosingEntity>" +} + +data class QualifierIndex( + override val enclosingEntity: EnclosingEntity.Object +) : BeginStaticInitializationIndex<IrClass>(), AccessibleIndex { + + override val lazilyInitialized: EnclosingEntity<*>? = enclosingEntity.takeIf { it.isNotPrivate }?.parentEnclosingEntityOrSelf + + context(_: EnclosingEntity<*>?, _: CompositeNode) + override val accessAnalysisResult: InitializationCycleAccessResult get() = InitializationCycleAccessResult.PropagatesTransitiveDependencies +} + +data class EnumEntryIndex( + override val enclosingEntity: EnclosingEntity.EnumEntry +) : BeginStaticInitializationIndex<IrEnumEntry>(), AccessibleIndex { + + override val lazilyInitialized: EnclosingEntity<*>? = enclosingEntity.parentEnclosingEntity.takeIf { it.isNotPrivate } + + context(_: EnclosingEntity<*>?, _: CompositeNode) + override val accessAnalysisResult: InitializationCycleAccessResult + get() = InitializationCycleAccessResult.UninitializedEnumEntryAccess(this) +} + +data class ClinitIndex(override val enclosingEntity: EnclosingEntity.Class) : BeginStaticInitializationIndex<IrClass>() { + override fun toString(): String = "${super.toString()}.<clinit>" +} + +data class BeginInstanceInitializationIndex(val symbol: IrClassSymbol) : DependencyNodeIndex { + + override fun toString(): String = "Begin ${symbol.owner.let { it.classId?.relativeClassName ?: FqName.topLevel(it.name) }}.<init>" +} + +data class EndInstanceInitializationIndex(val symbol: IrClassSymbol) : DependencyNodeIndex { + + override fun toString(): String = "End ${symbol.owner.let { it.classId?.relativeClassName ?: FqName.topLevel(it.name) }}.<init>" +} + +data class CompositeIndex(val indices: Set<DependencyNodeIndex>) : DependencyNodeIndex { + override fun unwrap(): Set<DependencyNodeIndex> = indices + override fun toString(): String = indices.joinToString(prefix = "{", postfix = "}") +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/EnclosingEntity.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/EnclosingEntity.kt new file mode 100644 index 0000000..63bf6c7 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/model/EnclosingEntity.kt
@@ -0,0 +1,139 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.model + +import org.jetbrains.kotlin.initialization.plugin.util.isPrivate +import org.jetbrains.kotlin.descriptors.isObject +import org.jetbrains.kotlin.ir.declarations.IrClass +import org.jetbrains.kotlin.ir.declarations.IrEnumEntry +import org.jetbrains.kotlin.ir.declarations.IrFile +import org.jetbrains.kotlin.ir.declarations.IrSymbolOwner +import org.jetbrains.kotlin.ir.declarations.name +import org.jetbrains.kotlin.ir.symbols.IrBindableSymbol +import org.jetbrains.kotlin.ir.symbols.IrClassSymbol +import org.jetbrains.kotlin.ir.symbols.IrEnumEntrySymbol +import org.jetbrains.kotlin.ir.symbols.IrFileSymbol +import org.jetbrains.kotlin.ir.util.classId +import org.jetbrains.kotlin.ir.util.classIdOrFail +import org.jetbrains.kotlin.ir.util.fileOrNull +import org.jetbrains.kotlin.ir.util.isEnumClass +import org.jetbrains.kotlin.ir.util.parentAsClass +import org.jetbrains.kotlin.ir.util.parentClassOrNull +import org.jetbrains.kotlin.name.FqName +import org.jetbrains.kotlin.name.Name +import org.jetbrains.kotlin.utils.findIsInstanceAnd + +sealed class EnclosingEntity<D : IrSymbolOwner> { + + abstract val symbol: IrBindableSymbol<*, D> + + abstract val name: FqName + + abstract val parentEnclosingEntity: EnclosingEntity<*>? + + abstract val isPrivate: Boolean + + abstract val containingFile: IrFile? + + abstract val beginInitializationIndex: BeginStaticInitializationIndex<D> + + val endInitializationIndex: EndStaticInitializationIndex<D> = EndStaticInitializationIndex(this) + + override fun toString(): String = name.asString() + + data class Class(override val symbol: IrClassSymbol) : EnclosingEntity<IrClass>() { + + override val name: FqName = symbol.owner.classId?.relativeClassName ?: FqName.topLevel(Name.special("<anonymous>")) + + override val parentEnclosingEntity: EnclosingEntity<*>? = null + + override val isPrivate: Boolean = symbol.isPrivate + + override val containingFile: IrFile? = symbol.owner.fileOrNull + + override val beginInitializationIndex: ClinitIndex = ClinitIndex(this) + } + + data class Object(override val symbol: IrClassSymbol) : EnclosingEntity<IrClass>() { + + override val name: FqName = symbol.owner.classIdOrFail.relativeClassName + + override val parentEnclosingEntity: Class? = symbol.owner.takeIf(IrClass::isCompanion) + ?.parentClassOrNull?.symbol?.asClassEntity() + + override val isPrivate: Boolean = symbol.isPrivate + + override val containingFile: IrFile? = symbol.owner.fileOrNull + + override val beginInitializationIndex: QualifierIndex = QualifierIndex(this) + + val isCompanion: Boolean = parentEnclosingEntity != null + } + + data class EnumEntry(override val symbol: IrEnumEntrySymbol) : EnclosingEntity<IrEnumEntry>() { + + override val name: FqName = symbol.owner.let { it.parentAsClass.classIdOrFail.relativeClassName.child(it.name) } + + override val parentEnclosingEntity: Class = symbol.owner.parentAsClass.symbol.asClassEntity() + + override val isPrivate: Boolean = false + + override val containingFile: IrFile? = symbol.owner.fileOrNull + + override val beginInitializationIndex: EnumEntryIndex = EnumEntryIndex(this) + } + + data class File(override val symbol: IrFileSymbol) : EnclosingEntity<IrFile>() { + + override val name: FqName = symbol.owner.packageFqName.child(Name.identifier(symbol.owner.name)) + + override val parentEnclosingEntity: EnclosingEntity<*>? = null + + override val isPrivate: Boolean = false + + override val containingFile: IrFile = symbol.owner + + override val beginInitializationIndex: TopLevelIndex = TopLevelIndex(this) + } + + companion object { + + val EnclosingEntity<*>.isNotPrivate: Boolean get() = !isPrivate + + val EnclosingEntity<*>.parentEnclosingEntityOrSelf: EnclosingEntity<*> get() = parentEnclosingEntity ?: this + + fun IrClassSymbol.asObjectEntity(): Object? = when { + owner.kind.isObject -> Object(this) + else -> null + } + + fun IrClass.asObjectEntity(): Object? = symbol.asObjectEntity() + + fun IrClassSymbol.asClassEntity(): Class = Class(this) + + fun IrClass.asClassEntity(): Class = symbol.asClassEntity() + + fun IrBindableSymbol<*, *>.asEntity(allowClass: Boolean = true): EnclosingEntity<*>? = + when (this) { + is IrClassSymbol -> asObjectEntity() + ?: run { + owner.parentClassOrNull?.takeIf(IrClass::isEnumClass) + ?.declarations?.findIsInstanceAnd<IrEnumEntry> { it.correspondingClass == this } + ?.symbol?.asEnumEntryEntity() + } ?: if (allowClass) asClassEntity() else null + is IrFileSymbol -> asFileEntity() + else -> null + } + + fun IrFileSymbol.asFileEntity(): File = File(this) + + fun IrFile.asFileEntity(): File = symbol.asFileEntity() + + fun IrEnumEntrySymbol.asEnumEntryEntity(): EnumEntry = EnumEntry(this) + + fun IrEnumEntry.asEnumEntryEntity(): EnumEntry = symbol.asEnumEntryEntity() + } +}
diff --git a/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/util/DependencyUtils.kt b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/util/DependencyUtils.kt new file mode 100644 index 0000000..8671f65 --- /dev/null +++ b/compiler/fir/entrypoint/src/org/jetbrains/kotlin/initialization/plugin/util/DependencyUtils.kt
@@ -0,0 +1,245 @@ +/* + * Copyright 2010-2026 JetBrains s.r.o. and Kotlin Programming Language contributors. + * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file. + */ + +package org.jetbrains.kotlin.initialization.plugin.util + +import org.jetbrains.kotlin.initialization.plugin.model.BeginInstanceInitializationIndex +import org.jetbrains.kotlin.initialization.plugin.model.EndInstanceInitializationIndex +import org.jetbrains.kotlin.descriptors.isInterface +import org.jetbrains.kotlin.ir.declarations.IrDeclaration +import org.jetbrains.kotlin.ir.declarations.IrDeclarationOrigin +import org.jetbrains.kotlin.ir.declarations.IrDeclarationWithVisibility +import org.jetbrains.kotlin.ir.declarations.IrEnumEntry +import org.jetbrains.kotlin.ir.declarations.IrFile +import org.jetbrains.kotlin.ir.declarations.IrFunction +import org.jetbrains.kotlin.ir.declarations.IrModuleFragment +import org.jetbrains.kotlin.ir.declarations.IrProperty +import org.jetbrains.kotlin.ir.declarations.IrSimpleFunction +import org.jetbrains.kotlin.ir.overrides.isEffectivelyPrivate +import org.jetbrains.kotlin.ir.symbols.IrBindableSymbol +import org.jetbrains.kotlin.ir.symbols.IrClassSymbol +import org.jetbrains.kotlin.ir.symbols.IrEnumEntrySymbol +import org.jetbrains.kotlin.ir.symbols.IrFileSymbol +import org.jetbrains.kotlin.ir.util.fileOrNull +import org.jetbrains.kotlin.ir.util.isGetter +import org.jetbrains.kotlin.ir.util.isSetter +import kotlin.coroutines.Continuation +import kotlin.coroutines.CoroutineContext +import kotlin.coroutines.EmptyCoroutineContext +import kotlin.coroutines.RestrictsSuspension +import kotlin.coroutines.intrinsics.COROUTINE_SUSPENDED +import kotlin.coroutines.intrinsics.createCoroutineUnintercepted +import kotlin.coroutines.intrinsics.suspendCoroutineUninterceptedOrReturn +import kotlin.coroutines.resume + +@RestrictsSuspension +interface TraversalScope<T, R> { + + suspend fun emit(value: R) + + suspend fun traverseFor(element: T) +} + +fun <T, R> traversal(initial: T, block: suspend TraversalScope<T, R>.(T) -> Unit): Sequence<R> = object : Sequence<R> { + override fun iterator(): Iterator<R> = TraversalIterator(block, initial) +} + +private fun <R, T, V> (suspend R.(T) -> V).lowerArity(argument: T): suspend R.() -> V = { this@lowerArity(argument) } + +/** + * This iterator tries to marry Sequences and DeepRecursiveFunctions in a coroutine-friendly way. + * It is used to generate a sequence of values such that the generation is given by a function that can be called recursively. + * It is called TraversalIterator since it allows natural implementations of graph traversals such as DFS. + * Most of the code is adapted from [SequenceBuilderIterator] class. + */ +private class TraversalIterator<T, R>( + private val block: suspend TraversalScope<T, R>.(T) -> Unit, + initial: T +) : TraversalScope<T, R>, Iterator<R>, Continuation<Unit> { + + private enum class TraversalState { + NotReady, + Ready, + Done, + Failed, + } + + private var state = TraversalState.NotReady + private var nextValue: R? = null + var nextStep: Continuation<Unit>? = + block.lowerArity(initial).createCoroutineUnintercepted(receiver = this, completion = this) + + override fun hasNext(): Boolean { + while (true) { + when (state) { + TraversalState.NotReady -> {} + TraversalState.Done -> return false + TraversalState.Ready -> return true + else -> throw exceptionalState() + } + + state = TraversalState.Failed + val step = nextStep!! + nextStep = null + step.resume(Unit) + } + } + + override fun next(): R { + when (state) { + TraversalState.NotReady if hasNext() -> return next() + TraversalState.NotReady -> throw NoSuchElementException() + TraversalState.Ready -> { + state = TraversalState.NotReady + val result = nextValue!! + nextValue = null + return result + } + else -> throw exceptionalState() + } + } + + private fun exceptionalState(): Throwable = when (state) { + TraversalState.Done -> NoSuchElementException() + TraversalState.Failed -> IllegalStateException("Iterator has failed. ($this)") + else -> IllegalStateException("Unexpected state of the iterator: $state") + } + + + override suspend fun emit(value: R) { + nextValue = value + state = TraversalState.Ready + return suspendCoroutineUninterceptedOrReturn { c -> + nextStep = c + COROUTINE_SUSPENDED + } + } + + override suspend fun traverseFor(element: T) { + return suspendCoroutineUninterceptedOrReturn { c -> + // Treat the iterator as if it has been initialized again, so the recursive traversal simply becomes reinitialization with a new initial value + // No need to clean the nextValue, as the nextStep resumption will only happen after its consumption (next() switches the state to NotReady) + state = TraversalState.NotReady + nextStep = block.lowerArity(element).createCoroutineUnintercepted(receiver = this, completion = c) + COROUTINE_SUSPENDED + } + } + + override fun resumeWith(result: Result<Unit>) { + result.getOrThrow() + state = TraversalState.Done + } + + override val context: CoroutineContext + get() = EmptyCoroutineContext +} + +sealed class TraversalOrder { + + abstract suspend fun <T> TraversalScope<T, T>.traverseNext(current: T, neighbours: (T) -> Sequence<T>) + + inline fun <T> traverse( + start: T, + visited: MutableSet<T> = mutableSetOf(), + crossinline predicate: (T) -> Boolean = { true }, + noinline neighbours: (T) -> Sequence<T> + ): Sequence<T> = traversal(start) { + when (predicate(it) && visited.add(it)) { + true -> traverseNext(it, neighbours) + false -> {} + } + } + + object PreOrder : TraversalOrder() { + override suspend fun <T> TraversalScope<T, T>.traverseNext(current: T, neighbours: (T) -> Sequence<T>) { + emit(current) + neighbours(current).forEach { traverseFor(it) } + } + } + + object PostOrder : TraversalOrder() { + override suspend fun <T> TraversalScope<T, T>.traverseNext(current: T, neighbours: (T) -> Sequence<T>) { + neighbours(current).forEach { traverseFor(it) } + emit(current) + } + } +} + +class PathCompressingAncestorMap<T>(val parents: (T) -> Sequence<T>) : Map<T, Set<T>> { + private val ancestorMap = mutableMapOf<T, Set<T>>() + + private fun findAncestors(element: T): Set<T> { + val ancestors = parents(element).flatMap(::findAncestors).distinct().toMutableSet() + if (ancestors.isEmpty()) ancestors += element + ancestorMap[element] = ancestors + return ancestors + } + + fun reset(): Unit = ancestorMap.clear() + + override val size: Int get() = ancestorMap.size + + override fun isEmpty(): Boolean = ancestorMap.isEmpty() + + override fun containsKey(key: T): Boolean = ancestorMap.containsKey(key) + + override fun containsValue(value: Set<T>): Boolean = ancestorMap.containsValue(value) + + override fun get(key: T): Set<T> = ancestorMap[key] ?: findAncestors(key) + + override val keys: Set<T> get() = ancestorMap.keys + + override val values: Collection<Set<T>> get() = ancestorMap.values + + override val entries: Set<Map.Entry<T, Set<T>>> get() = ancestorMap.entries + + override fun toString(): String = ancestorMap.asIterable() + .joinToString(prefix = "{", postfix = "}", separator = "\t\n") { [element, parent] -> "$element -> $parent" } +} + +operator fun <E, M : MutableCollection<E>> M.plus(other: Iterable<E>): M = apply { + other.forEach { add(it) } +} + +fun IrClassSymbol.collectEnumEntries(): List<IrEnumEntrySymbol> { + if (!isBound) return emptyList() + if (!owner.hasEnumEntries) return emptyList() + return owner.declarations.asSequence().filterIsInstance<IrEnumEntry>().map { it.symbol }.toList() +} + +val <D : IrDeclaration> IrBindableSymbol<*, D>.containingFileSymbol: IrFileSymbol? get() = owner.fileOrNull?.symbol + +val IrClassSymbol.isInitializedBySupertypes: Boolean + get() = owner.let { + !it.kind.isInterface || it.kind.isInterface && it.declarations.any { decl -> + decl is IrProperty && decl.hasCustomAccessors || decl is IrFunction && decl.body != null + } + } + +val IrSimpleFunction.isCustomAccessor: Boolean get() = (isGetter || isSetter) && origin != IrDeclarationOrigin.DEFAULT_PROPERTY_ACCESSOR + +val IrProperty.hasCustomAccessors: Boolean get() = (getter?.isCustomAccessor ?: false) || (setter?.isCustomAccessor ?: false) + +val <D : IrDeclarationWithVisibility> IrBindableSymbol<*, D>.isPrivate: Boolean get() = owner.isEffectivelyPrivate() + +operator fun <D : IrDeclaration> IrModuleFragment.contains(symbol: IrBindableSymbol<*, D>): Boolean = + symbol.owner.fileOrNull?.let { it in this } ?: false + +operator fun IrModuleFragment.contains(decl: IrDeclaration): Boolean = + decl.fileOrNull?.let { it in this } ?: false + +operator fun IrModuleFragment.contains(file: IrFile): Boolean = file in files + +val IrClassSymbol.beginInitializationIndex: BeginInstanceInitializationIndex + get() = BeginInstanceInitializationIndex(this) + +val IrClassSymbol.endInitializationIndex: EndInstanceInitializationIndex + get() = EndInstanceInitializationIndex(this) + +infix operator fun <T> List<T>.plus(element: T?): List<T> = toMutableList().apply { element?.let(::add) } + +infix operator fun <K, V> Map<K, V>.plus(entry: Pair<K, V>?): Map<K, V> = toMutableMap().apply { + entry?.let { put(it.first, it.second) } +}