1package io.protobase.f7.spreadsheet;
  2
  3import com.google.common.collect.ImmutableMap;
  4import io.protobase.f7.antlr.F7Lexer;
  5import io.protobase.f7.antlr.F7Parser;
  6import io.protobase.f7.errors.F7Exception;
  7import io.protobase.f7.errors.ParseException;
  8import io.protobase.f7.errors.RefException;
  9import io.protobase.f7.errors.ValueException;
 10import io.protobase.f7.formulas.FormulaCaller;
 11import io.protobase.f7.models.Cell;
 12import io.protobase.f7.models.CellQuery;
 13import io.protobase.f7.models.ColumnRowKey;
 14import io.protobase.f7.models.ErrorNode;
 15import io.protobase.f7.models.Grid;
 16import io.protobase.f7.models.GridColumnRowKey;
 17import io.protobase.f7.models.Node;
 18import io.protobase.f7.transpiler.TranspilationVisitor;
 19import io.protobase.f7.utils.Converters;
 20import org.antlr.v4.runtime.CharStreams;
 21import org.antlr.v4.runtime.CommonTokenStream;
 22import org.antlr.v4.runtime.misc.ParseCancellationException;
 23
 24import java.io.ByteArrayInputStream;
 25import java.io.IOException;
 26import java.nio.charset.StandardCharsets;
 27import java.util.HashMap;
 28import java.util.Iterator;
 29import java.util.Map;
 30import java.util.Optional;
 31import java.util.Stack;
 32
 33/**
 34 * Execute F7 code in the context of a spreadsheet, storing values in a grid.
 35 */
 36public class SpreadsheetExecutor {
 37  /**
 38   * All bound formulas.
 39   */
 40  private FormulaCaller formulaCaller;
 41
 42  /**
 43   * Stores the cells that we've looked up so we can keep track of cyclical dependencies between cells.
 44   */
 45  private Stack<GridColumnRowKey> computationOrderKeyStack = new Stack<>();
 46
 47  /**
 48   * Named grids that will store cells.
 49   */
 50  private Map<String, Worksheet> worksheets;
 51
 52  /**
 53   * Named variables available to the spreadsheet.
 54   */
 55  private Map<String, Node> variables;
 56
 57  /**
 58   * Private constructor that accepts worksheets.
 59   *
 60   * @param worksheets - of raw cell values.
 61   */
 62  private SpreadsheetExecutor(Map<String, Worksheet> worksheets, Map<String, String> namedRanges) {
 63    // Set worksheets. These are what we'll be running.
 64    this.worksheets = worksheets;
 65
 66    // Build variables, overriding with defaults.
 67    ImmutableMap.Builder<String, Node> variablesBuilder = ImmutableMap.builder();
 68    for (Map.Entry<String, String> namedRangeEntry : namedRanges.entrySet()) {
 69      String name = namedRangeEntry.getKey().toUpperCase();
 70      String rangeString = namedRangeEntry.getValue();
 71      variablesBuilder.put(name, this.parseNamedRange(rangeString));
 72    }
 73    variables = variablesBuilder.build();
 74
 75    // Bind formula caller.
 76    this.formulaCaller = new FormulaCaller(this::lookup, this::collateralLookup);
 77  }
 78
 79  /**
 80   * Utility to convert a string input to tokens that the parser can read.
 81   *
 82   * @param input - F7 code.
 83   * @return token stream.
 84   * @throws IOException - if there's a problem reading the stream.
 85   */
 86  private static CommonTokenStream stringToTokens(String input) throws IOException {
 87    return new CommonTokenStream(new F7Lexer(CharStreams.fromStream(
 88        new ByteArrayInputStream(input.getBytes(StandardCharsets.UTF_8)), StandardCharsets.UTF_8)));
 89  }
 90
 91  /**
 92   * Start a builder.
 93   *
 94   * @return builder.
 95   */
 96  public static Builder builder() {
 97    return new Builder();
 98  }
 99
100  /**
101   * Parse a range to node for execution.
102   *
103   * @param range - range string
104   * @return range node.
105   */
106  private Node parseNamedRange(String range) {
107    try {
108      CommonTokenStream tokens = stringToTokens(range);
109      try {
110        F7Parser parser = new F7Parser(tokens);
111        parser.removeErrorListeners();
112        parser.addErrorListener(new ParseErrorListener());
113        return new TranspilationVisitor().visit(parser.range());
114      } catch (ParseCancellationException parseException) {
115        return new ErrorNode(new ParseException("Parse error"));
116      } catch (F7Exception f7Exception) {
117        return new ErrorNode(f7Exception);
118      }
119    } catch (IOException io) {
120      return new ErrorNode(new ParseException("Parse error"));
121    }
122  }
123
124  /**
125   * If the value passed in is a CellQuery, lookup the value. If not, return value unchanged.
126   *
127   * @param queryOrValue - value that is possibly a range, and should be resolved/looked-up.
128   * @return resolved value or given range if not.
129   */
130  private Object lookup(Object queryOrValue) {
131    if (queryOrValue instanceof CellQuery) {
132      return this.performQuery(((CellQuery) queryOrValue));
133    }
134    return queryOrValue;
135  }
136
137  /**
138   * If the value passed in is a CellQuery, perform collateral lookup. If not return value unchanged.
139   *
140   * @param origin       - origin to use in potential collateral lookup.
141   * @param queryOrValue - query or value.
142   * @return
143   */
144  private Object collateralLookup(GridColumnRowKey origin, Object queryOrValue) {
145    if (queryOrValue instanceof CellQuery) {
146      return this.performCollateralLookup(origin, ((CellQuery) queryOrValue));
147    }
148    return queryOrValue;
149  }
150
151  /**
152   * Run the spreadsheet.
153   */
154  public void execute() {
155    // For each worksheet, iterate through the cells in reverse (bottom to top, right to left), computing the cells.
156    for (Map.Entry<String, Worksheet> entry : worksheets.entrySet()) {
157      String gridName = entry.getKey();
158      Grid<Cell> currentGrid = entry.getValue().getCells();
159      currentGrid.reverseIndexIterator().forEachRemaining(index -> processCell(new GridColumnRowKey(gridName, index)));
160    }
161  }
162
163  /**
164   * Process a single cell, setting the raw value if the cell does not contain a formula, or computing the cell's
165   * formula if it has one.
166   *
167   * @param key - where this cell will be stored in the grid.
168   */
169  private void processCell(GridColumnRowKey key) {
170    Optional<Cell> cell = getCell(key.getGridIndex(), key.toColumnRowKey());
171    if (cell.isPresent() && !cell.get().isComputed()) {
172      computationOrderKeyStack.push(key);
173      computeCell(key, cell.get().getRawValue());
174      computationOrderKeyStack.pop();
175    }
176  }
177
178  /**
179   * Compute a single cell, recursively computing other cells if necessary, ultimately storing the final cell in the
180   * grid.
181   *
182   * @param key      - where this cell will be stored in the grid.
183   * @param rawInput - cell raw value.
184   */
185  private void computeCell(GridColumnRowKey key, String rawInput) {
186    Worksheet worksheet = worksheets.get(key.getGridIndex());
187    ColumnRowKey columnRowKey = key.toColumnRowKey();
188    F7CodeExecutor codeExecutor = new F7CodeExecutor(variables, this::lookup, this::collateralLookup, formulaCaller);
189    try {
190      Object result = codeExecutor.execute(key, rawInput);
191      if (result instanceof Grid) {
192        try {
193          Grid<Object> gridToProject = Converters.castAsDataGrid(result);
194          checkProjectionValidity(key, gridToProject.getColumnSize(), gridToProject.getRowSize());
195          performProjection(key, gridToProject);
196        } catch (F7Exception exception) {
197          worksheet.setCellComputedValue(columnRowKey, exception);
198        }
199      } else {
200        worksheet.setCellComputedValue(columnRowKey, result);
201      }
202    } catch (F7Exception exception) {
203      worksheet.setCellComputedValue(columnRowKey, exception);
204    }
205  }
206
207  /**
208   * For a given key, project the values onto the grid. This should only be called after the projection validity has
209   * been checked.
210   *
211   * @param origin       - starting value of computed grid.
212   * @param computedGrid - computed grid to project, starting at key.
213   */
214  private void performProjection(GridColumnRowKey origin, Grid<Object> computedGrid) {
215    Worksheet worksheet = worksheets.get(origin.getGridIndex());
216    Iterator<ColumnRowKey> iterator = computedGrid.indexIterator();
217    while (iterator.hasNext()) {
218      ColumnRowKey localKey = iterator.next();
219      Object projectedValue = computedGrid.get(localKey);
220      ColumnRowKey projectedKey = new ColumnRowKey(origin.getColumnIndex() + localKey.getColumnIndex(),
221          origin.getRowIndex() + localKey.getRowIndex());
222      worksheet.setCell(projectedKey, new Cell(projectedValue, origin.toColumnRowKey()));
223    }
224  }
225
226  /**
227   * At a key, for a number of columns and rows, check to ensure that the values we're potentially projecting won't
228   * overwrite existing cell values.
229   *
230   * @param origin  - to start at
231   * @param columns - number of columns forward to project. If it's 1, then we're just projecting to the current key.
232   * @param rows    - number of rows forward to project. If it's 1, then we're just projecting to the current key.
233   */
234  private void checkProjectionValidity(GridColumnRowKey origin, int columns, int rows) {
235    Iterator<ColumnRowKey> iterator = worksheets.get(origin.getGridIndex()).getCells().reverseIndexIterator(
236        origin.getColumnIndex() + columns - 1, origin.getColumnIndex(), origin.getRowIndex() + rows - 1,
237        origin.getRowIndex());
238    while (iterator.hasNext()) {
239      ColumnRowKey scanKey = iterator.next();
240      if (!scanKey.equals(origin.toColumnRowKey())) {
241        Optional<Cell> found = getCell(origin.getGridIndex(), scanKey);
242        if (found.isPresent()) {
243          throw new RefException(String.format("Grid result was not projected because it would overwrite data in %s",
244              scanKey.toString()));
245        }
246      }
247    }
248  }
249
250  /**
251   * Get a cell from the grid.
252   *
253   * @param gridName - name of the grid that holds the cell.
254   * @param key      - grid index of the cell.
255   * @return cell.
256   */
257  public Optional<Cell> getCell(String gridName, ColumnRowKey key) {
258    return Optional.ofNullable(worksheets.get(gridName).getCell(key));
259  }
260
261  /**
262   * Ensure that a worksheet exists, throwing a #REF! error if it does not.
263   *
264   * @param worksheet to check for.
265   */
266  private void checkWorksheetExistence(String worksheet) {
267    if (!worksheets.containsKey(worksheet)) {
268      throw new RefException(String.format("Unresolved grid name '%s'.", worksheet));
269    }
270  }
271
272  /**
273   * Given a query, traverse the entire range, collecting values into a grid. This is a little complex, so here's the
274   * outline of how it works:
275   * <p>
276   * 1) Get the grid from the query. If we don't have a grid we can't proceed.
277   * 2) Get the grid, and build a query that represents the boundaries of the grid.
278   * 3) If the grid boundaries don't intersect the query boundaries, they are disjoint sets. Return empty grid.
279   * 4) Take the input query and constrict it to the size of the grid we're querying.
280   * 5) We now know we're going to be iterating over something. Start iterator, create grid that we'll be building.
281   * 6) For each key of the iterator, make sure we're not in a cycle.
282   * 7) Process the cell - possibly computing it's value if we've not done that yet.
283   * 8) Add the cell to the return grid.
284   * 9) Return the grid.
285   *
286   * @param query - to resolve.
287   * @return grid of values, or single value if we're using a collateral index.
288   */
289  private Grid performQuery(CellQuery query) {
290    String gridName = query.getGrid().orElseThrow(() -> new IllegalStateException("CellQuery does not have name."));
291    checkWorksheetExistence(gridName);
292
293    Grid<Cell> grid = worksheets.get(gridName).getCells();
294    CellQuery gridBoundaries = CellQuery.builder()
295        .columnsBetween(0, grid.getColumnSize())
296        .rowsBetween(0, grid.getRowSize())
297        .build();
298    if (!gridBoundaries.intersects(query)) {
299      return Grid.builder().build();
300    }
301    CellQuery boundedQuery = query.toBounded(grid.getColumnSize(), grid.getRowSize());
302
303    int endColumn = boundedQuery.getEndColumn();
304    int endRow = boundedQuery.getEndRow();
305    int startColumn = boundedQuery.getStartColumn();
306    int startRow = boundedQuery.getStartRow();
307
308    Iterator<ColumnRowKey> iterator = worksheets.get(gridName).getCells().reverseIndexIterator(endColumn,
309        startColumn, endRow, startRow);
310    Grid<Object> rangeGrid = new Grid<>();
311
312    while (iterator.hasNext()) {
313      ColumnRowKey key = iterator.next();
314      if (computationOrderKeyStack.contains(new GridColumnRowKey(gridName, key))) {
315        throw new RefException("Cycle detected.");
316      }
317      processCell(new GridColumnRowKey(gridName, key));
318      Optional<Cell> cell = getCell(gridName, key);
319      if (cell.isPresent()) {
320        rangeGrid.set(key.getColumnIndex() - startColumn, key.getRowIndex() - startRow, cell.get().getComputedValue());
321      } else {
322        rangeGrid.setEmpty(key.getColumnIndex() - startColumn, key.getRowIndex() - startRow);
323      }
324    }
325
326    return rangeGrid;
327  }
328
329  private Object performCollateralLookup(GridColumnRowKey origin, CellQuery query) {
330    String gridName = query.getGrid().orElseThrow(() -> new IllegalStateException("CellQuery does not have name."));
331    checkWorksheetExistence(gridName);
332
333    Grid<Cell> grid = worksheets.get(gridName).getCells();
334    CellQuery gridBoundaries = CellQuery.builder()
335        .columnsBetween(0, grid.getColumnSize())
336        .rowsBetween(0, grid.getRowSize())
337        .build();
338    if (!gridBoundaries.intersects(query)) {
339      return Grid.builder().build();
340    }
341    CellQuery boundedQuery = query.toBounded(grid.getColumnSize(), grid.getRowSize());
342
343    int endColumn = boundedQuery.getEndColumn();
344    int endRow = boundedQuery.getEndRow();
345    int startColumn = boundedQuery.getStartColumn();
346    int startRow = boundedQuery.getStartRow();
347
348    // Case 0: Single value, just return it.
349    if (startColumn == endColumn && startRow == endRow) {
350      GridColumnRowKey key = new GridColumnRowKey(gridName, new ColumnRowKey(startColumn, startRow));
351      return performSingleCellLookup(key);
352    }
353
354    // Case 1: Row-wise - query is a single row. Use column as collateral index.
355    if (startColumn != endColumn && startRow == endRow &&
356        origin.getColumnIndex() >= startColumn && origin.getColumnIndex() <= endColumn) {
357      GridColumnRowKey key = new GridColumnRowKey(gridName, new ColumnRowKey(origin.getColumnIndex(), startRow));
358      return performSingleCellLookup(key);
359    }
360
361    // Case 2: Column-wise - query is single column. Use row as collateral index.
362    if (startColumn == endColumn &&
363        origin.getRowIndex() >= startRow && origin.getRowIndex() <= endRow) {
364      GridColumnRowKey key = new GridColumnRowKey(gridName, new ColumnRowKey(startColumn, origin.getRowIndex()));
365      return performSingleCellLookup(key);
366    }
367
368    // Case 3: Other grid - query is multi-row, multi-column, and other grid. Use both as collateral index.
369    if (origin.getColumnIndex() >= startColumn && origin.getColumnIndex() <= endColumn &&
370        origin.getRowIndex() >= startRow && origin.getRowIndex() <= endRow &&
371        !origin.getGridIndex().equals(query.getGrid().get())) {
372      GridColumnRowKey key = new GridColumnRowKey(gridName, new ColumnRowKey(origin.getColumnIndex(), origin.getRowIndex()));
373      return performSingleCellLookup(key);
374    }
375
376    // Case 4: This grid, and exists. #REF! error - we're looking up the origin.
377    if (origin.getColumnIndex() >= startColumn && origin.getColumnIndex() <= endColumn &&
378        origin.getRowIndex() >= startRow && origin.getRowIndex() <= endRow &&
379        origin.getGridIndex().equals(query.getGrid().get())) {
380      return new RefException("Cycle detected");
381    }
382
383    // Case 5: This grid, not contained. #VALUE! error.
384    return new ValueException("Array value could not be found");
385  }
386
387  private Object performSingleCellLookup(GridColumnRowKey key) {
388    if (computationOrderKeyStack.contains(key)) {
389      throw new RefException("Cycle detected.");
390    }
391    processCell(key);
392    Optional<Cell> cell = getCell(key.getGridIndex(), key.toColumnRowKey());
393    if (cell.isPresent()) {
394      return cell.get().getComputedValue();
395    }
396    return null;
397  }
398
399  /**
400   * Simple way to build an executor.
401   */
402  public static class Builder {
403    Map<String, Grid<Cell>> grids = new HashMap<>();
404    Map<String, String> variables = new HashMap<>();
405
406    public Builder addGrids(Map<String, Grid<Cell>> toAdd) {
407      grids.putAll(toAdd);
408      return this;
409    }
410
411    public Builder addGrid(String name, Map<ColumnRowKey, String> values) {
412      Grid<Cell> grid = new Grid<>();
413      values.forEach((key, value) -> grid.set(key, new Cell(value)));
414      grids.put(name, grid);
415      return this;
416    }
417
418    public Builder addNamedRanges(Map<String, String> ranges) {
419      variables.putAll(ranges);
420      return this;
421    }
422
423    public SpreadsheetExecutor build() {
424      Map<String, Worksheet> worksheets = new HashMap<>();
425      for (Map.Entry<String, Grid<Cell>> entry : grids.entrySet()) {
426        worksheets.put(entry.getKey(), new Worksheet(entry.getKey(), entry.getValue()));
427      }
428      return new SpreadsheetExecutor(worksheets, variables);
429    }
430  }
431}