001: /*
002: * Created on 12.07.2004
003: */
004: package net.sourceforge.pmd.dfa;
005:
006: import java.util.List;
007:
008: import net.sourceforge.pmd.ast.ASTLabeledStatement;
009: import net.sourceforge.pmd.ast.SimpleNode;
010:
011: /**
012: * @author raik
013: * Links data flow nodes to each other.
014: */
015: public class Linker {
016:
017: private List braceStack;
018: private List continueBreakReturnStack;
019:
020: public Linker(List braceStack, List continueBreakReturnStack) {
021: this .braceStack = braceStack;
022: this .continueBreakReturnStack = continueBreakReturnStack;
023: }
024:
025: /**
026: * Creates all the links between the data flow nodes.
027: */
028: public void computePaths() throws LinkerException,
029: SequenceException {
030: // Returns true if there are more sequences, computes the first and
031: // the last index of the sequence.
032: SequenceChecker sc = new SequenceChecker(braceStack);
033: while (!sc.run()) {
034: if (sc.getFirstIndex() < 0 || sc.getLastIndex() < 0) {
035: throw new SequenceException(
036: "computePaths(): return index < 0");
037: }
038:
039: StackObject firstStackObject = (StackObject) braceStack
040: .get(sc.getFirstIndex());
041:
042: switch (firstStackObject.getType()) {
043: case NodeType.IF_EXPR:
044: int x = sc.getLastIndex() - sc.getFirstIndex();
045: if (x == 2) {
046: this .computeIf(sc.getFirstIndex(), sc
047: .getFirstIndex() + 1, sc.getLastIndex());
048: } else if (x == 1) {
049: this .computeIf(sc.getFirstIndex(), sc
050: .getLastIndex());
051: } else {
052: System.out.println("Error - computePaths 1");
053: }
054: break;
055:
056: case NodeType.WHILE_EXPR:
057: this
058: .computeWhile(sc.getFirstIndex(), sc
059: .getLastIndex());
060: break;
061:
062: case NodeType.SWITCH_START:
063: this .computeSwitch(sc.getFirstIndex(), sc
064: .getLastIndex());
065: break;
066:
067: case NodeType.FOR_INIT:
068: case NodeType.FOR_EXPR:
069: case NodeType.FOR_UPDATE:
070: case NodeType.FOR_BEFORE_FIRST_STATEMENT:
071: this .computeFor(sc.getFirstIndex(), sc.getLastIndex());
072: break;
073:
074: case NodeType.DO_BEFORE_FIRST_STATEMENT:
075: this .computeDo(sc.getFirstIndex(), sc.getLastIndex());
076: break;
077:
078: default:
079: }
080:
081: for (int y = sc.getLastIndex(); y >= sc.getFirstIndex(); y--) {
082: braceStack.remove(y);
083: }
084: }
085:
086: while (!continueBreakReturnStack.isEmpty()) {
087: StackObject stackObject = (StackObject) continueBreakReturnStack
088: .get(0);
089: IDataFlowNode node = stackObject.getDataFlowNode();
090:
091: switch (stackObject.getType()) {
092: case NodeType.THROW_STATEMENT:
093: // do the same like a return
094: case NodeType.RETURN_STATEMENT:
095: // remove all children (should contain only one child)
096: node.removePathToChild(node.getChildren().get(0));
097: IDataFlowNode lastNode = node.getFlow().get(
098: node.getFlow().size() - 1);
099: node.addPathToChild(lastNode);
100: continueBreakReturnStack.remove(0);
101: break;
102: case NodeType.BREAK_STATEMENT:
103: IDataFlowNode last = getNodeToBreakStatement(node);
104: node.removePathToChild(node.getChildren().get(0));
105: node.addPathToChild(last);
106: continueBreakReturnStack.remove(0);
107: break;
108:
109: case NodeType.CONTINUE_STATEMENT:
110: //List cList = node.getFlow();
111: /* traverse up the tree and find the first loop start node
112: */
113: /*
114: for(int i = cList.indexOf(node)-1;i>=0;i--) {
115: IDataFlowNode n = (IDataFlowNode)cList.get(i);
116:
117: if(n.isType(NodeType.FOR_UPDATE) ||
118: n.isType(NodeType.FOR_EXPR) ||
119: n.isType(NodeType.WHILE_EXPR)) {
120: */
121: /*
122: * while(..) {
123: * while(...) {
124: * ...
125: * }
126: * continue;
127: * }
128: *
129: * Without this Expression he continues the second
130: * WHILE loop. The continue statement and the while loop
131: * have to be in different scopes.
132: *
133: * TODO An error occurs if "continue" is even nested in
134: * scopes other than local loop scopes, like "if".
135: * The result is, that the data flow isn't build right
136: * and the pathfinder runs in invinity loop.
137: * */
138: /* if(n.getSimpleNode().getScope().equals(node.getSimpleNode().getScope())) {
139: System.err.println("equals");
140: continue;
141: }
142: else {
143: System.err.println("don't equals");
144: }
145:
146: //remove all children (should contain only one child)
147: node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
148:
149: node.addPathToChild(n);
150: cbrStack.remove(0);
151: break;
152:
153: }else if(n.isType(NodeType.DO_BEFOR_FIRST_STATEMENT)) {
154:
155: IDataFlowNode inode = (IDataFlowNode)n.getFlow().get(n.getIndex()1);
156:
157: for(int j=0;j<inode.getParents().size();j) {
158: IDataFlowNode parent = (IDataFlowNode)inode.getParents().get(j);
159:
160: if(parent.isType(NodeType.DO_EXPR)) {
161: node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
162: node.addPathToChild(parent);
163:
164: cbrStack.remove(0);
165: break;
166: }
167: }
168: break;
169: }
170: }
171: */
172: continueBreakReturnStack.remove(0); // delete this statement if you uncomment the stuff above
173: }
174: }
175: }
176:
177: private IDataFlowNode getNodeToBreakStatement(IDataFlowNode node) {
178: // What about breaks to labels above if statements?
179: List bList = node.getFlow();
180: int findEnds = 1; // ignore ends of other for's while's etc.
181:
182: // find out index of the node where the path goes to after the break
183: int index = bList.indexOf(node);
184: for (; index < bList.size() - 2; index++) {
185: IDataFlowNode n = (IDataFlowNode) bList.get(index);
186: if (n.isType(NodeType.DO_EXPR)
187: || n.isType(NodeType.FOR_INIT)
188: || n.isType(NodeType.WHILE_EXPR)
189: || n.isType(NodeType.SWITCH_START)) {
190: findEnds++;
191: }
192: if (n.isType(NodeType.WHILE_LAST_STATEMENT)
193: || n.isType(NodeType.SWITCH_END)
194: || n.isType(NodeType.FOR_END)
195: || n.isType(NodeType.DO_EXPR)) {
196: if (findEnds > 1) {
197: // thats not the right node
198: findEnds--;
199: } else {
200: break;
201: }
202: }
203:
204: if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
205: SimpleNode parentNode = n
206: .getSimpleNode()
207: .getFirstParentOfType(ASTLabeledStatement.class);
208: if (parentNode == null) {
209: break;
210: } else {
211: String label = node.getSimpleNode().getImage();
212: if (label == null
213: || label.equals(parentNode.getImage())) {
214: node.removePathToChild(node.getChildren()
215: .get(0));
216: IDataFlowNode last = (IDataFlowNode) bList
217: .get(index + 1);
218: node.addPathToChild(last);
219: break;
220: }
221: }
222: }
223: }
224: return node.getFlow().get(index + 1);
225: }
226:
227: private void computeDo(int first, int last) {
228: IDataFlowNode doSt = ((StackObject) this .braceStack.get(first))
229: .getDataFlowNode();
230: IDataFlowNode doExpr = ((StackObject) this .braceStack.get(last))
231: .getDataFlowNode();
232: IDataFlowNode doFirst = doSt.getFlow().get(doSt.getIndex() + 1);
233: if (doFirst.getIndex() != doExpr.getIndex()) {
234: doExpr.addPathToChild(doFirst);
235: }
236: }
237:
238: private void computeFor(int firstIndex, int lastIndex) {
239: IDataFlowNode fExpr = null;
240: IDataFlowNode fUpdate = null;
241: IDataFlowNode fSt = null;
242: IDataFlowNode fEnd = null;
243: boolean isUpdate = false;
244:
245: for (int i = firstIndex; i <= lastIndex; i++) {
246: StackObject so = (StackObject) this .braceStack.get(i);
247: IDataFlowNode node = so.getDataFlowNode();
248:
249: if (so.getType() == NodeType.FOR_EXPR) {
250: fExpr = node;
251: } else if (so.getType() == NodeType.FOR_UPDATE) {
252: fUpdate = node;
253: isUpdate = true;
254: } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
255: fSt = node;
256: } else if (so.getType() == NodeType.FOR_END) {
257: fEnd = node;
258: }
259: }
260: IDataFlowNode end = fEnd.getFlow().get(fEnd.getIndex() + 1);
261:
262: IDataFlowNode firstSt = fSt.getChildren().get(0);
263:
264: if (isUpdate) {
265: if (fSt.getIndex() != fEnd.getIndex()) {
266: end.reverseParentPathsTo(fUpdate);
267: fExpr.removePathToChild(fUpdate);
268: fUpdate.addPathToChild(fExpr);
269: fUpdate.removePathToChild(firstSt);
270: fExpr.addPathToChild(firstSt);
271: fExpr.addPathToChild(end);
272: } else {
273: fSt.removePathToChild(end);
274: fExpr.removePathToChild(fUpdate);
275: fUpdate.addPathToChild(fExpr);
276: fExpr.addPathToChild(fUpdate);
277: fExpr.addPathToChild(end);
278: }
279: } else {
280: if (fSt.getIndex() != fEnd.getIndex()) {
281: end.reverseParentPathsTo(fExpr);
282: fExpr.addPathToChild(end);
283: }
284: }
285: }
286:
287: private void computeSwitch(int firstIndex, int lastIndex) {
288:
289: int diff = lastIndex - firstIndex;
290: boolean defaultStatement = false;
291:
292: IDataFlowNode sStart = ((StackObject) this .braceStack
293: .get(firstIndex)).getDataFlowNode();
294: IDataFlowNode sEnd = ((StackObject) this .braceStack
295: .get(lastIndex)).getDataFlowNode();
296: IDataFlowNode end = sEnd.getChildren().get(0);
297:
298: for (int i = 0; i < diff - 2; i++) {
299: StackObject so = (StackObject) this .braceStack
300: .get(firstIndex + 2 + i);
301: IDataFlowNode node = so.getDataFlowNode();
302:
303: sStart.addPathToChild(node.getChildren().get(0));
304:
305: if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT)
306: defaultStatement = true;
307: }
308:
309: if (!defaultStatement)
310: sStart.addPathToChild(end);
311: }
312:
313: private void computeWhile(int first, int last) {
314: IDataFlowNode wStart = ((StackObject) this .braceStack
315: .get(first)).getDataFlowNode();
316: IDataFlowNode wEnd = ((StackObject) this .braceStack.get(last))
317: .getDataFlowNode();
318:
319: IDataFlowNode end = wEnd.getFlow().get(wEnd.getIndex() + 1);
320:
321: if (wStart.getIndex() != wEnd.getIndex()) {
322: end.reverseParentPathsTo(wStart);
323: wStart.addPathToChild(end);
324: }
325: }
326:
327: private void computeIf(int first, int second, int last) {
328: IDataFlowNode ifStart = ((StackObject) this .braceStack
329: .get(first)).getDataFlowNode();
330: IDataFlowNode ifEnd = ((StackObject) this .braceStack
331: .get(second)).getDataFlowNode();
332: IDataFlowNode elseEnd = ((StackObject) this .braceStack
333: .get(last)).getDataFlowNode();
334:
335: IDataFlowNode elseStart = ifEnd.getFlow().get(
336: ifEnd.getIndex() + 1);
337: IDataFlowNode end = elseEnd.getFlow().get(
338: elseEnd.getIndex() + 1);
339:
340: // if if-statement and else-statement contains statements or expressions
341: if (ifStart.getIndex() != ifEnd.getIndex()
342: && ifEnd.getIndex() != elseEnd.getIndex()) {
343: elseStart.reverseParentPathsTo(end);
344: ifStart.addPathToChild(elseStart);
345: }
346: // if only if-statement contains no expressions
347: else if (ifStart.getIndex() == ifEnd.getIndex()
348: && ifEnd.getIndex() != elseEnd.getIndex()) {
349: ifStart.addPathToChild(end);
350: }
351: // if only else-statement contains no expressions
352: else if (ifEnd.getIndex() == elseEnd.getIndex()
353: && ifStart.getIndex() != ifEnd.getIndex()) {
354: ifStart.addPathToChild(end);
355: }
356: }
357:
358: private void computeIf(int first, int last) {
359: IDataFlowNode ifStart = ((StackObject) this .braceStack
360: .get(first)).getDataFlowNode();
361: IDataFlowNode ifEnd = ((StackObject) this .braceStack.get(last))
362: .getDataFlowNode();
363:
364: // only if the if-statement contains another Statement or Expression
365: if (ifStart.getIndex() != ifEnd.getIndex()) {
366: IDataFlowNode end = ifEnd.getFlow().get(
367: ifEnd.getIndex() + 1);
368: ifStart.addPathToChild(end);
369: }
370: }
371: }
|