import { CompiledFormula, OPERATOR_MAP, UNARY_OPERATOR_MAP } from "../../../formulas/compiler";

import { createEvaluatedCell, evaluateLiteral } from "../../../helpers/cells/cell_evaluation";

import { CellValueType, EvaluatedCell, FormulaCell } from "../../../types/cells";
import {
  BadExpressionError,
  CellErrorType,
  CircularDependencyError,
  NumberTooLargeError,
  SplillBlockedError,
} from "../../../types/errors";
import { buildCompilationParameters, CompilationParameters } from "./compilation_parameters";
import { FormulaDependencyGraph } from "./formula_dependency_graph";
import { PositionSet, SheetSizes } from "./position_set";
import { RangeSet } from "./range_set";
import { SpreadingRelation } from "./spreading_relation";

import {
  handleError,
  implementationErrorMessage,
} from "../../../functions/create_compute_function";
import { matrixMap } from "../../../functions/helpers";
import { PositionMap } from "../../../helpers/cells/position_map";
import { lazy } from "../../../helpers/misc";
import { excludeTopLeft, getZoneArea, positionToZone, union } from "../../../helpers/zones";
import { onIterationEndEvaluationRegistry } from "../../../registries/evaluation_registry";
import { _t } from "../../../translation";
import {
  FunctionTimingEntry,
  FunctionTimingLog,
  PerfProfile,
  RangeTiming,
} from "../../../types/functions";
import { EvaluationGetters } from "../../../types/getters";
import {
  CellPosition,
  FunctionResultObject,
  GetSymbolValue,
  isMatrix,
  Matrix,
  UID,
  Zone,
} from "../../../types/misc";
import { ModelConfig } from "../../../types/model";
import { BoundedRange, Range } from "../../../types/range";

const MAX_ITERATION = 30;

const EMPTY_CELL = Object.freeze(createEvaluatedCell({ value: null }));

const FUNCTION_TO_OPERATOR: Record<string, string> = {};
for (const [op, fn] of Object.entries(OPERATOR_MAP)) {
  FUNCTION_TO_OPERATOR[fn] = op;
}
for (const [op, fn] of Object.entries(UNARY_OPERATOR_MAP)) {
  FUNCTION_TO_OPERATOR[fn] = op;
}

export class Evaluator {
  private readonly getters: EvaluationGetters;
  private compilationParams: CompilationParameters;

  private evaluatedCells: PositionMap<EvaluatedCell> = new PositionMap();
  private formulaDependencies = lazy(new FormulaDependencyGraph());
  private blockedArrayFormulas = new PositionSet({});
  private spreadingRelations = new SpreadingRelation();
  private perfProfile: PerfProfile | undefined;

  constructor(private readonly context: ModelConfig["custom"], getters: EvaluationGetters) {
    this.getters = getters;
    this.compilationParams = buildCompilationParameters(
      this.context,
      this.getters,
      this.computeAndSave.bind(this)
    );
  }

  getPerfProfile(): PerfProfile | undefined {
    return this.perfProfile;
  }

  getEvaluatedCell(position: CellPosition): EvaluatedCell {
    return this.evaluatedCells.get(position) || EMPTY_CELL;
  }

  getSpreadZone(position: CellPosition, options = { ignoreSpillError: false }): Zone | undefined {
    const spreadZone = this.spreadingRelations.getArrayResultZone(position);
    if (!spreadZone) {
      return undefined;
    }
    const evaluatedCell = this.evaluatedCells.get(position);
    if (
      evaluatedCell?.type === CellValueType.error &&
      !(options.ignoreSpillError && evaluatedCell?.value === CellErrorType.SpilledBlocked)
    ) {
      return positionToZone(position);
    }
    return union(positionToZone(position), spreadZone);
  }

  getEvaluatedPositions(): CellPosition[] {
    return this.evaluatedCells.keys();
  }

  getEvaluatedPositionsInSheet(sheetId: UID): CellPosition[] {
    return this.evaluatedCells.keysForSheet(sheetId);
  }

  getArrayFormulaSpreadingOn(position: CellPosition): CellPosition | undefined {
    const isEmpty = this.getEvaluatedCell(position).type === CellValueType.empty;
    if (isEmpty) {
      return undefined;
    }
    const arrayFormulas = this.spreadingRelations.searchFormulaPositionsSpreadingOn(
      position.sheetId,
      positionToZone(position)
    );
    return arrayFormulas.find((position) => !this.blockedArrayFormulas.has(position));
  }

