Clover coverage report - PMD - 3.9 Coverage timestamp: Tue Dec 19 2006 09:38:44 EST FRAMES NO FRAMES |
file stats: | LOC: | 326 |  | Methods: | 21
| NCLOC: | 251 |  | Classes: | 1
Source file | Conditionals | Statements | Methods | TOTAL
DAAPathFinder.java | 50% | 64.7% | 76.2% | 61% |

1 |  | /*
2 |  | * Created on 09.08.2004
3 |  | */
4 |  | package net.sourceforge.pmd.dfa.pathfinder;
5 |  |
6 |  | import net.sourceforge.pmd.dfa.IDataFlowNode;
7 |  | import net.sourceforge.pmd.dfa.NodeType;
8 |  |
9 |  | import javax.swing.tree.DefaultMutableTreeNode;
10 |  |
11 |  | /**
12 |  | * @author raik
13 |  | * <p/>
14 |  | * Finds all paths of a data flow. Each loop will be 0 or 2 times traversed ->
15 |  | * 2 paths. This is special to the data flow anomaly analysis.
16 |  | */
17 |  | public class DAAPathFinder {
18 |  | private static final int MAX_PATHS = 5000;
19 |  |
20 |  | private IDataFlowNode rootNode;
21 |  | private Executable shim;
22 |  | private CurrentPath currentPath = new CurrentPath();
23 |  | private DefaultMutableTreeNode stack = new DefaultMutableTreeNode();
24 |  | private int maxPaths;
25 |  |
26 | 1 | public DAAPathFinder(IDataFlowNode rootNode, Executable shim) {
27 | 1 | this.rootNode = rootNode;
28 | 1 | this.shim = shim;
29 | 1 | this.maxPaths = MAX_PATHS;
30 |  | }
31 |  |
32 | 5 | public DAAPathFinder(IDataFlowNode rootNode, Executable shim, int maxPaths) {
33 | 5 | this.rootNode = rootNode;
34 | 5 | this.shim = shim;
35 | 5 | this.maxPaths = maxPaths;
36 |  | }
37 |  |
38 | 5 | public void run() {
39 | 5 | phase1();
40 |  | }
41 |  |
42 |  | /*
43 |  | * Initialise the path search. Starts the searching.
44 |  | * */
45 | 5 | private void phase1() {
46 | 5 | currentPath.addLast(rootNode);
47 | 5 | int i = 0;
48 | 5 | boolean flag = true;
49 | 5 | do {
50 | 7 | i++;
51 |  | // System.out.println("Building path from " + currentPath.getLast());
52 | 7 | phase2(flag);
53 | 7 | shim.execute(currentPath);
54 | 7 | flag = false;
55 | 7 | } while (i < maxPaths && phase3());
56 |  | }
57 |  |
58 |  | /*
59 |  | * Builds up the path.
60 |  | * */
61 | 7 | private void phase2(boolean flag) {
62 | 7 | while (!currentPath.isEndNode()) {
63 | 28 | if (currentPath.isBranch() || currentPath.isFirstDoStatement()) {
64 | 6 | if (flag) {
65 | 4 | addNodeToTree();
66 |  | }
67 | 6 | flag = true;
68 | 6 | if (countLoops() <= 2) {
69 | 5 | addCurrentChild();
70 | 5 | continue;
71 |  | } else {
72 |  | // jump out of that loop
73 | 1 | addLastChild();
74 | 1 | continue;
75 |  | }
76 |  | } else {
77 | 22 | addCurrentChild();
78 |  | }
79 |  | }
80 |  | }
81 |  |
82 |  | /*
83 |  | * Decompose the path until it finds a node which branches are not all
84 |  | * traversed.
85 |  | * */
86 | 7 | private boolean phase3() {
87 | 7 | while (!currentPath.isEmpty()) {
88 | 35 | if (currentPath.isBranch()) {
89 | 6 | if (this.countLoops() == 1) {
90 | 4 | if (this.hasMoreChildren()) {
91 | 2 | this.incChild();
92 | 2 | return true;
93 |  | } else {
94 | 2 | this.removeFromTree();
95 | 2 | currentPath.removeLast();
96 |  | }
97 |  | } else {
98 | 2 | this.removeFromTree();
99 | 2 | currentPath.removeLast();
100 |  | }
101 |  | } else {
102 | 29 | currentPath.removeLast();
103 |  | }
104 |  | }
105 | 5 | return false;
106 |  | }
107 |  |
108 | 4 | private boolean hasMoreChildren() {
109 | 4 | PathElement e = (PathElement) stack.getLastLeaf().getUserObject();
110 | 4 | return e.currentChild + 1 < e.node.getChildren().size();
111 |  | }
112 |  |
113 | 1 | private void addLastChild() {
114 | 1 | PathElement e = (PathElement) stack.getLastLeaf().getUserObject();
115 | 1 | for (int i=e.node.getChildren().size()-1; i >= 0; i--) {
116 | 1 | if (i != e.currentChild) {
117 | 1 | currentPath.addLast((IDataFlowNode) e.node.getChildren().get(i));
118 | 1 | break;
119 |  | }
120 |  | }
121 |  | }
122 |  |
123 |  |
124 | 27 | private void addCurrentChild() {
125 | 27 | if (currentPath.isBranch()) { // TODO WHY????
126 | 5 | PathElement last = (PathElement) stack.getLastLeaf().getUserObject();
127 | 5 | IDataFlowNode inode = currentPath.getLast();
128 | 5 | if (inode.getChildren().size() > last.currentChild) {
129 |  | // for some unknown reasons last.currentChild might not be a children of inode, see bug 1597987
130 | 5 | IDataFlowNode child = (IDataFlowNode) inode.getChildren().get(last.currentChild);
131 | 5 | this.currentPath.addLast(child);
132 |  | }
133 |  | } else {
134 | 22 | IDataFlowNode inode = currentPath.getLast();
135 | 22 | IDataFlowNode child = (IDataFlowNode) inode.getChildren().get(0); //TODO ???? IMPORTANT - ERROR?
136 | 22 | this.currentPath.addLast(child);
137 |  | }
138 |  | }
139 |  |
140 |  | // ----------------------------------------------------------------------------
141 |  | // TREE FUNCTIONS
142 |  |
143 |  | /*
144 |  | * Adds a PathElement to a Tree, which contains information about
145 |  | * loops and "local scopes - encapsulation".
146 |  | * */
147 | 4 | private void addNodeToTree() {
148 | 4 | if (currentPath.isFirstDoStatement()) {
149 | 0 | DefaultMutableTreeNode level = stack;
150 | 0 | IDataFlowNode doBranch = currentPath.getDoBranchNodeFromFirstDoStatement();
151 |  |
152 | 0 | while (true) {
153 | 0 | if (level.getChildCount() != 0) {
154 | 0 | PathElement ref = this.isNodeInLevel(level);
155 | 0 | if (ref != null) {
156 | 0 | this.addRefPseudoPathElement(level, ref);
157 | 0 | break;
158 |  | } else {
159 | 0 | level = this.getLastChildNode(level);
160 | 0 | continue;
161 |  | }
162 |  | } else {
163 | 0 | this.addNewPseudoPathElement(level, doBranch);
164 | 0 | break;
165 |  | }
166 |  | }
167 |  | }
168 |  |
169 | 4 | if (currentPath.isBranch()) {
170 | 4 | DefaultMutableTreeNode level = stack;
171 |  |
172 | 4 | if (currentPath.isDoBranchNode()) {
173 | 0 | while (!this.equalsPseudoPathElementWithDoBranchNodeInLevel(level)) {
174 | 0 | level = this.getLastChildNode(level);
175 | 0 | if (level.getChildCount() == 0) {
176 | 0 | break;
177 |  | }
178 |  | }
179 | 0 | PathElement ref = this.getDoBranchNodeInLevel(level);
180 | 0 | if (ref != null) {
181 | 0 | addNode(level, ref);
182 |  | } else {
183 | 0 | this.addNewPathElement(level);
184 |  | }
185 |  |
186 |  | } else {
187 | 4 | while (true) {
188 | 4 | if (level.getChildCount() != 0) {
189 | 2 | PathElement ref;
190 | ? | if ((ref = this.isNodeInLevel(level)) != null) {
191 | 2 | addNode(level, ref);
192 | 2 | break;
193 |  | } else {
194 | 0 | level = this.getLastChildNode(level);
195 | 0 | continue;
196 |  | }
197 |  | } else {
198 | 2 | this.addNewPathElement(level);
199 | 2 | break;
200 |  | }
201 |  | }
202 |  | }
203 |  | }
204 |  | }
205 |  |
206 | 4 | private void removeFromTree() {
207 | 4 | DefaultMutableTreeNode last = stack.getLastLeaf();
208 | 4 | if (last == null) {
209 | 0 | System.out.println("removeFromTree - last == null");
210 | 0 | return;
211 |  | }
212 | 4 | DefaultMutableTreeNode parent = (DefaultMutableTreeNode) last.getParent();
213 | 4 | if (parent != null) {
214 |  | // for some unknown reasons parent might be null, see bug 1597987
215 | 4 | parent.remove(last);
216 |  | }
217 | 4 | last = stack.getLastLeaf();
218 | 2 | if (last == null || last.getUserObject() == null) return;
219 |  |
220 | 2 | PathElement e = (PathElement) last.getUserObject();
221 | 2 | if (e != null && e.isPseudoPathElement()) {
222 | 0 | this.removeFromTree();
223 |  | }
224 |  | }
225 |  |
226 | 2 | private void addNewPathElement(DefaultMutableTreeNode level) {
227 | 2 | addNode(level, new PathElement(currentPath.getLast()));
228 |  | }
229 |  |
230 |  | /*
231 |  | * Needed for do loops
232 |  | * */
233 | 0 | private void addNewPseudoPathElement(DefaultMutableTreeNode level, IDataFlowNode ref) {
234 | 0 | addNode(level, new PathElement(currentPath.getLast(), ref));
235 |  | }
236 |  |
237 |  | /*
238 |  | * Needed for do loops
239 |  | * */
240 | 0 | private void addRefPseudoPathElement(DefaultMutableTreeNode level, PathElement ref) {
241 | 0 | addNode(level, ref);
242 |  | }
243 |  |
244 | 0 | private boolean equalsPseudoPathElementWithDoBranchNodeInLevel(DefaultMutableTreeNode level) {
245 | 0 | IDataFlowNode inode = currentPath.getLast();
246 |  |
247 | 0 | if (!inode.isType(NodeType.DO_EXPR)) return false;
248 |  |
249 | 0 | int childCount = level.getChildCount();
250 | 0 | DefaultMutableTreeNode child;
251 |  |
252 | 0 | for (int i = 0; i < childCount; i++) {
253 | 0 | child = (DefaultMutableTreeNode) level.getChildAt(i);
254 | 0 | PathElement pe = (PathElement) child.getUserObject();
255 | 0 | if (pe != null && pe.isPseudoPathElement() && pe.pseudoRef.equals(inode)) {
256 | 0 | return true;
257 |  | }
258 |  | }
259 | 0 | return false;
260 |  | }
261 |  |
262 | 0 | private PathElement getDoBranchNodeInLevel(DefaultMutableTreeNode level) {
263 | 0 | IDataFlowNode inode = currentPath.getLast();
264 | 0 | if (!inode.isType(NodeType.DO_EXPR)) return null;
265 |  |
266 | 0 | int childCount = level.getChildCount();
267 | 0 | DefaultMutableTreeNode child;
268 |  |
269 | 0 | for (int i = 0; i < childCount; i++) {
270 | 0 | child = (DefaultMutableTreeNode) level.getChildAt(i);
271 | 0 | PathElement pe = (PathElement) child.getUserObject();
272 | 0 | if (inode.equals(pe.node)) {
273 | 0 | return pe;
274 |  | }
275 |  | }
276 | 0 | return null;
277 |  | }
278 |  |
279 | 4 | private void addNode(DefaultMutableTreeNode level, PathElement element) {
280 | 4 | DefaultMutableTreeNode node = new DefaultMutableTreeNode();
281 | 4 | node.setUserObject(element);
282 | 4 | level.add(node);
283 |  | }
284 |  |
285 | 2 | private PathElement isNodeInLevel(DefaultMutableTreeNode level) {
286 | 2 | IDataFlowNode inode = currentPath.getLast();
287 | 2 | DefaultMutableTreeNode child = (DefaultMutableTreeNode) level.getFirstChild();
288 |  |
289 | 2 | if (child != null) {
290 | 2 | PathElement levelElement = (PathElement) child.getUserObject();
291 | 2 | if (inode.equals(levelElement.node)) {
292 | 2 | return levelElement;
293 |  | }
294 |  | }
295 | 0 | return null;
296 |  | }
297 |  |
298 | 0 | private DefaultMutableTreeNode getLastChildNode(DefaultMutableTreeNode node) {
299 | 0 | if (node.getChildCount() != 0) {
300 | 0 | return (DefaultMutableTreeNode) node.getLastChild();
301 |  | }
302 | 0 | return node;
303 |  | }
304 |  |
305 | 12 | private int countLoops() {
306 | 12 | DefaultMutableTreeNode treeNode = stack.getLastLeaf();
307 | 12 | int counter = 0;
308 | 12 | if (treeNode.getParent() != null) {
309 |  | // for some unknown reasons the parent of treeNode might be null, see bug 1597987
310 | 12 | int childCount = treeNode.getParent().getChildCount();
311 | 12 | for (int i = 0; i < childCount; i++) {
312 | 18 | DefaultMutableTreeNode tNode = (DefaultMutableTreeNode) treeNode.getParent().getChildAt(i);
313 | 18 | PathElement e = (PathElement) tNode.getUserObject();
314 | 18 | if (e != null && !e.isPseudoPathElement()) {
315 | 18 | counter++;
316 |  | }
317 |  | }
318 |  | }
319 | 12 | return counter;
320 |  | }
321 |  |
322 | 2 | private void incChild() {
323 | 2 | ((PathElement) stack.getLastLeaf().getUserObject()).currentChild++;
324 |  | }
325 |  |
326 |  | }