Status report and Aha re positions and vnodes

[Edward K. Ream]

Work on #1631 has taken an unexpected turn. The issue has been renamed "Eliminate v.expandedPositions". Instead of using this list (and trying to update it), c.shouldBeExpanded(p) uses no data that must be kept in sync with the outline.

The new scheme isn't perfect, as you can see for itself. The difficult case involves a nodes having two clones (of the same node) as direct children.  Like this (As usual, ` denotes cloned nodes):

- A

  - B`

    - C

  -D

  - B`

    - C

Try expanding A and B` in various orders. If you collapse A and then expand A, both B` nodes will be expanded, even if only one was expanded previously. This is slightly annoying. Happily, this situation is rare.

Aha: a vnode-oriented approach would not help!

As a thought experiment, I considered vnode-oriented positions. The VPosition class would be similar to the Position class, except it would not use an _childIndex ivars. You can think of the VPosition class a projection of the Position class into a pure vnode space. In less highfalutin terms, a VPosition would simply consist of a stack of vnodes.

Hah! When the outline changes, it's no easier to keep VPositions in sync than it would be to keep Positions in sync! When a node moves, it's stack would changes pretty much exactly as does the stack in Positions.

Summary

The new scheme is in the bug-1631 branch. c.shouldBeExpanded uses a purely algorithmic approach. c.shouldBeExpanded does not use any data that needs to change when the outline changes.

A thought experiment shows that remembering expanded vnodes will suffer the same problems as remembering expanding positions.

Imo, the new scheme is probably the best that can be done. There is no need to change the undo/redo code, or any of the code that moves, inserts or deletes nodes. There is no need to have the gui code do extra work.

Your comments, please, amigos.

Edward

[vitalije]

There are possibly many ways to specify which node should be expanded. Some of them are more sensitive to outline changes than others. Here is an idea of encoding expanded positions in more robust way.

When traversing outline we can encounter same v node several times if it is cloned. A pair (v, count) where count is integer showing how many times this same v node was seen during the traversal, can be used to make distinction between clones. The first occurrence of  v is encoded as (v, 0). The second occurrence is encoded as (v, 1),...

Now if we want to know whether the position p should be expanded, the following code (untested) might give the answer:

def should_p_be_expanded(p, expanded): # expanded is a set of pairs (v, i)
    v = p.v
    for i, p1 in enumerate(sorted(c.all_positions_for_v(v))):
        if p1 != p: continue
        return (v, i) in expanded
    return False

Of course if p.v has no clones then, correct answer is just p.v.isExpanded()

This scheme can also be broken by outline change, when this change affects ordering of clones, but it is resilient against inserting and deleting new nodes, and moving nodes that are not ancestors of a node. That covers a lot of more frequent kinds of outline changes.

My 2 cents.

Vitalije

[Edward K. Ream]

On Mon, Aug 31, 2020 at 11:59 AM vitalije <vita...@gmail.com> wrote:

A pair (v, count) where count is integer showing how many times this same v node was seen during the traversal, can be used to make distinction between clones.

An interesting idea. Let me think about it.

 

This scheme can also be broken by outline change, when this change affects ordering of clones, but it is resilient against inserting and deleting new nodes, and moving nodes that are not ancestors of a node.

In this case, broken "links" are tolerable, because expansion state is not crucial.

I plan to experiment with your proposal.

Edward

[Edward K. Ream]

On Monday, August 31, 2020 at 10:53:11 AM UTC-5, Edward K. Ream wrote:

Work on #1631 has taken an unexpected turn. The issue has been renamed "Eliminate v.expandedPositions". Instead of using this list (and trying to update it), c.shouldBeExpanded(p) uses no data that must be kept in sync with the outline.

Tests show there are unexpected difficulties with eliminating v.expandedPositions. The present Qt gui code tacitly assumes that c.shouldBeExpanded will deliver a value that is (roughly) in sync with the actual expansion status of the gui nodes. I just now noticed that the new code (in the bug-1631 branch) does not always properly indicate that cloned nodes have children. This likely dooms the present code.

This is very tricky code. I'm not entirely sure why the legacy code (in devel) works as well as it does, but it mostly does work.

Summary

There are unexpected dependencies between the Qt gui code and c.shouldBeExpanded. The changes in the bug-1631 branch do not work.

Changing the representation of the v.expandedPositions list will fail in different ways, with different consequences.

The fundamental problem: there is no easy, correct way to describe a position that will persist when the outline changes. Cute tricks have no chance of working. Let me be clear. The problem is not the position class itself. This is a hard problem.

So we are left with a stark choice: either live with the present situation, or find a way to update v.expandedPositions rigorously whenever the outline changes. Even that may not suffice due to subtle interactions between the gui code and the data model.

Edward

P.S. There is another alternative, namely expand/contract all clones (of the same node) the same way. This was the status quo ante before v.expandedPositions existed. I would rather not do that, but this way isn't actually terrible because it is actually rare to have two sibling clones.

EKR

[vitalije]

I don't fully understand your previous post. Here is an example script that shows how expanded/collapsed state can be deduced without v.expandedPositions.

