#

# Chapter 10: Theory of Operation

This chapter discusses how Leo's code works, paying particular attention to topics that have caused difficulties in design or implementation. This chapter is the highest level view of Leo's code. It discusses everything important about the code that doesn't appear in the code itself. This information will be of use primarily to those wanting to change Leo's code. The previous chapter contains a full discussion of how Leo reads and writes @file trees.

Overview
Nodes
Drawing and events
Clones
Find and change commands
Tangle and untangle commands
Unlimited undo

## Overview

This documentation describes leo.py. Other versions of Leo are similar in design; the differences between versions are generally not interesting enough to describe here.

All versions of Leo are organized as a collection of classes. The general organization of Leo has remained remarkably stable throughout all versions of Leo, although the names of classes are different in different versions. Smalltalk's Model/View/Controller terminology is a good way to organize Leo's classes conceptually.

Model classes represent the fundamental data. The vnode and tnode classes are Leo's primary model classes.

View classes draw the screen. The main view classes are leoFrame.py and leoTree.py. The colorizer class in leoColor.py handles syntax coloring in the body pane. In leo.py, the view classes know about data stored in the vnode class. Most events (keystrokes and mouse actions) in the outline and body pane are handled in the leoTree class. The leoFrame class also creates the Leo window, including menus, and dispatches the appropriate members of the controller classes in response to menu commands.

Controller classes (aka commanders) control the application. In Leo, controllers mostly handle menu commands. In leo.py, the Commands class creates subcommanders to handle complex commands. The atFile class reads and writes files derived from @file trees. The LeoFind class handles the Find and Change commands. The leoImportCommands class handles the Import and Export commands, the tangleCommands class handles the Tangle and Untangle commands and the undoer class handles the Undo command. Other classes could be considered controller classes.

Each Leo window has its own commander and subcommanders. Subcommanders are not subclasses of their commander. Instead, subcommanders know the commander that created them, and call that commander as needed. Commanders and subcommanders call the model and view classes as needed. For example, the Commands class handles outline commands. To move a headline, the commander for the window calls a vnode move routine to alter the data, then calls the view class to redraw the screen based on the new data.

A singleton instance of the LeoApp class represents the application itself. All code uses the `app()` global function to gain access to this singleton member. The ivars of the `LeoApp` object are the equivalent of Leo's global variables. leo.py uses no global Python variables, except the `gApp` variable returned by `app()`. leoGlobals.py defines all application constants. Naturally, most constants are local to the class that uses them.

Several classes combine aspects of model, view and controller. For example, the LeoPrefs class represents user preferences (model), the Preference Panel (view) and the Preferences menu command (controller). Similarly, the LeoFind class represents find settings, the Find/Change dialog, and the Find/Change commands.

We use the following convention throughout this documentation. Any variable named `c` is a commander, i.e., an instance of the Commands class in leoCommands.py. Variables named `v` and `t` are vnodes and tnodes respectively. These classes are defined in leoNode.py.

## Nodes

The vnode and tnode classes represent most of the data contained in the outline. These classes are Leo's fundamental Model classes.

A vnode (visual node) represents a headline at a particular location on the screen. When a headline is cloned, vnodes must be copied. vnodes persist even if they are not drawn on the screen. Commanders call vnode routines to insert, delete and move headlines.

The vnode contains data associated with a headline, except the body text data which is contained in tnodes. A vnode contains headline text, a link to its tnode and other information. In leo.py, vnodes contain structure links: `parent`, `firstChild`, `next` and `back` ivars. To insert, delete, move or clone a vnode the vnode class just alters those links. The Commands class calls the leoTree class to redraw the outline pane whenever it changes. The leoTree class knows about these structure links; in effect, the leoTree and vnode classes work together. The implementation of vnodes is quite different in the Borland version of Leo. This does not affect the rest of the Leo. Indeed, vnodes are designed to shield Leo from such implementation details.

A tnode, (text node) represents body text: a tnode is shared by all vnodes that are clones of each other. In other words, tnodes are the unit of sharing of body text. The tnode class is more private than the vnode class. Most commanders deal only with vnodes, though there are exceptions.

Because leo.py has unlimited Undo commands, vnodes and tnodes can be deleted only when the window containing them is closed. Nodes are deleted indirectly. Several classes, including the vnode, tnode, leoFrame and leoTree classes, have destroy() routines. These `destroy()` routines merely clear links so that Python's and Tkinter's reference counting mechanisms will eventually delete vnodes, tnodes and other data when a window closes.

