eclipse-jdt / eclipse-jdt/eclipse.jdt.ui

Endless loop in RippleMethodFinder2.UnionFind.find

Open
#1,065 2 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
Java
Stars
59
Forks
127
Avg merge
22h 47m
Merged PRs (30d)
28

Description

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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.