About undoing commands, especially tree operations

[vitalije]

I haven't post here for a while, but from time to time, I'm still reading this forum. After reading the recent Edward's post about "big problems with undo/redo tree operations", I've just had to write something about this topic.

Personally, I've never had too much confidence in using Leo's undo before/after machinery. I've felt it has a deep defect buried inside which makes things fragile and easy to get wrong. The defect I am talking here about is the fact that all v-nodes instances constantly live and are present in the `c.fileCommands.gnxDict`. I don't remember all the details, but I do remember that this fact alone has caused some very difficult to solve bugs throughout the years. One that comes to my mind right now was the issue 1348 reported by Segundo Bob on the September 2019, and few months later another one issue 1437.

These two bugs were so much hard to solve that for a while I was very convinced that their cause is somewhere deep in the operating system, outside of Leo and even outside of the Python itself.

After I gave up in searching for these two bug's solution in March next year, I've found the solution by trying to solve something else and the solution was just one simple line clearing the gnxDict.

Instead of using Leo's before and after undo methods, I used to create my own undo data for the operations that I wrote. (Search for nodes in the LeoPy outline that have 'vitalije' in their gnx) for some examples.

Here is just one example.

def deletePositionsInList(self, aList):
    """
    Delete all vnodes corresponding to the positions in aList.
    Set c.p if the old position no longer exists.
    See "Theory of operation of c.deletePositionsInList" in LeoDocs.leo.
    """
    # New implementation by Vitalije 2020-03-17 17:29
    c = self
    # Ensure all positions are valid.
    aList = [p for p in aList if c.positionExists(p)]
    if not aList:
        return []

    def p2link(p):
        parent_v = p.stack[-1][0] if p.stack else c.hiddenRootNode
        return p._childIndex, parent_v

    links_to_be_cut = sorted( set(map(p2link, aList))

                            , key=lambda x: -x[0]

                            )
    undodata = []
    for i, v in links_to_be_cut:
        ch = v.children.pop(i)
        ch.parents.remove(v)
        undodata.append((v.gnx, i, ch.gnx))
    if not c.positionExists(c.p):
        c.selectPosition(c.rootPosition())
    return undodata

It collects undo data as a list of tuples (parent_gnx, index, child_gnx), in other words tuple (str, int, str) which in Python is immutable and the whole list can be also easily turned into the tuple and made immutable too. This immutability of the undo data greatly simplifies things and leaves no place for bugs to sneak in. Keeping undo data in the form of some mutable data structures whose elements can also be mutated leaves the door widely open and puts the big invitation sign at the entrance for all the bugs to come and stay.

With all of this, I just wished to illustrate how dangerous and tricky things can get when we have mutable state buried so deep down in the foundations of the Leo's code. Through the years I tried (without much success so far) to warn about this issue and even tried several other approaches in modeling outline data.

I've built several data models and each of them provided support for all tree operations that are supported by Leo. Each operation was totally undoable and handling undo/redo was part of the data model itself.

My last (so far) and most advanced data model is written in Rust as a native python extension module. I haven't the time to actually do something useful with it yet. I remember offering it to the author of the Leo vscode plugin when he first announced the idea of writing it, but he dismissed the idea and decided to use Leo bridge instead and not to rewrite Leo's core. However, later he has done just that rewrite Leo's core in javascript (or maybe he is still doing it).

Rust library can be just as easily packaged in the native module for Node as it was easy to turn it into a Python native module.

Not only this library runs much faster than Leo, but it has much simpler undo/redo logic. I haven't really tested it, but I wouldn't be too much surprised if the same code that I wrote in rust if rewritten in plain python, would run at the same speed as Leo or maybe even a bit faster than that.

All the operations (which modify the outline) return a string representing undo data. The undo/redo operations accept string as an argument and perform the same modification as the original operation in both directions. In fact all the operations are implemented in a similar way. In the first phase they do not modify anything and instead they just calculate the undo data. Once they have calculated the undo data, they simply perform redo operation which actually modifies the outline.

