ExpressionParseTree


1   /*
2    * Copyright 1999,2004 The Apache Software Foundation. Licensed under the
3    * Apache License, Version 2.0 (the "License"); you may not use this file
4    * except in compliance with the License. You may obtain a copy of the License
5    * at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable
6    * law or agreed to in writing, software distributed under the License is
7    * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
8    * KIND, either express or implied. See the License for the specific language
9    * governing permissions and limitations under the License.
10   */
11  package org.apache.catalina.ssi;
12  
13  
14  import java.text.ParseException  ;
15  import java.util.LinkedList  ;
16  import java.util.List  ;
17  /**
18   * Represents a parsed expression.
19   * 
20   * @version $Revision: 467222 $
21   * @author Paul Speed
22   */
23  public class ExpressionParseTree {
24      /**
25       * Contains the current set of completed nodes. This is a workspace for the
26       * parser.
27       */
28      private LinkedList   nodeStack = new LinkedList  ();
29      /**
30       * Contains operator nodes that don't yet have values. This is a workspace
31       * for the parser.
32       */
33      private LinkedList   oppStack = new LinkedList  ();
34      /**
35       * The root node after the expression has been parsed.
36       */
37      private Node root;
38      /**
39       * The SSIMediator to use when evaluating the expressions.
40       */
41      private SSIMediator ssiMediator;
42  
43  
44      /**
45       * Creates a new parse tree for the specified expression.
46       */
47      public ExpressionParseTree(String   expr, SSIMediator ssiMediator)
48              throws ParseException   {
49          this.ssiMediator = ssiMediator;
50          parseExpression(expr);
51      }
52  
53  
54      /**
55       * Evaluates the tree and returns true or false. The specified SSIMediator
56       * is used to resolve variable references.
57       */
58      public boolean evaluateTree() {
59          return root.evaluate();
60      }
61  
62  
63      /**
64       * Pushes a new operator onto the opp stack, resolving existing opps as
65       * needed.
66       */
67      private void pushOpp(OppNode node) {
68          // If node is null then it's just a group marker
69          if (node == null) {
70              oppStack.add(0, node);
71              return;
72          }
73          while (true) {
74              if (oppStack.size() == 0) break;
75              OppNode top = (OppNode)oppStack.get(0);
76              // If the top is a spacer then don't pop
77              // anything
78              if (top == null) break;
79              // If the top node has a lower precedence then
80              // let it stay
81              if (top.getPrecedence() < node.getPrecedence()) break;
82              // Remove the top node
83              oppStack.remove(0);
84              // Let it fill its branches
85              top.popValues(nodeStack);
86              // Stick it on the resolved node stack
87              nodeStack.add(0, top);
88          }
89          // Add the new node to the opp stack
90          oppStack.add(0, node);
91      }
92  
93  
94      /**
95       * Resolves all pending opp nodes on the stack until the next group marker
96       * is reached.
97       */
98      private void resolveGroup() {
99          OppNode top = null;
100         while ((top = (OppNode)oppStack.remove(0)) != null) {
101             // Let it fill its branches
102             top.popValues(nodeStack);
103             // Stick it on the resolved node stack
104             nodeStack.add(0, top);
105         }
106     }
107 
108 
109     /**
110      * Parses the specified expression into a tree of parse nodes.
111      */
112     private void parseExpression(String   expr) throws ParseException   {
113         StringNode currStringNode = null;
114         // We cheat a little and start an artificial
115         // group right away. It makes finishing easier.
116         pushOpp(null);
117         ExpressionTokenizer et = new ExpressionTokenizer(expr);
118         while (et.hasMoreTokens()) {
119             int token = et.nextToken();
120             if (token != ExpressionTokenizer.TOKEN_STRING)
121                 currStringNode = null;
122             switch (token) {
123                 case ExpressionTokenizer.TOKEN_STRING :
124                     if (currStringNode == null) {
125                         currStringNode = new StringNode(et.getTokenValue());
126                         nodeStack.add(0, currStringNode);
127                     } else {
128                         // Add to the existing
129                         currStringNode.value.append(" ");
130                         currStringNode.value.append(et.getTokenValue());
131                     }
132                     break;
133                 case ExpressionTokenizer.TOKEN_AND :
134                     pushOpp(new AndNode());
135                     break;
136                 case ExpressionTokenizer.TOKEN_OR :
137                     pushOpp(new OrNode());
138                     break;
139                 case ExpressionTokenizer.TOKEN_NOT :
140                     pushOpp(new NotNode());
141                     break;
142                 case ExpressionTokenizer.TOKEN_EQ :
143                     pushOpp(new EqualNode());
144                     break;
145                 case ExpressionTokenizer.TOKEN_NOT_EQ :
146                     pushOpp(new NotNode());
147                     // Sneak the regular node in. The NOT will
148                     // be resolved when the next opp comes along.
149                     oppStack.add(0, new EqualNode());
150                     break;
151                 case ExpressionTokenizer.TOKEN_RBRACE :
152                     // Closeout the current group
153                     resolveGroup();
154                     break;
155                 case ExpressionTokenizer.TOKEN_LBRACE :
156                     // Push a group marker
157                     pushOpp(null);
158                     break;
159                 case ExpressionTokenizer.TOKEN_GE :
160                     pushOpp(new NotNode());
161                     // Similar stategy to NOT_EQ above, except this
162                     // is NOT less than
163                     oppStack.add(0, new LessThanNode());
164                     break;
165                 case ExpressionTokenizer.TOKEN_LE :
166                     pushOpp(new NotNode());
167                     // Similar stategy to NOT_EQ above, except this
168                     // is NOT greater than
169                     oppStack.add(0, new GreaterThanNode());
170                     break;
171                 case ExpressionTokenizer.TOKEN_GT :
172                     pushOpp(new GreaterThanNode());
173                     break;
174                 case ExpressionTokenizer.TOKEN_LT :
175                     pushOpp(new LessThanNode());
176                     break;
177                 case ExpressionTokenizer.TOKEN_END :
178                     break;
179             }
180         }
181         // Finish off the rest of the opps
182         resolveGroup();
183         if (nodeStack.size() == 0) {
184             throw new ParseException  ("No nodes created.", et.getIndex());
185         }
186         if (nodeStack.size() > 1) {
187             throw new ParseException  ("Extra nodes created.", et.getIndex());
188         }
189         if (oppStack.size() != 0) {
190             throw new ParseException  ("Unused opp nodes exist.", et.getIndex());
191         }
192         root = (Node)nodeStack.get(0);
193     }
194 
195     /**
196      * A node in the expression parse tree.
197      */
198     private abstract class Node {
199         /**
200          * Return true if the node evaluates to true.
201          */
202         public abstract boolean evaluate();
203     }
204     /**
205      * A node the represents a String value
206      */
207     private class StringNode extends Node {
208         StringBuffer   value;
209         String   resolved = null;
210 
211 
212         public StringNode(String   value) {
213             this.value = new StringBuffer  (value);
214         }
215 
216 
217         /**
218          * Resolves any variable references and returns the value string.
219          */
220         public String   getValue() {
221             if (resolved == null)
222                 resolved = ssiMediator.substituteVariables(value.toString());
223             return resolved;
224         }
225 
226 
227         /**
228          * Returns true if the string is not empty.
229          */
230         public boolean evaluate() {
231             return !(getValue().length() == 0);
232         }
233 
234 
235         public String   toString() {
236             return value.toString();
237         }
238     }
239 
240     private static final int PRECEDENCE_NOT = 5;
241     private static final int PRECEDENCE_COMPARE = 4;
242     private static final int PRECEDENCE_LOGICAL = 1;
243 
244     /**
245      * A node implementation that represents an operation.
246      */
247     private abstract class OppNode extends Node {
248         /**
249          * The left branch.
250          */
251         Node left;
252         /**
253          * The right branch.
254          */
255         Node right;
256 
257 
258         /**
259          * Returns a preference level suitable for comparison to other OppNode
260          * preference levels.
261          */
262         public abstract int getPrecedence();
263 
264 
265         /**
266          * Lets the node pop its own branch nodes off the front of the
267          * specified list. The default pulls two.
268          */
269         public void popValues(List   values) {
270             right = (Node)values.remove(0);
271             left = (Node)values.remove(0);
272         }
273     }
274     private final class NotNode extends OppNode {
275         public boolean evaluate() {
276             return !left.evaluate();
277         }
278 
279 
280         public int getPrecedence() {
281             return PRECEDENCE_NOT;
282         }
283 
284 
285         /**
286          * Overridden to pop only one value.
287          */
288         public void popValues(List   values) {
289             left = (Node)values.remove(0);
290         }
291 
292 
293         public String   toString() {
294             return left + " NOT";
295         }
296     }
297     private final class AndNode extends OppNode {
298         public boolean evaluate() {
299             if (!left.evaluate()) // Short circuit
300                 return false;
301             return right.evaluate();
302         }
303 
304 
305         public int getPrecedence() {
306             return PRECEDENCE_LOGICAL;
307         }
308 
309 
310         public String   toString() {
311             return left + " " + right + " AND";
312         }
313     }
314     private final class OrNode extends OppNode {
315         public boolean evaluate() {
316             if (left.evaluate()) // Short circuit
317                 return true;
318             return right.evaluate();
319         }
320 
321 
322         public int getPrecedence() {
323             return PRECEDENCE_LOGICAL;
324         }
325 
326 
327         public String   toString() {
328             return left + " " + right + " OR";
329         }
330     }
331     private abstract class CompareNode extends OppNode {
332         protected int compareBranches() {
333             String   val1 = ((StringNode)left).getValue();
334             String   val2 = ((StringNode)right).getValue();
335             return val1.compareTo(val2);
336         }
337     }
338     private final class EqualNode extends CompareNode {
339         public boolean evaluate() {
340             return (compareBranches() == 0);
341         }
342 
343 
344         public int getPrecedence() {
345             return PRECEDENCE_COMPARE;
346         }
347 
348 
349         public String   toString() {
350             return left + " " + right + " EQ";
351         }
352     }
353     private final class GreaterThanNode extends CompareNode {
354         public boolean evaluate() {
355             return (compareBranches() > 0);
356         }
357 
358 
359         public int getPrecedence() {
360             return PRECEDENCE_COMPARE;
361         }
362 
363 
364         public String   toString() {
365             return left + " " + right + " GT";
366         }
367     }
368     private final class LessThanNode extends CompareNode {
369         public boolean evaluate() {
370             return (compareBranches() < 0);
371         }
372 
373 
374         public int getPrecedence() {
375             return PRECEDENCE_COMPARE;
376         }
377 
378 
379         public String   toString() {
380             return left + " " + right + " LT";
381         }
382     }
383 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags