1import { isNotNull, isNull, isUndefined } from "../utils/Other";
  2import { F7Exception } from "../errors/F7Exception";
  3import { RefException } from "../errors/RefException";
  4import { ValueException } from "../errors/ValueException";
  5import { FormulaCaller } from "../formulas/FormulaCaller";
  6import { ColumnRowKey } from "../models/common/ColumnRowKey";
  7import { Grid } from "../models/common/Grid";
  8import { SheetColumnRowKey } from "../models/common/SheetColumnRowKey";
  9import {
 10  CollateralLookupFunction,
 11  Complex,
 12  Computed,
 13  LookupFunction,
 14} from "../models/common/Types";
 15import { CellQuery } from "../models/nodes/CellQuery";
 16import { Node } from "../models/nodes/Node";
 17import { CellObject, cellObjectFromProjection } from "../spreadsheet/CellObject";
 18import { excelDataTypeFromActualType } from "../spreadsheet/ExcelDataType";
 19import { Ref } from "../spreadsheet/Ref";
 20import { Spreadsheet } from "../spreadsheet/Spreadsheet";
 21import { AlphaUtils } from "../utils/AlphaUtils";
 22import { Converters } from "../utils/Converters";
 23import { Parsers } from "../utils/Parsers";
 24import { CodeExecutor } from "./CodeExecutor";
 25
 26type ComputationMarkerMap = { [a1Key: string]: boolean };
 27
 28/**
 29 * Executes F7 code in the context of a spreadsheet.
 30 */
 31export class Executor {
 32  /**
 33   * Formula caller is the simplest way to bind a lot of formulas to the executor.
 34   */
 35  readonly formulaCaller: FormulaCaller;
 36  /**
 37   * Used to keep track of the computation order, so when we look up a cell, and find that it's not
 38   * been computed, we can compute it. As we repeat this process, if we're ever referencing a cell
 39   * in this stack, we know that there is a circular reference.
 40   */
 41  private computationOrderKeyStack: Array<SheetColumnRowKey> = [];
 42  /**
 43   * Spreadsheet that we're operating on. All interactions go through this.
 44   */
 45  private spreadsheet: Spreadsheet;
 46  /**
 47   * Variables available. Each variable should be represented by a node.
 48   */
 49  private variables: { [index: string]: Node } = {};
 50
 51  /**
 52   * Marks off computation of cells, so we don't have to store it on the cell itself.
 53   */
 54  private computationMarker: { [sheet: string]: ComputationMarkerMap } = {};
 55
 56  /**
 57   * Construct an executor.
 58   */
 59  constructor(spreadsheet: Spreadsheet, customFormulas: { [name: string]: any } = {}) {
 60    this.spreadsheet = spreadsheet;
 61    Object.keys(this.spreadsheet.sheets).forEach((name) => {
 62      const sheet = this.spreadsheet.sheets[name];
 63      const ref = Parsers.parseReferencePair(sheet["!ref"]);
 64      this.computationMarker[name] = Executor.generateMarkerMap(ref);
 65    });
 66    Object.keys(this.spreadsheet.names).forEach((name) => {
 67      const ref = this.spreadsheet.names[name].ref;
 68      this.variables[name] = Parsers.parseNamedRange(ref);
 69    });
 70    this.formulaCaller = new FormulaCaller(this.lookup, this.collateralLookup, customFormulas);
 71  }
 72
 73  private static generateMarkerMap(ref: Ref): ComputationMarkerMap {
 74    const toReturn: ComputationMarkerMap = {};
 75    for (let row = 0; row < ref.endRowIndex; row++) {
 76      for (let column = 0; column < ref.endColumnIndex; column++) {
 77        toReturn[new ColumnRowKey(column, row).toA1()] = false;
 78      }
 79    }
 80    return toReturn;
 81  }
 82
 83  /**
 84   * Run the spreadsheet.
 85   */
 86  execute() {
 87    for (const name of Object.keys(this.spreadsheet.sheets)) {
 88      const sheet = this.spreadsheet.sheets[name];
 89      const ref = Parsers.parseReferencePair(sheet["!ref"]);
 90      for (let row = ref.endRowIndex; row >= 0; row--) {
 91        for (let column = ref.endColumnIndex; column >= 0; column--) {
 92          this.processCell(new SheetColumnRowKey(name, column, row));
 93        }
 94      }
 95    }
 96  }
 97
 98  /**
 99   * Get a cell from the grid.
100   *
101   * @param sheetName - name of the grid that holds the cell.
102   * @param key - grid index of the cell.
103   * @return cell.
104   */
105  getCell(sheetName: string, key: string): CellObject {
106    return this.spreadsheet.getSheetByName(sheetName).getCell(key);
107  }
108
109  getSheet(name: string) {
110    return this.spreadsheet.getSheetByName(name);
111  }
112
113  /**
114   * If the value passed in is a CellQuery, lookup the value. If not, return value unchanged.
115   *
116   * @param queryOrValue - value that is possibly a range, and should be resolved/looked-up.
117   * @return resolved value or given range if not.
118   */
119  private lookup: LookupFunction = (queryOrValue: Complex) => {
120    if (queryOrValue instanceof CellQuery) {
121      return this.performQuery(queryOrValue as CellQuery);
122    }
123    return queryOrValue;
124  };
125
126  /**
127   * If the value passed in is a CellQuery, perform collateral lookup. If not return value unchanged.
128   *
129   * @param origin       - origin to use in potential collateral lookup.
130   * @param queryOrValue - query or value.
131   * @return
132   */
133  private collateralLookup: CollateralLookupFunction = (
134    origin: SheetColumnRowKey,
135    queryOrValue: Complex
136  ) => {
137    if (queryOrValue instanceof CellQuery) {
138      return this.performCollateralLookup(origin, queryOrValue as CellQuery);
139    }
140    return queryOrValue;
141  };
142
143  /**
144   * Process a single cell, setting the user entered value if the cell does not contain a formula, or computing the
145   * cell's formula if it has one.
146   *
147   * @param key - where this cell will be stored in the grid.
148   */
149  private processCell(key: SheetColumnRowKey) {
150    const a1Key = AlphaUtils.oneIndexedNumberToLetter(key.column + 1) + `${key.row + 1}`;
151    const cell = this.getCell(key.sheet, a1Key);
152    if (isNotNull(cell) && !this.hasCellBeenComputed(key)) {
153      this.computationOrderKeyStack.push(key);
154      this.computeCell(key, cell);
155      this.computationOrderKeyStack.pop();
156    }
157  }
158
159  /**
160   * Has the cell at this location been computed?
161   * @param key of cell
162   */
163  private hasCellBeenComputed(key: SheetColumnRowKey) {
164    return this.computationMarker[key.sheet][key.toA1()] || false;
165  }
166
167  /**
168   * Mark the cell at this location as computed.
169   * @param key of cell.
170   */
171  private markCellAsComputed(key: SheetColumnRowKey) {
172    return (this.computationMarker[key.sheet][key.toA1()] = true);
173  }
174
175  /**
176   * Compute a single cell, recursively computing other cells if necessary, ultimately storing the final cell in the
177   * grid.
178   *
179   * @param key - where this cell will be stored in the grid.
180   * @param cell - cell to compute.
181   */
182  private computeCell(key: SheetColumnRowKey, cell: CellObject) {
183    const sheet = this.spreadsheet.getSheetByName(key.sheet);
184    const columnRowKey = key.toColumnRowKey();
185    const a1 = columnRowKey.toA1();
186    const codeExecutor = new CodeExecutor(
187      this.variables,
188      this.lookup,
189      this.collateralLookup,
190      this.formulaCaller
191    );
192    try {
193      const result = codeExecutor.execute(key, cell);
194      if (result instanceof Grid) {
195        try {
196          const gridToProject = <Grid<Computed>>result;
197          this.checkProjectionValidity(key, gridToProject.getColumns(), gridToProject.getRows());
198          this.performProjection(key, gridToProject);
199        } catch (exception) {
200          sheet[a1] = {
201            ...sheet[a1],
202            t: "e",
203            v: Converters.castAsF7Exception(exception),
204          };
205          this.markCellAsComputed(key);
206        }
207      } else {
208        sheet[a1] = {
209          ...sheet[a1],
210          t: excelDataTypeFromActualType(result),
211          v: result,
212        };
213        this.markCellAsComputed(key);
214      }
215    } catch (exception) {
216      sheet[a1] = {
217        ...sheet[a1],
218        t: "e",
219        v: Converters.castAsF7Exception(exception),
220      };
221      this.markCellAsComputed(key);
222    }
223  }
224
225  /**
226   * For a given key, project the values onto the grid. This should only be called after the projection validity has
227   * been checked.
228   *
229   * @param origin - starting value of computed grid.
230   * @param computedGrid - computed grid to project, starting at key.
231   */
232  private performProjection(origin: SheetColumnRowKey, computedGrid: Grid<Computed>) {
233    const sheet = this.spreadsheet.getSheetByName(origin.sheet);
234    for (let row = computedGrid.getRows() - 1; row >= 0; row--) {
235      for (let column = computedGrid.getColumns() - 1; column >= 0; column--) {
236        const projectedValue = computedGrid.get(column, row);
237        const projectedKey = new ColumnRowKey(origin.column + column, origin.row + row);
238        sheet.setCell(projectedKey.toA1(), cellObjectFromProjection(projectedValue as any));
239        this.markCellAsComputed(SheetColumnRowKey.from(origin.sheet, projectedKey));
240      }
241    }
242  }
243
244  /**
245   * At a key, for a number of columns and rows, check to ensure that the values we're potentially projecting won't
246   * overwrite existing cell values.
247   *
248   * @param origin - to start at
249   * @param columns - number of columns forward to project. If it's 1, then we're just projecting to the current key.
250   * @param rows - number of rows forward to project. If it's 1, then we're just projecting to the current key.
251   */
252  private checkProjectionValidity(origin: SheetColumnRowKey, columns: number, rows: number) {
253    const highColumnIndex = origin.column + columns - 1;
254    const lowColumnIndex = origin.column;
255    const highRowIndex = origin.row + rows - 1;
256    const lowRowIndex = origin.row;
257    const sheet = this.spreadsheet.getSheetByName(origin.sheet);
258    const gridBoundaries = Parsers.parseReferencePair(sheet["!ref"]);
259    if (
260      highColumnIndex > gridBoundaries.endColumnIndex ||
261      highRowIndex > gridBoundaries.endRowIndex
262    ) {
263      throw new RefException(`Result was not projected because it is out of range.`);
264    }
265    for (let row = highRowIndex; row >= lowRowIndex; row--) {
266      for (let column = highColumnIndex; column >= lowColumnIndex; column--) {
267        const key = new ColumnRowKey(column, row);
268        if (!key.equals(origin.toColumnRowKey())) {
269          const a1Key = AlphaUtils.oneIndexedNumberToLetter(key.column + 1) + `${key.row + 1}`;
270          const found = this.getCell(origin.sheet, a1Key);
271          if (isNotNull(found) && isNotNull(found.v) && isNotNull(found.w)) {
272            throw new RefException(
273              `Result was not projected because it would overwrite data in ${a1Key}`
274            );
275          }
276        }
277      }
278    }
279  }
280
281  /**
282   * Ensure that a sheet exists, throwing a #REF! error if it does not.
283   *
284   * @param sheetTitle to check for.
285   */
286  private checkSheetExistence(sheetTitle: string) {
287    const sheet = this.spreadsheet.getSheetByName(sheetTitle);
288    if (isUndefined(sheet)) {
289      throw new RefException(`Unresolved sheet name '${sheet}'.`);
290    }
291  }
292
293  /**
294   * Given a query, traverse the entire range, collecting values into a grid. This is a little complex, so here's the
295   * outline of how it works:
296   *
297   * 1) Get the grid from the query. If we don't have a grid we can't proceed.
298   * 2) Get the grid, and build a query that represents the boundaries of the grid.
299   * 3) If the grid boundaries don't intersect the query boundaries, they are disjoint sets. Return empty grid.
300   * 4) Take the input query and constrict it to the size of the grid we're querying.
301   * 5) We now know we're going to be iterating over something. Start iterator, create grid that we'll be building.
302   * 6) For each key of the iterator, make sure we're not in a cycle.
303   * 7) Process the cell - possibly computing it's value if we've not done that yet.
304   * 8) Add the cell to the return grid.
305   * 9) Return the grid.
306   *
307   * @param query - to resolve.
308   * @return grid of values, or single value if we're using a collateral index.
309   */
310  private performQuery(query: CellQuery): string | number | CellQuery | F7Exception | Grid<any> {
311    const sheetName = query.getFormattedSheetName();
312    if (isNull(sheetName) || isUndefined(sheetName)) {
313      throw new Error("CellQuery does not have name.");
314    }
315    this.checkSheetExistence(sheetName);
316
317    const sheet = this.spreadsheet.getSheetByName(sheetName);
318    const gridBoundaries = Parsers.parseReferencePair(sheet["!ref"]);
319    const boundedQuery = query.toBounded(gridBoundaries.endColumnIndex, gridBoundaries.endRowIndex);
320
321    const endColumn = boundedQuery.columns.upperEndpoint();
322    const endRow = boundedQuery.rows.upperEndpoint();
323    const startColumn = boundedQuery.columns.lowerEndpoint();
324    const startRow = boundedQuery.rows.lowerEndpoint();
325    const rangeGrid = new Grid(0, 0);
326
327    for (let row = endRow; row >= startRow; row--) {
328      for (let column = endColumn; column >= startColumn; column--) {
329        const key = new ColumnRowKey(column, row);
330        const sheetKey = SheetColumnRowKey.from(sheetName, key);
331        if (this.computationOrderKeyStack.findIndex((i) => sheetKey.equals(i)) > -1) {
332          throw new RefException("Cycle detected.");
333        }
334        this.processCell(SheetColumnRowKey.from(sheetName, key));
335        const a1Key = AlphaUtils.oneIndexedNumberToLetter(key.column + 1) + `${key.row + 1}`;
336        const cell = this.getCell(sheetName, a1Key);
337        if (isNotNull(cell)) {
338          rangeGrid.set(key.column - startColumn, key.row - startRow, cell.v);
339        } else {
340          rangeGrid.setNull(key.column - startColumn, key.row - startRow);
341        }
342      }
343    }
344
345    return rangeGrid;
346  }
347
348  /**
349   * A collateral lookup is when a cell uses a query of a parallel range in only one dimension.
350   * @param origin - origin cell.
351   * @param query - cell query.
352   */
353  private performCollateralLookup(origin: SheetColumnRowKey, query: CellQuery): any {
354    const sheetName = query.getFormattedSheetName();
355    if (isNull(sheetName) || isUndefined(sheetName)) {
356      throw new Error("CellQuery does not have name.");
357    }
358    this.checkSheetExistence(sheetName);
359    const sheet = this.spreadsheet.getSheetByName(sheetName);
360    const gridBoundaries = Parsers.parseReferencePair(sheet["!ref"]);
361    const boundedQuery = query.toBounded(gridBoundaries.endColumnIndex, gridBoundaries.endRowIndex);
362
363    const endColumn = boundedQuery.columns.upperEndpoint();
364    const endRow = boundedQuery.rows.upperEndpoint();
365    const startColumn = boundedQuery.columns.lowerEndpoint();
366    const startRow = boundedQuery.rows.lowerEndpoint();
367
368    // Case 0: Single value, just return it.
369    if (startColumn == endColumn && startRow == endRow) {
370      const key = SheetColumnRowKey.from(sheetName, new ColumnRowKey(startColumn, startRow));
371      return this.performSingleCellLookup(key);
372    }
373
374    // Case 1: Row-wise - query is a single row. Use column as collateral index.
375    if (
376      startColumn != endColumn &&
377      startRow == endRow &&
378      origin.column >= startColumn &&
379      origin.column <= endColumn
380    ) {
381      const key = SheetColumnRowKey.from(sheetName, new ColumnRowKey(origin.column, startRow));
382      return this.performSingleCellLookup(key);
383    }
384
385    // Case 2: Column-wise - query is single column. Use row as collateral index.
386    if (startColumn == endColumn && origin.row >= startRow && origin.row <= endRow) {
387      const key = SheetColumnRowKey.from(sheetName, new ColumnRowKey(startColumn, origin.row));
388      return this.performSingleCellLookup(key);
389    }
390
391    // Case 3: Other grid - query is multi-row, multi-column, and other grid. Use both as collateral index.
392    if (
393      origin.column >= startColumn &&
394      origin.column <= endColumn &&
395      origin.row >= startRow &&
396      origin.row <= endRow &&
397      origin.sheet !== query.getFormattedSheetName()
398    ) {
399      const key = SheetColumnRowKey.from(sheetName, new ColumnRowKey(origin.column, origin.row));
400      return this.performSingleCellLookup(key);
401    }
402
403    // Case 4: This grid, and exists. #REF! error - we're looking up the origin.
404    if (
405      origin.column >= startColumn &&
406      origin.column <= endColumn &&
407      origin.row >= startRow &&
408      origin.row <= endRow &&
409      origin.sheet === query.getFormattedSheetName()
410    ) {
411      return new RefException("Cycle detected");
412    }
413
414    // Case 5: This grid, not contained. #VALUE! error.
415    return new ValueException("Array value could not be found");
416  }
417
418  /**
419   * Lookup a single cell by key, potentially processing it.
420   * @param key - of cell.
421   */
422  private performSingleCellLookup(key: SheetColumnRowKey) {
423    if (this.computationOrderKeyStack.findIndex((i) => key.equals(i)) > -1) {
424      throw new RefException("Cycle detected.");
425    }
426    this.processCell(key);
427    const a1Key = AlphaUtils.oneIndexedNumberToLetter(key.column + 1) + `${key.row + 1}`;
428    const cell = this.getCell(key.sheet, a1Key);
429    if (isNotNull(cell)) {
430      return cell.v;
431    }
432    return null;
433  }
434}