1
2
3
4 package net.sourceforge.pmd.lang.dfa;
5
6 import java.util.ArrayList;
7 import java.util.List;
8 import java.util.logging.Level;
9 import java.util.logging.Logger;
10
11
12
13
14
15
16
17
18
19
20
21 public class SequenceChecker {
22 private final static Logger LOGGER = Logger.getLogger(SequenceChecker.class.getName());
23
24
25
26
27 private static class Status {
28
29 public static final int ROOT = -1;
30
31 private List<Status> nextSteps = new ArrayList<Status>();
32
33 private int type;
34 private boolean lastStep;
35
36 public Status(int type) {
37 this(type, false);
38 }
39
40 public Status(int type, boolean lastStep) {
41 this.type = type;
42 this.lastStep = lastStep;
43 }
44
45 public void addStep(Status type) {
46 nextSteps.add(type);
47 }
48
49
50
51
52
53
54
55 public Status step(int type) {
56 for (int i = 0; i < this.nextSteps.size(); i++) {
57 if (type == nextSteps.get(i).type) {
58 return nextSteps.get(i);
59 }
60 }
61 return null;
62 }
63
64 public boolean isLastStep() {
65 return this.lastStep;
66 }
67
68 public boolean hasMoreSteps() {
69 return this.nextSteps.size() > 1;
70 }
71
72 public String toString() {
73 return "NodeType=" + NodeType.stringFromType(type) + "(" + type + "), lastStep=" + lastStep;
74 }
75 }
76
77 private static Status root;
78
79
80
81
82 static {
83 root = new Status(Status.ROOT);
84 Status ifNode = new Status(NodeType.IF_EXPR);
85 Status ifSt = new Status(NodeType.IF_LAST_STATEMENT);
86 Status ifStWithoutElse = new Status(NodeType.IF_LAST_STATEMENT_WITHOUT_ELSE, true);
87 Status elseSt = new Status(NodeType.ELSE_LAST_STATEMENT, true);
88 Status whileNode = new Status(NodeType.WHILE_EXPR);
89 Status whileSt = new Status(NodeType.WHILE_LAST_STATEMENT, true);
90 Status switchNode = new Status(NodeType.SWITCH_START);
91 Status caseSt = new Status(NodeType.CASE_LAST_STATEMENT);
92 Status switchDefault = new Status(NodeType.SWITCH_LAST_DEFAULT_STATEMENT);
93 Status switchEnd = new Status(NodeType.SWITCH_END, true);
94
95 Status forInit = new Status(NodeType.FOR_INIT);
96 Status forExpr = new Status(NodeType.FOR_EXPR);
97 Status forUpdate = new Status(NodeType.FOR_UPDATE);
98 Status forSt = new Status(NodeType.FOR_BEFORE_FIRST_STATEMENT);
99 Status forEnd = new Status(NodeType.FOR_END, true);
100
101 Status doSt = new Status(NodeType.DO_BEFORE_FIRST_STATEMENT);
102 Status doExpr = new Status(NodeType.DO_EXPR, true);
103
104 Status labelNode = new Status(NodeType.LABEL_STATEMENT);
105 Status labelEnd = new Status(NodeType.LABEL_LAST_STATEMENT, true);
106
107 root.addStep(ifNode);
108 root.addStep(whileNode);
109 root.addStep(switchNode);
110 root.addStep(forInit);
111 root.addStep(forExpr);
112 root.addStep(forUpdate);
113 root.addStep(forSt);
114 root.addStep(doSt);
115 root.addStep(labelNode);
116
117 ifNode.addStep(ifSt);
118 ifNode.addStep(ifStWithoutElse);
119 ifSt.addStep(elseSt);
120 ifStWithoutElse.addStep(root);
121 elseSt.addStep(root);
122
123 labelNode.addStep(labelEnd);
124 labelEnd.addStep(root);
125
126 whileNode.addStep(whileSt);
127 whileSt.addStep(root);
128
129 switchNode.addStep(caseSt);
130 switchNode.addStep(switchDefault);
131 switchNode.addStep(switchEnd);
132 caseSt.addStep(caseSt);
133 caseSt.addStep(switchDefault);
134 caseSt.addStep(switchEnd);
135 switchDefault.addStep(switchEnd);
136 switchDefault.addStep(caseSt);
137 switchEnd.addStep(root);
138
139 forInit.addStep(forExpr);
140 forInit.addStep(forUpdate);
141 forInit.addStep(forSt);
142 forExpr.addStep(forUpdate);
143 forExpr.addStep(forSt);
144 forUpdate.addStep(forSt);
145 forSt.addStep(forEnd);
146 forEnd.addStep(root);
147
148 doSt.addStep(doExpr);
149 doExpr.addStep(root);
150 }
151
152 private Status aktStatus;
153 private List<StackObject> bracesList;
154
155 private int firstIndex = -1;
156 private int lastIndex = -1;
157
158
159
160
161 public SequenceChecker(List<StackObject> bracesList) {
162 this.aktStatus = root;
163 this.bracesList = bracesList;
164 }
165
166
167
168
169
170 public boolean run() {
171 LOGGER.entering(this.getClass().getCanonicalName(), "run");
172 this.aktStatus = root;
173 this.firstIndex = 0;
174 this.lastIndex = 0;
175 boolean lookAhead = false;
176
177
178
179
180
181
182
183
184
185 int maximumIterations = this.bracesList.size() * this.bracesList.size();
186 int l = -1;
187 for (int i = 0; i < this.bracesList.size(); i++) {
188 l++;
189 StackObject so = bracesList.get(i);
190 if (LOGGER.isLoggable(Level.FINEST)) {
191 LOGGER.finest("Processing bracesList(l,i)=(" + l + "," + i + ") of Type "
192 + NodeType.stringFromType(so.getType()) + " with State (aktStatus) = " + aktStatus);
193
194 LOGGER.finest("DataFlowNode @ line " + so.getDataFlowNode().getLine() + " and index="
195 + so.getDataFlowNode().getIndex());
196 }
197
198
199
200 aktStatus = this.aktStatus.step(so.getType());
201 if (LOGGER.isLoggable(Level.FINEST)) {
202 LOGGER.finest("Transition aktStatus=" + aktStatus);
203 }
204
205 if (aktStatus == null) {
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
213 else if (l > maximumIterations) {
214 if (LOGGER.isLoggable(Level.SEVERE)) {
215 LOGGER.severe("aktStatus is NULL: maximum Iterations exceeded, abort " + i);
216 }
217 LOGGER.exiting(this.getClass().getCanonicalName(), "run", false);
218 return false;
219 } else {
220 this.aktStatus = root;
221 this.firstIndex = i;
222 i--;
223 if (LOGGER.isLoggable(Level.FINEST)) {
224 LOGGER.finest("aktStatus is NULL: Restarting search continue i==" + i + ", firstIndex="
225 + this.firstIndex);
226 }
227 continue;
228 }
229 } else {
230
231 if (aktStatus.isLastStep() && !aktStatus.hasMoreSteps()) {
232
233 this.lastIndex = i;
234 if (LOGGER.isLoggable(Level.FINEST)) {
235 LOGGER.finest("aktStatus is NOT NULL: lastStep reached and no moreSteps - firstIndex="
236 + firstIndex + ", lastIndex=" + lastIndex);
237 }
238 LOGGER.exiting(this.getClass().getCanonicalName(), "run", false);
239 return false;
240 } else if (aktStatus.isLastStep() && aktStatus.hasMoreSteps()) {
241 lookAhead = true;
242 this.lastIndex = i;
243 LOGGER.finest("aktStatus is NOT NULL: set lookAhead on");
244 }
245 }
246 }
247 if (LOGGER.isLoggable(Level.FINEST)) {
248 LOGGER.finer("Completed search: firstIndex=" + firstIndex + ", lastIndex=" + lastIndex);
249 }
250 LOGGER.exiting(this.getClass().getCanonicalName(), "run", this.firstIndex == this.lastIndex);
251 return this.firstIndex == this.lastIndex;
252 }
253
254 public int getFirstIndex() {
255 return this.firstIndex;
256 }
257
258 public int getLastIndex() {
259 return this.lastIndex;
260 }
261
262 }