OS/2 Shareware BBS: 5 Edit/05-Edit.zip/me34src.zip/me3/doc/Undo.article

Text File | 1995-01-14 | 28KB | 677 lines

-*-text-*-


          Implementing Undo for Text Editors
          ------------ ---- ---    ---- -------

                Craig Durland
               [e-mail]
                Copyright 1991


                February 1991
                   Updated
               September 1991
                February 1992
                November 1992

Probably anyone who has used a text editor has, at one time or another,
made a boo boo and immediately wished they could to go back in time and
not do it all over again.  The Undo command gives that ability by moving
backwards in time, reversing the effects of the most recent changes to
the text.  Some undo commands can go back to the beginning of time,
undoing all changes that have occurred to the text.

The undo described in this article is a subset of the idealized undo -
it only reverses changes to text.  It doesn't keep track of cursor
movements, buffer changes or the zillions of other things we do while
editing text.  While this can make undoing changes disconcerting because
it can jump from change to change differently from what you remember, it
also reduces the amount of stuff that the editor needs to remember
(saving memory) and helps keep the editor from bogging down trying to
keep track of whats been going on.  Finally, the material presented is
for text editors.  Editors of other types may find some of the
discussion relevant but that will be a happy accident.

Jonathan Payne (author of JOVE) has stated that "Undo/redo is trivial to
implement" (comp.editors, Tue, 2 Jan 1990).  Having just implemented
undo for the editor I am working on, I think that straight forward is a
better term than trivial.  Since it took me a long time to figure out a
workable undo scheme, I thought others might be interested in what I
did.



Caveats:  The algorithms, code and data structures used in this article
are based on working and tested code that has been "sanitized" to remove
obscuring details (like what stack data structures I used).  If you use
the code, make sure you understand it so that you can properly fill in
the missing details.

Conditions:  You are free to use the algorithms, code and data
structures contained in this article in anyway you please.  If you use
large chunks, I would appreciate an acknowledgment.  If you distribute
this article, in whole or part, please retain the authorship notice.



            What is Not Discussed
            ---- --    --- ---------

Redo is a undo for undo.  Very handy if you undo one time to many and
need to undo that last undo.  I haven't implemented it yet but I think
that it will be easy to modify the algorithms to support it.  I also
think some dragons are there but they are hiding from me.  We'll see
when I actually get around to doing it.



       Editor Implementations and How They Affect Undo
       ------ --------------- --- --- ---- ------ ----

Two popular ways text editors store text are "buffer gap" and "linked
list of lines" (described in detail else where - see comp.editors).  As
you might imagine, different implementations for storing text can affect
undo implementations.  Fortunately for this article, the affects are
relatively minor.  As I discuss data structures and algorithms, I will
point out the differences.

Note:  I will refer to buffer gap editors as BGE and linked list editors
as LLE.


           What You Need to Save to Implement Undo
           ---- ---    ---- --    ---- --    --------- ----

I use Undo Events to represent text changes.  These events are kept in a
undo stack, most recent event at the top of the stack.  There is one
stack per text object (buffer in Emacs) so undo can only track changes
on a per buffer basis.  This simplifies things quite a bit over tracking
all changes globally in a multibuffer editor.

I found that four event types seem to be enough describe all text
changes.  They are:
- BU_INSERT:  This event is used when text is inserted.  The most common
  case is when you type.  When text is inserted, we need to remember how
  much was inserted and where it was inserted.  We don't need to
  remember the what the text was because to undo this type of event, all
  we have to do is delete the inserted text.  Note that in order to
  reduce the number of events saved (and memory used), you need to be
  able to detect text that is inserted sequentially (like when you type
  "123") so that all these events can packed into one event.  This can
  affect more than you would think at first glance and will be discussed
  more fully else where.

- BU_DELETE:  This event is used when text is deleted, for example when
  you use the delete (or backspace) key.  Here we need to remember the
  place where the deletion took place and the text to be deleted.  Note
  that we have to save the text before (or while) it is deleted.  This
  is can cause trouble for some editor implementations.  Again, event
  packing can save much of space if users like to lean on the delete
  key.  To undo a delete, we have to insert the deleted text at the
  place where it was deleted.