Leo uses several kinds of node indices. Leo's XML file format uses tnode indices to indicate which tnodes (t elements) belong to which vnodes (v elements). Such indices are required. Even if we duplicated the body text of shared tnodes within the file, the file format would still need an unambiguous way to denote that tnodes are shared.

Present versions of Leo recompute these tnodes indices whenever Leo writes any .leo file. Earlier versions of Leo remembered tnode indices and rewrote the same indices whenever possible. Those versions of Leo recomputed indices when executing the Save As and Save To commands, so using these commands was a way of "compacting" indices. The main reason for not wanting to change tnode indices in .leo files was to reduce the number of changes reported by CVS and other Source Code Control Systems. I finally abandoned this goal in the interest of simplifying the code. Also, CVS will likely report many differences between two versions of the same .leo file, regardless of whether tnode indices are conserved.

A second kind of node index is the clone index used in `@+node` sentinels in files derived from @file trees. As with indices in .leo files, indices in derived files are required so that Leo can know unambiguously which nodes are cloned to each other.

It is imperative that clone indices be computed correctly, that is, that tnode `@+node` sentinels have the same index if and only if the corresponding vnodes are cloned. Early versions of leo.py had several bugs involving these clone indices. Such bugs are extremely serious because they corrupt the derived file and cause read errors when Leo reads the @file tree. Leo must guarantee that clone indices are always recomputed properly. This is not as simple as it might appear at first. In particular, Leo's commands must ensure that @file trees are marked dirty whenever any changed is made that affects cloned nodes within the tree. For example, a change made outside any @file tree may make several @file trees dirty if the change is made to a node with clones in those @file trees.

## Drawing and events

Leo must redraw the outline pane when commands are executed and as the result of mouse and keyboard events. The main challenges are eliminating flicker and handling events properly. These topics are interrelated.

Eliminating flicker. Leo must update the outline pane with minimum flicker. Various versions of Leo have approached this problem in different ways. The drawing code in leo.py is robust, flexible, relatively simple and should work in almost any conceivable environment.

Leo assumes that all code that changes the outline pane will be enclosed in matching calls to the `c.beginUpdate` and `c.endUpdate` methods of the Commands class. `c.beginUpdate()` inhibits drawing until the matching `c.endUpdate()`. These calls may be nested; only the outermost call to `c.endUpdate()` calls `c.redraw()` to force a redraw of the outline pane.

In leo.py, code may call `c.endUpdate(flag)` instead of `c.endUpdate()`. Leo redraws the screen only if flag is true. This allows code to suppress redrawing entirely when needed. For example, here is how the `idle_body_key` event handler in leoTree.py conditionally redraws the outline pane:

    	redraw_flag = false
      	c.beginUpdate()
    	val = v.computeIcon()
    	if val != v.iconVal:
    		v.iconVal = val
    		redraw_flag = true
    	c.endUpdate(redraw_flag) # redraw only if necessary

The leoTree class redraws all icons automatically when `c.redraw()` is called. This is a major simplification compared to previous versions of Leo. The entire machinery of drawing icons in the vnode class has been eliminated. The `v.computeIcon` method tells what the icon should be. The `v.iconVal` ivar that tells what the present icon is. The event handler simply compares these two values and sets `redraw_flag` if they don't match.

Handling events. Besides redrawing the screen, Leo must handle events or commands that change the text in the outline or body panes. It is surprisingly difficult to ensure that headline and body text corresponds to the vnode and tnode corresponding to presently selected outline, and vice versa. For example, when the user selects a new headline in the outline pane, we must ensure that 1) the vnode and tnode of the previously selected node have up-to-date information and 2) the body pane is loaded from the correct data in the corresponding tnode. Early versions of Leo attempted to satisfy these conditions when the user switched outline nodes. Such attempts never worked well; there were too many special cases. Later versions of Leo, including leo.py, use a much more direct approach. The event handlers make sure that the vnode and tnode corresponding to the presently selected node are always kept up-to-date. In particular, every keystroke in the body pane causes the presently selected tnode to be updated immediately. There is no longer any need for the `c.synchVnode` method, though that method still exists for compatibility with old scripts.

