   Copyright (C) 1992 - 1996 Ben Wing.  Copyright (C) 1996, 1997 Sun
Microsystems.  Copyright (C) 1994, 1995 Free Software Foundation.
Copyright (C) 1994, 1995 Board of Trustees, University of Illinois.

   Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.

   Permission is granted to copy and distribute modified versions of
this manual under the conditions for verbatim copying, provided that the
entire resulting derived work is distributed under the terms of a
permission notice identical to this one.

   Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions, except that this permission notice may be stated in a
translation approved by the Foundation.

   Permission is granted to copy and distribute modified versions of
this manual under the conditions for verbatim copying, provided also
that the section entitled "GNU General Public License" is included
exactly as in the original, and provided that the entire resulting
derived work is distributed under the terms of a permission notice
identical to this one.

   Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions, except that the section entitled "GNU General Public License"
may be included in a translation approved by the Free Software
Foundation instead of in the original English.

Line Start Cache
================

   The traditional scrolling code in Emacs breaks in a variable height
world.  It depends on the key assumption that the number of lines that
can be displayed at any given time is fixed.  This led to a complete
separation of the scrolling code from the redisplay code.  In order to
fully support variable height lines, the scrolling code must actually be
tightly integrated with redisplay.  Only redisplay can determine how
many lines will be displayed on a screen for any given starting point.

   What is ideally wanted is a complete list of the starting buffer
position for every possible display line of a buffer along with the
height of that display line.  Maintaining such a full list would be very
expensive.  We settle for having it include information for all areas
which we happen to generate anyhow (i.e. the region currently being
displayed) and for those areas we need to work with.

   In order to ensure that the cache accurately represents what
redisplay would actually show, it is necessary to invalidate it in many
situations.  If the buffer changes, the starting positions may no longer
be correct.  If a face or an extent has changed then the line heights
may have altered.  These events happen frequently enough that the cache
can end up being constantly disabled.  With this potentially constant
invalidation when is the cache ever useful?

   Even if the cache is invalidated before every single usage, it is
necessary.  Scrolling often requires knowledge about display lines which
are actually above or below the visible region.  The cache provides a
convenient light-weight method of storing this information for multiple
display regions.  This knowledge is necessary for the scrolling code to
always obey the First Golden Rule of Redisplay.

   If the cache already contains all of the information that the
scrolling routines happen to need so that it doesn't have to go
generate it, then we are able to obey the Third Golden Rule of
Redisplay.  The first thing we do to help out the cache is to always
add the displayed region.  This region had to be generated anyway, so
the cache ends up getting the information basically for free.  In those
cases where a user is simply scrolling around viewing a buffer there is
a high probability that this is sufficient to always provide the needed
information.  The second thing we can do is be smart about invalidating
the cache.

   TODO - Be smart about invalidating the cache.  Potential places:

   * Insertions at end-of-line which don't cause line-wraps do not
     alter the starting positions of any display lines.  These types of
     buffer modifications should not invalidate the cache.  This is
     actually a large optimization for redisplay speed as well.

   * Buffer modifications frequently only affect the display of lines
     at and below where they occur.  In these situations we should only
     invalidate the part of the cache starting at where the
     modification occurs.

   In case you're wondering, the Second Golden Rule of Redisplay is not
applicable.

Extents
*******

Introduction to Extents
=======================

   Extents are regions over a buffer, with a start and an end position
