/**
 * 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.hadoop.hbase.security.visibility;

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.apache.yetus.audience.InterfaceAudience;
import org.apache.hadoop.hbase.security.visibility.expression.ExpressionNode;
import org.apache.hadoop.hbase.security.visibility.expression.LeafExpressionNode;
import org.apache.hadoop.hbase.security.visibility.expression.NonLeafExpressionNode;
import org.apache.hadoop.hbase.security.visibility.expression.Operator;
import org.apache.hadoop.hbase.util.Bytes;

@InterfaceAudience.Private
public class ExpressionParser {

  private static final char CLOSE_PARAN = ')';
  private static final char OPEN_PARAN = '(';
  private static final char OR = '|';
  private static final char AND = '&';
  private static final char NOT = '!';
  private static final char SPACE = ' ';
  private static final char DOUBLE_QUOTES = '"';
  public ExpressionNode parse(String expS) throws ParseException {
    expS = expS.trim();
    Stack<ExpressionNode> expStack = new Stack<>();
    int index = 0;
    byte[] exp = Bytes.toBytes(expS);
    int endPos = exp.length;
    while (index < endPos) {
      byte b = exp[index];
      switch (b) {
        case OPEN_PARAN:
          processOpenParan(expStack, expS, index);
          index = skipSpaces(exp, index);
          break;
        case CLOSE_PARAN:
          processCloseParan(expStack, expS, index);
          index = skipSpaces(exp, index);
          break;
        case AND:
        case OR:
          processANDorOROp(getOperator(b), expStack, expS, index);
          index = skipSpaces(exp, index);
          break;
        case NOT:
          processNOTOp(expStack, expS, index);
          break;
        case DOUBLE_QUOTES:
          int labelOffset = ++index;
          // We have to rewrite the expression within double quotes as incase of expressions 
          // with escape characters we may have to avoid them as the original expression did
          // not have them
          List<Byte> list = new ArrayList<>();
          while (index < endPos && !endDoubleQuotesFound(exp[index])) {
            if (exp[index] == '\\') {
              index++;
              if (exp[index] != '\\' && exp[index] != '"')
                throw new ParseException("invalid escaping with quotes " + expS + " at column : "
                    + index);
            }
            list.add(exp[index]);
            index++;
          }
          // The expression has come to the end. still no double quotes found 
          if(index == endPos) {
            throw new ParseException("No terminating quotes " + expS + " at column : " + index);
          }
          // This could be costly. but do we have any alternative?
          // If we don't do this way then we may have to handle while checking the authorizations.
          // Better to do it here.
          byte[] array = org.apache.hbase.thirdparty.com.google.common.primitives.Bytes.toArray(list);
          String leafExp = Bytes.toString(array).trim();
          if (leafExp.isEmpty()) {
            throw new ParseException("Error parsing expression " + expS + " at column : " + index);
          }
          processLabelExpNode(new LeafExpressionNode(leafExp), expStack, expS, index);
          index = skipSpaces(exp, index);
          break;
        default:
          labelOffset = index;
          do {
            if (!VisibilityLabelsValidator.isValidAuthChar(exp[index])) {
              throw new ParseException("Error parsing expression " 
                 + expS + " at column : " + index);
            }
            index++;
          } while (index < endPos && !isEndOfLabel(exp[index]));
          leafExp =
              new String(exp, labelOffset, index - labelOffset, StandardCharsets.UTF_8).trim();
          if (leafExp.isEmpty()) {
            throw new ParseException("Error parsing expression " + expS + " at column : " + index);
          }
          processLabelExpNode(new LeafExpressionNode(leafExp), expStack, expS, index);
          // We already crossed the label node index. So need to reduce 1 here.
          index--;
          index = skipSpaces(exp, index);
      }
      index++;
    }
    if (expStack.size() != 1) {
      throw new ParseException("Error parsing expression " + expS);
    }
    ExpressionNode top = expStack.pop();
    if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
      throw new ParseException("Error parsing expression " + expS);
    }
    if (top instanceof NonLeafExpressionNode) {
      NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
      if (nlTop.getOperator() == Operator.NOT) {
        if (nlTop.getChildExps().size() != 1) {
          throw new ParseException("Error parsing expression " + expS);
        }
      } else if (nlTop.getChildExps().size() != 2) {
        throw new ParseException("Error parsing expression " + expS);
      }
    }
    return top;
  }

  private int skipSpaces(byte[] exp, int index) {
    while (index < exp.length -1 && exp[index+1] == SPACE) {
      index++;
    }
    return index;
  }

  private void processCloseParan(Stack<ExpressionNode> expStack, String expS, int index)
      throws ParseException {
    if (expStack.size() < 2) {
      // When ) comes we expect atleast a ( node and another leaf/non leaf node
      // in stack.
      throw new ParseException();
    } else {
      ExpressionNode top = expStack.pop();
      ExpressionNode secondTop = expStack.pop();
      // The second top must be a ( node and top should not be a ). Top can be
      // any thing else
      if (top == LeafExpressionNode.OPEN_PARAN_NODE
          || secondTop != LeafExpressionNode.OPEN_PARAN_NODE) {
        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
      }
      // a&(b|) is not valid.
      // The top can be a ! node but with exactly child nodes. !).. is invalid
      // Other NonLeafExpressionNode , then there should be exactly 2 child.
      // (a&) is not valid.
      if (top instanceof NonLeafExpressionNode) {
        NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
        if ((nlTop.getOperator() == Operator.NOT && nlTop.getChildExps().size() != 1)
            || (nlTop.getOperator() != Operator.NOT && nlTop.getChildExps().size() != 2)) {
          throw new ParseException("Error parsing expression " + expS + " at column : " + index);
        }
      }
      // When (a|b)&(c|d) comes while processing the second ) there will be
      // already (a|b)& node
      // avail in the stack. The top will be c|d node. We need to take it out
      // and combine as one
      // node.
      if (!expStack.isEmpty()) {
        ExpressionNode thirdTop = expStack.peek();
        if (thirdTop instanceof NonLeafExpressionNode) {
          NonLeafExpressionNode nlThirdTop = (NonLeafExpressionNode) expStack.pop();
          nlThirdTop.addChildExp(top);
          if (nlThirdTop.getOperator() == Operator.NOT) {
            // It is a NOT node. So there may be a NonLeafExpressionNode below
            // it to which the
            // completed NOT can be added now.
            if (!expStack.isEmpty()) {
              ExpressionNode fourthTop = expStack.peek();
              if (fourthTop instanceof NonLeafExpressionNode) {
                // Its Operator will be OR or AND
                NonLeafExpressionNode nlFourthTop = (NonLeafExpressionNode) fourthTop;
                assert nlFourthTop.getOperator() != Operator.NOT;
                // Also for sure its number of children will be 1
                assert nlFourthTop.getChildExps().size() == 1;
                nlFourthTop.addChildExp(nlThirdTop);
                return;// This case no need to add back the nlThirdTop.
              }
            }
          }
          top = nlThirdTop;
        }
      }
      expStack.push(top);
    }
  }

  private void processOpenParan(Stack<ExpressionNode> expStack, String expS, int index)
      throws ParseException {
    if (!expStack.isEmpty()) {
      ExpressionNode top = expStack.peek();
      // Top can not be a Label Node. a(.. is not valid. but ((a.. is fine.
      if (top instanceof LeafExpressionNode && top != LeafExpressionNode.OPEN_PARAN_NODE) {
        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
      } else if (top instanceof NonLeafExpressionNode) {
        // Top is non leaf.
        // It can be ! node but with out any child nodes. !a(.. is invalid
        // Other NonLeafExpressionNode , then there should be exactly 1 child.
        // a&b( is not valid.
        // a&( is valid though. Also !( is valid
        NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
        if ((nlTop.getOperator() == Operator.NOT && nlTop.getChildExps().size() != 0)
            || (nlTop.getOperator() != Operator.NOT && nlTop.getChildExps().size() != 1)) {
          throw new ParseException("Error parsing expression " + expS + " at column : " + index);
        }
      }
    }
    expStack.push(LeafExpressionNode.OPEN_PARAN_NODE);
  }

  private void processLabelExpNode(LeafExpressionNode node, Stack<ExpressionNode> expStack,
      String expS, int index) throws ParseException {
    if (expStack.isEmpty()) {
      expStack.push(node);
    } else {
      ExpressionNode top = expStack.peek();
      if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
        expStack.push(node);
      } else if (top instanceof NonLeafExpressionNode) {
        NonLeafExpressionNode nlTop = (NonLeafExpressionNode) expStack.pop();
        nlTop.addChildExp(node);
        if (nlTop.getOperator() == Operator.NOT && !expStack.isEmpty()) {
          ExpressionNode secondTop = expStack.peek();
          if (secondTop == LeafExpressionNode.OPEN_PARAN_NODE) {
            expStack.push(nlTop);
          } else if (secondTop instanceof NonLeafExpressionNode) {
            ((NonLeafExpressionNode) secondTop).addChildExp(nlTop);
          }
        } else {
          expStack.push(nlTop);
        }
      } else {
        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
      }
    }
  }

  private void processANDorOROp(Operator op, Stack<ExpressionNode> expStack, String expS, int index)
      throws ParseException {
    if (expStack.isEmpty()) {
      throw new ParseException("Error parsing expression " + expS + " at column : " + index);
    }
    ExpressionNode top = expStack.pop();
    if (top.isSingleNode()) {
      if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
      }
      expStack.push(new NonLeafExpressionNode(op, top));
    } else {
      NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
      if (nlTop.getChildExps().size() != 2) {
        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
      }
      expStack.push(new NonLeafExpressionNode(op, nlTop));
    }
  }

  private void processNOTOp(Stack<ExpressionNode> expStack, String expS, int index)
      throws ParseException {
    // When ! comes, the stack can be empty or top ( or top can be some exp like
    // a&
    // !!.., a!, a&b!, !a! are invalid
    if (!expStack.isEmpty()) {
      ExpressionNode top = expStack.peek();
      if (top.isSingleNode() && top != LeafExpressionNode.OPEN_PARAN_NODE) {
        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
      }
      if (!top.isSingleNode() && ((NonLeafExpressionNode) top).getChildExps().size() != 1) {
        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
      }
    }
    expStack.push(new NonLeafExpressionNode(Operator.NOT));
  }

  private static boolean endDoubleQuotesFound(byte b) {
    return (b == DOUBLE_QUOTES);
  }
  private static boolean isEndOfLabel(byte b) {
    return (b == OPEN_PARAN || b == CLOSE_PARAN || b == OR || b == AND || 
        b == NOT || b == SPACE);
  }

  private static Operator getOperator(byte op) {
    switch (op) {
    case AND:
      return Operator.AND;
    case OR:
      return Operator.OR;
    case NOT:
      return Operator.NOT;
    default:
      return null;
    }
  }
}