Семь стрел, 429 деревьев: семилетняя ошибка именования, всплывшая за чисткой Mermaid-визуализации

Соглашение об именовании композиций в движке машины Тьюринга было неинъективным с 2019 года: одно имя — до C_7 = 429 разных машин. v7 чинит это скобками.

Заходят как-то две машины Тьюринга в одну диаграмму... а у них имена одинаковые.

Я говорю «машины», а на деле — два разных экземпляра State @turing-machine-js/machine, сконструированные по-разному, с разным поведением во время исполнения, и со строго одинаковым state.name. Это происходило в библиотеке, которую я разрабатываю в качестве хобби с 2019 года, и я этого не замечал семь лет.

Обнаружил случайно, начиная с задачи на чистку Mermaid-визуализации. Закончил — кардинальной переделкой того, как композиция состояний отражается в имени. И узнал, что за этой переделкой прячется число $C_{7} = 429$ .

Лучник с натянутым луком думает, в какое из деревьев леса попадёт его стрела

С чего всё началось

Композиция в движке устроена одним примитивом: baseState.withOverrodeHaltState(overrideState). Возвращает копию baseState, у которой halt-переходы во время исполнения уходят в overrideState вместо реального halt’а. Дальше я буду называть baseState базовым состоянием, а возвращаемую копию — обёрткой над ним. Композиция через обёртку — единственный способ собрать большую машину из маленьких подпрограмм: каждая подпрограмма в идеале заканчивается halt, и каждый withOverrodeHaltState переопределяет, куда идти после, вместо того чтобы остановиться.

Имя у получившейся обёртки в старом API формировалось так:

state.#name = `${this.name}>${override.name}`;

То есть A.withOverrodeHaltState(B) называется A>B. Просто и наглядно: читается как «A, потом B».

Эта строка ушла в продакшен в 2019 году и с тех пор не менялась. Она просачивается в логи, сообщения об ошибках, тесты, которые сравнивают state.name, и в любой диагностический вывод, на который смотрит пользователь.

Поводом разобраться стала Mermaid-визуализация. Тикет turing-machine-js#138 ставил задачу убрать дублирование. До v7 toMermaid рендерил обёртку как отдельный узел, на котором повторял все переходы базового состояния — визуально это выглядело так, будто у обёртки своя жизнь. Но переходы у обёртки те же, что у базы — даже #symbolToDataMap тот же. Своё у неё другое — call-frame-семантика: на входе push override на halt-стек, на halt’е базы — pop. А по сути обёртка вносит сверх базы только одно: куда уходит halt.

Грубо говоря, это выглядело так:

A и A>B — два узла с буквально одинаковыми исходящими переходами в A1, плюс у обёртки появляется пунктирная стрелка onHalt в B. Читающий видит «два разных автомата», хотя на уровне поведения это один автомат с одной точкой расхождения — куда уходит halt.

Первая попытка исправить визуализацию выглядела разумно: обёртку отрисовать одним узлом, переходы взять с базы, override-halt — отдельной стрелкой:

Один узел A>B, переходы — те же, что у базы; override-halt — отдельной пунктирной стрелкой от halt’а в B. Чисто, компактно, без визуального шума. Почти сработало.

Почти сработало = сломалось

Возьмём minusOne из library-binary-numbers — он собирается через вложенные обёртки:

const minusOne = invertNumber
  .withOverrodeHaltState(
    plusOne
      .withOverrodeHaltState(
        invertNumber
          .withOverrodeHaltState(normalizeNumber),
      ),
  );

Получается имя invertNumber>plusOne>invertNumber>normalizeNumber — три разделителя > в реальном коде, к тому же одна база (invertNumber) встречается дважды. Если имя длиннее, его соблазнительно прочесть как «инструкцию обхода». Например, A>B>B>A>A>B>B>A (семь разделителей): каждая буква — база, в которую переходишь на halt’е предыдущей. Последовательность обхода баз должна совпасть с именем.

Только это самообман. Имя ни в каком формальном смысле не определяет последовательность обхода. Оно напоминает её. И только если конкретная цепочка собралась тем единственным образом, которым я её представлял, когда выбрал способ записи композиции в 2019-м.

Загвоздка

Возьмём имя поскромнее: A>B>A. Сколько способов его построить?

Минимум два:

// Конструкция 1
const c1 = A.withOverrodeHaltState(B.withOverrodeHaltState(A));

// Конструкция 2
const c2 = A.withOverrodeHaltState(B).withOverrodeHaltState(A);

В обоих случаях правило ${this.name}>${override.name} даёт одну и ту же строку — A>B>A. Но топология обёрток разная — каждая конструкция собирает своё бинарное дерево (внутренние узлы • — применения withOverrodeHaltState, листья — исходные State):

