Bug 194358 - [import rewrite] Organize Imports produces wrong order of imports
Summary: [import rewrite] Organize Imports produces wrong order of imports
Status: VERIFIED FIXED
Alias: None
Product: JDT
Classification: Eclipse Project
Component: Core (show other bugs)
Version: 3.3   Edit
Hardware: PC Linux
: P3 normal with 16 votes (vote)
Target Milestone: 3.6 M6   Edit
Assignee: Olivier Thomann CLA
QA Contact:
URL:
Whiteboard:
Keywords:
: 173551 275918 295220 (view as bug list)
Depends on: 295638
Blocks: 235253 295220
  Show dependency tree
 
Reported: 2007-06-25 23:11 EDT by Sergey Prigogin CLA
Modified: 2010-05-21 02:47 EDT (History)
12 users (show)

See Also:


Attachments
Bug fix + regression test to fix the issue. (4.68 KB, patch)
2009-01-10 13:46 EST, Al Maw CLA
frederic_fusier: review-
Details | Diff
Patch with performance marking logs (2.69 KB, patch)
2009-09-30 02:59 EDT, Jay Arthanareeswaran CLA
no flags Details | Diff
Patch with added performance test (7.91 KB, patch)
2009-10-05 07:09 EDT, Jay Arthanareeswaran CLA
no flags Details | Diff
Updated patch (7.35 KB, patch)
2009-10-08 05:04 EDT, Jay Arthanareeswaran CLA
frederic_fusier: review-
Details | Diff
Patch for perf_35x (2.59 KB, patch)
2009-10-09 05:03 EDT, Jay Arthanareeswaran CLA
frederic_fusier: iplog+
frederic_fusier: review+
Details | Diff
Updated patch with fix for on-demand issue. (11.55 KB, patch)
2009-11-04 14:56 EST, Kelly Campbell CLA
no flags Details | Diff
Latest patch (11.68 KB, patch)
2009-11-05 12:00 EST, Jay Arthanareeswaran CLA
frederic_fusier: review-
Details | Diff
Updated patch (13.42 KB, patch)
2009-11-11 01:24 EST, Jay Arthanareeswaran CLA
no flags Details | Diff
Updated patch (13.64 KB, patch)
2009-11-13 03:45 EST, Jay Arthanareeswaran CLA
frederic_fusier: review+
Details | Diff
Proposed fix (15.31 KB, patch)
2009-11-20 10:22 EST, Olivier Thomann CLA
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Sergey Prigogin CLA 2007-06-25 23:11:45 EDT
3.3 RC3 I20070601-1539:

Organize Imports command puts Map.Entry after Set. It should put it before.

import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
Comment 1 Trevor Robinson CLA 2008-10-29 17:45:01 EDT
Martin, do you have any advice on where to look in the code if I were to take a stab at fixing this? I've looked at OrganizeImportsAction and OrganizeImportsOperation, but where the sorting happens wasn't immediately evident.
Comment 2 Tom Ball CLA 2009-01-08 18:02:51 EST
The expected sorting behavior is to first sort by package (1), then by outer type (2), then by inner types (3):

1    java.io.File     
1    java.util.List
2      java.util.Map
3        java.util.Map.Entry
4          java.util.Map.Entry.Foo // etc.
2      java.util.Set

The issue is that import organizing doesn't use packages and types, but instead groups and packages in org.eclipse.jdt.internal.core.dom.rewrite.ImportRewriteAnalyzer.  It starts with the list of known groups defined in the organize import preferences, then adds packages to their respective groups.  All "type containers" are considered packages, so any inner class import causes its outer class to be considered a package: 

    java                // group defined in organize imports prefs
    java.io.File        // create java.io pkg, add File, add to group
    java.util.List      // create java.util pkg, add List, add to group
    java.util.Map       // add Map to java.util
    java.util.Map.Entry // create java.util.Map pkg, add Entry, add to group
    java.util.Set       // add Set to java.util

The java group now has two packages:  java.util, and java.util.Map.  Sorting is done at group insertion and package insertion, causing:

  (java.io)
    java.io.File
  (java.util)
    java.util.List
    java.util.Map
    java.util.Set
  (java.util.Map)
    java.util.Map.Entry

I suggest that PackageEntry be renamed something like ImportGroup, and that ImportDeclEntry include a list of children (PackageEntry is deleted).  Group sort order remains set by the current preferences, ImportDeclEntry instances are sorted by name (as is currently done), and child ImportDeclEntry instances sorted by name in the children list.  Imports are written out by having each group write out each ImportDeclEntry, which first writes its elementName followed by its children:

  (java)
    java.io.File
    java.util.List
    java.util.Map
      java.util.Map.Entry
    java.util.Set

If there's interest, I can create a patch that implements this change.  By eliminating the PackageEntry/ImportDeclEntry distinction, it may result is less code.
Comment 3 Tom Ball CLA 2009-01-08 18:06:41 EST
> The java group now has two packages:  java.util, and java.util.Map.

