MOffice

Спайк A1: движок формул — форк IronCalc против formualizer

Сессия A, 2026-10-04. Задача A1 брифа docs/sessions/A-kernel.md. Решение оформлено как ADR в разделе 6. Код форка — kernel/crates/meridian-calc и kernel/crates/meridian-calc-xlsx; стенд замеров — kernel/spikes/calc-bench (в продукт не входит); отчёт о покрытии — cargo run -p meridian-calc --example function_coverage -- docs/apps/sheets.md.

1. Что сделано

  1. Форк IronCalc 0.8.3 (зеркало meridian-oss/IronCalc, коммит 9b1ae3f от 2026-10-02, MIT OR Apache-2.0, используется на условиях MIT) скопирован в два крейта:
    • meridian-calc ← ironcalc_base: модель книги, парсер A1/R1C1 с локалями, вычислитель, 496 встроенных функций, LET/LAMBDA, динамические массивы, условное форматирование, форматы чисел;
    • meridian-calc-xlsx ← ironcalc (каталог xlsx/): импорт и экспорт xlsx, сверка вычислений движка со значениями, сохранёнными Excel (compare::test_file), бинарник calc-xlsx-check для корпуса. В каждом из 557 перенесённых файлов — заголовок «Основано на IronCalc», в крейтах — NOTICE с журналом изменений и тексты лицензий (licenses/).
  2. Тесты IronCalc проходят без изменений: 2 683 юнит-теста meridian-calc (8 помечены ignore ещё в исходнике), 23 сценария на 24 эталонных книгах xlsx (tests/calc_tests), 229 тестов meridian-calc-xlsx, doc-тесты; всего ≈ 2 990.
  3. Прежний мини-парсер заменён: его 8 групп тестов перенесены в tests/legacy_mini.rs и гоняются на движке IronCalc. Три ожидания исправлены под Excel: ROUND требует два аргумента; ссылка на пустую ячейку в формуле даёт 0; канонический вид формулы — =SUM(A1:B2,5) (без пробела после запятой).
  4. Найдена и исправлена ошибка IronCalc: =10^400 давал #DIV/0!, Excel — #NUM! (переполнение). Теперь #DIV/0! — только ноль в отрицательной степени. Тест overflow_is_num_error.
  5. Публичный список функций meridian_calc::builtin_function_names() и пример function_coverage, который разбирает каталог docs/apps/sheets.md §5.23 и сверяет его с движком (раздел 3).
  6. Лицензии зависимостей: 87 внешних крейтов дерева workspace — все в классах 0–1 (deny.toml, allow); ни одного крейта из списка запретов. Новые крейты: serde, ryu, chrono, chrono-tz, bitcode, csv, statrs, rand 0.8, regex, zip 0.6, quick-xml 0.42, thiserror 1, itertools 0.12, serde_json (и их зависимости).

2. Как устроен пересчёт в IronCalc и formualizer

IronCalc (форк) formualizer 0.10.1
Объём кода движка ≈ 132 тыс. строк (base, с тестами) ≈ 283 тыс. строк (formualizer-eval) + parse/common/workbook
Хранение ячеек HashMap строк/столбцов на лист столбцы Apache Arrow 59
Граф зависимостей нет: evaluate() проходит все ячейки в естественном порядке, рекурсивно вычисляет ссылки, кэширует результат на время прохода; глубина и стек ограничены, при превышении — раскрутка и повтор (set_max_evaluation_depth/stack) есть: рёбра CSR + дельты, дерево интервалов для диапазонов, «грязные» вершины, планировщик слоями
Инкрементальный пересчёт нет — любая правка пересчитывает всю книгу да — только транзитивное замыкание правки
Многопоточность нет rayon по слоям топологического порядка (enable_parallel)
Ускорители — кэш агрегатов диапазонов («полосы»), индекс точного поиска для VLOOKUP/MATCH, мемоизация форм
Функции 496 (458 имён каталога + 38 алиасов) «400+»
Лицензия MIT OR Apache-2.0 MIT OR Apache-2.0