И поведение тоже разное:

Конструкция 1 (A.wohs(B.wohs(A))): у A halt уходит в обёртку «B с halt’ом в A». При исполнении walk такой: A → B → A.
Конструкция 2 (A.wohs(B).wohs(A)): обёртка «A с halt’ом в B» дальше обёрнута ещё раз — теперь halt уходит в A. При исполнении walk: A → A. Внутренний override B мёртв: на halt-стек попадает только override самой внешней .wohs()-операции.

Имя одинаковое. Просто потому, что плоский разделитель > не запоминает, где в дереве конструирования каждая стрелка стояла. А дерево там было.

Потерянное дерево

Композиция через withOverrodeHaltState — операция бинарная: левый аргумент (this), правый аргумент (override). Каждое её применение — это новый узел в дереве. У узла два ребёнка: база и override. Если ребёнок сам обёртка, дерево там продолжается ещё одним узлом; если нет, это исходное State — лист. После N применений в дереве N узлов-обёрток и N+1 лист — стандартное свойство бинарного дерева. Например, у minusOne выше: 3 применения (3 узла-обёртки) и 4 листа — invertNumber, plusOne, invertNumber, normalizeNumber. Вот это же дерево явно:

Имя же — плоское — конкатенация имён через >. Из бинарного дерева получается строка, и обратно строка восстанавливает дерево только если соглашение об именовании биективно. У плоской >-нотации оно не биективно.

Сколько разных деревьев соответствует одному имени с N разделителями? Стандартный ответ из комбинаторики: число Каталана $C_{N}$ .

$C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})$ — это та самая последовательность, которая считает: число бинарных деревьев с n+1 листьями, число правильных скобочных последовательностей длины 2n, число путей Дика длины 2n, число триангуляций (n+2)-угольника, и ещё с десяток изоморфных комбинаторных объектов. Одно из тех чисел, которые «вылезают отовсюду».

В нашем случае самая близкая проекция — расстановка скобок: для произвольного бинарного оператора • число способов расставить скобки в выражении a • b • c • ... (n+1 операндов) равно $C_{n}$ . withOverrodeHaltState — как раз такой оператор, и каждой расстановке скобок соответствует своё дерево композиции.

Первые восемь значений: $C_{0} = 1$ , $C_{1} = 1$ , $C_{2} = 2$ , $C_{3} = 5$ , $C_{4} = 14$ , $C_{5} = 42$ , $C_{6} = 132$ , $𝑪_{7} = 429$ .

Для нашего A>B>B>A>A>B>B>A это значит: 429 различных деревьев композиции, у каждого по-своему расставлены родительско-дочерние связи, дают одну и ту же строку. И это не теоретическая верхняя оценка — это точное число несовпадающих структур, прячущихся за одним именем.

Пример поменьше — A>B>C>D (три разделителя). По формуле $C_{3} = 5$ ; вот эти пять деревьев, сконструированные в коде:

// 1. полностью левоассоциативное
((A.wohs(B)).wohs(C)).wohs(D)

// 2.
(A.wohs(B.wohs(C))).wohs(D)

// 3.
(A.wohs(B)).wohs(C.wohs(D))

// 4.
A.wohs((B.wohs(C)).wohs(D))

// 5. полностью правоассоциативное
A.wohs(B.wohs(C.wohs(D)))

Все пять схлопываются в одну и ту же плоскую строку A>B>C>D. В скобочной нотации, которая придёт в v7, каждое получит уникальное имя — об этом ниже.

Починка скобками

