Expr.java

Go to the documentation of this file.

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

package com.cloudera.impala.analysis;

import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.cloudera.impala.catalog.Catalog;
import com.cloudera.impala.catalog.Function;
import com.cloudera.impala.catalog.Function.CompareMode;
import com.cloudera.impala.catalog.PrimitiveType;
import com.cloudera.impala.catalog.ScalarType;
import com.cloudera.impala.catalog.Type;
import com.cloudera.impala.common.AnalysisException;
import com.cloudera.impala.common.TreeNode;
import com.cloudera.impala.thrift.TExpr;
import com.cloudera.impala.thrift.TExprNode;
import com.google.common.base.Joiner;
import com.google.common.base.Objects;
import com.google.common.base.Preconditions;
import com.google.common.base.Predicates;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

abstract public class Expr extends TreeNode<Expr> implements ParseNode, Cloneable {
  private final static 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 final static int EXPR_CHILDREN_LIMIT = 10000;
  // The expr depth limit is mostly due to our recursive implementation of clone().
  public final static int EXPR_DEPTH_LIMIT = 1000;

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

  // to be used where we can't come up with a better estimate
  protected static double DEFAULT_SELECTIVITY = 0.1;

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

  // Returns true if an Expr is a NOT CompoundPredicate.
  public final static 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 final static 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 final static 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 is an aggregate function that returns non-null on
  // an empty set (e.g. count).
  public final static 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 final static 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();
        }
      };

  public final static 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();
        }
      };

  // 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 isAnalyzed_;  // true after analyze() has been called
  protected boolean isWhereClauseConjunct_; // 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 if valid: invalid: -1
  protected double selectivity_;

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

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

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

  protected Expr(Expr other) {
    id_ = other.id_;
    isAuxExpr_ = other.isAuxExpr_;
    type_ = other.type_;
    isAnalyzed_ = other.isAnalyzed_;
    isWhereClauseConjunct_ = other.isWhereClauseConjunct_;
    printSqlInParens_ = other.printSqlInParens_;
    selectivity_ = other.selectivity_;
    numDistinctValues_ = other.numDistinctValues_;
    fn_ = other.fn_;
    children_ = Expr.cloneList(other.children_);
  }

  public ExprId getId() { return id_; }
  protected void setId(ExprId id) { this.id_ = id; }
  public Type getType() { return type_; }
  public double getSelectivity() { return selectivity_; }
  public long getNumDistinctValues() { return numDistinctValues_; }
  public void setPrintSqlInParens(boolean b) { printSqlInParens_ = b; }
  public boolean isWhereClauseConjunct() { return isWhereClauseConjunct_; }
  public void setIsWhereClauseConjunct() { isWhereClauseConjunct_ = true; }
  public boolean isAuxExpr() { return isAuxExpr_; }
  public boolean isRegisteredPredicate() { return id_ != null; }
  public void setIsAuxExpr() { isAuxExpr_ = true; }
  public Function getFn() { return fn_; }

  public void analyze(Analyzer analyzer) throws AnalysisException {
    // 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));
      }
    }
    for (Expr child: children_) {
      child.analyze(analyzer);
    }
    isAnalyzed_ = true;
    computeNumDistinctValues();

    if (analyzer != null) analyzer.decrementCallDepth();
  }

  public void analyzeNoThrow(Analyzer analyzer) {
    try {
      analyze(analyzer);
    } catch (AnalysisException e) {
      throw new IllegalStateException(e);
    }
  }

  protected void computeNumDistinctValues() {
    if (isConstant()) {
      numDistinctValues_ = 1;
    } else {
      // if this Expr contains slotrefs, we estimate the # of distinct values
      // to be the maximum such number for any of the slotrefs;
      // the subclass analyze() function may well want to override this, if it
      // knows better
      List<SlotRef> slotRefs = Lists.newArrayList();
      this.collect(Predicates.instanceOf(SlotRef.class), slotRefs);
      numDistinctValues_ = -1;
      for (SlotRef slotRef: slotRefs) {
        numDistinctValues_ = Math.max(numDistinctValues_, slotRef.numDistinctValues_);
      }
    }
  }

  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;
  }

  public void castChildCharsToStrings(Analyzer analyzer) throws AnalysisException {
    for (int i = 0; i < children_.size(); ++i) {
      if (children_.get(i).getType().isScalarType(PrimitiveType.CHAR)) {
        children_.set(i, children_.get(i).castTo(ScalarType.STRING));
        children_.get(i).analyze(analyzer);
      }
    }
  }

  protected Function getBuiltinFunction(Analyzer analyzer, String name,
      Type[] argTypes, CompareMode mode) throws AnalysisException {
    FunctionName fnName = new FunctionName(Catalog.BUILTINS_DB, name);
    Function searchDesc = new Function(fnName, argTypes, Type.INVALID, false);
    return analyzer.getCatalog().getFunction(searchDesc, mode);
  }

  protected void castForFunctionCall(boolean ignoreWildcardDecimals)
      throws AnalysisException {
    Preconditions.checkState(fn_ != null);
    Type[] fnArgs = fn_.getArgs();
    Type resolvedWildcardType = getResolvedWildCardType();
    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;
        Preconditions.checkState(resolvedWildcardType != null);
        if (!children_.get(i).type_.equals(resolvedWildcardType)) {
          castChild(resolvedWildcardType, i);
        }
      } else if (!children_.get(i).type_.matchesType(fnArgs[ix])) {
        castChild(fnArgs[ix], i);
      }
    }
  }

  Type getResolvedWildCardType() throws AnalysisException {
    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.");
      ScalarType decimalType = (ScalarType) childType;
      if (result == null) {
        result = decimalType.getMinResolutionDecimal();
      } else {
        result = Type.getAssignmentCompatibleType(result, childType);
      }
    }
    if (result != null) {
      if (result.isNull()) {
        throw new AnalysisException(
            "Cannot resolve DECIMAL precision and scale from NULL type.");
      }
      Preconditions.checkState(result.isDecimal() && !result.isWildcardDecimal());
    }
    return result;
  }

  private boolean isExplicitCastToDecimal(Expr e) {
    if (!(e instanceof CastExpr)) return false;
    CastExpr c = (CastExpr)e;
    return !c.isImplicit() && c.getType().isDecimal();
  }

  private Expr convertNumericLiteralsToFloat(Analyzer analyzer, Expr child,
      Type targetType) throws AnalysisException {
    if (!targetType.isFloatingPointType() && !targetType.isIntegerType()) return child;
    if (targetType.isIntegerType()) targetType = Type.DOUBLE;
    List<NumericLiteral> literals = Lists.newArrayList();
    child.collectAll(Predicates.instanceOf(NumericLiteral.class), literals);
    ExprSubstitutionMap smap = new ExprSubstitutionMap();
    for (NumericLiteral l: literals) {
      NumericLiteral castLiteral = (NumericLiteral) l.clone();
      castLiteral.explicitlyCastToFloat(targetType);
      smap.put(l, castLiteral);
    }
    return child.substitute(smap, analyzer, false);
  }

  protected void convertNumericLiteralsFromDecimal(Analyzer analyzer)
      throws AnalysisException {
    Preconditions.checkState(this instanceof ArithmeticExpr ||
        this instanceof BinaryPredicate);
    Preconditions.checkState(children_.size() == 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 = convertNumericLiteralsToFloat(analyzer, getChild(0), t1);
      setChild(0, c0);
    }
    if (c1IsConstantDecimal && !isExplicitCastToDecimal(getChild(1))) {
      Expr c1 = convertNumericLiteralsToFloat(analyzer, getChild(1), t0);
      setChild(1, c1);
    }
  }

  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 String toSql() {
    return (printSqlInParens_) ? "(" + toSqlImpl() + ")" : toSqlImpl();
  }

  protected abstract String toSqlImpl();

  // 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(this instanceof NullLiteral || 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.num_children = children_.size();
    if (fn_ != null) {
      msg.setFn(fn_.toThrift());
      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);

  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 *= expr.getNumDistinctValues();
    }
    return numDistinctValues;
  }

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

  public static com.google.common.base.Predicate<Expr> isAggregatePredicate() {
    return isAggregatePredicate_;
  }

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

  public List<String> childrenToSql() {
    List<String> result = Lists.newArrayList();
    for (Expr child: children_) {
      result.add(child.toSql());
    }
    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 = Lists.newArrayList();
    for (Expr expr: exprs) {
      strings.add(expr.debugString());
    }
    return Joiner.on(" ").join(strings);
  }

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

  @Override
  public boolean equals(Object obj) {
    if (obj == null) return false;
    if (obj.getClass() != this.getClass()) return false;
    // don't compare type, this could be called pre-analysis
    Expr expr = (Expr) obj;
    if (children_.size() != expr.children_.size()) return false;
    for (int i = 0; i < children_.size(); ++i) {
      if (!children_.get(i).equals(expr.children_.get(i))) return false;
    }
    if (fn_ == null && expr.fn_ == null) return true;
    if (fn_ == null || expr.fn_ == null) return false; // One null, one not
    // Both fn_'s are not null
    return fn_.equals(expr.fn_);
  }

  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;
  }

  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);
  }

  public static <C extends Expr> boolean isSubset(List<C> l1, List<C> l2) {
    if (l1.size() > l2.size()) return false;
    return l2.containsAll(l1);
  }

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

  public static void intersect(Analyzer analyzer,
      List<Expr> l1, List<Expr> l2, ExprSubstitutionMap smap,
      List<Expr> i1, List<Expr> i2) {
    i1.clear();
    i2.clear();
    List<Expr> s1List = Expr.substituteList(l1, smap, analyzer, false);
    Preconditions.checkState(s1List.size() == l1.size());
    List<Expr> s2List = Expr.substituteList(l2, smap, analyzer, false);
    Preconditions.checkState(s2List.size() == l2.size());
    for (int i = 0; i < s1List.size(); ++i) {
      Expr s1 = s1List.get(i);
      for (int j = 0; j < s2List.size(); ++j) {
        Expr s2 = s2List.get(j);
        if (s1.equals(s2)) {
          i1.add(l1.get(i));
          i2.add(l2.get(j));
          break;
        }
      }
    }
  }

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

  public List<Expr> getConjuncts() {
    List<Expr> list = Lists.newArrayList();
    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;
  }

  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())) result = result.castTo(type_);
    return result;
  }

  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 ArrayList<Expr> trySubstituteList(Iterable<? extends Expr> exprs,
      ExprSubstitutionMap smap, Analyzer analyzer, boolean preserveRootTypes)
          throws AnalysisException {
    if (exprs == null) return null;
    ArrayList<Expr> result = new ArrayList<Expr>();
    for (Expr e: exprs) {
      result.add(e.trySubstitute(smap, analyzer, preserveRootTypes));
    }
    return result;
  }

  public static ArrayList<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);
    }
  }

  protected Expr substituteImpl(ExprSubstitutionMap smap, Analyzer analyzer)
      throws AnalysisException {
    if (isImplicitCast()) return getChild(0).substituteImpl(smap, analyzer);
    if (smap != null) {
      Expr substExpr = smap.get(this);
      if (substExpr != null) return substExpr.clone();
    }
    for (int i = 0; i < children_.size(); ++i) {
      children_.set(i, children_.get(i).substituteImpl(smap, analyzer));
    }
    // SlotRefs must remain analyzed to support substitution across query blocks. All
    // other exprs must be analyzed again after the substitution to add implicit casts
    // and for resolving their correct function signature.
    if (!(this instanceof SlotRef)) resetAnalysisState();
    return this;
  }

  protected void resetAnalysisState() { isAnalyzed_ = false; }

  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 ArrayList<Expr> resetList(ArrayList<Expr> l) {
    for (int i = 0; i < l.size(); ++i) {
      l.set(i, l.get(i).reset());
    }
    return l;
  }

  @Override
  public abstract Expr clone();

  public static <C extends Expr> ArrayList<C> cloneList(Iterable<C> l) {
    Preconditions.checkNotNull(l);
    ArrayList<C> result = new ArrayList<C>();
    for (Expr element: l) {
      result.add((C) element.clone());
    }
    return result;
  }

  public static <C extends Expr> void removeDuplicates(List<C> l) {
    if (l == null) return;
    ListIterator<C> it1 = l.listIterator();
    while (it1.hasNext()) {
      C e1 = it1.next();
      ListIterator<C> it2 = l.listIterator();
      boolean duplicate = false;
      while (it2.hasNext()) {
        C e2 = it2.next();
          // only check up to but excluding e1
        if (e1 == e2) break;
        if (e1.equals(e2)) {
          duplicate = true;
          break;
        }
      }
      if (duplicate) it1.remove();
    }
  }

  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();
    }
  }

  public boolean isBound(TupleId tid) {
    return isBoundByTupleIds(Lists.newArrayList(tid));
  }

  public boolean isBoundByTupleIds(List<TupleId> tids) {
    for (Expr child: children_) {
      if (!child.isBoundByTupleIds(tids)) return false;
    }
    return true;
  }

  public boolean isBound(SlotId slotId) {
    return isBoundBySlotIds(Lists.newArrayList(slotId));
  }

  public boolean isBoundBySlotIds(List<SlotId> slotIds) {
    for (Expr child: children_) {
      if (!child.isBoundBySlotIds(slotIds)) return false;
    }
    return true;
  }

  public static boolean isBound(List<? extends Expr> exprs, List<TupleId> tids) {
    for (Expr expr: exprs) {
      if (!expr.isBoundByTupleIds(tids)) return false;
    }
    return true;
  }

  public void getIds(List<TupleId> tupleIds, List<SlotId> slotIds) {
    Set<TupleId> tupleIdSet = Sets.newHashSet();
    Set<SlotId> slotIdSet = Sets.newHashSet();
    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);
    }
  }

  public boolean isLiteral() {
    return this instanceof LiteralExpr;
  }

  public boolean isConstant() {
    return !contains(Predicates.instanceOf(SlotRef.class)) &&
           !contains(Predicates.instanceOf(Subquery.class));
  }

  public boolean isNullLiteral() {
    if (this instanceof NullLiteral) return true;
    if (!(this instanceof CastExpr)) return false;
    Preconditions.checkState(children_.size() == 1);
    return children_.get(0).isNullLiteral();
  }

  public boolean isScalarSubquery() {
    Preconditions.checkState(isAnalyzed_);
    return this instanceof Subquery && getType().isScalarType();
  }

  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()));
    }
  }

  public final Expr castTo(Type targetType) throws AnalysisException {
    Type type = Type.getAssignmentCompatibleType(this.type_, targetType);
    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 (!targetType.isDecimal()) {
      // requested cast must be to assignment-compatible type
      // (which implies no loss of precision)
      Preconditions.checkArgument(targetType.equals(type),
          "targetType=" + targetType + " type=" + type);
    }
    return uncheckedCastTo(targetType);
  }

  protected Expr uncheckedCastTo(Type targetType) throws AnalysisException {
    return new CastExpr(targetType, this);
  }

  public void castChild(Type targetType, int childIndex) throws AnalysisException {
    Expr child = getChild(childIndex);
    Expr newChild = child.castTo(targetType);
    setChild(childIndex, newChild);
  }


  protected void uncheckedCastChild(Type targetType, int childIndex)
      throws AnalysisException {
    Expr child = getChild(childIndex);
    Expr newChild = child.uncheckedCastTo(targetType);
    setChild(childIndex, newChild);
  }

  public Expr ignoreImplicitCast() {
    if (isImplicitCast()) return getChild(0).ignoreImplicitCast();
    return this;
  }

  public boolean isImplicitCast() {
    return this instanceof CastExpr && ((CastExpr) this).isImplicit();
  }

  @Override
  public String toString() {
    return Objects.toStringHelper(this.getClass())
        .add("id", id_)
        .add("type", type_)
        .add("sel", selectivity_)
        .add("#distinct", numDistinctValues_)
        .toString();
  }

  public SlotRef unwrapSlotRef(boolean implicitOnly) {
    if (this instanceof SlotRef) {
      return (SlotRef) this;
    } else if (this instanceof CastExpr
        && (!implicitOnly || ((CastExpr) this).isImplicit())
        && getChild(0) instanceof SlotRef) {
      return (SlotRef) getChild(0);
    } else {
      return null;
    }
  }

  public static Expr pushNegationToOperands(Expr root) {
    Preconditions.checkNotNull(root);
    if (Expr.IS_NOT_PREDICATE.apply(root)) {
      try {
        // Make sure we call function 'negate' only on classes that support it,
        // otherwise we may recurse infinitely.
        Method m = 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));
      return new CompoundPredicate(((CompoundPredicate)root).getOp(), left, right);
    }

    return root;
  }

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

  public Subquery getSubquery() {
    if (!contains(Subquery.class)) return null;
    List<Subquery> subqueries = Lists.newArrayList();
    collect(Subquery.class, subqueries);
    Preconditions.checkState(subqueries.size() == 1);
    return subqueries.get(0);
  }

  public void foldConstantChildren(Analyzer analyzer) throws AnalysisException {
    Preconditions.checkState(isAnalyzed_);
    Preconditions.checkNotNull(analyzer);
    for (int i = 0; i < children_.size(); ++i) {
      Expr child = getChild(i);
      if (child.isLiteral() || !child.isConstant()) continue;
      LiteralExpr literalExpr = LiteralExpr.create(child, analyzer.getQueryCtx());
      Preconditions.checkNotNull(literalExpr);
      setChild(i, literalExpr);
    }
    isAnalyzed_ = false;
  }
}