View Javadoc

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