[FIR] `SupertypeComputationSession.breakLoopFor`: change type of `pathSet` to `LinkedHashSet` and remove `path` list `pathSet` holds all needed info
diff --git a/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/transformers/LLFirSupertypeLazyResolver.kt b/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/transformers/LLFirSupertypeLazyResolver.kt index 8bfbcff..db90e6b 100644 --- a/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/transformers/LLFirSupertypeLazyResolver.kt +++ b/analysis/low-level-api-fir/src/org/jetbrains/kotlin/analysis/low/level/api/fir/transformers/LLFirSupertypeLazyResolver.kt
@@ -310,8 +310,7 @@ */ private val visited: MutableSet<FirClassLikeDeclaration> = hashSetOf() private val looped: MutableSet<FirClassLikeDeclaration> = hashSetOf() - private val pathSet: MutableSet<FirClassLikeDeclaration> = hashSetOf() - private val path: MutableList<FirClassLikeDeclaration> = mutableListOf() + private val pathOrderedSet: LinkedHashSet<FirClassLikeDeclaration> = LinkedHashSet() // --------------- /** @@ -331,14 +330,11 @@ session = declaration.llFirSession, visited = visited, looped = looped, - pathSet = pathSet, - path = path, + pathOrderedSet = pathOrderedSet, // LL resolver only works for non-local declarations localClassesNavigationInfo = null, ) - require(path.isEmpty()) { "Path should be empty" } - require(pathSet.isEmpty()) { "Path set should be empty" } visited.clear() looped.clear() return updatedTypesForDeclarationsWithLoop[declaration]
diff --git a/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/transformers/FirSupertypesResolution.kt b/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/transformers/FirSupertypesResolution.kt index fdc8396..2728278 100644 --- a/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/transformers/FirSupertypesResolution.kt +++ b/compiler/fir/resolve/src/org/jetbrains/kotlin/fir/resolve/transformers/FirSupertypesResolution.kt
@@ -661,21 +661,21 @@ * @param declaration declaration to be checked for loops * @param visited visited declarations during the current loop search (DFS tree) * @param looped declarations inside loop - * @param pathSet declaration set on a current path (DFS branch) - * @param path declarations on a current path (DFS branch) + * @param pathOrderedSet declaration ordered set (in visit order) on a current path (DFS branch). * @param localClassesNavigationInfo auxiliary parameter to find local classes parents + * + * The parameters [visited], [looped], [pathOrderedSet] exist + * to avoid repeated memory allocation for each search, see `LLFirSupertypeComputationSession`. */ protected fun breakLoopFor( declaration: FirClassLikeDeclaration, session: FirSession, visited: MutableSet<FirClassLikeDeclaration>, // always empty for LL FIR looped: MutableSet<FirClassLikeDeclaration>, // always empty for LL FIR - pathSet: MutableSet<FirClassLikeDeclaration>, - path: MutableList<FirClassLikeDeclaration>, + pathOrderedSet: LinkedHashSet<FirClassLikeDeclaration>, localClassesNavigationInfo: LocalClassesNavigationInfo?, ) { - require(path.isEmpty()) { "Path should be empty" } - require(pathSet.isEmpty()) { "Path set should be empty" } + require(pathOrderedSet.isEmpty()) { "Path ordered set should be empty before starting" } /** * Local function that operates as a DFS node during loop search. @@ -706,16 +706,16 @@ } if (classLikeDeclaration in visited) { - if (classLikeDeclaration in pathSet) { + if (classLikeDeclaration in pathOrderedSet) { looped.add(classLikeDeclaration) - looped.addAll(path.takeLastWhile { element -> element != classLikeDeclaration }) + looped.addAll(pathOrderedSet.reversed().takeWhile { element -> element != classLikeDeclaration }) } return } - path.add(classLikeDeclaration) - pathSet.add(classLikeDeclaration) + val declarationIsAdded = pathOrderedSet.add(classLikeDeclaration) + require(declarationIsAdded) { "The considered declaration should be unique" } visited.add(classLikeDeclaration) val classId = classLikeDeclaration.classId @@ -736,8 +736,7 @@ // This is an optimization that prevents collecting // loops we don't want to report anyway. if (wereTypeArgumentsInvolved && isSubtypingCurrentlyInvolved) { - path.removeAt(path.size - 1) - pathSet.remove(classLikeDeclaration) + pathOrderedSet.remove(classLikeDeclaration) // This declaration can be visited once more, for example, to find loops beginning with it visited.remove(classLikeDeclaration) return @@ -800,19 +799,17 @@ reportLoopErrorRefs(classLikeDeclaration, resultSupertypeRefs) } - path.removeAt(path.size - 1) - pathSet.remove(classLikeDeclaration) + pathOrderedSet.remove(classLikeDeclaration) } checkIsInLoop(declaration, wasSubtypingInvolved = false, wereTypeArgumentsInvolved = false) - require(path.isEmpty()) { "Path should be empty" } + require(pathOrderedSet.isEmpty()) { "Path ordered set should be empty after finishing" } } fun breakLoops(session: FirSession, localClassesNavigationInfo: LocalClassesNavigationInfo?) { val visitedClassLikeDecls = mutableSetOf<FirClassLikeDeclaration>() val loopedClassLikeDecls = mutableSetOf<FirClassLikeDeclaration>() - val path = mutableListOf<FirClassLikeDeclaration>() - val pathSet = mutableSetOf<FirClassLikeDeclaration>() + val pathOrderedSet = LinkedHashSet<FirClassLikeDeclaration>() for (classifier in newClassifiersForBreakingLoops) { breakLoopFor( @@ -820,8 +817,7 @@ session = session, visited = visitedClassLikeDecls, looped = loopedClassLikeDecls, - pathSet = pathSet, - path = path, + pathOrderedSet = pathOrderedSet, localClassesNavigationInfo = localClassesNavigationInfo, ) }