View Javadoc

    1   /*
    2    * Created on 09.08.2004
    3    */
    4   package net.sourceforge.pmd.lang.dfa.pathfinder;
    5
    6   import javax.swing.tree.DefaultMutableTreeNode;
    7
    8   import net.sourceforge.pmd.lang.dfa.DataFlowNode;
    9   import net.sourceforge.pmd.lang.dfa.NodeType;
    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 DataFlowNode 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(DataFlowNode rootNode, Executable shim) {
    27          this.rootNode = rootNode;
    28          this.shim = shim;
    29          this.maxPaths = MAX_PATHS;
    30      }
    31
    32      public DAAPathFinder(DataFlowNode 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             DataFlowNode 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         	DataFlowNode child = inode.getChildren().get(last.currentChild);
    131                 this.currentPath.addLast(child);
    132             }
    133         } else {
    134             DataFlowNode inode = currentPath.getLast();
    135             DataFlowNode 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             DataFlowNode 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 = this.isNodeInLevel(level);
    190                         if (ref != 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) {
    219             return;
    220         }
    221
    222         PathElement e = (PathElement) last.getUserObject();
    223         if (e != null && e.isPseudoPathElement()) {
    224             this.removeFromTree();
    225         }
    226     }
    227
    228     private void addNewPathElement(DefaultMutableTreeNode level) {
    229         addNode(level, new PathElement(currentPath.getLast()));
    230     }
    231
    232     /*
    233      * Needed for do loops
    234      * */
    235     private void addNewPseudoPathElement(DefaultMutableTreeNode level, DataFlowNode ref) {
    236         addNode(level, new PathElement(currentPath.getLast(), ref));
    237     }
    238
    239     /*
    240      * Needed for do loops
    241      * */
    242     private void addRefPseudoPathElement(DefaultMutableTreeNode level, PathElement ref) {
    243         addNode(level, ref);
    244     }
    245
    246     private boolean equalsPseudoPathElementWithDoBranchNodeInLevel(DefaultMutableTreeNode level) {
    247 	DataFlowNode inode = currentPath.getLast();
    248
    249         if (!inode.isType(NodeType.DO_EXPR)) {
    250             return false;
    251         }
    252
    253         int childCount = level.getChildCount();
    254         DefaultMutableTreeNode child;
    255
    256         for (int i = 0; i < childCount; i++) {
    257             child = (DefaultMutableTreeNode) level.getChildAt(i);
    258             PathElement pe = (PathElement) child.getUserObject();
    259             if (pe != null && pe.isPseudoPathElement() && pe.pseudoRef.equals(inode)) {
    260                 return true;
    261             }
    262         }
    263         return false;
    264     }
    265
    266     private PathElement getDoBranchNodeInLevel(DefaultMutableTreeNode level) {
    267 	DataFlowNode inode = currentPath.getLast();
    268         if (!inode.isType(NodeType.DO_EXPR)) {
    269             return null;
    270         }
    271
    272         int childCount = level.getChildCount();
    273         DefaultMutableTreeNode child;
    274
    275         for (int i = 0; i < childCount; i++) {
    276             child = (DefaultMutableTreeNode) level.getChildAt(i);
    277             PathElement pe = (PathElement) child.getUserObject();
    278             if (inode.equals(pe.node)) {
    279                 return pe;
    280             }
    281         }
    282         return null;
    283     }
    284
    285     private void addNode(DefaultMutableTreeNode level, PathElement element) {
    286         DefaultMutableTreeNode node = new DefaultMutableTreeNode();
    287         node.setUserObject(element);
    288         level.add(node);
    289     }
    290
    291     private PathElement isNodeInLevel(DefaultMutableTreeNode level) {
    292 	DataFlowNode inode = currentPath.getLast();
    293         DefaultMutableTreeNode child = (DefaultMutableTreeNode) level.getFirstChild();
    294
    295         if (child != null) {
    296             PathElement levelElement = (PathElement) child.getUserObject();
    297             if (inode.equals(levelElement.node)) {
    298                 return levelElement;
    299             }
    300         }
    301         return null;
    302     }
    303
    304     private DefaultMutableTreeNode getLastChildNode(DefaultMutableTreeNode node) {
    305         if (node.getChildCount() != 0) {
    306             return (DefaultMutableTreeNode) node.getLastChild();
    307         }
    308         return node;
    309     }
    310
    311     private int countLoops() {
    312         DefaultMutableTreeNode treeNode = stack.getLastLeaf();
    313         int counter = 0;
    314         if (treeNode.getParent() != null) {
    315             // for some unknown reasons the parent of treeNode might be null, see bug 1597987
    316             int childCount = treeNode.getParent().getChildCount();
    317             for (int i = 0; i < childCount; i++) {
    318                 DefaultMutableTreeNode tNode = (DefaultMutableTreeNode) treeNode.getParent().getChildAt(i);
    319                 PathElement e = (PathElement) tNode.getUserObject();
    320                 if (e != null && !e.isPseudoPathElement()) {
    321                     counter++;
    322                 }
    323             }
    324         }
    325         return counter;
    326     }
    327
    328     private void incChild() {
    329         ((PathElement) stack.getLastLeaf().getUserObject()).currentChild++;
    330     }
    331
    332 }