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 }