3. Покрытие каталога функций Sheets (docs/apps/sheets.md §5.23)

Категория Фаза В каталоге Есть в движке Покрытие Нет в движке
Математические и тригонометрические P0 57 56 98 % AGGREGATE
Математические и тригонометрические P1 24 24 100 % —
Статистические P0 63 63 100 % —
Статистические P1 48 48 100 % —
Текстовые P0 33 33 100 % —
Текстовые P1 15 11 73 % BAHTTEXT, DBCS, JIS, PHONETIC
Текстовые P2 2 0 0 % TRANSLATE, DETECTLANGUAGE
Логические P0 20 20 100 % —
Дата и время P0 25 25 100 % —
Ссылки и поиск P0 35 34 97 % GETPIVOTDATA
Ссылки и поиск P1 5 2 40 % IMAGE, GROUPBY, PIVOTBY
Ссылки и поиск P2 1 0 0 % RTD
Финансовые P0 27 27 100 % —
Финансовые P1 24 24 100 % —
Финансовые P2 4 4 100 % —
Инженерные P0 24 24 100 % —
Инженерные P1 30 30 100 % —
Информационные P0 20 20 100 % —
Базы данных P0 12 12 100 % —
Куб P2 7 0 0 % CUBEKPIMEMBER, CUBEMEMBER, CUBEMEMBERPROPERTY, CUBERANKEDMEMBER, CUBESET, CUBESETCOUNT, CUBEVALUE
Веб P0 1 1 100 % —
Веб P1 1 0 0 % FILTERXML
Веб P2 1 0 0 % WEBSERVICE
Надстройки P2 1 0 0 % EUROCONVERT
Расширения MS. P1 9 0 0 % MS.REGEX, MS.NOWUTC, MS.UUID, MS.HASH, MS.JSONVALUE, MS.CELLCOLOR, MS.SHEETNAME, MS.FORMULAS, MS.DISPLAYTEXT
Фаза В каталоге Есть в движке Покрытие
P0 317 315 99.4 %
P1 156 139 89.1 %
P2 16 4 25.0 %
Всего 489 458 93.7 %

Алиасы совместимости: 38 из 38 есть в движке; нет: —.

Функции движка вне каталога (0): —.

Имён в каталоге: 489, встроенных функций движка: 496.

Итог: P0 — 315 из 317 (99,4 %), не хватает AGGREGATE и GETPIVOTDATA; все 38 алиасов совместимости есть. P1 считает и 9 расширений MS.* (их нет в сумме каталога 518 имён), P2 — 16 имён. Таблица воспроизводится командой из шапки отчёта и пересчитывается при каждом изменении каталога или движка.

4. Замеры

Машина: Apple M5 Max, 18 ядер, 128 ГБ; сборка release (opt-level=3, thin LTO). Каждый замер — отдельный процесс (kernel/spikes/calc-bench/run.sh). Обозначения движков: IC — форк IronCalc; FZ1 — formualizer, один поток; FZP — formualizer, параллельно; FZB — formualizer, параллельно, пакетная загрузка set_values/set_formulas. «Сборка» — ввод всех ячеек; «пересчёт» — первый полный пересчёт; «правка» — среднее по 5 правкам одной ячейки с пересчётом. Контрольные значения всех движков совпали во всех сценариях.

Сценарии: fanout — B=A*2+1 (n независимых формул); chain — цепочка C_i=C_(i-1)+B_i; rchain — обратная цепочка C_i=C_(i+1)+B_i (худший порядок для прохода по строкам); prefix — SUM(A$1:A_i) (O(n²) чтений); vlookup — точный VLOOKUP по несортированному столбцу (O(n²) сравнений); heavy — 6 трансцендентных функций на ячейку; edit-tail/edit-head — цепочка 100 тыс., правка последней / первой строки.