Если плоский разделитель теряет дерево, то скобки его сохраняют. v7 (turing-machine-js#148) меняет соглашение об именовании на:

state.#name = `${this.name}(${override.name})`;

A.withOverrodeHaltState(B) теперь называется A(B). Возвращаемся к нашим двум конструкциям A>B>A:

// Конструкция 1: A(B(A))
const c1 = A.withOverrodeHaltState(B.withOverrodeHaltState(A));

// Конструкция 2: A(B)(A) — в чистой скобочной нотации
const c2 = A.withOverrodeHaltState(B).withOverrodeHaltState(A);

Те же буквы, разная расстановка скобок, разные деревья. Имена различимы. Биекция!

И это не изобретённое соглашение. Сбалансированные скобочные строки длины 2n — каноническая запись бинарных деревьев с n+1 листьями в комбинаторике. Это та самая биекция, на которой держится один из основных счётных результатов о числах Каталана. Лучший формат не был придуман — в нём просто будет отражена структурность, которую >-нотация всё это время выбрасывала.

Стоимость для пользователя — запрет на скобки ( и ) в именах состояний: конструктор State бросает исключение. Скобки зарезервированы под композицию. Зато > больше не зарезервирован — можно использовать в пользовательских именах свободно.

Вторая половина истории

Чистая скобочная биекция выше — это история про именование. v7 заодно подчищает и runtime. turing-machine-js#176 добавляет коллапс цепочек: внутри withOverrodeHaltState теперь делается bare = this.#bareState ?? this. То есть A.wohs(B).wohs(A) распознаётся как «обёртывание уже-обёрнутой A», внутренний override (B) при этом всё равно мёртв во время исполнения (на halt-стек кладётся только override самой внешней обёртки), и вместо A(B)(A) получается просто A(A).

Так что в реальном v7 наша Конструкция 2 не даст A(B)(A) — на этапе сборки она схлопывается в A(A). Скобочное именование само по себе биективно (каждому дереву — своё имя); коллапс цепочек убирает деревья, неотличимые на runtime. В итоге имя в v7 описывает поведение машины, а не историю её построения.

И заодно: метод переименовывается. withOverrodeHaltState → withOverriddenHaltState (turing-machine-js#149). Past-tense (overrode) в этой идиоме читался криво — должен был быть past participle (overridden). Семилетняя грамматическая опечатка на публичном API. Чинится одним rename без алиаса.

Где ещё встречается подобное

Неинъективная сериализация — общий паттерн. Если в вашем коде есть «имя», которое склеивается плоским разделителем из чего-то структурно древовидного, шансы на C_n-баг ненулевые. Несколько примеров:

Цепочки расширений файлов — .tar.gz, .spec.ts, .d.ts. Работает по соглашению, потому что расширения известны заранее. Стоит поставить точку в имени файла — и сразу возникает неоднозначность: my.app.tar.gz — это базовое имя my.app с расширением .tar.gz или базовое имя my.app.tar с расширением .gz? Разные инструменты разрешают по-разному.
Имена джоинов в БД через _: user_address_country. Если user_address уже сам по себе имя таблицы (подчёркивание — часть идентификатора), то user_address_country неоднозначно: то ли это user.address_country, то ли user_address.country. Починка — квалифицированное пространство имён или явные алиасы.
Модульные пути в Java/Python — com.example.foo.Bar. Это может быть класс Bar в пакете com.example.foo или вложенный класс foo.Bar в пакете com.example. Разрешается по соглашению (заглавная буква — класс), а не самим именованием.

Эвристика для код-ревью: если ваш «идентификатор» — это плоская конкатенация разделителем чего-то древовидного, поищите C_n-баг. Чаще всего он скрытый: имена случайно не пересекаются на тех данных, что в проде, но архитектурно дыра всегда там.

В моей библиотеке C_n-баг прятался семь лет, потому что никто не пытался поймать движок на коллизии имён. Чтобы её обнаружить, надо догадаться построить два структурно разных дерева и проверить, что имена у них различаются. Такой тест никто не пишет, пока не узнает, что коллизия в принципе возможна.

Что уезжает в v7

Три тикета, которые задумывались как три отдельных изменения, но при ближайшем рассмотрении — одна и та же мысль:

Скобочное именование (turing-machine-js#148). Биекция между деревьями композиции и именами.
Чистая Mermaid-визуализация (turing-machine-js#138, turing-machine-js#174). Обёртка рендерится как отдельный узел [[композитное-имя]], тело базы — как подграф callable subtree of NAME. Структурная ясность имени отражается в визуальной ясности диаграммы:

Обёртка — call-site; тело базы — callable subtree; halt — return. Композиция в движке буквально стала чтением как вызов функции.
withOverrodeHaltState → withOverriddenHaltState (turing-machine-js#149). Грамматика на публичном API.

Все три про одно: композиция — древовидная, представление должно сохранять дерево, а не размывать его.

В заключение

Чистка визуализации привела к перестройке именования. Это та же история, которую я уже описывал в "Два мажора, один README, одно демо": дизайн-ревью, которое тесты провести не могут, ловит то, что тестам не видно. Там это были документация и первый потребитель API. Здесь — визуализация. Жанр один и тот же: ставишь себя перед задачей показать структуру, и структура — если она кривая — начинает торчать. Тесты этого не делают, потому что они смотрят на поведение, а кривизна структуры зачастую видна только в её представлении.

Семь стрел, 429 деревьев. Имя, которое выглядело как инструкция обхода, на деле было одной из 429 возможных. v7 даёт каждой её собственное имя — и оставляет за визуализацией право показать, как это дерево на самом деле росло. А что обёртка — это call-frame, и эту структуру стоит вытащить в отдельный тип, — уже другая история (turing-machine-js#213).