core/src/main/java/org/apache/druid/math/expr/Parser.java

/*
 * 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.druid.math.expr;


import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Supplier;
import com.google.common.base.Suppliers;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Sets;
import org.antlr.v4.runtime.ANTLRInputStream;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;
import org.antlr.v4.runtime.tree.ParseTreeWalker;
import org.apache.druid.java.util.common.RE;
import org.apache.druid.java.util.common.StringUtils;
import org.apache.druid.java.util.common.logger.Logger;
import org.apache.druid.math.expr.antlr.ExprLexer;
import org.apache.druid.math.expr.antlr.ExprParser;

import javax.annotation.Nullable;
import java.lang.reflect.Modifier;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.UnaryOperator;
import java.util.stream.Collectors;

public class Parser
{
  private static final Logger log = new Logger(Parser.class);
  private static final Map<String, Function> FUNCTIONS;
  private static final Map<String, ApplyFunction> APPLY_FUNCTIONS;

  static {
    Map<String, Function> functionMap = new HashMap<>();
    for (Class clazz : Function.class.getClasses()) {
      if (!Modifier.isAbstract(clazz.getModifiers()) && Function.class.isAssignableFrom(clazz)) {
        try {
          Function function = (Function) clazz.newInstance();
          functionMap.put(StringUtils.toLowerCase(function.name()), function);
        }
        catch (Exception e) {
          log.error(e, "failed to instantiate %s.. ignoring", clazz.getName());
        }
      }
    }
    FUNCTIONS = ImmutableMap.copyOf(functionMap);

    Map<String, ApplyFunction> applyFunctionMap = new HashMap<>();
    for (Class clazz : ApplyFunction.class.getClasses()) {
      if (!Modifier.isAbstract(clazz.getModifiers()) && ApplyFunction.class.isAssignableFrom(clazz)) {
        try {
          ApplyFunction function = (ApplyFunction) clazz.newInstance();
          applyFunctionMap.put(StringUtils.toLowerCase(function.name()), function);
        }
        catch (Exception e) {
          log.error(e, "failed to instantiate %s.. ignoring", clazz.getName());
        }
      }
    }
    APPLY_FUNCTIONS = ImmutableMap.copyOf(applyFunctionMap);
  }

  /**
   * Get {@link Function} by {@link Function#name()}
   */
  public static Function getFunction(String name)
  {
    return FUNCTIONS.get(StringUtils.toLowerCase(name));
  }

  /**
   * Get {@link ApplyFunction} by {@link ApplyFunction#name()}
   */
  public static ApplyFunction getApplyFunction(String name)
  {
    return APPLY_FUNCTIONS.get(StringUtils.toLowerCase(name));
  }

  /**
   * Create a memoized lazy supplier to parse a string into a flattened {@link Expr}. There is some overhead to this,
   * and these objects are all immutable, so this assists in the goal of re-using instead of re-creating whenever
   * possible.
   *
   * Lazy form of {@link #parse(String, ExprMacroTable)}
   *
   * @param in expression to parse
   * @param macroTable additional extensions to expression language
   */
  public static Supplier<Expr> lazyParse(@Nullable String in, ExprMacroTable macroTable)
  {
    return Suppliers.memoize(() -> in == null ? null : Parser.parse(in, macroTable));
  }

  /**
   * Parse a string into a flattened {@link Expr}. There is some overhead to this, and these objects are all immutable,
   * so re-use instead of re-creating whenever possible.
   *
   * @param in expression to parse
   * @param macroTable additional extensions to expression language
   */
  public static Expr parse(String in, ExprMacroTable macroTable)
  {
    return parse(in, macroTable, true);
  }


  @VisibleForTesting
  public static Expr parse(String in, ExprMacroTable macroTable, boolean withFlatten)
  {
    ExprLexer lexer = new ExprLexer(new ANTLRInputStream(in));
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    ExprParser parser = new ExprParser(tokens);
    parser.setBuildParseTree(true);
    ParseTree parseTree = parser.expr();
    ParseTreeWalker walker = new ParseTreeWalker();
    ExprListenerImpl listener = new ExprListenerImpl(parseTree, macroTable);
    walker.walk(listener, parseTree);
    Expr parsed = listener.getAST();
    if (parsed == null) {
      throw new RE("Failed to parse expression: %s", in);
    }
    return withFlatten ? flatten(parsed) : parsed;
  }

  /**
   * Flatten an {@link Expr}, evaluating expressions on constants where possible to simplify the {@link Expr}.
   */
  public static Expr flatten(Expr expr)
  {
    return expr.visit(childExpr -> {
      if (childExpr instanceof BinaryOpExprBase) {
        BinaryOpExprBase binary = (BinaryOpExprBase) childExpr;
        if (Evals.isAllConstants(binary.left, binary.right)) {
          return childExpr.eval(null).toExpr();
        }
      } else if (childExpr instanceof UnaryExpr) {
        UnaryExpr unary = (UnaryExpr) childExpr;

        if (unary.expr instanceof ConstantExpr) {
          return childExpr.eval(null).toExpr();
        }
      } else if (childExpr instanceof FunctionExpr) {
        FunctionExpr functionExpr = (FunctionExpr) childExpr;
        List<Expr> args = functionExpr.args;
        if (Evals.isAllConstants(args)) {
          return childExpr.eval(null).toExpr();
        }
      } else if (childExpr instanceof ApplyFunctionExpr) {
        ApplyFunctionExpr applyFunctionExpr = (ApplyFunctionExpr) childExpr;
        List<Expr> args = applyFunctionExpr.argsExpr;
        if (Evals.isAllConstants(args)) {
          if (applyFunctionExpr.analyzeInputs().getFreeVariables().size() == 0) {
            return childExpr.eval(null).toExpr();
          }
        }
      }
      return childExpr;
    });
  }

  /**
   * Applies a transformation to an {@link Expr} given a list of known (or uknown) multi-value input columns that are
   * used in a scalar manner, walking the {@link Expr} tree and lifting array variables into the {@link LambdaExpr} of
   * {@link ApplyFunctionExpr} and transforming the arguments of {@link FunctionExpr} as necessary.
   *
   * This function applies a transformation for "map" style uses, such as column selectors, where the supplied
   * expression will be transformed to return an array of results instead of the scalar result (or appropriately
   * rewritten into existing apply expressions to produce correct results when referenced from a scalar context).
   *
   * This function and {@link #foldUnappliedBindings(Expr, Expr.BindingAnalysis, List, String)} exist to handle
   * "multi-valued" string dimensions, which exist in a superposition of both single and multi-valued during realtime
   * ingestion, until they are written to a segment and become locked into either single or multi-valued. This also
   * means that multi-valued-ness can vary for a column from segment to segment, so this family of transformation
   * functions exist so that multi-valued strings can be expressed in either and array or scalar context, which is
   * important because the writer of the query might not actually know if the column is definitively always single or
   * multi-valued (and it might in fact not be).
   *
   * @see #foldUnappliedBindings(Expr, Expr.BindingAnalysis, List, String)
   */
  public static Expr applyUnappliedBindings(
      Expr expr,
      Expr.BindingAnalysis bindingAnalysis,
      List<String> bindingsToApply
  )
  {
    if (bindingsToApply.isEmpty()) {
      // nothing to do, expression is fine as is
      return expr;
    }
    // filter the list of bindings to those which are used in this expression
    List<String> unappliedBindingsInExpression =
        bindingsToApply.stream()
                       .filter(x -> bindingAnalysis.getRequiredBindings().contains(x))
                       .collect(Collectors.toList());

    // any unapplied bindings that are inside a lambda expression need that lambda expression to be rewritten
    Expr newExpr = rewriteUnappliedSubExpressions(
        expr,
        unappliedBindingsInExpression,
        (arg) -> applyUnappliedBindings(arg, bindingAnalysis, bindingsToApply)
    );

    Expr.BindingAnalysis newExprBindings = newExpr.analyzeInputs();
    final Set<String> expectedArrays = newExprBindings.getArrayVariables();

    List<String> remainingUnappliedBindings =
        unappliedBindingsInExpression.stream().filter(x -> !expectedArrays.contains(x)).collect(Collectors.toList());

    // if lifting the lambdas got rid of all missing bindings, return the transformed expression
    if (remainingUnappliedBindings.isEmpty()) {
      return newExpr;
    }

    return applyUnapplied(newExpr, remainingUnappliedBindings);
  }


  /**
   * Applies a transformation to an {@link Expr} given a list of known (or uknown) multi-value input columns that are
   * used in a scalar manner, walking the {@link Expr} tree and lifting array variables into the {@link LambdaExpr} of
   * {@link ApplyFunctionExpr} and transforming the arguments of {@link FunctionExpr} as necessary.
   *
   * This function applies a transformation for "fold" style uses, such as aggregators, where the supplied
   * expression will be transformed to accumulate the result of applying the expression to each value of the unapplied
   * input (or appropriately rewritten into existing apply expressions to produce correct results when referenced from
   * a scalar context). This rewriting assumes that there exists some accumulator variable, which is re-used as the
   * accumulator for this fold rewrite, so that evaluating each expression can be accumulated into the larger external
   * fold operation that an aggregator might be performing.
   *
   * This function and {@link #applyUnappliedBindings(Expr, Expr.BindingAnalysis, List)} exist to handle
   * "multi-valued" string dimensions, which exist in a superposition of both single and multi-valued during realtime
   * ingestion, until they are written to a segment and become locked into either single or multi-valued. This also
   * means that multi-valued-ness can vary for a column from segment to segment, so this family of transformation
   * functions exist so that multi-valued strings can be expressed in either and array or scalar context, which is
   * important because the writer of the query might not actually know if the column is definitively always single or
   * multi-valued (and it might in fact not be).
   *
   * @see #applyUnappliedBindings(Expr, Expr.BindingAnalysis, List)
   */
  public static Expr foldUnappliedBindings(Expr expr, Expr.BindingAnalysis bindingAnalysis, List<String> bindingsToApply, String accumulatorId)
  {
    if (bindingsToApply.isEmpty()) {
      // nothing to do, expression is fine as is
      return expr;
    }

    // filter the list of bindings to those which are used in this expression
    List<String> unappliedBindingsInExpression =
        bindingsToApply.stream()
                       .filter(x -> bindingAnalysis.getRequiredBindings().contains(x))
                       .collect(Collectors.toList());

    Expr newExpr = rewriteUnappliedSubExpressions(
        expr,
        unappliedBindingsInExpression,
        (arg) -> foldUnappliedBindings(arg, bindingAnalysis, bindingsToApply, accumulatorId)
    );

    Expr.BindingAnalysis newExprBindings = newExpr.analyzeInputs();
    final Set<String> expectedArrays = newExprBindings.getArrayVariables();

    List<String> remainingUnappliedBindings =
        unappliedBindingsInExpression.stream().filter(x -> !expectedArrays.contains(x)).collect(Collectors.toList());

    // if lifting the lambdas got rid of all missing bindings, return the transformed expression
    if (remainingUnappliedBindings.isEmpty()) {
      return newExpr;
    }

    return foldUnapplied(newExpr, remainingUnappliedBindings, accumulatorId);
  }

  /**
   * Any unapplied bindings that are inside a lambda expression need that lambda expression to be rewritten to "lift"
   * the identifier variables and transform the function.
   *
   * For example:
   * if "y" is unapplied:
   *  map((x) -> x + y, x) => cartesian_map((x,y) -> x + y, x, y)
   *
   * @see #liftApplyLambda(ApplyFunctionExpr, List)
   *
   * Array functions on expressions using unapplied identifiers might also need transformed, so we recursively call the
   * unapplied binding transformation function (supplied to this method) on that expression to ensure proper
   * transformation and rewrite of these array expressions.
   *
   * For example:
   * if "y" is unapplied:
   *  array_length(filter((x) -> x > y, x))
   */
  private static Expr rewriteUnappliedSubExpressions(
      Expr expr,
      List<String> unappliedBindingsInExpression,
      UnaryOperator<Expr> applyUnappliedFn
  )
  {
    // any unapplied bindings that are inside a lambda expression need that lambda expression to be rewritten
    return expr.visit(
        childExpr -> {
          if (childExpr instanceof ApplyFunctionExpr) {
            // try to lift unapplied arguments into the apply function lambda
            return liftApplyLambda((ApplyFunctionExpr) childExpr, unappliedBindingsInExpression);
          } else if (childExpr instanceof FunctionExpr) {
            // check array function arguments for unapplied identifiers to transform if necessary
            FunctionExpr fnExpr = (FunctionExpr) childExpr;
            Set<Expr> arrayInputs = fnExpr.function.getArrayInputs(fnExpr.args);
            List<Expr> newArgs = new ArrayList<>();
            for (Expr arg : fnExpr.args) {
              if (arg.getIdentifierIfIdentifier() == null && arrayInputs.contains(arg)) {
                Expr newArg = applyUnappliedFn.apply(arg);
                newArgs.add(newArg);
              } else {
                newArgs.add(arg);
              }
            }

            FunctionExpr newFnExpr = new FunctionExpr(fnExpr.function, fnExpr.function.name(), newArgs);
            return newFnExpr;
          }
          return childExpr;
        }
    );
  }

  /**
   * translate an {@link Expr} into an {@link ApplyFunctionExpr} for {@link ApplyFunction.MapFunction} or
   * {@link ApplyFunction.CartesianMapFunction} if there are multiple unbound arguments to be applied.
   *
   * For example:
   * if "x" is unapplied:
   *  x + y => map((x) -> x + y, x)
   * if "x" and "y" are unapplied:
   *  x + y => cartesian_map((x, y) -> x + y, x, y)
   */
  private static Expr applyUnapplied(Expr expr, List<String> unappliedBindings)
  {
    // filter to get list of IdentifierExpr that are backed by the unapplied bindings
    final List<IdentifierExpr> args = expr.analyzeInputs()
                                          .getFreeVariables()
                                          .stream()
                                          .filter(x -> unappliedBindings.contains(x.getBinding()))
                                          .collect(Collectors.toList());

    final List<IdentifierExpr> lambdaArgs = new ArrayList<>();

    // construct lambda args from list of args to apply. Identifiers in a lambda body have artificial 'binding' values
    // that is the same as the 'identifier', because the bindings are supplied by the wrapping apply function
    // replacements are done by binding rather than identifier because repeats of the same input should not result
    // in a cartesian product
    final Map<String, IdentifierExpr> toReplace = new HashMap<>();
    for (IdentifierExpr applyFnArg : args) {
      if (!toReplace.containsKey(applyFnArg.getBinding())) {
        IdentifierExpr lambdaRewrite = new IdentifierExpr(applyFnArg.getBinding());
        lambdaArgs.add(lambdaRewrite);
        toReplace.put(applyFnArg.getBinding(), lambdaRewrite);
      }
    }

    // rewrite identifiers in the expression which will become the lambda body, so they match the lambda identifiers we
    // are constructing
    Expr newExpr = expr.visit(childExpr -> {
      if (childExpr instanceof IdentifierExpr) {
        if (toReplace.containsKey(((IdentifierExpr) childExpr).getBinding())) {
          return toReplace.get(((IdentifierExpr) childExpr).getBinding());
        }
      }
      return childExpr;
    });


    // wrap an expression in either map or cartesian_map to apply any unapplied identifiers
    final LambdaExpr lambdaExpr = new LambdaExpr(lambdaArgs, newExpr);
    final ApplyFunction fn;
    if (lambdaArgs.size() == 1) {
      fn = new ApplyFunction.MapFunction();
    } else {
      fn = new ApplyFunction.CartesianMapFunction();
    }

    final Expr magic = new ApplyFunctionExpr(fn, fn.name(), lambdaExpr, ImmutableList.copyOf(lambdaArgs));
    return magic;
  }

  /**
   * translate an {@link Expr} into an {@link ApplyFunctionExpr} for {@link ApplyFunction.FoldFunction} or
   * {@link ApplyFunction.CartesianFoldFunction} if there are multiple unbound arguments to be applied.
   *
   * This assumes a known {@link IdentifierExpr} is an "accumulator", which is re-used as the accumulator variable and
   * input for the translated fold.
   *
   * For example given an accumulator "__acc":
   *  if "x" is unapplied:
   *    __acc + x => fold((x, __acc) -> x + __acc, x, __acc)
   *  if "x" and "y" are unapplied:
   *    __acc + x + y => cartesian_fold((x, y, __acc) -> __acc + x + y, x, y, __acc)
   *
   */
  private static Expr foldUnapplied(Expr expr, List<String> unappliedBindings, String accumulatorId)
  {

    // filter to get list of IdentifierExpr that are backed by the unapplied bindings
    final List<IdentifierExpr> args = expr.analyzeInputs()
                                          .getFreeVariables()
                                          .stream()
                                          .filter(x -> unappliedBindings.contains(x.getBinding()))
                                          .collect(Collectors.toList());

    final List<IdentifierExpr> lambdaArgs = new ArrayList<>();

    // construct lambda args from list of args to apply. Identifiers in a lambda body have artificial 'binding' values
    // that is the same as the 'identifier', because the bindings are supplied by the wrapping apply function
    // replacements are done by binding rather than identifier because repeats of the same input should not result
    // in a cartesian product
    final Map<String, IdentifierExpr> toReplace = new HashMap<>();
    for (IdentifierExpr applyFnArg : args) {
      if (!toReplace.containsKey(applyFnArg.getBinding())) {
        IdentifierExpr lambdaRewrite = new IdentifierExpr(applyFnArg.getBinding());
        lambdaArgs.add(lambdaRewrite);
        toReplace.put(applyFnArg.getBinding(), lambdaRewrite);
      }
    }

    lambdaArgs.add(new IdentifierExpr(accumulatorId));

    // rewrite identifiers in the expression which will become the lambda body, so they match the lambda identifiers we
    // are constructing
    Expr newExpr = expr.visit(childExpr -> {
      if (childExpr instanceof IdentifierExpr) {
        if (toReplace.containsKey(((IdentifierExpr) childExpr).getBinding())) {
          return toReplace.get(((IdentifierExpr) childExpr).getBinding());
        }
      }
      return childExpr;
    });


    // wrap an expression in either fold or cartesian_fold to apply any unapplied identifiers
    final LambdaExpr lambdaExpr = new LambdaExpr(lambdaArgs, newExpr);
    final ApplyFunction fn;
    if (lambdaArgs.size() == 2) {
      fn = new ApplyFunction.FoldFunction();
    } else {
      fn = new ApplyFunction.CartesianFoldFunction();
    }

    final Expr magic = new ApplyFunctionExpr(fn, fn.name(), lambdaExpr, ImmutableList.copyOf(lambdaArgs));
    return magic;
  }

  /**
   * Performs partial lifting of free identifiers of the lambda expression of an {@link ApplyFunctionExpr}, constrained
   * by a list of "unapplied" identifiers, and translating them into arguments of a new {@link LambdaExpr} and
   * {@link ApplyFunctionExpr} as appropriate.
   *
   * The "unapplied" identifiers list is used to allow say only lifting array identifiers and adding it to the cartesian
   * product to allow "magical" translation of multi-value string dimensions which are expressed as single value
   * dimensions to function correctly and as expected.
   */
  private static ApplyFunctionExpr liftApplyLambda(ApplyFunctionExpr expr, List<String> unappliedArgs)
  {
    // recursively evaluate arguments to ensure they are properly transformed into arrays as necessary
    Set<String> unappliedInThisApply =
        unappliedArgs.stream()
                     .filter(u -> !expr.bindingAnalysis.getArrayBindings().contains(u))
                     .collect(Collectors.toSet());

    List<String> unappliedIdentifiers =
        expr.bindingAnalysis
            .getFreeVariables()
            .stream()
            .filter(x -> unappliedInThisApply.contains(x.getBindingIfIdentifier()))
            .map(IdentifierExpr::getIdentifierIfIdentifier)
            .collect(Collectors.toList());

    List<Expr> newArgs = new ArrayList<>();
    for (int i = 0; i < expr.argsExpr.size(); i++) {
      newArgs.add(
          applyUnappliedBindings(
              expr.argsExpr.get(i),
              expr.argsBindingAnalyses.get(i),
              unappliedIdentifiers
          )
      );
    }

    // this will _not_ include the lambda identifiers.. anything in this list needs to be applied
    List<IdentifierExpr> unappliedLambdaBindings =
        expr.lambdaBindingAnalysis.getFreeVariables()
                                  .stream()
                                  .filter(x -> unappliedArgs.contains(x.getBindingIfIdentifier()))
                                  .map(x -> new IdentifierExpr(x.getIdentifier(), x.getBinding()))
                                  .collect(Collectors.toList());

    if (unappliedLambdaBindings.isEmpty()) {
      return new ApplyFunctionExpr(expr.function, expr.name, expr.lambdaExpr, newArgs);
    }

    final ApplyFunction newFn;
    final ApplyFunctionExpr newExpr;

    newArgs.addAll(unappliedLambdaBindings);

    switch (expr.function.name()) {
      case ApplyFunction.MapFunction.NAME:
      case ApplyFunction.CartesianMapFunction.NAME:
        // map(x -> x + y, x) =>
        //  cartesian_map((x, y) -> x + y, x, y)
        // cartesian_map((x, y) -> x + y + z, x, y) =>
        //  cartesian_map((x, y, z) -> x + y + z, x, y, z)
        final List<IdentifierExpr> lambdaIds =
            new ArrayList<>(expr.lambdaExpr.getIdentifiers().size() + unappliedArgs.size());
        lambdaIds.addAll(expr.lambdaExpr.getIdentifierExprs());
        lambdaIds.addAll(unappliedLambdaBindings);
        final LambdaExpr newLambda = new LambdaExpr(lambdaIds, expr.lambdaExpr.getExpr());
        newFn = new ApplyFunction.CartesianMapFunction();
        newExpr = new ApplyFunctionExpr(newFn, newFn.name(), newLambda, newArgs);
        break;
      case ApplyFunction.AllMatchFunction.NAME:
      case ApplyFunction.AnyMatchFunction.NAME:
      case ApplyFunction.FilterFunction.NAME:
        // i'm lazy and didn't add 'cartesian_filter', 'cartesian_any', and 'cartesian_and', so instead steal the match
        // expressions lambda and translate it into a 'cartesian_map', and apply that to the match function with a new
        // identity expression lambda since the input is an array of boolean expression results (or should be..)
        // filter(x -> x > y, x) =>
        //  filter(x -> x, cartesian_map((x,y) -> x > y, x, y))
        // any(x -> x > y, x) =>
        //  any(x -> x, cartesian_map((x, y) -> x > y, x, y))
        // all(x -> x > y, x) =>
        //  all(x -> x, cartesian_map((x, y) -> x > y, x, y))
        ApplyFunction newArrayFn = new ApplyFunction.CartesianMapFunction();
        IdentifierExpr identityExprIdentifier = new IdentifierExpr("_");
        LambdaExpr identityExpr = new LambdaExpr(ImmutableList.of(identityExprIdentifier), identityExprIdentifier);
        ApplyFunctionExpr arrayExpr = new ApplyFunctionExpr(newArrayFn, newArrayFn.name(), identityExpr, newArgs);
        newExpr = new ApplyFunctionExpr(expr.function, expr.function.name(), identityExpr, ImmutableList.of(arrayExpr));
        break;
      case ApplyFunction.FoldFunction.NAME:
      case ApplyFunction.CartesianFoldFunction.NAME:
        // fold((x, acc) -> acc + x + y, x, acc) =>
        //  cartesian_fold((x, y, acc) -> acc + x + y, x, y, acc)
        // cartesian_fold((x, y, acc) -> acc + x + y + z, x, y, acc) =>
        //  cartesian_fold((x, y, z, acc) -> acc + x + y + z, x, y, z, acc)

        final List<Expr> newFoldArgs =
            new ArrayList<>(expr.argsExpr.size() + unappliedLambdaBindings.size());
        final List<IdentifierExpr> newFoldLambdaIdentifiers =
            new ArrayList<>(expr.lambdaExpr.getIdentifiers().size() + unappliedLambdaBindings.size());
        final List<IdentifierExpr> existingFoldLambdaIdentifiers = expr.lambdaExpr.getIdentifierExprs();
        // accumulator argument is last argument, slice it off when constructing new arg list and lambda args
        for (int i = 0; i < expr.argsExpr.size() - 1; i++) {
          newFoldArgs.add(expr.argsExpr.get(i));
          newFoldLambdaIdentifiers.add(existingFoldLambdaIdentifiers.get(i));
        }
        newFoldArgs.addAll(unappliedLambdaBindings);
        newFoldLambdaIdentifiers.addAll(unappliedLambdaBindings);
        // add accumulator last
        newFoldLambdaIdentifiers.add(existingFoldLambdaIdentifiers.get(existingFoldLambdaIdentifiers.size() - 1));
        newFoldArgs.add(expr.argsExpr.get(expr.argsExpr.size() - 1));
        final LambdaExpr newFoldLambda = new LambdaExpr(newFoldLambdaIdentifiers, expr.lambdaExpr.getExpr());

        newFn = new ApplyFunction.CartesianFoldFunction();
        newExpr = new ApplyFunctionExpr(newFn, newFn.name(), newFoldLambda, newFoldArgs);
        break;
      default:
        throw new RE("Unable to transform apply function:[%s]", expr.function.name());
    }

    return newExpr;
  }

  /**
   * Validate that an expression uses input bindings in a type consistent manner.
   */
  public static void validateExpr(Expr expression, Expr.BindingAnalysis bindingAnalysis)
  {
    final Set<String> conflicted =
        Sets.intersection(bindingAnalysis.getScalarBindings(), bindingAnalysis.getArrayBindings());
    if (!conflicted.isEmpty()) {
      throw new RE("Invalid expression: %s; %s used as both scalar and array variables", expression, conflicted);
    }
  }

  /**
   * Create {@link Expr.ObjectBinding} backed by {@link Map} to provide values for identifiers to evaluate {@link Expr}
   */
  public static Expr.ObjectBinding withMap(final Map<String, ?> bindings)
  {
    return bindings::get;
  }

  /**
   * Create {@link Expr.ObjectBinding} backed by map of {@link Supplier} to provide values for identifiers to evaluate
   * {@link Expr}
   */
  public static Expr.ObjectBinding withSuppliers(final Map<String, Supplier<Object>> bindings)
  {
    return (String name) -> {
      Supplier<Object> supplier = bindings.get(name);
      return supplier == null ? null : supplier.get();
    };
  }
}