moving stuff from idea to java-impl
[idea/community.git] / java / java-impl / src / com / intellij / cyclicDependencies / CyclicDependenciesBuilder.java
1 package com.intellij.cyclicDependencies;
2
3 import com.intellij.analysis.AnalysisScope;
4 import com.intellij.analysis.AnalysisScopeBundle;
5 import com.intellij.openapi.progress.ProcessCanceledException;
6 import com.intellij.openapi.progress.ProgressIndicator;
7 import com.intellij.openapi.progress.ProgressManager;
8 import com.intellij.openapi.project.Project;
9 import com.intellij.openapi.roots.ProjectFileIndex;
10 import com.intellij.openapi.roots.ProjectRootManager;
11 import com.intellij.packageDependencies.DependenciesBuilder;
12 import com.intellij.packageDependencies.ForwardDependenciesBuilder;
13 import com.intellij.psi.*;
14 import com.intellij.util.graph.CachingSemiGraph;
15 import com.intellij.util.graph.Graph;
16 import com.intellij.util.graph.GraphGenerator;
17
18 import java.util.*;
19
20 /**
21  * User: anna
22  * Date: Jan 30, 2005
23  */
24 public class CyclicDependenciesBuilder{
25   private final Project myProject;
26   private final AnalysisScope myScope;
27   private final Map<String, PsiPackage> myPackages = new HashMap<String, PsiPackage>();
28   private Graph<PsiPackage> myGraph;
29   private final Map<PsiPackage, Map<PsiPackage, Set<PsiFile>>> myFilesInDependentPackages = new HashMap<PsiPackage, Map<PsiPackage, Set<PsiFile>>>();
30   private final Map<PsiPackage, Map<PsiPackage, Set<PsiFile>>> myBackwardFilesInDependentPackages = new HashMap<PsiPackage, Map<PsiPackage, Set<PsiFile>>>();
31   private final Map<PsiPackage, Set<PsiPackage>> myPackageDependencies = new HashMap<PsiPackage, Set<PsiPackage>>();
32   private HashMap<PsiPackage, Set<List<PsiPackage>>> myCyclicDependencies = new HashMap<PsiPackage, Set<List<PsiPackage>>>();
33   private int myFileCount = 0;
34   private final ForwardDependenciesBuilder myForwardBuilder;
35
36   private String myRootNodeNameInUsageView;
37
38   public CyclicDependenciesBuilder(final Project project, final AnalysisScope scope) {
39     myProject = project;
40     myScope = scope;
41     myForwardBuilder = new ForwardDependenciesBuilder(myProject, myScope){
42       public String getRootNodeNameInUsageView() {
43         return CyclicDependenciesBuilder.this.getRootNodeNameInUsageView();
44       }
45
46       public String getInitialUsagesPosition() {
47         return AnalysisScopeBundle.message("cyclic.dependencies.usage.view.initial.text");
48       }
49     };
50   }
51
52   public String getRootNodeNameInUsageView() {
53     return myRootNodeNameInUsageView;
54   }
55
56   public void setRootNodeNameInUsageView(final String rootNodeNameInUsageView) {
57     myRootNodeNameInUsageView = rootNodeNameInUsageView;
58   }
59
60   public Project getProject() {
61     return myProject;
62   }
63
64   public AnalysisScope getScope() {
65     return myScope;
66   }
67
68   public DependenciesBuilder getForwardBuilder() {
69     return myForwardBuilder;
70   }
71
72   public void analyze() {
73     final ProjectFileIndex projectFileIndex = ProjectRootManager.getInstance(getProject()).getFileIndex();
74     getScope().accept(new PsiRecursiveElementVisitor() {
75       @Override public void visitFile(PsiFile file) {
76         if (file instanceof PsiJavaFile) {
77           PsiJavaFile psiJavaFile = (PsiJavaFile)file;
78           if (getScope().contains(psiJavaFile)) {
79             final PsiPackage aPackage = findPackage(psiJavaFile.getPackageName());
80             if (aPackage != null) {
81               myPackages.put(psiJavaFile.getPackageName(), aPackage);
82             }
83           }
84           final Set<PsiPackage> packs = getPackageHierarhy(psiJavaFile.getPackageName());
85           final ForwardDependenciesBuilder builder = new ForwardDependenciesBuilder(getProject(), new AnalysisScope(psiJavaFile));
86           builder.setTotalFileCount(getScope().getFileCount());
87           builder.setInitialFileCount(++myFileCount);
88           builder.analyze();
89           final Set<PsiFile> psiFiles = builder.getDependencies().get(psiJavaFile);
90           if (psiFiles == null) return;
91           for (PsiPackage pack : packs) {
92             Set<PsiPackage> pack2Packages = myPackageDependencies.get(pack);
93             if (pack2Packages == null) {
94               pack2Packages = new HashSet<PsiPackage>();
95               myPackageDependencies.put(pack, pack2Packages);
96             }
97             for (PsiFile psiFile : psiFiles) {
98               if (!(psiFile instanceof PsiJavaFile) ||
99                   !projectFileIndex.isInSourceContent(psiFile.getVirtualFile()) ||
100                   !getScope().contains(psiFile)) {
101                 continue;
102               }
103
104               // construct dependent packages
105               final String packageName = ((PsiJavaFile)psiFile).getPackageName();
106               //do not depend on parent packages
107               if (packageName.startsWith(pack.getQualifiedName())) {
108                 continue;
109               }
110               final PsiPackage depPackage = findPackage(packageName);
111               if (depPackage == null) { //not from analyze scope
112                 continue;
113               }
114               pack2Packages.add(depPackage);
115
116               constractFilesInDependenciesPackagesMap(pack, depPackage, psiFile, myFilesInDependentPackages);
117               constractFilesInDependenciesPackagesMap(depPackage, pack, psiJavaFile, myBackwardFilesInDependentPackages);
118               constractWholeDependenciesMap(psiJavaFile, psiFile);
119             }
120           }
121         }
122       }
123     });
124     ProgressIndicator indicator = ProgressManager.getInstance().getProgressIndicator();
125     if (indicator != null) {
126       if (indicator.isCanceled()) {
127         throw new ProcessCanceledException();
128       }
129       indicator.setText(AnalysisScopeBundle.message("cyclic.dependencies.progress.text"));
130       indicator.setText2("");
131       indicator.setIndeterminate(true);
132     }
133     myCyclicDependencies = getCycles(myPackages.values());
134   }
135
136   private void constractFilesInDependenciesPackagesMap(final PsiPackage pack,
137                                                        final PsiPackage depPackage,
138                                                        final PsiFile file,
139                                                        final Map<PsiPackage, Map<PsiPackage, Set<PsiFile>>> filesInDependentPackages) {
140     Map<PsiPackage, Set<PsiFile>> dependentPackages2Files = filesInDependentPackages.get(pack);
141     if (dependentPackages2Files == null) {
142       dependentPackages2Files = new HashMap<PsiPackage, Set<PsiFile>>();
143       filesInDependentPackages.put(pack, dependentPackages2Files);
144     }
145     Set<PsiFile> depFiles = dependentPackages2Files.get(depPackage);
146     if (depFiles == null) {
147       depFiles = new HashSet<PsiFile>();
148       dependentPackages2Files.put(depPackage, depFiles);
149     }
150     depFiles.add(file);
151   }
152
153 //construct all dependencies for usage view
154   private void constractWholeDependenciesMap(final PsiJavaFile psiJavaFile, final PsiFile psiFile) {
155     Set<PsiFile> wholeDependencies = myForwardBuilder.getDependencies().get(psiJavaFile);
156     if (wholeDependencies == null) {
157       wholeDependencies = new HashSet<PsiFile>();
158       myForwardBuilder.getDependencies().put(psiJavaFile, wholeDependencies);
159     }
160     wholeDependencies.add(psiFile);
161   }
162
163   public Set<PsiFile> getDependentFilesInPackage(PsiPackage pack, PsiPackage depPack) {
164     Set<PsiFile> psiFiles = new HashSet<PsiFile>();
165     final Map<PsiPackage, Set<PsiFile>> map = myFilesInDependentPackages.get(pack);
166     if (map != null){
167       psiFiles = map.get(depPack);
168     }
169     if (psiFiles == null) {
170       psiFiles = new HashSet<PsiFile>();
171     }
172     return psiFiles;
173   }
174
175   public Set<PsiFile> getDependentFilesInPackage(PsiPackage firstPack, PsiPackage middlePack, PsiPackage lastPack) {
176     Set<PsiFile> result = new HashSet<PsiFile>();
177     final Map<PsiPackage, Set<PsiFile>> forwardMap = myFilesInDependentPackages.get(firstPack);
178     if (forwardMap != null && forwardMap.get(middlePack) != null){
179       result.addAll(forwardMap.get(middlePack));
180     }
181     final Map<PsiPackage, Set<PsiFile>> backwardMap = myBackwardFilesInDependentPackages.get(lastPack);
182     if (backwardMap != null && backwardMap.get(middlePack) != null){
183       result.addAll(backwardMap.get(middlePack));
184     }
185     return result;
186   }
187
188
189   public HashMap<PsiPackage, Set<List<PsiPackage>>> getCyclicDependencies() {
190     return myCyclicDependencies;
191   }
192
193   public HashMap<PsiPackage, Set<List<PsiPackage>>> getCycles(Collection<PsiPackage> packages) {
194     if (myGraph == null){
195       myGraph = buildGraph();
196     }
197     final HashMap<PsiPackage, Set<List<PsiPackage>>> result = new HashMap<PsiPackage, Set<List<PsiPackage>>>();
198     for (Iterator<PsiPackage> iterator = packages.iterator(); iterator.hasNext();) {
199       PsiPackage psiPackage = iterator.next();
200         Set<List<PsiPackage>> paths2Pack = result.get(psiPackage);
201         if (paths2Pack == null) {
202           paths2Pack = new HashSet<List<PsiPackage>>();
203           result.put(psiPackage, paths2Pack);
204         }
205         paths2Pack.addAll(CyclicGraphUtil.getNodeCycles(myGraph, psiPackage));
206     }
207     return result;
208   }
209
210   public Map<String, PsiPackage> getAllScopePackages() {
211     if (myPackages.isEmpty()) {
212       final PsiManager psiManager = PsiManager.getInstance(getProject());
213       getScope().accept(new PsiRecursiveElementVisitor() {
214         @Override public void visitFile(PsiFile file) {
215           if (file instanceof PsiJavaFile) {
216             PsiJavaFile psiJavaFile = (PsiJavaFile)file;
217             final PsiPackage aPackage = JavaPsiFacade.getInstance(psiManager.getProject()).findPackage(psiJavaFile.getPackageName());
218             if (aPackage != null) {
219               myPackages.put(aPackage.getQualifiedName(), aPackage);
220             }
221           }
222         }
223       });
224     }
225     return myPackages;
226   }
227
228
229   private Graph<PsiPackage> buildGraph() {
230     final Graph<PsiPackage> graph = GraphGenerator.create(CachingSemiGraph.create(new GraphGenerator.SemiGraph<PsiPackage>() {
231       public Collection<PsiPackage> getNodes() {
232         return getAllScopePackages().values();
233       }
234
235       public Iterator<PsiPackage> getIn(PsiPackage psiPack) {
236         final Set<PsiPackage> psiPackages = myPackageDependencies.get(psiPack);
237         if (psiPackages == null) {     //for packs without java classes
238           return new HashSet<PsiPackage>().iterator();
239         }
240         return psiPackages.iterator();
241       }
242     }));
243     return graph;
244   }
245
246   public Set<PsiPackage> getPackageHierarhy(String packageName) {
247     final Set<PsiPackage> result = new HashSet<PsiPackage>();
248     PsiPackage psiPackage = findPackage(packageName);
249     if (psiPackage != null) {
250       result.add(psiPackage);
251     }
252     else {
253       return result;
254     }
255     while (psiPackage.getParentPackage() != null && psiPackage.getParentPackage().getQualifiedName().length() != 0) {
256       final PsiPackage aPackage = findPackage(psiPackage.getParentPackage().getQualifiedName());
257       if (aPackage == null) {
258         break;
259       }
260       result.add(aPackage);
261       psiPackage = psiPackage.getParentPackage();
262     }
263     return result;
264   }
265
266   private PsiPackage findPackage(String packName) {
267     final PsiPackage psiPackage = getAllScopePackages().get(packName);
268     return psiPackage;
269   }
270
271 }