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.Level;
9   import java.util.logging.Logger;
10  
11  /**
12   * @author raik
13   *         <p/>
14   *         Computes the first sequence in a list.
15   *         <p/>
16   *         e.g. IF_START 0 WHILE_EXPR 1 WHILE_END 2 IF_END 3
17   *         <p/>
18   *         The first sequence is WHILE_EXPR and WHILE_END. It returns always the
19   *         first inner nested scope.
20   */
21  public class SequenceChecker {
22      private final static Logger LOGGER = Logger.getLogger(SequenceChecker.class.getName());
23  
24      /*
25       * Element of logical structure of brace nodes.
26       */
27      private static class Status {
28  
29          public static final int ROOT = -1;
30  
31          private List<Status> nextSteps = new ArrayList<>();
32          // NodeType
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           * @param type candidate
52           * @return valid Status or null if NodeType is not a valid transition
53           *         NodeType
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       * Create State transition map for the control structures
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      * Defines the logical structure.
160      */
161     public SequenceChecker(List<StackObject> bracesList) {
162         this.aktStatus = root;
163         this.bracesList = bracesList;
164     }
165 
166     /**
167      * Finds the first innermost sequence e.g IFStart & IFEnd. If the list has
168      * been exhausted (firstIndex==lastIndex) the method returns true.
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          * Walk through the bracesList attempting to identify the first
179          * contiguous graph of Nodes from the initial Status to a final Status.
180          * 
181          * There are 2 loop indexes:- i which ranges through the bracesList:
182          * this may be reset l serves as a control to cope with invalid lists of
183          * StackObjects, preventing infinite loops within the SequenceChecker.
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                 // LOGGER.finest("StackObject of Type="+so.getType());
194                 LOGGER.finest("DataFlowNode @ line " + so.getDataFlowNode().getLine() + " and index="
195                         + so.getDataFlowNode().getIndex());
196             }
197 
198             // Attempt to get to this StackObject's NodeType from the current
199             // State
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) { // 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                     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 { // This NodeType _is_ a valid transition from the previous
230                      // State
231                 if (aktStatus.isLastStep() && !aktStatus.hasMoreSteps()) { // Terminal
232                                                                            // State
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 }