container/catalina/src/share/org/apache/catalina/ssi/ExpressionParseTree.java

/*
 * Copyright 1999,2004 The Apache Software Foundation. Licensed under the
 * Apache License, Version 2.0 (the "License"); you may not use this file
 * except in compliance with the License. You may obtain a copy of the License
 * at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable
 * law or agreed to in writing, software distributed under the License is
 * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied. See the License for the specific language
 * governing permissions and limitations under the License.
 */
package org.apache.catalina.ssi;


import java.text.ParseException;
import java.util.LinkedList;
import java.util.List;
/**
 * Represents a parsed expression.
 * 
 * @version $Revision$
 * @author Paul Speed
 */
public class ExpressionParseTree {
    /**
     * Contains the current set of completed nodes. This is a workspace for the
     * parser.
     */
    private LinkedList nodeStack = new LinkedList();
    /**
     * Contains operator nodes that don't yet have values. This is a workspace
     * for the parser.
     */
    private LinkedList oppStack = new LinkedList();
    /**
     * The root node after the expression has been parsed.
     */
    private Node root;
    /**
     * The SSIMediator to use when evaluating the expressions.
     */
    private SSIMediator ssiMediator;


    /**
     * Creates a new parse tree for the specified expression.
     */
    public ExpressionParseTree(String expr, SSIMediator ssiMediator)
            throws ParseException {
        this.ssiMediator = ssiMediator;
        parseExpression(expr);
    }


    /**
     * Evaluates the tree and returns true or false. The specified SSIMediator
     * is used to resolve variable references.
     */
    public boolean evaluateTree() {
        return root.evaluate();
    }


    /**
     * Pushes a new operator onto the opp stack, resolving existing opps as
     * needed.
     */
    private void pushOpp(OppNode node) {
        // If node is null then it's just a group marker
        if (node == null) {
            oppStack.add(0, node);
            return;
        }
        while (true) {
            if (oppStack.size() == 0) break;
            OppNode top = (OppNode)oppStack.get(0);
            // If the top is a spacer then don't pop
            // anything
            if (top == null) break;
            // If the top node has a lower precedence then
            // let it stay
            if (top.getPrecedence() < node.getPrecedence()) break;
            // Remove the top node
            oppStack.remove(0);
            // Let it fill its branches
            top.popValues(nodeStack);
            // Stick it on the resolved node stack
            nodeStack.add(0, top);
        }
        // Add the new node to the opp stack
        oppStack.add(0, node);
    }


    /**
     * Resolves all pending opp nodes on the stack until the next group marker
     * is reached.
     */
    private void resolveGroup() {
        OppNode top = null;
        while ((top = (OppNode)oppStack.remove(0)) != null) {
            // Let it fill its branches
            top.popValues(nodeStack);
            // Stick it on the resolved node stack
            nodeStack.add(0, top);
        }
    }


    /**
     * Parses the specified expression into a tree of parse nodes.
     */
    private void parseExpression(String expr) throws ParseException {
        StringNode currStringNode = null;
        // We cheat a little and start an artificial
        // group right away. It makes finishing easier.
        pushOpp(null);
        ExpressionTokenizer et = new ExpressionTokenizer(expr);
        while (et.hasMoreTokens()) {
            int token = et.nextToken();
            if (token != ExpressionTokenizer.TOKEN_STRING)
                currStringNode = null;
            switch (token) {
                case ExpressionTokenizer.TOKEN_STRING :
                    if (currStringNode == null) {
                        currStringNode = new StringNode(et.getTokenValue());
                        nodeStack.add(0, currStringNode);
                    } else {
                        // Add to the existing
                        currStringNode.value.append(" ");
                        currStringNode.value.append(et.getTokenValue());
                    }
                    break;
                case ExpressionTokenizer.TOKEN_AND :
                    pushOpp(new AndNode());
                    break;
                case ExpressionTokenizer.TOKEN_OR :
                    pushOpp(new OrNode());
                    break;
                case ExpressionTokenizer.TOKEN_NOT :
                    pushOpp(new NotNode());
                    break;
                case ExpressionTokenizer.TOKEN_EQ :
                    pushOpp(new EqualNode());
                    break;
                case ExpressionTokenizer.TOKEN_NOT_EQ :
                    pushOpp(new NotNode());
                    // Sneak the regular node in. The NOT will
                    // be resolved when the next opp comes along.
                    oppStack.add(0, new EqualNode());
                    break;
                case ExpressionTokenizer.TOKEN_RBRACE :
                    // Closeout the current group
                    resolveGroup();
                    break;
                case ExpressionTokenizer.TOKEN_LBRACE :
                    // Push a group marker
                    pushOpp(null);
                    break;
                case ExpressionTokenizer.TOKEN_GE :
                    pushOpp(new NotNode());
                    // Similar stategy to NOT_EQ above, except this
                    // is NOT less than
                    oppStack.add(0, new LessThanNode());
                    break;
                case ExpressionTokenizer.TOKEN_LE :
                    pushOpp(new NotNode());
                    // Similar stategy to NOT_EQ above, except this
                    // is NOT greater than
                    oppStack.add(0, new GreaterThanNode());
                    break;
                case ExpressionTokenizer.TOKEN_GT :
                    pushOpp(new GreaterThanNode());
                    break;
                case ExpressionTokenizer.TOKEN_LT :
                    pushOpp(new LessThanNode());
                    break;
                case ExpressionTokenizer.TOKEN_END :
                    break;
            }
        }
        // Finish off the rest of the opps
        resolveGroup();
        if (nodeStack.size() == 0) {
            throw new ParseException("No nodes created.", et.getIndex());
        }
        if (nodeStack.size() > 1) {
            throw new ParseException("Extra nodes created.", et.getIndex());
        }
        if (oppStack.size() != 0) {
            throw new ParseException("Unused opp nodes exist.", et.getIndex());
        }
        root = (Node)nodeStack.get(0);
    }

