Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!tut.cis.ohio-state.edu!bloom-beacon!eru!luth!sunic!mcsun!unido!gmdzi!jc
From: jc@gmdzi.UUCP (Juergen Christoffel)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Serious programming question
Keywords: editors, text, hypertext, data structures, memory management
Message-ID: <1391@gmdzi.UUCP>
Date: 24 Oct 89 17:57:10 GMT
References: <89295.142753CXT105@PSUVM.BITNET> <4002@helios.ee.lbl.gov> <8785@hoptoad.uucp> <299@fsu.scri.fsu.edu>
Organization: GMD - Gesellschaft fuer Mathematik und Datenverarbeitung mbH
Lines: 97

pepke@loligo (Eric Pepke) writes:

>It just so happens that I am curently working on a text editor for programming
>right now.  I am using a single buffer with a single gap using long integers
>to remember the offsets to the gap, which I think is similar to the way Capps 
>used to do it.  (If Capps were still a supported product, I would probably be
>using it.)

I've been thinking about these issues too for a while now and it
really looks that one has to re-invent most of the memory manager here
in order to get decent performance. Sigh.

Eric Pepke's description reminded me of an old MIT Memo which
described this technique in detail which you might be interested in;
luckily I found a copy after some searching:

	MIT/LCS/TM-165
	Theory and Practice of Text Editors
	(or: A Cookbook for an Emacs)
	Craig A. Finseth
	May 1980

It's still up-to-date these days; chapter two is about memory
management (about 30 pages), chapter three covers incremental
redisplay strategies.  You might like to get hold of a copy yourself.

The table of contents for chapter two lists:

	Data Structures
	Marks
	Interface Procedures
	Buffer Gap
	   Gap Size
	   Multiple Gaps and Why They Don't Work
	   The Hidden Second Gap
	Linked Line
	   Storage Comparison
	   Error recovery Comparison
	Multiple Buffers
	Paged Virtual Memory
	Editing Extremely Large Files
	Scratchpad memory

Poking around in the gnuemacs sources a bit assured me that it uses a
similar approach (routines like make_gap and move_gap called from
SelfInsert) so this approach seems to be still in use today.

Symbolics' lisp machines (which I'm quite familiar with) use the
linked line approach in their ZWEI editor substrate (ZWEI was
initially developed at MIT for MIT's lisp machines) and they must have
had a reason to not use the gap approach. Maybe it's their special
hardware support for various data structures.

Tradeoffs between these two approaches are visible e.g. for buffer
pointers (bps for short - or marks as they are called in MPW's
editor). If you use linked lines you may store bps relative to these
lines and have to update them only when inserting into the line they
point to while the gap approach would require to update them for each
insertion. It depends on how many bps you have ...

I really like bps and would like to see them in more editors (e.g.
Think C's) -- lisp machines use them a lot for example to record the
definitions of functions/procedures and global variables so you simply
have to mouse an indentifier while holding down a modifier key and off
you go to the definition (the real one, NOT the first textual
appearance in the buffer as THINK does -- that's annoying if you use
prototypes in C!)  So hopefully everybody writing a new editor for a
Mac spends some time thinking how s/he could provide such support.
It's really useful, not just for programmers but for large texts as
well, think of bps pointing to chapters/sections of your paper or
applications of various style sheets etc.

Using a general chunk approach (might think of linked lines as a
special case of chunks) instead of the gap approach seems a
straightforward way for editors which have some more complicated
structures to maintain than "just" linear text: Hypertext systems need
to keep track of nodes and links in their data structures and I wonder
whether the gap approach is capable of representing such text too in
an efficient manner. Does anybody have some experience in this and
would like to share it?

>Scroll bar handling is done as an integral part of the text editor.  I strongly
>recommend that you do this rather than follow TextEdit's method.  Scroll bar
>handling for long integers is very easy to do cleanly if you have enough 
>information available.  If you try to tack it on outside of the editor a la
>TextEdit, it is very difficult to do cleanly.

Would you please be so kind to elaborate a bit on this topic as I
would like to learn more about your approach. Thanks!

Juergen Christoffel

========================================================================
  Juergen Christoffel, jc@gmdzi.UUCP, (++49 2241) 14-2421
  German National Research Laboratory for Computer Science (GMD)
  Schloss Birlinghoven, Postfach 1240, D-5205 St. Augustin 1, FRG
========================================================================