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
    8   import net.sourceforge.pmd.lang.DataFlowHandler;
    9   import net.sourceforge.pmd.lang.ast.Node;
    10
    11  /**
    12   * @author raik
    13   *         Links data flow nodes to each other.
    14   */
    15  public class Linker {
    16
    17      private final DataFlowHandler dataFlowHandler;
    18      private List<StackObject> braceStack;
    19      private List<StackObject> continueBreakReturnStack;
    20
    21      public Linker(DataFlowHandler dataFlowHandler, List<StackObject> braceStack, List<StackObject> continueBreakReturnStack) {
    22  	this.dataFlowHandler = dataFlowHandler;
    23  	this.braceStack = braceStack;
    24  	this.continueBreakReturnStack = continueBreakReturnStack;
    25      }
    26
    27      /**
    28       * Creates all the links between the data flow nodes.
    29       */
    30      public void computePaths() throws LinkerException, SequenceException {
    31  	// Returns true if there are more sequences, computes the first and
    32  	// the last index of the sequence.
    33  	SequenceChecker sc = new SequenceChecker(braceStack);
    34  	while (!sc.run()) {
    35  	    if (sc.getFirstIndex() < 0 || sc.getLastIndex() < 0) {
    36  		throw new SequenceException("computePaths(): return index <  0");
    37  	    }
    38
    39  	    StackObject firstStackObject = braceStack.get(sc.getFirstIndex());
    40
    41  	    switch (firstStackObject.getType()) {
    42  	    case NodeType.IF_EXPR:
    43  		int x = sc.getLastIndex() - sc.getFirstIndex();
    44  		if (x == 2) {
    45  		    this.computeIf(sc.getFirstIndex(), sc.getFirstIndex() + 1, sc.getLastIndex());
    46  		} else if (x == 1) {
    47  		    this.computeIf(sc.getFirstIndex(), sc.getLastIndex());
    48  		} else {
    49  		    System.out.println("Error - computePaths 1");
    50  		}
    51  		break;
    52
    53  	    case NodeType.WHILE_EXPR:
    54  		this.computeWhile(sc.getFirstIndex(), sc.getLastIndex());
    55  		break;
    56
    57  	    case NodeType.SWITCH_START:
    58  		this.computeSwitch(sc.getFirstIndex(), sc.getLastIndex());
    59  		break;
    60
    61  	    case NodeType.FOR_INIT:
    62  	    case NodeType.FOR_EXPR:
    63  	    case NodeType.FOR_UPDATE:
    64  	    case NodeType.FOR_BEFORE_FIRST_STATEMENT:
    65  		this.computeFor(sc.getFirstIndex(), sc.getLastIndex());
    66  		break;
    67
    68  	    case NodeType.DO_BEFORE_FIRST_STATEMENT:
    69  		this.computeDo(sc.getFirstIndex(), sc.getLastIndex());
    70  		break;
    71
    72  	    default:
    73  	    }
    74
    75  	    for (int y = sc.getLastIndex(); y >= sc.getFirstIndex(); y--) {
    76  		braceStack.remove(y);
    77  	    }
    78  	}
    79
    80  	while (!continueBreakReturnStack.isEmpty()) {
    81  	    StackObject stackObject = continueBreakReturnStack.get(0);
    82  	    DataFlowNode node = stackObject.getDataFlowNode();
    83
    84  	    switch (stackObject.getType()) {
    85  	    case NodeType.THROW_STATEMENT:
    86  		// do the same like a return
    87  	    case NodeType.RETURN_STATEMENT:
    88  		// remove all children (should contain only one child)
    89  		node.removePathToChild(node.getChildren().get(0));
    90  		DataFlowNode lastNode = node.getFlow().get(node.getFlow().size() - 1);
    91  		node.addPathToChild(lastNode);
    92  		continueBreakReturnStack.remove(0);
    93  		break;
    94  	    case NodeType.BREAK_STATEMENT:
    95  		DataFlowNode last = getNodeToBreakStatement(node);
    96  		node.removePathToChild(node.getChildren().get(0));
    97  		node.addPathToChild(last);
    98  		continueBreakReturnStack.remove(0);
    99  		break;
    100
    101 	    case NodeType.CONTINUE_STATEMENT:
    102 		//List cList = node.getFlow();
    103 		/* traverse up the tree and find the first loop start node
    104 		 */
    105 		/*
    106 		                               for(int i = cList.indexOf(node)-1;i>=0;i--) {
    107 		                                   IDataFlowNode n = (IDataFlowNode)cList.get(i);
    108
    109 		                                   if(n.isType(NodeType.FOR_UPDATE) ||
    110 		                                               n.isType(NodeType.FOR_EXPR) ||
    111 		                                               n.isType(NodeType.WHILE_EXPR)) {
    112 		*/
    113 		/*
    114 		 * while(..) {
    115 		 *              while(...) {
    116 		 *                      ...
    117 		 *              }
    118 		 *              continue;
    119 		 * }
    120 		 *
    121 		 * Without this Expression he continues the second
    122 		 * WHILE loop. The continue statement and the while loop
    123 		 * have to be in different scopes.
    124 		 *
    125 		 * TODO An error occurs if "continue" is even nested in
    126 		 * scopes other than local loop scopes, like "if".
    127 		 * The result is, that the data flow isn't build right
    128 		 * and the pathfinder runs in invinity loop.
    129 		 * */
    130 		/*                                     if(n.getNode().getScope().equals(node.getNode().getScope())) {
    131 		                                               System.err.println("equals");
    132 		                                               continue;
    133 		                                       }
    134 		                                       else {
    135 		                                               System.err.println("don't equals");
    136 		                                       }
    137
    138 		                                               //remove all children (should contain only one child)
    139 		                                       node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
    140
    141 		                                       node.addPathToChild(n);
    142 		                                       cbrStack.remove(0);
    143 		                                       break;
    144
    145 		                                   }else if(n.isType(NodeType.DO_BEFOR_FIRST_STATEMENT)) {
    146
    147 		                                       IDataFlowNode inode = (IDataFlowNode)n.getFlow().get(n.getIndex()1);
    148
    149 		                                       for(int j=0;j<inode.getParents().size();j) {
    150 		                                               IDataFlowNode parent = (IDataFlowNode)inode.getParents().get(j);
    151
    152 		                                               if(parent.isType(NodeType.DO_EXPR)) {
    153 		                                                       node.removePathToChild((IDataFlowNode)node.getChildren().get(0));
    154 		                                               node.addPathToChild(parent);
    155
    156 		                                               cbrStack.remove(0);
    157 		                                                       break;
    158 		                                               }
    159 		                                       }
    160 		                                       break;
    161 		                                   }
    162 		                               }
    163 		*/
    164 		continueBreakReturnStack.remove(0); // delete this statement if you uncomment the stuff above
    165 		break;
    166 		default:
    167 		    // Do nothing
    168 		    break;
    169 	    }
    170 	}
    171     }
    172
    173     private DataFlowNode getNodeToBreakStatement(DataFlowNode node) {
    174 	// What about breaks to labels above if statements?
    175 	List<DataFlowNode> bList = node.getFlow();
    176 	int findEnds = 1; // ignore ends of other for's while's etc.
    177
    178 	// find out index of the node where the path goes to after the break
    179 	int index = bList.indexOf(node);
    180 	for (; index < bList.size() - 2; index++) {
    181 	    DataFlowNode n = bList.get(index);
    182 	    if (n.isType(NodeType.DO_EXPR) || n.isType(NodeType.FOR_INIT) || n.isType(NodeType.WHILE_EXPR)
    183 		    || n.isType(NodeType.SWITCH_START)) {
    184 		findEnds++;
    185 	    }
    186 	    if (n.isType(NodeType.WHILE_LAST_STATEMENT) || n.isType(NodeType.SWITCH_END) || n.isType(NodeType.FOR_END)
    187 		    || n.isType(NodeType.DO_EXPR)) {
    188 		if (findEnds > 1) {
    189 		    // thats not the right node
    190 		    findEnds--;
    191 		} else {
    192 		    break;
    193 		}
    194 	    }
    195
    196 	    if (n.isType(NodeType.LABEL_LAST_STATEMENT)) {
    197 		Node parentNode = n.getNode().getFirstParentOfType(dataFlowHandler.getLabelStatementNodeClass());
    198 		if (parentNode == null) {
    199 		    break;
    200 		} else {
    201 		    String label = node.getNode().getImage();
    202 		    if (label == null || label.equals(parentNode.getImage())) {
    203 			node.removePathToChild(node.getChildren().get(0));
    204 			DataFlowNode last = bList.get(index + 1);
    205 			node.addPathToChild(last);
    206 			break;
    207 		    }
    208 		}
    209 	    }
    210 	}
    211 	return node.getFlow().get(index + 1);
    212     }
    213
    214     private void computeDo(int first, int last) {
    215 	DataFlowNode doSt = this.braceStack.get(first).getDataFlowNode();
    216 	DataFlowNode doExpr = this.braceStack.get(last).getDataFlowNode();
    217 	DataFlowNode doFirst = doSt.getFlow().get(doSt.getIndex() + 1);
    218 	if (doFirst.getIndex() != doExpr.getIndex()) {
    219 	    doExpr.addPathToChild(doFirst);
    220 	}
    221     }
    222
    223     private void computeFor(int firstIndex, int lastIndex) {
    224 	DataFlowNode fExpr = null;
    225 	DataFlowNode fUpdate = null;
    226 	DataFlowNode fSt = null;
    227 	DataFlowNode fEnd = null;
    228 	boolean isUpdate = false;
    229
    230 	for (int i = firstIndex; i <= lastIndex; i++) {
    231 	    StackObject so = this.braceStack.get(i);
    232 	    DataFlowNode node = so.getDataFlowNode();
    233
    234 	    if (so.getType() == NodeType.FOR_EXPR) {
    235 		fExpr = node;
    236 	    } else if (so.getType() == NodeType.FOR_UPDATE) {
    237 		fUpdate = node;
    238 		isUpdate = true;
    239 	    } else if (so.getType() == NodeType.FOR_BEFORE_FIRST_STATEMENT) {
    240 		fSt = node;
    241 	    } else if (so.getType() == NodeType.FOR_END) {
    242 		fEnd = node;
    243 	    }
    244 	}
    245 	DataFlowNode end = fEnd.getFlow().get(fEnd.getIndex() + 1);
    246
    247 	DataFlowNode firstSt = fSt.getChildren().get(0);
    248
    249 	if (isUpdate) {
    250 	    if (fSt.getIndex() != fEnd.getIndex()) {
    251 		end.reverseParentPathsTo(fUpdate);
    252 		fExpr.removePathToChild(fUpdate);
    253 		fUpdate.addPathToChild(fExpr);
    254 		fUpdate.removePathToChild(firstSt);
    255 		fExpr.addPathToChild(firstSt);
    256 		fExpr.addPathToChild(end);
    257 	    } else {
    258 		fSt.removePathToChild(end);
    259 		fExpr.removePathToChild(fUpdate);
    260 		fUpdate.addPathToChild(fExpr);
    261 		fExpr.addPathToChild(fUpdate);
    262 		fExpr.addPathToChild(end);
    263 	    }
    264 	} else {
    265 	    if (fSt.getIndex() != fEnd.getIndex()) {
    266 		end.reverseParentPathsTo(fExpr);
    267 		fExpr.addPathToChild(end);
    268 	    }
    269 	}
    270     }
    271
    272     private void computeSwitch(int firstIndex, int lastIndex) {
    273
    274 	int diff = lastIndex - firstIndex;
    275 	boolean defaultStatement = false;
    276
    277 	DataFlowNode sStart = this.braceStack.get(firstIndex).getDataFlowNode();
    278 	DataFlowNode sEnd = this.braceStack.get(lastIndex).getDataFlowNode();
    279 	DataFlowNode end = sEnd.getChildren().get(0);
    280
    281 	for (int i = 0; i < diff - 2; i++) {
    282 	    StackObject so = this.braceStack.get(firstIndex + 2 + i);
    283 	    DataFlowNode node = so.getDataFlowNode();
    284
    285 	    sStart.addPathToChild(node.getChildren().get(0));
    286
    287 	    if (so.getType() == NodeType.SWITCH_LAST_DEFAULT_STATEMENT) {
    288 		defaultStatement = true;
    289 	    }
    290 	}
    291
    292 	if (!defaultStatement) {
    293 	    sStart.addPathToChild(end);
    294 	}
    295     }
    296
    297     private void computeWhile(int first, int last) {
    298 	DataFlowNode wStart = this.braceStack.get(first).getDataFlowNode();
    299 	DataFlowNode wEnd = this.braceStack.get(last).getDataFlowNode();
    300
    301 	DataFlowNode end = wEnd.getFlow().get(wEnd.getIndex() + 1);
    302
    303 	if (wStart.getIndex() != wEnd.getIndex()) {
    304 	    end.reverseParentPathsTo(wStart);
    305 	    wStart.addPathToChild(end);
    306 	}
    307     }
    308
    309     private void computeIf(int first, int second, int last) {
    310 	DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
    311 	DataFlowNode ifEnd = this.braceStack.get(second).getDataFlowNode();
    312 	DataFlowNode elseEnd = this.braceStack.get(last).getDataFlowNode();
    313
    314 	DataFlowNode elseStart = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
    315 	DataFlowNode end = elseEnd.getFlow().get(elseEnd.getIndex() + 1);
    316
    317 	// if if-statement and else-statement contains statements or expressions
    318 	if (ifStart.getIndex() != ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
    319 	    elseStart.reverseParentPathsTo(end);
    320 	    ifStart.addPathToChild(elseStart);
    321 	}
    322 	// if only if-statement contains no expressions
    323 	else if (ifStart.getIndex() == ifEnd.getIndex() && ifEnd.getIndex() != elseEnd.getIndex()) {
    324 	    ifStart.addPathToChild(end);
    325 	}
    326 	// if only else-statement contains no expressions
    327 	else if (ifEnd.getIndex() == elseEnd.getIndex() && ifStart.getIndex() != ifEnd.getIndex()) {
    328 	    ifStart.addPathToChild(end);
    329 	}
    330     }
    331
    332     private void computeIf(int first, int last) {
    333 	DataFlowNode ifStart = this.braceStack.get(first).getDataFlowNode();
    334 	DataFlowNode ifEnd = this.braceStack.get(last).getDataFlowNode();
    335
    336 	// only if the if-statement contains another Statement or Expression
    337 	if (ifStart.getIndex() != ifEnd.getIndex()) {
    338 	    DataFlowNode end = ifEnd.getFlow().get(ifEnd.getIndex() + 1);
    339 	    ifStart.addPathToChild(end);
    340 	}
    341     }
    342 }