For the last several days I have been refactoring and simplifying Leo's fundamental @shadow algorithm in x.propagate_changed_lines and its helpers in the ShadowController class.
Imo, this work is essential, whatever the short-term risk of breaking @shadow. We all must have complete confidence in this code before the new @nosent can replace @auto and @shadow. Fortunately, 45+ unit tests cover @shadow, so the chance of ruining the code is small. Furthermore, the changes so far, while extensive, have not changed the algorithm in any way. They are simply code-level simplifications. The postscript discusses these changes. A new unit test shows off the new tracing features. Another post-script shows the output. I know from past experience that changing the actual algorithm is tricky. The improved traces should help a lot. This unit test highlights one aspect of the algorithm I would like to improve. At present, added lines that could be placed either at the end of one node or the beginning of the following node are in fact placed at the start of the second node. This is unfortunate: it's much more common to add text to the end of a node. When all is finished I plan to document the @shadow algorithm thoroughly in LeoDocs.leo. One more thing. Sentinels in leoShadow.py show that Bernhard Mulder started this code in 2004. Iirc, it took me about a year to realize that the @shadow algorithm would yield the proper results even if it guessed wrongly about whether lines should go at the end of one node or the start of the next. So the new @nosent scheme could have been done at any time from, say, 2005 onwards. We've missed the obvious for 10 years! Edward P.S. Discussion of recent code changes. These changes have changed nothing essential about the algorithm. Instead, the changes make the algorithm as easy to understand as possible by removing cruft from the code. Here are the highlights: - Replaced the SourceWriter class by x.put, which simply appends (possibly munged) lines to x.result. There was a lot of spurious generality in this class. Calling x.put is much simpler. - Drastically simplified the SourceReader class. In fact, this class just gets the next line from an (unchanging!) list of lines and increments a pointer. The only remaining method is sr.get(). The class remains because the algorithm uses three separate reader streams. - Refactored the opcode handlers into separate methods: x.op_delete, x.op_equal, x.op_insert and x.op_replace. The code now uses a dispatch dict to call these methods. This has no effect on speed, but the new methods provide unlimited "room" to make changes. - The x.init_ivars method inits about a dozen ivars for the use of all the helpers, including the x.op_xxx methods. These ivars don't change, so not passing them around as arguments clarifies the code. I have mostly abandoned the public/private terminology, for at least two reasons: 1. There will be no such thing as private files once @nosent replaces @shadow. 2. The old terminology was unhelpful. What really matters is whether a list of lines contains sentinels. So now the readers are called x.rdr (with sentinels) and x.ns_rdr (no sentinels). - Dumping and tracing methods are now methods of the ShadowController class, not the Source/Reader/Writer classes. In practice, this is a simpler, more flexible arrangement. Which leads us to... P.P.S. A trace from a unit test showing the unwanted placement of lines. Here is a trace generated by running the unit test "@suite run child @shadow-test nodes with trace". It is substantially more useful than any previous trace. As you can see, the inserted text, "inserted node at end of node 1", is in fact inserted at the start of node two. The @shadow algorithm is a tricky 3-way merge. You can also imagine that putting the inserted text in the desired place may be tricky, or even impossible. Anyway, here is the trace:: old private lines... 0 u'#@+leo-ver=5\n' 1 u'#@+node:old\n' 2 u'#@+others\n' 3 u'#@+node:node 1\n' 4 u'node 1 line 1\n' 5 u'#@+node:node 2\n' 6 u'node 2 line 1\n' 7 u'#@-others\n' 8 u'#@-leo\n' old public lines... 0 u'node 1 line 1\n' 1 u'node 2 line 1\n' new public lines... 0 u'node 1 line 1\n' 1 u'inserted node at end of node 1\n' 2 u'node 2 line 1\n' propagate_changed_lines equal old_i:0 limit:4 get u'#@+leo-ver=5\n' put u'#@+leo-ver=5\n' get u'#@+node:old\n' put u'#@+node:old\n' get u'#@+others\n' put u'#@+others\n' get u'#@+node:node 1\n' put u'#@+node:node 1\n' get u'node 1 line 1\n' put u'node 1 line 1\n' propagate_changed_lines insert old_i:1 limit:6 get u'#@+node:node 2\n' put u'#@+node:node 2\n' get u'inserted node at end of node 1\n' put u'inserted node at end of node 1\n' propagate_changed_lines equal old_i:1 limit:6 get u'node 2 line 1\n' put u'node 2 line 1\n' get u'#@-others\n' put u'#@-others\n' get u'#@-leo\n' put u'#@-leo\n' results... 0 u'#@+leo-ver=5\n' 1 u'#@+node:old\n' 2 u'#@+others\n' 3 u'#@+node:node 1\n' 4 u'node 1 line 1\n' 5 u'#@+node:node 2\n' 6 u'inserted node at end of node 1\n' 7 u'node 2 line 1\n' 8 u'#@-others\n' 9 u'#@-leo\n' . ---------------------------------------------------------------------- Ran 1 test in 0.020s EKR -- 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 post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/leo-editor. For more options, visit https://groups.google.com/d/optout.
