View Javadoc
1   /**
2    * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
3    */
4   package net.sourceforge.pmd.lang.dfa;
5   
6   import java.util.List;
7   import java.util.logging.Level;
8   import java.util.logging.Logger;
9   
10  import net.sourceforge.pmd.lang.DataFlowHandler;
11  import net.sourceforge.pmd.lang.ast.Node;
12  
13  /**
14   * @author raik Links data flow nodes to each other.
15   */
16  public class Linker {
17      private final static Logger LOGGER = Logger.getLogger(Linker.class.getName());
18      private final static String CLASS_NAME = Linker.class.getCanonicalName();
19  
20      /** Maximum loops to prevent hanging of PMD. See https://sourceforge.net/p/pmd/bugs/1393/ */
21      private static final int MAX_LOOPS = 100;
22  
23      private final DataFlowHandler dataFlowHandler;
24      private List<StackObject> braceStack;
25      private List<StackObject> continueBreakReturnStack;
26  
27      public Linker(DataFlowHandler dataFlowHandler, List<StackObject> braceStack,
28              List<StackObject> continueBreakReturnStack) {
29          this.dataFlowHandler = dataFlowHandler;
30          this.braceStack = braceStack;
31          this.continueBreakReturnStack = continueBreakReturnStack;
32      }
33  
34      /**
35       * Creates all the links between the data flow nodes.
36       */
37      public void computePaths() throws LinkerException, SequenceException {
38          LOGGER.entering(CLASS_NAME, "computePaths");
39          // Returns true if there are more sequences, computes the first and
40          // the last index of the sequence.
41          LOGGER.fine("SequenceChecking continueBreakReturnStack elements");
42          SequenceChecker sc = new SequenceChecker(braceStack);
43          int i = 0;
44          while (!sc.run() && i < MAX_LOOPS) {
45              i++;
46              if (LOGGER.isLoggable(Level.FINE)) {
47                  LOGGER.fine("After sc.run - starting Sequence checking loop with firstIndex=" + sc.getFirstIndex()
48                          + ", lastIndex " + sc.getLastIndex() + " with this StackList " + dump("braceStack", braceStack));
49              }
50              if (sc.getFirstIndex() < 0 || sc.getLastIndex() < 0) {
51                  if (LOGGER.isLoggable(Level.SEVERE)) {
52                      LOGGER.severe("Sequence Checker problem: getFirstIndex()==" + sc.getFirstIndex()
53                              + ", getLastIndex()==" + sc.getLastIndex());
54                  }
55                  throw new SequenceException("computePaths(): return index <  0");
56              }
57  
58              StackObject firstStackObject = braceStack.get(sc.getFirstIndex());
59  
60              if (LOGGER.isLoggable(Level.FINE)) {
61                  LOGGER.fine("Checking first braceStack element of type=="
62                          + NodeType.stringFromType(firstStackObject.getType()));
63              }
64              switch (firstStackObject.getType()) {
65              case NodeType.IF_EXPR:
66                  LOGGER.finest("IF_EXPR");
67                  int x = sc.getLastIndex() - sc.getFirstIndex();
68                  if (x == 2) {
69                      this.computeIf(sc.getFirstIndex(), sc.getFirstIndex() + 1, sc.getLastIndex());
70                  } else if (x == 1) {
71                      this.computeIf(sc.getFirstIndex(), sc.getLastIndex());
72                  } else {
73                      LOGGER.severe("Error - computePaths 1");
74                  }
75                  break;
76  
77              case NodeType.WHILE_EXPR:
78                  LOGGER.finest("WHILE_EXPR");
79                  this.computeWhile(sc.getFirstIndex(), sc.getLastIndex());
80                  break;
81  
82              case NodeType.SWITCH_START:
83                  LOGGER.finest("SWITCH_START");
84                  this.computeSwitch(sc.getFirstIndex(), sc.getLastIndex());
85                  break;
86  
87              case NodeType.FOR_INIT:
88              case NodeType.FOR_EXPR:
89              case NodeType.FOR_UPDATE:
90              case NodeType.FOR_BEFORE_FIRST_STATEMENT:
91                  LOGGER.finest("FOR_EXPR");
92                  this.computeFor(sc.getFirstIndex(), sc.getLastIndex());
93                  break;
94  
95              case NodeType.DO_BEFORE_FIRST_STATEMENT:
96                  LOGGER.finest("DO_BEFORE_FIRST_STATEMENT");
97                  this.computeDo(sc.getFirstIndex(), sc.getLastIndex());
98                  break;
99  
100             default:
101             }
102 
103             if (LOGGER.isLoggable(Level.FINEST)) {
104                 LOGGER.finest("Removing braces from Last to first: " + sc.getLastIndex() + " to " + sc.getFirstIndex());
105             }
106             for (int y = sc.getLastIndex(); y >= sc.getFirstIndex(); y--) {
107                 if (LOGGER.isLoggable(Level.FINEST)) {
108                     LOGGER.finest("Removing brace : " + y);
109                 }
110                 braceStack.remove(y);
111             }
112             if (LOGGER.isLoggable(Level.FINE)) {
113                 LOGGER.fine("Completed Sequence checking loop" + braceStack);
114             }
115         }
116         if (LOGGER.isLoggable(Level.FINER)) {
117             LOGGER.log(Level.FINER, "After Sequence checking loop : remaining braces=={0}",
118                     dump("braceStack", braceStack));
119         }
120 
121         LOGGER.fine("Processing continueBreakReturnStack elements");
122         while (!continueBreakReturnStack.isEmpty()) {
123             LOGGER.fine("Starting continueBreakReturnStack processing loop");
124             StackObject stackObject = continueBreakReturnStack.get(0);
125             DataFlowNode node = stackObject.getDataFlowNode();
126 
127             switch (stackObject.getType()) {
128             case NodeType.THROW_STATEMENT:
129                 // do the same like a return
130             case NodeType.RETURN_STATEMENT:
131                 if (LOGGER.isLoggable(Level.FINEST)) {
132                     LOGGER.finest("CBR: " + NodeType.stringFromType(stackObject.getType()));
133                 }
134                 // remove all children (should contain only one child)
135                 node.removePathToChild(node.getChildren().get(0));
136                 DataFlowNode lastNode = node.getFlow().get(node.getFlow().size() - 1);
137                 node.addPathToChild(lastNode);
138                 continueBreakReturnStack.remove(0);
139                 break;
140             case NodeType.BREAK_STATEMENT:
141                 LOGGER.finest("CBR: BREAK_STATEMENT");
142                 DataFlowNode last = getNodeToBreakStatement(node);
143                 node.removePathToChild(node.getChildren().get(0));
144                 node.addPathToChild(last);
145                 continueBreakReturnStack.remove(0);
146                 break;
147 
148             case NodeType.CONTINUE_STATEMENT:
149                 LOGGER.finest("CBR: CONTINUE_STATEMENT");
150                 // List cList = node.getFlow();
151                 /*
152                  * traverse up the tree and find the first loop start node
153                  */
154                 /*
155                  * for(int i = cList.indexOf(node)-1;i>=0;i--) { IDataFlowNode n
156                  * = (IDataFlowNode)cList.get(i);
157                  * 
158                  * if(n.isType(NodeType.FOR_UPDATE) ||
159                  * n.isType(NodeType.FOR_EXPR) || n.isType(NodeType.WHILE_EXPR))
160                  * {
161                  */
162                 /*
163                  * while(..) { while(...) { ... } continue; }
164                  * 
165                  * Without this Expression he continues the second WHILE loop.
166                  * The continue statement and the while loop have to be in
167                  * different scopes.
168                  * 
169                  * TODO An error occurs if "continue" is even nested in scopes
170                  * other than local loop scopes, like "if". The result is, that
171                  * the data flow isn't build right and the pathfinder runs in
172                  * invinity loop.
173                  */
174                 /*
175                  * if(n.getNode().getScope().equals(node.getNode().getScope()))
176                  * { System.err.println("equals"); continue; } else {
177                  * System.err.println("don't equals"); }
178                  * 
179                  * //remove all children (should contain only one child)
180                  * node.removePathToChild
181                  * ((IDataFlowNode)node.getChildren().get(0));
182                  * 
183                  * node.addPathToChild(n); cbrStack.remove(0); break;
184                  * 
185                  * }else if(n.isType(NodeType.DO_BEFOR_FIRST_STATEMENT)) {
186                  * 
187                  * IDataFlowNode inode =
188                  * (IDataFlowNode)n.getFlow().get(n.getIndex()1);
189                  * 
190                  * for(int j=0;j<inode.getParents().size();j) { IDataFlowNode
191                  * parent = (IDataFlowNode)inode.getParents().get(j);
192                  * 
193                  * if(parent.isType(NodeType.DO_EXPR)) {
194                  * node.removePathToChild((
195                  * IDataFlowNode)node.getChildren().get(0));
196                  * node.addPathToChild(parent);
197                  * 
198                  * cbrStack.remove(0); break; } } break; } }
199                  */
200                 continueBreakReturnStack.remove(0); // delete this statement if
201                                                     // you uncomment the stuff
202                                                     // above
203                 break;
204             default:
205                 LOGGER.finest("CBR: default");
206                 // Do nothing
207                 break;
208             }
209             LOGGER.fine("Completed continueBreakReturnStack processing loop");
210         }
211         LOGGER.exiting(CLASS_NAME, "computePaths");
212     }
213 
214     private DataFlowNode getNodeToBreakStatement(DataFlowNode node) {
215         LOGGER.entering(CLASS_NAME, "getNodeToBreakStatement");
216         // What about breaks to labels above if statements?
217         List<DataFlowNode> bList = node.getFlow();
218         int findEnds = 1; // ignore ends of other for's while's etc.
219 
220         // find out index of the node where the path goes to after the break
221         int index = bList.indexOf(node);
222         for (; index < bList.size() - 2; index++) {
223             DataFlowNode n = bList.get(index);
224             if (n.isType(NodeType.DO_EXPR) || n.isType(NodeType.FOR_INIT) || n.isType(NodeType.WHILE_EXPR)
225                     || n.isType(NodeType.SWITCH_START)) {
226                 findEnds++;
227             }
228             if (n.isType(NodeType.WHILE_LAST_STATEMENT) || n.isType(NodeType.SWITCH_END) || n.isType(NodeType.FOR_END)
229                     || n.isType(NodeType.DO_EXPR)) {
230                 if (findEnds > 1) {
231                     // thats not the right node
232                     findEnds--;
233                 } else {
234                     break;
235                 }
236             }
237 
238             if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
239                 Node parentNode = n.getNode().getFirstParentOfType(dataFlowHandler.getLabelStatementNodeClass());
240                 if (parentNode == null) {
241                     break;
242                 } else {
243                     String label = node.getNode().getImage();
244                     if (label == null || label.equals(parentNode.getImage())) {
245                         node.removePathToChild(node.getChildren().get(0));
246                         DataFlowNode last = bList.get(index + 1);
247                         node.addPathToChild(last);
248                         break;
249                     }
250                 }
251             }
252         }
253         LOGGER.exiting(CLASS_NAME, "getNodeToBreakSttement");
254         return node.getFlow().get(index + 1);
255     }
256 
257     private void computeDo(int first, int last) {
258         LOGGER.entering(CLASS_NAME, "computeDo");
259         DataFlowNode doSt = this.braceStack.get(first).getDataFlowNode();
260         DataFlowNode doExpr = this.braceStack.get(last).getDataFlowNode();
261         DataFlowNode doFirst = doSt.getFlow().get(doSt.getIndex() + 1);
262         if (doFirst.getIndex() != doExpr.getIndex()) {
263             doExpr.addPathToChild(doFirst);
264         }
265         LOGGER.exiting(CLASS_NAME, "computeDo");
266     }
267 
268     private void computeFor(int firstIndex, int lastIndex) {
269         LOGGER.entering(CLASS_NAME, "computeFor");
270         DataFlowNode fExpr = null;
271         DataFlowNode fUpdate = null;
272         DataFlowNode fSt = null;
273         DataFlowNode fEnd = null;
274         boolean isUpdate = false;
275 
276         for (int i = firstIndex; i <= lastIndex; i++) {
277             StackObject so = this.braceStack.get(i);
278             DataFlowNode node = so.getDataFlowNode();
279 
280             if (so.getType() == NodeType.FOR_EXPR) {
281                 fExpr = node;
282             } else if (so.getType() == NodeType.FOR_UPDATE) {
283                 fUpdate = node;
284                 isUpdate = true;
285             } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
286                 fSt = node;
287             } else if (so.getType() == NodeType.FOR_END) {
288                 fEnd = node;
289             }
290         }
291         DataFlowNode end = fEnd.getFlow().get(fEnd.getIndex() + 1);
292 
293         DataFlowNode firstSt = fSt.getChildren().get(0);
294 
295         if (isUpdate) {
296             if (fSt.getIndex() != fEnd.getIndex()) {
297                 end.reverseParentPathsTo(fUpdate);
298                 fExpr.removePathToChild(fUpdate);
299                 fUpdate.addPathToChild(fExpr);
300                 fUpdate.removePathToChild(firstSt);
301                 fExpr.addPathToChild(firstSt);
302                 fExpr.addPathToChild(end);
303             } else {
304                 fSt.removePathToChild(end);
305                 fExpr.removePathToChild(fUpdate);
306                 fUpdate.addPathToChild(fExpr);
307                 fExpr.addPathToChild(fUpdate);
308                 fExpr.addPathToChild(end);
309             }
310         } else {
311             if (fSt.getIndex() != fEnd.getIndex()) {
312                 end.reverseParentPathsTo(fExpr);
313                 fExpr.addPathToChild(end);
314             }
315         }
316         LOGGER.exiting(CLASS_NAME, "computeFor");
317     }
318 
319     private void computeSwitch(int firstIndex, int lastIndex) {
320         LOGGER.entering(CLASS_NAME, "computeSwitch");
321 
322         int diff = lastIndex - firstIndex;
323         boolean defaultStatement = false;
324 
325         DataFlowNode sStart = this.braceStack.get(firstIndex).getDataFlowNode();
326         DataFlowNode sEnd = this.braceStack.get(lastIndex).getDataFlowNode();
327         DataFlowNode end = sEnd.getChildren().get(0);
328 
329         if (LOGGER.isLoggable(Level.FINE)) {
330             LOGGER.fine("Stack(sStart)=>" + sStart + ",Stack(sEnd)=>" + sEnd + ",end=>" + end);
331         }
332 
333         for (int i = 0; i < diff - 2; i++) {
334             StackObject so = this.braceStack.get(firstIndex + 2 + i);
335             DataFlowNode node = so.getDataFlowNode();
336 
337             if (LOGGER.isLoggable(Level.FINE)) {
338                 LOGGER.fine("so(" + (firstIndex + 2 + i) + ")=>" + so + " has  dfn=>" + node + " with first child =>"
339                         + node.getChildren().get(0));
340             }
341             sStart.addPathToChild(node.getChildren().get(0));
342 
343             if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT) {
344                 defaultStatement = true;
345             }
346         }
347 
348         if (!defaultStatement) {
349             sStart.addPathToChild(end);
350         }
351         LOGGER.exiting(CLASS_NAME, "computeSwitch");
352     }
353 
354     private void computeWhile(int first, int last) {
355         LOGGER.entering(CLASS_NAME, "computeWhile with first and last of" + first + "," + last);
356         DataFlowNode wStart = this.braceStack.get(first).getDataFlowNode();
357         DataFlowNode wEnd = this.braceStack.get(last).getDataFlowNode();
358 
359         DataFlowNode end = wEnd.getFlow().get(wEnd.getIndex() + 1);
360 
361         if (wStart.getIndex() != wEnd.getIndex()) {
362             end.reverseParentPathsTo(wStart);
363             wStart.addPathToChild(end);
364         }
365         LOGGER.exiting(CLASS_NAME, "computeWhile");
366     }
367 
368     private void computeIf(int first, int second, int last) {
369         LOGGER.entering(CLASS_NAME, "computeIf(3)", first + "," + second + "," + last);
370         DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
371         DataFlowNode ifEnd = this.braceStack.get(second).getDataFlowNode();
372         DataFlowNode elseEnd = this.braceStack.get(last).getDataFlowNode();
373 
374         DataFlowNode elseStart = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
375         DataFlowNode end = elseEnd.getFlow().get(elseEnd.getIndex() + 1);
376 
377         LOGGER.log(Level.FINEST, "If ifstart={0}, ifEnd={1}, elseEnd={2}, elseStart={3}, end={4}", new Object[] {
378                 ifStart, ifEnd, elseEnd, elseStart, end });
379 
380         // if if-statement and else-statement contains statements or expressions
381         if (ifStart.getIndex() != ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
382             elseStart.reverseParentPathsTo(end);
383             ifStart.addPathToChild(elseStart);
384         }
385         // if only if-statement contains no expressions
386         else if (ifStart.getIndex() == ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
387             ifStart.addPathToChild(end);
388         }
389         // if only else-statement contains no expressions
390         else if (ifEnd.getIndex() == elseEnd.getIndex() && ifStart.getIndex() != ifEnd.getIndex()) {
391             ifStart.addPathToChild(end);
392         }
393         LOGGER.exiting(CLASS_NAME, "computeIf(3)");
394     }
395 
396     private void computeIf(int first, int last) {
397         LOGGER.entering(CLASS_NAME, "computeIf(2)");
398         DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
399         DataFlowNode ifEnd = this.braceStack.get(last).getDataFlowNode();
400 
401         // only if the if-statement contains another Statement or Expression
402         if (ifStart.getIndex() != ifEnd.getIndex()) {
403             DataFlowNode end = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
404             ifStart.addPathToChild(end);
405         }
406         LOGGER.exiting(CLASS_NAME, "computeIf(2)");
407     }
408 
409     /**
410      * 
411      * @return formatted dump of the StackList
412      */
413     private static String dump(String description, List<StackObject> stackList) {
414         StringBuilder stringDump = new StringBuilder("Stack List (");
415         stringDump.append(description).append(") ListDump:\n");
416         for (StackObject stackObject : stackList) {
417             stringDump.append('\n').append(stackObject.toString());
418         }
419         return stringDump.toString();
420     }
421 
422 }