/* eslint-disable capitalized-comments */
import {
  defaultArmKey,
  fieldPathSeparator,
  isPartialObjectKey,
  numHashBuckets,
} from "../constants";
import emptyThrows from "./emptyThrows";
import evaluate, { complexFormExpressionEvaluationError } from "./evaluate";
import {
  getAnonymousObjectExpression,
  getBooleanExpression,
  getFloatExpression,
  getIntExpression,
  getNoOpExpression,
  getStringExpression,
} from "./expression";
import hash from "./hash";
import nullThrows from "./nullThrows";
import {
  getExpressionEvaluationCountLogs,
  getEventLogs,
  getExposureLogs,
  mergeLogs,
} from "./reductionLogs";
import stableStringify from "./stableStringify";
import {
  BooleanExpression,
  CommitConfig,
  SplitAssignment,
  DimensionMapping,
  Expression,
  FieldQuery,
  FloatExpression,
  FragmentDefinitions,
  InlineFragment,
  IntExpression,
  isQueryVariable,
  ObjectExpression,
  ObjectValue,
  ObjectValueWithVariables,
  Query,
  Split,
  SplitMap,
  Value,
  ValueWithVariables,
  Logs,
} from "../types";
import asError from "./asError";
import getNestedValue from "./getNestedValue";
import asPlainObjectOrThrow from "./asPlainObjectOrThrow";
import getInlineFragment from "./getInlineFragment";

/**
 * Summary
 *
 * Expression reduction takes a query and/or some arguments and applies
 * interpreter steps to reduce the expression as much as possible. It is
 * analogous to beta-reduction in the lambda calculus. If all function arguments
 * are supplied, we return a fully reduced expression in "normal form". Normal
 * form expressions can then be converted into JSON. Otherwise, we return a
 * partially reduced expression in "complex form" which requires further
 * reduction with additional arguments for the function expressions it contains.
 *
 * Each time we reduce an expression into a simpler form, we keep track of the
 * expressions we've needed to "evaluate" to compute the reduction. We track
 * this via "logs" which we attach to the result expression. This lets users
 * visualize how often different parts of the expression tree have been used.
 *
 * Partial Field Arguments
 *
 * When a query field has a partial field arguments object, we reduce the
 * expression tree as much as possible given the available fields within this
 * object and leave the function expression that references it intact so that on
 * a subsequent reduction, when the full field arguments object can be provided,
 * we can fully reduce the tree correctly. There are 3 changes to the main
 * reduction logic that allow for this:
 *
 * 1. We leave function expressions intact if any of the arguments passed to it
 * is a partial object.
 *
 * 2. We have a reduction flag that toggles partial object variable reduction.
 * If it's off (which it is by default), we do not reduce variable expressions
 * that reference partial objects.
 *
 * 3. The only time we enable partial object variable reduction is in the
 * (initial) object reduction in a get field expression when we check to see if
 * we can access the desired field. (And if we can't, we return the get field
 * expression with its object reduced but with partial object variable reduction
 * disabled.)
 *
 * Complexity and Logic
 *
 * For any expression, there are a finite number of reduction steps until it
 * cannot be reduced further. The reduction logic of each expression type
 * attempts to reduce the expression and its children as much as possible given
 * the current context. The logic for application and variable expressions is
 * especially prone to complexity blow-up. In particular, an application
 * argument should be reduced as much as possible before being passed to a
 * function expression reduction, where it becomes a variable, so that the
 * reduction isn't repeated for every variable expression in the function body
 * that references it.
 */

// TODO: Refactor using fold with pass down?
// eslint-disable-next-line max-params
export default function reduce(
  splits: SplitMap,
  commitConfig: CommitConfig,
  query: Query<ObjectValueWithVariables> | null,
  variableValues: ObjectValue,
  rootExpression: Expression,
  allowMissingVariables: boolean
): Expression {
  const innerQuery = getInnerQuery(
    query,
    variableValues,
    allowMissingVariables
  );
  return innerReduce(
    splits,
    commitConfig,
    createAssignmentCache(),
    /* enablePartialObjectVariableReduction */ false,
    innerQuery?.fragmentDefinitions ?? {},
    innerQuery?.fieldQuery ?? null,
    /* args */ null,
    /* variables */ {},
    rootExpression
  );
}

type AssignmentCache = {
  get(splitId: string, unitId: string): AssignmentCacheValue | null;
  set(splitId: string, unitId: string, value: AssignmentCacheValue): void;
};

type AssignmentCacheValue = {
  assignment: SplitAssignment;
  eventObjectTypeName: string | null;
  eventPayload: ObjectValue | null;
  eventPayloadLogs: Logs;
};

function createAssignmentCache(): AssignmentCache {
  const cache = new Map<string, AssignmentCacheValue>();

  return {
    get: (splitId, unitId) => {
      return cache.get(getAssignmentCacheKey(splitId, unitId)) ?? null;
    },
    set: (splitId, unitId, value) => {
      cache.set(getAssignmentCacheKey(splitId, unitId), value);
    },
  };
}

function getAssignmentCacheKey(splitId: string, unitId: string): string {
  return stableStringify({ splitId, unitId });
}

function getInnerQuery(
  query: Query<ObjectValueWithVariables> | null,
  variableValues: ObjectValue,
  allowMissingVariables: boolean
): Query<ObjectExpression> | null {
  return query
    ? {
        ...query,
        fragmentDefinitions: Object.fromEntries(
          Object.entries(query.fragmentDefinitions).map(
            ([fragmentName, fragment]) => [
              fragmentName,
              getInnerInlineFragment(
                query.variableDefinitions,
                fragment,
                variableValues,
                allowMissingVariables
              ),
            ]
          )
        ),
        fieldQuery: getInnerFieldQuery(
          query.variableDefinitions,
          query.fieldQuery,
          variableValues,
          allowMissingVariables
        ),
      }
    : null;
}

