This commit was manufactured by cvs2svn to create branch 'utf-2000'.

[chise/xemacs-chise.git-] / info / internals.info-8

This is ../info/internals.info, produced by makeinfo version 4.0 from
internals/internals.texi.

INFO-DIR-SECTION XEmacs Editor
START-INFO-DIR-ENTRY
* Internals: (internals).       XEmacs Internals Manual.
END-INFO-DIR-ENTRY

   Copyright (C) 1992 - 1996 Ben Wing.  Copyright (C) 1996, 1997 Sun
Microsystems.  Copyright (C) 1994 - 1998 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.

\1f
File: internals.info,  Node: Lstream Functions,  Next: Lstream Methods,  Prev: Lstream Types,  Up: Lstreams

Lstream Functions
=================

 - Function: Lstream * Lstream_new (Lstream_implementation *IMP, const
          char *MODE)
     Allocate and return a new Lstream.  This function is not really
     meant to be called directly; rather, each stream type should
     provide its own stream creation function, which creates the stream
     and does any other necessary creation stuff (e.g. opening a file).

 - Function: void Lstream_set_buffering (Lstream *LSTR,
          Lstream_buffering BUFFERING, int BUFFERING_SIZE)
     Change the buffering of a stream.  See `lstream.h'.  By default the
     buffering is `STREAM_BLOCK_BUFFERED'.

 - Function: int Lstream_flush (Lstream *LSTR)
     Flush out any pending unwritten data in the stream.  Clear any
     buffered input data.  Returns 0 on success, -1 on error.

 - Macro: int Lstream_putc (Lstream *STREAM, int C)
     Write out one byte to the stream.  This is a macro and so it is
     very efficient.  The C argument is only evaluated once but the
     STREAM argument is evaluated more than once.  Returns 0 on
     success, -1 on error.

 - Macro: int Lstream_getc (Lstream *STREAM)
     Read one byte from the stream.  This is a macro and so it is very
     efficient.  The STREAM argument is evaluated more than once.
     Return value is -1 for EOF or error.

 - Macro: void Lstream_ungetc (Lstream *STREAM, int C)
     Push one byte back onto the input queue.  This will be the next
     byte read from the stream.  Any number of bytes can be pushed back
     and will be read in the reverse order they were pushed back--most
     recent first. (This is necessary for consistency--if there are a
     number of bytes that have been unread and I read and unread a
     byte, it needs to be the first to be read again.) This is a macro
     and so it is very efficient.  The C argument is only evaluated
     once but the STREAM argument is evaluated more than once.

 - Function: int Lstream_fputc (Lstream *STREAM, int C)
 - Function: int Lstream_fgetc (Lstream *STREAM)
 - Function: void Lstream_fungetc (Lstream *STREAM, int C)
     Function equivalents of the above macros.

 - Function: ssize_t Lstream_read (Lstream *STREAM, void *DATA, size_t
          SIZE)
     Read SIZE bytes of DATA from the stream.  Return the number of
     bytes read.  0 means EOF. -1 means an error occurred and no bytes
     were read.

 - Function: ssize_t Lstream_write (Lstream *STREAM, void *DATA, size_t
          SIZE)
     Write SIZE bytes of DATA to the stream.  Return the number of
     bytes written.  -1 means an error occurred and no bytes were
     written.

 - Function: void Lstream_unread (Lstream *STREAM, void *DATA, size_t
          SIZE)
     Push back SIZE bytes of DATA onto the input queue.  The next call
     to `Lstream_read()' with the same size will read the same bytes
     back.  Note that this will be the case even if there is other
     pending unread data.

 - Function: int Lstream_close (Lstream *STREAM)
     Close the stream.  All data will be flushed out.

 - Function: void Lstream_reopen (Lstream *STREAM)
     Reopen a closed stream.  This enables I/O on it again.  This is not
     meant to be called except from a wrapper routine that reinitializes
     variables and such--the close routine may well have freed some
     necessary storage structures, for example.

 - Function: void Lstream_rewind (Lstream *STREAM)
     Rewind the stream to the beginning.

\1f
File: internals.info,  Node: Lstream Methods,  Prev: Lstream Functions,  Up: Lstreams

Lstream Methods
===============

 - Lstream Method: ssize_t reader (Lstream *STREAM, unsigned char
          *DATA, size_t SIZE)
     Read some data from the stream's end and store it into DATA, which
     can hold SIZE bytes.  Return the number of bytes read.  A return
     value of 0 means no bytes can be read at this time.  This may be
     because of an EOF, or because there is a granularity greater than
     one byte that the stream imposes on the returned data, and SIZE is
     less than this granularity. (This will happen frequently for
     streams that need to return whole characters, because
     `Lstream_read()' calls the reader function repeatedly until it has
     the number of bytes it wants or until 0 is returned.)  The lstream
     functions do not treat a 0 return as EOF or do anything special;
     however, the calling function will interpret any 0 it gets back as
     EOF.  This will normally not happen unless the caller calls
     `Lstream_read()' with a very small size.

     This function can be `NULL' if the stream is output-only.

 - Lstream Method: ssize_t writer (Lstream *STREAM, const unsigned char
          *DATA, size_t SIZE)
     Send some data to the stream's end.  Data to be sent is in DATA
     and is SIZE bytes.  Return the number of bytes sent.  This
     function can send and return fewer bytes than is passed in; in that
     case, the function will just be called again until there is no
     data left or 0 is returned.  A return value of 0 means that no
     more data can be currently stored, but there is no error; the data
     will be squirreled away until the writer can accept data. (This is
     useful, e.g., if you're dealing with a non-blocking file
     descriptor and are getting `EWOULDBLOCK' errors.)  This function
     can be `NULL' if the stream is input-only.

 - Lstream Method: int rewinder (Lstream *STREAM)
     Rewind the stream.  If this is `NULL', the stream is not seekable.

 - Lstream Method: int seekable_p (Lstream *STREAM)
     Indicate whether this stream is seekable--i.e. it can be rewound.
     This method is ignored if the stream does not have a rewind
     method.  If this method is not present, the result is determined
     by whether a rewind method is present.

 - Lstream Method: int flusher (Lstream *STREAM)
     Perform any additional operations necessary to flush the data in
     this stream.

 - Lstream Method: int pseudo_closer (Lstream *STREAM)

 - Lstream Method: int closer (Lstream *STREAM)
     Perform any additional operations necessary to close this stream
     down.  May be `NULL'.  This function is called when
     `Lstream_close()' is called or when the stream is
     garbage-collected.  When this function is called, all pending data
     in the stream will already have been written out.

 - Lstream Method: Lisp_Object marker (Lisp_Object LSTREAM, void
          (*MARKFUN) (Lisp_Object))
     Mark this object for garbage collection.  Same semantics as a
     standard `Lisp_Object' marker.  This function can be `NULL'.

\1f
File: internals.info,  Node: Consoles; Devices; Frames; Windows,  Next: The Redisplay Mechanism,  Prev: Lstreams,  Up: Top

Consoles; Devices; Frames; Windows
**********************************

* Menu:

* Introduction to Consoles; Devices; Frames; Windows::
* Point::
* Window Hierarchy::
* The Window Object::

\1f
File: internals.info,  Node: Introduction to Consoles; Devices; Frames; Windows,  Next: Point,  Up: Consoles; Devices; Frames; Windows

Introduction to Consoles; Devices; Frames; Windows
==================================================

   A window-system window that you see on the screen is called a
"frame" in Emacs terminology.  Each frame is subdivided into one or
more non-overlapping panes, called (confusingly) "windows".  Each
window displays the text of a buffer in it. (See above on Buffers.) Note
that buffers and windows are independent entities: Two or more windows
can be displaying the same buffer (potentially in different locations),
and a buffer can be displayed in no windows.

   A single display screen that contains one or more frames is called a
"display".  Under most circumstances, there is only one display.
However, more than one display can exist, for example if you have a
"multi-headed" console, i.e. one with a single keyboard but multiple
displays. (Typically in such a situation, the various displays act like
one large display, in that the mouse is only in one of them at a time,
and moving the mouse off of one moves it into another.) In some cases,
the different displays will have different characteristics, e.g. one
color and one mono.

   XEmacs can display frames on multiple displays.  It can even deal
simultaneously with frames on multiple keyboards (called "consoles" in
XEmacs terminology).  Here is one case where this might be useful: You
are using XEmacs on your workstation at work, and leave it running.
Then you go home and dial in on a TTY line, and you can use the
already-running XEmacs process to display another frame on your local
TTY.

   Thus, there is a hierarchy console -> display -> frame -> window.
There is a separate Lisp object type for each of these four concepts.
Furthermore, there is logically a "selected console", "selected
display", "selected frame", and "selected window".  Each of these
objects is distinguished in various ways, such as being the default
object for various functions that act on objects of that type.  Note
that every containing object remembers the "selected" object among the
objects that it contains: e.g. not only is there a selected window, but
every frame remembers the last window in it that was selected, and
changing the selected frame causes the remembered window within it to
become the selected window.  Similar relationships apply for consoles
to devices and devices to frames.

\1f
File: internals.info,  Node: Point,  Next: Window Hierarchy,  Prev: Introduction to Consoles; Devices; Frames; Windows,  Up: Consoles; Devices; Frames; Windows

Point
=====

   Recall that every buffer has a current insertion position, called
"point".  Now, two or more windows may be displaying the same buffer,
and the text cursor in the two windows (i.e. `point') can be in two
different places.  You may ask, how can that be, since each buffer has
only one value of `point'?  The answer is that each window also has a
value of `point' that is squirreled away in it.  There is only one
selected window, and the value of "point" in that buffer corresponds to
that window.  When the selected window is changed from one window to
another displaying the same buffer, the old value of `point' is stored
into the old window's "point" and the value of `point' from the new
window is retrieved and made the value of `point' in the buffer.  This
means that `window-point' for the selected window is potentially
inaccurate, and if you want to retrieve the correct value of `point'
for a window, you must special-case on the selected window and retrieve
the buffer's point instead.  This is related to why
`save-window-excursion' does not save the selected window's value of
`point'.

\1f
File: internals.info,  Node: Window Hierarchy,  Next: The Window Object,  Prev: Point,  Up: Consoles; Devices; Frames; Windows

Window Hierarchy
================

   If a frame contains multiple windows (panes), they are always created
by splitting an existing window along the horizontal or vertical axis.
Terminology is a bit confusing here: to "split a window horizontally"
means to create two side-by-side windows, i.e. to make a _vertical_ cut
in a window.  Likewise, to "split a window vertically" means to create
two windows, one above the other, by making a _horizontal_ cut.

   If you split a window and then split again along the same axis, you
will end up with a number of panes all arranged along the same axis.
The precise way in which the splits were made should not be important,
and this is reflected internally.  Internally, all windows are arranged
in a tree, consisting of two types of windows, "combination" windows
(which have children, and are covered completely by those children) and
"leaf" windows, which have no children and are visible.  Every
combination window has two or more children, all arranged along the same
axis.  There are (logically) two subtypes of windows, depending on
whether their children are horizontally or vertically arrayed.  There is
always one root window, which is either a leaf window (if the frame
contains only one window) or a combination window (if the frame contains
more than one window).  In the latter case, the root window will have
two or more children, either horizontally or vertically arrayed, and
each of those children will be either a leaf window or another
combination window.

   Here are some rules:

  1. Horizontal combination windows can never have children that are
     horizontal combination windows; same for vertical.

  2. Only leaf windows can be split (obviously) and this splitting does
     one of two things: (a) turns the leaf window into a combination
     window and creates two new leaf children, or (b) turns the leaf
     window into one of the two new leaves and creates the other leaf.
     Rule (1) dictates which of these two outcomes happens.

  3. Every combination window must have at least two children.

  4. Leaf windows can never become combination windows.  They can be
     deleted, however.  If this results in a violation of (3), the
     parent combination window also gets deleted.

  5. All functions that accept windows must be prepared to accept
     combination windows, and do something sane (e.g. signal an error
     if so).  Combination windows _do_ escape to the Lisp level.

  6. All windows have three fields governing their contents: these are
     "hchild" (a list of horizontally-arrayed children), "vchild" (a
     list of vertically-arrayed children), and "buffer" (the buffer
     contained in a leaf window).  Exactly one of these will be
     non-`nil'.  Remember that "horizontally-arrayed" means
     "side-by-side" and "vertically-arrayed" means "one above the
     other".

  7. Leaf windows also have markers in their `start' (the first buffer
     position displayed in the window) and `pointm' (the window's
     stashed value of `point'--see above) fields, while combination
     windows have `nil' in these fields.

  8. The list of children for a window is threaded through the `next'
     and `prev' fields of each child window.

  9. *Deleted windows can be undeleted*.  This happens as a result of
     restoring a window configuration, and is unlike frames, displays,
     and consoles, which, once deleted, can never be restored.
     Deleting a window does nothing except set a special `dead' bit to
     1 and clear out the `next', `prev', `hchild', and `vchild' fields,
     for GC purposes.

 10. Most frames actually have two top-level windows--one for the
     minibuffer and one (the "root") for everything else.  The modeline
     (if present) separates these two.  The `next' field of the root
     points to the minibuffer, and the `prev' field of the minibuffer
     points to the root.  The other `next' and `prev' fields are `nil',
     and the frame points to both of these windows.  Minibuffer-less
     frames have no minibuffer window, and the `next' and `prev' of the
     root window are `nil'.  Minibuffer-only frames have no root
     window, and the `next' of the minibuffer window is `nil' but the
     `prev' points to itself. (#### This is an artifact that should be
     fixed.)

\1f
File: internals.info,  Node: The Window Object,  Prev: Window Hierarchy,  Up: Consoles; Devices; Frames; Windows

The Window Object
=================

   Windows have the following accessible fields:

`frame'
     The frame that this window is on.

`mini_p'
     Non-`nil' if this window is a minibuffer window.

`buffer'
     The buffer that the window is displaying.  This may change often
     during the life of the window.

`dedicated'
     Non-`nil' if this window is dedicated to its buffer.

`pointm'
     This is the value of point in the current buffer when this window
     is selected; when it is not selected, it retains its previous
     value.

`start'
     The position in the buffer that is the first character to be
     displayed in the window.

`force_start'
     If this flag is non-`nil', it says that the window has been
     scrolled explicitly by the Lisp program.  This affects what the
     next redisplay does if point is off the screen: instead of
     scrolling the window to show the text around point, it moves point
     to a location that is on the screen.

`last_modified'
     The `modified' field of the window's buffer, as of the last time a
     redisplay completed in this window.

`last_point'
     The buffer's value of point, as of the last time a redisplay
     completed in this window.

`left'
     This is the left-hand edge of the window, measured in columns.
     (The leftmost column on the screen is column 0.)

`top'
     This is the top edge of the window, measured in lines.  (The top
     line on the screen is line 0.)

`height'
     The height of the window, measured in lines.

`width'
     The width of the window, measured in columns.

`next'
     This is the window that is the next in the chain of siblings.  It
     is `nil' in a window that is the rightmost or bottommost of a
     group of siblings.

`prev'
     This is the window that is the previous in the chain of siblings.
     It is `nil' in a window that is the leftmost or topmost of a group
     of siblings.

`parent'
     Internally, XEmacs arranges windows in a tree; each group of
     siblings has a parent window whose area includes all the siblings.
     This field points to a window's parent.

     Parent windows do not display buffers, and play little role in
     display except to shape their child windows.  Emacs Lisp programs
     usually have no access to the parent windows; they operate on the
     windows at the leaves of the tree, which actually display buffers.

`hscroll'
     This is the number of columns that the display in the window is
     scrolled horizontally to the left.  Normally, this is 0.

`use_time'
     This is the last time that the window was selected.  The function
     `get-lru-window' uses this field.

`display_table'
     The window's display table, or `nil' if none is specified for it.

`update_mode_line'
     Non-`nil' means this window's mode line needs to be updated.

`base_line_number'
     The line number of a certain position in the buffer, or `nil'.
     This is used for displaying the line number of point in the mode
     line.

`base_line_pos'
     The position in the buffer for which the line number is known, or
     `nil' meaning none is known.

`region_showing'
     If the region (or part of it) is highlighted in this window, this
     field holds the mark position that made one end of that region.
     Otherwise, this field is `nil'.

\1f
File: internals.info,  Node: The Redisplay Mechanism,  Next: Extents,  Prev: Consoles; Devices; Frames; Windows,  Up: Top

The Redisplay Mechanism
***********************

   The redisplay mechanism is one of the most complicated sections of
XEmacs, especially from a conceptual standpoint.  This is doubly so
because, unlike for the basic aspects of the Lisp interpreter, the
computer science theories of how to efficiently handle redisplay are not
well-developed.

   When working with the redisplay mechanism, remember the Golden Rules
of Redisplay:

  1. It Is Better To Be Correct Than Fast.

  2. Thou Shalt Not Run Elisp From Within Redisplay.

  3. It Is Better To Be Fast Than Not To Be.

* Menu:

* Critical Redisplay Sections::
* Line Start Cache::
* Redisplay Piece by Piece::

\1f
File: internals.info,  Node: Critical Redisplay Sections,  Next: Line Start Cache,  Up: The Redisplay Mechanism

Critical Redisplay Sections
===========================

   Within this section, we are defenseless and assume that the
following cannot happen:

  1. garbage collection

  2. Lisp code evaluation

  3. frame size changes

   We ensure (3) by calling `hold_frame_size_changes()', which will
cause any pending frame size changes to get put on hold till after the
end of the critical section.  (1) follows automatically if (2) is met.
#### Unfortunately, there are some places where Lisp code can be called
within this section.  We need to remove them.

   If `Fsignal()' is called during this critical section, we will
`abort()'.

   If garbage collection is called during this critical section, we
simply return. #### We should abort instead.

   #### If a frame-size change does occur we should probably actually
be preempting redisplay.

\1f
File: internals.info,  Node: Line Start Cache,  Next: Redisplay Piece by Piece,  Prev: Critical Redisplay Sections,  Up: The Redisplay Mechanism

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.

\1f
File: internals.info,  Node: Redisplay Piece by Piece,  Prev: Line Start Cache,  Up: The Redisplay Mechanism

Redisplay Piece by Piece
========================

   As you can begin to see redisplay is complex and also not well
documented. Chuck no longer works on XEmacs so this section is my take
on the workings of redisplay.

   Redisplay happens in three phases:

  1. Determine desired display in area that needs redisplay.
     Implemented by `redisplay.c'

  2. Compare desired display with current display Implemented by
     `redisplay-output.c'

  3. Output changes Implemented by `redisplay-output.c',
     `redisplay-x.c', `redisplay-msw.c' and `redisplay-tty.c'

   Steps 1 and 2 are device-independent and relatively complex.  Step 3
is mostly device-dependent.

   Determining the desired display

   Display attributes are stored in `display_line' structures. Each
`display_line' consists of a set of `display_block''s and each
`display_block' contains a number of `rune''s. Generally dynarr's of
`display_line''s are held by each window representing the current
display and the desired display.

   The `display_line' structures are tightly tied to buffers which
presents a problem for redisplay as this connection is bogus for the
modeline. Hence the `display_line' generation routines are duplicated
for generating the modeline. This means that the modeline display code
has many bugs that the standard redisplay code does not.

   The guts of `display_line' generation are in `create_text_block',
which creates a single display line for the desired locale. This
incrementally parses the characters on the current line and generates
redisplay structures for each.

   Gutter redisplay is different. Because the data to display is stored
in a string we cannot use `create_text_block'. Instead we use
`create_text_string_block' which performs the same function as
`create_text_block' but for strings. Many of the complexities of
`create_text_block' to do with cursor handling and selective display
have been removed.

\1f
File: internals.info,  Node: Extents,  Next: Faces,  Prev: The Redisplay Mechanism,  Up: Top

Extents
*******

* Menu:

* Introduction to Extents::     Extents are ranges over text, with properties.
* Extent Ordering::             How extents are ordered internally.
* Format of the Extent Info::   The extent information in a buffer or string.
* Zero-Length Extents::         A weird special case.
* Mathematics of Extent Ordering::  A rigorous foundation.
* Extent Fragments::            Cached information useful for redisplay.

\1f
File: internals.info,  Node: Introduction to Extents,  Next: Extent Ordering,  Up: 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.)

\1f
File: internals.info,  Node: Extent Ordering,  Next: Format of the Extent Info,  Prev: Introduction to Extents,  Up: Extents

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".

\1f
File: internals.info,  Node: Format of the Extent Info,  Next: Zero-Length Extents,  Prev: Extent Ordering,  Up: Extents

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).

