Сквозные алгоритмы ядра Meridian Kernel

Алгоритмы, общие для всех приложений: структуры текста, стили, идентификаторы, журнал операций, CRDT, рендер, файлы, поиск, буфер обмена, печать, планировщик, память, детерминизм. Для каждого — псевдокод или Rust, сложность, тесты. Привязка к крейтам — 03-architecture.md §3. Алгоритмы отдельных приложений (раскладка страниц Write, пересчёт Sheets, анимации Slides) — в docs/apps/<app>.md. Версия 0.1 · 2026-10-03.

Обозначения: n — длина текста в байтах, p — число кусков piece table, k — число спанов атрибутов, m — число узлов документа, s — число стилей, c — число команд списка отображения.

1. Структура текста

1.1 Выбор: piece table с индексом-B-деревом

Доводы: буфер оригинала (original) — это ровно текст из файла (часто просто срез mmap-буфера, без копии), он неизменяем — безопасен для фоновых снимков; add-буфер только растёт — тоже безопасен для чтения из других потоков; все правки — правки списка кусков, малого и дешёвого для клонирования в снимок (§5 архитектуры). Piece table естественно ложится на CRDT: Yrs тоже хранит текст как цепочку неизменяемых блоков. Реализация в kernel/crates/meridian-text/src/piece_table.rs — линейный список кусков (достаточно для абзацев: p редко > 50); индекс-B-дерево включается, когда p > 64, прозрачно для API.

1.2 Индекс кусков

/// B-дерево порядка 16 над кусками; внутренние узлы хранят суммарные длины поддеревьев
/// (байты и символы), что даёт поиск по байтовому и символьному смещению за O(log p).
/// B-tree of order 16 over pieces; inner nodes keep subtree byte and char totals.
struct Inner { keys: ArrayVec<Summary, 16>, children: ArrayVec<NodeRef, 16> }
struct Leaf  { pieces: ArrayVec<Piece, 32>, summary: Summary }
#[derive(Clone, Copy, Default)]
struct Summary { bytes: u32, chars: u32, newlines: u32 }   // newlines — для быстрых строк/абзацев

fn locate(root: &Node, mut byte: u32) -> (LeafRef, usize /*piece idx*/, u32 /*offset*/) {
    let mut node = root;
    loop {
        match node {
            Node::Inner(inner) => {
                // спуск по накопленным суммам / descend by cumulative sums
                let mut i = 0;
                while i + 1 < inner.keys.len() && byte >= inner.keys[i].bytes { byte -= inner.keys[i].bytes; i += 1; }
                node = &inner.children[i];
            }
            Node::Leaf(leaf) => {
                let mut i = 0;
                while i + 1 < leaf.pieces.len() && byte >= leaf.pieces[i].len { byte -= leaf.pieces[i].len; i += 1; }
                return (leaf.as_ref(), i, byte);
            }
        }
    }
}

Вставка: locate → разрез куска (0–2 новых куска) → вставка в лист → при переполнении листа (32) — split и подъём ключа; суммы обновляются вверх по пути (O(log p)). Удаление диапазона: два locate, обрезка крайних кусков, удаление целого поддиапазона листов/узлов за O(log p + удалённые куски), слияние узлов ниже 1/4 заполнения. Последовательный набор сливается с последним куском add-буфера (как в линейной версии).

Сложность: insert/delete — O(log p); byte_to_char/char_to_byte — O(log p) по Summary.chars; итерация диапазона — O(log p + число кусков в диапазоне); снимок (клон дерева) — O(1) с персистентными узлами (Arc, copy-on-write при правке по пути: O(log p) аллокаций на правку).

Компактация: при p > 4·(n / 4096) (слишком много мелких кусков) фоновая задача переписывает текст в новый original (единый кусок) — делается только в точке покоя (нет активного набора 2 с) и фиксируется как Op::Compact, невидимый для undo.

1.3 Атрибутные спаны и их слияние

Инварианты (meridian-text::AttrSpans): спаны покрывают [0, len) без дыр, отсортированы, непустые, соседние с равными Attrs слиты. Операции:

set(range, key, value):
  i = split_at(range.start)      # гарантирует границу; O(log k) поиск + O(k) сдвиг в Vec
  j = split_at(range.end)
  for span in spans[i..j]: span.attrs[key] = value
  normalize(i-1 ..= j)           # слить только затронутую окрестность / merge the touched neighbourhood only
on_insert(at, len):              # новые символы наследуют атрибуты слева (в начале — справа)
  span = spans[partition_point(end < at)] ; span.end += len ; сдвинуть последующие на len
on_delete(range):
  map(p) = p если p <= start; start если start < p < end; p - removed иначе
  для каждого спана: (start, end) = (map(start), map(end)) ; удалить пустые ; слить равных соседей

Представление спанов — Vec<AttrSpan>: для абзацев k мало (десятки), а линейная память и кэш-локальность важнее O(log k) обновлений. Для абзацев с k > 256 (сгенерированные документы с посимвольным форматированием) включается то же B-дерево с суммами, что у кусков. Attrs — BTreeMap<AttrKey, AttrValue>: детерминированный порядок (нужен для хэша резолвера §2 и для CBOR-сериализации), сравнение за O(|attrs|).

Слияние при вставке форматированного фрагмента (paste): спаны фрагмента сдвигаются на at, вставляются, затем normalize на окрестности; для копирования форматирования между абзацами с разными стилями применяется «приведение к явному»: атрибуты, которые во фрагменте наследовались от стиля-источника, материализуются прямыми (resolve(source) − resolve(target)), чтобы вид сохранился — O(k · |attrs|).

1.4 Тесты

• Детерминированный фаззер против String (есть: matches_string_model_under_random_edits, 2 000 операций, UTF-8 многобайтовые символы и эмодзи) — расширить до 10⁵ операций в ночном прогоне с проверкой инвариантов дерева (debug_assert_tree_sums).
• Свойства proptest: insert ∘ delete = id, byte_to_char ∘ char_to_byte = id, set(range) ⇒ attrs_at(p) == value ∀ p ∈ range, normalize идемпотентна, число спанов ≤ 2·(число операций) + 1.
• Производительность: 1 М вставок по случайным позициям в 10 МБ текста < 2 с (criterion text_insert_random).

