Linker


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 }
340
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags