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