That should read:  The java group now has three packages:  java.io, java.util, and java.util.Map.
Comment 4 Al Maw CLA 2009-01-10 13:46:26 EST
Created attachment 122186 [details]
Bug fix + regression test to fix the issue.

Please find attached a patch containing a fix plus a regression test for this issue.
Comment 5 Martin Aeschlimann CLA 2009-01-15 06:06:33 EST
Note that IJavaProject.findType is an expensive call to make and applying this patch will add a performance penalty for all usages of the import rewriter.
Comment 6 Markus Keller CLA 2009-01-15 06:24:20 EST
> Note that IJavaProject.findType is an expensive call to make and applying this
> patch will add a performance penalty for all usages of the import rewriter.

We could first check whether the simple name of the qualifier starts with an uppercase letter and only call findType() if the container really looks like an enclosing type (an not a package) by the Java naming conventions.

Moving to JDT/Core.
Comment 7 Al Maw CLA 2009-01-15 11:31:05 EST
I'm aware the cost isn't free, but this patch is minimally invasive for a correct result. I thought about just checking the case of the first letter of the class, but obviously people are free to name their classes with lowercase if they like - there's nothing enforced by the compiler in this regard. We should make it work universally, surely?

It would be better to rewrite this class so that it is much simpler. One could take the list of package orders specified by the user and for each one add a flat sorted list of all the imports under it. Making a tree structure as is done currently seems over-complex and completely unnecessary. That said, I didn't want to create a huge, invasive patch for this which completely changes how the class works. Thoughts?
Comment 8 Al Maw CLA 2009-04-14 10:30:14 EDT
This is still annoying me a great deal day-to-day. :-(
This patch has been in jdt-core-inbox for months now - can someone take a look?
Comment 9 Robert Konigsberg CLA 2009-05-07 17:03:13 EDT
Adding self to list. Yes, can someone please look at this? 
Comment 10 Nick Chalko CLA 2009-05-12 13:32:29 EDT
*** Bug 275918 has been marked as a duplicate of this bug. ***
Comment 11 Kelly Campbell CLA 2009-07-23 12:31:26 EDT
Ping?
Comment 12 Al Maw CLA 2009-07-23 12:39:09 EDT
I don't know about "ping".

The ~15 line patch I provided to fix this longstanding bug has been languishing here for six months without anyone doing anything about it. No offense, but my experience here is not really convincing me to contribute to the project and help fix other issues. Shame. :-(
Comment 13 Olivier Thomann CLA 2009-07-23 13:39:31 EDT
Jay,

Since David didn't look at it, could you please see what can be done with this?
Ideally we should minimize the performance impact for this fix (see comment 5).
Comment 14 Olivier Thomann CLA 2009-07-23 13:41:57 EDT
(In reply to comment #12)
> The ~15 line patch I provided to fix this longstanding bug has been languishing
> here for six months without anyone doing anything about it. No offense, but my
> experience here is not really convincing me to contribute to the project and
> help fix other issues. Shame. :-(
Thanks for the patch.
Comment 15 Tom Ball CLA 2009-07-23 13:48:18 EDT
(In reply to comment #5)
> Note that IJavaProject.findType is an expensive call to make and applying this
> patch will add a performance penalty for all usages of the import rewriter.

Is there any data to back-up this assertion?  Just noting that a call can be expensive in theory doesn't guarantee a performance penalty in practice.  

Organize Imports has two uses I'm aware of:  adding missing imports, where you want the certainty of a findType() result rather than some weaker lookup; and sorting existing imports, where all the types for the source file have already been fetched and are therefore cheap to re-reference.  The latter use needs to be fast because of the option to re-organize imports on save, but since the types are available from the last AST fetch, any findType() overhead should be dwarfed by the cost of the disk IO.

Comment 16 Al Maw CLA 2009-07-23 13:51:39 EDT
I can see three options here regarding performance:

1. Assume everyone follows standard naming conventions and names their classes
with an initial capital. Don't bother doing a full-blown check and just assume
anything with an initial cap is a class, otherwise it's a package. Not 100%
correct behaviour, but will work in the majority of cases and be an improvement
over the status quo. I'd be happy to modify the patch to do this if that's what
people want.

2. Accept this patch as-is.

3. Rewrite this entire class to be much simpler.

I didn't figure my chances of getting #3 through review would be very high
given I'm unknown in the Eclipse community. That said, if test coverage here is high enough to trust me to, I'd be happy to (the class is hopelessly complicated given what it does).
Comment 17 Sergey Prigogin CLA 2009-07-23 13:56:02 EDT
(In reply to comment #5)
> Note that IJavaProject.findType is an expensive call to make and applying this
> patch will add a performance penalty for all usages of the import rewriter.

In order to decide if the performance overhead of the patch is acceptable or not, somebody has to measure time it takes to organize imports on a file with a large number of imports with and without the patch. Import rewriter is not called very often, so anything up to 1 second should be acceptable.


Comment 18 Olivier Thomann CLA 2009-07-23 14:01:11 EDT
Jay,

Could you please try to get some benchmarks with and without the patch?
Once we have some datas we can decide if the patch gets it as is.
Thanks.
Comment 19 Jay Arthanareeswaran CLA 2009-09-29 02:00:56 EDT
These are the numbers for the new test (over 39 runs) and considering only samples well within standard deviation range:

With patch:
5.15 msec

Without patch: 
3.008 msec
Comment 20 Olivier Thomann CLA 2009-09-29 09:29:00 EDT
Thanks Jay.
I'll review the patch.
Comment 21 Olivier Thomann CLA 2009-09-29 11:56:43 EDT
Jay, what was the size of your code for the benchmark ?
Comment 22 Jay Arthanareeswaran CLA 2009-09-30 02:59:52 EDT
Created attachment 148389 [details]
Patch with performance marking logs

Well, I just used the same test as attached in the comment #4 and introduced the log messages. Attaching the patch with those logs.
Comment 23 Dani Megert CLA 2009-09-30 03:12:12 EDT
Jay, this is by far too small to serve as a serious performance test case ;-)

Please create (i.e. generate) a performance test case/workspace with more than 1000 types and make sure the CUs have up to 100 imports. Maybe there's already a framework in the JDT Core performance test suite that does this for you. Frédéric can you help out here?

And then measure the performance impact of the fix based on that test case.
Comment 24 Frederic Fusier CLA 2009-09-30 04:38:52 EDT
(In reply to comment #23)
> Jay, this is by far too small to serve as a serious performance test case ;-)
> 
> Please create (i.e. generate) a performance test case/workspace with more than
> 1000 types and make sure the CUs have up to 100 imports. Maybe there's already
> a framework in the JDT Core performance test suite that does this for you.
> Frédéric can you help out here?
> 
> And then measure the performance impact of the fix based on that test case.

There's currently no performance test cases for AST rewriting, hence a new test must be added to the FullSourceWorkspaceASTTests. I think the best solution would be to pick-up a compilation unit with a long list of import in the Eclipse 3.0 full source workspace used for the test and repeat the Organize Import operation enough times to get a test duration over the 100 ms threshold...
Comment 25 Jay Arthanareeswaran CLA 2009-10-05 07:09:52 EDT
Created attachment 148758 [details]
Patch with added performance test

Added a new performance test, which is included in the patch. The results don't show any significant performance impact or improvement with the patch. For the added performance test, the elapsed process time was in the range or 337ms to 340ms (both with and without patch)

Note that the CompilationUnit used in the performance test (JavaProject.java) has about 80 import statements with two inner type imports.
Comment 26 Frederic Fusier CLA 2009-10-05 08:43:15 EDT
(In reply to comment #25)
> Created an attachment (id=148758) [details]
> Patch with added performance test
> 
> Added a new performance test, which is included in the patch. The results don't
> show any significant performance impact or improvement with the patch. For the
> added performance test, the elapsed process time was in the range or 337ms to
> 340ms (both with and without patch)
> 
> Note that the CompilationUnit used in the performance test (JavaProject.java)
> has about 80 import statements with two inner type imports.

2 remarks for the added performance tests:
1) I do not see any reason to multiply the number of measures by 2, 
   MEASURES_COUNT is 10, I think this is enough to have a good idea whether
   the test is stable or not
2) The compilation unit is got inside the internal loop, hence the time to do it
   is also measured in the test... May be I'm wrong, but I do not think the CU
   is modified while using the ImportRewrite, only a TextEdit is created, hence
   as it was done in testPerfDomAstCreationJLS3, you'd rather to get the CU 
   before the measures loop and just use it while calling the rewriteImport
   method inside the loop. Then the measured time will better narrow the tested
   functionality...
Comment 27 Jay Arthanareeswaran CLA 2009-10-08 05:04:11 EDT
Created attachment 149099 [details]
Updated patch

Modified the performance tests as per Fred's comments. The performances (with and without patch) more or less match with each other. 

Fred, I have removed the multiplying factor. However I have kept the internal loop (with count at 10) so that the elapsed process is above 100 ms.
Comment 28 Frederic Fusier CLA 2009-10-08 05:24:17 EDT
(In reply to comment #27)
> Created an attachment (id=149099) [details]
> Updated patch
> 
> Modified the performance tests as per Fred's comments. The performances (with
> and without patch) more or less match with each other. 
> 
> Fred, I have removed the multiplying factor. However I have kept the internal
> loop (with count at 10) so that the elapsed process is above 100 ms.

The performance test looks good now. Note that it also must be added to the perf_35x branch to be measured in the baseline run, so please prepare a patch for this stream, thanks
Comment 29 Jay Arthanareeswaran CLA 2009-10-09 05:03:50 EDT
Created attachment 149218 [details]
Patch for perf_35x

Attaching the patch with the performance test for the perf_35x stream.
Comment 30 Frederic Fusier CLA 2009-10-23 12:04:54 EDT
Looking at the patch (I only looked at performance tests initially...), I still worry about the performance impact of that fix when there will have several inner classes in the import list. For that classes, the findType(...) will open the enclosing compilation unit, hence may slow down in a noticeable manner the ImportRewriterAnalyser. I guess that the performance test does not show any visible regression as the compilation unit used for the test does not have any inner class in the import declaration list.

However, talking about this with Jérôme, it appears that:

1) the loop isn't necessary, as the top level can be easily found for an IType
   by calling the getTypeRoot() method and the qualifier name is simply the name
   of the top level parent... As the loop disappears, it does no longer seem to 
   be necessary to split the getQualifier(ImportDeclaration) method...

2) if the rewrite imports operation is always done inside a reconciling context 
   (i.e. the compilation unit has been resolved), then the compilation unit of 
   the list should already have been opened, hence making a find type on the 
   name, even for inner classes, should not cost additional times.
   If we're not sure of that (I mean that the compilation unit is always resolved
   while using this method), then I think that another algorithm needs to be 
   implemented...
Comment 31 Kelly Campbell CLA 2009-10-23 12:35:14 EDT
Why is performance such a concern for this particular feature? Does anyone organize imports over many files at once? I think correctness should take precedence over performance here. Even if it takes a couple hundred extra milliseconds, I don't foresee it being a complaint from users.
Comment 32 Robert Konigsberg CLA 2009-10-23 12:43:47 EDT
+1
Comment 33 Nick Chalko CLA 2009-10-23 12:48:59 EDT
(In reply to comment #31)
>  I think correctness should take precedence over performance here. 
+1
Comment 34 Frederic Fusier CLA 2009-10-23 13:03:53 EDT
(In reply to comment #31)
> Why is performance such a concern for this particular feature? Does anyone
> organize imports over many files at once? I think correctness should take
> precedence over performance here. Even if it takes a couple hundred extra
> milliseconds, I don't foresee it being a complaint from users.

May be as you can launch an Organize Imports on a project... In this case, all the compilation unit of the project will be re-organized! I think this is a simple use case which entirely justify to spend a little time on possible performance impact, don't you?

BTW, that's not specific to this functionality, performance is always a concern while touching JDT/Core code. Find a type in a project may last more than a few milliseconds depending of your workspace and the place where the call is done. And doing that for many import declaration may introduce a real performance regression.

That's something we always want to avoid, hence explain why we double-check before using a method we already know they can add significant extra time in certain operations.

Of course, correctness is essential, so we'll fix this issue... but for a compiler, speed is the second law, hence we'll take the necessary time to find the faster and safer solution here...
Comment 35 Robert Konigsberg CLA 2009-10-23 15:20:45 EDT
I will buy that. Thanks.
Comment 36 Dani Megert CLA 2009-10-26 04:23:46 EDT
>May be as you can launch an Organize Imports on a project... In this case, all
>the compilation unit of the project will be re-organized! 
You can even launch it on the whole workspace.

Re comment 30, item 2: I guess we cannot assume this as the workspace might not be in auto-build mode and none of the CUs might be open when the Organized Imports is called upon a workspace resource.
Comment 37 Frederic Fusier CLA 2009-10-26 06:49:42 EDT
(In reply to comment #36)
> > May be as you can launch an Organize Imports on a project... In this case, 
> > all the compilation unit of the project will be re-organized! 
> You can even launch it on the whole workspace.
> 
So performance will definitely be the key point of the fix...

> Re comment 30, item 2: I guess we cannot assume this as the workspace might 
> not be in auto-build mode and none of the CUs might be open when the 
> Organized Imports is called upon a workspace resource.

Thanks Dani for the feedback.

Jay,

Hence, please think about another way to fix this issue. IMO, one possible solution would be to use the findPackageFragment(String) method available on JavaProject...

Another point is that looking at the Import Declarations specification (chapter §7.5), on demand import declaration may have package or type name... So, returning the name when the import declaration is on demand sounds like a potential bug for me. Please also double-check this assumption and fix it as well if it is confirmed...

Thanks
Comment 38 Jay Arthanareeswaran CLA 2009-11-02 08:39:14 EST
Fred,

Would you still be concerned if we used JavaProjct.findType only once instead of in a loop? I guess we can find the current (inner) type's package straightaway instead of having to go all the way up to the top level type.

(In reply to comment #37)
> IMO, one possible
> solution would be to use the findPackageFragment(String) method available on
> JavaProject...

With this is we need to be absolutely sure that we only have the package qualifier and not the enclosing class. I am not sure about this.


> Another point is that looking at the Import Declarations specification (chapter
> §7.5), on demand import declaration may have package or type name... So,
> returning the name when the import declaration is on demand sounds like a
> potential bug for me. Please also double-check this assumption and fix it as
> well if it is confirmed...

Yes, I saw this being an issue in one of the modified test. I will come up with a complete one and if required, will create a new bug.
Comment 39 Frederic Fusier CLA 2009-11-03 08:51:56 EST
(In reply to comment #38)
> Fred,
> 
> Would you still be concerned if we used JavaProjct.findType only once instead
> of in a loop? I guess we can find the current (inner) type's package
> straightaway instead of having to go all the way up to the top level type.
> 
Yes, this method will cost the first time as it will open the compilation unit and populate JavaModel cache. As I said in previous comment, this is a no-go while running this action on an entire project or furthermore on the whole workspace...

> (In reply to comment #37)
> > IMO, one possible
> > solution would be to use the findPackageFragment(String) method available on
> > JavaProject...
> 
> With this is we need to be absolutely sure that we only have the package
> qualifier and not the enclosing class. I am not sure about this.
> 
The tip is loop on the qualifier until this method does not return null. Roughly, the algorithm would look like:
1. set the name with the qualifier got from the name
2. if the findPackageFragment(name) is not null then return the name.
3. loop on 1.


> 
> > Another point is that looking at the Import Declarations specification (chapter
> > §7.5), on demand import declaration may have package or type name... So,
> > returning the name when the import declaration is on demand sounds like a
> > potential bug for me. Please also double-check this assumption and fix it as
> > well if it is confirmed...
> 
> Yes, I saw this being an issue in one of the modified test. I will come up with
> a complete one and if required, will create a new bug.
>
I'm not sure a new bug is really necessary. I think this one is OK to fix this potential issue if it's confirmed.
Comment 40 Kelly Campbell CLA 2009-11-04 11:37:24 EST
We've found a bug in the existing patch due to implicit imports being filtered.

E.g.:

package com.foobar.pkgA;

import com.foobar.pkgA.Foo;
import com.foobar.pkgA.Bar.Boo;
import com.foobar.pkgB.Foo.Bar;


The first two imports will get removed when running Organize Imports. However, I think the expected behavior is to only remove the first one. 

I'm not sure of the best way to improve this. Perhaps an additional flag (similar to isStatic()) on the PackageEntry which can be checked in getResultingEdits() where it filters implicit imports?
Comment 41 Kelly Campbell CLA 2009-11-04 12:31:12 EST
Actually the removing imports thing I just reported is a bug in the existing released implementation and has nothing to do with the patch on this bug. It's already reported as bug 235253. I will follow up there with a patch for that issue.
Comment 42 Kelly Campbell CLA 2009-11-04 14:19:02 EST
(In reply to comment #41)

I am wrong again. After trying to reproduce my version of bug 235253 in a test case without the patch for this bug, I was unable to, so it is related to this patch.

I have a fix for that but would like to also fix up the existing patch per the performance comments.

I tried the suggested changes. Here is the loop in the new function:
IJavaElement element = ((JavaProject)this.compilationUnit.getJavaProject()).findPackageFragment(name);
while (element == null) {
  name = Signature.getQualifier(name);
  element = ((JavaProject)this.compilationUnit.getJavaProject()).findPackageFragment(name);
}

However, this fails many tests due to imports from outside the project not being honored. E.g. import java.util.List becomes import java.*; The last line of the loop returns a JarPackageFragment in that case.

I will prepare a patch which contains the existing working patch plus my bugfix for the implict import problem. (This may be the same as the potential on-demand import issue suggested in comment #37)
Comment 43 Kelly Campbell CLA 2009-11-04 14:56:31 EST
Created attachment 151351 [details]
Updated patch with fix for on-demand issue.

Combines existing patch plus fix for issue with removing imports that were incorrectly considered on-demand.
Comment 44 Jay Arthanareeswaran CLA 2009-11-05 00:30:45 EST
(In reply to comment #43)
> Created an attachment (id=151351) [details]
> Updated patch with fix for on-demand issue.
> 
> Combines existing patch plus fix for issue with removing imports that were
> incorrectly considered on-demand.

Kelly, while I appreciate your effort, as Fred mentioned in his comment, JavaProject.findType can be avoided. I will look in to the failures that the other approach brings in.
Comment 45 Jay Arthanareeswaran CLA 2009-11-05 03:53:41 EST
The issue was with the jclMin.jar, which doesn't have the java.io, java.util and java.awt packages, which is causing some test cases to fail. 

Fred, is it okay to add only those packages to the jar? If that's not an option, we will have to add them locally to the test cases themselves. I think there are about 6 tests that will have to be modified.
Comment 46 Frederic Fusier CLA 2009-11-05 04:16:00 EST
(In reply to comment #45)
> The issue was with the jclMin.jar, which doesn't have the java.io, java.util
> and java.awt packages, which is causing some test cases to fail. 
> 
> Fred, is it okay to add only those packages to the jar? If that's not an
> option, we will have to add them locally to the test cases themselves. I think
> there are about 6 tests that will have to be modified.

I'd rather prefer to modify the tests as modifying the jclMin.jar may have strong consequences on the Java Model tests... Or maybe have you already tested the modified jar? Could you please attach the patch?
Comment 47 Jay Arthanareeswaran CLA 2009-11-05 12:00:46 EST
Created attachment 151446 [details]
Latest patch

I modified the tests to have the packages java.util etc. locally. Included the fix added by Kelly for bug 235253.

Please review.
Comment 48 Frederic Fusier CLA 2009-11-06 05:45:33 EST
(In reply to comment #47)
> Created an attachment (id=151446) [details]
> Latest patch
> 
> I modified the tests to have the packages java.util etc. locally. Included the
> fix added by Kelly for bug 235253.
> 
> Please review.

This is not a good idea in this case to merge the two fixes. I think, even if this would add an extra work, that it would be better (at least for the reviewer...) to write two separated patches and merge them after. It would be also easier to explain the design of each patch if they were released separately. So, please split the patch in two and attach them respectively to each bug.

Saying that, on the lines of the patch I identified to fix the current bug, I think there are several issues (i.e. code of getQualifier(String,int)):
1. The method still directly returns the name when the import declaration is on
   demand... Reading your comment 38, I think that you'll change this behavior,
   have you changed your mind on this?
2. You start the loop on the name although for not on demand import declaration
   we know that this is a type name, hence the first iteration of the loop is 
   not necessary
3. It's not necessary to get the index of the dot inside the loop, it will never
   change. Store it before entering the loop and in the loop test if the name
   length is equals to this index (e.g. while (name.length > index) {...})
Comment 49 Kelly Campbell CLA 2009-11-06 08:15:20 EST
(In reply to comment #48)
> 
> This is not a good idea in this case to merge the two fixes. I think, even if
> this would add an extra work, that it would be better (at least for the
> reviewer...) to write two separated patches and merge them after. It would be
> also easier to explain the design of each patch if they were released
> separately. So, please split the patch in two and attach them respectively to
> each bug.
> 

Frederic, As I stated in Comment #42 I was mistaken about that second fix being unrelated to the patch for this bug. The behavior where it removed the necessary import due to considering it implicit only happened with the getQualifier change. This is because the result is the package name rather than the package + toplevel class. I also mistakenly did not catch comment #2 on bug 235253 where he says it is NOT reproducible, which is what I also found to be true after writing the unit test and running it against the unpatched code.
Comment 50 Frederic Fusier CLA 2009-11-06 08:55:09 EST
(In reply to comment #49)
> 
> Frederic, As I stated in Comment #42 I was mistaken about that second fix being
> unrelated to the patch for this bug. The behavior where it removed the
> necessary import due to considering it implicit only happened with the
> getQualifier change. This is because the result is the package name rather than
> the package + toplevel class. I also mistakenly did not catch comment #2 on bug
> 235253 where he says it is NOT reproducible, which is what I also found to be
> true after writing the unit test and running it against the unpatched code.

OK, so after having fixed this bug you were getting the issue described in bug 235253, hence that proves that this bug is dependent from the other one. As Jay confirmed that he was able to reproduce bug 235253 using HEAD, that means that bug 235253 must be fixed first and this one must be fixed after...

It's always better to fix problems one by one, especially in a code area where we do not have a strong and long expertise... This make verifications and control of possible side effects easier to do (and to revert if necessary...).

So, I set this bug depending on bug 235253.
Comment 51 Kelly Campbell CLA 2009-11-06 11:20:15 EST
(In reply to comment #50)
> OK, so after having fixed this bug you were getting the issue described in bug
> 235253, hence that proves that this bug is dependent from the other one. As Jay
> confirmed that he was able to reproduce bug 235253 using HEAD, that means that
> bug 235253 must be fixed first and this one must be fixed after...

My point is that bug 235253 is not reproducible at HEAD. I don't see where Jay said it was either. I will attach my test cases to it.  I think bug 235253 should be closed.

I was mistaken to pull 235253 into this discussion before fully evaluating whether it applied. The getQualifier patch for this bug 194358 causes similar behavior, so the filterImplicitImports portion of this patch is needed.
Comment 52 Jay Arthanareeswaran CLA 2009-11-10 05:59:17 EST
After further investigation, this is what I figured out:

Currently we do not consider cases of inner type imports. Hence such imports are grouped separately instead of being in the appropriate package group. For e.g. "bug.Bug" should really be in the "bug" PackageEntry and not the "bug.Bug" entry.
This gets fixed by the new getQualifier(String, boolean) method. But the issue is, this breaks the isImplicitImport. In this case, the package of the compilation unit is same as the PackageEntry's name  and the 'implicit import', declaration gets removed. 

So, basically, there are two parts to the fix and each requiring the other. Even if we want to fix bug 235253, we would require both these parts - because the second part of the fix (filterImplicitImports) requires the PackageEntry name to be "bug" and not "bug.Bug" as you can see from this code.

boolean internalClassImport = curr.getElementName().lastIndexOf('.') > getName().length();

I have worked on your suggestions and have the patch ready. I will post it if you are fine with this - one single patch for both the bugs.
Comment 53 Frederic Fusier CLA 2009-11-10 16:40:44 EST
(In reply to comment #52)
> 
> I have worked on your suggestions and have the patch ready. I will post it if
> you are fine with this - one single patch for both the bugs.

I've no real time to verify this but I trust you if you said that there's no other solution to write a patch fixing both issues, so go ahead and I'll review your patch on Thursday (tomorrow is a day-off in France :-))...
Comment 54 Jay Arthanareeswaran CLA 2009-11-11 01:24:33 EST
Created attachment 151922 [details]
Updated patch

This patch fixes both this bug and bug 235253 and also includes the required tests.
Comment 55 Jay Arthanareeswaran CLA 2009-11-11 02:14:35 EST
(In reply to comment #48)

> 1. The method still directly returns the name when the import declaration is on
>    demand... Reading your comment 38, I think that you'll change this behavior,
>    have you changed your mind on this?

There are scenarios that would require us to keep it this way. For instance, consider this:

import p.A.*;
import p.Inner;

In this case, we need to differentiate these two. If we keep the qualifier as "p" for both, then we will have a problem. Hence I have kept it that way.
Comment 56 Frederic Fusier CLA 2009-11-12 10:11:44 EST
(In reply to comment #54)
> Created an attachment (id=151922) [details]
> Updated patch
> 
> This patch fixes both this bug and bug 235253 and also includes the required
> tests.

Looking at the added tests, it seems obvious that both patches are required to fix the entire problem...

However, using this patch, I played a little bit with those test cases in a workspace using similar test cases...

Test case 1:
-----------
package test.pack1;

import test.pack2.A;
import test.pack2.A.Inner;
import test.pack2.B;

public class C {
	A a;
	B b;
	Inner i;
}

Of course I needed to declare some variables to use the imports otherwise they are removed during the organize operation... For test case 1, it works fine, but it's not really a big deal as the imports are already well sorted...

So, let make it a little bit more complicated...

Test case 2:
-----------
package test.pack1;

import test.pack2.A;
import test.pack2.B;
import test.pack2.A.Inner;

public class C2 {
	A a;
	B b;
	Inner i;
}

I would expect to have the same order than test case 1 after the organize operation, but it remains unchanged!

Another variation...

Test case 3:
-----------
package test2.pack1;

import test2.pack3.A;
import test2.pack2.B;
import test2.pack3.A.Inner;

public class C {
	A a;
	Inner i;
	B b;
}

And it works for this one, as I get the expected output:
package test2.pack1;

import test2.pack2.B;
import test2.pack3.A;
import test2.pack3.A.Inner;

public class C {
	A a;
	Inner i;
	B b;
}

Trying to understand a little bit what happens it the fix, I put some breakpoints in getQualifier(...) methods and I was really surprised to see that it never breaks there!!!

The explanation is simple, the OrganizeImportsOperation creates an ImportRewrite using the following line:
ImportRewrite importsRewrite= StubUtility.createImportRewrite(astRoot, false);
which means that existing imports are not restored, hence the addExistingImports(CompilationUnit) method is not called in ImportRewriterAnalyzer constructor. As the is the single caller of getQualifier(ImportDeclaration) method, the fix will not be implied during this operation...

So, one question after this long comment would be: is the fix really addressing the problem described in comment 0 ("Organize Imports command puts Map.Entry after Set. It should put it before.")!? It definitely fixes issues but not for the Organize Imports operation...

Another question is, would it be possible to have one (or several) precisely detailed scenario(s) (i.e. complete test case + the exact operation to perform), to easily reproduce the problem in a workspace (it's usually the first place to show a problem, hence to easily verify that a fix is properly working...)
Comment 57 Frederic Fusier CLA 2009-11-12 10:19:12 EST
(In reply to comment #56)
> 
> However, using this patch, I played a little bit with those test cases in a
> workspace using similar test cases...
> 
> Test case 1:
> -----------
> package test.pack1;
> 
> import test.pack2.A;
> import test.pack2.A.Inner;
> import test.pack2.B;
> 
> public class C {
>     A a;
>     B b;
>     Inner i;
> }
> 
> Of course I needed to declare some variables to use the imports otherwise they
> are removed during the organize operation... For test case 1, it works fine,
> but it's not really a big deal as the imports are already well sorted...
> 
I was wrong on this one, in fact it does not work properly as after the Organize Imports operation, I get:

package test.pack1;

import test.pack2.A;
import test.pack2.B;
import test.pack2.A.Inner;

public class C {
	A a;
	B b;
	Inner i;
}

Which definitely shows that the current fix does not work for this operation.
Comment 58 Frederic Fusier CLA 2009-11-12 11:20:55 EST
(In reply to comment #57)
> (In reply to comment #56)
>
Hmmm, it seems that the day-off yesterday was not enough for me... Maybe I need more vacations as trying again to play with the patch, it works well for all the test cases I described in comment 56

So, forget these 2 comments, I surely mixed patch with HEAD contents while doing my tests. I also think I mixed breakpoints in getQualifier(ImportDeclaration)  and getQualifier(String, boolean) when thinking the tests didn't use the code of the patch...

I think I definitely won a red nose on this :-S

Sorry for the unnecessary noise...
Comment 59 Frederic Fusier CLA 2009-11-12 11:41:09 EST
(In reply to comment #54)
> Created an attachment (id=151922) [details]
> Updated patch
> 
> This patch fixes both this bug and bug 235253 and also includes the required
> tests.

So, as I now can reproduce the problem and see that the fix is working properly, here's my review for the proposed patch (if I still have some credits to do one!)...

The patch looks good to me but 2 points are worry me:

1) I'm not sure that the getQualifier(String, boolean) should be called with Signature.getQualifier(name) from the getQualifier(ImportDeclaration) method. Looking at callers of the new getQualifier(S,b) method, in addImport(...) and removeImport(...) methods, it's called with the full type name. So, why is it called with the qualifier from getQualifier(ImportDeclaration)? That does not seem coherent to me... Is there any explanation for this? IMO, the first qualifier should be done inside the getQualifier(S,b) method before entering the loop.

2) I'm not sure that skipping the JavaModelException inside the loop is a good thing to do. IMO, it should be better to give up with the name in this case
Comment 60 Jay Arthanareeswaran CLA 2009-11-13 03:45:03 EST
Created attachment 152135 [details]
Updated patch

(In reply to comment #59)

> 1) I'm not sure that the getQualifier(String, boolean) should be called with
> Signature.getQualifier(name) from the getQualifier(ImportDeclaration) method...

This change was made as per the suggestion in comment #48, point 2. And we couldn't move this inside getQualifier(String, boolean) because we don't know whether it's on demand or not at this point. As for finding the first qualifier outside the loop, we have a chance that we are already at the last last fragment. Hence, we need to take care of those conditions.

The patch has the other changes as suggested.
Comment 61 Frederic Fusier CLA 2009-11-13 05:46:49 EST
(In reply to comment #60)
> Created an attachment (id=152135) [details]
> Updated patch
> 
> (In reply to comment #59)
> 
> > 1) I'm not sure that the getQualifier(String, boolean) should be called with
> > Signature.getQualifier(name) from the getQualifier(ImportDeclaration) method...
> 
> This change was made as per the suggestion in comment #48, point 2. And we
> couldn't move this inside getQualifier(String, boolean) because we don't know
> whether it's on demand or not at this point. As for finding the first qualifier
> outside the loop, we have a chance that we are already at the last last
> fragment. Hence, we need to take care of those conditions.
> 
> The patch has the other changes as suggested.

OK, I understand this now (as I often say, I understand quickly, but you need to explain things to me during a loooong time ;-)).

The patch looks good now to me, I'll be happy to release it today :-)
Comment 62 Frederic Fusier CLA 2009-11-13 07:30:21 EST
(In reply to comment #29)
> Created an attachment (id=149218) [details]
> Patch for perf_35x
> 
> Attaching the patch with the performance test for the perf_35x stream.

Released for today's baseline run in perf_35x branch stream.
Comment 63 Frederic Fusier CLA 2009-11-13 07:37:41 EST
(In reply to comment #61)
> (In reply to comment #60)
> > Created an attachment (id=152135) [details] [details]
> > Updated patch
> 
> The patch looks good now to me, I'll be happy to release it today :-)

Released for 3.6M4 in HEAD stream.
Comment 64 Robert Konigsberg CLA 2009-11-13 10:09:40 EST
Hooray!
Comment 65 Olivier Thomann CLA 2009-11-13 10:20:21 EST
Thank you to all contributors to this bug!
Comment 66 Olivier Thomann CLA 2009-11-16 09:59:32 EST
The fix has to be reverted as it broke some tests in JDT/UI.
Don't worry, a new fix will be issued shortly that also take care of bug 295220.
Comment 67 Olivier Thomann CLA 2009-11-20 10:22:13 EST
Created attachment 152716 [details]
Proposed fix

Jay, please let me know what you think. We cannot release this as long as bug 295638 is not fixed.
Comment 68 Markus Keller CLA 2009-12-01 07:01:48 EST
(In reply to comment #67)
> Created an attachment (id=152716) [details]
> Proposed fix

The change in AddImportTest#testRemoveImports1() reveal a problem that should be fixed in the import rewrite, not in the tests. The client says:

	imports.removeImport("pack.List");

This should work no matter whether a package "pack" is available or not. I have not looked into the code in depth, but I guess ImportRewriteAnalyzer#removeImport(String, boolean) should try all possible interpretations of "qualifier" before it fails (no matter what packages are currently available).

Unfortunately, we won't have time to complete bug 295638 for M4, so I'm moving this bug to (early) M5 as well.
Comment 69 Olivier Thomann CLA 2010-01-22 10:30:52 EST
Moving to M6 as bug 295638 won't be fixed in time for M5.
Comment 70 Olivier Thomann CLA 2010-02-10 12:32:08 EST
*** Bug 295220 has been marked as a duplicate of this bug. ***
Comment 71 Olivier Thomann CLA 2010-02-10 14:08:01 EST
This will be released as part of the fix for bug 235253.
Comment 72 Olivier Thomann CLA 2010-02-10 19:50:47 EST
See patch in bug 235253.
Comment 73 Jay Arthanareeswaran CLA 2010-03-08 06:05:19 EST
Verified for 3.6M6 using build I20100305-1011.
Comment 74 Dani Megert CLA 2010-05-21 02:47:24 EDT
*** Bug 173551 has been marked as a duplicate of this bug. ***