cpp-spreadsheet

Учебный проект: электронная таблица

Mini Excel Spreadsheet Engine

C++ проект: движок электронной таблицы с поддержкой формул, ссылок между ячейками, графа зависимостей и кэширования.

Проект реализует упрощённую модель Excel с формулами, AST и системой пересчёта зависимых ячеек.

---

Состав проекта

В репозитории находятся следующие основные файлы:

common.h
structures.cpp

formula.h
formula.cpp

FormulaAST.h
FormulaAST.cpp
Formula.g4

cell.h
cell.cpp

sheet.h
sheet.cpp

main.cpp
test_runner_p.h

Описание компонентов:

файл	назначение
common.h	интерфейсы проекта (SheetInterface, CellInterface, Position, FormulaError)
structures.cpp	реализация базовых структур
formula.h / formula.cpp	интерфейс и реализация формулы
FormulaAST.h / FormulaAST.cpp	AST формулы и вычисление выражений
Formula.g4	grammar ANTLR для парсинга формул
cell.h / cell.cpp	реализация ячейки
sheet.h / sheet.cpp	реализация таблицы и графа зависимостей
main.cpp	unit-тесты
test_runner_p.h	минимальный фреймворк для тестирования

---

Возможности

Поддерживаются:

• текстовые ячейки
• формульные ячейки
• ссылки на другие ячейки
• арифметические операции
• скобки
• dependency graph
• lazy caching
• проверка циклических зависимостей
• selective cache invalidation
• strong exception guarantee для изменения ячеек
• печать значений таблицы
• печать текстов таблицы

---

Поддерживаемые операции

Формулы поддерживают:

+
-
*
/
()

Примеры:

1+2
A1+B2
-(A1/2)
2*(B3+4)

---

Поддерживаемые ошибки

Формулы могут возвращать:

ошибка	причина
#REF!	некорректная ссылка
#VALUE!	значение нельзя преобразовать в число
#ARITHM!	арифметическая ошибка

---

Архитектура

Общая структура

Sheet
 ├── Cell
 │   ├── Impl
 │   │   ├── EmptyImpl
 │   │   ├── TextImpl
 │   │   └── FormulaImpl
 │   │
 │   ├── referenced_cells_
 │   ├── dependents_
 │   └── cache_
 │
 └── Graph logic
     ├── cycle detection
     ├── dependency rebuild
     └── cache invalidation

---

Cell

Cell представляет одну ячейку таблицы.

Она хранит:

referenced_cells_   — graph-state: ячейки, на которые ссылается данный узел
dependents_         — ячейки, которые зависят от данного узла
cache_              — кэш вычисленного значения

Реализации содержимого:

EmptyImpl
TextImpl
FormulaImpl

Cell отвечает за:

• хранение локального содержимого
• вычисление видимого значения
• кэширование результата
• хранение graph-state конкретного узла

При этом логикой управления dependency graph всей таблицы занимается Sheet.

---

Sheet

Sheet — основной orchestrator таблицы.

Отвечает за:

• хранение ячеек
• управление графом зависимостей
• проверку циклов
• перестройку зависимостей
• инвалидацию кэша
• печать таблицы
• управление printable size

Ячейки хранятся как:

unordered_map<Key, unique_ptr<Cell>>

Это позволяет эффективно работать с разреженными таблицами.

---

Dependency Graph

Каждая ячейка является вершиной графа.

Используются два типа рёбер:

referenced_cells_  (outgoing edges)
dependents_        (incoming edges)

Это позволяет:

• быстро проверять циклы
• инвалидировать кэш зависимых ячеек
• не пересчитывать всю таблицу целиком после каждого изменения

---

Formula + AST

Формулы:

1. парсятся через ANTLR
2. строят AST
3. вычисляются через callback получения значений ячеек

double Execute(CellValueGetter)

Это позволяет AST не зависеть напрямую от Sheet.

Кроме дерева выражения FormulaAST также хранит подготовленный список ячеек, использованных в формуле. Поэтому GetReferencedCells() работает за O(1).

---

Проверка циклов

Перед установкой формулы выполняется проверка:

WouldIntroduceCycle(...)

Используется поиск пути:

HasPathToTarget(...)

Если путь существует, выбрасывается:

CircularDependencyException

---

Cache invalidation

После изменения ячейки:

1. сбрасывается кэш текущей ячейки
2. сбрасывается кэш всех зависимых от неё ячеек

Используется обход графа:

InvalidateCacheFrom(...)

Это позволяет инвалидировать только затронутую часть таблицы.

---

Two-Phase Commit при SetCell

Установка значения ячейки выполняется в два этапа.

Phase 1 — подготовка

tmp_cell.Set(text)
ExtractReferencedCells(tmp_cell)
WouldIntroduceCycle(...)

Во временной ячейке подготавливается новое содержимое. Если это формула, ссылки извлекаются из уже подготовленного состояния, без повторного парсинга выражения.

Phase 2 — commit

cell.Set(text)
RebuildDependencies(...)
InvalidateCacheFrom(...)

Сначала применяется новое содержимое, после чего перестраивается graph-state таблицы и инвалидируется кэш затронутых ячеек.

Это позволяет сохранить strong exception guarantee для операции изменения ячейки.

Если возникает ошибка:

• FormulaException
• CircularDependencyException

состояние таблицы остаётся прежним.

---

Производительность

Основные идеи:

GetValue()           O(1) при наличии кэша
cache invalidation   O(K)
cycle detection      O(K)

где K — число затронутых зависимых ячеек.

---

Тестирование

В main.cpp реализованы unit-тесты, проверяющие:

• преобразование Position <-> string
• граничные случаи для координат ячеек
• арифметику формул
• форматирование выражений
• ссылки на ячейки
• ссылки на отсутствующие ячейки
• ошибки формул (#REF!, #VALUE!, #ARITHM!)
• циклические зависимости
• rollback при циклической зависимости
• rollback при синтаксически неверной формуле
• пересчёт зависимых ячеек
• очистку ячеек
• printable size
• печать текстов и значений таблицы

---

Используемые технологии

Проект использует:

• C++17
• ANTLR4
• AST
• dependency graph
• lazy caching
• selective invalidation

---

Вывод

Проект демонстрирует реализацию mini Excel-движка на C++ с архитектурой, близкой к реальным spreadsheet-системам.

Основная сложность проекта заключается не только в парсинге формул, но и в корректной реализации:

• dependency graph
• cycle detection
• cache invalidation
• согласованности состояния таблицы
• strong exception guarantee

---

Что стало лучше после рефакторинга

Теперь:

• AST не зависит напрямую от Sheet
• управление dependency graph сосредоточено в Sheet
• Cell отвечает за локальное содержимое и кэш узла
• устранено дублирование ответственности между Cell и Sheet
• добавлен two-phase commit при SetCell
• ссылки из временной ячейки извлекаются без повторного парсинга
• кэш инвалидируется только там, где это необходимо

---

Архитектурная схема вычисления

Sheet
  │
  ▼
Cell
  │
  ▼
FormulaImpl
  │
  ▼
FormulaAST
  │
  ▼
Execute(CellValueGetter)

---