For most of the operation this undo data string is quite small.

But the best part of this library which I am most proud of is the fact that it allows stable outline positions. In the rust code they are called the labels and they are just plain integers.

In all of my previous attempts in creating data models for Leo outlines, I've tried to achieve this, and I had a stable positions but they could not survive undo/redo operation, but on each redo the model generated new different positions. This in turn has complicated undo/redo logic. Finally in my last attempt, I've found a way for generating positions (or labels) in such a way that the same outline will always generate same labels. That way tree modifications always produce the exact same memory representation of the outline. This means that the undo/redo data is stable too. One can send it over the net and apply it to the outline of the same shape and produce exactly the same result. They can be written in the log file allowing virtually unlimited undo/redo history.

The time of my last three commits to my mini_leo library are Jul 2019, Jul 2021 and Jul 2022. It seems that in July I am usually getting  interested in Leo data models. The library needs documentation and some cleaning of the building methods previously used. I haven't yet found a good way to make library automatically built on every commit. Probably github support for automatic rust builds is improved now comparing to the time I last tried to do it.

In what way is my data model different than the Leo's model?

Leo's basic data structure is VNode and it is by definition tied to many different parts of Leo. In tests one can't create VNode unless full Leo's commander is provided. Just creating an instance causes some modifications in the Leo's core data. If you detach VNode from the outline and you wish to keep the node around in the form of undo data, the outline itself is not the same because it's cache in the fileCommands.gnxDict is different and it will cause some hard to predict effects on the gnx generation functions.

On the other hand, in my data model node is just a simple object with the few simple values (strings, booleans, and integers). It can be instantiated without causing any side effect on the rest of the program. It's easy to move this simple values around, to keep them in the logs, to send them, to recreate them if necessary. This makes testing easy and allows simplicity throughout the library.

The plain immutable data types are really great for modeling and they can represent quite a lot of complex data. I use them whenever I can. I always start solving the problems by wandering how to represent all the necessary data using just a bunch of strings, integers, booleans, tuples, lists and dictionaries. Only when the problem is already solved, I sometimes write a class or two mimicking some of the used plain data structures, but quite often I am satisfied with the plain data especially if it is possible to hide all these plain data arrangements inside the single function that is published to the outside world. This gives me a certainty that I can later make whatever change I need and nobody will notice anything as long as my function still returns the same result.

My 2 cents
Vitalije

[Edward K. Ream]

On Fri, Jul 14 vitalije wrote:

> I just wished to illustrate how dangerous and tricky things can get when we have mutable state buried so deep down in the foundations of Leo's code. 

I agree. That's what PR #3438 fixes, as follows:

- The undo code for parse-body now uses bespoke undo/redo code.

- All commands that previously used the retired "change tree" logic (u.before/afterChangeTree, etc.) now use the undo/redo insert-node logic.

I don't see how offline data structures help recreate clones. How do they simulate Leo's low-level VNode operations?

In contrast, the PR's new undo/redo insert-node logic deletes/inserts a single node, thereby using the low-level operations. This change is safe. Leonistas insert and delete nodes all the time :-)

On Félix's advice, PR #3438 clears Leo's undo-related state when performing undoable commands. This change should fix previous problems with clones.

Edward

[Thomas Passin]

After reading this, I looked at the VNode class definition for the first time.  Ouch!  I think this must be an example of serious technical debt.  No doubt it seemed reasonable or even necessary but as I look at it without knowing the history or even much about how it's used, it's not how I try to go about things.  Like Vitalije, I would try hard to be able to create a basic stand-alone VNode and then insert it onto whatever application- or- outline-wide structures need it.

One example is this line in __init__():

    self.expandedPositions: list[Position] = []  # Positions that should be expanded.

In my limited understanding, positions have nothing to do with VNodes except for saying that "this position contains that VNode".  It's the tree that needs to know about which positions are expanded, not the VNode.  If you would say "But when I clone a position, I need to know its children and their expansion state", I would respond "ask the tree - it's the authority".  So positions should not be part of a VNode.

