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