Архитектура текстового редактора

[ilovb]

Есть у меня крамольная мысль сваять текстовый редактор. Изначально мысль родилась на оберкоре в процессе поиска причины диких тормозов ЧК на больших неприлично раскрашенных документах. Тогда выяснилось, что причиной является архитектурная особенность текстовой подсистемы. Оказалось что система перед отображением текста сканирует документ снизу вверх в поисках линейки. Решение мягко сказать деревянное. Если поиск линеек закоментить, то тормоза практически пропадают. Но это еще не все... Пока я ковырял текстовую подсистему, то обратил внимание, что система далеко не так проста как может сначала показаться. В общем наворочено там не мало... Довольно сложно и не понятно зачем. На эту сложность и Сергей Губанов обращал внимание. Прикрутить свистоперделки к ней как в современных редакторах кода если не невозможно, то довольно сложно. Саму текстовую подсистему с наскока вкурить вообще нереально имхо. (это я над блэкбоксовой обозримостью стебаюсь   ) Т.е. приходится долго и упорно читать код самой подсистемы, чтобы быть уверенным что ты ее правильно используешь. Хорошего понимания как она работает похоже нет ни у кого (возможно я ошибаюсь конечно)
Ладно... о чем это я?!
Ах да.
Изначально я хотел сваять простенькую, но расширяемую текстовую модель типа нотепад (а остальное (форматирование там всякое) прикрутить в расширении этой модели). Оберкоровцы в последнем сраче мне это желание поубавили.
В общем на данный момент у меня осталось желание этим заняться, но не ради переделки текстовой подсистемы ЧК, а для общего развития так сказать. Если в итоге кому-то будет польза, то гуд, если нет то нет...

Опыта конечно нет в таких задачах, и супермЭном-вундеркиндом-одиночкой я себя не считаю. Некоторые мысли есть, но пока в процессе переваривания. Пытался в инете найти информацию на эту тему, но безрезультатно.

В общем прошу помочь соображениями и информацией по этой теме. Ну и стоит ли вообще велосипед городить? Ценный ли это опыт будет?
Если кто уже занимался подобной задачей, то поделитесь опытом плиз.

ps Во накатал то... уф...

[valexey]

Опыт он конечно опыт и ценный. На счет архитектуры расширяемого текстового редактора пока не подскажу (просто я не слишком понимаю что в нем должно быть - это составной документ, или как?). Но подскажу в сторону алгоритмов и структур данных для редактирования больших текстов: rope.

[DIzer]

По идее неплохо бы было иметь хотя бы специализированную компоненту для подсветки текста (раскраска  не нужна и возможностью подключения доп . приблуд вроде intellisensa , codecompletion) кода, частично идея была реализована С. Губановым - но до презентабельного уровня не доведено ... А вы рассматривали возможность внедрения  ГОТОВОГО компонента - вроде коровцы били себя в грудь что это реально  веры конечно никакой... пусть даже ПЛАТНОГО -что там 100$
это ГРОШИ по сравнением с возможностью получить КАЧЕСТВЕННЫЙ результат в ПРИЕМЛЕМОЕ время....

[DIzer]

пример http://www.econtrol.ru/syntedit.html

[ilovb]

Но подскажу в сторону алгоритмов и структур данных для редактирования больших текстов: rope.

Не ожидал, что вот так прям сразу мне ссылку дадут. Спасибо!

Вот я гуглер бестолковый 

[ilovb]

...просто я не слишком понимаю что в нем должно быть - это составной документ, или как?

Просто поддержка форматированных документов. Атрибуты текста, форматирование абзацев, вставка картинок и т.д. и т.п. Если текстовый редактор в ЧК, то конечно и вьюхи нужно поддерживать. Но это все в расширении модели. А базовая модель должна быть проста "как пробка". Т.е. должна быть возможность работать с простой моделью, на базе которой можно построить приличный редактор кода.

[trurl]

