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