Undo/Redo в collaborative

Ctrl+Z - одна из самых используемых комбинаций клавиш. В collaborative редакторе за ней скрывается один из самых сложных алгоритмов: как отменить своё, не тронув чужое, в параллельно редактируемом документе.

• **Google Docs** реализует local undo с captureTimeout ~1.5с: слова объединяются в группы. При undo документ откатывается только по операциям текущего пользователя, даже если между ними были изменения коллег
• **Figma** очищает redo-стек при получении remote операций - компромисс между корректностью и простотой реализации. Команда сознательно пошла на это упрощение
• **Notion** хранит CRDT tombstone-историю для каждой страницы. Это позволяет восстанавливать удалённые блоки через 'Page history' даже спустя дни после удаления
• **Yjs UndoManager** - open-source реализация, которую используют Hocuspocus, BlockNote, Tiptap. Поддерживает undo через remote операции без очистки стека

Collab Undo

Ctrl+Z в одиночном редакторе - тривиальная операция: откат последней операции из стека. В collaborative редакторе это превращается в нетривиальную задачу. Представим: Алиса написала слово, Боб удалил следующее предложение, Алиса нажала Ctrl+Z. Что должно произойти? Отменить слово Алисы - окей. Но операция Боба уже вошла в общую историю документа.

Решение - **local undo**: каждый пользователь отменяет только свои собственные операции, не трогая чужие. Это противоречит интуитивной модели 'отмотать время назад', но единственный вариант, который не ломает чужую работу.

**captureTimeout** в Yjs UndoManager - аналог debounce для undo: быстрый набор текста объединяется в одну группу, иначе каждая буква была бы отдельным undo-шагом. Google Docs использует похожую логику: слова объединяются в одну undo-единицу, паузы >1.5с создают новую группу.

Selective Undo

Local undo отменяет операции в обратном порядке (LIFO). Selective undo - мощнее: можно отменить любую конкретную операцию из истории, не затрагивая более поздние. Это нужно например в Figma: 'отменить только изменение цвета этого объекта, оставив все остальные правки'.

Selective undo требует вычисления **inverse operation** для целевой операции с учётом всех последующих. Для текстовых операций это непрямолинейно: если удалить символ на позиции 5, а затем вставить 10 символов до позиции 5 - инверсия удаления должна вставить символ на позицию 15, не 5.

**Figma** реализует selective undo для свойств объектов: каждый `setProperty` - отдельная операция, которую можно отменить независимо. Это работает потому что изменения свойств объектов не зависят друг от друга (нет смещений как в тексте). Для текстовых CRDT selective undo значительно сложнее.

History Branches

В одиночном редакторе undo создаёт линейную историю: undo → undo → redo - возвращает туда же. В collaborative среде история становится **деревом**: после undo + новые изменения - redo-ветка становится недостижимой. Это history branching.

Проблема ещё глубже: два пользователя могут иметь разные локальные undo-стеки. Когда Алиса нажимает undo, она откатывает свою операцию - но документ уже содержит изменения Боба. Это создаёт **нелинейное дерево состояний** документа, где каждый узел - возможное состояние.

**Git** имеет похожую проблему: после `git rebase` старые коммиты становятся недостижимы. В collaborative редакторах Figma не реализует redo после чужих изменений - redo-стек очищается при приходе remote операций, пока cursor находится не в конце стека. Это упрощение, но пользователи его не замечают.

Undo Crdt

CRDT-структуры имеют специфику при undo: операции не просто 'откатываются' - они **помечаются как удалённые** (tombstone). Вставленный символ при undo не исчезает физически из CRDT - он получает флаг deleted. Это обеспечивает convergence: если удалённый символ ещё не дошёл до другого клиента - тот его обработает и тоже пометит.

**Yjs tombstone** хранится вечно (пока документ существует) - это цена convergence. В реальных документах Notion, Google Docs накапливаются тысячи tombstone-символов. Для оптимизации используется garbage collection: tombstone можно удалить если все клиенты подтвердили получение этой версии (all-acked). Yjs поддерживает GC через `ydoc.gc = true`.

Итоги

• Local undo - единственная корректная модель: каждый отменяет только свои операции, чужие не затрагиваются
• Selective undo требует трансформации инверсии через все последующие операции - аналогично OT
• CRDT undo использует tombstone вместо физического удаления: convergence важнее компактности

Связанные темы

Undo в collaborative среде тесно связан с базовыми алгоритмами consistency:

• Operational Transformation — Selective undo требует тех же transform-функций что и OT для convergence concurrent операций
• CRDT tombstones — Физическая основа undo в CRDT: удалённые элементы хранятся как tombstone для обеспечения eventual consistency
• Conflict Resolution — Undo порождает новый класс конфликтов - следующий урок о стратегиях их разрешения

Вопросы для размышления

• Как должен вести себя Undo если пользователь удалил параграф, а коллега за это время отредактировал его? При undo - что восстанавливать: оригинальный параграф или версию с правками коллеги?
• Почему Google Docs ограничивает глубину undo-истории? Какие технические и UX-причины стоят за этим решением?
• CRDT tombstone растут бесконечно. Как garbage collection должен определять когда tombstone можно безопасно удалить?

Связанные уроки

• net-01-intro