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.Logger;
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 public class SequenceChecker {
26 private final static Logger LOGGER = Logger.getLogger(SequenceChecker.class.getName());
27
28
29
30
31 private static class Status {
32
33 public static final int ROOT = -1;
34
35 private List<Status> nextSteps = new ArrayList<Status>();
36
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
56
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
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
163
164 public SequenceChecker(List<StackObject> bracesList) {
165 this.aktStatus = root;
166 this.bracesList = bracesList;
167 }
168
169
170
171
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
181
182
183
184
185
186
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
197 LOGGER.finest("DataFlowNode @ line "+ so.getDataFlowNode().getLine() + " and index="
198 + so.getDataFlowNode().getIndex()
199 );
200
201
202 aktStatus = this.aktStatus.step(so.getType());
203 LOGGER.finest("Transition aktStatus="+aktStatus);
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 {
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 {
227 if (aktStatus.isLastStep() && !aktStatus.hasMoreSteps()) {
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 }