View Javadoc

    1   /*
    2    * Created on 12.07.2004
    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.RETURN_STATEMENT:
    84                      // remove all children (should contain only one child)
    85                      node.removePathToChild((IDataFlowNode) node.getChildren().get(0));
    86                      IDataFlowNode lastNode = (IDataFlowNode) node.getFlow().get(node.getFlow().size() - 1);
    87                      node.addPathToChild(lastNode);
    88                      continueBreakReturnStack.remove(0);
    89                      break;
    90                  case NodeType.BREAK_STATEMENT:
    91                      IDataFlowNode last = getNodeToBreakStatement(node);
    92                      node.removePathToChild((IDataFlowNode) node.getChildren().get(0));
    93                      node.addPathToChild(last);
    94                      continueBreakReturnStack.remove(0);
    95                      break;
    96
    97                  case NodeType.CONTINUE_STATEMENT:
    98                      //List cList = node.getFlow();
    99                      /* traverse up the tree and find the first loop start node
    100                      */
    101 /*
    102                                for(int i = cList.indexOf(node)-1;i>=0;i--) {
    103                                    IDataFlowNode n = (IDataFlowNode)cList.get(i);
    104
    105                                    if(n.isType(NodeType.FOR_UPDATE) ||
    106                                                n.isType(NodeType.FOR_EXPR) ||
    107                                                n.isType(NodeType.WHILE_EXPR)) {
    108 */
    109                     /*
    110                      * while(..) {
    111                      *              while(...) {
    112                      *                      ...
    113                      *              }
    114                      *              continue;
    115                      * }
    116                      *
    117                      * Without this Expression he continues the second
    118                      * WHILE loop. The continue statement and the while loop
    119                      * have to be in different scopes.
    120                      *
    121                      * TODO An error occurs if "continue" is even nested in
    122                      * scopes other than local loop scopes, like "if".
    123                      * The result is, that the data flow isn't build right
    124                      * and the pathfinder runs in invinity loop.
    125                      * */
    126 /*                                     if(n.getSimpleNode().getScope().equals(node.getSimpleNode().getScope())) {
    127                                                System.err.println("equals");
    128                                                continue;
    129                                        }
    130                                        else {
    131                                                System.err.println("don't equals");
    132                                        }
    133
    134                                                //remove all children (should contain only one child)
    135                                        node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
    136
    137                                        node.addPathToChild(n);
    138                                        cbrStack.remove(0);
    139                                        break;
    140
    141                                    }else if(n.isType(NodeType.DO_BEFOR_FIRST_STATEMENT)) {
    142
    143                                        IDataFlowNode inode = (IDataFlowNode)n.getFlow().get(n.getIndex()1);
    144
    145                                        for(int j=0;j<inode.getParents().size();j) {
    146                                                IDataFlowNode parent = (IDataFlowNode)inode.getParents().get(j);
    147
    148                                                if(parent.isType(NodeType.DO_EXPR)) {
    149                                                        node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
    150                                                node.addPathToChild(parent);
    151
    152                                                cbrStack.remove(0);
    153                                                        break;
    154                                                }
    155                                        }
    156                                        break;
    157                                    }
    158                                }
    159 */continueBreakReturnStack.remove(0); // delete this statement if you uncomment the stuff above
    160             }
    161         }
    162     }
    163
    164     private IDataFlowNode getNodeToBreakStatement(IDataFlowNode node) {
    165         // What about breaks to labels above if statements?
    166         List bList = node.getFlow();
    167         int findEnds = 1; // ignore ends of other for's while's etc.
    168
    169
    170         // find out index of the node where the path goes to after the break
    171         int index = bList.indexOf(node);
    172         for (; index < bList.size()-2; index++) {
    173             IDataFlowNode n = (IDataFlowNode) bList.get(index);
    174             if (n.isType(NodeType.DO_EXPR) ||
    175                     n.isType(NodeType.FOR_INIT) ||
    176                     n.isType(NodeType.WHILE_EXPR) ||
    177                     n.isType(NodeType.SWITCH_START)) {
    178                 findEnds++;
    179             }
    180             if (n.isType(NodeType.WHILE_LAST_STATEMENT) ||
    181                     n.isType(NodeType.SWITCH_END) ||
    182                     n.isType(NodeType.FOR_END) ||
    183                     n.isType(NodeType.DO_EXPR)) {
    184                 if (findEnds > 1) {
    185                     // thats not the right node
    186                     findEnds--;
    187                 } else {
    188                     break;
    189                 }
    190             }
    191
    192             if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
    193                 SimpleNode parentNode = (SimpleNode) n.getSimpleNode().getFirstParentOfType(ASTLabeledStatement.class);
    194                 if (parentNode == null) {
    195                     break;
    196                 } else {
    197                     String label = node.getSimpleNode().getImage();
    198                     if (label == null || label.equals(parentNode.getImage())) {
    199                         node.removePathToChild((IDataFlowNode) node.getChildren().get(0));
    200                         IDataFlowNode last = (IDataFlowNode) bList.get(index + 1);
    201                         node.addPathToChild(last);
    202                         break;
    203                     }
    204                 }
    205             }
    206         }
    207         return (IDataFlowNode)node.getFlow().get(index+1);
    208     }
    209
    210     private void computeDo(int first, int last) {
    211         IDataFlowNode doSt = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
    212         IDataFlowNode doExpr = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
    213         IDataFlowNode doFirst = (IDataFlowNode) doSt.getFlow().get(doSt.getIndex() + 1);
    214         if (doFirst.getIndex() != doExpr.getIndex()) {
    215             doExpr.addPathToChild(doFirst);
    216         }
    217     }
    218
    219     private void computeFor(int firstIndex, int lastIndex) {
    220         IDataFlowNode fExpr = null;
    221         IDataFlowNode fUpdate = null;
    222         IDataFlowNode fSt = null;
    223         IDataFlowNode fEnd = null;
    224         boolean isUpdate = false;
    225
    226         for (int i = firstIndex; i <= lastIndex; i++) {
    227             StackObject so = (StackObject) this.braceStack.get(i);
    228             IDataFlowNode node = so.getDataFlowNode();
    229
    230             if (so.getType() == NodeType.FOR_EXPR) {
    231                 fExpr = node;
    232             } else if (so.getType() == NodeType.FOR_UPDATE) {
    233                 fUpdate = node;
    234                 isUpdate = true;
    235             } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
    236                 fSt = node;
    237             } else if (so.getType() == NodeType.FOR_END) {
    238                 fEnd = node;
    239             }
    240         }
    241         IDataFlowNode end = (IDataFlowNode) fEnd.getFlow().get(fEnd.getIndex() + 1);
    242
    243         IDataFlowNode firstSt = (IDataFlowNode) fSt.getChildren().get(0);
    244
    245         if (isUpdate) {
    246             if (fSt.getIndex() != fEnd.getIndex()) {
    247                 end.reverseParentPathsTo(fUpdate);
    248                 fExpr.removePathToChild(fUpdate);
    249                 fUpdate.addPathToChild(fExpr);
    250                 fUpdate.removePathToChild(firstSt);
    251                 fExpr.addPathToChild(firstSt);
    252                 fExpr.addPathToChild(end);
    253             } else {
    254                 fSt.removePathToChild(end);
    255                 fExpr.removePathToChild(fUpdate);
    256                 fUpdate.addPathToChild(fExpr);
    257                 fExpr.addPathToChild(fUpdate);
    258                 fExpr.addPathToChild(end);
    259             }
    260         } else {
    261             if (fSt.getIndex() != fEnd.getIndex()) {
    262                 end.reverseParentPathsTo(fExpr);
    263                 fExpr.addPathToChild(end);
    264             }
    265         }
    266     }
    267
    268     private void computeSwitch(int firstIndex, int lastIndex) {
    269
    270         int diff = lastIndex - firstIndex;
    271         boolean defaultStatement = false;
    272
    273         IDataFlowNode sStart = ((StackObject) this.braceStack.get(firstIndex)).getDataFlowNode();
    274         IDataFlowNode sEnd = ((StackObject) this.braceStack.get(lastIndex)).getDataFlowNode();
    275         IDataFlowNode end = (IDataFlowNode) sEnd.getChildren().get(0);
    276
    277         for (int i = 0; i < diff - 2; i++) {
    278             StackObject so = (StackObject) this.braceStack.get(firstIndex + 2 + i);
    279             IDataFlowNode node = so.getDataFlowNode();
    280
    281             sStart.addPathToChild((IDataFlowNode) node.getChildren().get(0));
    282
    283             if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT)
    284                 defaultStatement = true;
    285         }
    286
    287         if (!defaultStatement)
    288             sStart.addPathToChild(end);
    289     }
    290
    291     private void computeWhile(int first, int last) {
    292         IDataFlowNode wStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
    293         IDataFlowNode wEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
    294
    295         IDataFlowNode end = (IDataFlowNode) wEnd.getFlow().get(wEnd.getIndex() + 1);
    296
    297         if (wStart.getIndex() != wEnd.getIndex()) {
    298             end.reverseParentPathsTo(wStart);
    299             wStart.addPathToChild(end);
    300         }
    301     }
    302
    303     private void computeIf(int first, int second, int last) {
    304         IDataFlowNode ifStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
    305         IDataFlowNode ifEnd = ((StackObject) this.braceStack.get(second)).getDataFlowNode();
    306         IDataFlowNode elseEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
    307
    308         IDataFlowNode elseStart = (IDataFlowNode) ifEnd.getFlow().get(ifEnd.getIndex() + 1);
    309         IDataFlowNode end = (IDataFlowNode) elseEnd.getFlow().get(elseEnd.getIndex() + 1);
    310
    311         // if if-statement and else-statement contains statements or expressions
    312         if (ifStart.getIndex() != ifEnd.getIndex() &&
    313                 ifEnd.getIndex() != elseEnd.getIndex()) {
    314             elseStart.reverseParentPathsTo(end);
    315             ifStart.addPathToChild(elseStart);
    316         }
    317         // if only if-statement contains no expressions
    318         else if (ifStart.getIndex() == ifEnd.getIndex() &&
    319                 ifEnd.getIndex() != elseEnd.getIndex()) {
    320             ifStart.addPathToChild(end);
    321         }
    322         // if only else-statement contains no expressions
    323         else if (ifEnd.getIndex() == elseEnd.getIndex() &&
    324                 ifStart.getIndex() != ifEnd.getIndex()) {
    325             ifStart.addPathToChild(end);
    326         }
    327     }
    328
    329     private void computeIf(int first, int last) {
    330         IDataFlowNode ifStart = ((StackObject) this.braceStack.get(first)).getDataFlowNode();
    331         IDataFlowNode ifEnd = ((StackObject) this.braceStack.get(last)).getDataFlowNode();
    332
    333         // only if the if-statement contains another Statement or Expression
    334         if (ifStart.getIndex() != ifEnd.getIndex()) {
    335             IDataFlowNode end = (IDataFlowNode) ifEnd.getFlow().get(ifEnd.getIndex() + 1);
    336             ifStart.addPathToChild(end);
    337         }
    338     }
    339 }