\1f
File: internals.info,  Node: Zero-Length Extents,  Next: Mathematics of Extent Ordering,  Prev: Format of the Extent Info,  Up: Extents

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.

\1f
File: internals.info,  Node: Mathematics of Extent Ordering,  Next: Extent Fragments,  Prev: Zero-Length Extents,  Up: Extents

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.

\1f
File: internals.info,  Node: Extent Fragments,  Prev: Mathematics of Extent Ordering,  Up: Extents

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.

\1f
File: internals.info,  Node: Faces,  Next: Glyphs,  Prev: Extents,  Up: Top

Faces
*****

   Not yet documented.

\1f
File: internals.info,  Node: Glyphs,  Next: Specifiers,  Prev: Faces,  Up: Top

Glyphs
******

   Glyphs are graphical elements that can be displayed in XEmacs
buffers or gutters. We use the term graphical element here in the
broadest possible sense since glyphs can be as mundane as text or as
arcane as a native tab widget.

   In XEmacs, glyphs represent the uninstantiated state of graphical
elements, i.e. they hold all the information necessary to produce an
image on-screen but the image need not exist at this stage, and multiple
screen images can be instantiated from a single glyph.

   Glyphs are lazily instantiated by calling one of the glyph
functions. This usually occurs within redisplay when `Fglyph_height' is
called. Instantiation causes an image-instance to be created and
cached. This cache is on a per-device basis for all glyphs except
widget-glyphs, and on a per-window basis for widgets-glyphs.  The
caching is done by `image_instantiate' and is necessary because it is
generally possible to display an image-instance in multiple domains.
For instance if we create a Pixmap, we can actually display this on
multiple windows - even though we only need a single Pixmap instance to
do this. If caching wasn't done then it would be necessary to create
image-instances for every displayable occurrence of a glyph - and every
usage - and this would be extremely memory and cpu intensive.

   Widget-glyphs (a.k.a native widgets) are not cached in this way.
