You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by kw...@apache.org on 2016/09/30 02:14:59 UTC
[42/61] [partial] incubator-impala git commit: IMPALA-3786: Replace
"cloudera" with "apache" (part 1)
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/b544f019/fe/src/main/java/com/cloudera/impala/analysis/Expr.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/com/cloudera/impala/analysis/Expr.java b/fe/src/main/java/com/cloudera/impala/analysis/Expr.java
deleted file mode 100644
index fdc5bf1..0000000
--- a/fe/src/main/java/com/cloudera/impala/analysis/Expr.java
+++ /dev/null
@@ -1,1258 +0,0 @@
-// 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 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;
-
-/**
- * Root of the expr node hierarchy.
- *
- */
-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 cannot come up with a better estimate (selectivity_ is -1).
- public static 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 final static float ARITHMETIC_OP_COST = 1;
- public final static float BINARY_PREDICATE_COST = 1;
- public final static float VAR_LEN_BINARY_PREDICATE_COST = 5;
- public final static float CAST_COST = 1;
- public final static float COMPOUND_PREDICATE_COST = 1;
- public final static float FUNCTION_CALL_COST = 10;
- public final static float IS_NOT_EMPTY_COST = 1;
- public final static float IS_NULL_COST = 1;
- public final static float LIKE_COST = 10;
- public final static float LITERAL_COST = 1;
- public final static float SLOT_REF_COST = 1;
- public final static float TIMESTAMP_ARITHMETIC_COST = 5;
-
- // 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 final static int DEFAULT_AVG_STRING_LENGTH = 5;
-
- // 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();
- }
- };
-
- public final static 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 final static 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; }
- };
-
- // 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 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_;
-
- // 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;
- 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_;
- isOnClauseConjunct_ = other.isOnClauseConjunct_;
- printSqlInParens_ = other.printSqlInParens_;
- selectivity_ = other.selectivity_;
- evalCost_ = other.evalCost_;
- numDistinctValues_ = other.numDistinctValues_;
- fn_ = other.fn_;
- children_ = Expr.cloneList(other.children_);
- }
-
- 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 void setPrintSqlInParens(boolean b) { printSqlInParens_ = b; }
- public boolean isOnClauseConjunct() { return isOnClauseConjunct_; }
- public void setIsOnClauseConjunct(boolean b) { isOnClauseConjunct_ = b; }
- public boolean isAuxExpr() { return isAuxExpr_; }
- public boolean isRegisteredPredicate() { return id_ != null; }
- public void setIsAuxExpr() { isAuxExpr_ = true; }
- public Function getFn() { return fn_; }
-
- /**
- * Perform semantic analysis of node and all of its children.
- * Throws exception if any errors found.
- * @see com.cloudera.impala.parser.ParseNode#analyze(com.cloudera.impala.parser.Analyzer)
- */
- 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();
- }
-
- /**
- * 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);
- }
- }
-
- 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_);
- }
- }
- }
-
- /**
- * 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(Catalog.BUILTINS_DB, 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.
- * This does not do any validation and the casts are assumed to be safe.
- *
- * 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).
- */
- 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);
- }
- }
- }
-
- /**
- * Returns the max resolution type of all the wild card decimal types.
- * Returns null if there are no wild card types.
- */
- 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, false);
- }
- }
- 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;
- }
-
- /**
- * 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 = Lists.newArrayList();
- 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);
- }
-
- /**
- * Converts numeric literal in the expr tree rooted at this expr to return floating
- * point types instead of decimals, if possible.
- *
- * 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 when it is consistent with the user's intent.
- *
- * TODO: another option is to do constant folding in the FE and then apply this rule.
- */
- protected void convertNumericLiteralsFromDecimal(Analyzer analyzer)
- throws AnalysisException {
- Preconditions.checkState(this instanceof ArithmeticExpr ||
- this instanceof BinaryPredicate);
- if (children_.size() == 1) return; // Do not attempt to convert for unary ops
- 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 = 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 String toSql() {
- return (printSqlInParens_) ? "(" + toSqlImpl() + ")" : toSqlImpl();
- }
-
- /**
- * 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();
-
- // 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);
-
- /**
- * 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.
- */
- 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);
- }
-
- /**
- * Returns true if two expressions are equal. The equality comparison works on analyzed
- * as well as unanalyzed exprs by ignoring implicit casts (see CastExpr.equals()).
- */
- @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_);
- }
-
- /**
- * 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.599
- */
- 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;
- }
-
- /**
- * Compute the intersection of l1 and l2, given the smap, and
- * return the intersecting l1 elements in i1 and the intersecting l2 elements in i2.
- */
- 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();
- }
- }
-
- /**
- * 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 = 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;
- }
-
- /**
- * 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())) result = 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 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);
- }
- }
-
- /**
- * 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)
- 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;
- }
-
- /**
- * 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 ArrayList<Expr> resetList(ArrayList<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> ArrayList<C> cloneList(List<C> l) {
- Preconditions.checkNotNull(l);
- ArrayList<C> result = new ArrayList<C>(l.size());
- for (Expr element: l) {
- result.add((C) element.clone());
- }
- return result;
- }
-
- /**
- * Removes duplicate exprs (according to equals()).
- */
- 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();
- }
- }
-
- /**
- * 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();
- }
- }
-
- /**
- * 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 slotId, otherwise false.
- */
- public boolean isBound(SlotId slotId) {
- return isBoundBySlotIds(Lists.newArrayList(slotId));
- }
-
- /**
- * 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 boolean isBound(List<? extends Expr> exprs, List<TupleId> tids) {
- for (Expr expr: exprs) {
- if (!expr.isBoundByTupleIds(tids)) 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;
- }
-
- 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);
- }
- }
-
- /**
- * @return true if this is an instance of LiteralExpr
- */
- public boolean isLiteral() {
- return this instanceof LiteralExpr;
- }
-
- /**
- * @return true if this expr can be evaluated with Expr::GetValue(NULL),
- * i.e. if it doesn't contain any references to runtime variables (e.g. slot refs).
- * Expr subclasses should override this if necessary (e.g. SlotRef, Subquery, etc.
- * always return false).
- */
- public boolean isConstant() {
- for (Expr expr : children_) {
- if (!expr.isConstant()) return false;
- }
- return true;
- }
-
- /**
- * @return true if this expr is either a null literal or a cast from
- * a null literal.
- */
- 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();
- }
-
- /**
- * Return true if this expr is a scalar subquery.
- */
- public boolean isScalarSubquery() {
- Preconditions.checkState(isAnalyzed_);
- return this instanceof Subquery && 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 and
- * calls uncheckedCastTo().
- * @param targetType
- * type to be cast to
- * @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) throws AnalysisException {
- Type type = Type.getAssignmentCompatibleType(this.type_, targetType, false);
- 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);
- }
-
- /**
- * 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
- * @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) throws AnalysisException {
- return new CastExpr(targetType, this);
- }
-
- /**
- * 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() {
- if (isImplicitCast()) return getChild(0).ignoreImplicitCast();
- return this;
- }
-
- /**
- * Returns true if 'this' is an implicit cast expr.
- */
- 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("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) {
- 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;
- }
- }
-
- /**
- * 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() {
- SlotRef slotRef = unwrapSlotRef(false);
- if (slotRef == null) return null;
- SlotDescriptor slotDesc = slotRef.getDesc();
- if (slotDesc.isScanSlot()) return slotDesc;
- if (slotDesc.getSourceExprs().size() == 1) {
- return slotDesc.getSourceExprs().get(0).findSrcScanSlot();
- }
- // No known source expr, or there are several source exprs meaning the slot is
- // has no single source table.
- return null;
- }
-
- /**
- * Pushes negation to the individual operands of a predicate
- * tree rooted at 'root'.
- */
- 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;
- }
-
- /**
- * 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 = Lists.newArrayList();
- collect(Subquery.class, subqueries);
- Preconditions.checkState(subqueries.size() == 1);
- return subqueries.get(0);
- }
-
- /**
- * For children of 'this' that are constant expressions and the type of which has a
- * LiteralExpr subclass, evaluate them in the BE and substitute the child with the
- * resulting LiteralExpr. Modifies 'this' in place and does not re-analyze it. Hence,
- * it is not safe to evaluate the modified expr in the BE as the resolved fn_ may be
- * incorrect given the new arguments.
- *
- * Throws an AnalysisException if the evaluation fails in the BE.
- *
- * TODO: Convert to a generic constant expr folding function to be used during analysis.
- */
- 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());
- if (literalExpr == null) continue;
- setChild(i, literalExpr);
- }
- isAnalyzed_ = false;
- }
-
- /**
- * 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).getValue().length();
- } else {
- // TODO(tmarshall): Extend this to support other string Exprs, such as
- // function calls that return string.
- return DEFAULT_AVG_STRING_LENGTH;
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/b544f019/fe/src/main/java/com/cloudera/impala/analysis/ExprId.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/com/cloudera/impala/analysis/ExprId.java b/fe/src/main/java/com/cloudera/impala/analysis/ExprId.java
deleted file mode 100644
index 52292f5..0000000
--- a/fe/src/main/java/com/cloudera/impala/analysis/ExprId.java
+++ /dev/null
@@ -1,37 +0,0 @@
-// 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 com.cloudera.impala.analysis;
-
-import com.cloudera.impala.common.Id;
-import com.cloudera.impala.common.IdGenerator;
-
-public class ExprId extends Id<ExprId> {
- // Construction only allowed via an IdGenerator.
- protected ExprId(int id) {
- super(id);
- }
-
- public static IdGenerator<ExprId> createGenerator() {
- return new IdGenerator<ExprId>() {
- @Override
- public ExprId getNextId() { return new ExprId(nextId_++); }
- @Override
- public ExprId getMaxId() { return new ExprId(nextId_ - 1); }
- };
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/b544f019/fe/src/main/java/com/cloudera/impala/analysis/ExprSubstitutionMap.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/com/cloudera/impala/analysis/ExprSubstitutionMap.java b/fe/src/main/java/com/cloudera/impala/analysis/ExprSubstitutionMap.java
deleted file mode 100644
index cbff71a..0000000
--- a/fe/src/main/java/com/cloudera/impala/analysis/ExprSubstitutionMap.java
+++ /dev/null
@@ -1,176 +0,0 @@
-// 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 com.cloudera.impala.analysis;
-
-import java.util.List;
-
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import com.google.common.base.Joiner;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
-
-/**
- * Map of expression substitutions: lhs[i] gets substituted with rhs[i].
- * To support expression substitution across query blocks, rhs exprs must already be
- * analyzed when added to this map. Otherwise, analysis of a SlotRef may fail after
- * substitution, e.g., because the table it refers to is in a different query block
- * that is not visible.
- * See Expr.substitute() and related functions for details on the actual substitution.
- */
-public final class ExprSubstitutionMap {
- private final static Logger LOG = LoggerFactory.getLogger(ExprSubstitutionMap.class);
-
- private List<Expr> lhs_; // left-hand side
- private List<Expr> rhs_; // right-hand side
-
- public ExprSubstitutionMap() {
- this(Lists.<Expr>newArrayList(), Lists.<Expr>newArrayList());
- }
-
- public ExprSubstitutionMap(List<Expr> lhs, List<Expr> rhs) {
- lhs_ = lhs;
- rhs_ = rhs;
- }
-
- /**
- * Add an expr mapping. The rhsExpr must be analyzed to support correct substitution
- * across query blocks. It is not required that the lhsExpr is analyzed.
- */
- public void put(Expr lhsExpr, Expr rhsExpr) {
- Preconditions.checkState(rhsExpr.isAnalyzed_, "Rhs expr must be analyzed.");
- lhs_.add(lhsExpr);
- rhs_.add(rhsExpr);
- }
-
- /**
- * Returns the expr mapped to lhsExpr or null if no mapping to lhsExpr exists.
- */
- public Expr get(Expr lhsExpr) {
- for (int i = 0; i < lhs_.size(); ++i) {
- if (lhsExpr.equals(lhs_.get(i))) return rhs_.get(i);
- }
- return null;
- }
-
- /**
- * Returns true if the smap contains a mapping for lhsExpr.
- */
- public boolean containsMappingFor(Expr lhsExpr) {
- return lhs_.contains(lhsExpr);
- }
-
- /**
- * Return a map which is equivalent to applying f followed by g,
- * i.e., g(f()).
- * Always returns a non-null map.
- */
- public static ExprSubstitutionMap compose(ExprSubstitutionMap f, ExprSubstitutionMap g,
- Analyzer analyzer) {
- if (f == null && g == null) return new ExprSubstitutionMap();
- if (f == null) return g;
- if (g == null) return f;
- ExprSubstitutionMap result = new ExprSubstitutionMap();
- // f's substitution targets need to be substituted via g
- result.lhs_ = Expr.cloneList(f.lhs_);
- result.rhs_ = Expr.substituteList(f.rhs_, g, analyzer, false);
-
- // substitution maps are cumulative: the combined map contains all
- // substitutions from f and g.
- for (int i = 0; i < g.lhs_.size(); i++) {
- // If f contains expr1->fn(expr2) and g contains expr2->expr3,
- // then result must contain expr1->fn(expr3).
- // The check before adding to result.lhs is to ensure that cases
- // where expr2.equals(expr1) are handled correctly.
- // For example f: count(*) -> zeroifnull(count(*))
- // and g: count(*) -> slotref
- // result.lhs must only have: count(*) -> zeroifnull(slotref) from f above,
- // and not count(*) -> slotref from g as well.
- if (!result.lhs_.contains(g.lhs_.get(i))) {
- result.lhs_.add(g.lhs_.get(i).clone());
- result.rhs_.add(g.rhs_.get(i).clone());
- }
- }
-
- result.verify();
- return result;
- }
-
- /**
- * Returns the union of two substitution maps. Always returns a non-null map.
- */
- public static ExprSubstitutionMap combine(ExprSubstitutionMap f,
- ExprSubstitutionMap g) {
- if (f == null && g == null) return new ExprSubstitutionMap();
- if (f == null) return g;
- if (g == null) return f;
- ExprSubstitutionMap result = new ExprSubstitutionMap();
- result.lhs_ = Lists.newArrayList(f.lhs_);
- result.lhs_.addAll(g.lhs_);
- result.rhs_ = Lists.newArrayList(f.rhs_);
- result.rhs_.addAll(g.rhs_);
- result.verify();
- return result;
- }
-
- public void substituteLhs(ExprSubstitutionMap lhsSmap, Analyzer analyzer) {
- lhs_ = Expr.substituteList(lhs_, lhsSmap, analyzer, false);
- }
-
- public List<Expr> getLhs() { return lhs_; }
- public List<Expr> getRhs() { return rhs_; }
-
- public int size() { return lhs_.size(); }
-
- public String debugString() {
- Preconditions.checkState(lhs_.size() == rhs_.size());
- List<String> output = Lists.newArrayList();
- for (int i = 0; i < lhs_.size(); ++i) {
- output.add(lhs_.get(i).toSql() + ":" + rhs_.get(i).toSql());
- output.add("(" + lhs_.get(i).debugString() + ":" + rhs_.get(i).debugString() + ")");
- }
- return "smap(" + Joiner.on(" ").join(output) + ")";
- }
-
- /**
- * Verifies the internal state of this smap: Checks that the lhs_ has no duplicates,
- * and that all rhs exprs are analyzed.
- */
- private void verify() {
- for (int i = 0; i < lhs_.size(); ++i) {
- for (int j = i + 1; j < lhs_.size(); ++j) {
- if (lhs_.get(i).equals(lhs_.get(j))) {
- LOG.info("verify: smap=" + this.debugString());
- Preconditions.checkState(false);
- }
- }
- Preconditions.checkState(rhs_.get(i).isAnalyzed_);
- }
- }
-
- public void clear() {
- lhs_.clear();
- rhs_.clear();
- }
-
- @Override
- public ExprSubstitutionMap clone() {
- return new ExprSubstitutionMap(Expr.cloneList(lhs_), Expr.cloneList(rhs_));
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/b544f019/fe/src/main/java/com/cloudera/impala/analysis/ExtractFromExpr.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/com/cloudera/impala/analysis/ExtractFromExpr.java b/fe/src/main/java/com/cloudera/impala/analysis/ExtractFromExpr.java
deleted file mode 100644
index 48b9fb3..0000000
--- a/fe/src/main/java/com/cloudera/impala/analysis/ExtractFromExpr.java
+++ /dev/null
@@ -1,111 +0,0 @@
-// 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 com.cloudera.impala.analysis;
-
-import java.util.Set;
-
-import com.cloudera.impala.catalog.Catalog;
-import com.cloudera.impala.catalog.Type;
-import com.cloudera.impala.common.AnalysisException;
-import com.cloudera.impala.thrift.TExtractField;
-import com.google.common.base.Joiner;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Lists;
-
-/**
- * Representation of an EXTRACT(<Time Unit> FROM <Datetime Expr>) expression. EXTRACT(
- * <Datetime Expr>, <String>) is not handled by FunctionCallExpr.
- */
-public class ExtractFromExpr extends FunctionCallExpr {
-
- // Behaves like an immutable linked hash set containing the TExtractFields in the same
- // order as declared.
- private static final Set<String> EXTRACT_FIELDS;
- static {
- ImmutableSet.Builder<String> builder = new ImmutableSet.Builder<String>();
- for (TExtractField extractField: TExtractField.values()) {
- if (extractField != TExtractField.INVALID_FIELD) {
- builder.add(extractField.name());
- }
- }
- EXTRACT_FIELDS = builder.build();
- }
-
- public ExtractFromExpr(FunctionName fnName, String extractFieldIdent, Expr e) {
- // Note that the arguments are swapped so that they align with the EXTRACT function.
- // There is no EXTRACT(STRING, TIMESTAMP) function because it conflicts with
- // EXTRACT(TIMESTAMP, STRING) if STRINGs are used for TIMESTAMPs with implicit
- // casting.
- super(fnName, Lists.newArrayList(e, new StringLiteral(extractFieldIdent)));
- type_ = Type.INT;
- }
-
- /**
- * Copy c'tor used in clone().
- */
- protected ExtractFromExpr(ExtractFromExpr other) {
- super(other);
- }
-
- @Override
- public void analyze(Analyzer analyzer) throws AnalysisException {
- getFnName().analyze(analyzer);
- if (!getFnName().getFunction().equals("extract")) {
- throw new AnalysisException("Function " + getFnName().getFunction().toUpperCase()
- + " does not accept the keyword FROM.");
- }
- if ((getFnName().getDb() != null)
- && !getFnName().getDb().equals(Catalog.BUILTINS_DB)) {
- throw new AnalysisException("Function " + getFnName().toString() + " conflicts " +
- "with the EXTRACT builtin.");
- }
- if (isAnalyzed_) return;
- super.analyze(analyzer);
-
- String extractFieldIdent = ((StringLiteral)children_.get(1)).getValue();
- Preconditions.checkNotNull(extractFieldIdent);
- if (!EXTRACT_FIELDS.contains(extractFieldIdent.toUpperCase())) {
- throw new AnalysisException("Time unit '" + extractFieldIdent + "' in expression '"
- + toSql() + "' is invalid. Expected one of "
- + Joiner.on(", ").join(EXTRACT_FIELDS) + ".");
- }
- }
-
- @Override
- protected String getFunctionNotFoundError(Type[] argTypes) {
- Expr e = children_.get(0);
- return "Expression '" + e.toSql() + "' in '" + toSql() + "' has a return type of "
- + e.getType().toSql() + " but a TIMESTAMP is required.";
- }
-
- @Override
- public String toSqlImpl() {
- StringBuilder strBuilder = new StringBuilder();
- strBuilder.append(getFnName().toString().toUpperCase());
- strBuilder.append("(");
- strBuilder.append(((StringLiteral)getChild(1)).getValue());
- strBuilder.append(" FROM ");
- strBuilder.append(getChild(0).toSql());
- strBuilder.append(")");
- return strBuilder.toString();
- }
-
- @Override
- public Expr clone() { return new ExtractFromExpr(this); }
-}
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/b544f019/fe/src/main/java/com/cloudera/impala/analysis/FromClause.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/com/cloudera/impala/analysis/FromClause.java b/fe/src/main/java/com/cloudera/impala/analysis/FromClause.java
deleted file mode 100644
index bbe6f23..0000000
--- a/fe/src/main/java/com/cloudera/impala/analysis/FromClause.java
+++ /dev/null
@@ -1,129 +0,0 @@
-// 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 com.cloudera.impala.analysis;
-
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-
-import com.cloudera.impala.common.AnalysisException;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
-
-/**
- * Wraps a list of TableRef instances that form a FROM clause, allowing them to be
- * analyzed independently of the statement using them. To increase the flexibility of
- * the class it implements the Iterable interface.
- */
-public class FromClause implements ParseNode, Iterable<TableRef> {
-
- private final ArrayList<TableRef> tableRefs_;
-
- private boolean analyzed_ = false;
-
- public FromClause(List<TableRef> tableRefs) {
- tableRefs_ = Lists.newArrayList(tableRefs);
- // Set left table refs to ensure correct toSql() before analysis.
- for (int i = 1; i < tableRefs_.size(); ++i) {
- tableRefs_.get(i).setLeftTblRef(tableRefs_.get(i - 1));
- }
- }
-
- public FromClause() { tableRefs_ = Lists.newArrayList(); }
- public List<TableRef> getTableRefs() { return tableRefs_; }
-
- @Override
- public void analyze(Analyzer analyzer) throws AnalysisException {
- if (analyzed_) return;
-
- if (tableRefs_.isEmpty()) {
- analyzed_ = true;
- return;
- }
-
- // Start out with table refs to establish aliases.
- TableRef leftTblRef = null; // the one to the left of tblRef
- for (int i = 0; i < tableRefs_.size(); ++i) {
- // Resolve and replace non-InlineViewRef table refs with a BaseTableRef or ViewRef.
- TableRef tblRef = tableRefs_.get(i);
- tblRef = analyzer.resolveTableRef(tblRef);
- tableRefs_.set(i, Preconditions.checkNotNull(tblRef));
- tblRef.setLeftTblRef(leftTblRef);
- try {
- tblRef.analyze(analyzer);
- } catch (AnalysisException e) {
- // Only re-throw the exception if no tables are missing.
- if (analyzer.getMissingTbls().isEmpty()) throw e;
- }
- leftTblRef = tblRef;
- }
-
- // All tableRefs have been analyzed, but at least one table is missing metadata.
- if (!analyzer.getMissingTbls().isEmpty()) {
- throw new AnalysisException("Found missing tables. Aborting analysis.");
- }
- analyzed_ = true;
- }
-
- public FromClause clone() {
- ArrayList<TableRef> clone = Lists.newArrayList();
- for (TableRef tblRef: tableRefs_) clone.add(tblRef.clone());
- return new FromClause(clone);
- }
-
- public void reset() {
- for (int i = 0; i < size(); ++i) {
- TableRef origTblRef = get(i);
- if (origTblRef.isResolved() && !(origTblRef instanceof InlineViewRef)) {
- // Replace resolved table refs with unresolved ones.
- TableRef newTblRef = new TableRef(origTblRef);
- // Use the fully qualified raw path to preserve the original resolution.
- // Otherwise, non-fully qualified paths might incorrectly match a local view.
- // TODO for 2.3: This full qualification preserves analysis state which is
- // contrary to the intended semantics of reset(). We could address this issue by
- // changing the WITH-clause analysis to register local views that have
- // fully-qualified table refs, and then remove the full qualification here.
- newTblRef.rawPath_ = origTblRef.getResolvedPath().getFullyQualifiedRawPath();
- set(i, newTblRef);
- }
- get(i).reset();
- }
- this.analyzed_ = false;
- }
-
- @Override
- public String toSql() {
- StringBuilder builder = new StringBuilder();
- if (!tableRefs_.isEmpty()) {
- builder.append(" FROM ");
- for (int i = 0; i < tableRefs_.size(); ++i) {
- builder.append(tableRefs_.get(i).toSql());
- }
- }
- return builder.toString();
- }
-
- public boolean isEmpty() { return tableRefs_.isEmpty(); }
-
- @Override
- public Iterator<TableRef> iterator() { return tableRefs_.iterator(); }
- public int size() { return tableRefs_.size(); }
- public TableRef get(int i) { return tableRefs_.get(i); }
- public void set(int i, TableRef tableRef) { tableRefs_.set(i, tableRef); }
- public void add(TableRef t) { tableRefs_.add(t); }
-}
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/b544f019/fe/src/main/java/com/cloudera/impala/analysis/FunctionArgs.java
----------------------------------------------------------------------
diff --git a/fe/src/main/java/com/cloudera/impala/analysis/FunctionArgs.java b/fe/src/main/java/com/cloudera/impala/analysis/FunctionArgs.java
deleted file mode 100644
index 998c5fc..0000000
--- a/fe/src/main/java/com/cloudera/impala/analysis/FunctionArgs.java
+++ /dev/null
@@ -1,67 +0,0 @@
-// 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 com.cloudera.impala.analysis;
-
-import java.util.ArrayList;
-
-import com.cloudera.impala.catalog.Type;
-import com.cloudera.impala.common.AnalysisException;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
-
-// Wrapper class around argument types and if it has varArgs
-public class FunctionArgs implements ParseNode {
- private final ArrayList<TypeDef> argTypeDefs_;
- private boolean hasVarArgs_;
-
- // Result of analysis.
- private ArrayList<Type> argTypes_;
-
- public FunctionArgs() {
- argTypeDefs_ = Lists.newArrayList();
- hasVarArgs_ = false;
- }
-
- public FunctionArgs(ArrayList<TypeDef> argTypeDefs, boolean varArgs) {
- argTypeDefs_ = argTypeDefs;
- hasVarArgs_ = varArgs;
- if (varArgs) Preconditions.checkState(argTypeDefs.size() > 0);
- }
-
- public void setHasVarArgs(boolean b) { {
- Preconditions.checkState(argTypeDefs_.size() > 0);
- hasVarArgs_ = b; }
- }
-
- @Override
- public void analyze(Analyzer analyzer) throws AnalysisException {
- ArrayList<Type> argTypes = Lists.newArrayListWithCapacity(argTypeDefs_.size());
- for (TypeDef typeDef: argTypeDefs_) {
- typeDef.analyze(analyzer);
- argTypes.add(typeDef.getType());
- }
- argTypes_ = argTypes;
- }
-
- public ArrayList<TypeDef> getArgTypeDefs() { return argTypeDefs_; }
- public ArrayList<Type> getArgTypes() { return argTypes_; }
- public boolean hasVarArgs() { return hasVarArgs_; }
-
- @Override
- public String toSql() { return null; }
-}