This Engineering Notebook post discusses how to accelerate the speed of g.findLanguageDirectives. When I awoke this morning, I saw that the code I changed yesterday is unnecessarily slow. The new code can search a significant fraction of the entire outline when changing nodes! Note: I haven't noticed any real performance problems yet.
Here, I'll discuss how to avoid this search, using a new way of relating vnodes and positions. Afaik, this is something new in Leo's history, although Vitalije has explored similar ground. *Background* In this post <https://groups.google.com/d/msg/leo-editor/8AJ0PKFCwTw/JpnRTfm-BQAJ>I said: "#1625 <https://github.com/leo-editor/leo-editor/issues/1625> expands the search, looking for ancestor @<file> nodes for the *other* clones." However, this is a brute force search. Here is the new code in g.findLanguageDirectives: def find_language(p): for s in p.h, p.b: for m in g_language_pat.finditer(s): return m.group(1) return None ... # #1625: Second, expand the search for cloned nodes. # Similar to g.findRootsWithPredicate. clones = [] for p in p.self_and_parents(copy=False): if p.isCloned() and p.v not in clones: clones.append(p.v) if clones: for p in c.all_positions(copy=False): if p.isAnyAtFileNode(): for p2 in p.self_and_subtree(): if p2.v in clones: language = find_language(p) if language: return language *Accelerating the search* We don't need to search all positions of an outline to find all the @<file> nodes. Instead, we can search using vnodes, as I'll now explain. Terminology: Let v0 be the initial vnode, that is, c.p.v. A cloned vnode v is a node with len(v.parents) > 1. This is exactly what v.isCloned returns. If v0 is a clone, v0.parents is a list of v0's parent vnodes. That is, v0 appears in parent.children for every parent in v0.parents. My first thought was to translate vnodes into positions. Indeed, a Position p has three components: p.v, p._childIndex, and p.stack, which is a list of tuples (v, childIndex). As I was thinking about this, I realized: Aha: for this task, the algorithm does not need child indices! Instantly the algorithm collapses in complexity. The search instantly succeeds if v.isAnyAtFileNode() for any v in v0.parents. Otherwise, we extend the search, in no particular order, to parent.parents for every parent vnode in v0.parents. We continue the search until we have found an ancestor @<file> node or until we have looked at all possible ancestors of v0. In practice, this search will be extremely fast. *Summary* Amazingly, after all these years, fundamentally important ideas keep appearing. A new "parents" branch will contain much faster versions of g.findLanguageDirectives and g.findRootsWithPredicate. All questions and comments are welcome. Edward -- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/leo-editor/6b38ff9c-456b-46ff-8045-ed1d4a71ecfeo%40googlegroups.com.