This is because widget-glyph image-instances on screen are toolkit
windows, and thus cannot be reused in multiple XEmacs domains. Thus
widget-glyphs are cached on an XEmacs window basis.

   Any action on a glyph first consults the cache before actually
instantiating a widget.

Glyph Instantiation
===================

   Glyph instantiation is a hairy topic and requires some explanation.
The guts of glyph instantiation is contained within
`image_instantiate'. A glyph contains an image which is a specifier.
When a glyph function - for instance `Fglyph_height' - asks for a
property of the glyph that can only be determined from its instantiated
state, then the glyph image is instantiated and an image instance
created. The instantiation process is governed by the specifier code
and goes through a series of steps:

   * Validation. Instantiation of image instances happens dynamically -
     often within the guts of redisplay. Thus it is often not feasible
     to catch instantiator errors at instantiation time. Instead the
     instantiator is validated at the time it is added to the image
     specifier. This function is defined by `image_validate' and at a
     simple level validates keyword value pairs.

   * Duplication. The specifier code by default takes a copy of the
     instantiator. This is reasonable for most specifiers but in the
     case of widget-glyphs can be problematic, since some of the
     properties in the instantiator - for instance callbacks - could
     cause infinite recursion in the copying process. Thus the image
     code defines a function - `image_copy_instantiator' - which will
     selectively copy values.  This is controlled by the way that a
     keyword is defined either using `IIFORMAT_VALID_KEYWORD' or
     `IIFORMAT_VALID_NONCOPY_KEYWORD'. Note that the image caching and
     redisplay code relies on instantiator copying to ensure that
     current and new instantiators are actually different rather than
     referring to the same thing.

   * Normalization. Once the instantiator has been copied it must be
     converted into a form that is viable at instantiation time. This
     can involve no changes at all, but typically involves things like
     converting file names to the actual data. This function is defined
     by `image_going_to_add' and `normalize_image_instantiator'.

   * Instantiation. When an image instance is actually required for
     display it is instantiated using `image_instantiate'. This
     involves calling instantiate methods that are specific to the type
     of image being instantiated.

   The final instantiation phase also involves a number of steps. In
order to understand these we need to describe a number of concepts.

   An image is instantiated in a "domain", where a domain can be any
one of a device, frame, window or image-instance. The domain gives the
image-instance context and identity and properties that affect the
appearance of the image-instance may be different for the same glyph
instantiated in different domains. An example is the face used to
display the image-instance.

   Although an image is instantiated in a particular domain the
instantiation domain is not necessarily the domain in which the
image-instance is cached. For example a pixmap can be instantiated in a
window be actually be cached on a per-device basis. The domain in which
the image-instance is actually cached is called the "governing-domain".
A governing-domain is currently either a device or a window.
Widget-glyphs and text-glyphs have a window as a governing-domain, all
other image-instances have a device as the governing-domain. The
governing domain for an image-instance is determined using the
governing_domain image-instance method.

Widget-Glyphs
=============

Widget-Glyphs in the MS-Windows Environment
===========================================

   To Do

Widget-Glyphs in the X Environment
==================================

   Widget-glyphs under X make heavy use of lwlib (*note Lucid Widget
Library::) for manipulating the native toolkit objects. This is
primarily so that different toolkits can be supported for
widget-glyphs, just as they are supported for features such as menubars
etc.

   Lwlib is extremely poorly documented and quite hairy so here is my
understanding of what goes on.

   Lwlib maintains a set of widget_instances which mirror the
hierarchical state of Xt widgets. I think this is so that widgets can
be updated and manipulated generically by the lwlib library. For
instance update_one_widget_instance can cope with multiple types of
widget and multiple types of toolkit. Each element in the widget
hierarchy is updated from its corresponding widget_instance by walking
the widget_instance tree recursively.

   This has desirable properties such as lw_modify_all_widgets which is
called from `glyphs-x.c' and updates all the properties of a widget
without having to know what the widget is or what toolkit it is from.
Unfortunately this also has hairy properties such as making the lwlib
code quite complex. And of course lwlib has to know at some level what
the widget is and how to set its properties.

\1f
File: internals.info,  Node: Specifiers,  Next: Menus,  Prev: Glyphs,  Up: Top

Specifiers
**********

   Not yet documented.

\1f
File: internals.info,  Node: Menus,  Next: Subprocesses,  Prev: Specifiers,  Up: Top

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.

\1f
File: internals.info,  Node: Subprocesses,  Next: Interface to the X Window System,  Prev: Menus,  Up: Top

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.

\1f
File: internals.info,  Node: Interface to the X Window System,  Next: Index,  Prev: Subprocesses,  Up: Top

Interface to the X Window System
********************************

   Mostly undocumented.

* Menu:

* Lucid Widget Library::        An interface to various widget sets.