// 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.impala.analysis;

import static org.apache.impala.analysis.ToSqlOptions.DEFAULT;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Optional;
import java.util.Set;

import org.apache.impala.analysis.BinaryPredicate.Operator;
import org.apache.impala.catalog.BuiltinsDb;
import org.apache.impala.catalog.Function;
import org.apache.impala.catalog.Function.CompareMode;
import org.apache.impala.catalog.PrimitiveType;
import org.apache.impala.catalog.ScalarType;
import org.apache.impala.catalog.Type;
import org.apache.impala.catalog.TypeCompatibility;
import org.apache.impala.common.AnalysisException;
import org.apache.impala.common.InternalException;
import org.apache.impala.common.SqlCastException;
import org.apache.impala.common.TreeNode;
import org.apache.impala.rewrite.ExprRewriter;
import org.apache.impala.service.FeSupport;
import org.apache.impala.thrift.TColumnValue;
import org.apache.impala.thrift.TExplainLevel;
import org.apache.impala.thrift.TExpr;
import org.apache.impala.thrift.TExprNode;
import org.apache.impala.thrift.TFunction;
import org.apache.impala.util.MathUtil;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.google.common.base.Joiner;
import com.google.common.base.MoreObjects;
import com.google.common.base.Preconditions;
import com.google.common.base.Predicates;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;

/**
 * Root of the expr node hierarchy.
 */
abstract public class Expr extends TreeNode<Expr> implements ParseNode, Cloneable {
  private static final Logger LOG = LoggerFactory.getLogger(Expr.class);

  // Limits on the number of expr children and the depth of an expr tree. These maximum
  // values guard against crashes due to stack overflows (IMPALA-432) and were
  // experimentally determined to be safe.
  public static final int EXPR_CHILDREN_LIMIT = 10000;
  // The expr depth limit is mostly due to our recursive implementation of clone().
  public static final int EXPR_DEPTH_LIMIT = 1000;

  // Name of the function that needs to be implemented by every Expr that
  // supports negation.
  private static final String NEGATE_FN = "negate";

  // To be used where we cannot come up with a better estimate (selectivity_ is -1).
  public static final double DEFAULT_SELECTIVITY = 0.1;

  // The relative costs of different Exprs. These numbers are not intended as a precise
  // reflection of running times, but as simple heuristics for ordering Exprs from cheap
  // to expensive.
  // TODO(tmwarshall): Get these costs in a more principled way, eg. with a benchmark.
  public static final float ARITHMETIC_OP_COST = 1;
  public static final float BINARY_PREDICATE_COST = 1;
  public static final float VAR_LEN_BINARY_PREDICATE_COST = 5;
  public static final float COMPOUND_PREDICATE_COST = 1;
  public static final float FUNCTION_CALL_COST = 10;
  public static final float IS_NOT_EMPTY_COST = 1;
  public static final float IS_NULL_COST = 1;
  public static final float LIKE_COST = 10;
  public static final float LITERAL_COST = 1;
  public static final float SLOT_REF_COST = 1;
  public static final float TIMESTAMP_ARITHMETIC_COST = 5;
  public static final float UNKNOWN_COST = -1;

  // Arbitrary max exprs considered for constant propagation due to O(n^2) complexity.
  private static final int CONST_PROPAGATION_EXPR_LIMIT = 200;

  // To be used when estimating the cost of Exprs of type string where we don't otherwise
  // have an estimate of how long the strings produced by that Expr are.
  public static final int DEFAULT_AVG_STRING_LENGTH = 5;