Сценарий n Движок Сборка, мс Пересчёт, мс Правка, мс RSS, МБ
fanout 100 000 IC 265 18.5 — 65.9
fanout 1 000 000 IC 2 700 222 — 557
fanout 100 000 FZ1 3 207 40.9 — 136
fanout 1 000 000 FZ1 35 213 513 — 1 025
fanout 100 000 FZP 3 318 51.7 — 154
fanout 1 000 000 FZP 32 031 493 — 1 383
fanout 100 000 FZB 657 40.0 — 162
fanout 1 000 000 FZB 7 642 489 — 1 489
chain 100 000 IC 484 31.3 — 76.3
chain 100 000 FZ1 4 389 469 — 269
chain 100 000 FZP 4 302 274 — 295
chain 100 000 FZB 1 382 254 — 301
rchain 100 000 IC 462 48.3 — 75.2
rchain 10 000 FZ1 3 308 19.5 — 40.4
rchain 10 000 FZP 3 764 21.3 — 54.0
rchain 100 000 FZB 1 404 230 — 301
prefix 10 000 IC 30.9 336 — 14.0
prefix 10 000 FZ1 190 10.6 — 24.7
prefix 10 000 FZP 189 3.8 — 28.4
prefix 10 000 FZB 93.2 3.3 — 28.8
vlookup 10 000 IC 46.0 1 176 — 15.6
vlookup 10 000 FZ1 950 10.2 — 32.2
vlookup 10 000 FZP 856 7.8 — 35.7
vlookup 10 000 FZB 100 7.2 — 34.0
heavy 200 000 IC 2 517 74.6 — 138
heavy 200 000 FZ1 12 673 422 — 639
heavy 200 000 FZP 13 108 326 — 761
heavy 200 000 FZB 6 851 297 — 719
edit-tail 100 000 IC 370 23.0 22.7 93.7
edit-tail 100 000 FZ1 3 924 296 0.01 264
edit-tail 100 000 FZP 4 462 230 0.01 294
edit-tail 100 000 FZB 1 342 252 0.02 301
edit-head 100 000 IC 394 25.0 22.6 93.1
edit-head 100 000 FZ1 3 916 278 54.1 268
edit-head 100 000 FZP 3 978 233 53.1 293
edit-head 100 000 FZB 1 352 250 58.0 308

Сырые данные — kernel/spikes/calc-bench/results-2026-10-04-m5max.jsonl. Для FZ1/FZP обратная цепочка взята на 10 тыс. строк: поячеечная вставка formualizer на 100 тыс. занимает ≈ 278 с (см. вывод 4).

5. Выводы

  1. Загрузка, полный пересчёт и память — за IronCalc. На книгах 100 тыс. – 1 млн формул форк строит модель в 2,5–3 раза быстрее пакетной загрузки formualizer и в 10–13 раз быстрее поячеечной (formualizer строит граф и столбцы Arrow), полный пересчёт простых формул быстрее в 2–15 раз, пиковая память меньше в 2–5 раз. Для открытия файла (импорт xlsx + пересчёт) это главное.
  2. Инкрементальный пересчёт — за formualizer, но не везде. Правка «хвоста» цепочки: 0,01 мс против ≈ 23 мс — граф пересчитывает 2 ячейки вместо 200 тыс. Правка «головы» (замыкание = вся цепочка): formualizer ≈ 53 мс — медленнее полного пересчёта IronCalc (≈ 23 мс): накладные расходы графа на вершину выше, чем стоимость простой формулы. Значит, граф нужен, но с дешёвым обходом и порогом «замыкание больше X % книги → полный проход».
  3. Алгоритмические ускорители дают больше, чем потоки. Префиксные суммы у formualizer быстрее в 30–100 раз (кэш агрегатов диапазонов), точный VLOOKUP — в 115–160 раз (индекс поиска). Многопоточность formualizer даёт ×1,3 на «тяжёлых» формулах, ×1,7 на цепочке и ×2,8 на префиксных суммах, а на простых независимых формулах замедляет пересчёт (41 → 52 мс).
  4. Патология поячеечной вставки formualizer: обратная цепочка 100 тыс. строится 278 с (квадратично); пакетный API снимает проблему (≈ 1,5 с), но означает, что formualizer требует аккуратной загрузки.
  5. IronCalc не падает на глубоких цепочках (обратная цепочка 1 млн — 0,66 с пересчёта): ограничение глубины с раскруткой и повтором уже есть в исходнике.
  6. Пробелы форка (для плана фазы 2): нет графа и инкрементального пересчёта; нет многопоточности; нет 3D-ссылок (Лист1:Лист3!A1), внешних ссылок [Книга]Лист!A1, объединения и пересечения диапазонов; нет русского языка функций и локали ru (в IronCalc только en, de, es, fr, it) — СУММ/ЕСЛИ, запятая как десятичный разделитель и ; между аргументами нужно добавить в locale/language сами; нет AGGREGATE и GETPIVOTDATA (P0), IMAGE/GROUPBY/PIVOTBY, BAHTTEXT, DBCS, JIS, PHONETIC, FILTERXML (P1) и функций MS.*.

