The shifting sands of positions in face of multiple outline modifications

[Brian Theado]

I'm writing some commands for myself to help manage lists of things. I will bind the commands to keystrokes which I will be able to use to quickly add new items and highlight which items I've recently worked on. These commands will also create clones inside "@day <date>" (and automatically create the @day node if hasn't already been created). These details are not important for the point of this post. I just wanted to give a sense of context. The important part is that I have commands which will be making several modifications to the outline structure.

In the long past, I wrote a much simpler command which required multiple outline changes, I gave up trying to write position code directly and instead just used the 'executeMinibuffer' method. That way I was able to leave the handling of positions (and the invalidations thereof) for Leo to take care of.

But this new functionality seemed way too complicated to achieve using minibuffer commands, so I decided to give positions a try again. Based on problems I had in the past with positions, I decided to take the most conservative approach I could think of. Here is the "rule of thumb" I adopted:

• After making an outline modification, don't use any position variables from before the modification. 
• The only position which can be trusted is the position returned by the outline modification method call.
• If the old positions are still needed to complete the rest of the functionality of the command, then they need to be "re-queried" using the position returned by the outline modification.

In my case, the outline modifications were in "close" proximity to each other, so with some hard thinking I was able to figure out how to re-query the other positions. I'm not sure that will always be the case.

Using the above "rule of thumb", I have my code working (lightly tested). I write this email to find out if I've gone overboard and this rule is way more restrictive than necessary. Like maybe only a subset of outline modifications require such strict handling? If that is the case, what are the rules which can be followed in order to safely deal with positions during outline modification. Edward or Vitalije or anyone else, do you know?

Here is my working code (there is a lot of it) to show examples of what I mean. Search for comments with the word "trusted" to see how I'm re-querying positions. I made the "interesting" parts bold to make them easier to find:

import time
def cloneToSiblingTodayNode(p):
    """
    Clone the node identified by p and move that clone to a child of a
    sibling "@day %Y-%m-%d" node. If the @day node doesn't exist yet,
    create it. If p already has a clone as a child of @day, then do nothing.
    
    The position pointing at the original node is returned as output
    (warning:  actually the first child of the parent of p is returned...the
     assumption is that will be the same node as pointed to by the original p).
    """
    today = "@day " +  time.strftime("%Y-%m-%d", time.gmtime())
    def findTodayNode(p):
        day = (
            p1
            for p1 in p.self_and_siblings()
            if p1.h == today
        )
        return next(day, None)
    day = findTodayNode(p)
    if day:
        # The @day node for today already exists
        cloneAlreadyUnderDay = (
            p1
            for p1 in day.children()
            if p1.v == p.v
        )
        if next(cloneAlreadyUnderDay, None):
            # A clone is already child of @day, leave it where it is (should it also move to the top?)
            p2 = p
        else:
            # p doesn't have a clone in @day, so create one
            p2 = p.clone()   # Outline modification!
            # With the outline modification, the day position can't be trusted, so query it again
            day = findTodayNode(p2)
            p2.moveToFirstChildOf(day) # Outline modification!
            p2 = p2.parent().parent().moveToFirstChild()
    else:
        p2 = p.clone()  # Outline modification!
        day = p2.insertAfter() # Outline modification!
        day.h = today
        # With the outline modification, the p2 position can't be trusted, so query it again
        p2 = day.copy().moveToBack()
        p2.moveToFirstChildOf(day)
        p2 = p2.parent().parent().moveToFirstChild()
    return p2

def findFtlistAncestor(p):
    ftlist = (
        p1
        for p1 in p.parents()
        if p1.h.startswith("@ftlist")
    )
    return next(ftlist, None)

def moveOrCloneToTop(p, ftlist):
    """
        If p or a clone of p is already a direct child of ftlist, then move the node
        to the first child of ftlist. Otherwise, create a clone of p and move the clone
    """
    if ftlist.v != p.parent().v:
        # Node is  not a child of ftlist...it is a deeper descendant, so clone instead of move
        # But only add the clone if the node doesn't already have a direct clone child in @ftlist
        cloneIsAlreadyFtlistChild = (
            p1
            for p1 in ftlist.children()
            if p1.v == p.v
        )
        child = next(cloneIsAlreadyFtlistChild, None)
        if not child:
            p = p.clone() # Outline modification!
            # Since the outline changed, the ftlist position can't be trusted, so query it again
            ftlist = findFtlistAncestor(p)
        else:
            p = child
    return p, ftlist

# TODO: what about undo?
def moveToTopAndCloneToAtDay(c, p):
    """
        Move the node identified by position p to the first child of
        an ancestor @ftlist node and also clone it to a sibling @day
        node with date matching today's date
    """
    ftlist = findFtlistAncestor(p)
    if not ftlist:
        g.es("Not in ftlist tree")
        return
    p, ftlist = moveOrCloneToTop(p, ftlist) # Outline modification!
    p.moveToFirstChildOf(ftlist) # Outline modification!
    p2 = cloneToSiblingTodayNode(p) # Outline modification!
    c.redraw(p2)

def insertToTopAndCloneToAtDay(c, p):
    """
        Insert a new node as the first child of
        an ancestor @ftlist node and also clone it to a sibling @day
        node with date matching today's date
        
        Place the headline of the new node in edit mode
    """
    ftlist = findFtlistAncestor(p)
    if not ftlist:
        if p.h.startswith("@ftlist"):
            ftlist = p
        else:
            g.es("Not in ftlist tree")
            return
    p = ftlist.insertAsNthChild(0) # Outline modification!
    p2 = cloneToSiblingTodayNode(p) # Outline modification!
    c.redraw(p2)
    c.editHeadline()

@g.command('ftlist-insert-node')
def ftlistInsertNodeCommand(event):
    c = event['c']
    insertToTopAndCloneToAtDay(c,c.p)

@g.command('ftlist-move-to-top')
def ftlistMoveToTopCommand(event):
    c = event['c']
    moveToTopAndCloneToAtDay(c, c.p)

[vitalije]

Outline modifications that do not invalidate positions are:

1.  appending nodes at the end of children with for example:
   p1 = p.insertAsLastChild()
   # now p is still valid
   
   
   
2. deleting the last child

But for your use case I would probably use v nodes directly.

import time
def cloneToSiblingTodayNode(p):
    """
    Clone the node identified by p and move that clone to a child of a
    sibling "@day %Y-%m-%d" node. If the @day node doesn't exist yet,
    create it. If p already has a clone as a child of @day, then do nothing.
   
    The position pointing at the original node is returned as output
    (warning:  actually the first child of the parent of p is returned...the
     assumption is that will be the same node as pointed to by the original p).
    """
    today = "@day " +  time.strftime("%Y-%m-%d", time.gmtime())

    day = next(iter(c.find_h(today)), None)
    if not day:
        day = p.parent().insertAsLastChild()
        day.h = today
    vday = day.v
    if p.v not in vday.children:
        vday.children.insert(0, p.v)
        p.v.parents.append(vday)
    # position p should be valid as is
    p

After making outline changes using vnodes at the end you should call

c.redraw()

[vitalije]

moveOrCloneToTop should be something like:

def moveOrCloneToTop(p, ftlist):
    """
        If p or a clone of p is already a direct child of ftlist, then move the node
        to the first child of ftlist. Otherwise, create a clone of p and move the clone
    """

    if ftlist.v not in p.v.parents:
        # neither p nor clone of p is a direct child of ftlist
        ftlist.v.children.insert(0, p.v)
        p.v.parents.append(ftlist.v)
    else:
        # ftlist contains clone of p as a direct child
        i = ftlist.v.children.index(p.v)
        if i > 0:
            # clone is not at the top
            # moving it to the top
            del ftlist.v.children[i]
            ftlist.v.children.insert(0, p.v)
    return ftlist, ftlist.firstChild()

HTH Vitalije

[vitalije]

moveToTopAndCloneToAtDay should be like:

def moveToTopAndCloneToAtDay(c, p):
    """
        Move the node identified by position p to the first child of
        an ancestor @ftlist node and also clone it to a sibling @day
        node with date matching today's date
    """
    ftlist = findFtlistAncestor(p)
    if not ftlist:
        g.es("Not in ftlist tree")
        return

    ftlist, p = moveOrCloneToTop(p, ftlist)
    p2 = cloneToSiblingTodayNode(p)
    c.redraw(p2)

Sorry, I have permuted the return of moveOrCloneToTop (you had: return p, ftlist, and I wrote return ftlist, p)

I haven't tested this script thoroughly but it should work. Let me know if it doesn't work as you expected.

Vitalije

[Edward K. Ream]

On Fri, Aug 16, 2019 at 6:42 AM Brian Theado <brian....@gmail.com> wrote:

What are the rules which can be followed in order to safely deal with positions during outline modification. Edward or Vitalije or anyone else, do you know?

As Vitalije says"

- Adding (or deleting) the last sibling will not change the position of any existing node.  This includes adding/deleting the last top-level node.

- If you can recast your algorithm in terms of vnodes, it will be impervious to changes in the outline.

A pattern I use often for summarizing work is:

1. Create a summary node as the last top-level node.

2. Add clones as children of this summary node.

This is, roughly speaking, how the clone-fine and git-diff commands work.

Another possible pattern:

1. Create, say, an @dates node (somewhere) first, if it doesn't already exist.  If you do create an @dates node, then call c.redraw, which will, in effect, recompute all positions.

2. Now that you have an @dates node, create your @date nodes as children of the @dates node.  This will preserve all positions.

HTH.

Edward

[Brian Theado]

Vitalije,

Thanks a lot for all the code. It gives me a huge head start seeing a vnode version of the same position code I wrote. I can already tell from looking at your code that I don't understand positions and vnodes at all. Maybe while trying to adapt your code, I will be enlightened. Hopefully :-).

But at least for now I have the rule which will allow me to use positions while also avoiding the minefields:

Discard all positions other than the one used to modify the outline for any outline modification other than insertAsLastChild and deleting the last child

And now I also have this advice:

When making multiple outline modifications, it might be best to learn and use vnodes instead of positions

BTW, I won't be using c.find_h in my code as I think that is a global outline search. I plan to support (as my original code does) multple @ftlist subtrees in the outline. Each @ftlist will have their own set of @day node children. In order to operate on a given ftlist, the selection will have to already be in an @ftlist subtree.

Brian

--
You received this message because you are subscribed to the Google Groups "leo-editor" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leo-editor+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leo-editor/a7749d44-abb7-4e62-9bb0-746c27f91fdc%40googlegroups.com.

[Brian Theado]

Edward,

Thanks a  lot. See below:

On Fri, Aug 16, 2019 at 10:10 AM Edward K. Ream <edre...@gmail.com> wrote:

[...]

As Vitalije says"

- Adding (or deleting) the last sibling will not change the position of any existing node.  This includes adding/deleting the last top-level node.

- If you can recast your algorithm in terms of vnodes, it will be impervious to changes in the outline.

 

The way I read Vitalije's explanation, it sounded like the last child of a subtree. But are you saying it is only the last node in the entire outline?

 

[...] 

Another possible pattern:

1. Create, say, an @dates node (somewhere) first, if it doesn't already exist.  If you do create an @dates node, then call c.redraw, which will, in effect, recompute all positions.

 

Maybe I should start my journey on position enlightenment with c.redraw(). If I see how positions are recomputed, maybe I will better understand the behavior.

 

2. Now that you have an @dates node, create your @date nodes as children of the @dates node.  This will preserve all positions.

Hmm, are you saying no matter where I create the @dates node all previously create positions will still be valid? Even after making more modifications like inserting @date nodes?

Brian

[Edward K. Ream]

On Friday, August 16, 2019 at 4:39:06 PM UTC-5, btheado wrote:

As Vitalije says"

- Adding (or deleting) the last sibling will not change the position of any existing node.  This includes adding/deleting the last top-level node.

- If you can recast your algorithm in terms of vnodes, it will be impervious to changes in the outline.

 

The way I read Vitalije's explanation, it sounded like the last child of a subtree. But are you saying it is only the last node in the entire outline?

No.  See the emphasis above.  Adding after any last sibling will leave all positions unchanged.

 Maybe I should start my journey on position enlightenment with c.redraw(). If I see how positions are recomputed, maybe I will better understand the behavior.

I wouldn't advise that.  Instead, read << about the position class >>. If you want more detail, look at Position.__init__().

A position consists of a stack of ancestor vnodes, and a child index.

If you move a node, both the stack and child index will change for descendant nodes.

If you insert or delete a node, the child index of sibling nodes may change, and that will also affect the children of those siblings. But no positions will change if you only add/delete the last sibling.  Clear?

2. Now that you have an @dates node, create your @date nodes as children of the @dates node.  This will preserve all positions.

Hmm, are you saying no matter where I create the @dates node all previously create positions will still be valid? Even after making more modifications like inserting @date nodes?

What I said was:

1. Creating the @dates nodes will change positions (unless you create the @date nodes as the last top-level node, or the last child of some other node).  I should have said is that your script should call c.redraw to update the screen.

2. After you create the @dates node, inserting an @date node as the last child of the @dates node will leave all positions unchanged.

Important: Usually scripts don't care much about changing positions.  Changing positions only bite you if you save positions.  Instead, it may be simpler to recompute positions of interest.

Your script could scan for the @dates node (which will give you a valid position), and then the script could scan for the desired @date node in one of the children of the @dates node.

Please feel free to ask more questions.  This is a vital topic for anyone writing an interesting script.

Edward

[Brian Theado]

Edward,

On Sat, Aug 17, 2019 at 7:22 AM Edward K. Ream <edre...@gmail.com> wrote:

No.  See the emphasis above.  Adding after any last sibling will leave all positions unchanged.

Got it. Thanks. 

 

 Maybe I should start my journey on position enlightenment with c.redraw(). If I see how positions are recomputed, maybe I will better understand the behavior.

I wouldn't advise that.  Instead, read << about the position class >>. If you want more detail, look at Position.__init__().

A position consists of a stack of ancestor vnodes, and a child index.

Excellent, this is a huge help. I had it in my head before that there was some kind of linked list and C-style pointer type of thing going on.

 

If you move a node, both the stack and child index will change for descendant nodes.

If you insert or delete a node, the child index of sibling nodes may change, and that will also affect the children of those siblings. But no positions will change if you only add/delete the last sibling.  Clear?

Yes, very clear.

[...]

Important: Usually scripts don't care much about changing positions.  Changing positions only bite you if you save positions.  Instead, it may be simpler to recompute positions of interest.

I think my scripts aren't usual then. Most of the (few) scripts I've written over the years involve making multi-step modifications. Often that means keeping track of more than one position in the outline. Knowing what you said about "A position consists of..." is critical for correctly writing such scripts.

Now that I understand better, I can see the rule of thumb I wrote in my original post is far too restrictive:

• After making an outline modification, don't use any position variables from before the modification. 
• The only position which can be trusted is the position returned by the outline modification method call.

• If the old (saved) positions are still needed to complete the rest of the functionality of the command, then they need to be "re-queried" using the position returned by the outline modification.

 The code I wrote worked, but being unnecessarily conservative made it more complicated.

Your and Vitalije's advice that all saved positions are still safe when operating at the last sibling, didn't really help my case because I wasn't dealing with the last sibling much. What I didn't realize is that just because those are the only operations in which all saved positions are safe, doesn't mean there aren't some saved positions which will still be safe after other operations.

Armed with the knowledge of what a position is, I came up with these examples:

1. Position p gains a new following sibling (i.e. p2 = p.insertAfter()). In this case both p2 and p are safe. With the more restrictive rules, I thought only p2 would be safe, but p is still ok because its child index can only go wrong if previous siblings are inserted or modified
2. Position p gains a new niece/nephew from either previous or following siblings. Again in this case the position p remains valid
3. When changing a following sibling of position p to be a niece/nephew of any sibling, the position p remains valid

So armed with this knowledge and the code Vitalije share, I was able to re-write my code to be much simpler. Vitalije, using positions ended up being sufficient and I didn't need most of your vnode based code. Here is the revised code:

import time
def moveOrCloneToTop(p, parent):
    """
        If p or a clone of p is already a direct child of parent, then move the node
        to the first child of parent. Otherwise, create a clone of p and move the clone
    """
    clone = next((p1 for p1 in parent.children() if p1.v == p.v), None)
    p = clone if clone else p.clone()
    p.moveToFirstChildOf(parent)
    return p

def cloneToSiblingTodayNode(p):
    """
    Clone the node identified by p and move that clone to a child of a
    sibling "@day %Y-%m-%d" node. If the @day node doesn't exist yet,
    create it. If p already has a clone as a child of @day, then do nothing.
    
    The position pointing at the original node is returned as output
    """

    today = "@day " +  time.strftime("%Y-%m-%d", time.gmtime())
    day = (
        p1
        

for p1 in p.self_and_siblings()
        if p1.h ==

 today
    )
    day = next(day, None)
    if not day:
        # Create today's @day node
        day = p.insertAfter()
        day.h = today
    p1 = moveOrCloneToTop(p, day)
    # Since day is a sibling of p, modifying day's children don't affect
    # p so it is still valid
    return p

def findFtlistAncestor(p):
    ftlist = (
        p1
        for p1 in p.parents()
        if p1.h.startswith("@ftlist")
    )
    return next(ftlist, None)

def moveToTopAndCloneToAtDay(c, p):
    """
        Move the node identified by position p to the first child of
        an ancestor @ftlist node and also clone it to a sibling @day
        node with date matching today's date
    """
    ftlist = findFtlistAncestor(p)
    if not ftlist:
        g.es("Not in ftlist tree")
        return

    p = moveOrCloneToTop(p, ftlist)
    p2 = cloneToSiblingTodayNode(p)
    c.redraw(p2)

def insertToTopAndCloneToAtDay(c, p):
    """
        Insert a new node as the first child of
        an ancestor @ftlist node and also clone it to a sibling @day
        node with date matching today's date
        
        Place the headline of the new node in edit mode
    """
    ftlist = findFtlistAncestor(p)
    if not ftlist:
        if p.h.startswith("@ftlist"):
            ftlist = p
        else:
            g.es("Not in ftlist tree")
            return
    p = ftlist.insertAsNthChild(0

)
    p2 = cloneToSiblingTodayNode(p)
    c.redraw(p2)
    c.editHeadline()

[Edward K. Ream]

On Sat, Aug 17, 2019 at 2:14 PM Brian Theado <brian....@gmail.com> wrote:

A position consists of a stack of ancestor vnodes, and a child index.

Excellent, this is a huge help. I had it in my head before that there was some kind of linked list and C-style pointer type of thing going on.

Glad this helped.  It's always good to consult the sources. Having said that, the author of code has the highest level understanding of what's going on, so it's also good to ask.

What I didn't realize is that just because those are the only operations in which all saved positions are safe, doesn't mean there aren't some saved positions which will still be safe after other operations.

Yes, that could be helpful.  You can design your intermediate steps so that they preserve the positions you care about.

Armed with the knowledge of what a position is, I came up with these examples:

1. Position p gains a new following sibling (i.e. p2 = p.insertAfter()). In this case both p2 and p are safe. With the more restrictive rules, I thought only p2 would be safe, but p is still ok because its child index can only go wrong if previous siblings are inserted or modified
2. Position p gains a new niece/nephew from either previous or following siblings. Again in this case the position p remains valid
3. When changing a following sibling of position p to be a niece/nephew of any sibling, the position p remains valid

Yes, I think that's right.

 

So armed with this knowledge and the code Vitalije share, I was able to re-write my code to be much simpler.

Glad to hear it.

Edward