    /**
     * A node in the expression parse tree.
     */
    private abstract class Node {
        /**
         * Return true if the node evaluates to true.
         */
        public abstract boolean evaluate();
    }
    /**
     * A node the represents a String value
     */
    private class StringNode extends Node {
        StringBuffer value;
        String resolved = null;


        public StringNode(String value) {
            this.value = new StringBuffer(value);
        }


        /**
         * Resolves any variable references and returns the value string.
         */
        public String getValue() {
            if (resolved == null)
                resolved = ssiMediator.substituteVariables(value.toString());
            return resolved;
        }


        /**
         * Returns true if the string is not empty.
         */
        public boolean evaluate() {
            return !(getValue().length() == 0);
        }


        public String toString() {
            return value.toString();
        }
    }

    private static final int PRECEDENCE_NOT = 5;
    private static final int PRECEDENCE_COMPARE = 4;
    private static final int PRECEDENCE_LOGICAL = 1;

    /**
     * A node implementation that represents an operation.
     */
    private abstract class OppNode extends Node {
        /**
         * The left branch.
         */
        Node left;
        /**
         * The right branch.
         */
        Node right;


        /**
         * Returns a preference level suitable for comparison to other OppNode
         * preference levels.
         */
        public abstract int getPrecedence();


        /**
         * Lets the node pop its own branch nodes off the front of the
         * specified list. The default pulls two.
         */
        public void popValues(List values) {
            right = (Node)values.remove(0);
            left = (Node)values.remove(0);
        }
    }
    private final class NotNode extends OppNode {
        public boolean evaluate() {
            return !left.evaluate();
        }


        public int getPrecedence() {
            return PRECEDENCE_NOT;
        }


        /**
         * Overridden to pop only one value.
         */
        public void popValues(List values) {
            left = (Node)values.remove(0);
        }


        public String toString() {
            return left + " NOT";
        }
    }
    private final class AndNode extends OppNode {
        public boolean evaluate() {
            if (!left.evaluate()) // Short circuit
                return false;
            return right.evaluate();
        }


        public int getPrecedence() {
            return PRECEDENCE_LOGICAL;
        }


        public String toString() {
            return left + " " + right + " AND";
        }
    }
    private final class OrNode extends OppNode {
        public boolean evaluate() {
            if (left.evaluate()) // Short circuit
                return true;
            return right.evaluate();
        }


        public int getPrecedence() {
            return PRECEDENCE_LOGICAL;
        }


        public String toString() {
            return left + " " + right + " OR";
        }
    }
    private abstract class CompareNode extends OppNode {
        protected int compareBranches() {
            String val1 = ((StringNode)left).getValue();
            String val2 = ((StringNode)right).getValue();
            return val1.compareTo(val2);
        }
    }
    private final class EqualNode extends CompareNode {
        public boolean evaluate() {
            return (compareBranches() == 0);
        }


        public int getPrecedence() {
            return PRECEDENCE_COMPARE;
        }


        public String toString() {
            return left + " " + right + " EQ";
        }
    }
    private final class GreaterThanNode extends CompareNode {
        public boolean evaluate() {
            return (compareBranches() > 0);
        }


        public int getPrecedence() {
            return PRECEDENCE_COMPARE;
        }


        public String toString() {
            return left + " " + right + " GT";
        }
    }
    private final class LessThanNode extends CompareNode {
        public boolean evaluate() {
            return (compareBranches() < 0);
        }


        public int getPrecedence() {
            return PRECEDENCE_COMPARE;
        }


        public String toString() {
            return left + " " + right + " LT";
        }
    }
}