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