I have never written a tree anywhere near as complicated as Leo's.  But I have learned that to get good speed when you have to access objects that are collected in a list-like structure, it's necessary to have pointers to them in a structure that has much better access time than a list.  Typically I cache them in a dict. It's hard enough to keep such a cache current.  When the list's contents can form part of its entries, it sounds like a nightmare.

Otoh, two points.  It can be hard to keep various lists/dicts. etc in sync when changes take place.  And with non-VNode structures embedded into a VNode, refactoring will likely be really hard.

 Of course, I don't know anything much about this part of Leo's code so I may be misunderstanding in a big way!

[Thomas Passin]

On Friday, July 14, 2023 at 8:24:17 AM UTC-4 Edward K. Ream wrote:

On Fri, Jul 14 vitalije wrote:

> I just wished to illustrate how dangerous and tricky things can get when we have mutable state buried so deep down in the foundations of Leo's code. 

I agree. That's what PR #3438 fixes, as follows:

- The undo code for parse-body now uses bespoke undo/redo code.

- All commands that previously used the retired "change tree" logic (u.before/afterChangeTree, etc.) now use the undo/redo insert-node logic.

Does this mean that code in, say, an existing plugin won't work if it uses the currently-existing  before/afterChangeTree calls?

[Edward K. Ream]

On Fri, Jul 14, 2023 at 7:42 AM Thomas Passin <tbp1...@gmail.com> wrote:

Does this mean that code in, say, an existing plugin won't work if it uses the currently-existing  before/afterChangeTree calls?

Yes. Those calls are dangerous.

Edward

[Edward K. Ream]

On Fri, Jul 14, 2023 at 7:38 AM Thomas Passin <tbp1...@gmail.com> wrote:

After reading this, I looked at the VNode class definition for the first time.  Ouch!  I think this must be an example of serious technical debt.  No doubt it seemed reasonable or even necessary but as I look at it without knowing the history or even much about how it's used, it's not how I try to go about things. 

I stopped reading here.

Enough. This kind of carping has got to stop.

Leo's VNode class is the heart of Leo. It has a long history. It handles clones two orders of magnitude faster than the MORE outliner. All of its complications exist for a purpose.

Edward

[Thomas Passin]

On Friday, July 14, 2023 at 9:23:50 AM UTC-4 Edward K. Ream wrote:

Leo's VNode class is the heart of Leo. It has a long history. It handles clones two orders of magnitude faster than the MORE outliner. All of its complications exist for a purpose.

Of course they do.  The situation is something like when one denormalizes some database tables.  They "ought" to be normalized, it's good practice to normalize them (to at least 3NF) but sometimes for performance reasons one doesn't.  But then it can be hard to update all the denormalized tables correctly.  I think it's no different with Leo.   As I said, I probably don't understand the ins and outs because I'm not familiar with this part of the code or its history.

[Edward K. Ream]

>> Does this mean that code in, say, an existing plugin won't work if it uses the currently-existing  before/afterChangeTree calls?

> Yes. Those calls are dangerous.

Plugins have three ways forward:

1. Replace the existing undo calls with a call to u.clearAndWarn.

The code is no longer undoable but is already an improvement! Undo/redo won't corrupt the undo state.

2. Follow the pattern of the git-diff commands. That is:

- Place all changes in a single new node.

- Call u.before/afterInsertNode instead of u.before/afterChangeTree.

Now the plugin has safe undo/redo.

3. Follow the pattern of 'parse-body`. Write bespoke undo/redo handlers.

Plugins will rarely need to do this, but it's straightforward.

Edward

[Edward K. Ream]

On Fri, Jul 14, 2023 at 9:45 AM Thomas Passin wrote:

Leo's VNode class is the heart of Leo. It has a long history. It handles clones two orders of magnitude faster than the MORE outliner. All of its complications exist for a purpose.

Of course they do.  The situation is something like when one denormalizes some database tables.  They "ought" to be normalized, it's good practice to normalize them (to at least 3NF) but sometimes for performance reasons one doesn't.  But then it can be hard to update all the denormalized tables correctly.  I think it's no different with Leo.   As I said, I probably don't understand the ins and outs because I'm not familiar with this part of the code or its history.