6. Решение (ADR-A1, 2026-10-04)

Контекст. Нужен движок формул Sheets: совместимость с Excel по каталогу из 518 имён, быстрое открытие больших книг, интерактивные правки без полного пересчёта, всё — под лицензией MOffice (классы 0–1).

Решение.

  1. Основа — форк IronCalc в meridian-calc / meridian-calc-xlsx (сделано). formualizer не подключаем зависимостью: вдвое больше кода, дерево Arrow, медленнее загрузка и полный пересчёт, квадратичный поячеечный ввод. formualizer (MIT/Apache, класс 1) — образец алгоритмов; переносить фрагменты кода можно с заголовком «основано на formualizer» и записью в NOTICE.
  2. Свои доработки форка — по порядку выгоды (фаза 2, эпик «граф и пересчёт»):
    1. граф зависимостей в meridian-calc (deps/): прямые рёбра «ячейка → ячейка» и интервальный индекс «диапазон → формулы» (по образцу дерева интервалов formualizer), строится из статического анализа AST IronCalc; динамические ссылки (INDIRECT, OFFSET) — из записей «что прочитано» (record_seen, уже есть в IronCalc) с перестройкой рёбер после вычисления;
    2. инкрементальный пересчёт: «грязное» замыкание правки в топологическом порядке; если замыкание больше ≈ 20 % формул книги — обычный полный проход IronCalc (вывод 2);
    3. кэш агрегатов диапазонов для SUM/COUNT/AVERAGE/MIN/MAX и семейства *IFS по растущим диапазонам и индекс точного поиска для VLOOKUP/HLOOKUP/MATCH/XLOOKUP/XMATCH с инвалидацией по правкам (вывод 3);
    4. многопоточность — последней и только для слоёв с «тяжёлыми» формулами (оценка стоимости из AST); ожидаемый выигрыш ×1,3–3, а не кратный.
  3. В фазе 1 (до графа) — русская локаль и язык функций, AGGREGATE и GETPIVOTDATA (последние две — P0).
  4. Редакция Rust форка остаётся 2021 и rust-version = 1.87 (API is_multiple_of) до отдельной задачи перевода; missing_debug_implementations в форке разрешён на уровне крейта, чтобы diff с исходником оставался читаемым и можно было переносить исправления IronCalc.

Последствия. Открытие больших книг и полный пересчёт — сразу быстрые; интерактивность больших книг зависит от доработок 2.1–2.3 (оценка 6–9 чел.-нед.). Исправления IronCalc из основной ветки переносим вручную: в NOTICE крейта ведётся журнал наших изменений, заголовки файлов не мешают diff.

7. Как повторить

cargo test -p meridian-calc -p meridian-calc-xlsx
cargo run -p meridian-calc --example function_coverage -- docs/apps/sheets.md
kernel/spikes/calc-bench/run.sh results.jsonl   # formualizer берётся из зеркала meridian-oss по SSH