java/org/apache/catalina/ssi/ExpressionParseTree.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You 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;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.regex.PatternSyntaxException;

import org.apache.tomcat.util.ExceptionUtils;
import org.apache.tomcat.util.res.StringManager;

/**
 * Represents a parsed expression.
 */
public class ExpressionParseTree {
    private static final StringManager sm = StringManager.getManager(ExpressionParseTree.class);
    /**
     * Contains the current set of completed nodes. This is a workspace for the parser. Needs to be LinkedList since it
     * can contain {@code null}s.
     */
    private final LinkedList<Node> nodeStack = new LinkedList<>();
    /**
     * Contains operator nodes that don't yet have values. This is a workspace for the parser. Needs to be LinkedList
     * since it can contain {@code null}s.
     */
    private final LinkedList<OppNode> oppStack = new LinkedList<>();
    /**
     * The root node after the expression has been parsed.
     */
    private Node root;
    /**
     * The SSIMediator to use when evaluating the expressions.
     */
    private final SSIMediator ssiMediator;


    /**
     * Creates a new parse tree for the specified expression.
     *
     * @param expr        The expression string
     * @param ssiMediator Used to evaluate the expressions
     *
     * @throws ParseException a parsing error occurred
     */
    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.
     *
     * @return the evaluation result
     *
     * @throws SSIStopProcessingException If an error occurs evaluating the tree
     */
    public boolean evaluateTree() throws SSIStopProcessingException {
        try {
            return root.evaluate();
        } catch (Throwable t) {
            ExceptionUtils.handleThrowable(t);
            throw new SSIStopProcessingException(t);
        }
    }


    /**
     * Pushes a new operator onto the opp stack, resolving existing opps as needed.
     *
     * @param node The operator node
     */
    private void pushOpp(OppNode node) {
        // If node is null then it's just a group marker
        if (node == null) {
            oppStack.addFirst(null);
            return;
        }
        while (true) {
            if (oppStack.isEmpty()) {
                break;
            }
            OppNode top = oppStack.getFirst();
            // 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.removeFirst();
            // Let it fill its branches
            top.popValues(nodeStack);
            // Stick it on the resolved node stack
            nodeStack.addFirst(top);
        }
        // Add the new node to the opp stack
        oppStack.addFirst(node);
    }


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


    /**
     * Parses the specified expression into a tree of parse nodes.
     *
     * @param expr The expression to parse
     *
     * @throws ParseException a parsing error occurred
     */
    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.addFirst(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. They will NOT
                    // be resolved when the next opp comes along.
                    oppStack.addFirst(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 strategy to NOT_EQ above, except this
                    // is NOT less than
                    oppStack.addFirst(new LessThanNode());
                    break;
                case ExpressionTokenizer.TOKEN_LE:
                    pushOpp(new NotNode());
                    // Similar strategy to NOT_EQ above, except this
                    // is NOT greater than
                    oppStack.addFirst(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.isEmpty()) {
            throw new ParseException(sm.getString("expressionParseTree.noNodes"), et.getIndex());
        }
        if (nodeStack.size() > 1) {
            throw new ParseException(sm.getString("expressionParseTree.extraNodes"), et.getIndex());
        }
        if (!oppStack.isEmpty()) {
            throw new ParseException(sm.getString("expressionParseTree.unusedOpCodes"), et.getIndex());
        }
        root = nodeStack.getFirst();
    }

    /**
     * A node in the expression parse tree.
     */
    private abstract static class Node {
        /**
         * @return {@code true} if the node evaluates to true.
         */
        public abstract boolean evaluate();
    }

    /**
     * A node the represents a String value
     */
    private class StringNode extends Node {
        StringBuilder value;
        String resolved = null;


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


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


        /**
         * Returns true if the string is not empty.
         */
        @Override
        public boolean evaluate() {
            return !(getValue().isEmpty());
        }


        @Override
        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 static class OppNode extends Node {
        /**
         * The left branch.
         */
        Node left;
        /**
         * The right branch.
         */
        Node right;


        /**
         * @return a precedence 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.
         *
         * @param values The list from which to pop the values
         */
        public void popValues(List<Node> values) {
            right = values.removeFirst();
            left = values.removeFirst();
        }
    }

    private static final class NotNode extends OppNode {
        @Override
        public boolean evaluate() {
            return !left.evaluate();
        }


        @Override
        public int getPrecedence() {
            return PRECEDENCE_NOT;
        }


        /**
         * Overridden to pop only one value.
         */
        @Override
        public void popValues(List<Node> values) {
            left = values.removeFirst();
        }


        @Override
        public String toString() {
            return left + " NOT";
        }
    }

    private static final class AndNode extends OppNode {
        @Override
        public boolean evaluate() {
            if (!left.evaluate()) {
                return false;
            }
            return right.evaluate();
        }


        @Override
        public int getPrecedence() {
            return PRECEDENCE_LOGICAL;
        }


        @Override
        public String toString() {
            return left + " " + right + " AND";
        }
    }

    private static final class OrNode extends OppNode {
        @Override
        public boolean evaluate() {
            if (left.evaluate()) {
                return true;
            }
            return right.evaluate();
        }


        @Override
        public int getPrecedence() {
            return PRECEDENCE_LOGICAL;
        }


        @Override
        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();

            int val2Len = val2.length();
            if (val2Len > 1 && val2.charAt(0) == '/' && val2.charAt(val2Len - 1) == '/') {
                // Treat as a regular expression
                String expr = val2.substring(1, val2Len - 1);
                ssiMediator.clearMatchGroups();
                try {
                    Pattern pattern = Pattern.compile(expr);
                    // Regular expressions will only ever be used with EqualNode
                    // so return zero for equal and non-zero for not equal
                    Matcher matcher = pattern.matcher(val1);
                    if (matcher.find()) {
                        ssiMediator.populateMatchGroups(matcher);
                        return 0;
                    } else {
                        return -1;
                    }
                } catch (PatternSyntaxException pse) {
                    ssiMediator.log(sm.getString("expressionParseTree.invalidExpression", expr), pse);
                    return 0;
                }
            }
            return val1.compareTo(val2);
        }
    }

    private final class EqualNode extends CompareNode {
        @Override
        public boolean evaluate() {
            return (compareBranches() == 0);
        }


        @Override
        public int getPrecedence() {
            return PRECEDENCE_COMPARE;
        }


        @Override
        public String toString() {
            return left + " " + right + " EQ";
        }
    }

    private final class GreaterThanNode extends CompareNode {
        @Override
        public boolean evaluate() {
            return (compareBranches() > 0);
        }


        @Override
        public int getPrecedence() {
            return PRECEDENCE_COMPARE;
        }


        @Override
        public String toString() {
            return left + " " + right + " GT";
        }
    }

    private final class LessThanNode extends CompareNode {
        @Override
        public boolean evaluate() {
            return (compareBranches() < 0);
        }


        @Override
        public int getPrecedence() {
            return PRECEDENCE_COMPARE;
        }


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