The leoTree class contains all the event handlers for the body and outline panes. The actual work is done in the `idle_head_key` and `idle_body_key` methods. These routines are surprisingly complex; they must handle all the tasks mentioned above, as well as others. The `idle_head_key` and `idle_body_key` methods should not be called outside the leoTree class. However, it often happens that code that handles user commands must simulate an event. That is, the code needs to indicate that headline or body text has changed so that the screen may be redrawn properly. The leoTree class defines the following simplified event handlers: `onBodyChanged`, `onBodyWillChange`, `onBodyKey`, `onHeadChanged` and `onHeadlineKey`. Commanders and subcommanders call these event handlers to indicate that a command has changed, or will change, the headline or body text. Calling event handlers rather than `c.beginUpdate` and `c.endUpdate` ensures that the outline pane is redrawn only when needed.

## Clones

The following is a definition of clones from the user's point of view.

Definition 1

A clone node is a copy of a node that changes when the original changes. Changes to the children, grandchildren, etc. of a node are simultaneously made to the corresponding nodes contained in all cloned nodes. Clones are marked by a small clone arrow by its leader character.

As we shall see, this definition glosses over a number of complications. Note that all cloned nodes (including the original node) are equivalent. There is no such thing as a "master" node from which all clones are derived. When the penultimate cloned node is deleted, the remaining node becomes an ordinary node again.

Internally, the clone arrow is represented by a clone bit in the status field of the vnode. The Clone Node command sets the clone bits of the original and cloned vnodes when it creates the clone. Setting and clearing clone bits properly when nodes are inserted, deleted or moved, is non-trivial. We need the following machinery to do the job properly.

Two vnodes are joined if a) they share the same tnode (body text) and b) changes to any subtree of either joined vnodes are made to the corresponding nodes in all joined nodes. For example, Definition 1 defines clones as joined nodes that are marked with a clone arrow. Leo links all vnodes joined to each other in a circular list, called the join list. For any vnode n, let J(n) denote the join list of n, that is, the set of all vnodes joined to n. Again, maintaining the join lists in an outline is non-trivial.

The concept of structurally similar nodes provides an effective way of determining when two joined nodes should also have their cloned bit set. Two joined nodes are structurally similar if a) their parents are distinct but joined and b) they are both the nth child of their (distinct) parents. We can define cloned nodes using the concept of structurally similar nodes as follows:

Definition 2

Clones are joined vnodes such that at least two of the vnodes of J(n) are not structurally similar to each other. Non-cloned vnodes are vnodes such that all of the vnodes of J(n) are structurally similar. In particular, n is a non-cloned vnode if J(n) is empty.

Leo ensures that definitions 1 and 2 are consistent. Definition 1 says that changes to the children, grandchildren, etc. of a node are simultaneously made to the corresponding nodes contained in all cloned nodes. Making "corresponding changes" to the non-cloned descendents of all cloned nodes insures that the non-cloned joined nodes will be structurally similar. On the other hand, cloned nodes are never structurally similar. They are created as siblings, so they have the same parent with different "child indices." To see how this works in practice, let's look at some examples.

Example 1

    + root
    	+ a' (1)
    	+ a' (2)

