View Javadoc

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