function getInnerFieldQuery(
  variableDefinitions: Query<ObjectValueWithVariables>["variableDefinitions"],
  fieldQuery: FieldQuery<ObjectValueWithVariables>,
  variableValues: ObjectValue,
  allowMissingVariables: boolean
): FieldQuery<ObjectExpression> {
  return Object.fromEntries(
    Object.entries(fieldQuery).map(([objectTypeName, fragment]) => [
      objectTypeName,
      fragment.type === "InlineFragment"
        ? getInnerInlineFragment(
            variableDefinitions,
            fragment,
            variableValues,
            allowMissingVariables
          )
        : fragment,
    ])
  );
}

function getInnerInlineFragment(
  variableDefinitions: Query<ObjectValueWithVariables>["variableDefinitions"],
  fragment: InlineFragment<ObjectValueWithVariables>,
  variableValues: ObjectValue,
  allowMissingVariables: boolean
): InlineFragment<ObjectExpression> {
  return {
    type: "InlineFragment",
    objectTypeName: fragment.objectTypeName,
    selection: Object.fromEntries(
      Object.entries(fragment.selection).map(
        ([fieldName, { fieldArguments, fieldQuery }]) => [
          fieldName,
          {
            fieldArguments: getAnonymousObjectExpression(
              replaceVariables(
                variableDefinitions,
                fieldArguments,
                variableValues,
                allowMissingVariables
              ) as ObjectValue,
              /* isTransient */ true
            ),
            fieldQuery: fieldQuery
              ? getInnerFieldQuery(
                  variableDefinitions,
                  fieldQuery,
                  variableValues,
                  allowMissingVariables
                )
              : null,
          },
        ]
      )
    ),
  };
}

function replaceVariables(
  variableDefinitions: Query<ObjectValueWithVariables>["variableDefinitions"],
  value: ValueWithVariables,
  variableValues: ObjectValue,
  allowMissingVariables: boolean
): Value {
  switch (typeof value) {
    case "string":
    case "boolean":
    case "number":
    case "bigint":
      return value;
    case "object": {
      if (isQueryVariable(value)) {
        const variableName = value.name;
        if (!(variableName in variableDefinitions)) {
          throw new Error(`Unknown query variable ${variableName}`);
        }
        const { defaultValue } = variableDefinitions[variableName];

        if (
          !(variableName in variableValues) &&
          !defaultValue &&
          !allowMissingVariables
        ) {
          throw new Error(`Missing query variable ${variableName}`);
        }

        // TODO: this will actually return undefined when the variable is not present
        // This is expected behavior when running codegen, as we allowMissingVariables
        // The undefined is handled by filtering it out in the ObjectValueWithVariables case
        // However, it makes the types of this function a bit of a lie, which would be nice to fix.
        return variableValues[variableName] ?? defaultValue;
      }

      if (Array.isArray(value)) {
        return value.map((v) =>
          replaceVariables(
            variableDefinitions,
            v,
            variableValues,
            allowMissingVariables
          )
        );
      }

      return Object.fromEntries(
        Object.entries(value)
          .map(([fieldName, fieldValue]) => [
            fieldName,
            replaceVariables(
              variableDefinitions,
              fieldValue,
              variableValues,
              allowMissingVariables
            ),
          ])
          .filter(([, fieldValue]) => fieldValue !== undefined)
      );
    }
    default: {
      throw new Error(`Unexpected value type: ${typeof value}`);
    }
  }
}

// eslint-disable-next-line max-params
function innerReduce(
  splits: SplitMap,
  commitConfig: CommitConfig,
  assignmentCache: AssignmentCache,
  enablePartialObjectVariableReduction: boolean,
  fragmentDefinitions: FragmentDefinitions<ObjectExpression>,
  innerQuery: FieldQuery<ObjectExpression> | null,
  args: Expression[] | null, // Reduced expressions (given a null query)
  // Reduced expressions (given a null query)
  variables: { [variableId: string]: Expression },
  expression: Expression
): Expression {
  if (!!args && expression.type !== "FunctionExpression") {
    throw new Error(
      `Reduction arguments (${JSON.stringify(
        args
      )}) given for an expression that isn't a function (${JSON.stringify(
        expression.type
      )}).`
    );
  }

  const thisLogs = mergeLogs(
    expression.logs,
    getExpressionEvaluationCountLogs(expression)
  );

  switch (expression.type) {
    case "NoOpExpression":
    case "BooleanExpression":
    case "IntExpression":
    case "FloatExpression":
    case "StringExpression":
    case "RegexExpression":
    case "EnumExpression":
      return expression;

    /**
     * If there's no query, return the whole object expression with all fields
     * reduced (with no query or arguments).
     *
     * Else return the object expression with only the query fields included.
     * Pre-reduce query fields without query field arguments first. Then if
     * the result is a function expression, reduce them again with query field
     * arguments.
     */
    case "ObjectExpression": {
      if (!innerQuery) {
        return {
          ...expression,
          fields: Object.fromEntries(
            Object.keys(expression.fields).map((fieldName) => [
              fieldName,
              innerReduce(
                splits,
                commitConfig,
                assignmentCache,
                enablePartialObjectVariableReduction,
                fragmentDefinitions,
                null, // innerQuery
                null, // args
                variables,
                nullThrows(
                  expression.fields[fieldName],
                  `Object expression has null field "${fieldName}".`
                )
              ),
            ])
          ),
        };
      }

      const fragment = innerQuery[expression.objectTypeName];
      const selection = fragment
        ? getInlineFragment(fragmentDefinitions, fragment).selection
        : {};
      const fields = Object.fromEntries(
        Object.keys(selection).flatMap((fieldName) => {
          const unreducedField = expression.fields[fieldName];

          if (!unreducedField) {
            return [];
          }

          const field = innerReduce(
            splits,
            commitConfig,
            assignmentCache,
            enablePartialObjectVariableReduction,
            fragmentDefinitions,
            selection[fieldName].fieldQuery,
            null, // args
            variables,
            unreducedField
          );

          return [
            [
              fieldName,
              field.type === "FunctionExpression"
                ? innerReduce(
                    splits,
                    commitConfig,
                    assignmentCache,
                    enablePartialObjectVariableReduction,
                    fragmentDefinitions,
                    selection[fieldName].fieldQuery,
                    [selection[fieldName].fieldArguments],
                    variables,
                    field
                  )
                : field,
            ],
          ];
        })
      );

      return { ...expression, fields };
    }

    /**
     * Reduce the object without any query or arguments with partial object
     * variable reduction enabled (where we reduce partial object variable
     * expressions to the partial object expressions they reference in the
     * variables map). Then check if we can get the field we want. If we can,
     * return it.
     *
     * Else return the whole get field expression with the object reduced but
     * this time with partial object variable reduction disabled. So we reduce
     * what we can in the object while leaving partial object variable
     * references intact for subsequent reductions which may pass different
     * partial objects for these variables (with different fields present).
     */
    case "GetFieldExpression": {
      const object1 = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        true, // enablePartialObjectVariableReduction
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.object, "Get field expression has null object.")
      );

      const field = getField(
        object1,
        nullThrows(
          expression.fieldPath,
          "Get field expression has null field path."
        )
      );

      if (field) {
        const logs = mergeLogs(thisLogs, object1.logs, field.logs);
        return { ...field, logs };
      }

      const object2 = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        false, // enablePartialObjectVariableReduction
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.object, "Get field expression has null object.")
      );

      return {
        ...expression,
        object: object2,
      };
    }

    /**
     * Reduce the object with the current query. If the result is not an
     * object expression, return the whole update object expression with the
     * reduced object.
     *
     * Else return the object expression but with its fields updated with the
     * field update expressions. Only apply a field update if there's no query
     * or its field is in the query. Pre-reduce field updates without query
     * field arguments first. Then if we have a query and the result is a
     * function expression, reduce them again with query field arguments.
     */
    case "UpdateObjectExpression": {
      const object = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        innerQuery,
        null, // args
        variables,
        nullThrows(
          expression.object,
          "Update object expression has null object."
        )
      );

      if (object.type !== "ObjectExpression") {
        return { ...expression, object };
      }
      const { objectTypeName } = object;

      const fragment = innerQuery ? innerQuery[objectTypeName] : null;
      const selection = !fragment
        ? null
        : getInlineFragment(fragmentDefinitions, fragment).selection;

      Object.keys(expression.updates).forEach((fieldName) => {
        if (!selection || selection[fieldName]) {
          if (!object.fields[fieldName]) {
            throw new Error(
              "Update object expression has object with missing update " +
                `field "${fieldName}".`
            );
          }
          const update = innerReduce(
            splits,
            commitConfig,
            assignmentCache,
            enablePartialObjectVariableReduction,
            fragmentDefinitions,
            selection ? selection[fieldName].fieldQuery : null,
            null, // args
            variables,
            nullThrows(
              expression.updates[fieldName],
              `Update object expression has null update "${fieldName}".`
            )
          );
          object.fields[fieldName] =
            selection && update.type === "FunctionExpression"
              ? innerReduce(
                  splits,
                  commitConfig,
                  assignmentCache,
                  enablePartialObjectVariableReduction,
                  fragmentDefinitions,
                  selection[fieldName].fieldQuery,
                  [selection[fieldName].fieldArguments],
                  variables,
                  update
                )
              : update;
        }
      });

      const logs = mergeLogs(thisLogs, object.logs);

      return { ...object, logs };
    }

    /**
     * Return the whole list expression with all items reduced with the
     * current query (but no arguments).
     */
    case "ListExpression":
      return {
        ...expression,
        items: expression.items.map((item, index) =>
          innerReduce(
            splits,
            commitConfig,
            assignmentCache,
            enablePartialObjectVariableReduction,
            fragmentDefinitions,
            innerQuery,
            null, // args
            variables,
            nullThrows(item, `List expression has null item at index ${index}.`)
          )
        ),
      };

    /**
     * Reduce the control, each case 'when' and 'then', and the default. The
     * case 'then' and default expressions get reduced with the current query
     * as they are the possible return values and so on the query path. The
     * control and case 'when' expressions are not reduced with the current
     * query as they are not possible return values and so off the query path.
     *
     * We try to evaluate the control and then each case 'when'. As soon as
     * a 'when' value matches the control value, we return the corresponding
     * 'then' expression. We attach the merged logs of the switch expression,
     * the control and each case 'when' that was evaluated, to the returned
     * 'then' expression.
     *
     * If none of the 'when' values matched the control value, we return the
     * default expression.
     *
     * If evaluation fails at any point due to expressions being in complex
     * form, i.e. not fully reduced, we return the whole switch expression but
     * with the reduced control, case 'when's and 'then's, and default.
     */
    case "SwitchExpression": {
      const control = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.control, "Switch expression has null control.")
      );
      const cases = expression.cases.map((item, index) => ({
        id: item.id,
        when: innerReduce(
          splits,
          commitConfig,
          assignmentCache,
          enablePartialObjectVariableReduction,
          fragmentDefinitions,
          null, // innerQuery
          null, // args
          variables,
          nullThrows(
            item.when,
            `Switch expression case has null 'when' at index ${index}.`
          )
        ),
        then: innerReduce(
          splits,
          commitConfig,
          assignmentCache,
          enablePartialObjectVariableReduction,
          fragmentDefinitions,
          innerQuery,
          null, // args
          variables,
          nullThrows(
            item.then,
            `Switch expression case has null 'then' at index ${index}.`
          )
        ),
      }));
      const defaultExpression = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        innerQuery,
        null, // args
        variables,
        nullThrows(expression.default, "Switch expression has null default.")
      );

      try {
        const { value: controlValue, logs: controlLogs } = evaluate(control);
        let logs = mergeLogs(thisLogs, controlLogs);

        for (const { when, then } of cases) {
          const { value: whenValue, logs: whenLogs } = evaluate(when);
          logs = mergeLogs(logs, whenLogs);

          if (areEqual(controlValue, whenValue)) {
            logs = mergeLogs(logs, then.logs);
            return { ...then, logs };
          }
        }

        logs = mergeLogs(logs, defaultExpression.logs);
        return { ...defaultExpression, logs };
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, control, cases, default: defaultExpression };
    }

    /**
     * Similar to switch expression.
     */
    case "EnumSwitchExpression": {
      const control = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(
          expression.control,
          "Enum switch expression has null control."
        )
      );

      const cases = Object.fromEntries(
        Object.keys(expression.cases).map((enumValue) => [
          enumValue,
          innerReduce(
            splits,
            commitConfig,
            assignmentCache,
            enablePartialObjectVariableReduction,
            fragmentDefinitions,
            innerQuery,
            null, // args
            variables,
            nullThrows(
              expression.cases[enumValue],
              `Enum switch expression has null case "${enumValue}".`
            )
          ),
        ])
      );

      try {
        const { value: controlValue, logs: controlLogs } = evaluate(control);
        if (typeof controlValue !== "string") {
          throw new Error(
            "Evaluated control of enum switch expression is not a string."
          );
        }

        const then = cases[controlValue];
        if (!then) {
          throw new Error(
            `Evaluated control of enum switch expression "${controlValue}" is missing in cases.`
          );
        }

        const logs = mergeLogs(thisLogs, controlLogs, then.logs);

        return { ...then, logs };
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, control, cases };
    }

    /**
     * Reduce a and b. Evaluate them both. Compare their values. Return a new
     * "transient" result expression that represents the comparison result.
     * Attach the merged logs of the comparison expression, a and b, to the
     * result expression logs. If evaluation fails, return the whole
     * comparison expression with its reduced subexpressions.
     */
    case "ComparisonExpression": {
      const a = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.a, "Comparison expression has null a.")
      );
      const b = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.b, "Comparison expression has null b.")
      );

      try {
        const { value: aValue, logs: aLogs } = evaluate(a);
        const { value: bValue, logs: bLogs } = evaluate(b);

        const logs = mergeLogs(thisLogs, aLogs, bLogs);

        const operator = nullThrows(
          expression.operator,
          "Comparison expression has null operator."
        );
        switch (operator) {
          case "==":
          case "!=": {
            const result = areEqual(aValue, bValue);
            return getComparisonResultExpression(
              operator === "==" ? result : !result,
              logs
            );
          }

          case "<": {
            if (typeof aValue !== "number" || typeof bValue !== "number") {
              throw new Error(
                "Evaluated operands of comparison expression with '<' " +
                  "operator are not both numbers."
              );
            }
            return getComparisonResultExpression(aValue < bValue, logs);
          }

          case "<=": {
            if (typeof aValue !== "number" || typeof bValue !== "number") {
              throw new Error(
                "Evaluated operands of comparison expression with '<=' " +
                  "operator are not both numbers."
              );
            }
            return getComparisonResultExpression(aValue <= bValue, logs);
          }

          case ">": {
            if (typeof aValue !== "number" || typeof bValue !== "number") {
              throw new Error(
                "Evaluated operands of comparison expression with '>' " +
                  "operator are not both numbers."
              );
            }
            return getComparisonResultExpression(aValue > bValue, logs);
          }

          case ">=": {
            if (typeof aValue !== "number" || typeof bValue !== "number") {
              throw new Error(
                "Evaluated operands of comparison expression with '>=' " +
                  "operator are not both numbers."
              );
            }
            return getComparisonResultExpression(aValue >= bValue, logs);
          }

          case "AND": {
            if (typeof aValue !== "boolean" || typeof bValue !== "boolean") {
              throw new Error(
                "Evaluated operands of comparison expression with 'AND' " +
                  "operator are not both booleans."
              );
            }
            return getComparisonResultExpression(aValue && bValue, logs);
          }

          case "OR": {
            if (typeof aValue !== "boolean" || typeof bValue !== "boolean") {
              throw new Error(
                "Evaluated operands of comparison expression with 'OR' " +
                  "operator are not both booleans."
              );
            }
            return getComparisonResultExpression(aValue || bValue, logs);
          }

          case "in":
          case "notIn": {
            if (!Array.isArray(bValue)) {
              throw new Error(
                `Second evaluated operand of comparison expression with " +
                  "'${operator}' operator is not an array.`
              );
            }
            const result = bValue.some((itemValue) =>
              areEqual(aValue, itemValue)
            );
            return getComparisonResultExpression(
              operator === "in" ? result : !result,
              logs
            );
          }

          case "startsWith":
          case "notStartsWith": {
            const shouldInvert = operator === "notStartsWith";

            if (typeof aValue === "string" && typeof bValue === "string") {
              const result = aValue.startsWith(bValue);
              return getComparisonResultExpression(
                shouldInvert ? !result : result,
                logs
              );
            }

            if (Array.isArray(aValue)) {
              const result =
                aValue.length === 0 ? false : areEqual(aValue[0], bValue);
              return getComparisonResultExpression(
                shouldInvert ? !result : result,
                logs
              );
            }

            throw new Error(
              `Evaluated operands of comparison expression with '${operator}'` +
                "operator are not both strings or an array and an element."
            );
          }

          case "endsWith":
          case "notEndsWith": {
            const shouldInvert = operator === "notEndsWith";

            if (typeof aValue === "string" && typeof bValue === "string") {
              const result = aValue.endsWith(bValue);
              return getComparisonResultExpression(
                shouldInvert ? !result : result,
                logs
              );
            }

            if (Array.isArray(aValue)) {
              const result =
                aValue.length === 0
                  ? false
                  : areEqual(aValue[aValue.length - 1], bValue);
              return getComparisonResultExpression(
                shouldInvert ? !result : result,
                logs
              );
            }

            throw new Error(
              `Evaluated operands of comparison expression with '${operator}'` +
                "operator are not both strings or an array and an element."
            );
          }

          case "contains":
          case "notContains": {
            const shouldInvert = operator === "notContains";

            if (typeof aValue === "string" && typeof bValue === "string") {
              const result = aValue.includes(bValue);
              return getComparisonResultExpression(
                shouldInvert ? !result : result,
                logs
              );
            }

            if (Array.isArray(aValue)) {
              const result = aValue.some((itemValue) =>
                areEqual(itemValue, bValue)
              );
              return getComparisonResultExpression(
                shouldInvert ? !result : result,
                logs
              );
            }

            throw new Error(
              `Evaluated operands of comparison expression with '${operator}'` +
                "operator are not both strings or an array and an element."
            );
          }

          case "matches":
          case "notMatches": {
            if (typeof aValue !== "string" || typeof bValue !== "string") {
              throw new Error(
                `Evaluated operands of comparison expression with " +
                  "'${operator}' operator are not both strings.`
              );
            }
            const bRegex = new RegExp(bValue);
            const result = bRegex.test(aValue);
            return getComparisonResultExpression(
              operator === "matches" ? result : !result,
              logs
            );
          }

          default: {
            const neverOperator: never = operator;
            throw new Error(`unexpected operator: ${neverOperator}`);
          }
        }
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, a, b };
    }

    /**
     * Similar to comparison expression.
     */
    case "ArithmeticExpression": {
      const a = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.a, "Arithmetic expression has null a")
      );
      const b = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.b, "Arithmetic expression has null b")
      );

      try {
        const { value: aValue, logs: aLogs } = evaluate(a);
        const { value: bValue, logs: bLogs } = evaluate(b);

        if (typeof aValue !== "number" || typeof bValue !== "number") {
          throw new Error(
            "Evaluated operands of arithmetic expression are not both " +
              "numbers."
          );
        }

        const logs = mergeLogs(thisLogs, aLogs, bLogs);

        const operator = nullThrows(
          expression.operator,
          "Arithmetic expression has null operator."
        );
        switch (operator) {
          case "+":
            return getArithmeticResultExpression(aValue + bValue, logs);

          case "-":
            return getArithmeticResultExpression(aValue - bValue, logs);

          case "*":
            return getArithmeticResultExpression(aValue * bValue, logs);

          case "/":
            return getArithmeticResultExpression(aValue / bValue, logs);

          case "POW":
            return getArithmeticResultExpression(aValue ** bValue, logs);

          case "MOD":
            return getArithmeticResultExpression(aValue % bValue, logs);

          default: {
            const neverOperator: never = operator;
            throw new Error(`unexpected operator: ${neverOperator}`);
          }
        }
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, a, b };
    }

    case "RoundNumberExpression": {
      const number = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(
          expression.number,
          "Round number expression has null number."
        )
      );

      try {
        const { value: numberValue, logs: numberLogs } = evaluate(number);
        if (typeof numberValue !== "number") {
          throw new Error(
            "Evaluated number of round number expression is not a number."
          );
        }

        const result = getIntExpression(
          Math.round(numberValue),
          /* isTransient */ true
        );

        const logs = mergeLogs(thisLogs, numberLogs, result.logs);

        return { ...result, logs };
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, number };
    }

    case "StringifyNumberExpression": {
      const number = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(
          expression.number,
          "Stringify number expression has null number."
        )
      );

      try {
        const { value: numberValue, logs: numberLogs } = evaluate(number);
        if (typeof numberValue !== "number") {
          throw new Error(
            "Evaluated number of stringify number expression is not a number."
          );
        }

        const result = getStringExpression(
          numberValue.toString(),
          /* isTransient */ true
        );

        const logs = mergeLogs(thisLogs, numberLogs, result.logs);

        return { ...result, logs };
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, number };
    }

    case "StringConcatExpression": {
      const strings = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(
          expression.strings,
          "String concat expression has null strings."
        )
      );

      try {
        const { value: stringsValue, logs: stringsLogs } = evaluate(strings);
        if (!Array.isArray(stringsValue)) {
          throw new Error(
            "Evaluated strings of string concat expression is not an array."
          );
        }
        if (!stringsValue.every((x) => typeof x === "string")) {
          throw new Error(
            "Evaluated strings array of string concat expression contains " +
              "a value that isn't a string."
          );
        }

        const result = getStringExpression(
          stringsValue.join(""),
          /* isTransient */ true
        );

        const logs = mergeLogs(thisLogs, stringsLogs, result.logs);

        return { ...result, logs };
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, strings };
    }

    case "GetUrlQueryParameterExpression": {
      const url = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(
          expression.url,
          "Get url query parameter expression has null url."
        )
      );
      const queryParameterName = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(
          expression.queryParameterName,
          "Get url query parameter expression has null query parameter name."
        )
      );

      try {
        const { value: urlValue, logs: urlLogs } = evaluate(url);
        if (typeof urlValue !== "string") {
          throw new Error(
            "Evaluated url of get url query parameter expression is not a " +
              "string."
          );
        }

        const { value: queryParameterNameValue, logs: queryParameterNameLogs } =
          evaluate(queryParameterName);
        if (typeof queryParameterNameValue !== "string") {
          throw new Error(
            "Evaluated query parameter name of get url query parameter " +
              "expression is not a string."
          );
        }

        let queryParameterValue = "";
        try {
          const urlObject = new URL(urlValue);
          queryParameterValue =
            urlObject.searchParams.get(queryParameterNameValue) || "";
        } catch (error) {
          //
        }

        const result = getStringExpression(
          queryParameterValue,
          /* isTransient */ true
        );

        const logs = mergeLogs(
          thisLogs,
          urlLogs,
          queryParameterNameLogs,
          result.logs
        );

        return { ...result, logs };
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, url, queryParameterName };
    }

    case "SplitExpression": {
      const split = nullThrows(
        splits[
          nullThrows(expression.splitId, "Split expression has null split ID.")
        ],
        "Split expression has invalid split ID."
      );
      const dimensionId = nullThrows(
        expression.dimensionId,
        "Split expression has null dimension ID."
      );

      const expose = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.expose, "Split expression has null expose.")
      );
      const unitId = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(expression.unitId, "Split expression has null unit ID.")
      );
      const eventPayload = expression.eventPayload
        ? innerReduce(
            splits,
            commitConfig,
            assignmentCache,
            enablePartialObjectVariableReduction,
            fragmentDefinitions,
            null, // innerQuery
            null, // args
            variables,
            expression.eventPayload
          )
        : null;
      const unreducedDimensionMapping = expression.dimensionMapping;
      if (unreducedDimensionMapping.type !== "discrete") {
        // TODO: Implement
        throw new Error(
          "Split expression has dimension mapping which isn't discrete."
        );
      }
      const dimensionMapping: DimensionMapping = {
        type: "discrete",
        cases: Object.fromEntries(
          Object.keys(unreducedDimensionMapping.cases).map((armId) => [
            armId, // TODO: Validate armId
            innerReduce(
              splits,
              commitConfig,
              assignmentCache,
              enablePartialObjectVariableReduction,
              fragmentDefinitions,
              innerQuery,
              null, // args
              variables,
              nullThrows(
                unreducedDimensionMapping.cases[armId],
                "Split expression has discrete dimension mapping with null " +
                  `case for arm "${armId}".`
              )
            ),
          ])
        ),
      };

      try {
        const { value: exposeValue, logs: exposeLogs } = evaluate(expose);
        if (typeof exposeValue !== "boolean") {
          throw new Error(
            "Evaluated expose of split expression is not a boolean."
          );
        }
        const { value: unitIdValue, logs: unitIdLogs } = evaluate(unitId);
        if (typeof unitIdValue !== "string") {
          throw new Error(
            "Evaluated unit ID of split expression is not a string."
          );
        }

        let assignment: SplitAssignment | null = null;
        let eventObjectTypeName: string | null = null;
        let eventPayloadValue: ObjectValue | null = null;
        let eventPayloadLogs: Logs;

        // If we've previously assigned this unit for this split, reuse the
        // previous assignment and also reuse its feature values in the
        // exposure log.
        const cacheEntry = assignmentCache.get(split.id, unitIdValue);
        if (cacheEntry) {
          assignment = cacheEntry.assignment;
          eventObjectTypeName = cacheEntry.eventObjectTypeName;
          eventPayloadValue = cacheEntry.eventPayload;
          eventPayloadLogs = cacheEntry.eventPayloadLogs;
        } else {
          const payloadResult = eventPayload
            ? evaluate(eventPayload)
            : { value: null, logs: {} };

          eventPayloadValue =
            payloadResult.value === null
              ? null
              : asPlainObjectOrThrow(
                  payloadResult.value,
                  new Error(
                    "Evaluated payload of split expression is not an object."
                  )
                );
          eventPayloadLogs = payloadResult.logs;
          eventObjectTypeName = expression.eventObjectTypeName;

          if (!!eventPayloadValue !== !!eventObjectTypeName) {
            // If we have value and not name or vice versa,
            // then the expression is broken so we just throw an exception.
            throw new Error(
              "Evaluated payload of split expression or event object type name is missing."
            );
          }

          assignment = getAssignment(
            commitConfig,
            split,
            unitIdValue,
            eventPayloadValue
          );
          assignmentCache.set(split.id, unitIdValue, {
            assignment,
            eventObjectTypeName,
            eventPayloadLogs,
            eventPayload: eventPayloadValue,
          });
        }

        const shouldExpose =
          exposeValue &&
          Object.values(assignment).some(
            (dimensionAssignment) =>
              dimensionAssignment.type !== "discrete" ||
              dimensionAssignment.armId !== defaultArmKey
          );

        const dimensionAssignment = nullThrows(
          assignment[dimensionId],
          "Split expression has invalid dimension ID."
        );
        if (dimensionAssignment.type === "continuous") {
          // TODO: Implement
          throw new Error("Split expression has continuous dimension.");
        }
        const result = nullThrows(
          dimensionMapping.cases[dimensionAssignment.armId],
          `Split expression has reduced dimension mapping with missing case for assigned arm "${dimensionAssignment.armId}".`
        );

        const logs = mergeLogs(
          thisLogs,
          exposeLogs,
          unitIdLogs,
          eventPayloadLogs,
          shouldExpose
            ? getExposureLogs({
                splitId: split.id,
                unitId: unitIdValue,
                event:
                  eventPayloadValue && expression.eventObjectTypeName
                    ? {
                        objectTypeName: expression.eventObjectTypeName,
                        payload: eventPayloadValue,
                      }
                    : null,
                assignment,
              })
            : undefined,
          result.logs
        );

        return { ...result, logs };
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return {
        ...expression,
        expose,
        unitId,
        dimensionMapping,
        eventPayload,
      };
    }

    case "LogEventExpression": {
      const eventPayload = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        null, // innerQuery
        null, // args
        variables,
        nullThrows(
          expression.eventPayload,
          new Error("Log event expression is missing event payload.")
        )
      );
      try {
        const { value: rawPayloadValue, logs: payloadLogs } =
          evaluate(eventPayload);
        const payloadValue = asPlainObjectOrThrow(
          rawPayloadValue,
          new Error(
            "Evaluated payload of log event expression is not an object."
          )
        );

        const result = getNoOpExpression(/* isTransient */ true);

        const logs = mergeLogs(
          thisLogs,
          payloadLogs,
          getEventLogs({
            objectTypeName: nullThrows(
              expression.eventObjectTypeName,
              new Error(
                `Log event expression with id "${expression.id}" is missing event type name.`
              )
            ),
            payload: payloadValue,
          }),
          result.logs
        );

        return { ...result, logs };
      } catch (error) {
        const { message } = asError(error);
        if (message !== complexFormExpressionEvaluationError) {
          throw error;
        }
      }

      return { ...expression, eventPayload };
    }

    /**
     * If we have arguments, we create a new variables map (by extending the
     * existing one with them), then reduce the function body with this new
     * variables map and return the result.
     *
     * However, if one of the arguments was a partial object, we keep the
     * function expression intact, i.e. we return the whole function
     * expression but with the body still set to the result we got. This
     * allows for partial reduction.
     *
     * If we don't have any arguments, we return the whole function expression
     * with the body reduced with no arguments.
     */
    case "FunctionExpression": {
      if (Array.isArray(args)) {
        if (expression.parameters.length !== args.length) {
          throw new Error(
            `Function expression has ${expression.parameters.length} ` +
              `parameters but was passed ${args.length} arguments.`
          );
        }
        const newVariables = Object.fromEntries(
          expression.parameters.map((parameter, index) => [
            parameter.id,
            args[index],
          ])
        );

        const result = innerReduce(
          splits,
          commitConfig,
          assignmentCache,
          enablePartialObjectVariableReduction,
          fragmentDefinitions,
          innerQuery,
          null, // args
          {
            ...variables,
            ...newVariables,
          },
          nullThrows(expression.body, "Function expression has null body.")
        );

        if (
          args.some(
            (argument) =>
              argument.type === "ObjectExpression" &&
              !!argument.fields[isPartialObjectKey]
          )
        ) {
          return { ...expression, body: result };
        }

        const logs = mergeLogs(thisLogs, result.logs);

        return { ...result, logs };
      }

      const body = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        innerQuery,
        null, // args
        variables,
        nullThrows(expression.body, "Function expression has null body.")
      );
      return { ...expression, body };
    }

    /**
     * We get the referenced expression from the variables map. If it doesn't
     * exist, we just return the variable expression.
     *
     * Else we reduce the referenced expression. Even though it has already
     * been reduced (in the reduction of the ancestor application expression),
     * we reduce it again but this time with the current query, arguments (if
     * it's a function expression) and partial variable reduction mode which
     * may allow for further reduction.
     *
     * If the reduced result is a partial object and partial object variable
     * reduction is disabled, we just return the variable expression to leave
     * it intact. This is ok as its defining function expression will also be
     * left intact and so the variable will still be bound / valid.
     *
     * Else we return the reduced result.
     */
    case "VariableExpression": {
      const variable = variables[expression.variableId];
      if (!variable) {
        return expression;
      }

      const result = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        innerQuery,
        variable.type === "FunctionExpression" ? args : null,
        variables,
        variable
      );

      if (
        !enablePartialObjectVariableReduction &&
        result.type === "ObjectExpression" &&
        !!result.fields[isPartialObjectKey]
      ) {
        return expression;
      }

      const logs = mergeLogs(thisLogs, result.logs);

      return { ...result, logs };
    }

    /**
     * First we pre-reduce the function without any arguments (but with the
     * current query) and reduce the arguments.
     *
     * If the reduced function is a function expression, we reduce it again
     * but this time with the (reduced) arguments, and return the result.
     *
     * Else we return the whole application expression with its reduced
     * function and argument subexpressions.
     */
    case "ApplicationExpression": {
      const reducedFunction = innerReduce(
        splits,
        commitConfig,
        assignmentCache,
        enablePartialObjectVariableReduction,
        fragmentDefinitions,
        innerQuery,
        null, // args
        variables,
        nullThrows(
          expression.function,
          "Application expression has null function."
        )
      );
      const reducedArguments = expression.arguments.map((argument, index) =>
        innerReduce(
          splits,
          commitConfig,
          assignmentCache,
          enablePartialObjectVariableReduction,
          fragmentDefinitions,
          null, // innerQuery
          null, // args
          variables,
          nullThrows(
            argument,
            `Application expression has null argument at index ${index}.`
          )
        )
      );

      if (reducedFunction.type === "FunctionExpression") {
        const result = innerReduce(
          splits,
          commitConfig,
          assignmentCache,
          enablePartialObjectVariableReduction,
          fragmentDefinitions,
          innerQuery,
          reducedArguments,
          variables,
          reducedFunction
        );

        const logs = mergeLogs(thisLogs, result.logs);

        return { ...result, logs };
      }

      return {
        ...expression,
        function: reducedFunction,
        arguments: reducedArguments,
      };
    }

    default: {
      const neverExpression: never = expression;
      throw new Error(
        `Unexpected expression: ${JSON.stringify(neverExpression)}`
      );
    }
  }
}

function getField(
  startObject: Expression,
  fieldPath: string
): Expression | null {
  const fieldPathParts = fieldPath.split(fieldPathSeparator);
  let field: Expression | null = startObject;

  for (let i = 0; i < fieldPathParts.length; i += 1) {
    if (!field || field.type !== "ObjectExpression") {
      return null;
    }
    const fieldName = fieldPathParts[i];
    field = field.fields[fieldName] || null;
  }
  return field;
}

export function areEqual(
  a: Value | null | undefined,
  b: Value | null | undefined
): boolean {
  if (Array.isArray(a)) {
    return (
      Array.isArray(b) &&
      a.length === b.length &&
      a.every((value, index) => areEqual(value, b[index]))
    );
  }
  if (typeof a === "object" && a !== null) {
    // We ignore reserved properties (those beginning __) because they're not
    // relevant to the value equality itself, which is what comparisons using
    // areEqual care about.
    return (
      typeof b === "object" &&
      b !== null &&
      !Array.isArray(b) &&
      Object.keys(a).filter((k) => !k.startsWith("__")).length ===
        Object.keys(b).filter((k) => !k.startsWith("__")).length &&
      Object.keys(a)
        .filter((k) => !k.startsWith("__"))
        .every((key) => areEqual(a[key], b[key]))
    );
  }
  return a === b;
}