  isArrayFormulaSpillBlocked(position: CellPosition): boolean {
    return this.blockedArrayFormulas.has(position);
  }

  updateDependencies(position: CellPosition) {
    // removing dependencies is slow because it requires
    // to traverse the entire r-tree.
    // The data structure is optimized for searches the other way around
    this.formulaDependencies().removeAllDependencies(position);
    const dependencies = this.getDirectDependencies(position);
    this.formulaDependencies().addDependencies(
      position,
      this.getters.clipRangesToSheet(dependencies)
    );
  }

  private addDependencies(position: CellPosition, dependencies: Range[]) {
    this.formulaDependencies().addDependencies(
      position,
      this.getters.clipRangesToSheet(dependencies)
    );
    this.computeDependencies(dependencies);
  }

  private computeDependencies(dependencies: Range[]) {
    for (const range of dependencies) {
      // ensure that all ranges are computed
      this.compilationParams.ensureRange(range);
    }
  }

  private updateCompilationParametersForIsolatedFormula(originCellPosition?: CellPosition) {
    this.compilationParams = buildCompilationParameters(
      this.context,
      this.getters,
      this.computeAndSave.bind(this)
    );
    this.compilationParams.evalContext.__originCellPosition = originCellPosition;
    this.compilationParams.evalContext.updateDependencies = undefined;
    this.compilationParams.evalContext.addDependencies = undefined;
    this.compilationParams.evalContext.lookupCaches = this.compilationParams.evalContext
      .lookupCaches || {
      forwardSearch: new Map(),
      reverseSearch: new Map(),
    };
  }

  private updateCompilationParameters(functionTimingLog?: FunctionTimingLog) {
    // rebuild the compilation parameters (with a clean cache)
    this.compilationParams = buildCompilationParameters(
      this.context,
      this.getters,
      this.computeAndSave.bind(this)
    );
    this.compilationParams.evalContext.updateDependencies = this.updateDependencies.bind(this);
    this.compilationParams.evalContext.addDependencies = this.addDependencies.bind(this);
    this.compilationParams.evalContext.__timingEntries = functionTimingLog;
    this.compilationParams.evalContext.lookupCaches = {
      forwardSearch: new Map(),
      reverseSearch: new Map(),
    };
  }

  private createEmptyPositionSet() {
    const sheetSizes: SheetSizes = {};
    for (const sheetId of this.getters.getSheetIds()) {
      sheetSizes[sheetId] = {
        rows: this.getters.getNumberRows(sheetId),
        cols: this.getters.getNumberCols(sheetId),
      };
    }
    return new PositionSet(sheetSizes);
  }

  evaluateCells(positions: CellPosition[]) {
    const start = performance.now();
    const rangesToCompute = new RangeSet();
    rangesToCompute.addManyPositions(positions);
    const arrayFormulasPositions = this.getArrayFormulasImpactedByChangesOf(positions);
    rangesToCompute.addMany(this.getCellsDependingOn(rangesToCompute));
    rangesToCompute.addMany(arrayFormulasPositions);
    rangesToCompute.addMany(this.getCellsDependingOn(arrayFormulasPositions));
    this.evaluate(rangesToCompute);
    console.debug("evaluate Cells", performance.now() - start, "ms");
  }

  /**
   * Evaluates the given cells without propagating to their dependents.
   * Used when automatic evaluation is disabled, to show the result of a
   * directly modified cell without triggering a potentially expensive cascade.
   */
  evaluateCellsWithoutCascade(positions: CellPosition[]) {
    const rangesToCompute = new RangeSet();
    rangesToCompute.addManyPositions(positions);
    this.evaluate(rangesToCompute);
  }

  private getArrayFormulasImpactedByChangesOf(positions: Iterable<CellPosition>): RangeSet {
    const impactedRanges = new RangeSet();

    for (const position of positions) {
      const cell = this.getters.getCell(position);
      const arrayFormulaPosition = this.getArrayFormulaSpreadingOn(position);
      if (arrayFormulaPosition !== undefined) {
        // take into account new collisions.
        impactedRanges.addPosition(arrayFormulaPosition);
      }
      if (!cell?.isFormula && !cell?.content) {
        // The previous content could have blocked some array formulas
        impactedRanges.addPosition(position);
      }
    }
    for (const range of [...impactedRanges]) {
      impactedRanges.addMany(this.getArrayFormulasBlockedBy(range.sheetId, range.zone));
    }
    return impactedRanges;
  }

  buildDependencyGraph() {
    this.blockedArrayFormulas = this.createEmptyPositionSet();
    this.spreadingRelations = new SpreadingRelation();
    this.formulaDependencies = lazy(() => {
      const graph = new FormulaDependencyGraph();
      for (const sheetId of this.getters.getSheetIds()) {
        for (const cell of this.getters.getCells(sheetId)) {
          if (cell.isFormula) {
            const cellPosition = this.getters.getCellPosition(cell.id);
            const dependencies = this.getters.clipRangesToSheet(
              cell.compiledFormula.rangeDependencies
            );
            graph.addDependencies(cellPosition, dependencies);
          }
        }
      }
      return graph;
    });
  }

  evaluateAllCells(profiling?: boolean) {
    const start = performance.now();
    this.evaluatedCells = new PositionMap();
    const ranges: BoundedRange[] = [];
    for (const sheetId of this.getters.getSheetIds()) {
      const zone = this.getters.getSheetZone(sheetId);
      ranges.push({ sheetId, zone });
    }
    this.evaluate(ranges, profiling);
    console.debug("evaluate all cells", performance.now() - start, "ms");
  }

  evaluateFormulaResult(
    sheetId: UID,
    formulaString: string,
    originCellPosition?: CellPosition
  ): FunctionResultObject | Matrix<FunctionResultObject> {
    const compiledFormula = CompiledFormula.Compile(formulaString, sheetId, this.getters);
    this.updateCompilationParametersForIsolatedFormula(originCellPosition);
    return this.evaluateCompiledFormula(sheetId, compiledFormula);
  }

  evaluateCompiledFormula(
    sheetId: UID,
    compiledFormula: CompiledFormula,
    getContextualSymbolValue?: GetSymbolValue
  ) {
    try {
      const result = updateEvalContextAndExecute(
        compiledFormula,
        this.compilationParams,
        sheetId,
        this.buildSafeGetSymbolValue(getContextualSymbolValue),
        this.compilationParams.evalContext.__originCellPosition
      );
      if (isMatrix(result)) {
        return matrixMap(result, nullValueToZeroValue);
      }
      return nullValueToZeroValue(result);
    } catch (error) {
      return handleError(error, "");
    }
  }

  /**
   * Return the position of formulas blocked by the given positions
   * as well as all their dependencies.
   */
  private getArrayFormulasBlockedBy(sheetId: UID, zone: Zone): RangeSet {
    const arrayFormulaPositions = new RangeSet();
    const arrayFormulas = this.spreadingRelations.searchFormulaPositionsSpreadingOn(sheetId, zone);
    arrayFormulaPositions.addManyPositions(arrayFormulas);
    const spilledPositions = [...arrayFormulas].filter(
      (position) => !this.blockedArrayFormulas.has(position)
    );
    if (spilledPositions.length) {
      // ignore the formula spreading on the position. Keep only the blocked ones
      arrayFormulaPositions.deleteManyPositions(spilledPositions);
    }
    arrayFormulaPositions.addMany(this.getCellsDependingOn(arrayFormulaPositions));
    return arrayFormulaPositions;
  }

  private nextRangesToUpdate = new RangeSet();
  private cellsBeingComputed = new Set<number>();
  private symbolsBeingComputed = new Set<string>();

  private evaluate(ranges: Iterable<BoundedRange>, profiling?: boolean) {
    if (profiling) {
      this.perfProfile = undefined;
    }
    this.cellsBeingComputed = new Set<number>();
    this.nextRangesToUpdate = new RangeSet(ranges);
    const evaluatedRanges: Record<string, number> = {};
    let maxIterationReached = false;
    const functionTimingLog = profiling ? [] : undefined;
    while (!this.nextRangesToUpdate.isEmpty() && !maxIterationReached) {
      this.updateCompilationParameters(functionTimingLog);
      const ranges = [...this.nextRangesToUpdate];
      this.nextRangesToUpdate.clear();
      this.clearEvaluatedRanges(ranges);
      for (const range of ranges) {
        const { left, bottom, right, top } = range.zone;
        let zoneIsEntirelyEvaluated = true;
        for (let col = left; col <= right; col++) {
          for (let row = top; row <= bottom; row++) {
            const position = { sheetId: range.sheetId, col, row };
            if (this.nextRangesToUpdate.hasPosition(position)) {
              zoneIsEntirelyEvaluated = false;
              continue;
            }
            const evaluatedCell = this.computeCell(position);
            if (evaluatedCell.value !== null || evaluatedCell.format !== undefined) {
              this.evaluatedCells.set(position, evaluatedCell);
            }
          }
        }
        if (zoneIsEntirelyEvaluated) {
          const rangeString = `${range.sheetId}-${left}-${right}-${top}-${bottom}`;
          evaluatedRanges[rangeString] ??= 0;
          evaluatedRanges[rangeString] += 1;
          if (evaluatedRanges[rangeString] >= MAX_ITERATION) {
            maxIterationReached = true;
          }
        }
      }
      onIterationEndEvaluationRegistry.getAll().forEach((callback) => callback(this.getters));
    }
    if (maxIterationReached) {
      console.warn("Maximum iteration reached while evaluating cells");
    }
    if (profiling) {
      this.processPerfProfile();
    }
  }

  private clearEvaluatedRanges(ranges: Iterable<BoundedRange>) {
    for (const range of ranges) {
      const { left, bottom, right, top } = range.zone;
      for (let col = left; col <= right; col++) {
        for (let row = top; row <= bottom; row++) {
          this.evaluatedCells.delete({ sheetId: range.sheetId, col, row });
        }
      }
    }
  }

  private computeCell(position: CellPosition): EvaluatedCell {
    const evaluation = this.evaluatedCells.get(position);
    if (evaluation) {
      return evaluation; // already computed
    }

    if (!this.blockedArrayFormulas.has(position)) {
      this.invalidateSpreading(position);
    }

    if (this.spreadingRelations.isArrayFormula(position)) {
      this.spreadingRelations.removeNode(position);
    }

    const cell = this.getters.getCell(position);
    if (cell === undefined) {
      // EMPTY_CELL is the only evaluatedCell without position (for perf reasons). We need to add it here.
      return { ...EMPTY_CELL, position };
    }

    const cellId = cell.id;
    try {
      if (this.cellsBeingComputed.has(cellId)) {
        return errorCycleCell(position);
      }
      this.cellsBeingComputed.add(cellId);
      return cell.isFormula
        ? this.computeFormulaCell(position, cell)
        : evaluateLiteral(
            cell,
            {
              format: this.getters.getCellFormat(position),
              locale: this.getters.getLocale(),
            },
            position
          );
    } catch (e) {
      e.value = e?.value || CellErrorType.GenericError;
      e.message = e?.message || implementationErrorMessage;
      e.origin = position;
      e.errorOriginPosition = e?.errorOriginPosition;
      return createEvaluatedCell(e, this.getters.getLocale(), position);
    } finally {
      this.cellsBeingComputed.delete(cellId);
    }
  }

  private computeAndSave(position: CellPosition) {
    const evaluatedCell = this.computeCell(position);
    if (!this.evaluatedCells.has(position)) {
      this.evaluatedCells.set(position, evaluatedCell);
    }
    return evaluatedCell;
  }

  private computeFormulaCell(formulaPosition: CellPosition, cellData: FormulaCell): EvaluatedCell {
    const formulaReturn = updateEvalContextAndExecute(
      cellData.compiledFormula,
      this.compilationParams,
      formulaPosition.sheetId,
      this.buildSafeGetSymbolValue(),
      formulaPosition
    );
    const timeLog = this.compilationParams.evalContext.__timingEntries;

    // Only measure post-processing for array formulas (spreading values). Scalar formulas have negligible post-processing.
    const start = timeLog && isMatrix(formulaReturn) ? performance.now() : 0;
    const evaluatedCell = this.postProcessFormulaReturn(formulaPosition, cellData, formulaReturn);
    if (start) {
      // The last entry is the outermost function of this formula (e.g. MUNIT in =MUNIT(MAX(A1, A5))).
      // because arguments (including dependency evaluations) resolve
      // before the function call, so the outermost function always logs last.
      const lastEntry = timeLog?.at(-1);
      if (
        lastEntry &&
        // For formulas without function calls (e.g. =A1:B2), it may be empty or the last entry
        // belongs to a different cell.
        lastEntry.position.sheetId === formulaPosition.sheetId &&
        lastEntry.position.col === formulaPosition.col &&
        lastEntry.position.row === formulaPosition.row
      ) {
        lastEntry.time += performance.now() - start;
      }
    }
    return evaluatedCell;
  }

  private postProcessFormulaReturn(
    formulaPosition: CellPosition,
    cellData: FormulaCell,
    formulaReturn: FunctionResultObject | Matrix<FunctionResultObject>
  ) {
    const cellFormat = this.getters.getCellFormat(formulaPosition);
    if (!isMatrix(formulaReturn)) {
      const evaluatedCell = createEvaluatedCell(
        validateNumberValue(formulaReturn),
        this.getters.getLocale(),
        formulaPosition,
        cellFormat,
        formulaPosition
      );
      if (evaluatedCell.type === CellValueType.error) {
        evaluatedCell.errorOriginPosition = formulaReturn.errorOriginPosition ?? formulaPosition;
      }
      return evaluatedCell;
    }

    this.assertSheetHasEnoughSpaceToSpreadFormulaResult(formulaPosition, formulaReturn);

    const nbColumns = formulaReturn.length;
    const nbRows = formulaReturn[0].length;
    if (nbRows === 0) {
      // empty matrix
      return createEvaluatedCell(
        { value: 0 },
        this.getters.getLocale(),
        formulaPosition,
        cellFormat
      );
    }
    if (nbRows === 1 && nbColumns === 1) {
      // single value matrix
      return createEvaluatedCell(
        validateNumberValue(formulaReturn[0][0]),
        this.getters.getLocale(),
        formulaPosition,
        cellFormat
      );
    }

    const resultZone = {
      top: formulaPosition.row,
      bottom: formulaPosition.row + nbRows - 1,
      left: formulaPosition.col,
      right: formulaPosition.col + nbColumns - 1,
    };
    this.spreadingRelations.addRelation({ resultZone, arrayFormulaPosition: formulaPosition });
    this.assertNoMergedCellsInSpreadZone(formulaPosition, formulaReturn);
    forEachSpreadPositionInMatrix(nbColumns, nbRows, this.checkCollision(formulaPosition));
    forEachSpreadPositionInMatrix(
      nbColumns,
      nbRows,
      // thanks to the isMatrix check above, we know that formulaReturn is MatrixFunctionReturn
      this.spreadValues(formulaPosition, formulaReturn)
    );
    this.invalidatePositionsDependingOnSpread(formulaPosition.sheetId, resultZone);
    return createEvaluatedCell(
      validateNumberValue(formulaReturn[0][0]),
      this.getters.getLocale(),
      formulaPosition,
      cellFormat
    );
  }

  private invalidatePositionsDependingOnSpread(sheetId: UID, resultZone: Zone) {
    // the result matrix is split in 2 zones to exclude the array formula position
    const invalidatedPositions = this.getCellsDependingOn(
      excludeTopLeft(resultZone).map((zone) => ({ sheetId, zone }))
    );
    invalidatedPositions.delete({ sheetId, zone: resultZone });
    this.nextRangesToUpdate.addMany(invalidatedPositions);
  }

  private assertSheetHasEnoughSpaceToSpreadFormulaResult(
    { sheetId, col, row }: CellPosition,
    matrixResult: Matrix<FunctionResultObject>
  ) {
    const numberOfCols = this.getters.getNumberCols(sheetId);
    const numberOfRows = this.getters.getNumberRows(sheetId);
    const enoughCols = col + matrixResult.length <= numberOfCols;
    const enoughRows = row + matrixResult[0].length <= numberOfRows;

    if (enoughCols && enoughRows) {
      return;
    }

    throw new SplillBlockedError(_t("Result couldn't be automatically expanded."));
  }

  private assertNoMergedCellsInSpreadZone(
    { sheetId, col, row }: CellPosition,
    matrixResult: Matrix<FunctionResultObject>
  ) {
    const mergedCells = this.getters.getMergesInZone(sheetId, {
      top: row,
      bottom: row + matrixResult[0].length - 1,
      left: col,
      right: col + matrixResult.length - 1,
    });

    if (mergedCells.length === 0) {
      return;
    }

    throw new SplillBlockedError(
      _t("Merged cells found in the spill zone. Please unmerge cells before using array formulas.")
    );
  }

  private checkCollision(formulaPosition: CellPosition): (i: number, j: number) => void {
    const { sheetId, col, row } = formulaPosition;
    const checkCollision = (i: number, j: number) => {
      const position = { sheetId: sheetId, col: i + col, row: j + row };
      const rawCell = this.getters.getCell(position);
      if (
        rawCell?.isFormula ||
        rawCell?.content ||
        this.getters.getEvaluatedCell(position).type !== CellValueType.empty
      ) {
        this.blockedArrayFormulas.add(formulaPosition);
        throw new SplillBlockedError(
          _t("Array result was not expanded because it would overwrite data."),
          position
        );
      }
      this.blockedArrayFormulas.delete(formulaPosition);
    };
    return checkCollision;
  }

  private spreadValues(
    { sheetId, col, row }: CellPosition,
    matrixResult: Matrix<FunctionResultObject>
  ): (i: number, j: number) => void {
    const spreadValues = (i: number, j: number) => {
      const position = { sheetId, col: i + col, row: j + row };
      const cellFormat = this.getters.getCellFormat(position);
      const evaluatedCell = createEvaluatedCell(
        validateNumberValue(matrixResult[i][j]),
        this.getters.getLocale(),
        position,
        cellFormat,
        position
      );
      if (evaluatedCell.type === CellValueType.error) {
        evaluatedCell.errorOriginPosition = matrixResult[i][j].errorOriginPosition ?? position;
      }
      this.evaluatedCells.set(position, evaluatedCell);
    };
    return spreadValues;
  }

  private invalidateSpreading(position: CellPosition) {
    const zone = this.spreadingRelations.getArrayResultZone(position);
    if (!zone) {
      return;
    }
    for (let col = zone.left; col <= zone.right; col++) {
      for (let row = zone.top; row <= zone.bottom; row++) {
        const resultPosition = { sheetId: position.sheetId, col, row };
        const cell = this.getters.getCell(resultPosition);
        if (cell?.isFormula || cell?.content) {
          // there's no point at re-evaluating overlapping array formulas,
          // there's still a collision
          continue;
        }
        this.evaluatedCells.delete(resultPosition);
      }
    }
    const sheetId = position.sheetId;
    this.invalidatePositionsDependingOnSpread(sheetId, zone);
    this.nextRangesToUpdate.addMany(this.getArrayFormulasBlockedBy(sheetId, zone));
  }

  /**
   * Wraps a GetSymbolValue function to add cycle detection
   * and error handling.
   */
  private buildSafeGetSymbolValue(getContextualSymbolValue?: GetSymbolValue): GetSymbolValue {
    const getSymbolValue = (symbolName: string, isRange: boolean) => {
      if (this.symbolsBeingComputed.has(symbolName)) {
        return errorCycleCell(this.compilationParams.evalContext.__originCellPosition);
      }
      this.symbolsBeingComputed.add(symbolName);
      try {
        const namedRange = this.getters.getNamedRange(symbolName);
        if (namedRange) {
          const ctx = this.compilationParams.evalContext;
          ctx.__originCellPosition
            ? this.addDependencies(ctx.__originCellPosition, [namedRange.range])
            : this.computeDependencies([namedRange.range]);

          const isMultiCellZone = getZoneArea(namedRange.range.zone) > 1;
          return isMultiCellZone || isRange
            ? this.compilationParams.ensureRange(namedRange.range)
            : this.compilationParams.referenceDenormalizer(namedRange.range);
        }
        const symbolValue = getContextualSymbolValue?.(symbolName, isRange);
        if (symbolValue) {
          return symbolValue;
        }
        return new BadExpressionError(_t("Invalid formula"));
      } finally {
        this.symbolsBeingComputed.delete(symbolName);
      }
    };
    return getSymbolValue;
  }

  private processPerfProfile() {
    const timingEntries = this.compilationParams.evalContext.__timingEntries ?? [];

    const byFunction = Object.groupBy(timingEntries, (e) => e.functionName);
    let totalTime = 0;
    const rangeTimings: RangeTiming[] = [];
    for (const rawName in byFunction) {
      const functionName = FUNCTION_TO_OPERATOR[rawName] ?? rawName;
      const byFingerprint = Object.groupBy(byFunction[rawName]!, ({ position }) => {
        const cell = this.getters.getCell(position);
        const fingerprint = cell ? this.getters.getCellFingerprint(cell) : undefined;
        return fingerprint ?? "";
      });
      for (const fingerprint in byFingerprint) {
        for (const entry of this.mergeIntoRangeTimings(functionName, byFingerprint[fingerprint]!)) {
          totalTime += entry.time;
          rangeTimings.push(entry);
        }
      }
    }

    rangeTimings.sort((a, b) => b.time - a.time);
    this.perfProfile = {
      totalTime,
      totalCells: this.evaluatedCells.keys().length,
      totalFunctionCalls: timingEntries.length,
      entries: rangeTimings,
    };
  }

  /**
   * Merge timing entries into RangeTimings by combining adjacent cell
   * positions into contiguous ranges and summing their times.
   */
  private mergeIntoRangeTimings(
    functionName: string,
    entries: FunctionTimingEntry[]
  ): RangeTiming[] {
    const timeByPosition = new PositionMap<number>();
    const positions = new RangeSet();
    for (const { position, time } of entries) {
      timeByPosition.set(position, (timeByPosition.get(position) ?? 0) + time);
      positions.addPosition(position);
    }
    const rangeTimings: RangeTiming[] = [];
    for (const { sheetId, zone } of positions) {
      let time = 0;
      for (let col = zone.left; col <= zone.right; col++) {
        for (let row = zone.top; row <= zone.bottom; row++) {
          time += timeByPosition.get({ sheetId, col, row }) ?? 0;
        }
      }
      rangeTimings.push({
        functionName,
        range: this.getters.getRangeFromZone(sheetId, zone),
        time,
      });
    }
    return rangeTimings;
  }

  // ----------------------------------------------------------
  //                 COMMON FUNCTIONALITY
  // ----------------------------------------------------------

  private getDirectDependencies(position: CellPosition): Range[] {
    const cell = this.getters.getCell(position);
    if (!cell?.isFormula) {
      return [];
    }
    return cell.compiledFormula.rangeDependencies;
  }

  private getCellsDependingOn(ranges: Iterable<BoundedRange>): RangeSet {
    return this.formulaDependencies().getCellsDependingOn(ranges, this.nextRangesToUpdate);
  }
}

function forEachSpreadPositionInMatrix(
  nbColumns: number,
  nbRows: number,
  callback: (i: number, j: number) => void
) {
  for (let i = 0; i < nbColumns; ++i) {
    for (let j = 0; j < nbRows; ++j) {
      if (i === 0 && j === 0) {
        continue;
      }
      callback(i, j);
    }
  }
}

/**
 * This function replaces null payload values with 0.
 * This aids in the UI by ensuring that a cell with a
 * formula referencing an empty cell displays a value (0),
 * rather than appearing empty. This indicates that the
 * cell is the result of a non-empty content.
 */
function nullValueToZeroValue(functionResult: FunctionResultObject): FunctionResultObject {
  if (functionResult.value === null || functionResult.value === undefined) {
    // 'functionResult.value === undefined' is supposed to never happen, it's a safety net for javascript use
    return { ...functionResult, value: 0 };
  }
  return functionResult;
}

function validateNumberValue(data: FunctionResultObject): FunctionResultObject {
  return typeof data.value === "number" && Math.abs(data.value) > Number.MAX_VALUE
    ? new NumberTooLargeError()
    : nullValueToZeroValue(data);
}

export function updateEvalContextAndExecute(
  compiledFormula: CompiledFormula,
  compilationParams: CompilationParameters,
  sheetId: UID,
  getSymbolValue: GetSymbolValue,
  originCellPosition: CellPosition | undefined
) {
  const evalContext = compilationParams.evalContext;
  const currentCellPosition = evalContext.__originCellPosition;
  const currentSheetId = evalContext.__originSheetId;

  evalContext.__originCellPosition = originCellPosition;
  evalContext.__originSheetId = sheetId;
  const result = compiledFormula.execute(
    compiledFormula.rangeDependencies,
    compilationParams.referenceDenormalizer,
    compilationParams.ensureRange,
    getSymbolValue,
    evalContext,
    compiledFormula.computeFunctions
  );
  evalContext.__originCellPosition = currentCellPosition;
  evalContext.__originSheetId = currentSheetId;
  return result;
}

function errorCycleCell(position?: CellPosition) {
  return createEvaluatedCell(
    { ...new CircularDependencyError(), origin: undefined },
    undefined,
    position
  );
}