My apologies for my earlier testy response. I'm glad we're still on speaking terms.

Leo's history chapter discusses Leo's evolution. The great divide section discusses the so-called unified node world. No code remains from Leo's earliest history. We must make do with what git shows us.

I understated the performance advantages of VNodes. Leo forms clones in constant time. In comparison, MORE took O(N**2) time to make clones. MORE could be much worse than 100x slower than Leo.

Also, MORE made clones by copying trees, a significant storage allocation bug.

Finally, MORE crashed often. Whatever Leo's problems, it hardly ever just goes away :-)

Edward

[Thomas Passin]

On Friday, July 14, 2023 at 12:14:03 PM UTC-4 Edward K. Ream wrote:

I understated the performance advantages of VNodes. Leo forms clones in constant time. In comparison, MORE took O(N**2) time to make clones. MORE could be much worse than 100x slower than Leo.

Also, MORE made clones by copying trees, a significant storage allocation bug.

Yes, you want to copy references, not objects, when possible. 

Finally, MORE crashed often. Whatever Leo's problems, it hardly ever just goes away :-)

Well, that was Dave Winer, wasn't it?  Great ideas, practical designs, but, if his XML formats are anything to go by - well, they were atrocious.  I never used MORE but some of its core functionality made it into Radio Userland, which I messed with for a while.

[Edward K. Ream]

On Fri, Jul 14, 2023 at 11:56 AM Thomas Passin <tbp1...@gmail.com> wrote:

>> Finally, MORE crashed often. Whatever Leo's problems, it hardly ever just goes away :-)

> Well, that was Dave Winer, wasn't it?

He and three others sold MORE to Symantec (iirc) for 10 million dollars. Symantec never did anything with MORE. Oh, the internet bubble...

Edward

[vitalije]

I apologize if I have just made unnecessary noise with my post. It wasn't my intention.

> I don't see how offline data structures help recreate clones. How do they simulate Leo's low-level VNode operations?

In order to see, you have to be willing to look first.

We had argued about this subject several times in the past and I've never achieved to explain my idea well enough, so I've always felt in the end as not being understood at all. To me it looks like in the beginning Edward had an excellent idea of allowing clones in the outlines, but the first implementation was terrible. That was before node unification. Later, Edward has found a much better way to create and represent clones, which was great, but he became overly attached to this new solution.

To me it looks a lot like the hypothetical situation of a man who had a horse-drawn carriage with wooden wheels for a while and then one day he discovers pneumatic wheels. It was a great improvement but at the same time this improvement became a wall preventing him to see or to even look for any other improvements. This improvement made him so happy and satisfied that he got so attached to this idea that no other idea could penetrate his mind ever since. Even when someone has discovered a way to make a flying car or floating car, the man wouldn't want to consider any idea which would lead him to part with the pneumatic wheels. Yes they were a great invention at the time, but now there are many other inventions to consider and some of them can make traveling so much faster and safer. In order to fly, one must leave the old car behind and jump in the plane. It can be scary at the beginning, but later it becomes natural.

I believe that every technical decision should be made by exploring all tradeoffs related to it. Almost every decision gains you something and at the same time takes away from you something else, it costs you something. The design process should be based on the search for the best possible solution by comparing the gains and costs. It is not always the cheapest solution that is the best. Sometimes, the solution which has some initial costs can save you the tons of money in the future.

In my mind, the fact that it is so easy to create a clone in Leo just by linking two existing v nodes isn't worth enough to let it make every other operation costly, complex and inefficient. I would argue that Leo would be greatly improved in so many other areas if it trades this "clone making simplicity" for the ability to make undo, redo, drawing, testing and some other parts of code much simpler and more efficient.

