| /** |
| * 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.ambari.server.api.predicate; |
| |
| import org.apache.ambari.server.api.predicate.expressions.Expression; |
| import org.apache.ambari.server.api.predicate.expressions.LogicalExpressionFactory; |
| import org.apache.ambari.server.api.predicate.expressions.RelationalExpression; |
| import org.apache.ambari.server.api.predicate.operators.*; |
| import org.apache.ambari.server.controller.spi.Predicate; |
| |
| import java.util.*; |
| |
| /** |
| * Parser which produces a predicate instance from an array of tokens, |
| * which is generated by the lexer. |
| */ |
| public class QueryParser { |
| |
| /** |
| * Map of token type to token handlers. |
| */ |
| private static final Map<Token.TYPE, TokenHandler> TOKEN_HANDLERS = |
| new HashMap<Token.TYPE, TokenHandler>(); |
| |
| /** |
| * Constructor. |
| * Register token handlers. |
| * |
| */ |
| public QueryParser() { |
| TOKEN_HANDLERS.put(Token.TYPE.BRACKET_OPEN, new BracketOpenTokenHandler()); |
| TOKEN_HANDLERS.put(Token.TYPE.BRACKET_CLOSE, new BracketCloseTokenHandler()); |
| TOKEN_HANDLERS.put(Token.TYPE.RELATIONAL_OPERATOR, new RelationalOperatorTokenHandler()); |
| TOKEN_HANDLERS.put(Token.TYPE.LOGICAL_OPERATOR, new LogicalOperatorTokenHandler()); |
| TOKEN_HANDLERS.put(Token.TYPE.LOGICAL_UNARY_OPERATOR, new LogicalUnaryOperatorTokenHandler()); |
| TOKEN_HANDLERS.put(Token.TYPE.PROPERTY_OPERAND, new PropertyOperandTokenHandler()); |
| TOKEN_HANDLERS.put(Token.TYPE.VALUE_OPERAND, new ValueOperandTokenHandler()); |
| TOKEN_HANDLERS.put(Token.TYPE.RELATIONAL_OPERATOR_FUNC, new RelationalOperatorFuncTokenHandler()); |
| } |
| |
| /** |
| * Generate a Predicate instance from an array of tokens. |
| * Each input token contains a type and a value. |
| * |
| * Based on the token type and location, the tokens are first translated into a list of |
| * expressions, both relational and logical. These expressions are then merged into a tree |
| * of expressions with a single root following operator precedence and explicit grouping rules. |
| * Depending on the query, this merging of expressions into a tree of expressions may occur in |
| * several passes, one pass per level of precedence starting at the highest level of precedence. |
| * |
| * The predicate is built by traversing the expression tree in-order with each node expressing itself |
| * as a predicate. |
| * |
| * @param tokens an array of tokens which represent the query, |
| * each token contains type and value information |
| * |
| * @return a new predicate instance based on the supplied tokens |
| * @throws InvalidQueryException if unable to parse the tokens and produce a predicate |
| */ |
| public Predicate parse(Token[] tokens) throws InvalidQueryException { |
| ParseContext ctx = parseExpressions(tokens); |
| |
| List<Expression> listExpressions = ctx.getExpressions(); |
| List<Expression> listMergedExpressions = mergeExpressions(listExpressions, ctx.getMaxPrecedence()); |
| |
| return listMergedExpressions.isEmpty() ? null : |
| listMergedExpressions.get(0).toPredicate(); |
| } |
| |
| /** |
| * Create parse context from an array of tokens. The parse context contains a list of expressions |
| * and other information about the expressions an parsed tokens. |
| * |
| * @param tokens an array of tokens which represent the query, |
| * each token contains type and value information |
| * |
| * @return a parse context which contains a list of expressions |
| * @throws InvalidQueryException if unable to properly parse the tokens into a parse context |
| */ |
| private ParseContext parseExpressions(Token[] tokens) throws InvalidQueryException { |
| ParseContext ctx = new ParseContext(tokens); |
| |
| while (ctx.getCurrentTokensIndex() < tokens.length) { |
| TOKEN_HANDLERS.get(tokens[ctx.getCurrentTokensIndex()].getType()).handleToken(ctx); |
| } |
| |
| if (ctx.getPrecedenceLevel() != 0) { |
| throw new InvalidQueryException("Invalid query string: mismatched parentheses."); |
| } |
| |
| return ctx; |
| } |
| |
| /** |
| * Merge list of expressions into a tree of logical/relational expressions. |
| * This is done recursively in several passes, one per level of precedence starting at the |
| * highest precedence level. Recursion exits when a single expression remains. |
| * |
| * @param listExpressions list of expressions to merge |
| * @param precedenceLevel the precedence level that is to be merged |
| * |
| * @return tree of expressions with a single root expression |
| */ |
| private List<Expression> mergeExpressions(List<Expression> listExpressions, int precedenceLevel) { |
| if (listExpressions.size() > 1) { |
| Stack<Expression> stack = new Stack<Expression>(); |
| |
| stack.push(listExpressions.remove(0)); |
| while (! listExpressions.isEmpty()) { |
| Expression exp = stack.pop(); |
| Expression left = stack.empty() ? null : stack.pop(); |
| Expression right = listExpressions.remove(0); |
| stack.addAll(exp.merge(left, right, precedenceLevel)); |
| } |
| return mergeExpressions(new ArrayList<Expression>(stack), precedenceLevel - 1); |
| } |
| return listExpressions; |
| } |
| |
| /** |
| * A parse context which contains information related to parsing the provided tokens into expressions. |
| */ |
| private class ParseContext { |
| /** |
| * The current context precedence level. This is dictated by bracket tokens. |
| */ |
| private int m_precedence = 0; |
| |
| /** |
| * Current position in tokens array |
| */ |
| private int m_tokensIdx = 0; |
| |
| /** |
| * Tokens |
| */ |
| private Token[] m_tokens; |
| |
| /** |
| * The type of the previous token used in validation. |
| */ |
| private Token.TYPE m_previousTokenType = null; |
| |
| /** |
| * The list of expressions which are generated from the tokens. |
| */ |
| private List<Expression> m_listExpressions = new ArrayList<Expression>(); |
| |
| /** |
| * Highest precedence level in expression. |
| */ |
| int m_maxPrecedence = 0; |
| |
| public ParseContext(Token[] tokens) { |
| m_tokens = tokens; |
| } |
| |
| /** |
| * Get array of all tokens. |
| * @return token array |
| */ |
| public Token[] getTokens() { |
| return m_tokens; |
| } |
| |
| /** |
| * Get the current position in the tokens array. |
| * @return the current tokens index |
| */ |
| public int getCurrentTokensIndex() { |
| return m_tokensIdx; |
| } |
| |
| /** |
| * Set the current position in the tokens array. |
| * Each handler should set this value after processing a token(s). |
| * @param idx current tokens index |
| */ |
| public void setCurrentTokensIndex(int idx) { |
| m_tokensIdx = idx; |
| } |
| |
| /** |
| * Increment the context precedence level. |
| * |
| * @param val how much the level is increased by |
| */ |
| public void incPrecedenceLevel(int val) { |
| m_precedence += val; |
| } |
| |
| /** |
| * Decrement the context precedence level. |
| * |
| * @param val how much the level is decremented by |
| * @throws InvalidQueryException if the level is decremented below 0 |
| */ |
| public void decPrecedenceLevel(int val) throws InvalidQueryException { |
| m_precedence -= val; |
| if (m_precedence < 0) { |
| throw new InvalidQueryException("Invalid query string: mismatched parentheses."); |
| } |
| } |
| |
| /** |
| * Get the current context precedence level. |
| * |
| * @return current context precedence level |
| */ |
| public int getPrecedenceLevel() { |
| return m_precedence; |
| } |
| |
| /** |
| * Get the list of generated expressions. |
| * |
| * @return the list of generated expressions |
| */ |
| public List<Expression> getExpressions() { |
| return m_listExpressions; |
| } |
| |
| /** |
| * Get the last expression. |
| * |
| * @return the last expression |
| */ |
| public Expression getPrecedingExpression() { |
| return m_listExpressions == null ? null : |
| m_listExpressions.get(m_listExpressions.size() - 1); |
| } |
| |
| /** |
| * Get the highest operator precedence in the list of generated expressions. |
| * |
| * @return the max operator precedence |
| */ |
| public int getMaxPrecedence() { |
| return m_maxPrecedence; |
| } |
| |
| /** |
| * Update the max precedence level. |
| * The max precedence level is only updated if the provided level > the current level. |
| * |
| * @param precedenceLevel the new value |
| */ |
| public void updateMaxPrecedence(int precedenceLevel) { |
| if (precedenceLevel > m_maxPrecedence) { |
| m_maxPrecedence = precedenceLevel; |
| } |
| } |
| |
| /** |
| * Add a generated expression. |
| * |
| * @param exp the expression to add |
| */ |
| public void addExpression(Expression exp) { |
| m_listExpressions.add(exp); |
| } |
| |
| /** |
| * Set the token type of the current token |
| * |
| * @param type type of the current token |
| */ |
| private void setTokenType(Token.TYPE type) { |
| m_previousTokenType = type; |
| } |
| |
| /** |
| * Get the last token type set. |
| * |
| * @return the last token type set |
| */ |
| public Token.TYPE getPreviousTokenType() { |
| return m_previousTokenType; |
| } |
| } |
| |
| |
| /** |
| * Base token handler. |
| * Token handlers are responsible for handling the processing of a specific token type. |
| */ |
| private abstract class TokenHandler { |
| /** |
| * Process a token. Handles common token processing functionality then delegates to the individual |
| * concrete handlers. |
| * |
| * @param ctx the current parse context |
| * @throws InvalidQueryException if unable to process the token |
| */ |
| public void handleToken(ParseContext ctx) throws InvalidQueryException { |
| Token token = ctx.getTokens()[ctx.getCurrentTokensIndex()]; |
| if (! validate(ctx.getPreviousTokenType())) { |
| throw new InvalidQueryException("Unexpected token encountered in query string. Last Token Type=" + |
| ctx.getPreviousTokenType() + ", Current Token[type=" + token.getType() + |
| ", value='" + token.getValue() + "']"); |
| } |
| ctx.setTokenType(token.getType()); |
| |
| int idxIncrement = _handleToken(ctx); |
| ctx.setCurrentTokensIndex(ctx.getCurrentTokensIndex() + idxIncrement); |
| } |
| |
| /** |
| * Process a token. |
| * |
| * @param ctx the current parse context |
| * @throws InvalidQueryException if unable to process the token |
| */ |
| public abstract int _handleToken(ParseContext ctx) throws InvalidQueryException; |
| |
| /** |
| * Validate the token based on the previous token. |
| * |
| * @param previousTokenType the type of the previous token |
| * @return true if validation is successful, false otherwise |
| */ |
| public abstract boolean validate(Token.TYPE previousTokenType); |
| } |
| |
| /** |
| * Open Bracket token handler. |
| */ |
| private class BracketOpenTokenHandler extends TokenHandler { |
| |
| @Override |
| public int _handleToken(ParseContext ctx) { |
| ctx.incPrecedenceLevel(Operator.MAX_OP_PRECEDENCE); |
| return 1; |
| } |
| |
| @Override |
| public boolean validate(Token.TYPE previousTokenType) { |
| return previousTokenType == null || |
| previousTokenType == Token.TYPE.BRACKET_OPEN || |
| previousTokenType == Token.TYPE.LOGICAL_OPERATOR || |
| previousTokenType == Token.TYPE.LOGICAL_UNARY_OPERATOR; |
| } |
| } |
| |
| /** |
| * Close Bracket token handler |
| */ |
| private class BracketCloseTokenHandler extends TokenHandler { |
| @Override |
| public int _handleToken(ParseContext ctx) throws InvalidQueryException{ |
| ctx.decPrecedenceLevel(Operator.MAX_OP_PRECEDENCE); |
| |
| return 1; |
| } |
| |
| @Override |
| public boolean validate(Token.TYPE previousTokenType) { |
| return previousTokenType == Token.TYPE.VALUE_OPERAND || |
| previousTokenType == Token.TYPE.BRACKET_CLOSE; |
| } |
| } |
| |
| /** |
| * Relational Operator token handler |
| */ |
| private class RelationalOperatorTokenHandler extends TokenHandler { |
| @Override |
| public int _handleToken(ParseContext ctx) throws InvalidQueryException { |
| Token token = ctx.getTokens()[ctx.getCurrentTokensIndex()]; |
| RelationalOperator relationalOp = RelationalOperatorFactory.createOperator(token.getValue()); |
| //todo: use factory to create expression |
| ctx.addExpression(new RelationalExpression(relationalOp)); |
| |
| return 1; |
| } |
| |
| @Override |
| public boolean validate(Token.TYPE previousTokenType) { |
| return previousTokenType == null || |
| previousTokenType == Token.TYPE.BRACKET_OPEN || |
| previousTokenType == Token.TYPE.LOGICAL_OPERATOR || |
| previousTokenType == Token.TYPE.LOGICAL_UNARY_OPERATOR; |
| } |
| } |
| |
| /** |
| * Relational Operator function token handler |
| */ |
| private class RelationalOperatorFuncTokenHandler extends TokenHandler { |
| @Override |
| public int _handleToken(ParseContext ctx) throws InvalidQueryException { |
| Token[] tokens = ctx.getTokens(); |
| int idx = ctx.getCurrentTokensIndex(); |
| Token token = tokens[idx]; |
| RelationalOperator relationalOp = RelationalOperatorFactory.createOperator(token.getValue()); |
| |
| ctx.addExpression(new RelationalExpression(relationalOp)); |
| ctx.setCurrentTokensIndex(++idx); |
| |
| TokenHandler propertyHandler = new PropertyOperandTokenHandler(); |
| propertyHandler.handleToken(ctx); |
| |
| // handle right operand if applicable to operator |
| idx = ctx.getCurrentTokensIndex(); |
| if (ctx.getCurrentTokensIndex() < tokens.length && |
| tokens[idx].getType().equals(Token.TYPE.VALUE_OPERAND)) { |
| TokenHandler valueHandler = new ValueOperandTokenHandler(); |
| valueHandler.handleToken(ctx); |
| } |
| |
| // skip closing bracket |
| idx = ctx.getCurrentTokensIndex(); |
| if (idx >= tokens.length || tokens[idx].getType() != Token.TYPE.BRACKET_CLOSE) { |
| throw new InvalidQueryException("Missing closing bracket for in expression.") ; |
| } |
| return 1; |
| } |
| |
| @Override |
| public boolean validate(Token.TYPE previousTokenType) { |
| return previousTokenType == null || |
| previousTokenType == Token.TYPE.BRACKET_OPEN || |
| previousTokenType == Token.TYPE.LOGICAL_OPERATOR || |
| previousTokenType == Token.TYPE.LOGICAL_UNARY_OPERATOR; |
| } |
| } |
| |
| /** |
| * Logical Operator token handler |
| */ |
| private class LogicalOperatorTokenHandler extends TokenHandler { |
| @Override |
| public int _handleToken(ParseContext ctx) throws InvalidQueryException { |
| Token token = ctx.getTokens()[ctx.getCurrentTokensIndex()]; |
| LogicalOperator logicalOp = LogicalOperatorFactory.createOperator(token.getValue(), ctx.getPrecedenceLevel()); |
| ctx.updateMaxPrecedence(logicalOp.getPrecedence()); |
| ctx.addExpression(LogicalExpressionFactory.createLogicalExpression(logicalOp)); |
| |
| return 1; |
| } |
| |
| @Override |
| public boolean validate(Token.TYPE previousTokenType) { |
| return previousTokenType == Token.TYPE.VALUE_OPERAND || |
| previousTokenType == Token.TYPE.BRACKET_CLOSE; |
| } |
| } |
| |
| /** |
| * Logical Unary Operator token handler |
| */ |
| private class LogicalUnaryOperatorTokenHandler extends LogicalOperatorTokenHandler { |
| @Override |
| public boolean validate(Token.TYPE previousTokenType) { |
| return previousTokenType == null || |
| previousTokenType == Token.TYPE.BRACKET_OPEN || |
| previousTokenType == Token.TYPE.LOGICAL_OPERATOR; |
| } |
| } |
| |
| /** |
| * Property Operand token handler |
| */ |
| private class PropertyOperandTokenHandler extends TokenHandler { |
| @Override |
| public int _handleToken(ParseContext ctx) throws InvalidQueryException { |
| Token token = ctx.getTokens()[ctx.getCurrentTokensIndex()]; |
| ctx.getPrecedingExpression().setLeftOperand(token.getValue()); |
| |
| return 1; |
| } |
| |
| @Override |
| public boolean validate(Token.TYPE previousTokenType) { |
| return previousTokenType == Token.TYPE.RELATIONAL_OPERATOR || |
| previousTokenType == Token.TYPE.RELATIONAL_OPERATOR_FUNC; |
| } |
| } |
| |
| /** |
| * Value Operand token handler |
| */ |
| private class ValueOperandTokenHandler extends TokenHandler { |
| @Override |
| public int _handleToken(ParseContext ctx) throws InvalidQueryException { |
| Token token = ctx.getTokens()[ctx.getCurrentTokensIndex()]; |
| ctx.getPrecedingExpression().setRightOperand(token.getValue()); |
| |
| return 1; |
| } |
| |
| @Override |
| public boolean validate(Token.TYPE previousTokenType) { |
| return previousTokenType == Token.TYPE.PROPERTY_OPERAND; |
| } |
| } |
| } |
| |