|
1
20 package edu.umd.cs.findbugs.detect;
21
22
23 import edu.umd.cs.findbugs.*;
24 import java.util.*;
25 import org.apache.bcel.classfile.JavaClass;
26
27 public class FindCircularDependencies extends BytecodeScanningDetector
28 {
29 private HashMap<String  , Set<String >> dependencyGraph = null;
30
31 private BugReporter bugReporter;
32 private String clsName;
33
34 public FindCircularDependencies(BugReporter bugReporter) {
35 this.bugReporter = bugReporter;
36 this.dependencyGraph = new HashMap<String ,Set<String >>();
37 }
38
39 @Override
40 public void visit(JavaClass obj) {
41 clsName = obj.getClassName();
42 }
43
44 @Override
45 public void sawOpcode(int seen) {
46 if ((seen == INVOKESPECIAL)
47 || (seen == INVOKESTATIC)
48 || (seen == INVOKEVIRTUAL)) {
49 String refClsName = getClassConstantOperand();
50 refClsName = refClsName.replace('/', '.');
51 if (refClsName.startsWith("java"))
52 return;
53
54 if (clsName.equals(refClsName))
55 return;
56
57 if (clsName.startsWith(refClsName) && (refClsName.indexOf("$") >= 0))
58 return;
59
60 if (refClsName.startsWith(refClsName) && (clsName.indexOf("$") >= 0))
61 return;
62
63 Set<String > dependencies = dependencyGraph.get(clsName);
64 if (dependencies == null) {
65 dependencies = new HashSet<String >();
66 dependencyGraph.put(clsName, dependencies);
67 }
68
69 dependencies.add(refClsName);
70 }
71 }
72
73 @Override
74 public void report() {
75 removeDependencyLeaves(dependencyGraph);
76
77 LoopFinder lf = new LoopFinder();
78
79 while (dependencyGraph.size() > 0) {
80 String clsName = dependencyGraph.keySet().iterator().next();
81 Set<String > loop = lf.findLoop(dependencyGraph, clsName);
82 boolean pruneLeaves;
83 if (loop != null) {
84 BugInstance bug = new BugInstance(
85 this,
86 "CD_CIRCULAR_DEPENDENCY",
87 NORMAL_PRIORITY);
88 for (String loopCls : loop) {
89 bug.addClass(loopCls);
90 }
91 bugReporter.reportBug(bug);
92 pruneLeaves = removeLoopLinks(dependencyGraph, loop);
93 } else {
94 dependencyGraph.remove(clsName);
95 pruneLeaves = true;
96 }
97 if (pruneLeaves)
98 removeDependencyLeaves(dependencyGraph);
99 }
100
101 dependencyGraph.clear();
102 }
103
104 private void removeDependencyLeaves(Map<String , Set<String >> dependencyGraph)
105 {
106 boolean changed = true;
107 while (changed) {
108 changed = false;
109 Iterator<Set<String >> it = dependencyGraph.values().iterator();
110 while (it.hasNext()) {
111 Set<String > dependencies = it.next();
112
113 boolean foundClass = false;
114 Iterator<String > dit = dependencies.iterator();
115 while (dit.hasNext()) {
116 foundClass = dependencyGraph.containsKey(dit.next());
117 if (!foundClass) {
118 dit.remove();
119 changed = true;
120 }
121 }
122 if (dependencies.size() == 0) {
123 it.remove();
124 changed = true;
125 }
126 }
127 }
128 }
129
130 private boolean removeLoopLinks(Map<String , Set<String >> dependencyGraph, Set<String > loop)
131 {
132 Set<String > dependencies = null;
133 for (String clsName : loop) {
134 if (dependencies != null)
135 dependencies.remove(clsName);
136 dependencies = dependencyGraph.get(clsName);
137 }
138 if (dependencies != null)
139 dependencies.remove(loop.iterator().next());
140
141 boolean removedClass = false;
142 Iterator<String > cIt = loop.iterator();
143 while (cIt.hasNext()) {
144 String clsName = cIt.next();
145 dependencies = dependencyGraph.get(clsName);
146 if (dependencies.size() == 0) {
147 cIt.remove();
148 removedClass = true;
149 }
150 }
151 return removedClass;
152 }
153
154 static class LoopFinder
155 {
156 private Map<String , Set<String >> dGraph = null;
157 private String startClass = null;
158 private Set<String > visited = null;
159 private Set<String > loop = null;
160
161 public Set<String > findLoop(Map<String , Set<String >> dependencyGraph, String startCls) {
162 dGraph = dependencyGraph;
163 startClass = startCls;
164 visited = new HashSet<String >();
165 loop = new LinkedHashSet<String >();
166 if (findLoop(startClass))
167 return loop;
168 return null;
169 }
170
171 private boolean findLoop(String curClass) {
172 Set<String > dependencies = dGraph.get(curClass);
173 if (dependencies == null)
174 return false;
175
176 visited.add(curClass);
177 loop.add(curClass);
178 for (String depClass : dependencies) {
179 if (depClass.equals(startClass))
180 return true;
181
182 if (visited.contains(depClass))
183 continue;
184
185 if (findLoop(depClass))
186 return true;
187 }
188 loop.remove(curClass);
189 return false;
190 }
191 }
192 }
193 |
Popular Tags |
Java API By Example, From Geeks To Geeks.