View Javadoc

    1   /**
    2    * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
    3    */
    4   package net.sourceforge.pmd.dfa;
    5
    6   import java.util.List;
    7
    8   import net.sourceforge.pmd.ast.ASTLabeledStatement;
    9   import net.sourceforge.pmd.ast.SimpleNode;
    10
    11  /**
    12   * @author raik
    13   *         Links data flow nodes to each other.
    14   */
    15  public class Linker {
    16
    17      private List braceStack;
    18      private List continueBreakReturnStack;
    19
    20      public Linker(List braceStack, List continueBreakReturnStack) {
    21          this.braceStack = braceStack;
    22          this.continueBreakReturnStack = continueBreakReturnStack;
    23      }
    24
    25      /**
    26       * Creates all the links between the data flow nodes.
    27       */
    28      public void computePaths() throws LinkerException, SequenceException {
    29          // Returns true if there are more sequences, computes the first and
    30          // the last index of the sequence.
    31          SequenceChecker sc = new SequenceChecker(braceStack);
    32          while (!sc.run()) {
    33              if (sc.getFirstIndex() < 0 || sc.getLastIndex() < 0) {
    34                  throw new SequenceException("computePaths(): return index <  0");
    35              }
    36
    37              StackObject firstStackObject = (StackObject) braceStack.get(sc.getFirstIndex());
    38
    39              switch (firstStackObject.getType()) {
    40                  case NodeType.IF_EXPR:
    41                      int x = sc.getLastIndex() - sc.getFirstIndex();
    42                      if (x == 2) {
    43                          this.computeIf(sc.getFirstIndex(), sc.getFirstIndex() + 1, sc.getLastIndex());
    44                      } else if (x == 1) {
    45                          this.computeIf(sc.getFirstIndex(), sc.getLastIndex());
    46                      } else {
    47                          System.out.println("Error - computePaths 1");
    48                      }
    49                      break;
    50
    51                  case NodeType.WHILE_EXPR:
    52                      this.computeWhile(sc.getFirstIndex(), sc.getLastIndex());
    53                      break;
    54
    55                  case NodeType.SWITCH_START:
    56                      this.computeSwitch(sc.getFirstIndex(), sc.getLastIndex());
    57                      break;
    58
    59                  case NodeType.FOR_INIT:
    60                  case NodeType.FOR_EXPR:
    61                  case NodeType.FOR_UPDATE:
    62                  case NodeType.FOR_BEFORE_FIRST_STATEMENT:
    63                      this.computeFor(sc.getFirstIndex(), sc.getLastIndex());
    64                      break;
    65
    66                  case NodeType.DO_BEFORE_FIRST_STATEMENT:
    67                      this.computeDo(sc.getFirstIndex(), sc.getLastIndex());
    68                      break;
    69
    70                  default:
    71              }
    72
    73              for (int y = sc.getLastIndex(); y >= sc.getFirstIndex(); y--) {
    74                  braceStack.remove(y);
    75              }
    76          }
    77
    78          while (!continueBreakReturnStack.isEmpty()) {
    79              StackObject stackObject = (StackObject) continueBreakReturnStack.get(0);
    80              IDataFlowNode node = stackObject.getDataFlowNode();
    81
    82              switch (stackObject.getType()) {
    83              	case NodeType.THROW_STATEMENT:
    84              		// do the same like a return
    85                  case NodeType.RETURN_STATEMENT:
    86                      // remove all children (should contain only one child)
    87                      node.removePathToChild(node.getChildren().get(0));
    88                      IDataFlowNode lastNode = node.getFlow().get(node.getFlow().size() - 1);
    89                      node.addPathToChild(lastNode);
    90                      continueBreakReturnStack.remove(0);
    91                      break;
    92                  case NodeType.BREAK_STATEMENT:
    93                      IDataFlowNode last = getNodeToBreakStatement(node);
    94                      node.removePathToChild(node.getChildren().get(0));
    95                      node.addPathToChild(last);
    96                      continueBreakReturnStack.remove(0);
    97                      break;
    98
    99                  case NodeType.CONTINUE_STATEMENT:
    100                     //List cList = node.getFlow();
    101                     /* traverse up the tree and find the first loop start node
    102                      */
    103 /*
    104                                for(int i = cList.indexOf(node)-1;i>=0;i--) {
    105                                    IDataFlowNode n = (IDataFlowNode)cList.get(i);
    106
    107                                    if(n.isType(NodeType.FOR_UPDATE) ||
    108                                                n.isType(NodeType.FOR_EXPR) ||
    109                                                n.isType(NodeType.WHILE_EXPR)) {
    110 */
    111                     /*
    112                      * while(..) {
    113                      *              while(...) {
    114                      *                      ...
    115                      *              }
    116                      *              continue;
    117                      * }
    118                      *
    119                      * Without this Expression he continues the second
    120                      * WHILE loop. The continue statement and the while loop
    121                      * have to be in different scopes.
    122                      *
    123                      * TODO An error occurs if "continue" is even nested in
    124                      * scopes other than local loop scopes, like "if".
    125                      * The result is, that the data flow isn't build right
    126                      * and the pathfinder runs in invinity loop.
    127                      * */
    128 /*                                     if(n.getSimpleNode().getScope().equals(node.getSimpleNode().getScope())) {
    129                                                System.err.println("equals");
    130                                                continue;
    131                                        }
    132                                        else {
    133                                                System.err.println("don't equals");
    134                                        }
    135
    136                                                //remove all children (should contain only one child)
    137                                        node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
    138
    139                                        node.addPathToChild(n);
    140                                        cbrStack.remove(0);
    141                                        break;
    142
    143                                    }else if(n.isType(NodeType.DO_BEFOR_FIRST_STATEMENT)) {
    144
    145                                        IDataFlowNode inode = (IDataFlowNode)n.getFlow().get(n.getIndex()1);
    146
    147                                        for(int j=0;j<inode.getParents().size();j) {
    148                                                IDataFlowNode parent = (IDataFlowNode)inode.getParents().get(j);
    149
    150                                                if(parent.isType(NodeType.DO_EXPR)) {
    151                                                        node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
    152                                                node.addPathToChild(parent);
    153
    154                                                cbrStack.remove(0);
    155                                                        break;
    156                                                }
    157                                        }
    158                                        break;
    159                                    }
    160                                }
    161 */continueBreakReturnStack.remove(0); // delete this statement if you uncomment the stuff above
    162             }
    163         }
    164     }
    165
    166     private IDataFlowNode getNodeToBreakStatement(IDataFlowNode node) {
    167         // What about breaks to labels above if statements?
    168         List bList = node.getFlow();
    169         int findEnds = 1; // ignore ends of other for's while's etc.
    170
    171
    172         // find out index of the node where the path goes to after the break
    173         int index = bList.indexOf(node);
    174         for (; index < bList.size()-2; index++) {
    175             IDataFlowNode n = (IDataFlowNode) bList.get(index);
    176             if (n.isType(NodeType.DO_EXPR) ||
    177                     n.isType(NodeType.FOR_INIT) ||
    178                     n.isType(NodeType.WHILE_EXPR) ||
    179                     n.isType(NodeType.SWITCH_START)) {
    180                 findEnds++;
    181             }
    182             if (n.isType(NodeType.WHILE_LAST_STATEMENT) ||
    183                     n.isType(NodeType.SWITCH_END) ||
    184                     n.isType(NodeType.FOR_END) ||
    185                     n.isType(NodeType.DO_EXPR)) {
    186                 if (findEnds > 1) {
    187                     // thats not the right node
    188                     findEnds--;
    189                 } else {
    190                     break;
    191                 }
    192             }
    193
    194             if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
    195                 SimpleNode parentNode = n.getSimpleNode().getFirstParentOfType(ASTLabeledStatement.class);
    196                 if (parentNode == null) {
    197                     break;
    198                 } else {
    199                     String label = node.getSimpleNode().getImage();
    200                     if (label == null || label.equals(parentNode.getImage())) {
    201                         node.removePathToChild(node.getChildren().get(0));
    202                         IDataFlowNode last = (IDataFlowNode) bList.get(index + 1);
    203                         node.addPathToChild(last);
    204                         break;
    205                     }
    206                 }
    207             }
    208         }
    209         return node.getFlow().get(index+1);
    210     }
    211
    212     private void computeDo(int first, int last) {
    213         IDataFlowNode doSt = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
    214         IDataFlowNode doExpr = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
    215         IDataFlowNode doFirst = doSt.getFlow().get(doSt.getIndex() + 1);
    216         if (doFirst.getIndex() != doExpr.getIndex()) {
    217             doExpr.addPathToChild(doFirst);
    218         }
    219     }
    220
    221     private void computeFor(int firstIndex, int lastIndex) {
    222         IDataFlowNode fExpr = null;
    223         IDataFlowNode fUpdate = null;
    224         IDataFlowNode fSt = null;
    225         IDataFlowNode fEnd = null;
    226         boolean isUpdate = false;
    227
    228         for (int i = firstIndex; i <= lastIndex; i++) {
    229             StackObject so = (StackObject) this.braceStack.get(i);
    230             IDataFlowNode node = so.getDataFlowNode();
    231
    232             if (so.getType() == NodeType.FOR_EXPR) {
    233                 fExpr = node;
    234             } else if (so.getType() == NodeType.FOR_UPDATE) {
    235                 fUpdate = node;
    236                 isUpdate = true;
    237             } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
    238                 fSt = node;
    239             } else if (so.getType() == NodeType.FOR_END) {
    240                 fEnd = node;
    241             }
    242         }
    243         IDataFlowNode end = fEnd.getFlow().get(fEnd.getIndex() + 1);
    244
    245         IDataFlowNode firstSt = fSt.getChildren().get(0);
    246
    247         if (isUpdate) {
    248             if (fSt.getIndex() != fEnd.getIndex()) {
    249                 end.reverseParentPathsTo(fUpdate);
    250                 fExpr.removePathToChild(fUpdate);
    251                 fUpdate.addPathToChild(fExpr);
    252                 fUpdate.removePathToChild(firstSt);
    253                 fExpr.addPathToChild(firstSt);
    254                 fExpr.addPathToChild(end);
    255             } else {
    256                 fSt.removePathToChild(end);
    257                 fExpr.removePathToChild(fUpdate);
    258                 fUpdate.addPathToChild(fExpr);
    259                 fExpr.addPathToChild(fUpdate);
    260                 fExpr.addPathToChild(end);
    261             }
    262         } else {
    263             if (fSt.getIndex() != fEnd.getIndex()) {
    264                 end.reverseParentPathsTo(fExpr);
    265                 fExpr.addPathToChild(end);
    266             }
    267         }
    268     }
    269
    270     private void computeSwitch(int firstIndex, int lastIndex) {
    271
    272         int diff = lastIndex - firstIndex;
    273         boolean defaultStatement = false;
    274
    275         IDataFlowNode sStart = ((StackObject) this.braceStack.get(firstIndex)).getDataFlowNode();
    276         IDataFlowNode sEnd = ((StackObject) this.braceStack.get(lastIndex)).getDataFlowNode();
    277         IDataFlowNode end = sEnd.getChildren().get(0);
    278
    279         for (int i = 0; i < diff - 2; i++) {
    280             StackObject so = (StackObject) this.braceStack.get(firstIndex + 2 + i);
    281             IDataFlowNode node = so.getDataFlowNode();
    282
    283             sStart.addPathToChild(node.getChildren().get(0));
    284
    285             if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT)
    286                 defaultStatement = true;
    287         }
    288
    289         if (!defaultStatement)
    290             sStart.addPathToChild(end);
    291     }
    292
    293     private void computeWhile(int first, int last) {
    294         IDataFlowNode wStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
    295         IDataFlowNode wEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
    296
    297         IDataFlowNode end = wEnd.getFlow().get(wEnd.getIndex() + 1);
    298
    299         if (wStart.getIndex() != wEnd.getIndex()) {
    300             end.reverseParentPathsTo(wStart);
    301             wStart.addPathToChild(end);
    302         }
    303     }
    304
    305     private void computeIf(int first, int second, int last) {
    306         IDataFlowNode ifStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
    307         IDataFlowNode ifEnd = ((StackObject) this.braceStack.get(second)).getDataFlowNode();
    308         IDataFlowNode elseEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
    309
    310         IDataFlowNode elseStart = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
    311         IDataFlowNode end = elseEnd.getFlow().get(elseEnd.getIndex() + 1);
    312
    313         // if if-statement and else-statement contains statements or expressions
    314         if (ifStart.getIndex() != ifEnd.getIndex() &&
    315                 ifEnd.getIndex() != elseEnd.getIndex()) {
    316             elseStart.reverseParentPathsTo(end);
    317             ifStart.addPathToChild(elseStart);
    318         }
    319         // if only if-statement contains no expressions
    320         else if (ifStart.getIndex() == ifEnd.getIndex() &&
    321                 ifEnd.getIndex() != elseEnd.getIndex()) {
    322             ifStart.addPathToChild(end);
    323         }
    324         // if only else-statement contains no expressions
    325         else if (ifEnd.getIndex() == elseEnd.getIndex() &&
    326                 ifStart.getIndex() != ifEnd.getIndex()) {
    327             ifStart.addPathToChild(end);
    328         }
    329     }
    330
    331     private void computeIf(int first, int last) {
    332         IDataFlowNode ifStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
    333         IDataFlowNode ifEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
    334
    335         // only if the if-statement contains another Statement or Expression
    336         if (ifStart.getIndex() != ifEnd.getIndex()) {
    337             IDataFlowNode end = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
    338             ifStart.addPathToChild(end);
    339         }
    340     }
    341 }