;;;; -*- Mode: Text, Spell -*-

William's ideas about the buffer representation in Cobweb.


Primary issue: I feel that having the internal editor representation be
<expression> 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:

<text> - A <text> object is sequence of characters that supports efficient
insert, delete, and overwrite operations.

<mark> - A <mark> 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 <text> object.  A <mark> continues to point between or at
the same characters across arbitrary changes to the <text> object.

<code-fragment> - A <code-fragment> is a subclass of <text> that also
maintains a parallel sequences of tokens that span the entire
<code-fragment>, and a parse tree generated from those tokens.  The set of
tokens and the parse tree are automatically updated whenever the
<code-fragment> is modified.


;;;; <text> details:

<Text> 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 <text> 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 <text> object.  Whether the
gap is hidden from subclasses of <text> remains yet to be decided.  (My
instinct is to say yes.)


make <text> #key fill size => text

    Create a new <text> 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 <text>
    object and to invoke mark-modified on all active marks that are
    affected.


;;;; <mark> details:

<Mark>s are associated with a <text> 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 <text> 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 <text> object should be designed to facilitate
this.

The association from <mark> to <text> is via a weak pointer, so that if all
references to a <mark> are dropped, the <text> quits bothering to update
it.


make <mark> #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 <text> 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.



;;;; <active-mark>s

<Active-mark> is a subclass of <mark>.  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 <active-mark> #key text active? start ...

    Make a new <active-mark>.  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

    <Active-mark>s can be turned on and off.  Mark-modified is only invoked
    for active marks that are currently turned on.  <Active-mark>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 <mark>s?

Should <mark>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 <text>
object could quickly throw away garbage marks, because there would be many
of them.



;;;; <code-fragment> details.

The details about <code-fragment>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 <code-fragment>, 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.]

<code-fragment> specializes text-modified in order to tell when it needs to
re-run the tokenizer.  When a region of text is modified, the
<code-fragment> 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 <text>s?

Question: should <text>s be atomic like described above, or should they
support nesting objects inside them?  Being able to nest arbitrary objects
inside a <text> object would be one way of addressing some of the
hyper-code like features we want.  Let's pursue this idea:

Instead of <text> 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 <text>, 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
<text> objects and other objects.  That would be the actual node in the
hyper-program.  The <text> 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 <text>s merged into some parent object, the parser
would have to be able to start extracting tokens from one <text> object and
then move to some other <text> 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 <text>s, the higher-level node would have to handle overall
redisplay and ^f'ing from one <text> into the next.  With objects nested
inside the <text>, the <text>'s view would have to deal with basically the
same issues.

Originally I was thinking that <text>'s would want to be atomic, but now
I'm leaning the other way.


;;;; <text-view>

A <text-view> is subclass of <view> that knows about how to display <text>
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.

<Text-view>s are responsible for rendering <text> objects.  As most <text>
objects are going to be larger then one screen worth, the <text-view> needs
to keep track of where in the <text> it should start displaying.  Also, as
<text-view>s are involved in converting UI events into edit operations, a
<text-view> needs a notion of a cursor.

The editing side of a <text-view> is pretty straight forward: input events
are mapped to manipulations of the next object.

The display side of a <text-view> is more complicated.  (Don't let anyone
claim that I ever said redisplay was easy.)  The <text-view> needs examine
the <text> object, build up its display lists, and render them.
Additionally, it needs to use <active-mark>s (or some other means) to
detect when a visible portion of the <text> 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 <text> object.

So to do this, the <text-view> 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 <text> object is
to make a subclass of <text-view> that overrides the display list
generation generic functions.

Furthermore, if one kind of <text> object is embedded in another kind of
<text> object (for example, a <styled-text> object embedded as a comment in
a <code-fragment> object), the parent <text-view> can invoke the
display-list generation routines on the child <text-view> directly instead
of allocating a large rectangle chunk for the child <text-view>, 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.]