- BU_SP:  A sequence point is a stopping point in the undo stack.  It
  tells the undo routine that this is the last event to undo so the user
  will think that one of his actions has been undone.  Note that this
  implies that one user action may cause one or (many) more undo events
  to be saved.  This is especially true when the editor supports macros
  or an extension language.  I think that it is important that one press
  of the undo key undoes one user action (there are a few exceptions
  (like query replace)).  Probably one of the hardest things to "get
  right" (from the users point of view) is where to place sequence
  points.  Here is my list of rules for sequence points (take these with
  a grain of salt - these are my opinions with nothing to back them up.
  They may change.):
  - Need sequence points so undoing stops at "natural, expected" places.
  - Undo should stop where user explicitly marked the buffer as
    unchanged (like save buffer to disk).  These are usually UNCHANGED
    events.
  - A string of self insert keys should undo as one.  Its pretty
    annoying to have to hit undo 14 times to undo "this is a test".
  - A word wrap or Return should break a character stream.  Thus undo
    only backs up a line at at time, probably better than undoing an
    entire paragraph when only one line needed undoing.
  - Commands, macros, programs written in the extension language, etc
    should undo as a unit.  ie if pressing a key caused a bunch of stuff
    to happen, pressing undo should undo all the stuff the key caused.
  - Since rules can't cover all cases (like query replace), programs
    need to be able to add sequence points.

  I also store the buffer modified state here so I know to mark the
  buffer as unchanged if it was before this change happened.

- BU_UNCHANGED:  This event marks a time when the text was marked as
  unchanged or saved.  Examples include saving the text to the disk.
  When undoing, this event marks a stopping point:  The user has undoed
  back to a time when the buffer was "safe".  When you make an
  inadvertent change to text that you only wanted to look at, it is
  psychologically reassuring to know the text is back to its original
  state.

  Only the most recent unchanged event actually indicates that the
  buffer contents match those out on the disk (and every buffer change
  before and after that event means the buffer is out of sync with the
  disk).  For undo, this means that only the most recent unchanged event
  is valid - when that event is undone, the buffer matches the disk.
  After that one, other unchanged events need to be ignored because the
  buffer at that point can't match the disk.

  Note that BU_UNCHANGED events are really just special cases of
  sequence points.  You could easily just combine them into one event.

It should be obvious by now that much editing would generate a LOT of
undo events.  Unless your computer has an infinite amount of memory, you
need some rules about when to start throwing away events.  Since
different people will have different ideas about this and the amount of
memory can greatly affect this, you need to let the user control it.
There are three parameters that need to be specified:
- Save or don't save undos.  For Emacs-like editors, there are probably
  many buffers that don't need (or want) undo.  For example, I don't
  care if help buffers have undo.  Not turning on undo for all buffers
  can really save memory and help performance (undo can really slow down
  extension programs).
- The maximum amount of text saved.  When text is deleted, it has to be
  saved somewhere.  The more deleted, the more that needs to saved.  It
  adds up.  We need a point where we discard some of the old saved text
  in order to save some.  Note that a big delete can clean out all the
  existing undos and worst case, the delete is bigger than the max so we
  have to throw away the undos and ignore the delete (because there is
  not enough room to save it).
- The maximum number of events saved.  Each event takes up a bit of
  memory.  Events pile up amazingly fast during editing.  At some point
  we have to start throwing away the old to make room for the new (kinda
  like my garage).  When dumping events, you have to also clean up any
  text the deleted event might have saved.

It can be a real guessing game to figure out how to balance the number
of events saved against text saved.  Different editing operations use up
one or the other at different rates.  I'm currently using 600 events and
a 5K save buffer.





               When an Editor Does Undo
               ---- -- ------ ---- ----

