FarColorer для Far 1.75 и Far 2

Поборов рекурсию и падения, можно выпустить новую версию плагина. Да и не просто для Far2 , а и еще для Far 1.75. Судя по сайту проекта, спрос на 1.75 большой.

Эти версии особенные еще и тем, что скорее всего они последние в своих линейках. Что-то дорабатывать для Far 1.75 желания нет, разве что баги поправить.  А Far2 умер в непотребном состоянии, надо сразу на 3 версию переходить.

Да и с Colorer надо что то делать. Хотя бы нумерацию версий привести к какому то порядку. Что-то типа   первая цифра - это версия фара, а остальное как получится. Бардак иначе получается.

Ну хватит слов, перейдем к делу.

Изменения схем

New:
- Python scheme completely rewritten (anatoly techtonik)
- add support Expect
Fixed:
- remove .cgi from Perl extensions, use first line for detection
- fix firstline of Python prototype to allow spaces in shebang
- fix comments in Tcl ( Nikita Retunsky)
- c# add #region/#endregion , get, set, yield

Colorer 1.0.3.1 для Far2

Изменения

1. Работа с очень длинными строками. Ранее падали или недокрашивали длинные строки.
   Если нужно ограничить длину строки для раскраски используйте параметр maxlinelength в настройках схем.
2. оптимизации и борьба с утечками в библиотеке.

Colorer 1.0.2.2 для Far 1.75 x86
Colorer 1.0.2.2 для Far 1.75 x64

Изменения

1. Работа с очень длинными строками. Ранее падали или недокрашивали длинные строки.
   Если нужно ограничить длину строки для раскраски используйте параметр maxlinelength в proto.hrc.
2. оптимизации и борьба с утечками в библиотеке.
3. увеличена скорость работы за счет хака far
4. убрана не используемая опция "Время до показа диалога отмены"
5. меню "Список функций" нормально вводятся в фильтр клавиши ":;-_~" , цифры с цифровой клавиатуры
6. исправлено отображение неверного числа схем в меню выбора схемы
7. исправлена ошибка работы "креста" при выборе типа раскраски
8. ошибка работы с диалогом настроек плагина в 64-битной версии, приводящая к падению Far
9. всякие мелочи

Опыт отказа от рекурсии. Happy end

Как оказалось, я был не прав по поводу того, что устранить потерю скорости не получится. При более внимательном рассмотрении увидел, что переменных класса CRegExp довольно таки много, а не одна. Соответственно им создавался отдельный стек. А это бага .... Ну ты лошара (с).

В общем после исправления этого момента потеря производительности стала незначительной. Так что Happy End

Попробовать изменения можно будет в новой версии плагина FarColorer 1.0.3.1

Опыт отказа от рекурсии

В интернете практически не освещена тема отказа от рекурсии в алгоритмах. Много статей и книг где рассказывается, что такое рекурсия, как ей пользоваться. Но вот как от неё избавится - почти ничего нет.

Итак, рекурсия - это вызов функцией самой себя. Всем известен алгоритм вычисления факториала, классика книг. Все красиво и элегантно, хоть циклом кажется и проще. А уж всевозможные алгоритмы анализа строки и работы с регулярными выражениями. Казалось бы, используй и радуйся.
Но не все так просто. Глубина рекурсии (как много раз функция может вызвать саму себя ) ограничена. Ограничена размером стека. Дело в том, что перед вызовом функцией самой себя, нужно сохранить значения всех локальных переменных, чтобы ими можно было воспользоваться после возвращения. А сохраняется это все в стек. И вот пока в стеке есть место, мы можем углубляться в рекурсию. Все глубже , глубже. Пока не выскочит ошибка - Stack overflow. И все , тушите свет.
Стандартная величина стека примерно 2 мб (для windows программ). Так давайте увеличим размер стека опциями компилятора, делов то. А на сколько увеличить, так чтобы было и не много и не мало? а если запросы растут со временем , постоянно перекомпилировать? А если у вас библиотека, которая использует стек вызвавшей её программы ? И вот тут то и понимаешь, что это не наш метод. Надо как то избавляться от рекурсии.
Вот с этим я и столкнулся в поддерживаемой мной библиотеке Colorer. Алгоритм разбора строки по регулярному выражению был рекурсивный. Так же был красив и пах. Но на длинных строках любил падать. Дай строку в 3000 символов и все, приехали. Надо было что то делать.
Единственным методом ликвидации рекурсии, который я нашел , это избавление от хвостовой рекурсии. Суть его в следующем - если рекурсивный вызов идет последним в функции, то функцию можно заменить на цикл. Факториал как раз является примером для этого.
Но у меня рекурсивных вызовов было очень много в функции. Часть можно было развернуть в цикл, но это совсем малая часть. Да и кстати, код был построен так, что в зависимости от результата вызова (функция возвращала bool значение) функция могла завершится или продолжить работу далее. А сама функция была циклом внутри которого switch.
Вот тут то приходит единственное оставшееся решение - а почему бы нам не воспроизвести рекурсивный вызов с помощью цикла и сохранения параметров? т.е. сделать это все вместо компилятора. Что нам для этого нужно:

1. список локальных переменных, которые нужно сохранить.
2. динамический список типа стека, в который мы будем сохранять значения локальных переменных, и извлекать от туда
3. после-рекурсионные действия , или action (не знаю как назвать это лучше)
4. цикл 

В начале остановимся на action. Каждый рекурсионный вызов в зависимости от результат приводил к return true, или return false, или return результат_функции, или к продолжению работы функции многими строками кода. Т.к. мы избавляемся от рекурсии в пользу цикла, то этот код нужно выполнить после завершения цикла для этого рекурсионного вызова. Т.е. когда цикл придет к return ... Потому все такие ситуации выделяем в один switch, присваивая  им свой код action.

Создаем функцию, которая сохраняет локальные переменные,а на их место задает новые (если есть параметры при вызове рекурсии). Как их сохранять, это отдельная песня. У меня было их мало, и я передавал их по ссылке.  Помимо переменных нужно сохранить и действие (action) которое нужно сделать в зависимости от результат функции. Эта функция заменяет нам рекурсионный вызов - сохраняем текущие значения, заменяем их на новые.  После сохранения мы должны вернутся в начало цикла, как будто мы только зашли в функцию.
Далее, создаем функцию проверки нашего стека на наличие там записей и извлечения их из него. Она нам потребуется для замены строк return чего_то_там. Передаем в неё это чего_то_там. И если стек пустой, возвращаем action = чего_то_там, иначе извлекаем из стека данные, обновляем локальные переменные и возвращаем action в зависимости от чего_то_там. По этому action выполняем код.
Ну а дальше это все объединяем в один цикл и работаем.

В общем описание получилось очень сумбурное, малопонятное.  Но объяснить тяжело. Проще показать результат. Правилась функция CRegExp::lowParse. До изменений файлы были следующими cregexp.cpp, cregexp.h. После применения данного метода cregexp.cpp, cregexp.h .

В ходе испытаний, подтвердилась стабильная работа на длинных строках. Код работает корректно. Но немного упала скорость. На тестовых файлах скорость работы упала на 1 секунду (на моем компьютере). После анализа в профайлере, выяснилось , что узким местом стала работа с памятью в нашем стеке. Оптимизированный вариант приведен выше, как финальный. В нем падение скорости составляет уже примерно 0.4 секунды. Но это уже не устранимо. Зато мы не падаем на рекурсии.

В новой версии FarColorer будет применен этот патч. И проблема, зафиксированная во многих баг-репортах , наконец таки уйдет.

Happy end ?