content: /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to you under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.calcite.plan;
  
  import org.apache.calcite.rex.RexCall;
  import org.apache.calcite.rex.RexFieldAccess;
  import org.apache.calcite.rex.RexInputRef;
  import org.apache.calcite.rex.RexLiteral;
  import org.apache.calcite.rex.RexNode;
  import org.apache.calcite.rex.RexSubQuery;
  import org.apache.calcite.rex.RexUnknownAs;
  import org.apache.calcite.rex.RexUtil;
  import org.apache.calcite.rex.RexVisitorImpl;
  import org.apache.calcite.sql.SqlKind;
  import org.apache.calcite.sql.SqlOperator;
  import org.apache.calcite.sql.fun.SqlQuantifyOperator;
  import org.apache.calcite.util.ImmutableBitSet;
  import org.apache.calcite.util.Sarg;
  
  import com.google.common.collect.ImmutableList;
  import com.google.common.collect.ImmutableSet;
  import com.google.common.collect.Iterables;
  
  import java.util.ArrayList;
  import java.util.EnumMap;
  import java.util.List;
  import java.util.Map;
  
  import static java.util.Objects.requireNonNull;
  
  /** Utilities for strong predicates.
   *
   * <p>A predicate is strong (or null-rejecting) with regard to selected subset of inputs
   * if it is UNKNOWN if all inputs in selected subset are UNKNOWN.
   *
   * <p>By the way, UNKNOWN is just the boolean form of NULL.
   *
   * <p>Examples:
   * <ul>
   *   <li>{@code UNKNOWN} is strong in [] (definitely null)
   *   <li>{@code c = 1} is strong in [c] (definitely null if and only if c is
   *   null)
   *   <li>{@code c IS NULL} is not strong (always returns TRUE or FALSE, never
   *   null)
   *   <li>{@code p1 AND p2} is strong in [p1, p2] (definitely null if either p1
   *   is null or p2 is null)
   *   <li>{@code p1 OR p2} is strong if p1 and p2 are strong
   * </ul>
   */
  public class Strong {
    private static final Map<SqlKind, Policy> MAP = createPolicyMap();
  
    public Strong() {
      super();
    }
  
    /** Returns a checker that consults a bit set to find out whether particular
     * inputs may be null. */
    public static Strong of(final ImmutableBitSet nullColumns) {
      return new Strong() {
        @Override public boolean isNull(RexInputRef ref) {
          return nullColumns.get(ref.getIndex());
        }
      };
    }
  
    /** Returns a checker that consults a set to find out whether particular
     * field may be null. */
    public static Strong of(final ImmutableSet<RexFieldAccess> nullFields) {
      return new Strong() {
        @Override public boolean isNull(RexFieldAccess ref) {
          return nullFields.contains(ref);
        }
      };
    }
  
    /** Returns whether the analyzed expression will definitely return null if
     * all of a given set of input columns are null. */
    public static boolean isNull(RexNode node, ImmutableBitSet nullColumns) {
      return of(nullColumns).isNull(node);
    }
  
    /** Returns whether the analyzed expression will definitely not return true
     * (equivalently, will definitely return null or false) if
     * all of a given set of input columns are null. */
    public static boolean isNotTrue(RexNode node, ImmutableBitSet nullColumns) {
      return of(nullColumns).isNotTrue(node);
    }
  
    /**
     * Returns how to deduce whether a particular kind of expression is null,
     * given whether its arguments are null.
     *
     * @deprecated Use {@link Strong#policy(RexNode)} or {@link Strong#policy(SqlOperator)}
     */
    @Deprecated // to be removed before 2.0
    public static Policy policy(SqlKind kind) {
      return MAP.getOrDefault(kind, Policy.AS_IS);
    }
  
    /**
     * Returns how to deduce whether a particular {@link RexNode} expression is null,
     * given whether its arguments are null.
     */
    public static Policy policy(RexNode rexNode) {
      if (rexNode instanceof RexCall) {
        return policy(((RexCall) rexNode).getOperator());
      }
      return MAP.getOrDefault(rexNode.getKind(), Policy.AS_IS);
    }
  
    /**
     * Returns how to deduce whether a particular {@link SqlOperator} expression is null,
     * given whether its arguments are null.
     */
    public static Policy policy(SqlOperator operator) {
      if (operator.getStrongPolicyInference() != null) {
        return operator.getStrongPolicyInference().get();
      }
      return MAP.getOrDefault(operator.getKind(), Policy.AS_IS);
    }
  
    /**
     * Returns whether a given expression is strong.
     *
     * <p>Examples:
     * <ul>
     *   <li>Returns true for {@code c = 1} since it returns null if and only if
     *   c is null
     *   <li>Returns false for {@code c IS NULL} since it always returns TRUE
     *   or FALSE
     *</ul>
     *
     * @param e Expression
     * @return true if the expression is strong, false otherwise
     */
    public static boolean isStrong(RexNode e) {
      final ImmutableBitSet.Builder nullColumns = ImmutableBitSet.builder();
      e.accept(
          new RexVisitorImpl<Void>(true) {
            @Override public Void visitInputRef(RexInputRef inputRef) {
              nullColumns.set(inputRef.getIndex());
              return super.visitInputRef(inputRef);
            }
          });
      return isNull(e, nullColumns.build());
    }
  
    /** Returns whether all expressions in a list are strong. */
    public static boolean allStrong(List<RexNode> operands) {
      return operands.stream().allMatch(Strong::isStrong);
    }
  
    /** Returns whether the analyzed expression will definitely not return true
     * (equivalently, will definitely return null or false). */
    public boolean isNotTrue(RexNode node) {
      switch (node.getKind()) {
      // TODO Enrich with more possible cases?
      case IS_NOT_NULL:
        return isNull(((RexCall) node).getOperands().get(0));
      case OR:
        return allNotTrue(((RexCall) node).getOperands());
      case AND:
        return anyNotTrue(((RexCall) node).getOperands());
      default:
        return isNull(node);
      }
    }
  
    /** Returns whether all expressions in a list are definitely not true. */
    private boolean allNotTrue(List<RexNode> operands) {
      for (RexNode operand : operands) {
        if (!isNotTrue(operand)) {
          return false;
        }
      }
      return true;
    }
  
    /** Returns whether any expressions in a list are definitely not true. */
    private boolean anyNotTrue(List<RexNode> operands) {
      for (RexNode operand : operands) {
        if (isNotTrue(operand)) {
          return true;
        }
      }
      return false;
    }
  
    /** Returns whether an expression is definitely null.
     *
     * <p>The answer is based on calls to {@link #isNull} for its constituent
     * expressions, and you may override methods to test hypotheses such as
     * "if {@code x} is null, is {@code x + y} null? */
    public boolean isNull(RexNode node) {
      final Policy policy = policy(node);
      switch (policy) {
      case NOT_NULL:
        return false;
      case ANY:
        return anyNull(((RexCall) node).getOperands());
      default:
        break;
      }
  
      switch (node.getKind()) {
      case LITERAL:
        return ((RexLiteral) node).isNull();
      // We can only guarantee AND to return NULL if both inputs are NULL  (similar for OR)
      // AND(NULL, FALSE) = FALSE
      case AND:
      case OR:
      case COALESCE:
        return allNull(((RexCall) node).getOperands());
      case NULLIF:
        // NULLIF(null, X) where X can be NULL, returns NULL
        // NULLIF(X, Y) where X is not NULL, then this may return NULL if X = Y, otherwise X.
        return allNull(ImmutableList.of(((RexCall) node).getOperands().get(0)));
      case INPUT_REF:
        return isNull((RexInputRef) node);
      case FIELD_ACCESS:
        return isNull((RexFieldAccess) node);
      case CASE:
        final RexCall caseCall = (RexCall) node;
        final List<RexNode> caseValues = new ArrayList<>();
        for (int i = 0; i < caseCall.getOperands().size(); i++) {
          if (!RexUtil.isCasePredicate(caseCall, i)) {
            caseValues.add(caseCall.getOperands().get(i));
          }
        }
        return allNull(caseValues);
      case SEARCH:
        final RexCall searchCall = (RexCall) node;
        boolean isNull = isNull(searchCall.getOperands().get(0));
        if (isNull) {
          final Sarg<?> sarg =
              requireNonNull(((RexLiteral) searchCall.getOperands().get(1)).getValueAs(Sarg.class));
          return sarg.nullAs == RexUnknownAs.UNKNOWN;
        }
        return false;
      case SOME:
      case ALL:
        final RexCall rexCall = (RexCall) node;
        // For example:
        // select NULL > all (select comm from emp where 1 = 0) from emp
        // return FALSE when the sub-query returns 0 row
        if (rexCall instanceof RexSubQuery) {
          return false;
        }
        if (rexCall.getOperator() instanceof SqlQuantifyOperator) {
          return anyNull(rexCall.getOperands());
        }
        return false;
      default:
        return false;
      }
    }
  
    /** Returns whether a given input is definitely null. */
    public boolean isNull(RexInputRef ref) {
      return false;
    }
  
    /** Returns whether a given field is definitely null. */
    public boolean isNull(RexFieldAccess ref) {
      return false;
    }
  
    /** Returns whether all expressions in a list are definitely null. */
    private boolean allNull(List<RexNode> operands) {
      for (RexNode operand : operands) {
        if (!isNull(operand)) {
          return false;
        }
      }
      return true;
    }
  
    /** Returns whether any expressions in a list are definitely null. */
    private boolean anyNull(List<RexNode> operands) {
      for (RexNode operand : operands) {
        if (isNull(operand)) {
          return true;
        }
      }
      return false;
    }
  
    private static Map<SqlKind, Policy> createPolicyMap() {
      EnumMap<SqlKind, Policy> map = new EnumMap<>(SqlKind.class);
  
      map.put(SqlKind.INPUT_REF, Policy.AS_IS);
      map.put(SqlKind.LOCAL_REF, Policy.AS_IS);
      map.put(SqlKind.DYNAMIC_PARAM, Policy.AS_IS);
      map.put(SqlKind.OTHER_FUNCTION, Policy.AS_IS);
  
      // The following types of expressions could potentially be custom.
      map.put(SqlKind.CASE, Policy.AS_IS);
      map.put(SqlKind.DECODE, Policy.AS_IS);
      // NULLIF(1, NULL) yields 1, but NULLIF(1, 1) yields NULL
      map.put(SqlKind.NULLIF, Policy.AS_IS);
      // COALESCE(NULL, 2) yields 2
      map.put(SqlKind.COALESCE, Policy.AS_IS);
      map.put(SqlKind.NVL, Policy.AS_IS);
      // FALSE AND NULL yields FALSE
      // TRUE AND NULL yields NULL
      map.put(SqlKind.AND, Policy.AS_IS);
      // TRUE OR NULL yields TRUE
      // FALSE OR NULL yields NULL
      map.put(SqlKind.OR, Policy.AS_IS);
  
      // Expression types with custom handlers.
      map.put(SqlKind.LITERAL, Policy.CUSTOM);
  
      map.put(SqlKind.EXISTS, Policy.NOT_NULL);
      map.put(SqlKind.IS_DISTINCT_FROM, Policy.NOT_NULL);
      map.put(SqlKind.IS_NOT_DISTINCT_FROM, Policy.NOT_NULL);
      map.put(SqlKind.IS_NULL, Policy.NOT_NULL);
      map.put(SqlKind.IS_NOT_NULL, Policy.NOT_NULL);
      map.put(SqlKind.IS_TRUE, Policy.NOT_NULL);
      map.put(SqlKind.IS_NOT_TRUE, Policy.NOT_NULL);
      map.put(SqlKind.IS_FALSE, Policy.NOT_NULL);
      map.put(SqlKind.IS_NOT_FALSE, Policy.NOT_NULL);
  
      map.put(SqlKind.NOT, Policy.ANY);
      map.put(SqlKind.EQUALS, Policy.ANY);
      map.put(SqlKind.NOT_EQUALS, Policy.ANY);
      map.put(SqlKind.LESS_THAN, Policy.ANY);
      map.put(SqlKind.LESS_THAN_OR_EQUAL, Policy.ANY);
      map.put(SqlKind.GREATER_THAN, Policy.ANY);
      map.put(SqlKind.GREATER_THAN_OR_EQUAL, Policy.ANY);
      map.put(SqlKind.LIKE, Policy.ANY);
      map.put(SqlKind.SIMILAR, Policy.ANY);
      map.put(SqlKind.PLUS, Policy.ANY);
      map.put(SqlKind.PLUS_PREFIX, Policy.ANY);
      map.put(SqlKind.MINUS, Policy.ANY);
      map.put(SqlKind.MINUS_PREFIX, Policy.ANY);
      map.put(SqlKind.TIMES, Policy.ANY);
      map.put(SqlKind.CHECKED_PLUS, Policy.ANY);
      map.put(SqlKind.CHECKED_MINUS, Policy.ANY);
      map.put(SqlKind.CHECKED_MINUS_PREFIX, Policy.ANY);
      map.put(SqlKind.CHECKED_TIMES, Policy.ANY);
      map.put(SqlKind.CHECKED_DIVIDE, Policy.ANY);
  
      map.put(SqlKind.DIVIDE, Policy.ANY);
      map.put(SqlKind.CAST, Policy.ANY);
      map.put(SqlKind.REINTERPRET, Policy.ANY);
      map.put(SqlKind.TRIM, Policy.ANY);
      map.put(SqlKind.LTRIM, Policy.ANY);
      map.put(SqlKind.RTRIM, Policy.ANY);
      map.put(SqlKind.CEIL, Policy.ANY);
      map.put(SqlKind.FLOOR, Policy.ANY);
      map.put(SqlKind.EXTRACT, Policy.ANY);
      map.put(SqlKind.GREATEST, Policy.ANY);
      map.put(SqlKind.LEAST, Policy.ANY);
      map.put(SqlKind.TIMESTAMP_ADD, Policy.ANY);
      map.put(SqlKind.TIMESTAMP_DIFF, Policy.ANY);
      map.put(SqlKind.ITEM, Policy.ANY);
  
      // Assume that any other expressions cannot be simplified.
      for (SqlKind k
          : Iterables.concat(SqlKind.EXPRESSION, SqlKind.AGGREGATE)) {
        if (!map.containsKey(k)) {
          map.put(k, Policy.AS_IS);
        }
      }
      return map;
    }
  
    /** How whether an operator's operands are null affects whether a call to
     * that operator evaluates to null. */
    public enum Policy {
      /** This kind of expression is never null. No need to look at its arguments,
       * if it has any. */
      NOT_NULL,
  
      /** This kind of expression has its own particular rules about whether it
       * is null. */
      CUSTOM,
  
      /** This kind of expression is null if and only if at least one of its
       * arguments is null. */
      ANY,
  
      /** This kind of expression may be null. There is no way to rewrite. */
      AS_IS,
    }
  }
  