This example shows the simplest possible clone. A prime (') indicates a cloned node. Node a in position (1) has just been cloned to produce a' in position (2). Clearly, these two cloned nodes are not structurally similar because their parents are not distinct and they occupy different positions relative to their common parent.

Example 2

If we add a node b to either a' node we get the following tree:

    + root
    	+ a'
    		+ b
    	+ a'
    		+ b

The b nodes are structurally similar because the a' nodes are joined and each b node is the first child of its parent.

Example 3

If we now clone either b, we will get:

    + root
    	+ a'
    		+ b' (1)
    		+ b' (2)
    	+ a'
    		+ b' (1)
    		+ b' (2)

All b' nodes must be clones because the nodes marked (1) are not structurally similar to the nodes marked (2).

Dependent nodes are nodes created or destroyed when corresponding linked nodes are created or destroyed in another tree. For example, going from example 1 to example 2 above, adding node b to either node a' causes another (dependent) node to be created as the ancestor of the other node a'. Similarly, going from example 2 to example 1, deleting node b from either node a' causes the other (dependent) node b to be deleted from the other node a'. Cloned nodes may also be dependent nodes. In Example 3, all the b' nodes are dependent on any of the other b' nodes.

We can now give simple rules for inserting and deleting dependent vnodes when other vnodes are created, moved or destroyed. For the purposes of this discussion, moving a node is handled exactly like deleting the node then inserting the node; we need not consider moving nodes further. We insert a new node n as the nth child of a parent node p as follows. We insert n, then for every node pi linked to p, we insert a dependent node ni as the nth child of pi. Each ni is linked to n. Clearly, each ni is structurally similar to n. Similarly, it is easy to delete a node n that is the nth child of a parent node p. We delete each dependent node ni that is the nth child of any node pi linked to p. We then delete n. When inserting or deleting any vnode n we must update its join list, J(n). Updating the join list is easy because the join list is circular: the entire list is accessible from any of its members.

Inserting or deleting nodes can cause the clone bits of all joined nodes to change in non-trivial ways. To see the problems that can arise, consider deleting any of the b' nodes from Example 3. We would be left with the tree in Example 2. There are two remaining b nodes, each with the clone bit set. Unless we know that both b nodes are structurally similar, there would be no way to conclude that we should clear the clone bits in each node. In order to update clone links properly we could examine many special cases, but there is an easier way. Because of definition 2, we can define a shouldBeCloned function that checks J(n) to see whether all nodes of J(n) are structurally similar.

Leo's XML file format does not contain join lists. This makes it easy to change a Leo file "by hand." If join lists were a part of the file, as they are in the Mac version of Leo, corrupting a join list would corrupt the entire file. It is easy to recreate the join lists when reading a file using a dedicated field in the tnode. This field is the head of a list of all vnodes that points to the tnode. After reading all nodes, Leo creates this list with one pass through the vnodes. Leo then convert each list to a circular list with one additional pass through the tnodes.

## Find and change commands

The find and change commands are tricky; there are many details that must be handled properly. This documentation describes the leo.py code. Previous versions of Leo used an inferior scheme. The following principles govern the LeoFind class:

1. Find and Change commands initialize themselves using only the state of the present Leo window. In particular, the Find class must not save internal state information from one invocation to the next. This means that when the user changes the nodes, or selects new text in headline or body text, those changes will affect the next invocation of any Find or Change command. Failure to follow this principle caused all kinds of problems in the Borland and Macintosh codes. There is one exception to this rule: we must remember where interactive wrapped searches start. This principle simplifies the code because most ivars do not persist. However, each command must ensure that the Leo window is left in a state suitable for restarting the incremental (interactive) Find and Change commands. Details of initialization are discussed below.

2. The Find and Change commands must not change the state of the outline or body pane during execution. That would cause severe flashing and slow down the commands a great deal. In particular, `c.selectVnode` and `c.editVnode` methods must not be called while looking for matches.

3. When incremental Find or Change commands succeed they must leave the Leo window in the proper state to execute another incremental command. We restore the Leo window as it was on entry whenever an incremental search fails and after any Find All and Change All command.

Initialization involves setting the `self.c`, `self.v`, `self.in_headline`, `self.wrapping` and `self.s_text` ivars. Setting `self.in_headline` is tricky; we must be sure to retain the state of the outline pane until initialization is complete. Initializing the Find All and Change All commands is much easier because such initialization does not depend on the state of the Leo window.

Using Tk.Text widgets for both headlines and body text results in a huge simplification of the code. Indeed, the searching code does not know whether it is searching headline or body text. The search code knows only that `self.s_text` is a Tk.Text widget that contains the text to be searched or changed and the `insert` and `sel` Tk attributes of `self.search_text` indicate the range of text to be searched. Searching headline and body text simultaneously is complicated. The `selectNextVnode()` method handles the many details involved by setting `self.s_text` and its `insert` and `sel` attributes.

## Tangle and Untangle commands

This section describes Leo's explicit Tangle and Untangle commands. Such commands operate only on @root and @unit trees. The previous chapter discusses the implicit Tangle on Write/Untangle on Read processes used to read and write @file trees.

The Tangle command translates the selected @root tree into one or more well-formatted C source files. The outline should contain directives, sections references and section definitions, as described in Chapter 4. The Untangle command is essentially the reverse of the Tangle command. The Tangle command creates a derived file from an @root tree; the Untangle command incorporates changes made to derived files back into the @root tree.

The Tangle command operates in two passes. The first pass discovers the complete definitions of all sections and places these definitions in a symbol table. The first pass also makes a list of root sections. Definitions can appear in any order, so we must scan the entire input file to know whether any particular definition has been completed.

Tangle's second pass creates one file for each @root node. Tangle rescans each section in the list of roots, copying the root text to the output and replacing each section reference by the section's definition. This is a recursive process because any definition may contain other references. We can not allow a section to be defined in terms of itself, either directly or indirectly. We check for such illegally recursive definitions in pass 2 using the section stack class. Tangle indicates where sections begin and end using comment lines called sentinel lines. The this part of the appendix discusses the format of the sentinels output by the Tangle command.

The key design principle of the Tangle command is this: Tangle must output newlines in a context-free manner. That is, Tangle must never output conditional newlines, either directly or indirectly. Without this rule Untangle could not determine whether to skip or copy newlines.

The Tangle command increases the indentation level of a section expansion the minimum necessary to align the section expansion with the surrounding code. In essence, this scheme aligns all section expansions with the line of code in which the reference to the section occurs. In some cases, several nested sections expansions will have the same indentation level. This can occur, for example, when a section reference in an outline occurs at the left margin of the outline.

This scheme is probably better than more obvious schemes that indent more "consistently." Such schemes would produce too much indentation for deeply nested outlines. The present scheme is clear enough and avoids indentation wherever possible, yet indents sections adequately. End sentinel lines make this scheme work by making clear where the expansion of one section ends and the expansion of a containing section resumes.

Tangle increases indentation if the section reference does not start a line. Untangle is aware of this hack and adjusts accordingly. This extra indentation handles several common code idioms, which otherwise would create under-indented code. In short, Tangle produces highly readable, given the necessity of preserving newlines for Untangle.

Untangle is inherently complex. It must do a perfect job of updating the outline, especially whitespace, from expansions of section definitions created by the Tangle command. Such expansions need not be identical because they may have been generated at different levels of indentation. The Untangle command can not assume that all expansions of a section will be identical in the derived file; within the derived file, the programmer may have made incompatible changes to two different expansions of the same section. Untangle must check to see that all expansions of a section are "equivalent". As an added complication, derived files do not contain all the information found in @root trees. @root trees may contain headlines that generate no code at all. Also, an outline may define a section in several ways: with an @c or @code directive or with a section definition line. To be useful, Untangle must handle all these complications flawlessly. The this part of the appendix discusses the various conventions used in the sentinels output by the Tangle command. These conventions allow the Untangle command to recreate whitespace correctly.

Untangle operates in two passes. The first pass finds definitions in the derived file and enters them into the Untangle Symbol Table, or UST. Definitions often include references to other sections, so definitions often include nested definitions of referenced sections. The first pass of Untangle uses a definition stack to keep track of nested definitions. The top of the stack represents the definition following the latest reference, except for the very first entry pushed on the stack, which represents the code in the outline that contains the @root directive. The stack never becomes empty because of the entry for the @root section. All definitions of a section should match--otherwise there is an inconsistent definition. This pass uses a forgiving compare routine that ignores differences that do not affect the meaning of a program.

Untangle's second pass enters definitions from the outline into the Tangle Symbol Table, or TST. The second pass simultaneously updates all sections in the outline whose definition in the TST does not match the definition in the UST. The central coding insight of the Untangle command is that the second pass of Untangle is almost identical to the first pass of Tangle! That is, Tangle and Untangle share key parts of code, namely the `skip_body()` method and its allies. Just when `skip_body()` enters a definition into the symbol table, all the information is present that Untangle needs to update that definition.

## Unlimited undo

Only leo.py supports unlimited undo. Unlimited undo is straightforward; it merely requires that all commands that affect the outline or body text must be undoable. In other words, everything that affects the outline or body text must be remembered.

We may think of all the actions that may be Undone or Redone as a string of beads (undo nodes). Undoing an operation moves backwards to the next bead; redoing an operation moves forwards to the next bead. A bead pointer points to the present bead. The bead pointer points in front of the first bead when Undo is disabled. The bead pointer points at the last bead when Redo is disabled. An undo node is a Python dictionary containing all information needed to undo or redo the operation.

The Undo command uses the present bead to undo the action, then moves the bead pointer backwards. The Redo command uses the bead after the present bead to redo the action, then moves the bead pointer forwards. All undoable operations call setUndoParams() to create a new bead. The list of beads does not branch; all undoable operations (except the Undo and Redo commands themselves) delete any beads following the newly created bead.

I did not invent this model of unlimited undo. I first came across it in the documentation for Apple's Yellow Box classes.