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