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