Clover coverage report - PMD - 3.7 Coverage timestamp: Wed May 31 2006 09:25:59 EDT FRAMES NO FRAMES |
file stats: | LOC: | 300 |  | Methods: | 20
| NCLOC: | 230 |  | Classes: | 1
Source file | Conditionals | Statements | Methods | TOTAL
DAAPathFinder.java | 0% | 1.4% | 5% | 1.3% |

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