  // returns true if an Expr is a non-analytic aggregate.
  public static final com.google.common.base.Predicate<Expr> IS_AGGREGATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof FunctionCallExpr &&
              ((FunctionCallExpr)arg).isAggregateFunction();
        }
      };

  // Returns true if an Expr is a NOT CompoundPredicate.
  public static final com.google.common.base.Predicate<Expr> IS_NOT_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof CompoundPredicate &&
              ((CompoundPredicate)arg).getOp() == CompoundPredicate.Operator.NOT;
        }
      };

  // Returns true if an Expr is an OR CompoundPredicate.
  public static final com.google.common.base.Predicate<Expr> IS_OR_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof CompoundPredicate &&
              ((CompoundPredicate)arg).getOp() == CompoundPredicate.Operator.OR;
        }
      };

  // Returns true if an Expr is a scalar subquery
  public static final com.google.common.base.Predicate<Expr> IS_SCALAR_SUBQUERY =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg.isScalarSubquery();
        }
      };

  // Returns true if an Expr has a subquery as a direct child.
  public static final com.google.common.base.Predicate<Expr> HAS_SUBQUERY_CHILD =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          for (Expr child : arg.getChildren()) {
            if (child instanceof Subquery) return true;
          }
          return false;
        }
      };

  // Returns true if an Expr is an aggregate function that returns non-null on
  // an empty set (e.g. count).
  public static final com.google.common.base.Predicate<Expr>
      NON_NULL_EMPTY_AGG = new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof FunctionCallExpr &&
              ((FunctionCallExpr)arg).returnsNonNullOnEmpty();
        }
      };

  // Returns true if an Expr is a builtin aggregate function.
  public static final com.google.common.base.Predicate<Expr> IS_BUILTIN_AGG_FN =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof FunctionCallExpr &&
              ((FunctionCallExpr)arg).getFnName().isBuiltin();
        }
      };

  // Returns true if an Expr is a user-defined aggregate function.
  public static final com.google.common.base.Predicate<Expr> IS_UDA_FN =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return IS_AGGREGATE.apply(arg) &&
              !((FunctionCallExpr)arg).getFnName().isBuiltin();
        }
      };

  public static final com.google.common.base.Predicate<Expr> IS_TRUE_LITERAL =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof BoolLiteral && ((BoolLiteral)arg).getValue();
        }
      };

  public static final com.google.common.base.Predicate<Expr> IS_FALSE_LITERAL =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof BoolLiteral && !((BoolLiteral)arg).getValue();
        }
      };

  public static final com.google.common.base.Predicate<Expr> IS_EQ_BINARY_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) { return BinaryPredicate.getEqSlots(arg) != null; }
      };

  public static final com.google.common.base.Predicate<Expr> IS_NOT_EQ_BINARY_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof BinaryPredicate
              && ((BinaryPredicate) arg).getOp() != Operator.EQ
              && ((BinaryPredicate) arg).getOp() != Operator.NOT_DISTINCT;
        }
      };

  public static final com.google.common.base.Predicate<Expr> IS_BINARY_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) { return arg instanceof BinaryPredicate; }
      };

  public static final com.google.common.base.Predicate<Expr>
    IS_EXPR_EQ_LITERAL_PREDICATE = new com.google.common.base.Predicate<Expr>() {
    @Override
    public boolean apply(Expr arg) {
      return arg instanceof BinaryPredicate
          && ((BinaryPredicate) arg).getOp() == Operator.EQ
          && IS_LITERAL.apply(((BinaryPredicate) arg).getChild(1));
    }
  };

  public static final com.google.common.base.Predicate<Expr>
      IS_NONDETERMINISTIC_BUILTIN_FN_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof FunctionCallExpr
              && ((FunctionCallExpr) arg).isNondeterministicBuiltinFn();
        }
      };

  public static final com.google.common.base.Predicate<Expr> IS_UDF_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof FunctionCallExpr
              && !((FunctionCallExpr) arg).getFnName().isBuiltin();
        }
      };

  /**
   * @return true if the expression is a literal.
   */
  public static final com.google.common.base.Predicate<Expr> IS_LITERAL =
    new com.google.common.base.Predicate<Expr>() {
      @Override
      public boolean apply(Expr arg) {
        return arg instanceof LiteralExpr;
      }
    };

  /**
   * @return true if the expression is a null literal.
   */
  public static final com.google.common.base.Predicate<Expr> IS_NULL_LITERAL =
    new com.google.common.base.Predicate<Expr>() {
      @Override
      public boolean apply(Expr arg) {
        return arg instanceof NullLiteral;
      }
    };

  /**
   * @return true if the expression is a literal value other than NULL.
   */
  public static final com.google.common.base.Predicate<Expr> IS_NON_NULL_LITERAL =
    new com.google.common.base.Predicate<Expr>() {
      @Override
      public boolean apply(Expr arg) {
        return IS_LITERAL.apply(arg) && !IS_NULL_LITERAL.apply(arg);
      }
    };

  /**
   * @return true if the expression is a null literal, or a
   * cast of a null (as created by the ConstantFoldingRule.)
   */
  public static final com.google.common.base.Predicate<Expr> IS_NULL_VALUE =
    new com.google.common.base.Predicate<Expr>() {
      @Override
      public boolean apply(Expr arg) {
        if (arg instanceof NullLiteral) return true;
        if (! (arg instanceof CastExpr)) return false;
        return IS_NULL_VALUE.apply(((CastExpr) arg).getChild(0));
      }
    };

  /**
   * @return true if the expression is a  literal, or a
   * cast of a null (as created by the ConstantFoldingRule.)
   */
  public static final com.google.common.base.Predicate<Expr> IS_LITERAL_VALUE =
    new com.google.common.base.Predicate<Expr>() {
      @Override
      public boolean apply(Expr arg) {
        return IS_LITERAL.apply(arg) || IS_NULL_VALUE.apply(arg);
      }
    };

  public static final com.google.common.base.Predicate<Expr> IS_INT_LITERAL =
    new com.google.common.base.Predicate<Expr>() {
      @Override
      public boolean apply(Expr arg) {
        return IS_LITERAL.apply(arg) && arg.getType().isIntegerType();
      }
    };

  public static final com.google.common.base.Predicate<Expr>
    IS_CONDITIONAL_BUILTIN_FN_PREDICATE =
    new com.google.common.base.Predicate<Expr>() {
      @Override
      public boolean apply(Expr arg) {
        return arg instanceof FunctionCallExpr
            && ((FunctionCallExpr) arg).isConditionalBuiltinFn();
      }
    };

  public static final com.google.common.base.Predicate<Expr> IS_IS_NULL_PREDICATE =
    new com.google.common.base.Predicate<Expr>() {
      @Override
      public boolean apply(Expr arg) {
        return arg instanceof IsNullPredicate
            && !((IsNullPredicate) arg).isNotNull();
      }
    };

  public static final com.google.common.base.Predicate<Expr>
    IS_DISTINCT_FROM_OR_NOT_DISTINCT_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof BinaryPredicate
              && (((BinaryPredicate) arg).getOp() == Operator.DISTINCT_FROM
              || ((BinaryPredicate) arg).getOp() == Operator.NOT_DISTINCT);
        }
      };

  public static final com.google.common.base.Predicate<Expr> IS_CASE_EXPR_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof CaseExpr;
        }
      };

  public static final com.google.common.base.Predicate<Expr> IS_ALWAYS_TRUE_PREDICATE =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof Predicate
              && ((Predicate) arg).hasAlwaysTrueHint();
        }
      };

  // Returns true if an Expr is a builtin sleep function.
  public static final com.google.common.base.Predicate<Expr> IS_FN_SLEEP =
      new com.google.common.base.Predicate<Expr>() {
        @Override
        public boolean apply(Expr arg) {
          return arg instanceof FunctionCallExpr
              && ((FunctionCallExpr) arg).getFnName().isBuiltin()
              && ((FunctionCallExpr) arg).getFnName().getFunction() != null
              && ((FunctionCallExpr) arg).getFnName().getFunction().equals("sleep");
        }
      };

  // id that's unique across the entire query statement and is assigned by
  // Analyzer.registerConjuncts(); only assigned for the top-level terms of a
  // conjunction, and therefore null for most Exprs
  protected ExprId id_;

  // true if Expr is an auxiliary predicate that was generated by the plan generation
  // process to facilitate predicate propagation;
  // false if Expr originated with a query stmt directly
  private boolean isAuxExpr_ = false;

  protected Type type_;  // result of analysis

  protected boolean isOnClauseConjunct_; // set by analyzer

  // Flag to indicate whether to wrap this expr's toSql() in parenthesis. Set by parser.
  // Needed for properly capturing expr precedences in the SQL string.
  protected boolean printSqlInParens_ = false;

  // Estimated probability of a predicate evaluating to true. Set during analysis.
  // Between 0 and 1, or set to -1 if the selectivity could not be estimated.
  protected double selectivity_;

  // Estimated relative cost of evaluating this expression, including the costs of
  // its children. Set during analysis and used to sort conjuncts within a PlanNode.
  // Has a default value of -1 indicating unknown cost if the cost of this expression
  // or any of its children was not set, but it is required to be set for any
  // expression which may be part of a conjunct.
  protected float evalCost_;

  // estimated number of distinct values produced by Expr; invalid: -1
  // set during analysis
  protected long numDistinctValues_;

  // Cached value of IsConstant(), set during analyze() and valid if isAnalyzed_ is true.
  private boolean isConstant_;

  // The function to call. This can either be a scalar or aggregate function.
  // Set in analyze().
  protected Function fn_;

  // True after analysis successfully completed. Protected by accessors isAnalyzed() and
  // analysisDone().
  private boolean isAnalyzed_ = false;
  private boolean isRewritten_ = false;


  // True if this has already been counted towards the number of statement expressions
  private boolean isCountedForNumStmtExprs_ = false;

  // For exprs of type Predicate, this keeps track of predicate hints
  protected List<PlanHint> predicateHints_;

  // Is codegen disabled for this expression ?
  private boolean isCodegenDisabled_ = false;

  protected Expr() {
    type_ = Type.INVALID;
    selectivity_ = -1.0;
    evalCost_ = -1.0f;
    numDistinctValues_ = -1;
  }

  /**
   * Copy c'tor used in clone().
   */
  protected Expr(Expr other) {
    id_ = other.id_;
    isAuxExpr_ = other.isAuxExpr_;
    type_ = other.type_;
    isAnalyzed_ = other.isAnalyzed_;
    isRewritten_ = other.isRewritten_;
    isOnClauseConjunct_ = other.isOnClauseConjunct_;
    printSqlInParens_ = other.printSqlInParens_;
    selectivity_ = other.selectivity_;
    evalCost_ = other.evalCost_;
    numDistinctValues_ = other.numDistinctValues_;
    isConstant_ = other.isConstant_;
    fn_ = other.fn_;
    isCountedForNumStmtExprs_ = other.isCountedForNumStmtExprs_;
    children_ = Expr.cloneList(other.children_);
    if (other.predicateHints_ != null) {
      predicateHints_ = new ArrayList<>();
      predicateHints_.addAll(other.predicateHints_);
    }
    isCodegenDisabled_ = other.isCodegenDisabled_;
  }

  public boolean isAnalyzed() { return isAnalyzed_; }
  public boolean isRewritten() { return isRewritten_; }
  public void setRewritten(boolean isRewritten) { isRewritten_ = isRewritten; }
  public ExprId getId() { return id_; }
  protected void setId(ExprId id) { id_ = id; }
  public Type getType() { return type_; }
  public double getSelectivity() { return selectivity_; }
  public boolean hasSelectivity() { return selectivity_ >= 0; }
  public float getCost() {
    Preconditions.checkState(isAnalyzed_);
    return evalCost_;
  }
  public boolean hasCost() { return evalCost_ >= 0; }
  public long getNumDistinctValues() { return numDistinctValues_; }
  public boolean getPrintSqlInParens() { return printSqlInParens_; }
  public void setPrintSqlInParens(boolean b) { printSqlInParens_ = b; }
  public boolean isOnClauseConjunct() { return isOnClauseConjunct_; }
  public void setIsOnClauseConjunct(boolean b) { isOnClauseConjunct_ = b; }
  public boolean isAuxExpr() { return isAuxExpr_; }
  public void setIsAuxExpr() { isAuxExpr_ = true; }
  public Function getFn() { return fn_; }
  public void disableCodegen() {
    isCodegenDisabled_ = true;
    for (Expr child : children_) {
      child.disableCodegen();
    }
  }

  /**
   * Perform semantic analysis of node and all of its children.
   * Throws exception if any errors found.
   * @see ParseNode#analyze(Analyzer)
   */
  // TODO: Analyze for expressions should return a possibly-rewritten
  // expression, leaving the StmtNode version to analyze statements
  // in-place.
  public final void analyze(Analyzer analyzer) throws AnalysisException {
    if (isAnalyzed()) return;

    // Check the expr child limit.
    if (children_.size() > EXPR_CHILDREN_LIMIT) {
      String sql = toSql();
      String sqlSubstr = sql.substring(0, Math.min(80, sql.length()));
      throw new AnalysisException(String.format("Exceeded the maximum number of child " +
          "expressions (%s).\nExpression has %s children:\n%s...",
          EXPR_CHILDREN_LIMIT, children_.size(), sqlSubstr));
    }

    // analyzer may be null for certain literal constructions (e.g. IntLiteral).
    if (analyzer != null) {
      analyzer.incrementCallDepth();
      // Check the expr depth limit. Do not print the toSql() to not overflow the stack.
      if (analyzer.getCallDepth() > EXPR_DEPTH_LIMIT) {
        throw new AnalysisException(String.format("Exceeded the maximum depth of an " +
            "expression tree (%s).", EXPR_DEPTH_LIMIT));
      }
      incrementNumStmtExprs(analyzer);
    }
    for (Expr child: children_) {
      child.analyze(analyzer);
    }
    if (analyzer != null) analyzer.decrementCallDepth();
    computeNumDistinctValues();

    // Do all the analysis for the expr subclass before marking the Expr analyzed.
    analyzeImpl(analyzer);
    evalCost_ = computeEvalCost();
    analysisDone();
  }

  protected void analyzeHints(Analyzer analyzer) throws AnalysisException {
    if (predicateHints_ != null && !predicateHints_.isEmpty()) {
      if (!(this instanceof Predicate)) {
        throw new AnalysisException("Expr hints are only supported for predicates");
      }
      for (PlanHint hint : predicateHints_) {
        if (hint.is("ALWAYS_TRUE")) {
          ((Predicate) this).setHasAlwaysTrueHint(true);
          // If the top level expr has always_true hint, its conjuncts must
          // also have the same hint (note that there's a TODO in the parser
          // grammar to allow hints on a per expr basis).
          List<Expr> conjuncts = getConjuncts();
          if (conjuncts.size() > 1) {
            for (Expr e : conjuncts) ((Predicate) e).setHasAlwaysTrueHint(true);
          }
          analyzer.setHasPlanHints();
        } else {
          analyzer.addWarning("Predicate hint not recognized: " + hint);
        }
      }
    }
  }

  /**
   * Does subclass-specific analysis. Subclasses should override analyzeImpl().
   */
  abstract protected void analyzeImpl(Analyzer analyzer) throws AnalysisException;

  /**
   * Helper function to analyze this expr and assert that the analysis was successful.
   * TODO: This function could be used in many more places to clean up. Consider
   * adding an IAnalyzable interface or similar to and move this helper into Analyzer
   * such that non-Expr things can use the helper also.
   */
  public void analyzeNoThrow(Analyzer analyzer) {
    try {
      analyze(analyzer);
    } catch (AnalysisException e) {
      throw new IllegalStateException(e);
    }
  }

  /**
   * Helper function to properly count the number of statement expressions.
   * If this expression has not been counted already and this is not a WITH clause,
   * increment the number of statement expressions. This function guarantees that an
   * expression will be counted at most once.
   */
  private void incrementNumStmtExprs(Analyzer analyzer) {
    // WITH clauses use a separate Analyzer with its own GlobalState. Skip counting
    // this expression towards that GlobalState. If the view defined by the WITH
    // clause is referenced, it will be counted during that analysis.
    if (analyzer.hasWithClause()) return;
    // If the expression is already counted, do not count it again. This is important
    // for expressions that can be cloned (e.g. when doing Expr::trySubstitute()).
    if (isCountedForNumStmtExprs_) return;
    analyzer.incrementNumStmtExprs();
    isCountedForNumStmtExprs_ = true;
  }

  /**
   * Compute and return evalcost of this expr given the evalcost of all children has been
   * computed. Should be called bottom-up whenever the structure of subtree is modified.
   */
  abstract protected float computeEvalCost();

  protected void computeNumDistinctValues() {
    if (isConstant()) {
      numDistinctValues_ = 1;
    } else {
      numDistinctValues_ = -1;

      // get the max number of distinct values over all children of this node
      for (Expr child: children_) {
        // A constant should not override a -1 from a SlotRef, so we only consider
        // non-constant expressions. This is functionally similar to considering
        // only the SlotRefs, except that it allows an Expr to override the values
        // that come out of its children.
        if (!child.isConstant()) {
          numDistinctValues_ = Math.max(numDistinctValues_, child.getNumDistinctValues());
        }
      }
    }
  }

  /**
   * Collects the returns types of the child nodes in an array.
   */
  protected Type[] collectChildReturnTypes() {
    Type[] childTypes = new Type[children_.size()];
    for (int i = 0; i < children_.size(); ++i) {
      childTypes[i] = children_.get(i).type_;
    }
    return childTypes;
  }

  /**
   * Looks up in the catalog the builtin for 'name' and 'argTypes'.
   * Returns null if the function is not found.
   */
  protected Function getBuiltinFunction(Analyzer analyzer, String name,
      Type[] argTypes, CompareMode mode) throws AnalysisException {
    FunctionName fnName = new FunctionName(BuiltinsDb.NAME, name);
    Function searchDesc = new Function(fnName, argTypes, Type.INVALID, false);
    return analyzer.getCatalog().getFunction(searchDesc, mode);
  }

  /**
   * Generates the necessary casts for the children of this expr to call fn_.
   * child(0) is cast to the function's first argument, child(1) to the second etc.
   *
   * If ignoreWildcardDecimals is true, the function will not cast arguments that
   * are wildcard decimals. This is used for builtins where the cast is done within
   * the BE function.
   * Otherwise, if the function signature contains wildcard decimals, each wildcard child
   * argument will be cast to the highest resolution that can contain all of the child
   * wildcard arguments.
   * e.g. fn(decimal(*), decimal(*))
   *      called with fn(decimal(10,2), decimal(5,3))
   * both children will be cast to (11, 3).
   *
   * 'compatibility' defines the mode of wildcard type resolution;
   * if TypeCompatibility.isStrictDecimal() is true, it only considers casts that result
   * in no loss of information, if 'compatibility' is DEFAULT it does not guarantee
   * decimal cast without information loss.
   */
  protected void castForFunctionCall(boolean ignoreWildcardDecimals,
      TypeCompatibility compatibility) throws AnalysisException {
    Preconditions.checkState(fn_ != null);
    Type[] fnArgs = fn_.getArgs();
    Type resolvedWildcardType = getResolvedWildCardType(compatibility);
    if (resolvedWildcardType != null) {
      if (resolvedWildcardType.isNull()) {
        throw new SqlCastException(String.format(
            "Cannot resolve DECIMAL precision and scale from NULL type in %s function.",
            fn_.getFunctionName().getFunction()));
      }
      if (resolvedWildcardType.isInvalid() && !ignoreWildcardDecimals) {
        StringBuilder argTypes = new StringBuilder();
        for (int j = 0; j < children_.size(); ++j) {
          if (argTypes.length() > 0) argTypes.append(", ");
          Type childType = children_.get(j).type_;
          argTypes.append(childType.toSql());
        }
        throw new SqlCastException(String.format(
            "Cannot resolve DECIMAL types of the %s(%s) function arguments. You need " +
            "to wrap the arguments in a CAST.", fn_.getFunctionName().getFunction(),
            argTypes.toString()));
      }
    }
    for (int i = 0; i < children_.size(); ++i) {
      // For varargs, we must compare with the last type in fnArgs.argTypes.
      int ix = Math.min(fnArgs.length - 1, i);
      if (fnArgs[ix].isWildcardDecimal()) {
        if (children_.get(i).type_.isDecimal() && ignoreWildcardDecimals) continue;
        if (children_.get(i).type_.isDecimal() || !ignoreWildcardDecimals) {
          Preconditions.checkState(resolvedWildcardType != null);
          Preconditions.checkState(!resolvedWildcardType.isInvalid());
          if (!children_.get(i).type_.equals(resolvedWildcardType)) {
            castChild(resolvedWildcardType, i);
          }
        } else if (children_.get(i).type_.isNull()) {
          castChild(ScalarType.createDecimalType(), i);
        } else {
          Preconditions.checkState(children_.get(i).type_.isScalarType());
          // It is safe to assign an arbitrary decimal here only if the backend function
          // can handle it (in which case ignoreWildcardDecimals is true).
          Preconditions.checkState(ignoreWildcardDecimals);
          castChild(((ScalarType) children_.get(i).type_).getMinResolutionDecimal(), i);
        }
      } else if (!children_.get(i).type_.matchesType(fnArgs[ix])) {
        castChild(fnArgs[ix], i);
      }
    }
  }

  /**
   * Returns the max resolution type of all the wild card decimal types.
   * Returns null if there are no wild card types. If compatibility.isStrictDecimal() is
   * true, it will return an invalid type if it is not possible to come up with a decimal
   * type that is guaranteed to not lose information.
   */
  Type getResolvedWildCardType(TypeCompatibility compatibility) {
    Preconditions.checkState(compatibility.equals(TypeCompatibility.DEFAULT)
        || compatibility.equals(TypeCompatibility.STRICT_DECIMAL));
    Type result = null;
    Type[] fnArgs = fn_.getArgs();
    for (int i = 0; i < children_.size(); ++i) {
      // For varargs, we must compare with the last type in fnArgs.argTypes.
      int ix = Math.min(fnArgs.length - 1, i);
      if (!fnArgs[ix].isWildcardDecimal()) continue;

      Type childType = children_.get(i).type_;
      Preconditions.checkState(!childType.isWildcardDecimal(),
          "Child expr should have been resolved.");
      Preconditions.checkState(childType.isScalarType(),
          "Function should not have resolved with a non-scalar child type.");
      if (result == null) {
        ScalarType decimalType = (ScalarType) childType;
        result = decimalType.getMinResolutionDecimal();
      } else {
        result = Type.getAssignmentCompatibleType(result, childType, compatibility);
      }
    }
    if (result != null && !result.isNull()) {
      result = ((ScalarType)result).getMinResolutionDecimal();
      Preconditions.checkState(result.isDecimal() || result.isInvalid());
      Preconditions.checkState(!result.isWildcardDecimal());
    }
    return result;
  }

  /**
   * Returns true if e is a CastExpr and the target type is a decimal.
   */
  private boolean isExplicitCastToDecimal(Expr e) {
    if (!(e instanceof CastExpr)) return false;
    CastExpr c = (CastExpr)e;
    return !c.isImplicit() && c.getType().isDecimal();
  }

  /**
   * Returns a clone of child with all decimal-typed NumericLiterals in it explicitly
   * cast to targetType.
   */
  private Expr convertDecimalLiteralsToFloat(Analyzer analyzer, Expr child,
      Type targetType) throws AnalysisException {
    if (!targetType.isFloatingPointType() && !targetType.isIntegerType()) return child;
    if (targetType.isIntegerType()) targetType = Type.DOUBLE;
    List<NumericLiteral> literals = new ArrayList<>();
    child.collectAll(Predicates.instanceOf(NumericLiteral.class), literals);
    ExprSubstitutionMap smap = new ExprSubstitutionMap();
    for (NumericLiteral l: literals) {
      if (!l.getType().isDecimal()) continue;
      NumericLiteral castLiteral = (NumericLiteral) l.clone();
      castLiteral.explicitlyCastToFloat(targetType);
      smap.put(l, castLiteral);
    }
    return child.substitute(smap, analyzer, false);
  }

  /**
   * DECIMAL_V1:
   * ----------
   * This function applies a heuristic that casts literal child exprs of this expr from
   * decimal to floating point in certain circumstances to reduce processing cost. In
   * earlier versions of Impala's decimal support, it was much slower than floating point
   * arithmetic. The original rationale for the automatic casting follows.
   *
   * Decimal has a higher processing cost than floating point and we should not pay
   * the cost if the user does not require the accuracy. For example:
   * "select float_col + 1.1" would start out with 1.1 as a decimal(2,1) and the
   * float_col would be promoted to a high accuracy decimal. This function will identify
   * this case and treat 1.1 as a float.
   * In the case of "decimal_col + 1.1", 1.1 would remain a decimal.
   * In the case of "float_col + cast(1.1 as decimal(2,1))", the result would be a
   * decimal.
   *
   * Another way to think about it is that DecimalLiterals are analyzed as returning
   * decimals (of the narrowest precision/scale) and we later convert them to a floating
   * point type according to a heuristic that attempts to guess what the user intended.
   *
   * DECIMAL_V2:
   * ----------
   * This function does nothing. All decimal numeric literals are interpreted as decimals
   * and the normal expression typing rules apply.
   */
  protected void convertNumericLiteralsFromDecimal(Analyzer analyzer)
      throws AnalysisException {
    Preconditions.checkState(this instanceof ArithmeticExpr ||
        this instanceof BinaryPredicate);
    // This heuristic conversion is not part of DECIMAL_V2.
    if (analyzer.getQueryOptions().isDecimal_v2()) return;
    if (getChildCount() == 1) return; // Do not attempt to convert for unary ops
    Preconditions.checkState(getChildCount() == 2);
    Type t0 = getChild(0).getType();
    Type t1 = getChild(1).getType();
    boolean c0IsConstantDecimal = getChild(0).isConstant() && t0.isDecimal();
    boolean c1IsConstantDecimal = getChild(1).isConstant() && t1.isDecimal();
    if (c0IsConstantDecimal && c1IsConstantDecimal) return;
    if (!c0IsConstantDecimal && !c1IsConstantDecimal) return;

    // Only child(0) or child(1) is a const decimal. See if we can cast it to
    // the type of the other child.
    if (c0IsConstantDecimal && !isExplicitCastToDecimal(getChild(0))) {
      Expr c0 = convertDecimalLiteralsToFloat(analyzer, getChild(0), t1);
      setChild(0, c0);
    }
    if (c1IsConstantDecimal && !isExplicitCastToDecimal(getChild(1))) {
      Expr c1 = convertDecimalLiteralsToFloat(analyzer, getChild(1), t0);
      setChild(1, c1);
    }
  }

  /**
   * Helper function: analyze list of exprs
   */
  public static void analyze(List<? extends Expr> exprs, Analyzer analyzer)
      throws AnalysisException {
    if (exprs == null) return;
    for (Expr expr: exprs) {
      expr.analyze(analyzer);
    }
  }

  @Override
  public final String toSql() {
    return toSql(DEFAULT);
  }

  /**
   * Some expression nodes are also statement-like and know about
   * before/after rewrite expressions.
   */
  @Override
  public String toSql(ToSqlOptions options) {
    return (printSqlInParens_) ? "(" + toSqlImpl(options) + ")" : toSqlImpl(options);
  }

  /**
   * Returns a SQL string representing this expr. Subclasses should override this method
   * instead of toSql() to ensure that parenthesis are properly added around the toSql().
   */
  protected abstract String toSqlImpl(ToSqlOptions options);

  protected String toSqlImpl() { return toSqlImpl(DEFAULT); };

  // Convert this expr, including all children, to its Thrift representation.
  public TExpr treeToThrift() {
    if (type_.isNull()) {
      // Hack to ensure BE never sees TYPE_NULL. If an expr makes it this far without
      // being cast to a non-NULL type, the type doesn't matter and we can cast it
      // arbitrarily.
      Preconditions.checkState(IS_NULL_LITERAL.apply(this) ||
          this instanceof SlotRef);
      return NullLiteral.create(ScalarType.BOOLEAN).treeToThrift();
    }
    TExpr result = new TExpr();
    treeToThriftHelper(result);
    return result;
  }

  // Append a flattened version of this expr, including all children, to 'container'.
  protected void treeToThriftHelper(TExpr container) {
    Preconditions.checkState(isAnalyzed_,
        "Must be analyzed before serializing to thrift. %s", this);
    Preconditions.checkState(!type_.isWildcardDecimal());
    // The BE should never see TYPE_NULL
    Preconditions.checkState(!type_.isNull(), "Expr has type null!");
    TExprNode msg = new TExprNode();
    msg.type = type_.toThrift();
    msg.is_constant = isConstant_;
    msg.num_children = children_.size();
    msg.setIs_codegen_disabled(isCodegenDisabled_);
    if (fn_ != null) {
      TFunction thriftFn = fn_.toThrift();
      thriftFn.setLast_modified_time(fn_.getLastModifiedTime());
      msg.setFn(thriftFn);
      if (fn_.hasVarArgs()) msg.setVararg_start_idx(fn_.getNumArgs() - 1);
    }
    toThrift(msg);
    container.addToNodes(msg);
    for (Expr child: children_) {
      child.treeToThriftHelper(container);
    }
  }

  // Convert this expr into msg (excluding children), which requires setting
  // msg.op as well as the expr-specific field.
  protected abstract void toThrift(TExprNode msg);

  /**
   * Returns the product of the given exprs' number of distinct values or -1 if any of
   * the exprs have an invalid number of distinct values. Uses saturating arithmetic,
   * so that if the product would overflow, return Long.MAX_VALUE.
   */
  public static long getNumDistinctValues(List<Expr> exprs) {
    if (exprs == null || exprs.isEmpty()) return 0;
    long numDistinctValues = 1;
    for (Expr expr: exprs) {
      if (expr.getNumDistinctValues() == -1) {
        numDistinctValues = -1;
        break;
      }
      numDistinctValues = MathUtil.saturatingMultiply(
          numDistinctValues, expr.getNumDistinctValues());
    }
    return numDistinctValues;
  }

  public static List<TExpr> treesToThrift(List<? extends Expr> exprs) {
    List<TExpr> result = new ArrayList<>();
    for (Expr expr: exprs) {
      result.add(expr.treeToThrift());
    }
    return result;
  }

  public boolean isAggregate() {
    return IS_AGGREGATE.apply(this);
  }

  public List<String> childrenToSql(ToSqlOptions options) {
    List<String> result = new ArrayList<>();
    for (Expr child: children_) {
      result.add(child.toSql(options));
    }
    return result;
  }

  public String debugString() {
    return (id_ != null ? "exprid=" + id_.toString() + " " : "") + debugString(children_);
  }

  public static String debugString(List<? extends Expr> exprs) {
    if (exprs == null || exprs.isEmpty()) return "";
    List<String> strings = new ArrayList<>();
    for (Expr expr: exprs) {
      strings.add(expr.debugString());
    }
    return Joiner.on(" ").join(strings);
  }

  public static String toSql(List<? extends Expr> exprs, ToSqlOptions options) {
    if (exprs == null || exprs.isEmpty()) return "";
    List<String> strings = new ArrayList<>();
    for (Expr expr: exprs) {
      strings.add(expr.toSql(options));
    }
    return Joiner.on(", ").join(strings);
  }

  /**
   * Returns true if this expr matches 'that'. Two exprs match if:
   * 1. The tree structures ignoring implicit casts are the same.
   * 2. For every pair of corresponding SlotRefs, slotRefCmp.matches() returns true.
   * 3. For every pair of corresponding non-SlotRef exprs, localEquals() returns true.
   */
  public boolean matches(Expr that, SlotRef.Comparator slotRefCmp) {
    if (that == null) return false;
    if (this instanceof CastExpr && ((CastExpr)this).isImplicit()) {
      return children_.get(0).matches(that, slotRefCmp);
    }
    if (that instanceof CastExpr && ((CastExpr)that).isImplicit()) {
      return matches(((CastExpr) that).children_.get(0), slotRefCmp);
    }
    if (this instanceof SlotRef && that instanceof SlotRef) {
      return slotRefCmp.matches((SlotRef)this, (SlotRef)that);
    }
    if (!localEquals(that)) return false;
    if (children_.size() != that.children_.size()) return false;
    for (int i = 0; i < children_.size(); ++i) {
      if (!children_.get(i).matches(that.children_.get(i), slotRefCmp)) return false;
    }
    return true;
  }

  /**
   * Local eq comparator. Returns true if this expr is equal to 'that' ignoring children.
   */
  protected boolean localEquals(Expr that) {
    return getClass() == that.getClass() &&
        (fn_ == null ? that.fn_ == null : fn_.equals(that.fn_));
  }

  /**
   * Returns true if two expressions are equal. The equality comparison works on analyzed
   * as well as unanalyzed exprs by ignoring implicit casts.
   */
  @Override
  public final boolean equals(Object obj) {
    return obj instanceof Expr && matches((Expr) obj, SlotRef.SLOTREF_EQ_CMP);
  }

  /**
   * Return true if l1[i].equals(l2[i]) for all i.
   */
  public static <C extends Expr> boolean equalLists(List<C> l1, List<C> l2) {
    if (l1.size() != l2.size()) return false;
    Iterator<C> l1Iter = l1.iterator();
    Iterator<C> l2Iter = l2.iterator();
    while (l1Iter.hasNext()) {
      if (!l1Iter.next().equals(l2Iter.next())) return false;
    }
    return true;
  }

  /**
   * Return true if l1 equals l2 when both lists are interpreted as sets.
   * TODO: come up with something better than O(n^2)?
   */
  public static <C extends Expr> boolean equalSets(List<C> l1, List<C> l2) {
    if (l1.size() != l2.size()) return false;
    return l1.containsAll(l2) && l2.containsAll(l1);
  }

  /**
   * Return true if l1 is a subset of l2.
   */
  public static <C extends Expr> boolean isSubset(List<C> l1, List<C> l2) {
    if (l1.size() > l2.size()) return false;
    return l2.containsAll(l1);
  }

  /**
   * Return the intersection of l1 and l2.
   */
  public static <C extends Expr> List<C> intersect(List<C> l1, List<C> l2) {
    List<C> result = new ArrayList<>();
    for (C element: l1) {
      if (l2.contains(element)) result.add(element);
    }
    return result;
  }

  @Override
  public int hashCode() {
    if (id_ == null) {
      throw new UnsupportedOperationException(
          "Expr.hashCode() is not implemented in " + this.getClass().getName());
    } else {
      return id_.asInt();
    }
  }

  /**
   * Gather conjuncts from this expr and return them in a list.
   * A conjunct is an expr that returns a boolean, e.g., Predicates, function calls,
   * SlotRefs, etc. Hence, this method is placed here and not in Predicate.
   */
  public List<Expr> getConjuncts() {
    List<Expr> list = new ArrayList<>();
    if (this instanceof CompoundPredicate
        && ((CompoundPredicate) this).getOp() == CompoundPredicate.Operator.AND) {
      // TODO: we have to convert CompoundPredicate.AND to two expr trees for
      // conjuncts because NULLs are handled differently for CompoundPredicate.AND
      // and conjunct evaluation.  This is not optimal for jitted exprs because it
      // will result in two functions instead of one. Create a new CompoundPredicate
      // Operator (i.e. CONJUNCT_AND) with the right NULL semantics and use that
      // instead
      list.addAll((getChild(0)).getConjuncts());
      list.addAll((getChild(1)).getConjuncts());
    } else {
      list.add(this);
    }
    return list;
  }

  /**
   * Returns true if this expression is trivially true. Currently we only check if
   * it is comprised of conjuncts that are all TRUE literals.
   */
  public boolean isTriviallyTrue() {
    for (Expr conjunct : getConjuncts()) {
      if (!Expr.IS_TRUE_LITERAL.apply(conjunct)) return false;
    }
    return true;
  }

  /**
   * Returns an analyzed clone of 'this' with exprs substituted according to smap.
   * Removes implicit casts and analysis state while cloning/substituting exprs within
   * this tree, such that the returned result has minimal implicit casts and types.
   * Throws if analyzing the post-substitution expr tree failed.
   * If smap is null, this function is equivalent to clone().
   * If preserveRootType is true, the resulting expr tree will be cast if necessary to
   * the type of 'this'.
   */
  public Expr trySubstitute(ExprSubstitutionMap smap, Analyzer analyzer,
      boolean preserveRootType)
      throws AnalysisException {
    Expr result = clone();
    // Return clone to avoid removing casts.
    if (smap == null) return result;
    result = result.substituteImpl(smap, analyzer);
    result.analyze(analyzer);
    if (preserveRootType && !type_.equals(result.getType())) {
      if (this instanceof CastExpr) {
        CastExpr thisCastExpr = (CastExpr) this;
        TypeCompatibility compatibility = thisCastExpr.getCompatibility();
        return result.castTo(type_, compatibility);
      }
      return result.castTo(type_);
    }
    return result;
  }

  /**
   * Returns an analyzed clone of 'this' with exprs substituted according to smap.
   * Removes implicit casts and analysis state while cloning/substituting exprs within
   * this tree, such that the returned result has minimal implicit casts and types.
   * Expects the analysis of the post-substitution expr to succeed.
   * If smap is null, this function is equivalent to clone().
   * If preserveRootType is true, the resulting expr tree will be cast if necessary to
   * the type of 'this'.
   */
  public Expr substitute(ExprSubstitutionMap smap, Analyzer analyzer,
      boolean preserveRootType) {
    try {
      return trySubstitute(smap, analyzer, preserveRootType);
    } catch (Exception e) {
      throw new IllegalStateException("Failed analysis after expr substitution.", e);
    }
  }

  public static List<Expr> trySubstituteList(Iterable<? extends Expr> exprs,
      ExprSubstitutionMap smap, Analyzer analyzer, boolean preserveRootTypes)
          throws AnalysisException {
    if (exprs == null) return null;
    List<Expr> result = new ArrayList<>();
    for (Expr e: exprs) {
      result.add(e.trySubstitute(smap, analyzer, preserveRootTypes));
    }
    return result;
  }

  public static List<Expr> substituteList(Iterable<? extends Expr> exprs,
      ExprSubstitutionMap smap, Analyzer analyzer, boolean preserveRootTypes) {
    try {
      return trySubstituteList(exprs, smap, analyzer, preserveRootTypes);
    } catch (Exception e) {
      throw new IllegalStateException("Failed analysis after expr substitution.", e);
    }
  }

  /**
   * Recursive method that performs the actual substitution for try/substitute() while
   * removing implicit casts. Resets the analysis state in all non-SlotRef expressions.
   * Exprs that have non-child exprs which should be affected by substitutions must
   * override this method and apply the substitution to such exprs as well.
   */
  protected Expr substituteImpl(ExprSubstitutionMap smap, Analyzer analyzer) {
    if (isImplicitCast()) return getChild(0).substituteImpl(smap, analyzer);
    if (smap != null) {
      Expr substExpr = smap.get(this);
      if (substExpr != null) return substExpr.clone();
    }
    substituteImplOnChildren(smap, analyzer);
    resetAnalysisState();
    return this;
  }

  protected final void substituteImplOnChildren(ExprSubstitutionMap smap,
      Analyzer analyzer) {
    for (int i = 0; i < children_.size(); ++i) {
      children_.set(i, children_.get(i).substituteImpl(smap, analyzer));
    }
  }

  /**
   * Set the expr to be analyzed and computes isConstant_.
   */
  protected void analysisDone() {
    Preconditions.checkState(!isAnalyzed_);
    // We need to compute the const-ness as the last step, since analysis may change
    // the result, e.g. by resolving function.
    isConstant_ = isConstantImpl();
    isAnalyzed_ = true;
  }

  /**
   * Resets the internal state of this expr produced by analyze().
   * Only modifies this expr, and not its child exprs.
   */
  protected void resetAnalysisState() { isAnalyzed_ = false; }

  /**
   * Resets the internal analysis state of this expr tree. Removes implicit casts.
   */
  public Expr reset() {
    if (isImplicitCast()) return getChild(0).reset();
    for (int i = 0; i < children_.size(); ++i) {
      children_.set(i, children_.get(i).reset());
    }
    resetAnalysisState();
    return this;
  }

  public static List<Expr> resetList(List<Expr> l) {
    for (int i = 0; i < l.size(); ++i) {
      l.set(i, l.get(i).reset());
    }
    return l;
  }

  /**
   * Creates a deep copy of this expr including its analysis state. The method is
   * abstract in this class to force new Exprs to implement it.
   */
  @Override
  public abstract Expr clone();

  /**
   * Create a deep copy of 'l'. The elements of the returned list are of the same
   * type as the input list.
   */
  public static <C extends Expr> List<C> cloneList(List<C> l) {
    Preconditions.checkNotNull(l);
    List<C> result = new ArrayList<>(l.size());
    for (Expr element: l) {
      result.add((C) element.clone());
    }
    return result;
  }

  /**
   * Create a deep copy of 'ls'. The elements of the returned list are of the same
   * type as the input list.
   */
  public static <C extends Expr> List<List<C>> deepCopy(List<List<C>> ls) {
    Preconditions.checkNotNull(ls);
    List<List<C>> result = new ArrayList<>(ls.size());
    for (List<C> l : ls) {
      if (l == null) {
        result.add(null);
        continue;
      }
      List<C> l2 = new ArrayList<>(l.size());
      for (Expr element : l) {
        l2.add((C) element.clone());
      }
      result.add(l2);
    }
    return result;
  }

  /**
   * Create a clone of the expression including analysis state with a different
   * selectivity.
   */
  public Expr cloneAndOverrideSelectivity(double selectivity) {
    Preconditions.checkArgument(selectivity >= 0.0 && selectivity <= 1.0, selectivity);
    Expr e = clone();
    e.selectivity_ = selectivity;
    return e;
  }

  /**
   * Removes duplicate exprs (according to equals()).
   */
  public static <C extends Expr> void removeDuplicates(List<C> l) {
    if (l == null) return;
    List<C> origList = Lists.newArrayList(l);
    l.clear();
    for (C expr: origList) if (!l.contains(expr)) l.add(expr);
  }

  /**
   * Return a new list without duplicate exprs (according to matches() using cmp).
   */
  public static <C extends Expr> List<C> removeDuplicates(List<C> l,
      SlotRef.Comparator cmp) {
    List<C> newList = new ArrayList<>();
    for (C expr: l) {
      boolean exists = false;
      for (C newExpr : newList) {
        if (newExpr.matches(expr, cmp)) {
          exists = true;
          break;
        }
      }
      if (!exists) newList.add(expr);
    }
    return newList;
  }

  /**
   * Removes constant exprs
   */
  public static <C extends Expr> void removeConstants(List<C> l) {
    if (l == null) return;
    ListIterator<C> it = l.listIterator();
    while (it.hasNext()) {
      C e = it.next();
      if (e.isConstant()) it.remove();
    }
  }

  /**
   * Propagates constant expressions of the form <slot ref> = <constant> or,
   * for certain data types, <slot ref> range_operator <constant> to
   * other uses of slot ref in the given conjuncts; returns a BitSet with
   * bits set to true in all changed indices.  Only one round of substitution
   * is performed.  The candidates BitSet is used to determine which members of
   * conjuncts are considered for propagation. The keepConjuncts list is
   * populated in specific cases (e.g for date/time range predicate propagation)
   * with the original conjuncts that need to be preserved even after rewrite.
   */
  private static BitSet propagateConstants(List<Expr> conjuncts, BitSet candidates,
      List<Expr> keepConjuncts, Analyzer analyzer) {
    Preconditions.checkState(conjuncts.size() <= candidates.size());

    // first pass: gather the constant predicates into separate buckets
    // for range and equality predicates
    ConstantPredicateHandler handler = new ConstantPredicateHandler();
    handler.classifyPredicates(conjuncts, candidates);

    // second pass: propagate constants to the other predicates and keep track
    // of which other predicates have been changed
    BitSet changed = new BitSet(conjuncts.size());
    handler.propagateConstantPreds(conjuncts, changed, keepConjuncts, analyzer);
    return changed;
  }

  /*
   * Propagates constants, performs expr rewriting and removes duplicates.
   * Returns false if a contradiction has been implied, true otherwise.
   * Catches and logs, but ignores any exceptions thrown during rewrite, which
   * will leave conjuncts intact and rewritten as far as possible until the
   * exception.
   */
  public static boolean optimizeConjuncts(List<Expr> conjuncts, Analyzer analyzer) {
    Preconditions.checkNotNull(conjuncts);
    List<Expr> tmpConjuncts = new ArrayList<>();
    List<Expr> keepConjuncts = new ArrayList<>();
    try {
      BitSet candidates = new BitSet(conjuncts.size());
      candidates.set(0, Math.min(conjuncts.size(), CONST_PROPAGATION_EXPR_LIMIT));
      int transfers = 0;
      tmpConjuncts.addAll(conjuncts);
      // Constant propagation may make other slots constant, so repeat the process
      // until there are no more changes.
      while (!candidates.isEmpty()) {
        // Use tmpConjuncts instead of conjuncts because propagateConstants can
        // change the content of the first input param. We do not want to
        // change the expr in conjucts before make sure the constant propagation
        // does not cause analysis failures.
        BitSet changed = propagateConstants(tmpConjuncts, candidates, keepConjuncts,
            analyzer);
        candidates.clear();
        int pruned = 0;
        for (int i = changed.nextSetBit(0); i >= 0; i = changed.nextSetBit(i+1)) {
          // When propagating constants, we may de-normalize expressions, so we
          // must normalize binary predicates.  Any additional rules will be
          // applied by the rewriter.
          int index = i - pruned;
          Preconditions.checkState(index >= 0);
          ExprRewriter rewriter = analyzer.getExprRewriter();
          Expr rewritten = rewriter.rewrite(tmpConjuncts.get(index), analyzer);
          // Re-analyze to add implicit casts and update cost
          rewritten.reset();
          rewritten.analyze(analyzer);
          if (!rewritten.isConstant()) {
            conjuncts.set(index, rewritten);
            tmpConjuncts.set(index, rewritten);
            if (++transfers < CONST_PROPAGATION_EXPR_LIMIT) candidates.set(index, true);
            continue;
          }
          // Remove constant boolean literal expressions.  N.B. - we may have
          // expressions determined to be constant which can not yet be discarded
          // because they can't be evaluated if expr rewriting is turned off.
          if (IS_NULL_LITERAL.apply(rewritten) ||
              IS_FALSE_LITERAL.apply(rewritten)) {
            conjuncts.clear();
            conjuncts.add(rewritten);
            return false;
          }
          if (IS_TRUE_LITERAL.apply(rewritten)) {
            pruned++;
            conjuncts.remove(index);
            tmpConjuncts.remove(index);
          }
        }
      }
    } catch (AnalysisException e) {
      LOG.warn("Not able to analyze after rewrite: " + e.toString() + " conjuncts: " +
          Expr.debugString(conjuncts));
    }
    // add the conjuncts that need to be preserved
    conjuncts.addAll(keepConjuncts);
    Expr.removeDuplicates(conjuncts);
    return true;
  }

  /**
   * Returns true if expr is fully bound by tid, otherwise false.
   */
  public boolean isBound(TupleId tid) {
    return isBoundByTupleIds(Lists.newArrayList(tid));
  }

  /**
   * Returns true if expr is fully bound by tids, otherwise false.
   */
  public boolean isBoundByTupleIds(List<TupleId> tids) {
    for (Expr child: children_) {
      if (!child.isBoundByTupleIds(tids)) return false;
    }
    return true;
  }

  /**
   * Returns true if expr is fully bound by slotIds, otherwise false.
   */
  public boolean isBoundBySlotIds(List<SlotId> slotIds) {
    for (Expr child: children_) {
      if (!child.isBoundBySlotIds(slotIds)) return false;
    }
    return true;
  }

  public static Expr getFirstBoundChild(Expr expr, List<TupleId> tids) {
    for (Expr child: expr.getChildren()) {
      if (child.isBoundByTupleIds(tids)) return child;
    }
    return null;
  }

  /**
   * Find all unique slot and/or tuple ids referenced by this expr tree.
   * @param tupleIds unique tuple IDs from this expr tree are appended here.
   * @param slotIds unique slot IDs from this expr tree are appended here.
   */
  public void getIds(List<TupleId> tupleIds, List<SlotId> slotIds) {
    Set<TupleId> tupleIdSet = new HashSet<>();
    Set<SlotId> slotIdSet = new HashSet<>();
    getIdsHelper(tupleIdSet, slotIdSet);
    if (tupleIds != null) tupleIds.addAll(tupleIdSet);
    if (slotIds != null) slotIds.addAll(slotIdSet);
  }

  protected void getIdsHelper(Set<TupleId> tupleIds, Set<SlotId> slotIds) {
    for (Expr child: children_) {
      child.getIdsHelper(tupleIds, slotIds);
    }
  }

  public static <C extends Expr> void getIds(List<? extends Expr> exprs,
      List<TupleId> tupleIds, List<SlotId> slotIds) {
    if (exprs == null) return;
    for (Expr e: exprs) {
      e.getIds(tupleIds, slotIds);
    }
  }

  /**
   * Returns true if this expression tree references a slot in the tuple identified
   * by tid.
   */
  public boolean referencesTuple(TupleId tid) {
    // This is the default implementation. Expr subclasses that reference slots in
    // tuples, i.e. SlotRef, must override this.
    for (Expr child: children_) {
      if (child.referencesTuple(tid)) return true;
    }
    return false;
  }

  /**
   * Returns true if this expression should be treated as constant. I.e. if the frontend
   * and backend should assume that two evaluations of the expression within a query will
   * return the same value. Examples of constant expressions include:
   * - Literal values like 1, "foo", or NULL
   * - Deterministic operators applied to constant arguments, e.g. 1 + 2, or
   *   concat("foo", "bar")
   * - Functions that should be always return the same value within a query but may
   *   return different values for different queries. E.g. now(), which we want to
   *   evaluate only once during planning.
   * May incorrectly return true if the expression is not analyzed.
   * TODO: isAnalyzed_ should be a precondition for isConstant(), since it is not always
   * possible to correctly determine const-ness before analysis (e.g. see
   * FunctionCallExpr.isConstant()).
   */
  public final boolean isConstant() {
    if (isAnalyzed_) return isConstant_;
    return isConstantImpl();
  }

  /**
   * Implements isConstant() - computes the value without using 'isConstant_'.
   */
  protected boolean isConstantImpl() {
    for (Expr expr : children_) {
      if (!expr.isConstant()) return false;
    }
    return true;
  }

  /**
   * Return true if and only if all exprs in 'exprs' are constant.
   */
  public static boolean allConstant(List<Expr> exprs) {
    for (Expr p: exprs) {
      if (!p.isConstant()) return false;
    }
    return true;
  }

  /**
   * Return true if this expr is a scalar subquery.
   */
  public boolean isScalarSubquery() {
    Preconditions.checkState(isAnalyzed_);
    if (!(this instanceof Subquery)) return false;
    Subquery subq = (Subquery) this;
    SelectStmt stmt = (SelectStmt) subq.getStatement();
    return stmt.returnsAtMostOneRow() && getType().isScalarType();
  }

  /**
   * Checks whether this expr returns a boolean type or NULL type.
   * If not, throws an AnalysisException with an appropriate error message using
   * 'name' as a prefix. For example, 'name' could be "WHERE clause".
   * The error message only contains this.toSql() if printExpr is true.
   */
  public void checkReturnsBool(String name, boolean printExpr) throws AnalysisException {
    if (!type_.isBoolean() && !type_.isNull()) {
      throw new AnalysisException(
          String.format("%s%s requires return type 'BOOLEAN'. " +
              "Actual type is '%s'.", name, (printExpr) ? " '" + toSql() + "'" : "",
              type_.toString()));
    }
  }

  /**
   * Casts this expr to a specific target type. It checks the validity of the cast
   * according to 'compatibility' and calls uncheckedCastTo().
   * @param targetType
   *          type to be cast to
   * @param compatibility
   *          compatibility level that defines the relation between 'targetType' and the
   *          type of the expression
   * @return cast expression, or converted literal,
   *         should never return null
   * @throws AnalysisException
   *           when an invalid cast is asked for, for example,
   *           failure to convert a string literal to a date literal
   */
  public final Expr castTo(Type targetType, TypeCompatibility compatibility)
      throws AnalysisException {
    Type type = Type.getAssignmentCompatibleType(this.type_, targetType, compatibility);
    Preconditions.checkState(type.isValid(), "cast %s to %s", this.type_, targetType);
    // If the targetType is NULL_TYPE then ignore the cast because NULL_TYPE
    // is compatible with all types and no cast is necessary.
    if (targetType.isNull()) return this;
    // If decimal, cast to the target type.
    if (targetType.isDecimal()) return uncheckedCastTo(targetType, compatibility);
    // If they match, cast to the type both values can be assigned to (the definition of
    // getAssignmentCompatibleType), which implies no loss of precision. Note that
    // getAssignmentCompatibleType always returns a "real" (not wildcard) type.
    if (type.matchesType(targetType)) return uncheckedCastTo(type, compatibility);
    throw new SqlCastException("targetType=" + targetType + " type=" + type);
  }

  public final Expr castTo(Type targetType) throws AnalysisException {
    return castTo(targetType, TypeCompatibility.DEFAULT);
  }

  /**
   * Create an expression equivalent to 'this' but returning targetType; possibly by
   * inserting an implicit cast, or by returning an altogether new expression or by
   * returning 'this' with a modified return type'.
   *
   * @param targetType    type to be cast to
   * @param compatibility compatibility level used to calculate the cast
   * @return cast expression, or converted literal, should never return null
   * @throws AnalysisException when an invalid cast is asked for, for example, failure to
   *                           convert a string literal to a date literal
   */
  protected Expr uncheckedCastTo(Type targetType, TypeCompatibility compatibility)
      throws AnalysisException {
    return new CastExpr(targetType, this, compatibility);
  }

  protected Expr uncheckedCastTo(Type targetType) throws AnalysisException {
    return uncheckedCastTo(targetType, TypeCompatibility.DEFAULT);
  }

  /**
   * Add a cast expression above child.
   * If child is a literal expression, we attempt to
   * convert the value of the child directly, and not insert a cast node.
   * @param targetType
   *          type to be cast to
   * @param childIndex
   *          index of child to be cast
   */
  public void castChild(Type targetType, int childIndex) throws AnalysisException {
    Expr child = getChild(childIndex);
    Expr newChild = child.castTo(targetType);
    setChild(childIndex, newChild);
  }

  /**
   * Convert child to to targetType, possibly by inserting an implicit cast, or by
   * returning an altogether new expression, or by returning 'this' with a modified
   * return type'.
   * @param targetType
   *          type to be cast to
   * @param childIndex
   *          index of child to be cast
   */
  protected void uncheckedCastChild(Type targetType, int childIndex)
      throws AnalysisException {
    Expr child = getChild(childIndex);
    Expr newChild = child.uncheckedCastTo(targetType);
    setChild(childIndex, newChild);
  }

  /**
   * Returns child expr if this expr is an implicit cast, otherwise returns 'this'.
   */
  public Expr ignoreImplicitCast() { return this; }

  /**
   * Returns true if 'this' is an implicit cast expr.
   */
  public boolean isImplicitCast() { return false; }

  @Override
  public String toString() {
    return MoreObjects.toStringHelper(this.getClass())
        .add("id", id_)
        .add("type", type_)
        .add("toSql", toSql(ToSqlOptions.SHOW_IMPLICIT_CASTS))
        .add("sel", selectivity_)
        .add("evalCost", evalCost_)
        .add("#distinct", numDistinctValues_)
        .toString();
  }

  /**
   * If 'this' is a SlotRef or a Cast that wraps a SlotRef, returns that SlotRef.
   * Otherwise returns null.
   */
  public SlotRef unwrapSlotRef(boolean implicitOnly) {
    Expr unwrappedExpr = unwrapExpr(implicitOnly);
    if (unwrappedExpr instanceof SlotRef) return (SlotRef) unwrappedExpr;
    return null;
  }

  /**
   * Returns the first child if this Expr is a CastExpr or builtin cast
   * function. Otherwise, returns 'this'.
   */
  public Expr unwrapExpr(boolean implicitOnly) {
    if ((this instanceof CastExpr
        && (!implicitOnly || ((CastExpr) this).isImplicit()))
        || (this instanceof FunctionCallExpr
            && ((FunctionCallExpr) this).isBuiltinCastFunction())) {
      return children_.get(0);
    }
    return this;
  }

  /**
   * Returns the source expression for this expression. Traverses the source
   * exprs of intermediate slot descriptors to resolve materialization points
   * (e.g., aggregations). Returns null if there are multiple source Exprs
   * mapped to the expression at any given point.
   */
  public Expr findSrcExpr() {
    // If the source expression is a constant expression, it won't have a scanSlotRef
    // and we can return this.
    if (isConstant()) {
      return this;
    }
    SlotRef slotRef = unwrapSlotRef(false);
    if (slotRef == null) return null;
    SlotDescriptor slotDesc = slotRef.getDesc();
    if (slotDesc.isScanSlot()) return slotRef;
    if (slotDesc.getSourceExprs().size() == 1) {
      return slotDesc.getSourceExprs().get(0).findSrcExpr();
    }
    // No known source expr, or there are several source exprs meaning the slot is
    // has no single source table.
    return null;
  }

  /**
   * Returns the descriptor of the scan slot that directly or indirectly produces
   * the values of 'this' SlotRef. Traverses the source exprs of intermediate slot
   * descriptors to resolve materialization points (e.g., aggregations).
   * Returns null if 'e' or any source expr of 'e' is not a SlotRef or cast SlotRef.
   */
  public SlotDescriptor findSrcScanSlot() {
    Expr sourceExpr = findSrcExpr();
    if (sourceExpr == null) {
      return null;
    }
    SlotRef slotRef = sourceExpr.unwrapSlotRef(false);
    if (slotRef == null) {
      return null;
    }
    return slotRef.getDesc();
  }

  /**
   * Pushes negation to the individual operands of a predicate
   * tree rooted at 'root'.
   */
  public static Expr pushNegationToOperands(Expr root) {
    Preconditions.checkNotNull(root);
    if (IS_NOT_PREDICATE.apply(root)) {
      try {
        // Make sure we call function 'negate' only on classes that support it,
        // otherwise we may recurse infinitely.
        root.getChild(0).getClass().getDeclaredMethod(NEGATE_FN);
        return pushNegationToOperands(root.getChild(0).negate());
      } catch (NoSuchMethodException e) {
        // The 'negate' function is not implemented. Break the recursion.
        return root;
      }
    }

    if (root instanceof CompoundPredicate) {
      Expr left = pushNegationToOperands(root.getChild(0));
      Expr right = pushNegationToOperands(root.getChild(1));
      CompoundPredicate compoundPredicate =
        new CompoundPredicate(((CompoundPredicate)root).getOp(), left, right);
      compoundPredicate.setPrintSqlInParens(root.getPrintSqlInParens());
      return compoundPredicate;
    }

    return root;
  }

  /**
   * Negates a boolean Expr.
   */
  public Expr negate() {
    Preconditions.checkState(type_.getPrimitiveType() == PrimitiveType.BOOLEAN);
    return new CompoundPredicate(CompoundPredicate.Operator.NOT, this, null);
  }

  /**
   * Returns the subquery of an expr. Returns null if this expr does not contain
   * a subquery.
   *
   * TODO: Support predicates with more that one subqueries when we implement
   * the independent subquery evaluation.
   */
  public Subquery getSubquery() {
    if (!contains(Subquery.class)) return null;
    List<Subquery> subqueries = new ArrayList<>();
    collect(Subquery.class, subqueries);
    Preconditions.checkState(subqueries.size() == 1);
    return subqueries.get(0);
  }

  /**
   * Returns true iff all of this Expr's children have their costs set.
   */
  protected boolean hasChildCosts() {
    for (Expr child : children_) {
      if (!child.hasCost()) return false;
    }
    return true;
  }

  /**
   * Computes and returns the sum of the costs of all of this Expr's children.
   */
  protected float getChildCosts() {
    float cost = 0;
    for (Expr child : children_) cost += child.getCost();
    return cost;
  }

  /**
   * Returns the average length of the values produced by an Expr
   * of type string. Returns a default for unknown lengths.
   */
  protected static double getAvgStringLength(Expr e) {
    Preconditions.checkState(e.getType().isStringType());
    Preconditions.checkState(e.isAnalyzed_);

    SlotRef ref = e.unwrapSlotRef(false);
    if (ref != null) {
      if (ref.getDesc() != null && ref.getDesc().getStats().getAvgSize() > 0) {
        return ref.getDesc().getStats().getAvgSize();
      } else {
        return DEFAULT_AVG_STRING_LENGTH;
      }
    } else if (e instanceof StringLiteral) {
      return ((StringLiteral) e).getUnescapedValue().length();
    } else {
      // TODO(tmarshall): Extend this to support other string Exprs, such as
      // function calls that return string.
      return DEFAULT_AVG_STRING_LENGTH;
    }
  }

  /**
   * Generates a comma-separated string from the toSql() string representations of
   * 'exprs'.
   */
  public static String listToSql(List<Expr> exprs, ToSqlOptions options) {
    com.google.common.base.Function<Expr, String> toSql =
        new com.google.common.base.Function<Expr, String>() {
        @Override
        public String apply(Expr arg) {
          return arg.toSql(options);
        }
    };
    return Joiner.on(",").join(Iterables.transform(exprs, toSql));
  }

  public static String getExplainString(
      List<? extends Expr> exprs, TExplainLevel detailLevel) {
    if (exprs == null) return "";
    ToSqlOptions toSqlOptions =
        detailLevel.ordinal() >= TExplainLevel.EXTENDED.ordinal() ?
        ToSqlOptions.SHOW_IMPLICIT_CASTS :
        ToSqlOptions.DEFAULT;
    StringBuilder output = new StringBuilder();
    for (int i = 0; i < exprs.size(); ++i) {
      if (i > 0) output.append(", ");
      output.append(exprs.get(i).toSql(toSqlOptions));
    }
    return output.toString();
  }

  /**
   * Analyzes and evaluates expression to an integral value, returned as a long.
   * Throws if the expression cannot be evaluated or if the value evaluates to null.
   * The 'name' parameter is used in exception messages, e.g. "LIMIT expression
   * evaluates to NULL".
   */
  public long evalToInteger(Analyzer analyzer, String name) throws AnalysisException {
    // Check for slotrefs and subqueries before analysis so we can provide a more
    // helpful error message.
    if (contains(SlotRef.class) || contains(Subquery.class)) {
      throw new AnalysisException(name + " expression must be a constant expression: " +
          toSql());
    }
    analyze(analyzer);
    if (!isConstant()) {
      throw new AnalysisException(name + " expression must be a constant expression: " +
          toSql());
    }
    if (!getType().isIntegerType()) {
      throw new AnalysisException(name + " expression must be an integer type but is '" +
          getType() + "': " + toSql());
    }
    TColumnValue val = null;
    try {
      val = FeSupport.EvalExprWithoutRow(this, analyzer.getQueryCtx());
    } catch (InternalException e) {
      throw new AnalysisException("Failed to evaluate expr: " + toSql(), e);
    }
    long value;
    if (val.isSetLong_val()) {
      value = val.getLong_val();
    } else if (val.isSetInt_val()) {
      value = val.getInt_val();
    } else if (val.isSetShort_val()) {
      value = val.getShort_val();
    } else if (val.isSetByte_val()) {
      value = val.getByte_val();
    } else {
      throw new AnalysisException(name + " expression evaluates to NULL: " + toSql());
    }
    return value;
  }

  /**
   * Analyzes and evaluates expression to a non-negative integral value, returned as a
   * long. Throws if the expression cannot be evaluated, if the value evaluates to null,
   * or if the result is negative. The 'name' parameter is used in exception messages,
   * e.g. "LIMIT expression evaluates to NULL".
   */
  public long evalToNonNegativeInteger(Analyzer analyzer, String name)
      throws AnalysisException {
    long value = evalToInteger(analyzer, name);
    if (value < 0) {
      throw new AnalysisException(name + " must be a non-negative integer: " +
          toSql() + " = " + value);
    }
    return value;
  }

  public void setPredicateHints(List<PlanHint> hints) {
    Preconditions.checkNotNull(hints);
    predicateHints_ = hints;
  }

  public List<PlanHint> getPredicateHints() { return predicateHints_; }

  // A wrapper method to create null literal. This can be overriden
  // in a derived class
  protected Expr createNullLiteral() {
    return new NullLiteral();
  }

  /**
   * Subclass that contains query statements, e.g SubQuery, should override this.
   */
  public boolean resolveTableMask(Analyzer analyzer) throws AnalysisException {
    boolean hasChanges = false;
    for (Expr child : children_) {
      hasChanges |= child.resolveTableMask(analyzer);
    }
    return hasChanges;
  }

  /**
   * A slot descriptor may be associated with more than 1 source expression.
   * This method returns the first source expr in that case or null if there
   * are no source exprs.
   */
  public Expr getSlotDescFirstSourceExpr() {
    SlotRef slotRef = unwrapSlotRef(false);
    if (slotRef == null) return null;
    SlotDescriptor slotDesc = slotRef.getDesc();
    if (slotDesc.getSourceExprs().size() >= 1) {
      return slotDesc.getSourceExprs().get(0);
    }
    return null;
  }

  /**
   * Returns the first non-const expression on the following path:
   *  - checking whether the expression itself is constant or not
   *  If there's an underlying slot ref:
   *  - checking the slot desc's source expressions constness
   */
  public Optional<Expr> getFirstNonConstSourceExpr() {
    SlotRef slotRef = unwrapSlotRef(false);

    if (slotRef == null) {
      Preconditions.checkState(isAnalyzed());
      return isConstant() ? Optional.empty() : Optional.of(this);
    }

    SlotDescriptor slotDesc = slotRef.getDesc();
    Preconditions.checkNotNull(slotDesc);

    if (slotDesc.getSourceExprs().isEmpty()) {
      return Optional.of(this);
    }

    Optional<Expr> nonConstSourceExpr = Optional.empty();
    for (Expr expr : slotDesc.getSourceExprs()) {
      Preconditions.checkState(expr.isAnalyzed());
      if (!expr.isConstant()) {
        nonConstSourceExpr = Optional.of(expr);
        break;
      }
    }
    return nonConstSourceExpr;
  }

  /**
   * Returns true if 'this' is a constant.
   */
  public boolean shouldConvertToCNF() {
    return isConstant();
  }
}