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.rel.rules;
  
  import org.apache.calcite.plan.RelOptCluster;
  import org.apache.calcite.plan.RelOptPlanner;
  import org.apache.calcite.plan.RelTraitSet;
  import org.apache.calcite.rel.RelNode;
  import org.apache.calcite.rel.core.Calc;
  import org.apache.calcite.rel.logical.LogicalCalc;
  import org.apache.calcite.rel.type.RelDataType;
  import org.apache.calcite.rel.type.RelDataTypeFactory;
  import org.apache.calcite.rex.RexCall;
  import org.apache.calcite.rex.RexDynamicParam;
  import org.apache.calcite.rex.RexFieldAccess;
  import org.apache.calcite.rex.RexInputRef;
  import org.apache.calcite.rex.RexLiteral;
  import org.apache.calcite.rex.RexLocalRef;
  import org.apache.calcite.rex.RexNode;
  import org.apache.calcite.rex.RexProgram;
  import org.apache.calcite.rex.RexShuttle;
  import org.apache.calcite.rex.RexUtil;
  import org.apache.calcite.rex.RexVisitorImpl;
  import org.apache.calcite.tools.RelBuilder;
  import org.apache.calcite.util.Litmus;
  import org.apache.calcite.util.Util;
  import org.apache.calcite.util.graph.DefaultDirectedGraph;
  import org.apache.calcite.util.graph.DefaultEdge;
  import org.apache.calcite.util.graph.DirectedGraph;
  import org.apache.calcite.util.graph.TopologicalOrderIterator;
  
  import com.google.common.collect.ImmutableList;
  import com.google.common.primitives.Ints;
  
  import org.checkerframework.checker.nullness.qual.Nullable;
  import org.slf4j.Logger;
  
  import java.io.PrintWriter;
  import java.io.StringWriter;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.List;
  import java.util.Set;
  
  import static com.google.common.base.Preconditions.checkArgument;
  
  import static org.apache.calcite.util.Util.isDistinct;
  
  /**
   * CalcRelSplitter operates on a
   * {@link org.apache.calcite.rel.core.Calc} with multiple {@link RexCall}
   * sub-expressions that cannot all be implemented by a single concrete
   * {@link RelNode}.
   *
   * <p>For example, the Java and Fennel calculator do not implement an identical
   * set of operators. The Calc can be used to split a single Calc with
   * mixed Java- and Fennel-only operators into a tree of Calc object that can
   * each be individually implemented by either Java or Fennel.and splits it into
   * several Calc instances.
   *
   * <p>Currently the splitter is only capable of handling two "rel types". That
   * is, it can deal with Java vs. Fennel Calcs, but not Java vs. Fennel vs.
   * some other type of Calc.
   *
   * <p>See {@link ProjectToWindowRule}
   * for an example of how this class is used.
   */
  public abstract class CalcRelSplitter {
    //~ Static fields/initializers ---------------------------------------------
  
    private static final Logger RULE_LOGGER = RelOptPlanner.LOGGER;
  
    //~ Instance fields --------------------------------------------------------
  
    protected final RexProgram program;
    private final RelDataTypeFactory typeFactory;
  
    private final List<RelType> relTypes;
    private final RelOptCluster cluster;
    private final RelTraitSet traits;
    private final RelNode child;
    protected final RelBuilder relBuilder;
  
    //~ Constructors -----------------------------------------------------------
  
    /**
     * Constructs a CalcRelSplitter.
     *
     * @param calc     Calc to split
     * @param relTypes Array of rel types, e.g. {Java, Fennel}. Must be
     *                 distinct.
     */
    CalcRelSplitter(Calc calc, RelBuilder relBuilder, RelType[] relTypes) {
      this.relBuilder = relBuilder;
      this.program = calc.getProgram();
      this.cluster = calc.getCluster();
      this.traits = calc.getTraitSet();
      this.typeFactory = calc.getCluster().getTypeFactory();
      this.child = calc.getInput();
      this.relTypes = ImmutableList.copyOf(relTypes);
      checkArgument(isDistinct(this.relTypes));
    }
  
    //~ Methods ----------------------------------------------------------------
  
    RelNode execute() {
      // Check that program is valid. In particular, this means that every
      // expression is trivial (either an atom, or a function applied to
      // references to atoms) and every expression depends only on
      // expressions to the left.
      assert program.isValid(Litmus.THROW, null);
      final List<RexNode> exprList = program.getExprList();
      final RexNode[] exprs = exprList.toArray(new RexNode[0]);
      assert !RexUtil.containComplexExprs(exprList);
  
      // Figure out what level each expression belongs to.
      int[] exprLevels = new int[exprs.length];
  
      // The type of a level is given by
      // relTypes[levelTypeOrdinals[level]].
      int[] levelTypeOrdinals = new int[exprs.length];
  
      int levelCount = chooseLevels(exprs, -1, exprLevels, levelTypeOrdinals);
  
      // For each expression, figure out which is the highest level where it
      // is used.
      int[] exprMaxUsingLevelOrdinals =
          new HighestUsageFinder(exprs, exprLevels)
              .getMaxUsingLevelOrdinals();
  
      // If expressions are used as outputs, mark them as higher than that.
      final List<RexLocalRef> projectRefList = program.getProjectList();
      final RexLocalRef conditionRef = program.getCondition();
      for (RexLocalRef projectRef : projectRefList) {
        exprMaxUsingLevelOrdinals[projectRef.getIndex()] = levelCount;
      }
      if (conditionRef != null) {
        exprMaxUsingLevelOrdinals[conditionRef.getIndex()] = levelCount;
      }
  
      // Print out what we've got.
      if (RULE_LOGGER.isTraceEnabled()) {
        traceLevelExpressions(
            exprs,
            exprLevels,
            levelTypeOrdinals,
            levelCount);
      }
  
      // Now build the calcs.
      RelNode rel = child;
      final int inputFieldCount = program.getInputRowType().getFieldCount();
      int[] inputExprOrdinals = identityArray(inputFieldCount);
      boolean doneCondition = false;
      for (int level = 0; level < levelCount; level++) {
        final int[] projectExprOrdinals;
        final RelDataType outputRowType;
        if (level == (levelCount - 1)) {
          outputRowType = program.getOutputRowType();
          projectExprOrdinals = new int[projectRefList.size()];
          for (int i = 0; i < projectExprOrdinals.length; i++) {
            projectExprOrdinals[i] = projectRefList.get(i).getIndex();
          }
        } else {
          outputRowType = null;
  
          // Project the expressions which are computed at this level or
          // before, and will be used at later levels.
          List<Integer> projectExprOrdinalList = new ArrayList<>();
          for (int i = 0; i < exprs.length; i++) {
            RexNode expr = exprs[i];
            if (expr instanceof RexLiteral) {
              // Don't project literals. They are always created in
              // the level where they are used.
              exprLevels[i] = -1;
              continue;
            }
            if ((exprLevels[i] <= level)
                && (exprMaxUsingLevelOrdinals[i] > level)) {
              projectExprOrdinalList.add(i);
            }
          }
          projectExprOrdinals = Ints.toArray(projectExprOrdinalList);
        }
  
        final RelType relType = relTypes.get(levelTypeOrdinals[level]);
  
        // Can we do the condition this level?
        int conditionExprOrdinal = -1;
        if ((conditionRef != null) && !doneCondition) {
          conditionExprOrdinal = conditionRef.getIndex();
          if ((exprLevels[conditionExprOrdinal] > level)
              || !relType.supportsCondition()) {
            // stand down -- we're not ready to do the condition yet
            conditionExprOrdinal = -1;
          } else {
            doneCondition = true;
          }
        }
  
        RexProgram program1 =
            createProgramForLevel(
                level,
                levelCount,
                rel.getRowType(),
                exprs,
                exprLevels,
                inputExprOrdinals,
                projectExprOrdinals,
                conditionExprOrdinal,
                outputRowType);
        rel =
            relType.makeRel(cluster, traits, relBuilder, rel, program1);
  
        // Sometimes a level's program merely projects its inputs. We don't
        // want these. They cause an explosion in the search space.
        if (rel instanceof LogicalCalc
            && ((LogicalCalc) rel).getProgram().isTrivial()) {
          rel = rel.getInput(0);
        }
  
        rel = handle(rel);
  
        // The outputs of this level will be the inputs to the next level.
        inputExprOrdinals = projectExprOrdinals;
      }
  
      checkArgument(doneCondition || conditionRef == null, "unhandled condition");
      return rel;
    }
  
    /**
     * Opportunity to further refine the relational expression created for a
     * given level. The default implementation returns the relational expression
     * unchanged.
     */
    protected RelNode handle(RelNode rel) {
      return rel;
    }
  
    /**
     * Figures out which expressions to calculate at which level.
     *
     * @param exprs             Array of expressions
     * @param conditionOrdinal  Ordinal of the condition expression, or -1 if no
     *                          condition
     * @param exprLevels        Level ordinal for each expression (output)
     * @param levelTypeOrdinals The type of each level (output)
     * @return Number of levels required
     */
    private int chooseLevels(
        final RexNode[] exprs,
        int conditionOrdinal,
        int[] exprLevels,
        int[] levelTypeOrdinals) {
      final int inputFieldCount = program.getInputRowType().getFieldCount();
  
      int levelCount = 0;
      final MaxInputFinder maxInputFinder = new MaxInputFinder(exprLevels);
      boolean[] relTypesPossibleForTopLevel = new boolean[relTypes.size()];
      Arrays.fill(relTypesPossibleForTopLevel, true);
  
      // Compute the order in which to visit expressions.
      final List<Set<Integer>> cohorts = getCohorts();
      final List<Integer> permutation =
          computeTopologicalOrdering(exprs, cohorts);
  
      for (int i : permutation) {
        RexNode expr = exprs[i];
        final boolean condition = i == conditionOrdinal;
  
        if (i < inputFieldCount) {
          assert expr instanceof RexInputRef;
          exprLevels[i] = -1;
          continue;
        }
  
        // Deduce the minimum level of the expression. An expression must
        // be at a level greater than or equal to all of its inputs.
        int level = maxInputFinder.maxInputFor(expr);
  
        // If the expression is in a cohort, it can occur no lower than the
        // levels of other expressions in the same cohort.
        Set<Integer> cohort = findCohort(cohorts, i);
        if (cohort != null) {
          for (Integer exprOrdinal : cohort) {
            if (exprOrdinal == i) {
              // Already did this member of the cohort. It's a waste
              // of effort to repeat.
              continue;
            }
            final RexNode cohortExpr = exprs[exprOrdinal];
            int cohortLevel = maxInputFinder.maxInputFor(cohortExpr);
            if (cohortLevel > level) {
              level = cohortLevel;
            }
          }
        }
  
        // Try to implement this expression at this level.
        // If that is not possible, try to implement it at higher levels.
      levelLoop:
        for (;; ++level) {
          if (level >= levelCount) {
            // This is a new level. We can use any type we like.
            for (int relTypeOrdinal = 0;
                relTypeOrdinal < relTypes.size();
                relTypeOrdinal++) {
              if (!relTypesPossibleForTopLevel[relTypeOrdinal]) {
                continue;
              }
              if (relTypes.get(relTypeOrdinal).canImplement(expr, condition)) {
                // Success. We have found a type where we can
                // implement this expression.
                exprLevels[i] = level;
                levelTypeOrdinals[level] = relTypeOrdinal;
                assert (level == 0)
                    || (levelTypeOrdinals[level - 1]
                    != levelTypeOrdinals[level])
                    : "successive levels of same type";
  
                // Figure out which of the other reltypes are
                // still possible for this level.
                // Previous reltypes are not possible.
                for (int j = 0; j < relTypeOrdinal; ++j) {
                  relTypesPossibleForTopLevel[j] = false;
                }
  
                // Successive reltypes may be possible.
                for (int j = relTypeOrdinal + 1;
                    j < relTypes.size();
                    ++j) {
                  if (relTypesPossibleForTopLevel[j]) {
                    relTypesPossibleForTopLevel[j] =
                        relTypes.get(j).canImplement(expr, condition);
                  }
                }
  
                // Move to next level.
                levelTypeOrdinals[levelCount] =
                    firstSet(relTypesPossibleForTopLevel);
                ++levelCount;
                Arrays.fill(relTypesPossibleForTopLevel, true);
                break levelLoop;
              }
            }
  
            // None of the reltypes still active for this level could
            // implement expr. But maybe we could succeed with a new
            // level, with all options open?
            if (count(relTypesPossibleForTopLevel) >= relTypes.size()) {
              // Cannot implement for any type.
              throw new AssertionError("cannot implement " + expr);
            }
            levelTypeOrdinals[levelCount] =
                firstSet(relTypesPossibleForTopLevel);
            ++levelCount;
            Arrays.fill(relTypesPossibleForTopLevel, true);
          } else {
            final int levelTypeOrdinal = levelTypeOrdinals[level];
            if (!relTypes.get(levelTypeOrdinal).canImplement(expr, condition)) {
              // Cannot implement this expression in this type;
              // continue to next level.
              continue;
            }
            exprLevels[i] = level;
            break;
          }
        }
      }
      if (levelCount > 0) {
        // The latest level should be CalcRelType otherwise literals cannot be
        // implemented.
        final String name = relTypes.get(0).name;
        checkArgument(name.equals("CalcRelType"),
            "The first RelType should be CalcRelType for proper RexLiteral"
                + " implementation at the last level, got %s", name);
        if (levelTypeOrdinals[levelCount - 1] != 0) {
          levelCount++;
        }
      }
      return levelCount;
    }
  
    /**
     * Computes the order in which to visit expressions, so that we decide the
     * level of an expression only after the levels of lower expressions have
     * been decided.
     *
     * <p>First, we need to ensure that an expression is visited after all of
     * its inputs.
     *
     * <p>Further, if the expression is a member of a cohort, we need to visit
     * it after the inputs of all other expressions in that cohort. With this
     * condition, expressions in the same cohort will very likely end up in the
     * same level.
     *
     * <p>Note that if there are no cohorts, the expressions from the
     * {@link RexProgram} are already in a suitable order. We perform the
     * topological sort just to ensure that the code path is well-trodden.
     *
     * @param exprs   Expressions
     * @param cohorts List of cohorts, each of which is a set of expr ordinals
     * @return Expression ordinals in topological order
     */
    private static List<Integer> computeTopologicalOrdering(
        RexNode[] exprs,
        List<Set<Integer>> cohorts) {
      final DirectedGraph<Integer, DefaultEdge> graph =
          DefaultDirectedGraph.create();
      for (int i = 0; i < exprs.length; i++) {
        graph.addVertex(i);
      }
      for (int i = 0; i < exprs.length; i++) {
        final RexNode expr = exprs[i];
        final Set<Integer> cohort = findCohort(cohorts, i);
        final Set<Integer> targets;
        if (cohort == null) {
          targets = Collections.singleton(i);
        } else {
          targets = cohort;
        }
        expr.accept(
            new RexVisitorImpl<Void>(true) {
              @Override public Void visitLocalRef(RexLocalRef localRef) {
                for (Integer target : targets) {
                  graph.addEdge(localRef.getIndex(), target);
                }
                return null;
              }
            });
      }
      TopologicalOrderIterator<Integer, DefaultEdge> iter =
          new TopologicalOrderIterator<>(graph);
      final List<Integer> permutation = new ArrayList<>();
      while (iter.hasNext()) {
        permutation.add(iter.next());
      }
      return permutation;
    }
  
    /**
     * Finds the cohort that contains the given integer, or returns null.
     *
     * @param cohorts List of cohorts, each a set of integers
     * @param ordinal Integer to search for
     * @return Cohort that contains the integer, or null if not found
     */
    private static @Nullable Set<Integer> findCohort(
        List<Set<Integer>> cohorts,
        int ordinal) {
      for (Set<Integer> cohort : cohorts) {
        if (cohort.contains(ordinal)) {
          return cohort;
        }
      }
      return null;
    }
  
    private static int[] identityArray(int length) {
      final int[] ints = new int[length];
      for (int i = 0; i < ints.length; i++) {
        ints[i] = i;
      }
      return ints;
    }
  
    /**
     * Creates a program containing the expressions for a given level.
     *
     * <p>The expression list of the program will consist of all entries in the
     * expression list <code>allExprs[i]</code> for which the corresponding
     * level ordinal <code>exprLevels[i]</code> is equal to <code>level</code>.
     * Expressions are mapped according to <code>inputExprOrdinals</code>.
     *
     * @param level                Level ordinal
     * @param levelCount           Number of levels
     * @param inputRowType         Input row type
     * @param allExprs             Array of all expressions
     * @param exprLevels           Array of the level ordinal of each expression
     * @param inputExprOrdinals    Ordinals in the expression list of input
     *                             expressions. Input expression <code>i</code>
     *                             will be found at position
     *                             <code>inputExprOrdinals[i]</code>.
     * @param projectExprOrdinals  Ordinals of the expressions to be output this
     *                             level.
     * @param conditionExprOrdinal Ordinal of the expression to form the
     *                             condition for this level, or -1 if there is no
     *                             condition.
     * @param outputRowType        Output row type
     * @return Relational expression
     */
    private RexProgram createProgramForLevel(
        int level,
        int levelCount,
        RelDataType inputRowType,
        RexNode[] allExprs,
        int[] exprLevels,
        int[] inputExprOrdinals,
        final int[] projectExprOrdinals,
        int conditionExprOrdinal,
        @Nullable RelDataType outputRowType) {
      // Build a list of expressions to form the calc.
      List<RexNode> exprs = new ArrayList<>();
  
      // exprInverseOrdinals describes where an expression in allExprs comes
      // from -- from an input, from a calculated expression, or -1 if not
      // available at this level.
      int[] exprInverseOrdinals = new int[allExprs.length];
      Arrays.fill(exprInverseOrdinals, -1);
      int j = 0;
  
      // First populate the inputs. They were computed at some previous level
      // and are used here.
      for (int i = 0; i < inputExprOrdinals.length; i++) {
        final int inputExprOrdinal = inputExprOrdinals[i];
        exprs.add(
            new RexInputRef(
                i,
                allExprs[inputExprOrdinal].getType()));
        exprInverseOrdinals[inputExprOrdinal] = j;
        ++j;
      }
  
      // Next populate the computed expressions.
      final RexShuttle shuttle =
          new InputToCommonExprConverter(
              exprInverseOrdinals,
              exprLevels,
              level,
              inputExprOrdinals,
              allExprs);
      for (int i = 0; i < allExprs.length; i++) {
        if (exprLevels[i] == level
            || exprLevels[i] == -1
            && level == (levelCount - 1)
            && allExprs[i] instanceof RexLiteral) {
          RexNode expr = allExprs[i];
          final RexNode translatedExpr = expr.accept(shuttle);
          exprs.add(translatedExpr);
          assert exprInverseOrdinals[i] == -1;
          exprInverseOrdinals[i] = j;
          ++j;
        }
      }
  
      // Form the projection and condition list. Project and condition
      // ordinals are offsets into allExprs, so we need to map them into
      // exprs.
      final List<RexLocalRef> projectRefs =
          new ArrayList<>(projectExprOrdinals.length);
      final List<String> fieldNames =
          new ArrayList<>(projectExprOrdinals.length);
      for (int i = 0; i < projectExprOrdinals.length; i++) {
        final int projectExprOrdinal = projectExprOrdinals[i];
        final int index = exprInverseOrdinals[projectExprOrdinal];
        assert index >= 0;
        RexNode expr = allExprs[projectExprOrdinal];
        projectRefs.add(new RexLocalRef(index, expr.getType()));
  
        // Inherit meaningful field name if possible.
        fieldNames.add(deriveFieldName(expr, i));
      }
      RexLocalRef conditionRef;
      if (conditionExprOrdinal >= 0) {
        final int index = exprInverseOrdinals[conditionExprOrdinal];
        conditionRef =
            new RexLocalRef(
                index,
                allExprs[conditionExprOrdinal].getType());
      } else {
        conditionRef = null;
      }
      if (outputRowType == null) {
        outputRowType =
            RexUtil.createStructType(typeFactory, projectRefs, fieldNames, null);
      }
      // Program is NOT normalized here (e.g. can contain literals in
      // call operands), since literals should be inlined.
      return new RexProgram(inputRowType, exprs, projectRefs, conditionRef,
          outputRowType);
    }
  
    private String deriveFieldName(RexNode expr, int ordinal) {
      if (expr instanceof RexInputRef) {
        int inputIndex = ((RexInputRef) expr).getIndex();
        String fieldName =
            child.getRowType().getFieldList().get(inputIndex).getName();
        // Don't inherit field names like '$3' from child: that's
        // confusing.
        if (!fieldName.startsWith("$") || fieldName.startsWith("$EXPR")) {
          return fieldName;
        }
      }
      return "$" + ordinal;
    }
  
    /**
     * Traces the given array of level expression lists at the finer level.
     *
     * @param exprs             Array expressions
     * @param exprLevels        For each expression, the ordinal of its level
     * @param levelTypeOrdinals For each level, the ordinal of its type in
     *                          the {@link #relTypes} array
     * @param levelCount        The number of levels
     */
    private void traceLevelExpressions(
        RexNode[] exprs,
        int[] exprLevels,
        int[] levelTypeOrdinals,
        int levelCount) {
      StringWriter traceMsg = new StringWriter();
      PrintWriter traceWriter = new PrintWriter(traceMsg);
      traceWriter.println("FarragoAutoCalcRule result expressions for: ");
      traceWriter.println(program);
  
      for (int level = 0; level < levelCount; level++) {
        traceWriter.println("Rel Level " + level
            + ", type " + relTypes.get(levelTypeOrdinals[level]));
  
        for (int i = 0; i < exprs.length; i++) {
          RexNode expr = exprs[i];
          assert (exprLevels[i] >= -1) && (exprLevels[i] < levelCount)
              : "expression's level is out of range";
          if (exprLevels[i] == level) {
            traceWriter.println("\t" + i + ": " + expr);
          }
        }
        traceWriter.println();
      }
      String msg = traceMsg.toString();
      RULE_LOGGER.trace(msg);
    }
  
    /**
     * Returns the number of bits set in an array.
     */
    private static int count(boolean[] booleans) {
      int count = 0;
      for (boolean b : booleans) {
        if (b) {
          ++count;
        }
      }
      return count;
    }
  
    /**
     * Returns the index of the first set bit in an array.
     */
    private static int firstSet(boolean[] booleans) {
      for (int i = 0; i < booleans.length; i++) {
        if (booleans[i]) {
          return i;
        }
      }
      return -1;
    }
  
    /**
     * Searches for a value in a map, and returns the position where it was
     * found, or -1.
     *
     * @param value Value to search for
     * @param map   Map to search in
     * @return Ordinal of value in map, or -1 if not found
     */
    private static int indexOf(int value, int[] map) {
      for (int i = 0; i < map.length; i++) {
        if (value == map[i]) {
          return i;
        }
      }
      return -1;
    }
  
    /**
     * Returns whether a relational expression can be implemented solely in a
     * given {@link RelType}.
     *
     * @param rel         Calculation relational expression
     * @param relTypeName Name of a {@link RelType}
     * @return Whether relational expression can be implemented
     */
    protected boolean canImplement(LogicalCalc rel, String relTypeName) {
      for (RelType relType : relTypes) {
        if (relType.name.equals(relTypeName)) {
          return relType.canImplement(rel.getProgram());
        }
      }
      throw new AssertionError("unknown type " + relTypeName);
    }
  
    /**
     * Returns a list of sets of expressions that should be on the same level.
     *
     * <p>For example, if this method returns { {3, 5}, {4, 7} }, it means that
     * expressions 3 and 5, should be on the same level, and expressions 4 and 7
     * should be on the same level. The two cohorts do not need to be on the
     * same level.
     *
     * <p>The list is best effort. If it is not possible to arrange that the
     * expressions in a cohort are on the same level, the {@link #execute()}
     * method will still succeed.
     *
     * <p>The default implementation of this method returns the empty list;
     * expressions will be put on the most suitable level. This is generally
     * the lowest possible level, except for literals, which are placed at the
     * level where they are used.
     *
     * @return List of cohorts, that is sets of expressions, that the splitting
     * algorithm should attempt to place on the same level
     */
    protected List<Set<Integer>> getCohorts() {
      return Collections.emptyList();
    }
  
    //~ Inner Classes ----------------------------------------------------------
  
    /** Type of relational expression. Determines which kinds of
     * expressions it can handle. */
    public abstract static class RelType {
      private final String name;
  
      protected RelType(String name) {
        this.name = name;
      }
  
      @Override public String toString() {
        return name;
      }
  
      protected abstract boolean canImplement(RexFieldAccess field);
  
      protected abstract boolean canImplement(RexDynamicParam param);
  
      protected abstract boolean canImplement(RexLiteral literal);
  
      protected abstract boolean canImplement(RexCall call);
  
      protected boolean supportsCondition() {
        return true;
      }
  
      protected RelNode makeRel(RelOptCluster cluster,
          RelTraitSet traitSet, RelBuilder relBuilder, RelNode input,
          RexProgram program) {
        return LogicalCalc.create(input, program);
      }
  
      /**
       * Returns whether this <code>RelType</code> can implement a given
       * expression.
       *
       * @param expr      Expression
       * @param condition Whether expression is a condition
       * @return Whether this <code>RelType</code> can implement a given
       * expression.
       */
      public boolean canImplement(RexNode expr, boolean condition) {
        if (condition && !supportsCondition()) {
          return false;
        }
        try {
          expr.accept(new ImplementTester(this));
          return true;
        } catch (CannotImplement e) {
          Util.swallow(e, null);
          return false;
        }
      }
  
      /**
       * Returns whether this tester's <code>RelType</code> can implement a
       * given program.
       *
       * @param program Program
       * @return Whether this tester's <code>RelType</code> can implement a
       * given program.
       */
      public boolean canImplement(RexProgram program) {
        if ((program.getCondition() != null)
            && !canImplement(program.getCondition(), true)) {
          return false;
        }
        for (RexNode expr : program.getExprList()) {
          if (!canImplement(expr, false)) {
            return false;
          }
        }
        return true;
      }
    }
  
    /**
     * Visitor which returns whether an expression can be implemented in a given
     * type of relational expression.
     */
    private static class ImplementTester extends RexVisitorImpl<Void> {
      private final RelType relType;
  
      ImplementTester(RelType relType) {
        super(false);
        this.relType = relType;
      }
  
      @Override public Void visitCall(RexCall call) {
        if (!relType.canImplement(call)) {
          throw CannotImplement.INSTANCE;
        }
        return null;
      }
  
      @Override public Void visitDynamicParam(RexDynamicParam dynamicParam) {
        if (!relType.canImplement(dynamicParam)) {
          throw CannotImplement.INSTANCE;
        }
        return null;
      }
  
      @Override public Void visitFieldAccess(RexFieldAccess fieldAccess) {
        if (!relType.canImplement(fieldAccess)) {
          throw CannotImplement.INSTANCE;
        }
        return null;
      }
  
      @Override public Void visitLiteral(RexLiteral literal) {
        if (!relType.canImplement(literal)) {
          throw CannotImplement.INSTANCE;
        }
        return null;
      }
    }
  
    /**
     * Control exception for {@link ImplementTester}.
     */
    private static class CannotImplement extends RuntimeException {
      @SuppressWarnings("ThrowableInstanceNeverThrown")
      static final CannotImplement INSTANCE = new CannotImplement();
    }
  
    /**
     * Shuttle which converts every reference to an input field in an expression
     * to a reference to a common sub-expression.
     */
    private static class InputToCommonExprConverter extends RexShuttle {
      private final int[] exprInverseOrdinals;
      private final int[] exprLevels;
      private final int level;
      private final int[] inputExprOrdinals;
      private final RexNode[] allExprs;
  
      InputToCommonExprConverter(
          int[] exprInverseOrdinals,
          int[] exprLevels,
          int level,
          int[] inputExprOrdinals,
          RexNode[] allExprs) {
        this.exprInverseOrdinals = exprInverseOrdinals;
        this.exprLevels = exprLevels;
        this.level = level;
        this.inputExprOrdinals = inputExprOrdinals;
        this.allExprs = allExprs;
      }
  
      @Override public RexNode visitInputRef(RexInputRef input) {
        final int index = exprInverseOrdinals[input.getIndex()];
        assert index >= 0;
        return new RexLocalRef(
            index,
            input.getType());
      }
  
      @Override public RexNode visitLocalRef(RexLocalRef local) {
        // A reference to a local variable becomes a reference to an input
        // if the local was computed at a previous level.
        final int localIndex = local.getIndex();
        final int exprLevel = exprLevels[localIndex];
        if (exprLevel < level) {
          if (allExprs[localIndex] instanceof RexLiteral) {
            // Expression is to be inlined. Use the original expression.
            return allExprs[localIndex];
          }
          int inputIndex = indexOf(localIndex, inputExprOrdinals);
          assert inputIndex >= 0;
          return new RexLocalRef(
              inputIndex,
              local.getType());
        } else {
          // It's a reference to what was a local expression at the
          // previous level, and was then projected.
          final int exprIndex = exprInverseOrdinals[localIndex];
          return new RexLocalRef(
              exprIndex,
              local.getType());
        }
      }
    }
  
    /**
     * Finds the highest level used by any of the inputs of a given expression.
     */
    private static class MaxInputFinder extends RexVisitorImpl<Void> {
      int level;
      private final int[] exprLevels;
  
      MaxInputFinder(int[] exprLevels) {
        super(true);
        this.exprLevels = exprLevels;
      }
  
      @Override public Void visitLocalRef(RexLocalRef localRef) {
        int inputLevel = exprLevels[localRef.getIndex()];
        level = Math.max(level, inputLevel);
        return null;
      }
  
      /**
       * Returns the highest level of any of the inputs of an expression.
       */
      public int maxInputFor(RexNode expr) {
        level = 0;
        expr.accept(this);
        return level;
      }
    }
  
    /**
     * Builds an array of the highest level which contains an expression which
     * uses each expression as an input.
     */
    private static class HighestUsageFinder extends RexVisitorImpl<Void> {
      private final int[] maxUsingLevelOrdinals;
      private int currentLevel;
  
      HighestUsageFinder(RexNode[] exprs, int[] exprLevels) {
        super(true);
        this.maxUsingLevelOrdinals = new int[exprs.length];
        Arrays.fill(maxUsingLevelOrdinals, -1);
        for (int i = 0; i < exprs.length; i++) {
          if (exprs[i] instanceof RexLiteral) {
            // Literals are always used directly. It never makes sense
            // to compute them at a lower level and project them to
            // where they are used.
            maxUsingLevelOrdinals[i] = -1;
            continue;
          }
          currentLevel = exprLevels[i];
          @SuppressWarnings("argument.type.incompatible")
          final Void unused = exprs[i].accept(this);
        }
      }
  
      public int[] getMaxUsingLevelOrdinals() {
        return maxUsingLevelOrdinals;
      }
  
      @Override public Void visitLocalRef(RexLocalRef ref) {
        final int index = ref.getIndex();
        maxUsingLevelOrdinals[index] =
            Math.max(maxUsingLevelOrdinals[index], currentLevel);
        return null;
      }
    }
  }
  