Endless loop in RippleMethodFinder2.UnionFind.find

guw commented 7 months ago

While working in a self-hosting session I attempted a method signature refactoring. This took a very long time and pausing the ModalContext thread and stepping through it I found an endless loop in the following code.

https://github.com/eclipse-jdt/eclipse.jdt.ui/blob/756cca59703dbd314fdc10fd79f5ec1add7978ca/org.eclipse.jdt.core.manipulation/core%20extension/org/eclipse/jdt/internal/corext/refactoring/rename/RippleMethodFinder2.java#L101-L104

What happened was that the loop changed root and rep in each iteration.

loop N: rep = ResolvedBinaryType (id=522) and root = ResolvedBinaryType (id=421)
loop N+1: rep = ResolvedBinaryType (id=421) and root = ResolvedBinaryType (id=522)
loop N+2: rep = ResolvedBinaryType (id=522) and root = ResolvedBinaryType (id=421)

With the following types:

interface Builder {key=Lcom/google/protobuf/MessageLite$Builder;} [in MessageLite$Builder.class [in com.google.protobuf [in /Users/.../external/com_google_protobuf_protobuf_java/protobuf-java-3.22.3.jar]]]

interface Builder {key=Lcom/google/protobuf/Message$Builder;} [in Message$Builder.class [in com.google.protobuf [in /Users/.../external/com_google_protobuf_protobuf_java/protobuf-java-3.22.3.jar]]]

So somehow the fElementToRepresentative map contains a mapping for each other. This causes the endless loop. I don't know whether the fElementToRepresentative is invalid, i.e. it is never supposed to contain a recursive mapping, or whether the loop is incorrect, i.e. the loop is supposed to check for visited items.

Also, since this is a refactoring, I am confused by BinaryTypes are even processed.

The callstack to the find method is:

Thread [ModalContext] (Suspended)   
    RippleMethodFinder2$UnionFind.find(IType) line: 101 
    RippleMethodFinder2.uniteWithSupertypes(IType, IType) line: 518 
    RippleMethodFinder2.uniteWithSupertypes(IType, IType) line: 531 
    RippleMethodFinder2.uniteWithSupertypes(IType, IType) line: 521 
    RippleMethodFinder2.uniteWithSupertypes(IType, IType) line: 521 
    RippleMethodFinder2.createUnionFind() line: 505 
    RippleMethodFinder2.findAllRippleMethods(IProgressMonitor, WorkingCopyOwner) line: 222  
    RippleMethodFinder2.getAllRippleMethods(IProgressMonitor, WorkingCopyOwner) line: 187   
    RippleMethodFinder2.getRelatedMethods(IMethod, ReferencesInBinaryContext, IProgressMonitor, WorkingCopyOwner) line: 180 
    ChangeSignatureProcessor.checkFinalConditions(IProgressMonitor, CheckConditionsContext) line: 823   
    ProcessorBasedRefactoring.checkFinalConditions(IProgressMonitor) line: 227  
    CheckConditionsOperation.run(IProgressMonitor) line: 86 
    CreateChangeOperation.run(IProgressMonitor) line: 122   
    UIPerformChangeOperation(PerformChangeOperation).run(IProgressMonitor) line: 210    
    Workspace.run(ICoreRunnable, ISchedulingRule, int, IProgressMonitor) line: 2453 
    Workspace.run(IWorkspaceRunnable, ISchedulingRule, int, IProgressMonitor) line: 2478    
    WorkbenchRunnableAdapter.run(IProgressMonitor) line: 89 
    ModalContext$ModalContextThread.run() line: 122

On a side note, RippleMethodFinder2.getRelatedMethods is ignoring the IProgressMonitor. Therefore the cancellation is a not working and Eclipse appears to hang.

jukzi commented 7 months ago

Please give a minimal reproducer

guw commented 7 months ago

I can't this is closed source code base with many jars. I am able to collect more debug output if you need it.

eclipse-jdt / eclipse.jdt.ui

Endless loop in RippleMethodFinder2.UnionFind.find #1065