def p_to_count(p):
    v = p.v
    if len(v.parents) == 1:
        return 0

    for i, p1 in enumerate(sorted(c.all_positions_for_v(v))):

        if p1 == p:
            return i
    return -1 # position isn't valid

class ExpandController:
    def __init__(self, c):
        counts = {}
        self._expanded = expanded = set()
        for _p in c.all_positions():
            i = counts.get(_p.v, 0)
            if _p.isExpanded():
                expanded.add((_p.v, i))
            counts[_p.v] = i + 1

    def should_be_expanded(self, p):
        v = p.v
        i = p_to_count(p)
        return (v, i) in self._expanded

    def expand_position(self, p):
        i = p_to_count(p)
        if i > -1:
            v = p.v
            self._expanded.add((v, i))

    def collapse_position(self, p):
        i = p_to_count(p)
        if i > -1:
            v = p.v
            self._expanded.remove((v, i))

    def toggle_position(self, p):
        i = p_to_count(p)
        if i > -1:
            v = p.v
            if (v, i) in self._expanded:
                self._expanded.remove((v, i))
            else:
                self._expanded.add((v, i))

# now let's test if both methods give the same result
ec = ExpandController(c)
expandables = [x for x in c.all_positions() if x.v.children]
    # only nodes that have children can be expanded
for p1 in expandables:
    a = p1.isExpanded()
    assert a == ec.should_be_expanded(p1), repr((p_to_count(p1), a, p1))
    if a: # let's toggle position using p methods
        p1.contract()
    else:
        p1.expand()
    ec.toggle_position(p1) # let's toggle in ExpandController too
    assert p1.isExpanded() == p1.isExpanded()
    if a: # return to the previous state
        p1.expand()
    else:
        p1.contract()
    ec.toggle_position(p1) # in ExpandController too

g.es('all tests pass')

The script creates an ExpandController which copies the expanded/collapsed state from the Leo during the init.

Then it creates a list of all positions that have children, because only those positions can be expanded/collapsed.

Then for each position in this list check to see if both methods give the same expanded state. Additionally it

toggles the state checks the results are still the same, and toggles once more to restore the previous state.

The script doesn't try to change the outline to see if the expanded state would survive, but I am pretty sure that ExpandController is more immune to the outline changes than the v.expandedPositions method.

Vitalije

[vitalije]

Profiling gives almost the same result for both methods.

import timeit
def f1():
    for p1 in expandables:
        p1.isExpanded()
def f2():
    for p1 in expandables:
        ec.should_be_expanded(p1)

def tt(s, fun):
    t1 = timeit.timeit(fun, number=1000)
    g.es(f'{s} average: {t1:.3f}')
tt('using p.isExpanded', f1)
tt('using ExpandController', f2)

On my machine this gives:

using p.isExpanded average: 0.816
using ExpandController average: 0.861

Vitalije

[Edward K. Ream]

On Tue, Sep 1, 2020 at 10:55 AM vitalije <vita...@gmail.com> wrote:

> I don't fully understand your previous post.

...

> I am pretty sure that ExpandController is more immune to the outline changes than the v.expandedPositions method.

We agree that positions, no matter how defined, do not necessarily survive changes in the outline. That's true of Leo's existing positions, and it's true of the ExpandController class.

In my previous post I hinted that a complete fix to #1631 would involve updating all saved positions (using either v.expandedPosition or your proposed ExpandController class) whenever the outline changes.

Imo, this is not worth doing. It's a lot of work for virtually no gain. One could even say that contracting a moved position is a good thing.

Yes, the present behavior confused Félix, but he's a special case :-) He was paying much closer attention to Leo's behavior than the average user, including me! That's because he was taking the implementor's view, not the user's view.

Unexpected difficulties

Here are some details that indicate the difficulties in a complete fix:

I tried defining c.shouldBeExpanded as in the bug-1631 branch. The proposed code does not use any data structures at all. Alas, the new code fails in difficult-to-understand ways. The attached code fails in the bug-1631 branch. As noted in the "Readme" node, the a1 node does not always show that it has children. (You may have to insert or delete the "a" clone to see this.)

As I said, the reasons for these problems are difficult to understand. They involve Leo's complex tree redrawing code. Here are some of the difficulties with the redraw code:

1. Redraw code happens while changing nodes, so c.p is not guaranteed to be what one might naively think it is.

2. There are at least three paths through the tree code relating to expansion and contraction:

- The user clicks the expand/contract icon, thereby possibly selecting a new node.

- The user uses an arrow key in the tree pane (or an alt-arrow key anywhere) to expand or contract a node, and possibly move to a new node.

- A script modifies the expansion state of a node (vnode) and then calls c.redraw().

At present, Leo handles all these details properly. The new code doesn't. Yes, there could be a bug lurking in Leo's Qt tree code that the new code exposes.

Summary

I am willing to consider fixing #1631 only if the following conditions are met:

1. The Qt code does not change in any way, except possibly for bug fixes that stand on their own merits.

2. All positions, no matter how represented, are always updated properly when the outline changes. In particular, positions must be updated when undoing a delete operation, which seems like the acid test.

Imo, this is just too much work to be worthwhile. I am about to close #1631. I will consider PR's that meet the above requirements, but I advise against further work on this issue.

Edward