Given in how many places throughout the Leo's code base it is necessary to check if the position is still valid or not, I would argue that just to be able to have stable, simple and incorruptible positions in the outline is worth enough for switching to the new data model. This alone would make so many simplifications throughout the Leo's code base. Having the simple undo/redo, being able to simplify outline drawing would come as a bonus. And if the library solves the clone creation in more than just two lines of code is it really worth arguing that some simplicity is lost? When the new model provides the function that creates clones reliably and predictably, why would you still insist on having the ability to make clones yourself by making two simple links?

Please don't be offended by anything I wrote because it wasn't my intention to disrespect you or your work in any way. I am just calling you to open your eyes and see the brave new world out there beyond the existing implementation. The present solution to the representation of clones in the outline is just one of many possible solutions. It was a great solution once but there is so much evidence now that it isn't the best one (even if it remains the simplest one). Try to detach yourself from the current implementation and you might find that there are other better solutions to the same problem. Do not compare just the complexity in the clone representation. Instead, you should compare overall complexity including the complexity of writing tests, drawing outline code, undo/redo code, initialization code,... and I am sure you'll see that there are simpler solutions.

Imagine that you have a module `m` that provides you with all necessary outline operations, traversals, queries...

Let's say you wish to load a leo file and get the outline along with all the external files (@clean, @thin, @file, @edit, ...). You just need to make a single call `t = m.load_leo(filename)`. Now that you have the full outline in t, you may wish to iterate over all the nodes. You can write something like `for lev, p, v in m.iterate_nodes(t)` and you get the level, the position and v node in the outline order. The positions that were given to you are stable. You can later ask for the node at given position by calling `lev, v = m.node_at(t, p)`. Let's say you wish to move up, right, left or down the node at position p. You would use something like `undodata = m.move_up(t, p)`. If the move was legal, the outline has been changed and the undo data contains data necessary to undo the operation. If the move was illegal than the outline has not been changed and the undo data is None. After the outline was successfully changed all the positions are still valid. When you delete a node using `udata = m.delete_node_at(t, p)`, only the position p and all the positions inside the subtree will become invalid while all other positions in the outline remain still valid and unchanged. If you undo the delete operation the position p and its subtree positions will be valid again. Let's say you wish to save all the external files. You use the following function: `for path, content in m.find_filenodes(t)` and you'll get all the file names with the content of each file. If you wish to make a clone of the node at position p, you would use `udata, p1 = m.clone_node_at(t, p)` If you want to promote or demote node, you would use `udata = m.promote_node_at(t, p)`. If you want to insert a new node, you would use `udata, p1 = m.insert_node_at(t, p)`. If you wish to insert one outline into the other retaining clones, you would use `udata, p1 = m.insert_outline_retaining_clones(t, p, t1)` If you want to insert the outline with newly generated indices you would use `udata, p1 = m.insert_outline_copy(t, p, t1)` If you wish to change headline or the body you would use something like `udata = m.set_h(t, p, h)` or `udata = m.set_b(t, p, b)`

If you need to iterate children or subtree of any given node, you would use something like `for lev, p1, v in m.children(t, p)` or `for lev, p1, v in m.subtree(t, p)` or `for lev, p1, v in m.unique_nodes(t)`.

Now, let's say you want to draw the outline using the qTreeWidget. You would use something like: `m.attach_widget(t, p, qtw)` and the qtw widget will be populated with the outline t and position p would be drawn as selected. Now, whenever you modify outline using functions in module m, this widget will be updated accordingly. When you click in any node you'll get the event with the corresponding position p. Finally when you wish to detach the widget from the model you would use something like `m.detach_widget(t, qtw)`. You can also call `m.set_hoist(t, p)` or `m.dehoist(t, p)` and the widget would reflect those views. You can also call `udata = m.expand_node_at(t, p)` and `udata = m.contract_node_at(t, p)` as well as `udata = m.expand_to_level(t, p, lev)` and any other expand/contract command you can think of.

The module itself is tested using hypothesis to generate thousands and thousands of pseudorandom sequences of valid outline operations, than undoing and again redoing each of them checking the correctness of the outline before and after each operation. And if by any chance sometimes in the future hypothesis find the sequence of the operations that lead to the invalid outline, you would get 100% reproducible test. That makes fixing bugs much easier.

