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.ArrayList;
7   import java.util.List;
8   import java.util.logging.Logger;
9   
10  
11  /**
12   * @author raik
13   *         <p/>
14   *         Computes the first sequence in a list.
15   *         <p/>
16   *         e.g.
17   *         IF_START			0
18   *         WHILE_EXPR		1
19   *         WHILE_END		2
20   *         IF_END			3
21   *         <p/>
22   *         The first sequence is WHILE_EXPR and WHILE_END. It returns always the
23   *         first inner nested scope.
24   */
25  public class SequenceChecker {
26      private final static Logger LOGGER = Logger.getLogger(SequenceChecker.class.getName());
27  
28      /*
29       * Element of logical structure of brace nodes.
30       * */
31      private static class Status {
32  
33  	public static final int ROOT = -1;
34  
35  	private List<Status> nextSteps = new ArrayList<Status>();
36          //NodeType
37  	private int type;
38  	private boolean lastStep;
39  
40  	public Status(int type) {
41  	    this(type, false);
42  	}
43  
44  	public Status(int type, boolean lastStep) {
45  	    this.type = type;
46  	    this.lastStep = lastStep;
47  	}
48  
49  	public void addStep(Status type) {
50  	    nextSteps.add(type);
51  	}
52  
53          /**
54           * 
55           * @param type candidate 
56           * @return valid Status or null if NodeType is not a valid transition NodeType 
57           */
58  	public Status step(int type) {
59  	    for (int i = 0; i < this.nextSteps.size(); i++) {
60  		if (type == nextSteps.get(i).type) {
61  		    return nextSteps.get(i);
62  		}
63  	    }
64  	    return null;
65  	}
66  
67  	public boolean isLastStep() {
68  	    return this.lastStep;
69  	}
70  
71  	public boolean hasMoreSteps() {
72  	    return this.nextSteps.size() > 1;
73  	}
74  
75  	public String toString() {
76  	 return "NodeType=" + NodeType.stringFromType(type) + "("+ type + "), lastStep=" + lastStep;
77  	}
78      }
79  
80      private static Status root;
81  
82      /**
83       * Create State transition map for the control structures
84       */
85      static { 
86  	root = new Status(Status.ROOT);
87  	Status ifNode = new Status(NodeType.IF_EXPR);
88  	Status ifSt = new Status(NodeType.IF_LAST_STATEMENT);
89  	Status ifStWithoutElse = new Status(NodeType.IF_LAST_STATEMENT_WITHOUT_ELSE, true);
90  	Status elseSt = new Status(NodeType.ELSE_LAST_STATEMENT, true);
91  	Status whileNode = new Status(NodeType.WHILE_EXPR);
92  	Status whileSt = new Status(NodeType.WHILE_LAST_STATEMENT, true);
93  	Status switchNode = new Status(NodeType.SWITCH_START);
94  	Status caseSt = new Status(NodeType.CASE_LAST_STATEMENT);
95  	Status switchDefault = new Status(NodeType.SWITCH_LAST_DEFAULT_STATEMENT);
96  	Status switchEnd = new Status(NodeType.SWITCH_END, true);
97  
98  	Status forInit = new Status(NodeType.FOR_INIT);
99  	Status forExpr = new Status(NodeType.FOR_EXPR);
100 	Status forUpdate = new Status(NodeType.FOR_UPDATE);
101 	Status forSt = new Status(NodeType.FOR_BEFORE_FIRST_STATEMENT);
102 	Status forEnd = new Status(NodeType.FOR_END, true);
103 
104 	Status doSt = new Status(NodeType.DO_BEFORE_FIRST_STATEMENT);
105 	Status doExpr = new Status(NodeType.DO_EXPR, true);
106 
107 	Status labelNode = new Status(NodeType.LABEL_STATEMENT);
108 	Status labelEnd = new Status(NodeType.LABEL_LAST_STATEMENT, true);
109 
110 	root.addStep(ifNode);
111 	root.addStep(whileNode);
112 	root.addStep(switchNode);
113 	root.addStep(forInit);
114 	root.addStep(forExpr);
115 	root.addStep(forUpdate);
116 	root.addStep(forSt);
117 	root.addStep(doSt);
118 	root.addStep(labelNode);
119 
120 	ifNode.addStep(ifSt);
121 	ifNode.addStep(ifStWithoutElse);
122 	ifSt.addStep(elseSt);
123 	ifStWithoutElse.addStep(root);
124 	elseSt.addStep(root);
125 
126 	labelNode.addStep(labelEnd);
127 	labelEnd.addStep(root);
128 
129 	whileNode.addStep(whileSt);
130 	whileSt.addStep(root);
131 
132 	switchNode.addStep(caseSt);
133 	switchNode.addStep(switchDefault);
134 	switchNode.addStep(switchEnd);
135 	caseSt.addStep(caseSt);
136 	caseSt.addStep(switchDefault);
137 	caseSt.addStep(switchEnd);
138 	switchDefault.addStep(switchEnd);
139 	switchDefault.addStep(caseSt);
140 	switchEnd.addStep(root);
141 
142 	forInit.addStep(forExpr);
143 	forInit.addStep(forUpdate);
144 	forInit.addStep(forSt);
145 	forExpr.addStep(forUpdate);
146 	forExpr.addStep(forSt);
147 	forUpdate.addStep(forSt);
148 	forSt.addStep(forEnd);
149 	forEnd.addStep(root);
150 
151 	doSt.addStep(doExpr);
152 	doExpr.addStep(root);
153     }
154 
155     private Status aktStatus;
156     private List<StackObject> bracesList;
157 
158     private int firstIndex = -1;
159     private int lastIndex = -1;
160 
161     /*
162      * Defines the logical structure.
163      * */
164     public SequenceChecker(List<StackObject> bracesList) {
165 	this.aktStatus = root;
166 	this.bracesList = bracesList;
167     }
168 
169     /**
170      * Finds the first innermost sequence e.g IFStart & IFEnd. 
171      * If the list has been exhausted (firstIndex==lastIndex) the method returns true.
172      */
173     public boolean run() {
174         LOGGER.entering(this.getClass().getCanonicalName(),"run");
175 	this.aktStatus = root;
176 	this.firstIndex = 0;
177 	this.lastIndex = 0;
178 	boolean lookAhead = false;
179 
180         /*Walk through the bracesList attempting to identify the first contiguous graph of Nodes 
181          * from the initial Status to a final Status. 
182          * 
183          *There are 2 loop indexes:-
184          * i which ranges through the bracesList: this may be reset 
185          * l serves as a control to cope with invalid lists of StackObjects,
186          * preventing infinite loops within the SequenceChecker. 
187          */
188         int maximumIterations = this.bracesList.size() * this.bracesList.size() ;
189 	for (int i = 0, l = 0; i < this.bracesList.size(); l++, i++) {
190 	    StackObject so = bracesList.get(i);
191             LOGGER.finest("Processing bracesList(l,i)=("+l+","+i+") of Type "
192                           + NodeType.stringFromType(so.getType()) + " with State (aktStatus) = " 
193                           + aktStatus
194                          );
195 
196             //LOGGER.finest("StackObject of Type="+so.getType());
197             LOGGER.finest("DataFlowNode @ line "+ so.getDataFlowNode().getLine() + " and index=" 
198                            + so.getDataFlowNode().getIndex()
199                          );
200 
201             //Attempt to get to this StackObject's NodeType from the current State
202 	    aktStatus = this.aktStatus.step(so.getType());
203             LOGGER.finest("Transition aktStatus="+aktStatus);
204 
205 	    if (aktStatus == null) { // Not a valid Node from the current State
206 		if (lookAhead) {
207 		    this.lastIndex = i - 1;
208                     LOGGER.finer("aktStatus is NULL (lookAhead): Invalid transition");
209                     LOGGER.exiting(this.getClass().getCanonicalName(),"run", false);
210 		    return false;
211 		}
212                 //Cope with incorrect bracesList contents
213                 else if (l >  maximumIterations )
214                 {
215                   LOGGER.severe("aktStatus is NULL: maximum Iterations exceeded, abort "+i);
216                   LOGGER.exiting(this.getClass().getCanonicalName(),"run", false);
217                   return false;
218                 }
219                 else {
220                   this.aktStatus = root;
221                   this.firstIndex = i;
222                   i--;
223                   LOGGER.finest("aktStatus is NULL: Restarting search continue i==" +i + ", firstIndex=" + this.firstIndex );
224                   continue;
225                 }
226 	    } else { // This NodeType _is_ a valid transition from the previous State
227 		if (aktStatus.isLastStep() && !aktStatus.hasMoreSteps()) { //Terminal State
228 		    this.lastIndex = i;
229                     LOGGER.finest("aktStatus is NOT NULL: lastStep reached and no moreSteps - firstIndex=" + firstIndex + ", lastIndex=" + lastIndex);
230                     LOGGER.exiting(this.getClass().getCanonicalName(),"run", false);
231 		    return false;
232 		} else if (aktStatus.isLastStep() && aktStatus.hasMoreSteps()) {
233 		    lookAhead = true;
234 		    this.lastIndex = i;
235                     LOGGER.finest("aktStatus is NOT NULL: set lookAhead on");
236 		}
237 	    }
238 	}
239         LOGGER.finer("Completed search: firstIndex=" + firstIndex + ", lastIndex=" + lastIndex);
240         LOGGER.exiting(this.getClass().getCanonicalName(),"run", this.firstIndex == this.lastIndex);
241 	return this.firstIndex == this.lastIndex;
242     }
243 
244     public int getFirstIndex() {
245 	return this.firstIndex;
246     }
247 
248     public int getLastIndex() {
249 	return this.lastIndex;
250     }
251 
252 }