Не ожидал, что вот так прям сразу мне ссылку дадут. Спасибо!

Вот я гуглер бестолковый 

Собственно, в ББ и в Обероне та же структура для текстов.

[Губанов Сергей Юрьевич]

подскажу в сторону алгоритмов и структур данных для редактирования больших текстов: rope.

Мозги свернёшь пока поймёшь 

Я думаю такие сложные структуры были изобретены во времена когда оперативной памяти в компьютере было мало. Сейчас это не очень актуально, поэтому можно использовать более простую структуру данных -- двухсвязный список. Текст -- это двухсвязный список символов. Каждый символ имеет указатель на предыдущий и следующий символ текста, а так же указатель на атрибуты, ну и свой код.

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

Имея ввиду организацию двухсвязного списка на массиве структур получаем что-то вроде такого:

public struct Symbol
{
    public uint value; // код этого символа
    public uint attributes; // индекс в массиве атрибутов -- атрибуты этого символа
    public uint prev; // индекс в массиве символов -- предыдущий символ текста
    public uint next; // индекс в массиве символов -- следующий символ текста
}

public struct Attributes
{
    public uint font; // индекс в массиве шрифтов
    public uint size; // размер шрифта
    public uint color; // цвет символа
    public uint flags; // всякие флаги: жирный, наклонный, подчёркнутый, зачёркнутый...
}

В массиве атрибутов элементы лучше сделать уникальными, тогда можно будет легко вычислять равенство и неравенство аттрибутов имея лишь индексы массива: если индексы не равны, то и атрибуты не равны.

Расход памяти на символ - 16 байтов, то есть на документ из миллиона символов уйдёт 16 мегабайтов. Лет 20 назад за такое злодеяние программиста бы расстреляли, а сейчас нормально. Подумаешь каких-то там 16 мегабайт...

Ну, в общем, я думаю как-то так...

[valexey]

Это было изобретено не столько для экономии памяти, сколько ради сложности операций. Там все сложности (кроме build) O(log(n)), в списке же тот же search будет O(n).

[ilovb]

Собственно, в ББ и в Обероне та же структура для текстов.

Это точно? Я что-то не помню там такого 
Эта структура же в 1995 вроде опубликована была (по данным в Wiki)

Когда я копался в текстовой подсистеме ЧК, мне показалось что она использует линейный связанный список. Я не исключаю конечно что плохо смотрел 

Забавно. Это получается Вирт эту структуру раньше изобрел?!

[Губанов Сергей Юрьевич]

Это было изобретено не столько для экономии памяти, сколько ради сложности операций. Там все сложности (кроме build) O(log(n)), в списке же тот же search будет O(n).

А что там имеется в виду под словом search?

Для эффективного поиска подстрок нужно создать дополнительную структуру ("проиндексировать текст"). Эта дополнительная структура будет лежать рядышком и не отменять основную (не вместо, а вместе).

[Губанов Сергей Юрьевич]

Кстати, задача огромной важности которую ещё надо решить это организация механизма отмены совершённых правок (undo/redo).

[Vartovyj]

Было бы неплохо делать текстовый редактор вместе с IDE

[ilovb]

Вот еще пара ссылок:
http://www.ibm.com/developerworks/ru/library/j-ropes/
http://fprog.ru/2010/issue6/eugene-kirpichov-incremental-regular-expressions/

[Губанов Сергей Юрьевич]

Это было изобретено не столько для экономии памяти, сколько ради сложности операций. Там все сложности (кроме build) O(log(n)), в списке же тот же search будет O(n).

А что там имеется в виду под словом search?

Definition: Search(i): return the character at position i

То же мне сёрч. Для текстового редактора извлечение буквы находящейся в позиции i=1'234'567 не актуальна.  Куда актуальнее чтобы вставка/удаление подстрок выполнялась за О(1). Для текстов из миллионов букв, кстати, разница между O(1) и O(log(N)) может стать заметной, так что двухсвязный список символов рулит.