Clover coverage report - PMD - 3.3
Coverage timestamp: Thu Sep 15 2005 17:59:57 EDT
file stats: LOC: 415   Methods: 35
NCLOC: 313   Classes: 2
 
 Source file Conditionals Statements Methods TOTAL
DAAPathFinder.java 0% 1.1% 2.9% 1%
coverage coverage
 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    import java.util.LinkedList;
 11   
 12    /**
 13    * @author raik
 14    * <p/>
 15    * Finds all paths of a data flow. Each loop will be 0 or 2 times traversed ->
 16    * 2 paths. This is special to the data flow anomaly analysis.
 17    */
 18    public class DAAPathFinder {
 19   
 20    private IDataFlowNode rootNode;
 21    private Executable shim;
 22    private LinkedList currentPath = new LinkedList();
 23    private DefaultMutableTreeNode stack = new DefaultMutableTreeNode();
 24    private static final int MAX_PATHS = 5000;
 25   
 26    private static class PathElement {
 27    int currentChild;
 28    IDataFlowNode node;
 29    IDataFlowNode pseudoRef;
 30  0 PathElement(IDataFlowNode node) {
 31  0 this.node = node;
 32    }
 33    }
 34   
 35  1 public DAAPathFinder(IDataFlowNode rootNode, Executable shim) {
 36  1 this.rootNode = rootNode;
 37  1 this.shim = shim;
 38    }
 39   
 40  0 public void run() {
 41  0 phase1(rootNode);
 42    }
 43   
 44    /*
 45    * Initialise the path search. Starts the searching.
 46    * */
 47  0 private void phase1(IDataFlowNode startNode) {
 48  0 this.currentPath.clear();
 49  0 this.currentPath.addLast(startNode);
 50   
 51  0 int i = 0;
 52  0 boolean flag = true;
 53  0 do {
 54  0 i++;
 55  0 phase2(flag);
 56  0 shim.execute(currentPath);
 57  0 flag = false;
 58  0 } while (i < MAX_PATHS && phase3());
 59    //System.out.println("found: " + i + " path(s)");
 60    }
 61   
 62    /*
 63    * Builds up the path.
 64    * */
 65  0 private void phase2(boolean flag) {
 66  0 while (!isEndNode()) {
 67  0 if (isBranch() || isFirstDoStatement()) {
 68  0 if (flag) {
 69  0 addNodeToTree();
 70    }
 71  0 flag = true;
 72  0 if (countLoops() <= 2) {
 73  0 addCurrentChild();
 74  0 continue;
 75    } else {
 76  0 addSecondChild();
 77  0 continue;
 78    }
 79    } else {
 80  0 addCurrentChild();
 81    }
 82    }
 83    }
 84   
 85    /*
 86    * Decompose the path until it finds a node which branches are not all
 87    * traversed.
 88    * */
 89  0 private boolean phase3() {
 90   
 91  0 while (!this.isEmpty()) {
 92  0 if (this.isBranch()) {
 93  0 if (this.countLoops() == 1) {
 94  0 if (this.hasMoreChildren()) {
 95  0 this.incChild();
 96  0 return true;
 97    } else {
 98  0 this.removeFromTree();
 99  0 this.removeFromList();
 100    }
 101    } else {
 102  0 this.removeFromTree();
 103  0 this.removeFromList();
 104    }
 105    } else {
 106  0 this.removeFromList();
 107    }
 108    }
 109   
 110  0 return false;
 111    }
 112   
 113  0 private void removeFromList() {
 114  0 this.currentPath.removeLast();
 115    }
 116   
 117  0 private boolean isEmpty() {
 118  0 return this.currentPath.isEmpty();
 119    }
 120   
 121  0 private boolean hasMoreChildren() {
 122  0 DefaultMutableTreeNode last = this.getLastNode();
 123  0 PathElement e = (PathElement) last.getUserObject();
 124  0 return e.currentChild + 1 < e.node.getChildren().size();
 125    }
 126   
 127  0 private boolean isEndNode() {
 128  0 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
 129    // TODO use instanceof StartOrEndNode?
 130  0 return inode.getChildren().size() == 0;
 131    }
 132   
 133  0 private boolean isBranch() {
 134  0 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
 135  0 return inode.getChildren().size() > 1;
 136    }
 137   
 138  0 private boolean isFirstDoStatement() {
 139  0 IDataFlowNode inode = (IDataFlowNode)this.currentPath.getLast();
 140  0 return this.isFirstDoStatement(inode);
 141    }
 142   
 143  0 private void addSecondChild() {
 144  0 PathElement e = (PathElement) this.getLastNode().getUserObject();
 145  0 int secondChild;
 146  0 if (e.currentChild == 1) {
 147  0 secondChild = 0;
 148    } else {
 149  0 secondChild = 1;
 150    }
 151  0 IDataFlowNode child = (IDataFlowNode) e.node.getChildren().get(secondChild);
 152  0 this.currentPath.addLast(child);
 153    }
 154   
 155  0 private void addCurrentChild() {
 156  0 if (this.isBranch()) { // TODO WHY????
 157  0 PathElement last = (PathElement) this.getLastNode().getUserObject();
 158  0 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
 159  0 IDataFlowNode child = (IDataFlowNode) inode.getChildren().get(last.currentChild);
 160  0 this.currentPath.addLast(child);
 161    } else {
 162  0 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
 163  0 IDataFlowNode child = (IDataFlowNode) inode.getChildren().get(0); //TODO ???? IMPORTANT - ERROR?
 164  0 this.currentPath.addLast(child);
 165    }
 166    }
 167   
 168  0 private boolean isFirstDoStatement(IDataFlowNode inode) {
 169  0 int index = inode.getIndex() - 1;
 170  0 if (index < 0) return false;
 171   
 172  0 IDataFlowNode before = (IDataFlowNode) inode.getFlow().get(index);
 173  0 return before.isType(NodeType.DO_BEFORE_FIRST_STATEMENT);
 174    }
 175   
 176  0 private boolean isDoBranchNode() {
 177  0 IDataFlowNode last = (IDataFlowNode) this.currentPath.getLast();
 178  0 return this.isDoBranch(last);
 179    }
 180   
 181  0 private boolean isDoBranch(IDataFlowNode inode) {
 182  0 return inode.isType(NodeType.DO_EXPR);
 183    }
 184   
 185    // ----------------------------------------------------------------------------
 186    // TREE FUNCTIONS
 187   
 188    /*
 189    * Adds a PathElement to a Tree, which contains information about
 190    * loops and "local scopes - encapsulation".
 191    * */
 192  0 private void addNodeToTree() {
 193  0 if (this.isFirstDoStatement()) {
 194  0 DefaultMutableTreeNode level = this.getRootNode();
 195  0 IDataFlowNode doBranch = this.getDoBranchNodeFromFirstDoStatement();
 196   
 197  0 while (true) {
 198  0 if (this.hasTheLevelChildren(level)) {
 199  0 PathElement ref;
 200  0 if ((ref = this.isNodeInLevel(level)) != null) {
 201    //addRefPseudoNode
 202  0 this.addRefPseudoPathElement(level, ref);
 203  0 break;
 204    } else {
 205  0 level = this.getLastChildNode(level);
 206  0 continue;
 207    }
 208    } else {
 209    //addNewPseudoNode
 210  0 this.addNewPseudoPathElement(level, doBranch);
 211  0 break;
 212    }
 213    }
 214    }
 215   
 216  0 if (this.isBranch()) {
 217  0 DefaultMutableTreeNode level = this.getRootNode();
 218   
 219  0 if (this.isDoBranchNode()) {
 220  0 while (!this.equalsPseudoPathElementWithDoBranchNodeInLevel(level)) {
 221  0 level = this.getLastChildNode(level);
 222    }
 223  0 PathElement ref;
 224  0 if ((ref = this.getDoBranchNodeInLevel(level)) != null) {
 225    //addRefNode
 226  0 this.addRefPathElement(level, ref);
 227    } else {
 228    //createNewNode
 229  0 this.addNewPathElement(level);
 230    }
 231   
 232    } else {
 233  0 while (true) {
 234  0 if (this.hasTheLevelChildren(level)) {
 235  0 PathElement ref;
 236  0 if ((ref = this.isNodeInLevel(level)) != null) {
 237    //addRefNode
 238  0 this.addRefPathElement(level, ref);
 239  0 break;
 240    } else {
 241  0 level = this.getLastChildNode(level);
 242  0 continue;
 243    }
 244    } else {
 245    //createNewNode
 246  0 this.addNewPathElement(level);
 247  0 break;
 248    }
 249    }
 250    }
 251    }
 252    }
 253   
 254  0 private void removeFromTree() {
 255  0 DefaultMutableTreeNode last = this.getLastNode();
 256   
 257  0 if (last == null) {
 258  0 System.out.println("removeFromTree - last == null");
 259  0 return;
 260    }
 261   
 262  0 DefaultMutableTreeNode parent = (DefaultMutableTreeNode) last.getParent();
 263  0 parent.remove(last);
 264   
 265  0 last = this.getLastNode();
 266   
 267  0 if (last == null) return;
 268  0 if (last.getUserObject() == null) return;
 269   
 270  0 PathElement e = (PathElement) last.getUserObject();
 271  0 if (this.isPseudoPathElement(e)) {
 272  0 this.removeFromTree();
 273    }
 274    }
 275   
 276  0 private IDataFlowNode getDoBranchNodeFromFirstDoStatement() {
 277  0 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
 278   
 279  0 if (!this.isFirstDoStatement()) return null;
 280   
 281  0 for (int i = 0; i < inode.getParents().size(); i++) {
 282  0 IDataFlowNode parent = (IDataFlowNode) inode.getParents().get(i);
 283   
 284  0 if (this.isDoBranch(parent)) {
 285  0 return parent;
 286    }
 287    }
 288  0 return null;
 289    }
 290   
 291  0 private void addNewPathElement(DefaultMutableTreeNode level) {
 292  0 IDataFlowNode last = (IDataFlowNode) this.currentPath.getLast();
 293  0 PathElement e = new PathElement(last);
 294  0 this.addNode(level, e);
 295    }
 296   
 297  0 private void addRefPathElement(DefaultMutableTreeNode level, PathElement ref) {
 298  0 this.addNode(level, ref);
 299    }
 300   
 301    /*
 302    * Needed for do loops
 303    * */
 304  0 private void addNewPseudoPathElement(DefaultMutableTreeNode level, IDataFlowNode ref) {
 305  0 IDataFlowNode last = (IDataFlowNode) this.currentPath.getLast();
 306  0 PathElement e = new PathElement(last);
 307  0 e.pseudoRef = ref;
 308  0 this.addNode(level, e);
 309    }
 310   
 311    /*
 312    * Needed for do loops
 313    * */
 314  0 private void addRefPseudoPathElement(DefaultMutableTreeNode level, PathElement ref) {
 315  0 this.addNode(level, ref);
 316    }
 317   
 318  0 private boolean equalsPseudoPathElementWithDoBranchNodeInLevel(DefaultMutableTreeNode level) {
 319  0 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
 320   
 321  0 if (!this.isDoBranch(inode)) return false;
 322   
 323  0 int childCount = level.getChildCount();
 324  0 DefaultMutableTreeNode child;
 325   
 326  0 for (int i = 0; i < childCount; i++) {
 327  0 child = (DefaultMutableTreeNode) level.getChildAt(i);
 328  0 PathElement pe = (PathElement) child.getUserObject();
 329  0 if (isPseudoPathElement(pe) && pe.pseudoRef.equals(inode)) {
 330  0 return true;
 331    }
 332    }
 333  0 return false;
 334    }
 335   
 336  0 private PathElement getDoBranchNodeInLevel(DefaultMutableTreeNode level) {
 337  0 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
 338   
 339  0 if (!this.isDoBranch(inode)) return null;
 340   
 341  0 int childCount = level.getChildCount();
 342  0 DefaultMutableTreeNode child;
 343   
 344  0 for (int i = 0; i < childCount; i++) {
 345  0 child = (DefaultMutableTreeNode) level.getChildAt(i);
 346  0 PathElement pe = (PathElement) child.getUserObject();
 347  0 if (inode.equals(pe.node)) {
 348  0 return pe;
 349    }
 350    }
 351  0 return null;
 352    }
 353   
 354  0 private void addNode(DefaultMutableTreeNode level, PathElement element) {
 355  0 DefaultMutableTreeNode node = new DefaultMutableTreeNode();
 356  0 node.setUserObject(element);
 357  0 level.add(node);
 358    }
 359   
 360  0 private PathElement isNodeInLevel(DefaultMutableTreeNode level) {
 361  0 IDataFlowNode inode = (IDataFlowNode) this.currentPath.getLast();
 362  0 DefaultMutableTreeNode child = (DefaultMutableTreeNode) level.getFirstChild();
 363   
 364  0 if (child != null) {
 365  0 PathElement levelElement = (PathElement) child.getUserObject();
 366  0 if (inode.equals(levelElement.node)) {
 367  0 return levelElement;
 368    }
 369    }
 370  0 return null;
 371    }
 372   
 373  0 private DefaultMutableTreeNode getLastChildNode(DefaultMutableTreeNode node) {
 374  0 if (this.hasTheLevelChildren(node)) {
 375  0 return (DefaultMutableTreeNode) node.getLastChild();
 376    }
 377  0 return node;
 378    }
 379   
 380  0 private DefaultMutableTreeNode getRootNode() {
 381  0 return this.stack;
 382    }
 383   
 384  0 private boolean hasTheLevelChildren(DefaultMutableTreeNode level) {
 385  0 return level.getChildCount() != 0;
 386    }
 387   
 388  0 private DefaultMutableTreeNode getLastNode() {
 389  0 return this.stack.getLastLeaf();
 390    }
 391   
 392  0 private int countLoops() {
 393  0 DefaultMutableTreeNode treeNode = this.getLastNode();
 394  0 int counter = 0;
 395  0 int childCount = treeNode.getParent().getChildCount();
 396  0 for (int i = 0; i < childCount; i++) {
 397  0 DefaultMutableTreeNode tNode = (DefaultMutableTreeNode) treeNode.getParent().getChildAt(i);
 398  0 PathElement e = (PathElement) tNode.getUserObject();
 399  0 if (!this.isPseudoPathElement(e)) {
 400  0 counter++;
 401    }
 402    }
 403  0 return counter;
 404    }
 405   
 406  0 private void incChild() {
 407  0 DefaultMutableTreeNode last = this.getLastNode();
 408  0 PathElement e = (PathElement) last.getUserObject();
 409  0 e.currentChild++;
 410    }
 411   
 412  0 private boolean isPseudoPathElement(PathElement pe) {
 413  0 return pe != null && pe.pseudoRef != null;
 414    }
 415    }