| пилите, Шура, пилите |
[Jan. 14th, 2022|07:05 pm] |
текстовый редактор наконец нарисовал в иксовом окошке страничку текста. а это обозначает, что большинство низкоуровневой механики (не только хранилище текстовых байтов — буфера, модификация текста и структур данных, навешиваемые оверлеи и всё такое — обрело пусть не конечную, но форму). и естественно, у меня получится emacs.
не то, чтобы можно было ожидать чего-то иного, когда в воображаемом ТЗ я видел: возможность открыть несколько отдельных фреймов для одного и того же текстового буфера; независимые, легко создаваемые и меняемые хайлайтеры; возможность цеплять к текстовым спанам произвольные атрибуты. это emacs и есть, в том числе и архитектурно.
собственно, сама архитектура очень простая: в самом низу верха лежит текстовый буфер. он реализован на piece table с aa-trees, но эту частную деталь никому знать не обязательно, наружу структура буфера не торчит, только API.
API буфера позволяет подцеплять к нему любые юзерские данные, и колбэки, которые будут вызываться при модификации буфера. этого, собственно, уже достаточно, чтобы сделать emacs.
то есть, всё-всё остальное — это просто «оверлеи», которые цепляются к буферу и апдейтят свои структуры данных, когда буфер поменялся. что именно делает оверлей — неважно: он может расцвечивать синтаксис, или держать наготове семантическое дерево текста, или, собственно, рисовать текст в окошке.
выделение памяти в движке редактора делается блоками по 4 кб, через mmap (memory manager mmap-ит, понятно, регионы побольше, но отдаёт только по 4 кб за раз). так что на пустой текстовый буфер уходит около 32 кб (сразу создаётся несколько пулов), но это некритично. память буфера освобождают только по своему уничтожению, но и это на практике неважно. зато отсутствие фрагментации хипа — гарантировано.
загрузка двух гигабайт текста (тупо дамп sqlite-базы на 200 мегов, который несколько раз сам к себе в конец дописан) занимает около секунды (быстрее из дисковых кэшей не добывается, лол, дофига memcpy), и примерно около секунды у редактора уходит на то, чтобы просканировать прочитаное и создать массив с длинами строк. после этого навигация по тексту мгновенная, переход на любую строку мгновенный, удаление и вставка текста мгновенные.
ну, то есть, переход по строкам — O(2*log n) от количества строк в тексте при худшем раскладе (их там почти три миллиона, например), сканирование строки побайтово — O(1) (амортизированое), изменение текста — до O(2*log n) в самом худшем раскладе.
если похожие O(2*log n) выглядят подозрительно — то это потому, что одна и та же стуктура данных. информация о строках тоже лежит в array-tree, что позволяет очень быстро (сильно меньше миллисекунд) находить как номер строки по байтовому смещению, так и байтовое смещение по номеру строки. апдейты массива строк — с обычной гарантией балансированого двоичного дерева.
естественно, никто тексты размером два гига редактировать не будет (emacs такое вообще прочитать не в состоянии, у него лимит 2^29; у меня 2^31); но в качестве стресс-теста очень полезно. если на таком не тормозит — то на остальном и подавно не будет.
бэкэнд пока чисто X11. консольный можно будет сделать потом, это несложно (X11 бэкэнд всё равно эмулирует терминал с моноширинным шрифтом). да, сделать всякие разные шрифты и стили текста можно, это просто чуть-чуть другой оверлей рендера, в движке ничего менять не придётся. но мне пока не надо.
в общем, процесс движется, и скоро надеюсь — как и полагается — продолжать разработку редактора уже в самом этом редакторе. |
|
|