Now, try to remember how many times have you written some piece of code and a year later found out that code couldn't possibly work (or more often it works, but you cant figure out why it works) and then you rewrite it again to make it simpler and more elegant. How many different kinds of testing helpers have you written until now and yet you have recently discovered that the tests could be much improved for the tenth time... If you just look at the history of this forum, you'll find that each of the following code areas: testing, importing, undo/redo, drawing, batching the outline updates, tree selecting, initialization, loading and reloading settings, themes. Many of these code areas have their own complexity, but I am sure that you would agree that each one of them has at least to deal with the position fragility and therefore could be simplified if the positions were more stable. Also the code in each one of them can be easier and more thoroughly tested if one could instantiate vnode and position simply and without causing any hidden side effects which is impossible with the current implementation.

What if all these problems can be fully (or partially) avoided by using module m? Wouldn't it be nice to have such module? Well I have written this module several times so far each time a bit better than the last time. The features that were described in this post are from the latest version. This module is sitting on my computer (and  on github too) waiting for the chance to be used and useful. The last commit was a year ago, in July 2022.

> I don't see how offline data structures help recreate clones. How do they simulate Leo's low-level VNode operations?

Have you look at it? If not, then no wonder you didn't see how it can help. If you look and try to understand how it works, and if you need some help I could try to explain it in more details. But I didn't get the impression that you even tried to look at it. If you are unwilling to even try to understand how it works, or at least to try to use the code, to experiment a bit, then there will be no words for me to explain it well enough. But if you put some effort in understanding the code, if you try to use it, if you explore and play with it, then I might be able to help you by giving some more details and explanations if necessary.

Anyway, I think I've given my best shot at selling you the idea. Now it is up to you. I won't bother you again (* at least a year ;-)  unless you ask me to.

[Edward K. Ream]

On Fri, Jul 14, 2023 at 5:05 PM vitalije <vita...@gmail.com> wrote:

> I don't see how offline data structures help recreate clones. How do they simulate Leo's low-level VNode operations?

In order to see, you have to be willing to look first.

I'm not willing to change Leo's Position and VNode classes in any way.

Edward

[jkn]

putting Edward's response to the side for now at least, I would like to say as a general point that I am always very interested to read anything Vitalije writes here.

I seem to remember he has an occasionally-updated blog, i must go and hunt that down...

J^n

[Edward K. Ream]

On Friday, July 14, 2023 at 5:05:40 PM UTC-5 vitalije wrote:

> I would argue that just to be able to have stable, simple and incorruptible positions in the outline is worth enough for switching to the new data model.

This appears to be the lede that you buried.

A new data module must be completely compatible will all existing scripts, plugins and Leo's core. I don't believe such a compatible data model is possible.

Nor do I believe that u.saveTree is sound. It did not work for refresh-from-disk.

Edward

[Thomas Passin]

On Saturday, July 15, 2023 at 6:11:59 AM UTC-4 Edward K. Ream wrote:

A new data module must be completely compatible will all existing scripts, plugins and Leo's core. I don't believe such a compatible data model is possible.

I think this is the key here. Using a completely new data model would basically entail a completely new implementation, as best as I can see.  In the abstract this might be desirable for future development, but as a practical matter who's going to do it and what would be the impetus?

[Edward K. Ream]

On Sat, Jul 15, 2023 at 7:02 AM Thomas Passin <tbp1...@gmail.com> wrote:

>> A new data module must be completely compatible will all existing scripts, plugins and Leo's core. I don't believe such a compatible data model is possible.

>> Using a completely new data model would basically entail a completely new implementation.

A new data model would create a new application.

> In the abstract this might be desirable for future development.

Huh? An incompatible data model would be the end of Leo as we know it.

Edward

[Thomas Passin]

That's why I said "in the abstract" - I meant, it might make some kinds of future development better or easier.  But yes of course, a new implementation would be a new application - which I am not suggesting.