2. Резолвер стилей с кэшем

2.1 Цепочка наследования

Для узла N вычисленное форматирование R(N):

R(N) = merge(
  defaults(kind),                                   # встроенные значения по типу узла
  chain(style(N)) ,                                 # basedOn-цепочка от корня к стилю узла, глубина ≤ 32
  conditional(table_style, N.position),             # условное форматирование таблиц (первая строка, полосы)
  inherited(parent(N)),                             # для символов: абзацные свойства «по умолчанию для runs»
  N.attrs,                                          # прямое форматирование
)

merge — поатрибутное наложение: позже — сильнее; toggle-свойства (bold/italic в OOXML) — XOR по цепочке стилей символов (как в Word), что реализовано отдельным проходом apply_toggle. Тема (Theme) резолвится последней: ссылки на цвета/шрифты темы (theme:accent1, +mn-lt) заменяются значениями.

2.2 Кэш

#[derive(Hash, Eq, PartialEq)]
struct ResolveKey { style_chain: u64, attrs: u64, context: u32, sheet_version: u64 }

fn resolve(&mut self, node: &Node, ctx: &ResolveContext) -> Arc<ResolvedStyle> {
    let key = ResolveKey {
        style_chain: self.chain_hash(node.style),        // кэшируется по StyleId: O(1) после первого вызова
        attrs: hash_attrs(&node.attrs),                   // BTreeMap → детерминированный порядок → стабильный хэш
        context: ctx.bits(),                              // позиция в таблице, уровень списка, секция
        sheet_version: self.sheet.version,
    };
    if let Some(r) = self.cache.get(&key) { return r.clone(); }
    let r = Arc::new(self.compute(node, ctx));
    self.cache.insert(key, r.clone());                    // LRU 10 000 записей на документ
    r
}

chain_hash(style) = хэш последовательности (StyleId, style.version) по цепочке basedOn — пересчитывается при изменении любого стиля в цепочке (style.version++ и инвалидация потомков через обратный индекс based_on_children: HashMap<StyleId, Vec<StyleId>>). Так как большинство абзацев документа имеют пустые attrs и один из ~10 стилей, попадание в кэш > 99 % — резолв одного абзаца амортизированно O(1), холодный — O(d · a), d — глубина цепочки, a — число атрибутов.

Потокобезопасность: кэш — на поток раскладки (без блокировок); результаты — Arc<ResolvedStyle>, разделяются между потоками. Инвалидация по sheet.version делает старые ключи недостижимыми, LRU их вытесняет.

2.3 Тесты

• Эквивалентность с эталоном: для корпуса docx сравнение R(N) с значениями, которые Word записывает в w:rPrChange/settings (через tools/corpus-ref --dump-styles), на 500 файлах.
• Свойства: resolve детерминирован (два резолвера → равные результаты); изменение стиля-предка меняет потомков и только их; toggle-свойства: bold(style A: on) ∘ bold(style B basedOn A: on) = off.
• Производительность: 100 000 резолвов на 20 стилях < 20 мс при горячем кэше.

3. Адресация узлов и стабильные ID

3.1 UUIDv7 и монотонность

Генератор (meridian-core::id): 48 бит мс + 12 бит счётчика + 62 бита xorshift64*; при одной миллисекунде счётчик растёт, при переполнении (4096) время сдвигается на 1 мс вперёд; при уходе часов назад используется последнее время. Гарантии: строгая монотонность в процессе, уникальность между процессами с вероятностью коллизии < 2⁻⁶² на пару при одинаковой мс. Сложность O(1), блокировка — Mutex на ~30 нс.

3.2 Детерминированные ID при импорте

import_id(path, content) = v7_from_parts(
    unix_ms = IMPORT_EPOCH_MS,                        # константа 2026-01-01: все импортные ID в прошлом → сортируются раньше новых
    seq     = blake3(path)[0..12 бит],
    rand    = blake3(path ‖ content_hash)[0..62 бит])

