К лекции Fr. Nyarlathotep Otis
Которая цитировалась в записи «Об укладывании в воображении перпендикулярного времени (а также 4-х, 5-ти и 6-ти измерений)».
Оригинал взят у nabbla1 в Граф Андуку.
Два года назад я написал свой первый прототип древовидного Undo, где при возвращении назад и "изменении прошлого" вся дальнейшая история не стирается, а просто "уходит вбок" - мы создаём параллельную реальность, но при желании можем вернуться в исходную.
Этот древовидный Undo мне казался промежуточной ступенью к еще более продвинутому механизму графового Undo, когда история может не только ветвиться, но и склеиваться назад, у нас могут появиться временные петли, например, удалив все объекты, мы тем самым вернемся в самое начало, к пустому документу. Использование хэш-функций позволяет реализовать такой подход - выполнив очередную команду, мы подсчитываем хэш документа и сравниваем с ранее посчитанными хэшами (неплохая идея хранить хэши в хэш-таблице, и замечу, это не вовсе не тавтология), если совпало, то не создаём новое состояние, а переходим к найденному.
У этого подхода есть положительные моменты - закончится, наконец, путаница, что означает выделенное действие в History - что оно уже сделано, или сделано все, что было до него? А проблема вся в том, что у нас всё время смешивалось два совершенно различных понятия - "состояние документа", вершина графа, и "действие", которое переводит одно состояние в другое, т.е ребро графа. Когда мы жмем undo/redo или жмем на одно из действий в History, мы хотим вернуть определенное состояние документа, но нам упорно показывают действия. Из этой же оперы - неизбежный фиктивный элемент в History, как правило, первая запись "новый документ" - он нужен, потому что в линейном Undo состояний на одно больше, чем действий, а мы должны уметь переходить на каждое из состояний!
Но проблем тоже хватает: в линейном undo определено и прошлое, и будущее, так что кнопок undo/redo вполне достаточно. В древовидном undo определено по крайней мере прошлое, так что действие кнопки undo определяется однозначно, а redo можно заставить работать по "текущей альтернативной вселенной". В графовом же undo уже и прошлое становится неопределенным, поскольку в один узел мы могли попасть разными путями, и какой из них выбрать при нажатии undo - уже неясно. Скорее всего, на этот граф все-таки придется наложить "нашу мировую линию" - линейный список пройденных нами узлов, и при нажатии на undo/redo путешествовать по этому списку, иногда даже по кругу.
Техническую реализацию я как будто бы продумал, каждая команда может находиться в одном из трех состояний - "вперед", "назад" и "фиктивная", в первом случае внутри команды хранится достаточно информации, чтобы выполниться, и если это сделать, она сохранит внутри себя информацию, достаточную для отмены ("назад"). Фиктивная же команда вообще не хранит ничего, поскольку выяснилось, что из одного состояния в другое можно перейти окольным путем, и именно так мы и сделаем, чтобы случайно не "зайти с тыла" и не дублировать информацию почем зря. То есть, в реальности мы будем путешествовать по остовному дереву графа, а остальные ребра - "для красоты".
Тяжелее всего для меня - красивая визуализация всего этого дела, вот где можно поломать голову. И еще одна проблема - код древовидного undo за 2 года "эволюции" пришел в совершенно непотребный вид, все обросло взаимозависимостями, так что просто поменять дерево на граф, не порушив все остальное, практически невозможно.
Сейчас занялся рефакторингом всего этого бреда, и по мере выхода более-менее юзабельного кода собираюсь выкладывать его в ЖЖ, вдруг кому будет интересно. Вещь специфическая - код написан на Delphi, меня многие после этой фразы перестают воспринимать всерьез, но привести мне пример другого языка, который компилировался бы в нормальный машинный код, а не промежуточный, как java/dotnet/ruby/python, и при этом поддерживал бы интроспекцию (метаклассы, просмотр свойств и методов объектов, автоматическая сериализация/десериализация без тьмы кода), и еще и обходился бы без зверских Фреймворков на сотни мегабайт, они не могут. Хорошо, что я не программист, а то мог бы и обидеться.
Из-за специфичности я подумываю описывать всё это не здесь, а от имени ЖЖ-юзера undooku, созданного с этой целью.
Оригинал взят у nabbla1 в Граф Андуку.
Два года назад я написал свой первый прототип древовидного Undo, где при возвращении назад и "изменении прошлого" вся дальнейшая история не стирается, а просто "уходит вбок" - мы создаём параллельную реальность, но при желании можем вернуться в исходную.
Этот древовидный Undo мне казался промежуточной ступенью к еще более продвинутому механизму графового Undo, когда история может не только ветвиться, но и склеиваться назад, у нас могут появиться временные петли, например, удалив все объекты, мы тем самым вернемся в самое начало, к пустому документу. Использование хэш-функций позволяет реализовать такой подход - выполнив очередную команду, мы подсчитываем хэш документа и сравниваем с ранее посчитанными хэшами (неплохая идея хранить хэши в хэш-таблице, и замечу, это не вовсе не тавтология), если совпало, то не создаём новое состояние, а переходим к найденному.
У этого подхода есть положительные моменты - закончится, наконец, путаница, что означает выделенное действие в History - что оно уже сделано, или сделано все, что было до него? А проблема вся в том, что у нас всё время смешивалось два совершенно различных понятия - "состояние документа", вершина графа, и "действие", которое переводит одно состояние в другое, т.е ребро графа. Когда мы жмем undo/redo или жмем на одно из действий в History, мы хотим вернуть определенное состояние документа, но нам упорно показывают действия. Из этой же оперы - неизбежный фиктивный элемент в History, как правило, первая запись "новый документ" - он нужен, потому что в линейном Undo состояний на одно больше, чем действий, а мы должны уметь переходить на каждое из состояний!
Но проблем тоже хватает: в линейном undo определено и прошлое, и будущее, так что кнопок undo/redo вполне достаточно. В древовидном undo определено по крайней мере прошлое, так что действие кнопки undo определяется однозначно, а redo можно заставить работать по "текущей альтернативной вселенной". В графовом же undo уже и прошлое становится неопределенным, поскольку в один узел мы могли попасть разными путями, и какой из них выбрать при нажатии undo - уже неясно. Скорее всего, на этот граф все-таки придется наложить "нашу мировую линию" - линейный список пройденных нами узлов, и при нажатии на undo/redo путешествовать по этому списку, иногда даже по кругу.
Техническую реализацию я как будто бы продумал, каждая команда может находиться в одном из трех состояний - "вперед", "назад" и "фиктивная", в первом случае внутри команды хранится достаточно информации, чтобы выполниться, и если это сделать, она сохранит внутри себя информацию, достаточную для отмены ("назад"). Фиктивная же команда вообще не хранит ничего, поскольку выяснилось, что из одного состояния в другое можно перейти окольным путем, и именно так мы и сделаем, чтобы случайно не "зайти с тыла" и не дублировать информацию почем зря. То есть, в реальности мы будем путешествовать по остовному дереву графа, а остальные ребра - "для красоты".
Тяжелее всего для меня - красивая визуализация всего этого дела, вот где можно поломать голову. И еще одна проблема - код древовидного undo за 2 года "эволюции" пришел в совершенно непотребный вид, все обросло взаимозависимостями, так что просто поменять дерево на граф, не порушив все остальное, практически невозможно.
Сейчас занялся рефакторингом всего этого бреда, и по мере выхода более-менее юзабельного кода собираюсь выкладывать его в ЖЖ, вдруг кому будет интересно. Вещь специфическая - код написан на Delphi, меня многие после этой фразы перестают воспринимать всерьез, но привести мне пример другого языка, который компилировался бы в нормальный машинный код, а не промежуточный, как java/dotnet/ruby/python, и при этом поддерживал бы интроспекцию (метаклассы, просмотр свойств и методов объектов, автоматическая сериализация/десериализация без тьмы кода), и еще и обходился бы без зверских Фреймворков на сотни мегабайт, они не могут. Хорошо, что я не программист, а то мог бы и обидеться.
Из-за специфичности я подумываю описывать всё это не здесь, а от имени ЖЖ-юзера undooku, созданного с этой целью.