Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * 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.facebook.presto.sql.planner;
 
 
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
 import static com.facebook.presto.sql.ExpressionUtils.extractConjuncts;
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Predicates.equalTo;
 import static com.google.common.base.Predicates.not;
 import static com.google.common.collect.Iterables.filter;

Makes equality based inferences to rewrite Expressions and generate equality sets in terms of specified symbol scopes
 
 public class EqualityInference
 {
     // Ordering used to determine Expression preference when determining canonicals
     private static final Ordering<ExpressionCANONICAL_ORDERING = Ordering.from(new Comparator<Expression>()
     {
         @Override
         public int compare(Expression expression1Expression expression2)
         {
             // Current cost heuristic:
             // 1) Prefer fewer input symbols
             // 2) Prefer smaller expression trees
             // 3) Ordering.arbitrary() - creates a stable consistent ordering (extremely useful for unit testing)
             // TODO: be more precise in determining the cost of an expression
             return ComparisonChain.start()
                     .compare(DependencyExtractor.extractAll(expression1).size(), DependencyExtractor.extractAll(expression2).size())
                     .compare(SubExpressionExtractor.extract(expression1).size(), SubExpressionExtractor.extract(expression2).size())
                     .compare(expression1expression2, Ordering.arbitrary())
                     .result();
         }
     });
 
     private final SetMultimap<ExpressionExpressionequalitySets// Indexed by canonical expression
     private final Map<ExpressionExpressioncanonicalMap// Map each known expression to canonical expression
 
     private EqualityInference(Iterable<Set<Expression>> equalityGroups)
     {
         ImmutableSetMultimap.Builder<ExpressionExpressionsetBuilder = ImmutableSetMultimap.builder();
         for (Set<ExpressionequalityGroup : equalityGroups) {
             if (!equalityGroup.isEmpty()) {
                 setBuilder.putAll(.min(equalityGroup), equalityGroup);
             }
         }
          = setBuilder.build();
 
         ImmutableMap.Builder<ExpressionExpressionmapBuilder = ImmutableMap.builder();
         for (Map.Entry<ExpressionExpressionentry : .entries()) {
             Expression canonical = entry.getKey();
             Expression expression = entry.getValue();
             mapBuilder.put(expressioncanonical);
         }
          = mapBuilder.build();
     }

    
Attempts to rewrite an Expression in terms of the symbols allowed by the symbol scope given the known equalities. Returns null if unsuccessful.
    public Expression rewriteExpression(Expression expressionPredicate<SymbolsymbolScope)
    {
        checkArgument(DeterminismEvaluator.isDeterministic(expression), "Only deterministic expressions may be considered for rewrite");
        return rewriteExpression(expressionsymbolScopetrue);
    }
    private Expression rewriteExpression(Expression expressionPredicate<SymbolsymbolScopeboolean allowFullReplacement)
    {
        Iterable<ExpressionsubExpressions = SubExpressionExtractor.extract(expression);
        if (!allowFullReplacement) {
            subExpressions = filter(subExpressionsnot(equalTo(expression)));
        }
        ImmutableMap.Builder<ExpressionExpressionexpressionRemap = ImmutableMap.builder();
        for (Expression subExpression : subExpressions) {
            Expression canonical = getScopedCanonical(subExpressionsymbolScope);
            if (canonical != null) {
                expressionRemap.put(subExpressioncanonical);
            }
        }
        // Perform a naive single-pass traversal to try to rewrite non-compliant portions of the tree. Prefers to replace
        // larger subtrees over smaller subtrees
        // TODO: this rewrite can probably be made more sophisticated
        Expression rewritten = ExpressionTreeRewriter.rewriteWith(new ExpressionNodeInliner(expressionRemap.build()), expression);
        if (!symbolToExpressionPredicate(symbolScope).apply(rewritten)) {
            // If the rewritten is still not compliant with the symbol scope, just give up
            return null;
        }
        return rewritten;
    }

    
Dumps the inference equalities as equality expressions that are partitioned by the symbolScope. All stored equalities are returned in a compact set and will be classified into three groups as determined by the symbol scope:
  1. equalities that fit entirely within the symbol scope
  2. equalities that fit entirely outside of the symbol scope
  3. equalities that straddle the symbol scope
 Example:
   Stored Equalities:
     a = b = c
     d = e = f = g

   Symbol Scope:
     a, b, d, e

   Output EqualityPartition:
     Scope Equalities:
       a = b
       d = e
     Complement Scope Equalities
       f = g
     Scope Straddling Equalities
       a = c
       d = f
 
    {
        Set<ExpressionscopeEqualities = new HashSet<>();
        Set<ExpressionscopeComplementEqualities = new HashSet<>();
        Set<ExpressionscopeStraddlingEqualities = new HashSet<>();
        for (Collection<ExpressionequalitySet : .asMap().values()) {
            Set<ExpressionscopeExpressions = new HashSet<>();
            Set<ExpressionscopeComplementExpressions = new HashSet<>();
            Set<ExpressionscopeStraddlingExpressions = new HashSet<>();
            // Try to push each expression into one side of the scope
            for (Expression expression : equalitySet) {
                Expression scopeRewritten = rewriteExpression(expressionsymbolScopefalse);
                if (scopeRewritten != null) {
                    scopeExpressions.add(scopeRewritten);
                }
                Expression scopeComplementRewritten = rewriteExpression(expressionnot(symbolScope), false);
                if (scopeComplementRewritten != null) {
                    scopeComplementExpressions.add(scopeComplementRewritten);
                }
                if (scopeRewritten == null && scopeComplementRewritten == null) {
                    scopeStraddlingExpressions.add(expression);
                }
            }
            // Compile the equality expressions on each side of the scope
            Expression matchingCanonical = getCanonical(scopeExpressions);
            if (scopeExpressions.size() >= 2) {
                for (Expression expression : filter(scopeExpressionsnot(equalTo(matchingCanonical)))) {
                    scopeEqualities.add(new ComparisonExpression(..matchingCanonicalexpression));
                }
            }
            Expression complementCanonical = getCanonical(scopeComplementExpressions);
            if (scopeComplementExpressions.size() >= 2) {
                for (Expression expression : filter(scopeComplementExpressionsnot(equalTo(complementCanonical)))) {
                    scopeComplementEqualities.add(new ComparisonExpression(..complementCanonicalexpression));
                }
            }
            // Compile the scope straddling equality expressions
            List<ExpressionconnectingExpressions = new ArrayList<>();
            connectingExpressions.add(matchingCanonical);
            connectingExpressions.add(complementCanonical);
            connectingExpressions.addAll(scopeStraddlingExpressions);
            connectingExpressions = ImmutableList.copyOf(filter(connectingExpressions, Predicates.notNull()));
            Expression connectingCanonical = getCanonical(connectingExpressions);
            if (connectingCanonical != null) {
                for (Expression expression : filter(connectingExpressionsnot(equalTo(connectingCanonical)))) {
                    scopeStraddlingEqualities.add(new ComparisonExpression(..connectingCanonicalexpression));
                }
            }
        }
        return new EqualityPartition(scopeEqualitiesscopeComplementEqualitiesscopeStraddlingEqualities);
    }

    
Returns the most preferrable expression to be used as the canonical expression
    private static Expression getCanonical(Iterable<Expressionexpressions)
    {
        if (Iterables.isEmpty(expressions)) {
            return null;
        }
        return .min(expressions);
    }

    
Returns a canonical expression that is fully contained by the symbolScope and that is equivalent to the specified expression. Returns null if unable to to find a canonical.
    Expression getScopedCanonical(Expression expressionPredicate<SymbolsymbolScope)
    {
        Expression canonicalIndex = .get(expression);
        if (canonicalIndex == null) {
            return null;
        }
        return getCanonical(filter(.get(canonicalIndex), symbolToExpressionPredicate(symbolScope)));
    }
    private static Predicate<ExpressionsymbolToExpressionPredicate(final Predicate<SymbolsymbolScope)
    {
        return expression -> Iterables.all(DependencyExtractor.extractUnique(expression), symbolScope);
    }

    
Determines whether an Expression may be successfully applied to the equality inference
    public static Predicate<ExpressionisInferenceCandidate()
    {
        return expression -> {
            expression = normalizeInPredicateToEquality(expression);
            if (DeterminismEvaluator.isDeterministic(expression) && expression instanceof ComparisonExpression) {
                ComparisonExpression comparison = (ComparisonExpressionexpression;
                if (comparison.getType() == ..) {
                    // We should only consider equalities that have distinct left and right components
                    return !comparison.getLeft().equals(comparison.getRight());
                }
            }
            return false;
        };
    }

    
Rewrite single value InPredicates as equality if possible
    private static Expression normalizeInPredicateToEquality(Expression expression)
    {
        if (expression instanceof InPredicate) {
            InPredicate inPredicate = (InPredicateexpression;
            if (inPredicate.getValueList() instanceof InListExpression) {
                InListExpression valueList = (InListExpressioninPredicate.getValueList();
                if (valueList.getValues().size() == 1) {
                    return new ComparisonExpression(..inPredicate.getValue(), Iterables.getOnlyElement(valueList.getValues()));
                }
            }
        }
        return expression;
    }

    
Provides a convenience Iterable of Expression conjuncts which have not been added to the inference
    public static Iterable<ExpressionnonInferrableConjuncts(Expression expression)
    {
        return filter(extractConjuncts(expression), not(isInferenceCandidate()));
    }
    public static EqualityInference createEqualityInference(Expression... expressions)
    {
        EqualityInference.Builder builder = new EqualityInference.Builder();
        for (Expression expression : expressions) {
            builder.extractInferenceCandidates(expression);
        }
        return builder.build();
    }
    public static class EqualityPartition
    {
        private final List<ExpressionscopeEqualities;
        private final List<ExpressionscopeComplementEqualities;
        private final List<ExpressionscopeStraddlingEqualities;
        public EqualityPartition(Iterable<ExpressionscopeEqualitiesIterable<ExpressionscopeComplementEqualitiesIterable<ExpressionscopeStraddlingEqualities)
        {
            this. = ImmutableList.copyOf(checkNotNull(scopeEqualities"scopeEqualities is null"));
            this. = ImmutableList.copyOf(checkNotNull(scopeComplementEqualities"scopeComplementEqualities is null"));
            this. = ImmutableList.copyOf(checkNotNull(scopeStraddlingEqualities"scopeStraddlingEqualities is null"));
        }
        public List<ExpressiongetScopeEqualities()
        {
            return ;
        }
        public List<ExpressiongetScopeComplementEqualities()
        {
            return ;
        }
        public List<ExpressiongetScopeStraddlingEqualities()
        {
            return ;
        }
    }
    public static class Builder
    {
        private final Map<ExpressionExpressionmap = new HashMap<>();
        private final Multimap<ExpressionExpressionreverseMap = HashMultimap.create();
        public Builder extractInferenceCandidates(Expression expression)
        {
            return addAllEqualities(filter(extractConjuncts(expression), isInferenceCandidate()));
        }
        public Builder addAllEqualities(Iterable<Expressionexpressions)
        {
            for (Expression expression : expressions) {
                addEquality(expression);
            }
            return this;
        }
        public Builder addEquality(Expression expression)
        {
            expression = normalizeInPredicateToEquality(expression);
            checkArgument(isInferenceCandidate().apply(expression), "Expression must be a simple equality: " + expression);
            ComparisonExpression comparison = (ComparisonExpressionexpression;
            addEquality(comparison.getLeft(), comparison.getRight());
            return this;
        }
        public Builder addEquality(Expression expression1Expression expression2)
        {
            checkArgument(!expression1.equals(expression2), "need to provide equality between different expressions");
            checkArgument(DeterminismEvaluator.isDeterministic(expression1), "Expression must be deterministic: " + expression1);
            checkArgument(DeterminismEvaluator.isDeterministic(expression2), "Expression must be deterministic: " + expression2);
            Expression canonical1 = canonicalize(expression1);
            Expression canonical2 = canonicalize(expression2);
            if (!canonical1.equals(canonical2)) {
                .put(canonical1canonical2);
                .put(canonical2canonical1);
            }
            return this;
        }
        private Expression canonicalize(Expression expression)
        {
            while (.containsKey(expression)) {
                expression = .get(expression);
            }
            return expression;
        }
        private void collectEqualities(Expression expressionImmutableSet.Builder<Expressionbuilder)
        {
            builder.add(expression);
            for (Expression childExpression : .get(expression)) {
                collectEqualities(childExpressionbuilder);
            }
        }
        private Set<ExpressionextractEqualExpressions(Expression expression)
        {
            ImmutableSet.Builder<Expressionbuilder = ImmutableSet.builder();
            collectEqualities(canonicalize(expression), builder);
            return builder.build();
        }
        public EqualityInference build()
        {
            HashSet<ExpressionseenCanonicals = new HashSet<>();
            ImmutableList.Builder<Set<Expression>> builder = ImmutableList.builder();
            for (Expression expression : .keySet()) {
                Expression canonical = canonicalize(expression);
                if (!seenCanonicals.contains(canonical)) {
                    builder.add(extractEqualExpressions(canonical));
                    seenCanonicals.add(canonical);
                }
            }
            return new EqualityInference(builder.build());
        }
    }
New to GrepCode? Check out our FAQ X