001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: package org.apache.catalina.ssi;
018:
019: import java.text.ParseException;
020: import java.util.LinkedList;
021: import java.util.List;
022:
023: /**
024: * Represents a parsed expression.
025: *
026: * @version $Revision: 531303 $
027: * @author Paul Speed
028: */
029: public class ExpressionParseTree {
030: /**
031: * Contains the current set of completed nodes. This is a workspace for the
032: * parser.
033: */
034: private LinkedList nodeStack = new LinkedList();
035: /**
036: * Contains operator nodes that don't yet have values. This is a workspace
037: * for the parser.
038: */
039: private LinkedList oppStack = new LinkedList();
040: /**
041: * The root node after the expression has been parsed.
042: */
043: private Node root;
044: /**
045: * The SSIMediator to use when evaluating the expressions.
046: */
047: private SSIMediator ssiMediator;
048:
049: /**
050: * Creates a new parse tree for the specified expression.
051: */
052: public ExpressionParseTree(String expr, SSIMediator ssiMediator)
053: throws ParseException {
054: this .ssiMediator = ssiMediator;
055: parseExpression(expr);
056: }
057:
058: /**
059: * Evaluates the tree and returns true or false. The specified SSIMediator
060: * is used to resolve variable references.
061: */
062: public boolean evaluateTree() {
063: return root.evaluate();
064: }
065:
066: /**
067: * Pushes a new operator onto the opp stack, resolving existing opps as
068: * needed.
069: */
070: private void pushOpp(OppNode node) {
071: // If node is null then it's just a group marker
072: if (node == null) {
073: oppStack.add(0, node);
074: return;
075: }
076: while (true) {
077: if (oppStack.size() == 0)
078: break;
079: OppNode top = (OppNode) oppStack.get(0);
080: // If the top is a spacer then don't pop
081: // anything
082: if (top == null)
083: break;
084: // If the top node has a lower precedence then
085: // let it stay
086: if (top.getPrecedence() < node.getPrecedence())
087: break;
088: // Remove the top node
089: oppStack.remove(0);
090: // Let it fill its branches
091: top.popValues(nodeStack);
092: // Stick it on the resolved node stack
093: nodeStack.add(0, top);
094: }
095: // Add the new node to the opp stack
096: oppStack.add(0, node);
097: }
098:
099: /**
100: * Resolves all pending opp nodes on the stack until the next group marker
101: * is reached.
102: */
103: private void resolveGroup() {
104: OppNode top = null;
105: while ((top = (OppNode) oppStack.remove(0)) != null) {
106: // Let it fill its branches
107: top.popValues(nodeStack);
108: // Stick it on the resolved node stack
109: nodeStack.add(0, top);
110: }
111: }
112:
113: /**
114: * Parses the specified expression into a tree of parse nodes.
115: */
116: private void parseExpression(String expr) throws ParseException {
117: StringNode currStringNode = null;
118: // We cheat a little and start an artificial
119: // group right away. It makes finishing easier.
120: pushOpp(null);
121: ExpressionTokenizer et = new ExpressionTokenizer(expr);
122: while (et.hasMoreTokens()) {
123: int token = et.nextToken();
124: if (token != ExpressionTokenizer.TOKEN_STRING)
125: currStringNode = null;
126: switch (token) {
127: case ExpressionTokenizer.TOKEN_STRING:
128: if (currStringNode == null) {
129: currStringNode = new StringNode(et.getTokenValue());
130: nodeStack.add(0, currStringNode);
131: } else {
132: // Add to the existing
133: currStringNode.value.append(" ");
134: currStringNode.value.append(et.getTokenValue());
135: }
136: break;
137: case ExpressionTokenizer.TOKEN_AND:
138: pushOpp(new AndNode());
139: break;
140: case ExpressionTokenizer.TOKEN_OR:
141: pushOpp(new OrNode());
142: break;
143: case ExpressionTokenizer.TOKEN_NOT:
144: pushOpp(new NotNode());
145: break;
146: case ExpressionTokenizer.TOKEN_EQ:
147: pushOpp(new EqualNode());
148: break;
149: case ExpressionTokenizer.TOKEN_NOT_EQ:
150: pushOpp(new NotNode());
151: // Sneak the regular node in. The NOT will
152: // be resolved when the next opp comes along.
153: oppStack.add(0, new EqualNode());
154: break;
155: case ExpressionTokenizer.TOKEN_RBRACE:
156: // Closeout the current group
157: resolveGroup();
158: break;
159: case ExpressionTokenizer.TOKEN_LBRACE:
160: // Push a group marker
161: pushOpp(null);
162: break;
163: case ExpressionTokenizer.TOKEN_GE:
164: pushOpp(new NotNode());
165: // Similar stategy to NOT_EQ above, except this
166: // is NOT less than
167: oppStack.add(0, new LessThanNode());
168: break;
169: case ExpressionTokenizer.TOKEN_LE:
170: pushOpp(new NotNode());
171: // Similar stategy to NOT_EQ above, except this
172: // is NOT greater than
173: oppStack.add(0, new GreaterThanNode());
174: break;
175: case ExpressionTokenizer.TOKEN_GT:
176: pushOpp(new GreaterThanNode());
177: break;
178: case ExpressionTokenizer.TOKEN_LT:
179: pushOpp(new LessThanNode());
180: break;
181: case ExpressionTokenizer.TOKEN_END:
182: break;
183: }
184: }
185: // Finish off the rest of the opps
186: resolveGroup();
187: if (nodeStack.size() == 0) {
188: throw new ParseException("No nodes created.", et.getIndex());
189: }
190: if (nodeStack.size() > 1) {
191: throw new ParseException("Extra nodes created.", et
192: .getIndex());
193: }
194: if (oppStack.size() != 0) {
195: throw new ParseException("Unused opp nodes exist.", et
196: .getIndex());
197: }
198: root = (Node) nodeStack.get(0);
199: }
200:
201: /**
202: * A node in the expression parse tree.
203: */
204: private abstract class Node {
205: /**
206: * Return true if the node evaluates to true.
207: */
208: public abstract boolean evaluate();
209: }
210:
211: /**
212: * A node the represents a String value
213: */
214: private class StringNode extends Node {
215: StringBuffer value;
216: String resolved = null;
217:
218: public StringNode(String value) {
219: this .value = new StringBuffer(value);
220: }
221:
222: /**
223: * Resolves any variable references and returns the value string.
224: */
225: public String getValue() {
226: if (resolved == null)
227: resolved = ssiMediator.substituteVariables(value
228: .toString());
229: return resolved;
230: }
231:
232: /**
233: * Returns true if the string is not empty.
234: */
235: public boolean evaluate() {
236: return !(getValue().length() == 0);
237: }
238:
239: public String toString() {
240: return value.toString();
241: }
242: }
243:
244: private static final int PRECEDENCE_NOT = 5;
245: private static final int PRECEDENCE_COMPARE = 4;
246: private static final int PRECEDENCE_LOGICAL = 1;
247:
248: /**
249: * A node implementation that represents an operation.
250: */
251: private abstract class OppNode extends Node {
252: /**
253: * The left branch.
254: */
255: Node left;
256: /**
257: * The right branch.
258: */
259: Node right;
260:
261: /**
262: * Returns a preference level suitable for comparison to other OppNode
263: * preference levels.
264: */
265: public abstract int getPrecedence();
266:
267: /**
268: * Lets the node pop its own branch nodes off the front of the
269: * specified list. The default pulls two.
270: */
271: public void popValues(List values) {
272: right = (Node) values.remove(0);
273: left = (Node) values.remove(0);
274: }
275: }
276:
277: private final class NotNode extends OppNode {
278: public boolean evaluate() {
279: return !left.evaluate();
280: }
281:
282: public int getPrecedence() {
283: return PRECEDENCE_NOT;
284: }
285:
286: /**
287: * Overridden to pop only one value.
288: */
289: public void popValues(List values) {
290: left = (Node) values.remove(0);
291: }
292:
293: public String toString() {
294: return left + " NOT";
295: }
296: }
297:
298: private final class AndNode extends OppNode {
299: public boolean evaluate() {
300: if (!left.evaluate()) // Short circuit
301: return false;
302: return right.evaluate();
303: }
304:
305: public int getPrecedence() {
306: return PRECEDENCE_LOGICAL;
307: }
308:
309: public String toString() {
310: return left + " " + right + " AND";
311: }
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: public int getPrecedence() {
322: return PRECEDENCE_LOGICAL;
323: }
324:
325: public String toString() {
326: return left + " " + right + " OR";
327: }
328: }
329:
330: private abstract class CompareNode extends OppNode {
331: protected int compareBranches() {
332: String val1 = ((StringNode) left).getValue();
333: String val2 = ((StringNode) right).getValue();
334: return val1.compareTo(val2);
335: }
336: }
337:
338: private final class EqualNode extends CompareNode {
339: public boolean evaluate() {
340: return (compareBranches() == 0);
341: }
342:
343: public int getPrecedence() {
344: return PRECEDENCE_COMPARE;
345: }
346:
347: public String toString() {
348: return left + " " + right + " EQ";
349: }
350: }
351:
352: private final class GreaterThanNode extends CompareNode {
353: public boolean evaluate() {
354: return (compareBranches() > 0);
355: }
356:
357: public int getPrecedence() {
358: return PRECEDENCE_COMPARE;
359: }
360:
361: public String toString() {
362: return left + " " + right + " GT";
363: }
364: }
365:
366: private final class LessThanNode extends CompareNode {
367: public boolean evaluate() {
368: return (compareBranches() < 0);
369: }
370:
371: public int getPrecedence() {
372: return PRECEDENCE_COMPARE;
373: }
374:
375: public String toString() {
376: return left + " " + right + " LT";
377: }
378: }
379: }
|