From: nmouawad@waterloo.edu (Naji Mouawad)
Subject: Undoing, Emacs and unlimited files ... summery.
Organization: University of Waterloo
Date: Mon, 27 Jul 1992 17:18:47 GMT


Firt of, I would like to thank Michael Meissner, Mike Hejl, Craig
Durland, Jim Cathey, Sami-Jaakko Tikka, and Guy Harris for
their detailed answers to my querry concerning the ability of some
editors such as Emacs to undo the effect of a command and to
manipulate unlimited file size.

I stand corrected on my assumption regarding Emcas' ability to handle
unlimited file size. Almost everyone pointed out that Emacs (in almost
all its incarnations) does not handle unlimited file size. The limit
is determined by available (virtual) memory. 

From Jim Cathey's answer:

	(GNU Emacs) The file size is not unlimited.  The file is read into
	memory with a single read() call, so it has to fit into the virtual
	address space of a task.  On some machines (like ours) VM space is
	limited (from 2-8 MB depending on model), so huge files do not work
	on these.

This is the easy part.

The ability of an editor to "undo" seems pretty well tighed to its
internal representation of the file. There seems to be two methods for
representing a file: the linked list method and the "Gap method".

Quoting from Michael Meissner's answer:

Emacs uses the buffer gap mathod.  You have one large contingous
buffer with a gap somewhere in the middle:

        +---------------+---------------+---------------+
        | left side     | gap           | right side    |
        +---------------+---------------+---------------+

Whenever you want to insert text, the gap is moved to the point of
insertion (usually it's fairly close, because you just moved a couple
of lines from the last position), and insert the text.  If the buffer
fills up, it realloc's a bigger buffer, and puts a gap in.  Buffer gap
is usually a lot simpler in terms of coding, than other
representations, which include paged buffer gap, keeping each line in
a separate buffer, etc.


Jim Cathey's adds:

This approach incredibly speeds up searches, file opens and saves, and
insertion/deletion, the things that people do most and that they would
most notice having performance problems.  It also simplifies a lot of
the internal editing routines.  It does, however, complicate rendering
the current view of the display, although this is not too onerous a
task.  As a benefit, newlines can be treated just like any other
characters, binary data can be edited with impunity, and there is no
concept of a 'line' or a line length limit internally.  All nice
features.


Now, there are two types of undo. One which "undoes" the effect of
selected commands such deleting a line, or a block of text etc ...
another which undoes everything. Each approach has its strong and week
points and is quiet an undertaking.

Mike Hejl who wrote his own editor has implemented it as a doubly
linked list. His editor is capable of the undo of the first kind:

  The file is stored internally as a double linked list. A node is
  allocated (malloced) for each line in the file and contains various
  flags (bitwise; like block marks), pointers to next and last, and a
  pointer to a dynamically allocated buffer for the actual string. I
  won't get into ctrl and tab processing. This allows an "unlimited"
  file size. Further, the dynamically allocated strings allow
  unlimited length line sizes (but I have limited them to the system
  buffer size BUFSIZ for portability reasons with stdio.h and string.h)

  Unlike vi, this method requires reading the entire file into active
  memory. [Random access, like vi does, is difficult on char files.] 

  Various pointers are kept as indexes into the file - current line
  pointer and counter,  Block mark position, etc.

  Line undo is easy - simply buffer the current line each time a delete (or
  undoable operation) is performed.  Block undo isn't too bad but the
  entire file must be buffered (again dynamically and in the same
  method as above) before the block operation is performed.
  [Obviously, I have built in advanced, versatile block operations.]
  To undo a block operation, just free the "active" file's memory and
  set the pointers (also saved) to the buffered file. Unfortunately,
  this method will only buffer the latest operation (which is entirely
  adequate for my needs). I don't buffer single char changes - its a 
  waste.



Likewise, Craig Durland has implemented undo for his editor. He has
written an article detailing the process. From the header:

                  ------------ ---- --- ---- -------

                            Craig Durland
                           craig@cv.hp.com
                            Copyright 1991


                            February 1991
                               Revised
                           September 1991
                            February 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.


His appoach is event-driven. He lists four events that one should keep
track of in order to manage undo: Insert, Delete, SP and Unchanged.
While delete and insert are events generated by the user, SP and
Unchanged are "turning points" within the sequence of past events. SP
tells the editor that all the steps requiered for the current undoing
have been performed, while unchanged marks a point in time where the
copy of the file in memory corresponds to the file on disk. Craig uses
a stack of events to implement the undo mechanism.


As far as "total undo" is concerned, I did not get any detailed
answer. It seems that this has to do with "logging". A technique for
keeping a log file of all the events that took place while the file
was edited. Apparently there is a lot of activity going-on within the
data-base community in order to find good ways for implementing the
logging technique.


Finally, Guy Harris states:

   Finseth's posting is the one in this group with the title "Emacs
   implementations, list of, regular post [long]".  Some selected bits from
   it are attached.

   I don't know if his book "The Craft of Text Editing" discusses
   implementation details or not.  You can probably send him mail asking
   him about his paper on editor implementation.

                 Emacs Implementations and Literature


   Changes and additions to:                       last posted 17 July 1992
   Craig A. Finseth                        reposted about every 2 months

        fin@unet.umn.edu
        Finseth@nic.mr.net

        +1 612 644 4027

        1343 Lafond
        St Paul MN 55104-2437
        USA

   This document provides a partial -- and not comprehensive -- list of
   implementations of Emacs-type editors and literature about such
   editors.  You can help make it more comprehensive by sending me
   additional information and/or updates.

   This document is available via anonymous FTP from:

        mail.unet.umn.edu in import/fin/emacs

   To be included in this list, a piece of literature should be a book,
   manual, article, paper, or something that covers (or mentions) Emacs
   in particular or text editing techniques in general.  Specifically
   excluded are items that are only of interest to non-Emacs users (a
   book on "how to use vi") or vendor manuals for Emacs implementations
   (as those are implicitly included in the implementations).  Non-vendor
   manuals are included.

   To be included in this list, an implmentation must either (1) be
   "advertised" as being an Emacs-type editor or (2) be extensible and
   come with an Emacs command set "mode" already written.  Editors that
   are extensible but do not come with such a mode (i.e., you have to
   write it yourself) are not listed.

        ...

         -------------------- Literature --------------------

        ...



   Title:          The Craft of Text Editing: Emacs for the Modern World
   Author(s):      Craig A. Finseth
   Publisher:      Springer-Verlag
   Size:           220pp, 10 chapters, 5 appendices
   ISBN:           0-387-97616-7, 3-540-97616-7
   Price:          $39.95


Once again, I would like to thank all of you who took the time and
effort for replying in detail. I hope I did justice to all of the
replies. All mistakes are mine.

naji.




--
     -------------------------------------------------------------------
    | Naji Mouawad  |          nmouawad@watmath.waterloo.edu            |
    |  University   |---------------------------------------------------|
    | Of Waterloo   |   "The Stranger in us is our most familiar Self"  |
     -------------------------------------------------------------------
Newsgroups: comp.lang.c++
From: nikki@trmphrst.demon.co.uk (Nikki Locke)