+ 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.
+
+\1f
+File: internals.info, Node: Lucid Widget Library, Up: Interface to the X Window System
+
+Lucid Widget Library
+====================
+
+Lwlib is extremely poorly documented and quite hairy. The author(s)
+blame that on X, Xt, and Motif, with some justice, but also sufficient
+hypocrisy to avoid drawing the obvious conclusion about their own work.
+
+ The Lucid Widget Library is composed of two more or less independent
+pieces. The first, as the name suggests, is a set of widgets. These
+widgets are intended to resemble and improve on widgets provided in the
+Motif toolkit but not in the Athena widgets, including menubars and
+scrollbars. Recent additions by Andy Piper integrate some "modern"
+widgets by Edward Falk, including checkboxes, radio buttons, progress
+gauges, and index tab controls (aka notebooks).
+
+ The second piece of the Lucid widget library is a generic interface
+to several toolkits for X (including Xt, the Athena widget set, and
+Motif, as well as the Lucid widgets themselves) so that core XEmacs
+code need not know which widget set has been used to build the
+graphical user interface.
+
+* Menu:
+
+* Generic Widget Interface:: The lwlib generic widget interface.
+* Scrollbars::
+* Menubars::
+* Checkboxes and Radio Buttons::
+* Progress Bars::
+* Tab Controls::
+
+\1f
+File: internals.info, Node: Generic Widget Interface, Next: Scrollbars, Up: Lucid Widget Library
+
+Generic Widget Interface
+------------------------
+
+In general in any toolkit a widget may be a composite object. In Xt,
+all widgets have an X window that they manage, but typically a complex
+widget will have widget children, each of which manages a subwindow of
+the parent widget's X window. These children may themselves be
+composite widgets. Thus a widget is actually a tree or hierarchy of
+widgets.
+
+ For each toolkit widget, lwlib maintains a tree of `widget_values'
+which mirror the hierarchical state of Xt widgets (including Motif,
+Athena, 3D Athena, and Falk's widget sets). Each `widget_value' has
+`contents' member, which points to the head of a linked list of its
+children. The linked list of siblings is chained through the `next'
+member of `widget_value'.
+
+ +-----------+
+ | composite |
+ +-----------+
+ |
+ | contents
+ V
+ +-------+ next +-------+ next +-------+
+ | child |----->| child |----->| child |
+ +-------+ +-------+ +-------+
+ |
+ | contents
+ V
+ +-------------+ next +-------------+
+ | grand child |----->| grand child |
+ +-------------+ +-------------+
+
+ The `widget_value' hierarchy of a composite widget with two simple
+ children and one composite child.
+
+ The `widget_instance' structure maintains the inverse view of the
+tree. As for the `widget_value', siblings are chained through the
+`next' member. However, rather than naming children, the
+`widget_instance' tree links to parents.
+
+ +-----------+
+ | composite |
+ +-----------+
+ A
+ | parent
+ |
+ +-------+ next +-------+ next +-------+
+ | child |----->| child |----->| child |
+ +-------+ +-------+ +-------+
+ A
+ | parent
+ |
+ +-------------+ next +-------------+
+ | grand child |----->| grand child |
+ +-------------+ +-------------+
+
+ The `widget_value' hierarchy of a composite widget with two simple
+ children and one composite child.
+
+ This permits widgets derived from different toolkits to 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_value' by walking the
+`widget_value' tree. This has desirable properties. For example,
+`lw_modify_all_widgets' 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 its hairy
+properties; 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.
+
+ The `widget_instance' structure also contains a pointer to the root
+of its tree. Widget instances are further confi
+
+\1f
+File: internals.info, Node: Scrollbars, Next: Menubars, Prev: Generic Widget Interface, Up: Lucid Widget Library
+
+Scrollbars
+----------
+
+\1f
+File: internals.info, Node: Menubars, Next: Checkboxes and Radio Buttons, Prev: Scrollbars, Up: Lucid Widget Library
+
+Menubars
+--------
+
+\1f
+File: internals.info, Node: Checkboxes and Radio Buttons, Next: Progress Bars, Prev: Menubars, Up: Lucid Widget Library
+
+Checkboxes and Radio Buttons