Given the undo event types and rules, the editor just has to save undo
events when needed and add sequence points at the "proper" times.  Now
is the time you will be glad you funneled all you buffer changes through
just a couple of insert/delete routines.  Here is where I save events
for my Emacs-like editor:
- Insert a block of text.        save_for_undo(BU_INSERT,n);
  This routine is used when doing things like a kill buffer yank.  It is
  also used to undo a delete so care has to be taken not to get into a
  do/undo tug of war.
- Read a file.                save_for_undo(BU_UNCHANGED,0);
  We mark the buffer as unchanged because it has been cleared and filled
  with new text.  Note that it is up the buffer clear routine to save
  the delete text.  Also note that to do a "real" undo, we should also
  save_for_undo(BU_INSERT,<characters in file>).  I don't because I
  don't think it makes sense and because of the clear buffer problem
  mentioned below.
- Insert a file.            save_for_undo(BU_INSERT,n);
  If you don't know the size of the file that is going to be inserted,
  you can use this trick:  Insert the file (and figure out how much was
  inserted), go back to where the file was inserted (the start of the
  new text) and then save the undo.
- Insert n characters.            save_for_undo(BU_INSERT,n);
  This is used for the self inserting characters.
- Delete n characters.            save_for_undo(BU_DELETE,n);
  Have to be careful here because this routine is also used to undo
  character inserts.  Actually, the undo routine is the one who cares
  and protects against this.
- After a key has been processed.    save_for_undo(BU_SP,0);
- Mark a buffer as unchanged.        save_for_undo(BU_UNCHANGED,0);
- Save a file.  This routine doesn't need to do anything because it
  calls the buffer_is_unchanged() routine.  That routine saves the event.

Where I should (but don't) save undo events:
- Clear buffer.  Because it is awkward to do with my type of editor.
  See below for more on this.  Other editors would not have this routine
  and would just use delete.  Instead, I clear all undos.

To do undo, the editor just calls the undo routine.



               Data Structures
               ----    ----------

Each text object (buffer) has a pointer to a undo header.  This header
contains a undo event stack, number of events in the stack (so I can
easily check to see if the stack has grown too big), a flag that
indicates whether or not the BU_UNCHANGED events are valid and an area
in which to save deleted text.

In C, this looks like:
     typedef struct
     {
       Undo *undo_stack;    /* where the undo events are */
       int undo_count;        /* number of undos in the stack */
       int there_is_a_valid_unchanged_event;
       Bag *bag;        /* deleted text saved here */
     } UndoHeader;

An undo stack is a linked list of undo events.  I used a linked list
because it was easy and worked well but there are many other ways to
store the data that would probably work as well.  An event contains a
pointer to the next (older) event, the event type (BU_INSERT, etc), a
marker to where the event took place, the number of characters involved
and a pointer to the saved text (if any).  Note that some events may not
use some of these fields.  The clever programmer could probably save
quite a bit of space by having different (sized) structures for each
event type.

LLEs (Linked List Editors) can run into problems when asked to save
delete events.  Its quite possible that the we could be asked to save
more text than buffer contains.  For example, in Emacs, the user could
hit control-U a bunch of times and hit the delete key - delete 16384
characters when the buffer only contains 53.  With a BGE (Buffer Gap
Editor), this is very easy to check but is very time consuming with a
LLE.  What I do with LLE is "trust but verify".  I make enough room to
hold that much deleted text, then go ahead and try and save it.  I then
figure out how much I really saved (a side affect of copying the text)
and save that number.  The big drawback with this is that its easy to
clear out most of the undo stack when you didn't need to and looks very
fishy when you can't undo very much.  The other way around this is to
put the "save-deleted-text" stuff in the routine that actually deletes
the text but this would add a lot of noise to a already hard to
understand routine.

A problem related to the I-don't-know-how-much-is-going-to-be-deleted
problem is the clear-buffer problem.  With BGE, you know how much you
are going to remove, with LLE, you don't.  So, I just clear the undo
stack when the buffer is cleared because 1) most buffers will probably
be bigger than the undo buffer anyway and cause it to be cleared and 2)
buffer clears don't happen very often - usually for buffer deletes and
file reads.

