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