;;;; -*- Mode: Text, Spell -*- William's ideas about the buffer representation in Cobweb. Primary issue: I feel that having the internal editor representation be or any other flavor of parse tree will not buy us any additional functionally, and will just cause lots of nightmares for those of us who have to implement it. First of all, I think it is pretty obvious that most people are not very structured when they go to write a piece of code. They don't generate their code by performing a bunch of graph manipulations. They type random gibberish into an editor buffer, and after moving chunks of text around, inserting extra parens, cutting-and-pasting chunks of text, etc. Lots of these operations don't happen along any reasonably boundary that a compiler would recognize. Also, most, if not all, of the intervening stages are not syntactically well-formed. So we would have to have some kind of augmented parse tree that could represent, in addition to any valid program, any invalid program also. I maintain that maintaining any kind of parse tree as the only internal representation is going to make it arbitrarily hard to allow for free-form editing. Even if we do put huge amounts of effort into allowing for free-form edits of a parse tree, it is going to be very bug-prone because it is by nature an indefinite set of special cases. So we either have to do away with free-form edits of the parse tree, or do away with the parse tree. If the system is going to be actually usable, instead of just a toy, then I assert we can't do away with free-form edits. That leaves doing away with the parse tree internal representation. Before anyone suggests that we free-form edits of straight text without all the wizzy features, and just require the parse tree internal representation for if you want the bells and whistles, let me address that. My beef with that idea is that it is an all or nothing solution, and hence is lousy as far as a compromise goes. If there were no other solution, then it would be better then requiring the parse-tree based structured editor all the time, but I assert that we don't need to do that. So now that I've spewed all this verbage about why I think a parse-tree based internal representation is going to cause lots of problems, let me spew about how we can get the same result from the users perspective but with a lot less hassel. The general idea is this: maintain the original text, just like in a conventional editor. Free-form edits are trivial to implement. (Well, just as easy as they are in a conventional editor, that is.) But while the user is modifying the original source text, we feed the changed sections though an incremental tokenizer and parser, and maintain cross-references between the generated parse tree and the original text. When any of the original text is edited in a free-form way, we can regenerate that portion of the parse tree. If you want to use some structured template doo-dad, then the editor can consult the parse tree, figure out what the appropriate textual modification is, and then make that modification. As far as the user can tell, the parse tree was changed directly. The details are dependent on our being about to write an incremental tokenizer and parser. Well, an incremental tokenizer is trivial because tokenization is local by nature. An incremental parser is more difficult. But in my opinion much easier then trying to make free-form edits of the parse tree directly. In summary: using a parse tree as the only internal representation does not buy us anything over incrementally generating the parse tree on the fly, and incrementally generating the parse tree on the fly will be a lot easier. Towards that end, I've started to spec out a little bit about what I think the fundamental internal representation might be something like. ;;;; Class overview: - A object is sequence of characters that supports efficient insert, delete, and overwrite operations. - A is used to keep track of a position (i.e. between two neighboring characters) or a substring (i.e. a series of adjacent characters) in a object. A continues to point between or at the same characters across arbitrary changes to the object. - A is a subclass of that also maintains a parallel sequences of tokens that span the entire , and a parse tree generated from those tokens. The set of tokens and the parse tree are automatically updated whenever the is modified. ;;;; details: objects are internally stored using a buffer/gap represented. A buffer/gap representation is just an oversized vector with the excess, or gap, moving around inside the vector as needed. Inserting or deleting characters at the gap is easy: just fill in part of or enlarge the gap. If we want to insert or delete somewhere else, move the gap there first. If we ever fill up the gap, then we grow it by effectively moving the gap to the end of the buffer, realloc'ing the buffer, and the moving the gap back to wherever we wanted it. Positions in a object refer to real character offsets as if the gap didn't exist. All interface routines use positions, so the existence of the gap is totally hidden from clients of the object. Whether the gap is hidden from subclasses of remains yet to be decided. (My instinct is to say yes.) make #key fill size => text Create a new object. Size: defaults to 0, and fill: defaults to #\space. subtext text #key start end => sequence Create a lightweight sequence object that contain the start (inclusive) through end (exclusive) characters of text. The exact class of the sequence returned is not specified. This subtext sequence will track changes in the original source text, and modifications to the subtext will be propagated back. ### Should this take a mark instead of an explicit start and end? ### Should start and end be required? If not, what are reasonable defaults? text-modified text what where count => undefined Invoked by the text internals whenever the underlying characters are changed. What is either 'insert, 'change, or 'delete. Where is the position of the start of the modication. Count is the number of characters affected. The default method is to update the marks associated with this object and to invoke mark-modified on all active marks that are affected. ;;;; details: s are associated with a object, have a start and end position, and an include-beginning? and include-ending? flag. The start and end positions are stored as raw indices into the objects internal vector. So the location of the gap has to be taken into account when accessing the start and end positions. The reason for representing the start and end positions this was is so that we only have to change them when we move the gap. The main assumption behind a buffer/gap representation is that edits frequently occur near one another, implying that moving the gap will allow us to make additional edits cheaply. Well, we don't want to waste all that by making each additional edit update the marks. When we do move the gap, we need to find all the marks who started or ended on one side of the gap, and now start or end on the other side. The way marks are hung off of the object should be designed to facilitate this. The association from to is via a weak pointer, so that if all references to a are dropped, the quits bothering to update it. make #key text start end include-beginning? include-ending? => mark Create a new mark associated with text, which must be supplied. Start and end supply the initial start and end positions for the mark. Start defaults to 0, and end defaults to start. Include-beginning? and include-ending? specify the initial values for the include-beginning? and include-ending? slots (see below). Include-beginning? defaults to #f and include-ending? defaults to #t. binary= mark1 mark2 => boolean Returns true iff mark1 and mark2 refer to the same start and end positions in the same object. The include-mumble? flags are ignored as far as binary= is concerned. Note: there is no binary< method, because there is not necessarily a strict ordering between marks. mark-start mark => position mark-start-setter mark new-position => undefined Get (or set) the start position of the mark. It is an error if the position is outside the bounds of the text object this mark is associated with. If the start is ever advanced past the end, the end is advanced to be the same as the new start. mark-end mark => position mark-end-setter mark new-position => undefined Get (or set) the end position of the mark. It is an error if the position is outside the bounds of the text object this mark is associated with. If the end is ever backed before the start, the start is moved back to be the same as the new end. mark-include-beginning? mark => boolean mark-include-beginning?-setter mark boolean => undefined mark-include-ending? mark => boolean mark-include-ending?-setter mark boolean => undefined Get and set the include-{beginning,ending}? slot. Include-beginning? controls whether insertions that happen at the start position are considered inside the area covered by this mark. In other words, if text is inserted at the start, the start position will not change if include-beginning? is true. Likewise, for include-ending? and insertions at the end position. ;;;; s is a subclass of . The only difference between an active mark and a regular mark is that mark-modified gets invoked on active-marks, while it does not get invoked on regular marks. When the gap is moved, the set of active marks that are interested in edits can be determined from the gap location. Then on each edit, mark-modified can be invoked for those marks without any additional searching having to happen. Active marks could be used by the redisplay code to determine when portions of the screen image need to be redisplayed. make #key text active? start ... Make a new . Keyword arguments just like for regular marks, except for active? which controls the initial value of the active? slot. mark-active? active-mark => boolean mark-active?-setter active-mark boolean => undefined s can be turned on and off. Mark-modified is only invoked for active marks that are currently turned on. s can turn themselves off in mark-modified method if the first indication of an edit is enough, and then back on once they are interested in changes again. Note: when you are done with an active mark, it should be turned off, otherwise it will never become garbage, and hence never be gc'ed. mark-modified mark what where count => undefined Called by text-modified if and only if the affected region intersect the extend of this mark. Whether insertions at the borders are included in this covered range depends on the insert-beginning? and insert-ending? slots (see below). The default method does whatever is necessary to keep start and end referring to the same place in the text object. ;;;; Read-only s? Should s be read-only? By this, I mean should we not allow the start, end, etc. to be changed once the mark is created. If we said yes, then marks could be freely shared. I kinda prefer making them read-only, because it seems cleaner to me. But I can also see the argument that that would just result in excessive consing of new marks. But hey, that might motivate me to finish the gengc system. This would also require the object could quickly throw away garbage marks, because there would be many of them. ;;;; details. The details about s depend a lot on what we want to do with them. Here I'm assuming that the goal is incrementally tokenize the text as modifications are made. This is the first step in being able to incrementally reparse pieces of the , which is one of our pre-stated goals. [And the ease of this solution in addressing that goal is why I'm arguing for it over just keeping the parse tree around.] specializes text-modified in order to tell when it needs to re-run the tokenizer. When a region of text is modified, the support code restarts the tokenizer at the start of first modified token. If the tokenizer is ever about to start a token at the same place a token was found before (and that token hasn't been modified), it can just use the old token, because the result is guaranteed to be the same (otherwise the tokenizer is broken). The incremental parser would sorta do the same thing, except for two details. First off, the test for re-convergence is a lot trickier. Instead of just checking to see if we are about to start tokenizing the same characters as before, we have to check to see if the lookahead token is the same unmodified token (not just an identical token, but the same token) and that the parser state is identical. The second detail is that we will want to be able to reuse parts of the old parse tree that have moved around. For example, changing the until to a while in: until some-condition some-hairy-stuff end; should not result in some-hairy-stuff being reparsed. The parser should notice that it wants a body, and the last time though it wanted a body, and there is a body there. So it should just snag the body wholesale from the previous parse and continue at the end of the body. ;;;; Nested s? Question: should s be atomic like described above, or should they support nesting objects inside them? Being able to nest arbitrary objects inside a object would be one way of addressing some of the hyper-code like features we want. Let's pursue this idea: Instead of objects being a sequence of characters, they could be a sequence of objects, with characters being optimized for. The subtext function could return different kinds of sequences if the result spans nothing but characters, or if it result has to span across some arbitrary objects. But allowing non-characters makes using the buffer/gap representation difficult, if not impossible. I guess we could embed some placeholder character in the vector. When we see that character, we access some hash table that maps vector indices to the real object. We could also wrap an active mark (w/ include-beginning? and include-ending? false) around the placeholder character to detect when the object gets overwritten or deleted. [Okay, so that impossible at the beginning of this paragraph was a little premature...] If we don't allow other objects to be nested inside a , then we need to come up with some other way to implement the hyper-code features we want. One possibility would be to have some object that holds a bunch of objects and other objects. That would be the actual node in the hyper-program. The objects would just be one flavor of leaf, just like any other kind of leaf in the document. What is the effective difference between these two schemes? Well, with the separate s merged into some parent object, the parser would have to be able to start extracting tokens from one object and then move to some other object. Commands like next-page and forward character are different in structure, not not really all that different in complexity between the two schemes. With atomic s, the higher-level node would have to handle overall redisplay and ^f'ing from one into the next. With objects nested inside the , the 's view would have to deal with basically the same issues. Originally I was thinking that 's would want to be atomic, but now I'm leaning the other way. ;;;; A is subclass of that knows about how to display objects. I'm not sure what Mike's idea about how controllers work, so I'm not going to go into much detail. Basically, I'm going to outline what I think should happen, and we can figure out how to mold this stuff into Mike's model later. s are responsible for rendering objects. As most objects are going to be larger then one screen worth, the needs to keep track of where in the it should start displaying. Also, as s are involved in converting UI events into edit operations, a needs a notion of a cursor. The editing side of a is pretty straight forward: input events are mapped to manipulations of the next object. The display side of a is more complicated. (Don't let anyone claim that I ever said redisplay was easy.) The needs examine the object, build up its display lists, and render them. Additionally, it needs to use s (or some other means) to detect when a visible portion of the object changes and needs to be redisplayed. But the main interesting part about this is not just reimplementing Hemlock's redisplay code (without the bugs, of course :-). We want to use all the fun toys available to the modern UI designer: colors, font families, variable sizes, proportional fonts, etc. Also, we want to be able to display the non-character objects embedded in the object. So to do this, the redisplay code is split in half: there is the code to generate the display lists, and the code to render the display lists. The main avenue for customizing the display of a object is to make a subclass of that overrides the display list generation generic functions. Furthermore, if one kind of object is embedded in another kind of object (for example, a object embedded as a comment in a object), the parent can invoke the display-list generation routines on the child directly instead of allocating a large rectangle chunk for the child , resulting in a more seamless boundary between the two. [I'm not sure if this is actually a good idea, but it seems reasonable on the surface.]