C code:
     typedef struct Undo
     {
       struct Undo *next;    /* pointer to next older event */
       int type;
       UnMark mark;        /* where the event took place */
       int n;            /* number of characters involved */
       char *text;        /* where deleted text is saved */
     } Undo;

In my editor, I have the concept of bags.  Bags hold various types of
text objects and I have a lot of builtin support for them.  It was
natural and very easy to use these to hold deleted text.  Your editor is
probably different so you'll have to use something else (like
malloc()ing some space).  I use one per buffer and holds it all the
deleted text.  The undo delete events point into the bag (actually, I
use offsets but the concept is the same).

The undo markers are where in the buffer the event took place.  These
only matter for insert and delete events.  This is one of the areas
where editor implementation really matters.  A BGE (buffer gap editor)
is a real win here.  Since undo events are effectively snapshots of
buffer history, as you undo, the buffer returns to its exact state back
in time.  A BGE mark is just an offset into the buffer.  We can just
store this offset in the event and never mess with it because we know
that it will be correct when we undo to the point where we want to use
it.  We can't do this with a LLE (linked list editor).  A LLE mark is a
pair:  (line pointer, offset in line).  Both editor types have to adjust
marks as text is inserted and deleted but unlike the BGE, LLE marks can
become invalid as time goes on (and lines unlinked).  One example of
this is if you insert text into the middle of a block and then delete
that block.  The delete has unlinked the lines that were inserted so the
marks with insert are invalid.  When you undo the delete, you can't undo
the insert because you no longer know where it took place.  This is not
a problem with BGE because even though the delete made the insert mark
point to the wrong place, when the delete was undoed, the mark became
valid again.

To get around this problem a LLE has to either 1) track all cursor
movement or 2) calculate the pair (line number, offset in line).
  1) Pros:  Can undo cursor movements.
     Cons:
       - This would generate bazillions of cursor move events.
       - This could really be a pain in the butt and slow down the
       cursor movement routines.  One of the main reasons for writing a
       LLE is not having to worry about stuff like this.
  2) Pros:
       - Some LLEs might already keep marks like this.
       - You can (sometimes) keep track of this position so that you
       don't have recalculate it all the time.  You would track it when
       you could and mark it as invalid when you couldn't.
       - Its easy to calculate.
       - These marks work just like BGE marks.
       - There are some optimizations that can be made if many events
       are generated (sequentially) for the same line.  Basically, if
       the dot line remains the same, you calculated the line number
       earlier.  Caution - this can be trickier than you think.
     Cons:
       - It takes time to calculate the mark.
       - You have to calculate it a lot.
       - It adds a bunch of piddlie details to try and track the dot
       and greatly increases the chances of screwing up.

I chose to do 2) (since my editor is a LLE).  Here is the C code:
     typedef struct
     {
       int line;
       int offset;
     } UnMark;

For a BGE, just use the mark type you already have.

Some combinations of events occur together frequently and it might be a
win to create an event to take advantage of them.  For example, replace
operations involve a delete and insert at the same place.  If you packed
these two events into one, you could potentially save lots of space in a
big query replace.


             Alternative Data Structures
             ----------- ---- ----------

I've glossed over how I actually store the undo stack.  This is because
there many (good) ways to do it.  I use linked lists because they are
simple.  A more clever and compact method would be to pack the deleted
text into the event structure (using the "clever" technique mentioned
above) and store the event plus text in a fixed size data area.  This
has several advantages:  You don't have to worry the number of events -
when you run out space to store them, start removing the old events.  It
is much easier to garbage collect the undo stack during undo.  Its
also easier to make room for a new event.  The disadvantages are that
you have to worry about structure alignment (and machine architecture)
and the some of the code will get messy (in my opinion).  The old trade
off of fast and small versus big and simple (or, as Julie Brown would
say, "I like 'em big and stupid").




               Global Variables
               ------ ---------

I use a few global variables to make controlling undo a little easier.

Bool do_undo;
  This variable is TRUE if undo is turned on for the current buffer.
  The switch buffer code sets this so people who need to know can do so
  quickly.  The user can change it by toggling a buffer flag.