denoting the region of the buffer included in the extent.  In addition,
either end can be closed or open, meaning that the endpoint is or is
not logically included in the extent.  Insertion of a character at a
closed endpoint causes the character to go inside the extent; insertion
at an open endpoint causes the character to go outside.

   Extent endpoints are stored using memory indices (see `insdel.c'),
to minimize the amount of adjusting that needs to be done when
characters are inserted or deleted.

   (Formerly, extent endpoints at the gap could be either before or
after the gap, depending on the open/closedness of the endpoint.  The
intent of this was to make it so that insertions would automatically go
inside or out of extents as necessary with no further work needing to
be done.  It didn't work out that way, however, and just ended up
complexifying and buggifying all the rest of the code.)

Extent Ordering
===============

   Extents are compared using memory indices.  There are two orderings
for extents and both orders are kept current at all times.  The normal
or "display" order is as follows:

     Extent A is ``less than'' extent B, that is, earlier in the display order,
     if:    A-start < B-start,
     or if: A-start = B-start, and A-end > B-end

   So if two extents begin at the same position, the larger of them is
the earlier one in the display order (`EXTENT_LESS' is true).

   For the e-order, the same thing holds:

     Extent A is ``less than'' extent B in e-order, that is, later in the buffer,
     if:    A-end < B-end,
     or if: A-end = B-end, and A-start > B-start

   So if two extents end at the same position, the smaller of them is
the earlier one in the e-order (`EXTENT_E_LESS' is true).

   The display order and the e-order are complementary orders: any
theorem about the display order also applies to the e-order if you swap
all occurrences of "display order" and "e-order", "less than" and
"greater than", and "extent start" and "extent end".

Format of the Extent Info
=========================

   An extent-info structure consists of a list of the buffer or string's
extents and a "stack of extents" that lists all of the extents over a
particular position.  The stack-of-extents info is used for
optimization purposes - it basically caches some info that might be
expensive to compute.  Certain otherwise hard computations are easy
given the stack of extents over a particular position, and if the stack
of extents over a nearby position is known (because it was calculated
at some prior point in time), it's easy to move the stack of extents to
the proper position.

   Given that the stack of extents is an optimization, and given that
it requires memory, a string's stack of extents is wiped out each time
a garbage collection occurs.  Therefore, any time you retrieve the
stack of extents, it might not be there.  If you need it to be there,
use the `_force' version.

   Similarly, a string may or may not have an extent_info structure.
(Generally it won't if there haven't been any extents added to the
string.) So use the `_force' version if you need the extent_info
structure to be there.

   A list of extents is maintained as a double gap array: one gap array
is ordered by start index (the "display order") and the other is
ordered by end index (the "e-order").  Note that positions in an extent
list should logically be conceived of as referring _to_ a particular
extent (as is the norm in programs) rather than sitting between two
extents.  Note also that callers of these functions should not be aware
of the fact that the extent list is implemented as an array, except for
the fact that positions are integers (this should be generalized to
handle integers and linked list equally well).

Zero-Length Extents
===================

   Extents can be zero-length, and will end up that way if their
endpoints are explicitly set that way or if their detachable property
is nil and all the text in the extent is deleted. (The exception is
open-open zero-length extents, which are barred from existing because
there is no sensible way to define their properties.  Deletion of the
text in an open-open extent causes it to be converted into a closed-open
extent.)  Zero-length extents are primarily used to represent
annotations, and behave as follows:

  1. Insertion at the position of a zero-length extent expands the
     extent if both endpoints are closed; goes after the extent if it
     is closed-open; and goes before the extent if it is open-closed.

  2. Deletion of a character on a side of a zero-length extent whose
     corresponding endpoint is closed causes the extent to be detached
     if it is detachable; if the extent is not detachable or the
     corresponding endpoint is open, the extent remains in the buffer,
     moving as necessary.

   Note that closed-open, non-detachable zero-length extents behave
exactly like markers and that open-closed, non-detachable zero-length
extents behave like the "point-type" marker in Mule.

Mathematics of Extent Ordering
==============================

   The extents in a buffer are ordered by "display order" because that
is that order that the redisplay mechanism needs to process them in.
The e-order is an auxiliary ordering used to facilitate operations over
extents.  The operations that can be performed on the ordered list of
extents in a buffer are

  1. Locate where an extent would go if inserted into the list.

  2. Insert an extent into the list.

  3. Remove an extent from the list.

  4. Map over all the extents that overlap a range.

   (4) requires being able to determine the first and last extents that
overlap a range.

   NOTE: "overlap" is used as follows:

   * two ranges overlap if they have at least one point in common.
     Whether the endpoints are open or closed makes a difference here.

   * a point overlaps a range if the point is contained within the
     range; this is equivalent to treating a point P as the range [P,
     P].

   * In the case of an _extent_ overlapping a point or range, the extent
     is normally treated as having closed endpoints.  This applies
     consistently in the discussion of stacks of extents and such below.
     Note that this definition of overlap is not necessarily consistent
     with the extents that `map-extents' maps over, since `map-extents'
     sometimes pays attention to whether the endpoints of an extents
     are open or closed.  But for our purposes, it greatly simplifies
     things to treat all extents as having closed endpoints.

   First, define >, <, <=, etc. as applied to extents to mean
comparison according to the display order.  Comparison between an
extent E and an index I means comparison between E and the range [I, I].

   Also define e>, e<, e<=, etc. to mean comparison according to the
e-order.

   For any range R, define R(0) to be the starting index of the range
and R(1) to be the ending index of the range.

   For any extent E, define E(next) to be the extent directly following
E, and E(prev) to be the extent directly preceding E.  Assume E(next)
and E(prev) can be determined from E in constant time.  (This is
because we store the extent list as a doubly linked list.)

   Similarly, define E(e-next) and E(e-prev) to be the extents directly
following and preceding E in the e-order.

   Now:

   Let R be a range.  Let F be the first extent overlapping R.  Let L
be the last extent overlapping R.

   Theorem 1: R(1) lies between L and L(next), i.e. L <= R(1) < L(next).

   This follows easily from the definition of display order.  The basic
reason that this theorem applies is that the display order sorts by
increasing starting index.

   Therefore, we can determine L just by looking at where we would
insert R(1) into the list, and if we know F and are moving forward over
extents, we can easily determine when we've hit L by comparing the
extent we're at to R(1).

     Theorem 2: F(e-prev) e< [1, R(0)] e<= F.

   This is the analog of Theorem 1, and applies because the e-order
sorts by increasing ending index.

   Therefore, F can be found in the same amount of time as operation
(1), i.e. the time that it takes to locate where an extent would go if
inserted into the e-order list.

   If the lists were stored as balanced binary trees, then operation (1)
would take logarithmic time, which is usually quite fast.  However,
currently they're stored as simple doubly-linked lists, and instead we
do some caching to try to speed things up.

   Define a "stack of extents" (or "SOE") as the set of extents
(ordered in the display order) that overlap an index I, together with
the SOE's "previous" extent, which is an extent that precedes I in the
e-order. (Hopefully there will not be very many extents between I and
the previous extent.)

   Now:

   Let I be an index, let S be the stack of extents on I, let F be the
first extent in S, and let P be S's previous extent.

   Theorem 3: The first extent in S is the first extent that overlaps
any range [I, J].

   Proof: Any extent that overlaps [I, J] but does not include I must
have a start index > I, and thus be greater than any extent in S.

   Therefore, finding the first extent that overlaps a range R is the
same as finding the first extent that overlaps R(0).

   Theorem 4: Let I2 be an index such that I2 > I, and let F2 be the
first extent that overlaps I2.  Then, either F2 is in S or F2 is
greater than any extent in S.

   Proof: If F2 does not include I then its start index is greater than
I and thus it is greater than any extent in S, including F.  Otherwise,
F2 includes I and thus is in S, and thus F2 >= F.

Extent Fragments
================

   Imagine that the buffer is divided up into contiguous,
non-overlapping "runs" of text such that no extent starts or ends
within a run (extents that abut the run don't count).

   An extent fragment is a structure that holds data about the run that
contains a particular buffer position (if the buffer position is at the
junction of two runs, the run after the position is used) - the
beginning and end of the run, a list of all of the extents in that run,
the "merged face" that results from merging all of the faces
corresponding to those extents, the begin and end glyphs at the
beginning of the run, etc.  This is the information that redisplay needs
in order to display this run.

   Extent fragments have to be very quick to update to a new buffer
position when moving linearly through the buffer.  They rely on the
stack-of-extents code, which does the heavy-duty algorithmic work of
determining which extents overly a particular position.

Faces and Glyphs
****************

   Not yet documented.

Specifiers
**********

   Not yet documented.

Menus
*****

   A menu is set by setting the value of the variable `current-menubar'
(which may be buffer-local) and then calling `set-menubar-dirty-flag'
to signal a change.  This will cause the menu to be redrawn at the next
redisplay.  The format of the data in `current-menubar' is described in
`menubar.c'.

   Internally the data in current-menubar is parsed into a tree of
`widget_value's' (defined in `lwlib.h'); this is accomplished by the
recursive function `menu_item_descriptor_to_widget_value()', called by
`compute_menubar_data()'.  Such a tree is deallocated using
`free_widget_value()'.

   `update_screen_menubars()' is one of the external entry points.
This checks to see, for each screen, if that screen's menubar needs to
be updated.  This is the case if

  1. `set-menubar-dirty-flag' was called since the last redisplay.
     (This function sets the C variable menubar_has_changed.)

  2. The buffer displayed in the screen has changed.

  3. The screen has no menubar currently displayed.

   `set_screen_menubar()' is called for each such screen.  This
function calls `compute_menubar_data()' to create the tree of
widget_value's, then calls `lw_create_widget()',
`lw_modify_all_widgets()', and/or `lw_destroy_all_widgets()' to create
the X-Toolkit widget associated with the menu.

   `update_psheets()', the other external entry point, actually changes
the menus being displayed.  It uses the widgets fixed by
`update_screen_menubars()' and calls various X functions to ensure that
the menus are displayed properly.

   The menubar widget is set up so that `pre_activate_callback()' is
called when the menu is first selected (i.e. mouse button goes down),
and `menubar_selection_callback()' is called when an item is selected.
`pre_activate_callback()' calls the function in activate-menubar-hook,
which can change the menubar (this is described in `menubar.c').  If
the menubar is changed, `set_screen_menubars()' is called.
`menubar_selection_callback()' enqueues a menu event, putting in it a
function to call (either `eval' or `call-interactively') and its
argument, which is the callback function or form given in the menu's
description.

Subprocesses
************

   The fields of a process are:

`name'
     A string, the name of the process.

`command'
     A list containing the command arguments that were used to start
     this process.

`filter'
     A function used to accept output from the process instead of a
     buffer, or `nil'.

`sentinel'
     A function called whenever the process receives a signal, or `nil'.

`buffer'
     The associated buffer of the process.

`pid'
     An integer, the Unix process ID.

`childp'
     A flag, non-`nil' if this is really a child process.  It is `nil'
     for a network connection.

`mark'
     A marker indicating the position of the end of the last output
     from this process inserted into the buffer.  This is often but not
     always the end of the buffer.

`kill_without_query'
     If this is non-`nil', killing XEmacs while this process is still
     running does not ask for confirmation about killing the process.

`raw_status_low'
`raw_status_high'
     These two fields record 16 bits each of the process status
     returned by the `wait' system call.

`status'
     The process status, as `process-status' should return it.

`tick'
`update_tick'
     If these two fields are not equal, a change in the status of the
     process needs to be reported, either by running the sentinel or by
     inserting a message in the process buffer.

`pty_flag'
     Non-`nil' if communication with the subprocess uses a PTY; `nil'
     if it uses a pipe.

`infd'
     The file descriptor for input from the process.

`outfd'
     The file descriptor for output to the process.

`subtty'
     The file descriptor for the terminal that the subprocess is using.
     (On some systems, there is no need to record this, so the value is
     `-1'.)

`tty_name'
     The name of the terminal that the subprocess is using, or `nil' if
     it is using pipes.

Interface to X Windows
**********************

   Not yet documented.