v.self_and_subtree, a true vnode generator
Edward K. Ream
PR #3473 defines Leo's first VNode generator, v.self_and_subtree generator.
This generator is more than a curiosity. It shows that for some purposes VNodes can supplant positions. Here is the code:
def self_and_subtree(self) -> Generator:
"""
Yield v itself and all descendant vnodes.
It *is* valid for v to be c.hiddenRootNode
"""
v = self
seen: list[VNode] = [v]
to_be_visited = [z for z in v.children]
yield v
while to_be_visited:
v = to_be_visited.pop()
yield v
for child in v.children:
if child not in seen:
seen.append(child)
to_be_visited.append(child)
Not all Position generators have direct analogs in the VNode world. For example, vnode generators can not emulate p.parents() and p.self_and_parents() because VNodes may have multiple parent VNodes.
Otoh, a v.all_parents() generator might simplify Leo's code.
Summary
VNode generators are worth further investigation.
Edward
Edward K. Ream
Edward K. Ream
On Tuesday, August 8, 2023, Edward K. Ream wrote:
> PR #3473 defines Leo's first VNode generator, v.self_and_subtree.
Here are some ENB-like notes. Feel free to ignore this post.
- v.self_and_subtree contains no recursion and no "yield from" statements. The PR will simplify other methods using this code pattern.
- v.self_and_subtree generator yields no duplicates. Duplicates would be useless because outline order is undefined in the vnode world. So methods such as v.parents_iter or v.self_and_parents would make no sense.
- Vitalije's c.all_positions_for_v method shows how to generate all positions p such that p.v == v. Yes, this is possible even in the unordered VNode world. Imo, this should be a VNode method. Yes, we'll retain the Commander method for compatibility.
- c.all_unique_roots contains code equivalent to c.hiddenRootNode.self_and_subtree(). The PR will simplify c.all_unique_roots accordingly.
- g.getLanguageFromAncestorAtFileNode contains an internal v_and_parents generator. The PR will replace this local generator with a new v.self_and_parents generator.
- Similarly, the PR will simplify v.setAllAncestorAtFileNodesDirty.
- c.pasteAsTemplate contains an internal skip_root generator that generates the outside set. The PR will remove this internal generator, replacing:
outside = {x.gnx for x in skip_root(c.hiddenRootNode)}
with:
outside = {x.gnx for x in c.hiddenRootNode.self_and_subtree()}
outside.remove(c.hiddenRootNode.gnx)
If Leo defines v.subtree, this can become:
outside = {x.gnx for x in c.hiddenRootNode.subtree()}
Summary
-
v.self_and_subtree
is not the first generator yielding VNodes, but the existing generators are fairly well hidden.
A (new?) PR will replace ad-hoc internal generators with new (official) VNode generators.
All these changes must wait until Leo 6.7.5.
Edward
Edward K. Ream
c = self
for p in c.all_positions():
if p.v == v:
yield p.copy()
Edward K. Ream
vitalije
On Tuesday, August 8, 2023 at 10:27:14 AM UTC-5 Edward K. Ream wrote:> c.all_positions_for_v shows how to generate all positions p such that p.v == v.This method "reconstitutes" positions using only VNode operations. But this trick is only mildly interesting.
def all_positions_for_v(v):
for p in c.all_positions():
if p.v == v:
yield p.copy()
t1 = time.perf_counter_ns()
for i, v in enumerate(allvnodes):
f(v)
dt = (time.perf_counter_ns() - t1)/1e6
if dt > 60000:
g.es(f'too slow: average time: {dt/i:.2f}ms')
break
else:
g.es(f'Total for {name} is {dt:.2f}ms')
g.es(f'Average for {name} is {dt/len(allvnodes):.2f}ms')
def using_p(v):
return list(all_positions_for_v(v))
def using_v(v):
return list(c.all_positions_for_v(v))
measure('using_v', using_v)
Total for using_v is 148.46ms
Average for using_v is 0.01ms
too slow: average time: 26.26ms
So, the "straightforward" solution, using position generators is about 2600 times slower than the code using only v nodes generators.
Instead, the following straightforward generator yields positions in outline order:def all_positions_for_v(self, v: VNode) -> Generator:
c = self
for p in c.all_positions():
if p.v == v:
yield p.copy()Afaik no part of Leo uses this code. Perhaps the PR should delete it.
The idea that generator using v nodes should be deleted because it isn't used, and your remark that
> - v.self_and_subtree contains no recursion and no "yield from" statements
explains a lot to me. Not that I understand why it matters to you that "yield from" is not being used, but I now understand a little better your unwillingness to accept my ideas. You just don't see how much of unnecessary work is being done under the hood of p generators. Yes, they might seem a bit shorter or perhaps more useful or more straightforward on the surface, but they are just hiding a lot of unnecessary complexity deep down, while having simple and innocent appearance.
In all my code related to Leo and outlines, I've always used short helper generators defined inside the body of the function that uses them. In most cases the resulting code was shorter and much faster than the equivalent code based on p generators.
Vitalije
PS: By the way, "yield from" is just a shorter form that doesn't require you to explicitly name item that you are yielding from the generator. Much like lambda allows you to define function without explicitly naming it if it is used in just one place.
yield from xs
# is the same as
for x in xs:
yield x
# but doesn't require inventing a new name for item x
Edward K. Ream
Edward K. Ream
for v2 in v.self_and_all_parents():
if v2.isAnyAtFileNode():
v2.setDirty()