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 }