path — структурный путь в исходном формате (word/document.xml#/w:body/w:p[17]), content_hash — хэш содержимого узла без детей. Повторный импорт того же файла даёт те же ID (сравнение версий, повторное открытие после сбоя без истории); два одинаковых абзаца различаются путём. Коллизии в пределах документа проверяются при импорте (HashSet), при коллизии — к rand прибавляется индекс.

3.3 Пути и разрешение

NodePath = Vec<(NodeId, u32)>; resolve(path): спуск от корня по индексам с проверкой children[i] == id (O(глубина)); при несовпадении (документ изменился) — поиск id по хэш-карте (O(1)) и перестроение пути. Текстовые позиции TextPos { node, byte } переживают правки через StickyIndex Yrs (§5.4) либо, вне CRDT, через подписку на TextInsert/TextDelete того же абзаца (O(1) обновление на операцию, список подписчиков — курсоры, закладки, комментарии, результаты поиска).

3.4 Тесты

Монотонность 5 000 ID (есть), переполнение счётчика (есть), детерминизм импорта (два прогона → равные ID), разрешение пути после перемещения узла, миграция TextPos через 10⁴ случайных правок (позиция указывает на тот же символ).

4. Журнал операций и группировка undo

4.1 Применение транзакции

apply(doc, tx):
  inverse = []
  for op in tx.ops:                      # по порядку / in order
    inv = doc.apply_op(op)               # возвращает обратную операцию с «старыми» значениями
    inverse.push(inv)
  tx.inverse = reverse(inverse)          # обратный порядок для отката
  doc.version += 1
  emit(ChangeSet::from(&tx))             # для раскладки/UI: множество NodeId + диапазоны
  undo.push(tx) ; oplog.append(tx) ; crdt.apply(tx)

Каждая Op обратима локально: InsertNode ↔︎ RemoveNode(с сохранённым поддеревом), SetAttr(old), TextInsert ↔︎ TextDelete(с текстом), CellSet(old), MoveNode(old parent, old index). Сложность применения — сумма сложностей операций; построение обратной — O(размер удаляемых данных) (копия текста/поддерева).

4.2 Группировка undo

Группа = последовательность транзакций, отменяемая одним действием. Правила объединения новой tx с верхней группой:

Отмена: pop группу → применить inverse всех её транзакций в обратном порядке как одну tx с Origin::Undo → группа уходит в redo-стек; любая новая локальная tx очищает redo. Курсор восстанавливается из cursor_before первой транзакции группы. Сложность отмены — O(число операций группы).

4.3 Коалесценция в журнале

OpLog хранит транзакции как есть, но для автосохранения (§10) последовательные TextInsert в один абзац подряд сливаются в один кадр (TextInsert{at, "abc"}), что сокращает журнал в ~10 раз при наборе.

4.4 Тесты

Свойство «undo ∘ do = id» и «redo ∘ undo ∘ do = do» на случайных последовательностях операций (proptest, сравнение сериализованной модели); группировка набора слов ("Hello world" → 2 группы); удалённая транзакция закрывает группу; redo очищается новой правкой; восстановление курсора.

5. CRDT на Yrs

5.1 Представление

Yrs (YATA): каждый вставленный элемент — Item { id: (client, clock), left, right, origin, right_origin, content, deleted }; текст — цепочка Item с содержимым-строками (сливаются при последовательном наборе одним клиентом), карты — Item на ключ (последний по (clock, client) виден), массивы — цепочки. Состояние документа описывает state vector SV = {client → clock} — максимальный виденный clock каждого клиента; удаления — delete set DS = {client → интервалы clock}.

5.2 Слияние

Обновление U (lib0 v2) содержит элементы и DS. Интеграция элемента: по origin/right_origin найти позицию среди уже существующих соседей; конфликт одновременных вставок в одну позицию решается правилом YATA — порядок по client среди элементов с одинаковым origin (детерминированно у всех участников). Элементы, зависимости которых ещё не получены (clock предшественника > SV[client]), откладываются в pending до прихода недостающих обновлений. Сложность интеграции элемента — O(число конкурирующих соседей), обычно O(1); обмен состояниями — SyncStep1(SV) → SyncStep2(diff(U, SV)) за O(|diff|).

Применение к модели: события Yrs (observe_deep) дают дельты (insert/delete/retain для текста, set/remove для карт, вставки/удаления элементов для массивов) → транслятор строит Op с Origin::Remote → apply (§4) без записи в undo (кроме закрытия группы).

5.3 Сжатие истории

• GC удалённого содержимого: при gc = true удалённые элементы, не нужные ни одному сохранённому Snapshot (§5.4), теряют содержимое (остаётся «тень» с длиной для согласования позиций) — память ~8 Б/элемент вместо текста.
• Слияние элементов: соседние элементы одного клиента с последовательными clock объединяются (Yrs делает это при интеграции) — после набора абзаца из 500 символов остаётся 1–3 элемента.
• Компактация журнала history/log.yrs: при превышении 10 МБ или 10 000 обновлений в файл пишется одно обновление encode_state_as_update(SV_0) (полное состояние, с учётом GC) + помечаются неактуальные чанки; старые чанки удаляются после успешной записи (§8.3 архитектуры о форматах MOP).
• База + дельты для Sheets — 03-architecture.md §5.2.

5.4 Снимки и версии

Snapshot = (SV, DS) — O(число клиентов + число интервалов удалений). Восстановление состояния на момент снимка: Doc::from_snapshot проходит элементы и считает видимыми те, у которых clock < SV[client] и которые не в DS снимка (требует несобранных GC элементов до этой точки, поэтому GC ограничен самым старым сохранённым снимком). Дифф двух версий: прогон текста обеих и Myers-дифф по абзацам (O((N+M)·D), D — размер изменений), внутри изменённых абзацев — посимвольный Myers с ограничением 10 000 символов (дальше — «абзац заменён»); дерево узлов — сравнение по NodeId (O(m)) с классификацией «добавлен/удалён/перемещён/изменён».

5.5 Тесты

• Сходимость: N клиентов (2–8) с случайными операциями и случайным порядком доставки → одинаковый текст (proptest, 1 000 итераций). Пример: клиент A вставляет «X» в позицию 3, клиент B одновременно удаляет 2..5 → у обоих результат с «X» на месте удалённого диапазона (YATA сохраняет вставку).
• Undo не трогает чужое: A печатает «abc», B печатает «def» в конец, A делает undo → остаётся «def».
• Компактация не меняет состояния: state(before) == state(after compaction) по хэшу.
• Снимок: восстановление версии даёт байт-в-байт текст, записанный при создании версии.
• Таблицы: 1 М ячеек база + 10 000 правок → память Yrs < 5 МБ; вставка строки двумя клиентами одновременно → обе строки присутствуют, порядок одинаков у всех.

6. Список отображения и инвалидация

6.1 Построение

build_page_dl(page):
  dl = DisplayList::new()
  for block in page.blocks:                         # абзацы, таблицы, фигуры в порядке z-index
    if let Some(cached) = block_dl_cache.get(block.id, block.layout_version):
      dl.append_translated(cached, block.origin)     # копия команд со сдвигом, O(c_block)
    else:
      sub = render_block(block)                      # глифы, линии, заливки; O(размер блока)
      block_dl_cache.insert(block.id, block.layout_version, sub.clone())
      dl.append_translated(sub, block.origin)
    dl.index.insert(block.bbox, cmd_range)           # R-tree по блокам, не по командам
  return dl

append_translated не трансформирует координаты по одной: добавляет Transform(translate) + команды + Restore; глифы хранятся в одном плотном Vec<Glyph> (SoA: glyph_ids: Vec<u16>, positions: Vec<[f32;2]>). R-tree (rstar) — bulk-load за O(b log b) по b блокам страницы, запрос видимой области — O(log b + ответ).

6.2 Распространение «грязи»

on_changeset(cs):                                   # из apply() §4
  for node in cs.nodes: mark_dirty(block_of(node))  # абзац/таблица/фигура; O(1) через индекс node → block
  schedule(layout_pass, priority = Visible if any dirty block visible else Background)

layout_pass():
  first = min_dirty_block_by_flow_order()
  pos = first.flow_position_before
  for block in flow.from(first):
    new_layout = layout(block, pos)                  # пересчёт только изменённых; остальные — сдвиг
    dirty_rect |= old_bbox(block) ∪ new_bbox(block)
    pos = new_layout.end
    if !block.dirty && new_layout.start == old_start(block): break   # ранний выход: дальше ничего не сдвинулось
  invalidate_tiles(dirty_rect)

Ранний выход — ключевое свойство: вставка символа в абзац, не меняющая число строк, стоит O(абзац); изменение числа строк — O(до конца страницы или до первого блока, чья позиция совпала); вставка страницы — O(остаток документа), но в фоне и с приоритетом видимого (§17).

6.3 Сложность и тесты

Построение DL страницы при горячем кэше блоков — O(c) копирования; хит-тест точки — O(log b) по R-tree + O(строк абзаца) внутри блока. Тесты: инкрементальная раскладка даёт тот же DL, что полная (.dl.txt равны) на корпусе после случайных правок; dirty_rect покрывает все изменившиеся пиксели (сравнение растров до/после по маске); ранний выход срабатывает на вставке символа в середине 100-страничного документа (< 2 мс).

7. Тайловый кэш

struct TileKey { page: u32, tx: u16, ty: u16, scale_q: u16 /* масштаб·64 */, theme: u8 }
struct TileCache { map: HashMap<TileKey, TileSlot>, lru: LinkedList<TileKey>, bytes: usize, limit: usize }

fn get_or_schedule(&mut self, key: TileKey, dl: &DisplayList) -> TileState {
    if let Some(slot) = self.map.get_mut(&key) { self.lru.touch(key); return slot.state(); }   // O(1)
    self.scheduler.submit(RasterJob { key, cmds: dl.index.query(key.rect()), priority: Visible });
    TileState::Pending(fallback: self.nearest_scale(key))   // ближайший масштаб для немедленного показа
}
fn invalidate(&mut self, page: u32, rect: RectPx) {       // из §6.2
    for key in self.keys_intersecting(page, rect) { self.map.remove(&key); }   // через per-page сетку, O(затронутых тайлов)
}
fn insert(&mut self, key: TileKey, tex: Texture) {
    while self.bytes + tex.bytes() > self.limit { let k = self.lru.pop_oldest(); self.bytes -= self.map.remove(&k).bytes(); }
    self.bytes += tex.bytes(); self.map.insert(key, TileSlot::Ready(tex)); self.lru.push(key);
}

Предвыборка: после кадра планируются тайлы на 1 экран по направлению прокрутки с приоритетом Background; при смене направления очередь очищается (cancel_pending). Квантование масштаба: scale_q = round(scale·64); во время жеста зума рисуются тайлы ближайшего готового масштаба с билинейной интерполяцией, точные тайлы запрашиваются после 80 мс покоя. Память тайла — 256·256·4 = 256 КБ; лимит 512 МБ = 2 048 тайлов ≈ 16 экранов 4K.

Тесты: LRU вытесняет самые старые; инвалидация прямоугольника удаляет ровно пересекающие тайлы; после invalidate + get тайл перерисован (хэш пикселей изменился); бенч: прокрутка 100 страниц без кэш-промахов на видимых тайлах при включённой предвыборке.

8. Детект формата файла

Расширение — только подсказка; решает содержимое. Порядок: магические байты → контейнер → содержимое → текстовые эвристики → расширение как tie-breaker.

detect(bytes: &[u8; ≤ 64 KiB], ext: Option<&str>) -> FormatId:
  match bytes:
    "PK\x03\x04" | "PK\x05\x06" → zip_detect(bytes)
    "\xD0\xCF\x11\xE0\xA1\xB1\x1A\xE1" → cfb_detect()         # doc/xls/ppt/msg/vsd: по именам потоков
    "%PDF-" (в первых 1024 байтах) → Pdf
    "{\\rtf" → Rtf
    "\x89PNG\r\n\x1A\n" → Png ; "\xFF\xD8\xFF" → Jpeg ; "RIFF....WEBP" → WebP ; "GIF8" → Gif
    "BM" → Bmp ; "II*\0" | "MM\0*" → Tiff ; "\0\0\x01\0" → Ico ; "8BPS" → Psd ; "....ftypheic|avif" → Heic/Avif
    "<?xml" | "<" с корнем:
        "office:document" → ODF flat ; "urn:meridian:office:<app>" → MOP flat ; "pkg:package" → OOXML flat (чтение)
        "svg" → Svg ; "math" → MathML ; "FictionBook" → Fb2 ; "html"|"HTML"|"!DOCTYPE html" → Html
    "From " | "Return-Path:" | "Received:" → Mbox/Eml (Eml, если нет "From " в начале)
    "BEGIN:VCALENDAR" → Ics ; "BEGIN:VCARD" → Vcf
    "\x00\x01\x00\x00Standard Jet DB" | "Standard ACE DB" → Mdb/Accdb
    "SQLite format 3\0" → Sqlite (→ Mbx, если есть таблица meridian_manifest)
    "!<arch>" | "\x1F\x8B" → не документ
    иначе → text_detect(bytes, ext)

zip_detect(bytes):                                  # читаем центральный каталог первых 64 КБ или весь файл по требованию
  if первая запись == "mimetype" (stored): → по значению ("application/vnd.meridian.write" → Mwx; "application/vnd.oasis.opendocument.text" → Odt; …)
  if есть "[Content_Types].xml": по частям "word/document.xml" → Docx (macro → Docm по "vbaProject.bin"; шаблон по ContentType),
     "xl/workbook.xml" → Xlsx/Xlsm/Xltx ; "ppt/presentation.xml" → Pptx ; "visio/document.xml" → Vsdx
  if есть "META-INF/manifest.xml" без mimetype → ODF по корню content.xml
  if есть "Index/Document.iwa" | "Index/" + "Metadata/" → iWork (Pages/Numbers/Keynote по BuildVersionHistory.plist)
  if есть "mimetype" == "image/openraster" → Ora ; "META-INF/container.xml" → Epub ; "Document.xml"+"Index" → Key
  иначе → Zip (не документ)

text_detect(bytes, ext):
  decode: BOM → UTF-8/16; иначе UTF-8 valid? → UTF-8; иначе по статистике байтов → cp1251/koi8-r/cp866 (для ru), latin1
  if начинается с "---\n" или много "# " / "**" / "](": → Markdown (score ≥ 3)
  delimiter sniff (первые 20 строк): кандидаты [",", ";", "\t", "|"]; выбрать тот, у которого число вхождений
     одинаково в ≥ 80 % строк и > 0 → Csv/Tsv (Csv с разделителем в метаданных)
  if ext ∈ {tex} и есть "\documentclass" | "\begin{document}" → Tex
  иначе → PlainText

Сложность O(64 КБ) на файл; для ZIP — чтение EOCD с конца (§9) и имён каталога (O(число записей)). Тесты: таблица «байты → формат» (100 кейсов, включая обманчивые расширения .docx с RTF внутри), все файлы корпуса детектируются как их format в .toml, CSV-сниффер на 50 образцах с разными разделителями и кавычками.

9. Потоковый ZIP

open(file):
  size = file.len(); tail = read(file, max(0, size-66_000)..size)      # EOCD 22 Б + комментарий ≤ 65 535
  eocd = rfind(tail, "PK\x05\x06") else Err(Corrupt)
  if eocd.entries == 0xFFFF || eocd.cd_offset == 0xFFFF_FFFF:         # ZIP64
      locator = find(tail, "PK\x06\x07") ; eocd64 = read_at(locator.eocd64_offset)
  cd = read(file, cd_offset..cd_offset+cd_size)                        # центральный каталог целиком (≤ 100 000 записей ⇒ ≤ ~10 МБ)
  entries = parse_cd(cd) → Vec<Entry{name, method, crc, csize, usize, local_offset, flags}>
  проверить: имена без "..", без абсолютных путей, без дубликатов; сумма usize ≤ 4 ГБ; usize/csize ≤ 200 (zip-бомба)
  index = HashMap<name, idx>

read_entry(e) -> impl Read:
  local = read_at(e.local_offset, 30) ; data_start = local_offset + 30 + local.name_len + local.extra_len
  match e.method: 0 (stored) → CrcReader(Slice(mmap[data_start..+csize]))  # без копии
                  8 (deflate) → CrcReader(Inflate(Slice(…)))               # потоково, буфер 64 КБ
                  иначе → Err(Unsupported)
  CrcReader на EOF сравнивает crc32 с e.crc → Err(Corrupt) при расхождении

Для флага 3 (data descriptor: размеры после данных) используем значения из центрального каталога — они всегда есть. Шифрованные записи (ZipCrypto/AES) → Unsupported с подсказкой (документные шифрования — на уровне формата, §8.6 архитектуры). Запись: ZipWriter::start_entry(name, method) → Write → finish_entry() считает CRC и размеры, пишет local header заранее с флагом 3 и data descriptor после данных (потоково, без seek) или, если цель seekable, патчит заголовок (без descriptor — лучше для старых читателей). mimetype — первой, stored, без extra. Сложность: открытие O(E) по числу записей, чтение записи O(размер), память — каталог + буфер 64 КБ + mmap.

Тесты: round-trip 1 000 случайных пакетов (proptest: имена, размеры 0..10 МБ, методы); ZIP64 с записью 5 ГБ (ночной); обрезанный файл → Corrupt без паники; zip-бомба 42.zip → отказ по лимиту; совместимость — пакеты читаются unzip, 7z, Word (для docx).

10. Журнал автосохранения

Формат journal.bin: заголовок MRDJ + u16 version + u128 doc_id + u64 base_seq (seq снимка), далее кадры:

frame := u32 len | u32 crc32c(payload) | payload
payload := CBOR { seq: u64, ts_ms: u64, tx_id: uuid, origin: u8, ops: [Op…] }   # ops — коалесцированные (§4.3)

writer (поток автосохранения):
  on_transaction(tx): queue.push(tx); timer.arm(2 s, coalesce)       # debounce, но не дольше 10 с от первой правки
  on_timer(): batch = queue.drain(); frame = encode(coalesce(batch)); file.write_all(frame); file.sync_data()
  if frames_since_snapshot ≥ 1000 || bytes ≥ 16 MiB || elapsed ≥ 5 min: schedule(snapshot)
snapshot():                                                           # по снимку модели (§4.5 архитектуры), фон
  write MOP → snapshot.mop.tmp ; fsync ; rename → snapshot.mop ; journal = new(base_seq = last_seq) ; remove old journal

recover(dir):
  doc = open(snapshot.mop) or empty
  for frame in journal: if crc_ok(frame) && frame.seq == expected: apply(frame.ops); expected += 1 else break
  report(recovered_through = expected-1, lost = tail present && !crc_ok)

Ошибки диска (ENOSPC, EIO) → автосохранение отключается с баннером «не удаётся сохранить резервную копию»; журнал на другой FS не делается. Шифрование кадров (ChaCha20-Poly1305 с nonce = seq) — если документ защищён паролем. Стоимость кадра — O(размер операций), fsync раз в 2 с; при наборе — ~200 Б/с.

Тесты: обрезание журнала в каждой байтовой позиции последнего кадра → восстановление до предыдущего кадра без паники; порча байта в середине → восстановление до кадра перед ним, остальные игнорируются (не применяются «через дыру»); снимок + журнал = полное состояние (хэш модели); потеря питания имитируется O_DIRECT-тестом на CI Linux.

11. Хэш-отпечаток устройства

Только алгоритм клиента; сервер — в 10-licensing-accounts.md.

Компоненты (каждый нормализуется: trim, lowercase, пустое → отсутствует):

Персональных данных нет (имена пользователей/хостов не используются). Отпечаток:

component_hash_i = sha256(salt_install ‖ "meridian-fp-v1" ‖ i ‖ normalized_value_i)   # 32 Б каждый; salt_install — 16 случайных байт установки (P6 в 10-licensing-accounts.md)
fingerprint = { v: 1, parts: [Option<[u8;32]>; 5] }                                  # хранится в лицензии и запросе активации
device_id  = sha256(concat(parts_present_sorted_by_index))[0..16]                     # короткий id для UI/портала (`fingerprint_hash` в .mlic)
match(stored, current) = count(i : stored[i] == current[i], оба присутствуют) ≥ 3 && stored[1] == current[1] или stored[2] == current[2]

Правило совпадения терпит замену диска или сетевой карты (пользователь меняет железо), но требует совпадения ОС-идентификатора или платы; смена ≥ 3 компонентов → повторная активация (онлайн или через портал). Виртуальные машины (детект по Win32_ComputerSystem.Model/DMI «VMware/VirtualBox/QEMU») — помечаются vm = true; политика лицензий для ВМ — серверная. Сложность: 5 системных вызовов при старте (< 20 мс), кэш на сессию.

Тесты: нормализация (регистр, пробелы); совпадение при замене одного и двух компонентов; несовпадение при трёх; стабильность между запусками (мок-источники); отсутствующие компоненты не ломают сравнение; device_id детерминирован и не раскрывает компоненты (нет обратимости — только хэши).

12. Полнотекстовый индекс (tantivy) и подсветка

Индекс Hub (недавние и папки пользователя), Notes (книжки), Mail (письма) — один движок, разные индексы (<data>/index/<scope>/).

schema: doc_id (STRING, stored, fast) | path (STRING, stored) | title (TEXT, stored) | body (TEXT) |
        app (STRING, fast) | modified (DATE, fast) | tags (TEXT) | lang (STRING)
tokenizer "meridian": SimpleTokenizer → RemoveLong(40) → LowerCaser → AsciiFolding/Unicode NFKC-fold →
        Stemmer(по lang: ru, en, de, fr, es, …; snowball) ; для CJK — ngram(2..3)
indexing: наблюдатель FS (notify) → очередь (debounce 1 с) → meridian-convert --text (в песочнице, лимит 2 МБ текста) →
        IndexWriter.add_document ; удаления — по doc_id ; commit раз в 5 с или 100 документов ; merge policy LogMerge
query: QueryParser по полям [title^3, body, tags^2] ; фразы "…" ; фильтры app:, modified:[..] ; опечатки — FuzzyTermQuery(1) при 0 результатов
snippet: SnippetGenerator(body, max 160 символов) → фрагмент с <b>…</b> по позициям токенов

Подсветка в открытом документе использует не tantivy, а поиск §13 по модели (точные байтовые позиции → TextPos → раскладка → прямоугольники строк → слой оверлеев). Сложность: индексация O(размер текста), запрос O(log N + результаты); 10 000 документов (~2 ГБ текста) → индекс ~400 МБ, запрос < 50 мс.

Тесты: русская морфология («документы» находит «документ»), фразовый поиск, фильтр по приложению, удаление файла убирает его из результатов, переиндексация после изменения, лимит текста не ломает индекс.

13. Поиск с нормализацией Unicode

Задача: найти вхождения запроса в тексте абзаца с опциями «учитывать регистр», «учитывать диакритику», «слово целиком», «регулярное выражение», «похожие формы» (ё/е, кавычки, дефисы) и вернуть байтовые позиции в исходном тексте.

normalize(text) -> (norm: String, map: Vec<u32>):          # map[i] = байтовое смещение в исходнике для norm[i]
  for (orig_off, ch) in text.char_indices():
    for nch in nfd(ch).filter(not combining if ignore_diacritics).map(casefold if ignore_case).map(unify):
        # unify: ё→е, "«»„“”"→'"', "‐‑–—"→'-', NBSP→' ', fi→fi (NFKC для совместимых)
        push(nch) ; map.push(orig_off)     # все байты nch указывают на начало исходного символа
  map.push(text.len())

find_all(text, query, opts):
  (hay, map) = normalize(text) ; needle = normalize(query).0
  matcher = if opts.regex { Regex::new(with_flags(needle)) } else { memchr::memmem::Finder(needle) }   # Two-Way, O(n+m)
  for (s, e) in matcher.find_iter(hay):
    if opts.whole_word && !(is_boundary(hay, s) && is_boundary(hay, e)): continue   # UAX#29 word boundaries
    yield (map[s], map_end(e))             # map_end: смещение конца исходного символа, покрывающего hay[e-1]

Совпадения, начинающиеся или заканчивающиеся внутри одного исходного символа (например, fi → fi, запрос «f»), расширяются до границ исходного символа. Замена: replace(range, text) через транзакции §4 с корректировкой последующих позиций (StickyIndex/подписка §3.3) — замена всех N вхождений в абзаце за O(n + N). Поиск по документу — обход абзацев в порядке потока, лениво (итератор), с кэшем нормализации на абзац (инвалидируется по layout_version). Для регулярных выражений — крейт regex (линейное время, без катастрофического отката), размер скомпилированного автомата ограничен 10 МБ.

Тесты: «Résumé» находится по «resume» без диакритики; «ёлка» по «елка»; fi по «fi» с корректными границами; регистр: «Σ» и «ς/σ» при casefold; слово целиком не находит «кот» в «кота»; позиции указывают на исходные байты (слайс исходника == исходный текст совпадения); 10 МБ текста — поиск < 50 мс.

14. Буфер обмена

14.1 Форматы

14.2 Алгоритмы

copy(selection):
  frag = model.extract(selection)                       # поддерево с материализованными стилями, O(размер)
  offer(Meridian.Fragment → encode_cbor(frag))          # сразу
  offer(text/plain → frag.to_plain_text())              # сразу (дёшево)
  offer_delayed(RTF, HTML, OOXML, PNG(для фигур))        # по запросу системы: render через кодеки в фоне (§17)
  hub.clipboard_history.push(summary(frag))             # Hub хранит до 25 последних (Pro+), с превью

paste(target):
  avail = system.formats()
  for fmt in priority_list(target.kind):                # Write: MOP > OOXML > RTF > HTML > text ; Sheets: MOP > OOXML > TSV/CSV > HTML > text
    if fmt in avail: data = system.get(fmt); frag = decode(fmt, data) (в песочнице для чужих форматов); break
  frag = sanitize(frag)                                 # §14.3
  frag = adapt_styles(frag, target.doc, mode)           # mode: keep-source | merge | text-only (как в Office «параметры вставки»)
  doc.transaction("Вставка", |tx| tx.insert(target.pos, frag))

adapt_styles: стили фрагмента, одноимённые со стилями целевого документа, заменяются целевыми (merge), отсутствующие — добавляются с суффиксом (Heading 1 (2)) только при keep-source; прямое форматирование — resolve(source) − resolve(target) (§1.3). «Специальная вставка» показывает все доступные форматы.

14.3 Санитизация

HTML/RTF из внешних источников: удаление скриптов, событий, iframe/object/embed, внешних изображений (заменяются заглушкой с кнопкой «загрузить» — §10.1 архитектуры), ограничений нет только для data:-картинок известных типов. Фрагменты чужих форматов декодируются в codec-host (песочница). Текст из буфера проходит проверку на Unicode-трюки: двунаправленные переопределения (U+202E) показываются видимыми маркерами.

Тесты: матрица «источник × цель» (Write→Sheets, Sheets→Write, Slides→Draw, внешний Word/Excel/браузер через записанные дампы буфера), сохранение форматирования в keep-source, корректность text/plain для таблиц (TSV), delayed rendering не блокирует UI (вызывается в фоновом потоке, таймаут 5 с → только текст).

15. Drag-and-drop

drag_start(selection):                                  # внутренний источник
  payload = { origin_doc, selection_ref (NodeId/диапазоны), formats: same as copy }
  system.start_drag(payload, preview = render_thumbnail(selection, ≤ 256 px))   # Qt QDrag с теми же MIME

drag_over(point):                                        # цель — холст
  hit = dl.index.query_point(point) → block → точная позиция (строка/символ/ячейка/слот фигуры)  O(log b + строки)
  indicator = caret_or_outline(hit) ; autoscroll if point within 24 px of edge (скорость ∝ расстоянию)
  effect = if same_doc && !ctrl { Move } else { Copy }

drop(point, payload):
  if payload.is_internal && effect == Move:
      tx: Op::MoveNode / TextDelete+TextInsert (один Composite — одна группа undo), позиции корректируются,
      если цель после источника (вычесть удалённую длину)
  else: paste(target = hit, data = payload)              # §14.2 с тем же приоритетом форматов
  external files: по формату — документ → открыть в новом окне (или вставить как объект при Alt), картинка →
      вставить, шрифт → предложить установить (Hub), .mxt → установить расширение (с подтверждением)

Внешние файлы приходят как text/uri-list/CF_HDROP; содержимое читается кодеками в песочнице. На Wayland перетаскивание между окнами разных процессов работает через портал — Qt делает это прозрачно. Тесты: перемещение абзаца вниз/вверх в том же документе (позиции корректны), перетаскивание ячеек с формулами (ссылки корректируются как в Excel: относительные сдвигаются), внешняя картинка вставляется с привязкой к абзацу, автопрокрутка останавливается при уходе курсора.

16. Печать

16.1 Разбиение на страницы

Экранная раскладка уже постраничная (Write) или задаёт область (Sheets: PrintArea, разрывы, масштаб «вписать в N страниц»; Slides: раздаточные N-up). Печать берёт PageSetup документа и переопределения задания:

print_pages(doc, job):
  setup = doc.page_setup.override(job: paper, orientation, margins ≥ printer.hardware_margins, scale)
  if setup != doc.page_setup: layout = relayout(doc.snapshot(), setup)    # фон, снимок; экран не трогаем
  pages = select(layout.pages, job.range)                                  # 1-5,8 ; чётные/нечётные ; обратный порядок
  for sheet in n_up(pages, job.pages_per_sheet, job.duplex):             # N-up: трансформации страниц на листе
      dl = compose(sheet.pages.map(build_page_dl))                         # §6.1, со сдвигом/масштабом
      yield dl

Sheets: разбиение на страницы — по накопленным ширинам столбцов/высотам строк (prefix sums, O(log n) на границу), заголовки печати повторяются, масштаб «вписать» — бинарный поиск по масштабу 10..100 % (≤ 7 раскладок).

16.2 Вывод

Принтер с PDF/PostScript/XPS-путём (CUPS, macOS, Windows XPS): DisplayList → SkDocument постранично, потоком в спулер (не держим весь документ в памяти, ≤ 1 страница + шрифты). Принтер без векторного пути (Windows GDI-only, некоторые сетевые): растеризация полосами:

rasterize_banded(dl, dpi = min(printer.dpi, 600), band_px = floor(64 MiB / (width_px * 4))):
  for y in (0..height_px).step(band_px):
      surface = cpu_surface(width_px, min(band_px, height_px - y))
      surface.translate(0, -y) ; backend.render(dl, surface)             # Skia отсекает команды вне полосы по R-tree §6.1
      spooler.write_band(surface.pixels(), y)                             # StretchDIBits / CUPS raster

Текст при растеризации — без хинтинга и субпикселей, grayscale AA; цвет — sRGB → профиль принтера только при наличии ICC (иначе как есть). Сложность — O(c · число полос) в худшем случае, фактически O(c) благодаря отсечению. Предпросмотр — те же dl в тайловый кэш с эмуляцией непечатаемых полей.

Тесты: .dl.txt печатной страницы == экранной при одинаковом PageSetup; N-up 2/4/6 даёт верные трансформации (снимки); полосный растр == цельный растр (сравнение пикселей); печать 1 000 страниц держит память < 300 МБ.

17. Планировщик фоновых задач

pub enum Priority { Interactive = 0, Visible = 1, Background = 2, Idle = 3 }
pub struct Task { id: TaskId, priority: Priority, cancel: CancellationToken, deadline: Option<Instant>,
                  run: Box<dyn FnOnce(&Ctx) -> Outcome + Send> }
pub struct Scheduler { queues: [SegQueue<Task>; 4], pool: rayon::ThreadPool /* n = cores-1, ≥ 2 */,
                       io: Thread /* отдельный поток для fs/ipc */, running: DashMap<TaskId, Handle> }

impl Scheduler {
    pub fn submit(&self, t: Task) -> Handle { self.queues[t.priority as usize].push(t); self.notify(); handle }
    fn worker_loop(&self) {
        loop {
            // строгий приоритет с антиголоданием: 1 из 8 выборов берёт следующий уровень, если он непуст
            let task = self.pick_with_aging();
            let ctx = Ctx { cancel: task.cancel.clone(), budget: Budget::new(4ms) };
            match catch_unwind(|| (task.run)(&ctx)) { … }  // паника задачи не роняет пул
        }
    }
}
// Кооперативность: длинные задачи проверяют ctx.should_yield() каждые ~4 мс (счётчик итераций + Instant)
// и возвращают Outcome::Yield(continuation), чтобы Interactive-задачи не ждали.

Правила:

• Interactive — результат нужен к следующему кадру (хит-тест, автодополнение, раскладка строки с курсором); выполняется вне очереди на выделенном потоке «interactive» (не в rayon-пуле).
• Visible — раскладка/растеризация видимого; Background — остальной документ, индексирование, автосохранение (снимок), delayed clipboard; Idle — компактация текста (§1.2), GC истории, предвыборка тайлов.
• Отмена — CancellationToken (атомарный флаг + уведомление); задача обязана проверять его на границах итераций; при отмене результат отбрасывается. Переподача той же работы (новый layout_pass) отменяет предыдущую по ключу TaskKey (дедупликация).
• Дедлайны: при приближении дедлайна Visible-задачи её приоритет временно поднимается (наследование при ожидании в Interactive).
• Ограничение потоков: пул = cores − 1 (минимум 2, максимум 16); на ноутбуках при питании от батареи — cores/2; IO-задачи не занимают пул (отдельный поток + async для сети в Hub).
• Память: задачи объявляют ожидаемый объём (Task::memory_hint), планировщик не запускает задачи сверх бюджета MemoryPressure (§18.3).

Сложность: submit/pick — O(1) амортизированно (lock-free очереди), дедупликация — O(1) по хэшу ключа. Тесты: приоритеты соблюдаются (Interactive всегда стартует < 1 мс при загруженном пуле); антиголодание (Idle выполняется при постоянном потоке Visible); отмена прерывает длинную задачу ≤ 8 мс; паника в задаче не ломает пул; детерминизм результата не зависит от числа потоков (раскладка на 1 и 8 потоках даёт равный .dl.txt).

18. Память

18.1 Арены с генерационными индексами

pub struct Arena<T> { slots: Vec<Slot<T>>, free: Vec<u32>, generation: Vec<u32>, live: usize }
#[derive(Clone, Copy, PartialEq, Eq, Hash)] pub struct Idx { index: u32, generation: u32 }
impl<T> Arena<T> {
    pub fn insert(&mut self, v: T) -> Idx {                    // O(1): переиспользуем свободный слот
        if let Some(i) = self.free.pop() { self.slots[i as usize] = Slot::Full(v); self.generation[i as usize] += 1; … }
        else { self.slots.push(Slot::Full(v)); self.generation.push(0); … }
    }
    pub fn get(&self, idx: Idx) -> Option<&T> {                 // O(1); устаревший индекс → None, а не чужой объект
        (self.generation[idx.index as usize] == idx.generation).then(|| self.slots[idx.index as usize].as_ref())
    }
    pub fn remove(&mut self, idx: Idx) -> Option<T> { … self.free.push(idx.index) … }
}

Узлы, абзацы, фигуры, стили — в аренах по типу; NodeId → Idx через HashMap (FxHash). Арены дают локальность (обход детей — последовательные слоты при импорте), отсутствие Rc<RefCell>-циклов, дешёвые снимки (персистентный вариант PArena<T> с Arc-чанками по 1 024 слота: copy-on-write чанка при записи, клон за O(число чанков)).

18.2 Интернирование строк

Interner: HashMap<Arc<str>, Symbol(u32)> + Vec<Arc<str>>; интернируются имена стилей, ключи Custom-атрибутов, имена шрифтов, имена листов, ключи CBOR. Сравнение — по u32, хэш — u32; память на символ — 24 Б + строка. Интернер на документ (не глобальный) — детерминированные номера при повторном открытии (порядок первого появления), что важно для воспроизводимых сериализаций.

18.3 Лимиты и давление памяти

MemoryPressure: Normal → High (RSS > 70 % лимита процесса или сигнал ОС) → Critical (> 90 %)
on High:     tile cache → 25 %, shape cache → 25 %, block DL cache → только видимые ± 2 страницы,
             декодированные изображения → только видимые, миниатюры → сброс
on Critical: + отменить Background/Idle задачи, отказ открывать новые документы в этом процессе (Hub откроет в новом),
             + предупреждение пользователю, если документ > 1 ГБ в памяти

Сигналы ОС: Windows CreateMemoryResourceNotification, macOS DISPATCHSOURCE_MEMORYPRESSURE, Linux PSI (/proc/pressure/memory) + cgroup.events. Лимит процесса — настраиваемый ([performance] memory_limit_mb), по умолчанию 50 % физической памяти. Большие растры (Paint, >100 МП) — тайловые с вытеснением на диск (<cache>/tiles/), mmap-обратно.

Тесты: арена — get по устаревшему Idx возвращает None; 10⁶ вставок/удалений без роста slots сверх максимума живых; интернер даёт равные Symbol для равных строк и стабильные номера при повторной загрузке; имитация High сбрасывает кэши и RSS падает ≥ 30 % на тестовом документе с 200 картинками.

19. Детерминизм раскладки

Цель: одинаковый .dl.txt для одного документа на всех ОС/CPU/числе потоков. Правила и механизмы:

Фиксированная арифметика там, где нужны дроби: масштабные коэффициенты — рациональные (num, den) в i64 (mul_div), проценты — Permille/Percent100k, тригонометрия для поворотов фигур — табличная i32-фиксированная (sin/cos в 1/65536 с линейной интерполяцией по 1/60000°-углу) — чтобы повёрнутый прямоугольник имел одни и те же EMU-координаты у всех. Растровый вывод (f32) недетерминизма на уровне раскладки не создаёт: расхождения в последних битах f32 не меняют .dl.txt, а снимки сравниваются с порогом.

Проверка: CI сравнивает .dl.txt всех файлов smoke-корпуса между Linux, Windows и macOS (job determinism, ночной) — любое расхождение блокирует релиз; proptest-тест layout_is_pure — раскладка одного документа дважды в разных потоках даёт равный результат; бенч justify_distribute — O(g) и сумма равна R.

Приложение. Сводка сложностей