Buffer *current_buffer;
  Pointer to the buffer where changes are taking place.  The current
  undo header hangs off this buffer.

int max_undos = 600;
  The maximum number of undo events.

int max_undo_saved = 5000;
  The maximum amount of deleted characters that can be saved.



          Algorithm for Saving Undo Events
          --------- ---    ------ ---- ------

I save undo events as they occur.  I leave it to the undo routine to
figure out how to undo this type of event because its easy, undo has
more time to do it and this routine should be as fast as possible
because most undo events will never be used and you want the editor to
keep up with you.

     save_for_undo(type,n)
       int type;    /* event type:  BU_INSERT, etc */
       int n;        /* number of characters involved (if any) */
     {
       Undo undo;
       UnMark mark;

       if (!do_undo) return;    /* don't save undos for this buffer */

       switch (type)
       {
     case BU_INSERT:            /* Characters inserted */
       set_unmark(&mark);
       pack_sequential_insert_events();

       undo.n = n;
       undo.mark = mark;

       break;
     case BU_DELETE:            /* Characters deleted */
     {
       if (n == 0) return;            /* that was easy! */

       set_unmark(&mark);
       undo.mark = mark;
       open_bag(n);             /* make sure there is enough space */
       undo.n = save_text(n);    /* returns number of characters saved */

       break;
     }
     case BU_SP:                /* Set sequence point */
       if (last_event_was_a_sequence_point()) return;
       break;
     case BU_UNCHANGED:        /* Buffer has been marked safe */
       if (last_event_was_a_save()) return;
       header->there_is_a_valid_unchanged_event = TRUE;
       break;
       }

       undo.type = type;

       push_undo(&undo);
     }



             Algorithm for Undoing Events
             --------- --- ------- ------

This routine performs undo by reversing the effects of undo events from
most recent until it finds a sequence point or runs out of events.

Note that undo is turned off so we don't try and re-save undo events as
we march through the stack.

If the last event undid was a UNCHANGED, we need to add a new one to the
undo list (to replace the one we popped).  If we don't, when we undo
back to this point in the future, there won't be a UNCHANGED event to
tell us the buffer is unchanged.  Ditto if we empty the undo stack.