function getComparisonResultExpression(
  resultValue: boolean,
  comparisonLogs: Logs
): BooleanExpression {
  const result = getBooleanExpression(resultValue, /* isTransient */ true);
  const logs = mergeLogs(comparisonLogs, result.logs);
  return { ...result, logs };
}

function getArithmeticResultExpression(
  resultValue: number,
  arithmeticLogs: Logs
): IntExpression | FloatExpression {
  const result = Number.isInteger(resultValue)
    ? getIntExpression(resultValue, /* isTransient */ true)
    : getFloatExpression(resultValue, /* isTransient */ true);

  const logs = mergeLogs(arithmeticLogs, result.logs);

  return { ...result, logs };
}

function getAssignment(
  commitConfig: CommitConfig,
  split: Split,
  unitId: string,
  payload: ObjectValue | null
): SplitAssignment {
  if (split.type === "test") {
    const assignment: SplitAssignment = {};

    Object.values(split.dimensions).forEach((dimension) => {
      if (dimension.type !== "discrete") {
        throw new Error(
          `Test split "${split.id}" has non-discrete dimension "${dimension.id}".`
        );
      }

      const unitPoint =
        (hash(`${split.id}${dimension.id}${unitId}`) % numHashBuckets) /
        numHashBuckets;

      const sortedArms = Object.values(dimension.arms).sort(
        (a, b) => a.index - b.index
      );

      let allocationsSum = 0;
      let i = -1;
      while (i + 1 < sortedArms.length && allocationsSum <= unitPoint) {
        allocationsSum += sortedArms[i + 1].allocation;
        i += 1;
      }

      const armId =
        allocationsSum > unitPoint ? sortedArms[i].id : defaultArmKey;
      assignment[dimension.id] = { type: "discrete", armId };
    });

    return assignment;
  }

  const splitConfig = nullThrows(
    commitConfig.splitConfig[split.id],
    `No config for split "${split.id}".`
  );

  const randomAssignment: SplitAssignment = {};
  Object.values(split.dimensions).forEach((dimension) => {
    if (dimension.type !== "discrete") {
      // TODO: Support continuous dimensions
      throw new Error(
        `ML split "${split.id}" has non-discrete dimension "${dimension.id}".`
      );
    }
    const arms = emptyThrows(
      Object.values(dimension.arms),
      `ML split "${split.id}" has dimension "${dimension.id}" with no arms.`
    );
    const armId = arms[Math.floor(Math.random() * arms.length)].id;
    randomAssignment[dimension.id] = { type: "discrete", armId };
  });

  if (splitConfig.type === "EpsilonGreedyConfig") {
    if (Math.random() < splitConfig.epsilon) {
      return randomAssignment; // Explore
    }

    const assignment: SplitAssignment = {};
    Object.values(split.dimensions).forEach((dimension) => {
      const bestDimensionAssignment = nullThrows(
        splitConfig.bestAssignment[dimension.id],
        "Best assignment has no dimension assignment for dimension " +
          `"${dimension.id}" of ML split "${split.id}".`
      );
      assignment[dimension.id] = bestDimensionAssignment;
    });
    return assignment;
  }

  if (splitConfig.type === "PersonalizationSplitConfig") {
    if (Math.random() < splitConfig.epsilon) {
      return randomAssignment; // Explore
    }

    const assignment: SplitAssignment = {};

    Object.values(split.dimensions).forEach((dimension) => {
      if (dimension.type !== "discrete") {
        // TODO: Support continuous dimensions
        throw new Error(
          `ML split "${split.id}" has non-discrete dimension "${dimension.id}".`
        );
      }

      const logic = splitConfig.logic[dimension.id];
      if (!logic) {
        assignment[dimension.id] = randomAssignment[dimension.id];
        return;
      }

      for (const { featureValuesPath, featureValue, armId } of logic.rules) {
        if (
          getNestedValue(payload, featureValuesPath) === featureValue &&
          dimension.arms[armId]
        ) {
          assignment[dimension.id] = { type: "discrete", armId };
          return;
        }
      }

      assignment[dimension.id] = dimension.arms[logic.defaultArmId]
        ? { type: "discrete", armId: logic.defaultArmId }
        : randomAssignment[dimension.id];
    });

    return assignment;
  }

  const neverSplitConfig: never = splitConfig;
  throw new Error(
    `Unexpected split config: ${JSON.stringify(neverSplitConfig)}`
  );
}