Community
Participate
Working Groups
Created attachment 208046 [details] Effect of cycles in a call chain graph Hi, this is the beginning of a series of questions/design decisions regarding a call chain completion engine for/based-on JDT (see http://code-recommenders.blogspot.com/2010/12/how-do-i-get-instance-of.html if you need more information on call chain completion). The intent of these questions is to discuss implementation decisions before the code gets written and to learn what you appreciate most. Call chain also has some characteristics which may be show-stoppers to become part of JDT. Thus, your feedback is very appreciated. This post is about limiting the search space as soon as a known type has been observed. See the example screenshot attached. When triggering code completion on "PlatformUI.<^Space>", we get 7 proposals with a length up to 5 (search has been limited to maxlength=5)). You see that there is a circle in the call-graph for IWorkbench: getWorkbench() -> getActiveWorkbenchWindow() -> getWorkbench() getWorkbench() -> getWorkbenchWindows()[index] -> getWorkbench() getWorkbench() -> showPerspective() -> getActiveWorkbenchWindow() -> getWorkbench() ... There are other examples with result in an even worse dependency graphs with hundreds of chains. Question: How should the engine deal with these kinds of circles? Option 1: Stop as soon as the same type has been part of the chain? This would cut off many paths, potentially also interesting ones. (Need an example?) Option 2: Put in as many paths as possible to find until completion timeout occurs. This is not perfectly heuristic and leads to many results. People might get flooded with proposals. In this case, call-chain completion should work as a quick fix rather than a code completion (maybe it should do so in general). Option 3: Limit the number of proposal to the, say, 7 shortest proposals. People don't get flooded but probably don't get the proposals they want. As a side-note: We have in mind an approach that collects the information which proposals have been used actually used in similar situations. Given this info, we can cut down the number of proposals furthermore. Whats your opinion on that? Option 1, 2, or 3? Or something different?
(In reply to comment #0) > Question: How should the engine deal with these kinds of circles? > > Option 1: Stop as soon as the same type has been part of the chain? > This would cut off many paths, potentially also interesting ones. (Need an > example?) This could be the right option to take, unless we get examples where interesting paths are cut off, for example a cycle returns a different object of the same type. > Option 2: Put in as many paths as possible to find until completion timeout > occurs. > This is not perfectly heuristic and leads to many results. People might get > flooded with proposals. In this case, call-chain completion should work as a > quick fix rather than a code completion (maybe it should do so in general). This option is also not too bad, at least to begin with. > Option 3: Limit the number of proposal to the, say, 7 shortest proposals. > People don't get flooded but probably don't get the proposals they want. In general, you should show all possible proposals while keeping the most relevant proposals on top. This way a user can find any proposal via filtering. Hence I would not limit the number of proposals to an arbitrary number. > As a side-note: We have in mind an approach that collects the information which > proposals have been used actually used in similar situations. Given this info, > we can cut down the number of proposals furthermore. So far JDT does not collect usage information, and I don't think we want to venture in this area in near future. The real question is, whether call chain completion are included in the default proposals i.e. shown on the first 'Ctrl+space' or not. This will depend on the quality of Chain completion proposals. To begin with, I would probably keep Chain completions on a non-default list.
To summarize: I'll go for: * show all possible chains and order by length. * run on non-default content assist (to be done). * dependency to jdt.core 3.8 * no dependencies to other plug-ins than jdt.* or core platform. * written for Java 1.6 Regarding click-feedback: The click-feedback leveraging version would be part of Code Recommenders. Regarding timeouts / multi-threading: Traversing the chain graph, resolving types and argument names takes a considerable amount of time. Given a max timeout of ~4 seconds our implementations use a separate ThreadPool inside the chain completion proposal computer. Is this acceptable for JDT too? Regarding members to travers: At the moment, we only consider public methods and fields as edges in the call chain graph. Visibility checks are *not* performed, thus some expected edges can be missed. This is more an information than a question. It should be relatively straight-forward to implement later.
(In reply to comment #2) > To summarize: > > * written for Java 1.6 JDT/UI is on Java 1.5 > Regarding timeouts / multi-threading: > Traversing the chain graph, resolving types and argument names takes a > considerable amount of time. Given a max timeout of ~4 seconds our > implementations use a separate ThreadPool inside the chain completion proposal > computer. Is this acceptable for JDT too? 4 secs is probably a bit too much. Currently the default value of 'Timeout for fetching a parameter name from attached Javadoc' (for use in content assist) is set to 50 ms. This should give an idea on expected performance of content assist. However, as Chain completions are expected to save developers from manually hunting for stuff, 4 seconds might also be acceptable.
(In reply to comment #0) > Option 1: Stop as soon as the same type has been part of the chain? > This would cut off many paths, potentially also interesting ones. (Need an > example?) This option looks the best among the given choices. Usually, I wouldn't expect to get a different object from the same method in a cycle (or a 'circle'). That said, re-calling that method will be wasteful code i.e. one should call getWorkbench() and assign it to an object and then use it for different purposes. > Option 2: Put in as many paths as possible to find until completion timeout > occurs. This option will be tempt you to increase timeout limits. However, a word of caution about that - users may not be too patient with content assist waiting for upto 4 secs. Especially because only in a few cases will that 4 sec wait be really worth it. Rest of the times the user will know what he wants to call and will invoke content assist to aid in typing. In that case, it'll be annoying to wait for too long. Even with the current timeout, I've heard complaints that content assist is slow (eg. in constructor completion) and its annoying to people.
Created attachment 208070 [details] chain completion v0.1 This is a first draft of call chain completion based on JDT 3.8 APIs only. Please note that *this code is a prototype*. It has been rewritten from ground up in the last days to present a working prototype on JDT 3.8 before M5 starts. I did not spent too much time on cleaning it up. Dependencies to non Eclipse APIs have been removed. A few utility classes from org.eclipse.recommenders.utils have been copied into the "dep" package for my personal convenience and will be removed or replaced later on. http://goo.gl/DHwEV contains the test suite for call chain completion. It's not an extensive test suite. If you experience any issues I would welcome new test cases (that use Java 1.6 APIs only). Limitations I'm aware of: * only public elements are used to build call chains. Package visibile elements that might be accessible are not considered and thus may lead to missing chains. * Generics are ignored. Assignments like List<Object> dontUse; List<String s = $ --> dontUse (will be proposed...) are possible. * No completions in message send as in "method($)". * No constructors are proposed (needed?) * Search should be canceled after 4 seconds in any case. However, you will notice short UI freezes if search takes little longer. * completion on fields of another field/local as in "event.evt.$" don't work yet. What should work: Completion on assignments "X x = $" Completion with prefixes "X x = me$" -> all elements that start with me Completion on static types: "X x = Collections.$" Completion on method returns "return $" Completion that use arrays as return type as in "getWorkbenchWindows()[index]" The source code is hosted and maintained here: http://goo.gl/V0c1v An initial test suite is defined here: http://goo.gl/DHwEV Best, Marcel
(In reply to comment #5) > Created attachment 208070 [details] > chain completion v0.1 > > This is a first draft of call chain completion based on JDT 3.8 APIs only. I was expecting a patch for JDT/UI :-)
(In reply to comment #6) > > This is a first draft of call chain completion based on JDT 3.8 APIs only. > I was expecting a patch for JDT/UI :-) I'm confused: You changed it From JDT UI to JDT Text: >> Deepak Azad <deepak.azad@in.ibm.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |deepak.azad@in.ibm.com Component|UI |Text AssignedTo|jdt-ui-inbox@eclipse.org |jdt-text-inbox@eclipse.org Summary|Call Chain Completion |[content assist] Call Chain | |Completion << Or do you mean it should not be based on the latest JDT.core with Ayushman's patch for completion context? Anyway. One more sentence to the patch. Since I'm not fully aware of all JDT APIs, I moved almost all code that extensively uses internal APIs into the InteralApiHelper. I guess there is a lot that might be replaced by internal code that already exists somewhere.
(In reply to comment #7) > (In reply to comment #6) > > > This is a first draft of call chain completion based on JDT 3.8 APIs only. > > I was expecting a patch for JDT/UI :-) > > I'm confused: You changed it From JDT UI to JDT Text: It is a blurry distinction between UI and Text in any case since there is only one plugin/project org.eclipse.jdt.ui. What I meant was I expected a patch for this project and not a separate project. (See http://wiki.eclipse.org/Platform-releng/Git_Workflows#Create_a_patch)
(In reply to comment #8) > What I meant was I expected a patch for this project and not a separate project. (See > http://wiki.eclipse.org/Platform-releng/Git_Workflows#Create_a_patch) Ok, got that. I'll provide a patch against the latest git repository next time.
FWIW, the rewrite for JDT call chain continued in code recommenders repository. It now uses an internal thread pool for computing the callchain graph using "times number of cores" threads. Several minor improvements have been made regarding completion on fields and code readability. A preliminary top-level design description is available here: http://eclipse.org/recommenders/docbook/ch03.html#isv-chain-completion Dani, I'll wait for some kind of feedback before migrating this code to jdt/ui - something like "thumbs up"/"thumbs down".
(In reply to comment #0) > When triggering code completion on "PlatformUI.<^Space>", we get 7 proposals > with a length up to 5 (search has been limited to maxlength=5)). You see that > there is a circle in the call-graph for IWorkbench: > > getWorkbench() -> getActiveWorkbenchWindow() -> getWorkbench() > getWorkbench() -> getWorkbenchWindows()[index] -> getWorkbench() > getWorkbench() -> showPerspective() -> getActiveWorkbenchWindow() -> > getWorkbench() > ... > > There are other examples with result in an even worse dependency graphs with > hundreds of chains. > > > > Question: How should the engine deal with these kinds of circles? It should stop (and not show) when a call has the same name and return type. > To begin with, I would probably keep Chain completions on a non-default list. +1. Regarding the time it needs to compute the proposals: there's a hard limit (5s) which will trigger a dialog showing the user which proposal computer took too much time. > Given a max timeout of ~4 seconds our > implementations use a separate ThreadPool inside the chain completion proposal > computer. What's the benefit of the thread pool? Do you compute the proposals in parallel? Loading the attached bundles gives tons of compile errors because the BREE is set to 1.5 but the compliance is set to 1.6. >Ok, got that. I'll provide a patch against the latest git repository next time. You'd have to provide a patch for JDT Core and one for JDT UI (two different repositories). I assume that the computation of the proposals can be done more efficiently inside the JDT Core code. >http://eclipse.org/recommenders/docbook/ch03.html#isv-chain-completion This gives me 404.
> Loading the attached bundles gives tons of compile errors because the BREE is > set to 1.5 but the compliance is set to 1.6. Actually it compiles as attached here, but if it's loaded in the workspace and the compliance is fixed to match the BREE (1.5), one gets the errors.
(In reply to comment #11) > > Question: How should the engine deal with these kinds of circles? > > It should stop (and not show) when a call has the same name and return type. ok. > > Given a max timeout of ~4 seconds our > > implementations use a separate ThreadPool inside the chain completion proposal > > computer. > What's the benefit of the thread pool? Do you compute the proposals in > parallel? Yes, we do since it's an exhaustive search that potentially creates hundreds of thousands search paths. In a multi-core environment this worked out well. But if working on the compiler representation would be much faster, this might be preferred the way to go. > >Ok, got that. I'll provide a patch against the latest git repository next time. > You'd have to provide a patch for JDT Core and one for JDT UI (two different > repositories). I assume that the computation of the proposals can be done more > efficiently inside the JDT Core code. OK, I've to figure out how then. Questions regarding how/when to use the compiler classes are probably better posted in the forum, right? Maybe it makes sense to move all the analysis stuff we do into the compiler AST if it's much faster? > >http://eclipse.org/recommenders/docbook/ch03.html#isv-chain-completion > This gives me 404. http://eclipse.org/recommenders/documentation/isv.html#isv-chain-completion
> OK, I've to figure out how then. Questions regarding how/when to use the > compiler classes are probably better posted in the forum, right? Since this is a concrete work item, I think communication is better/faster through the bug, even if you only ask questions. Ayush is cc-ed, so he can help with those.
(In reply to comment #14) > Ayush is cc-ed, so he can help with those. Ayush, is it possible to do all the completion API graph traversal on org.eclipse.jdt.internal.compiler.lookup.Bindings only? Will it be much faster than working on the IJavaElement equivalents? Is there anything special I should take care of? Can I get access to the latest org.eclipse.jdt.internal.compiler.ast.TypeDeclaration or org.eclipse.jdt.internal.compiler.ast.MethodDeclaration given that I only have a JavaElement? Thanks, Marcel
(In reply to comment #15) > (In reply to comment #14) > > Ayush is cc-ed, so he can help with those. > > Ayush, is it possible to do all the completion API graph traversal on > org.eclipse.jdt.internal.compiler.lookup.Bindings only? Will it be much faster > than working on the IJavaElement equivalents? Assuming that you're not changing the way JDT/Core calculates the proposals, but only collecting those proposals first and then building the call graph, you'd be working with IJavaElements and not Bindings. In that case, working with the java elements should be more efficient, both in terms of performance and memory. You can obtain the bindings using org.eclipse.jdt.core.dom.ASTParser.createBindings(IJavaElement[], IProgressMonitor), but this call itself creates a binding so its not cheap. However, if I'm wrong and you do have bindings with you, then working with bindings may be more straightforward. Do let me know if you plan any changes for JDT/Core as well. Please also open a bug against JDT/Core for the same so we can track it easily. > Can I get access to the latest > org.eclipse.jdt.internal.compiler.ast.TypeDeclaration or > org.eclipse.jdt.internal.compiler.ast.MethodDeclaration given that I only have > a JavaElement? org.eclipse.jdt.core.dom.CompilationUnit.findDeclaringNode(String) should work. You need to pass the binding key to this method which can be obtained by getKey() methods (in one of the subtypes of IJavaElement) HTH
(In reply to comment #16) Just to make sure we speak about the same APIs: I was speaking about jdt.core.compiler bindings - not jdt.core.dom bindings The InternalCoreCompletionContext gives me access to the compiler bindings for all visible fields, methods and variables. I currently create JavaElements from these compiler bindings, and use these elements as starting points for the call chain search. Dani proposed to use some jdt core api: > I assume that the computation of the proposals can be done more > efficiently inside the JDT Core code. I'd just like to know what exactly this means... (dom vs. compiler vs. javaelements vs. ???) :) Thanks.
(In reply to comment #17) > The InternalCoreCompletionContext gives me access to the compiler bindings for > all visible fields, methods and variables. I currently create JavaElements from > these compiler bindings, and use these elements as starting points for the call > chain search. Oh! I thought you're going the other way round. :) > Dani proposed to use some jdt core api: > > > I assume that the computation of the proposals can be done more > > efficiently inside the JDT Core code. > > I'd just like to know what exactly this means... (dom vs. compiler vs. > javaelements vs. ???) :) I see. Inside the compiler, everything can be done using compiler bindings since they're there already. Using java elements is a wasteful indirection unless memory is an issue, since bindings are heavier. However, I still don't have clarity on what you want to do inside JDT/Core. The proposals are already being computed there - do you intend to recursively call complete(..) on each proposal?
(In reply to comment #18) > However, I still don't have clarity on what you want to do inside JDT/Core. The > proposals are already being computed there - do you intend to recursively call > complete(..) on each proposal? Given a method binding, I request the return type of the method and travers all its visible members recursively until a path through the API graph is found that returns an instance of the requested type or a traversal limit is reached. Same is done for fields and local variables. We don't call any completion engine here but do the complete traversal on our own yet. But maybe there is some code we can reuse... Maybe this figure (http://eclipse.org/recommenders/documentation/isv.html#isv-chain-completion) helps how we traverse the API graph.
(In reply to comment #19) > [..]. But maybe there is > some code we can reuse... Ok. In this case you can just do the traversal on the bindings, but you might want to have a lightweight data structure such as the org.eclipse.jdt.core.CompletionProposal to store your results in the completion requestor. I don't think there's any code in jdt.core which can be reused as such. We do have ASTVisitor but thats not valid for your case.
Thanks Ayush. Two more questions: How can I obtain to the (compiler) TypeDeclaration or MethodDeclaration if I have its counterpart as jdt.core.dom or jdt.core javaelement object? If it's not straight forward, can you make the assistScope accessible from InternalCompletionContext via getAssistScope()? From what I can see so far, this gives access to the enclosing method and would enable us to our completion analysis on the compiler data structures (assuming it is faster than working on the dom.AST bindings).
(In reply to comment #21) > Thanks Ayush. > > Two more questions: > How can I obtain to the (compiler) TypeDeclaration or MethodDeclaration if I > have its counterpart as jdt.core.dom or jdt.core javaelement object? After obtaining the dom ast node as suggested in comment 16 you can use org.eclipse.jdt.core.dom.DefaultBindingResolver.newAstToOldAst to get compiler AST node. However, as you can see that's a roundabout route. > If it's not straight forward, can you make the assistScope accessible from > InternalCompletionContext via getAssistScope()? Yeah, I don't see any problem with that. Go ahead and file a bug, I can do that for M6