UNCHANGED events are a no-op if the buffer is not modified.  This makes
<save buffer><undo> work "nicer" and lets the above work (if it wasn't,
undo would stop at the UNCHANGED event and you couldn't undo any more).

     undo()
     {
       int undo_flag, num_events, something_happened, push_an_unchanged;
       Undo *ptr;

       if (no_undos()) return;

       undo_flag = do_undo; do_undo = FALSE;

       num_events = 0;
       something_happened = FALSE;
       push_an_unchanged = FALSE;

       while (ptr = pop_undo())
       {
     num_events++;
     switch (ptr->type)
     {
       case BU_INSERT:    /* To undo: Delete inserted characters */
         something_happened = TRUE;
         goto_unmark(&ptr->mark);
         delete_text(ptr->n);
         break;
       case BU_DELETE:    /* To undo: Insert deleted characters */
         something_happened = TRUE;
         goto_unmark(&ptr->mark);
         insert_block(ptr->text, ptr->n);
         break;
       case BU_UNCHANGED:    /* At this point, buffer might be unchanged */
         if (header->there_is_a_valid_unchanged_event &&
         buffer_is_modified())
         {
        buffer_modified(FALSE);
        something_happened = TRUE;
        push_an_unchanged = TRUE;
         }
         header->there_is_a_valid_unchanged_event = FALSE;
         /* fall through:  a BU_UNCHANGED acts like a sequence point */
       case BU_SP:        /* Hit a sequence point, stop undoing */
         if (something_happened) goto done;
         break;
     }
       }

     done:

       gc_undos(num_events);    /* clean up the undo stack needed */

       do_undo = undo_flag;

       if (push_an_unchanged || (undo_stack_empty() && buffer_not_modified()))
         save_for_undo(BU_UNCHANGED,0);
     }



               Miscellaneous Algorithms
               ------------- ----------

Here are some miscellaneous routines to flesh out undo.  Note that there
are a lot missing, for example undo stack management and garbage
collection.  The routines presented here aren't as "clean" as I'd like
because they have to know how the undo stack is implemented.

Note:  When I say walk the stack, I mean move towards the older events.
I do this because it is easy and in the case of undo() and thats what you
want.


The next routine is used to make space available to hold a copy of the
text that will be deleted.  Basically, it figures out which (if any) of
the older events need to be removed from the stack to make room in the
bag.  It does this by looking at delete events (the only event that
saves text) and finding an event such that by deleting that event and all
older events, it will remove the minimum number of events necessary to
free enough space so that the bag can hold space_needed more characters.
The key here is that the number of characters in the bag is the sum of
all delete events (the n in the Undo structure).  Note it would be
faster, in general, to walk the stack backwards (from oldest event to
youngest) and find the first event that met the requirements but that is
not possible the way I implemented the stacks.


     /* Check to see if space_needed is available in the bag.  If not,
      *   try and pack the bag and stack to make enough room.  If more
      *   space is requested than we allow, clear the stack because if
      *   we can't save this undo, every undo before this one is
      *   invalid.
      * Returns:
      *   TRUE:  Bag (now) has enough room.
      *   FALSE:  You want too much space and can't have it.  Undo stack
      *     cleared.  Try again with a more reasonable request.
      */
     static int open_bag(space_needed) int space_needed;
     {
       int tot, da_total, total_so_far;
       Undo *ptr, *da_winner;
       UndoHeader *header;

       header = <the undo header for the current buffer>;

       total_so_far = bag_size(header->bag); /* number of characters in bag */
       tot = space_needed -(max_undo_saved -total_so_far);

       if (tot <= 0) return TRUE;        /* Plenty of room! */

       if (space_needed > max_undo_saved)    /* You want too much! */
       {
     clear_undos();
     return FALSE;
       }

       da_winner = NULL;
       for (ptr = <walk undo stack starting at the most recent event>)
       {
     if (ptr->type == BU_DELETE)
     {
       if (total_so_far >= tot)    /* found enough space here */
       {
         da_winner = ptr;
         da_total = total_so_far;
       }
       else break;        /* the last one was the one we wanted */
       total_so_far -= ptr->n;
     }
       }

       /* We KNOW (and can prove it) that da_winner != NULL because
        *   bag_size >= tot > max - bag_size
        *   (from
        *   max_undo_saved >= space_needed > max_undo_saved -bag_size
        *   among other things).  Since bag_size is the sum of all the
        *   BU_DELETEs, there must be one or more events that are
        *   winners.
        */
       for (ptr = <walk undo stack starting at da_winner>)
       {
     free_undo(ptr);
       }
       pack_bag(da_total);    /* remove text from bag, fix up pointers */

       return TRUE;
     }


     /* Go though the undo stack and adjust the text indices to reflect
      * n characters being removed from the front of the bag.  Shift n
      * characters off the front of the bag.
      */
     static void pack_bag(n) int n;
     {
       Undo *ptr;
       UndoHeader *header;

       header = <the undo header for the current buffer>;

       for (ptr = <walk undo stack starting at the most recent event>)
     if (ptr->type == BU_DELETE)
     {
       <adjust ptr->text back by n characters>
     }

        /* remove n characters from front of bag */
       slide_bag(header->bag,n);
     }


Here are a couple of routines that you will need if you have a LLE.
This is how to calculate and use undo marks.

     static void goto_unmark(mark) UnMark *mark;
     {
       goto_line(mark->line);
       next_character(mark->offset);
     }

     static void set_unmark(mark) UnMark *mark;
     {
       extern Mark *the_dot;    /* the dot in the current buffer */

       register Line *lp, *dot_line;
       register int line;

       dot_line = the_dot->line;
       for (line = 1, lp = BUFFER_FIRST_LINE(current_buffer);
        lp != dot_line; lp = lp->l_next)
     line++;

       mark->line = line;
       mark->offset = the_dot->offset;
     }