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

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

   Edition History:

   Created November 1995 (?) by Ben Wing.  XEmacs Internals Manual
Version 1.0, March, 1996.  XEmacs Internals Manual Version 1.1, March,
1997.  XEmacs Internals Manual Version 1.4, March, 2001.  XEmacs
Internals Manual Version 21.5, October, 2004.

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


File: internals.info,  Node: Garbage Collection - Step by Step,  Next: Integers and Characters,  Prev: GCPROing,  Up: Allocation of Objects in XEmacs Lisp

19.4 Garbage Collection - Step by Step
======================================

* Menu:

* Invocation::
* garbage_collect_1::
* mark_object::
* gc_sweep::
* sweep_lcrecords_1::
* compact_string_chars::
* sweep_strings::
* sweep_bit_vectors_1::


File: internals.info,  Node: Invocation,  Next: garbage_collect_1,  Prev: Garbage Collection - Step by Step,  Up: Garbage Collection - Step by Step

19.4.1 Invocation
-----------------

The first thing that anyone should know about garbage collection is:
when and how the garbage collector is invoked. One might think that this
could happen every time new memory is allocated, e.g. new objects are
created, but this is _not_ the case. Instead, we have the following
situation:

   The entry point of any process of garbage collection is an invocation
of the function `garbage_collect_1' in file `alloc.c'. The invocation
can occur _explicitly_ by calling the function `Fgarbage_collect' (in
addition this function provides information about the freed memory), or
can occur _implicitly_ in four different situations:
  1. In function `main_1' in file `emacs.c'. This function is called at
     each startup of xemacs. The garbage collection is invoked after all
     initial creations are completed, but only if a special internal
     error checking-constant `ERROR_CHECK_GC' is defined.

  2. In function `disksave_object_finalization' in file `alloc.c'. The
     only purpose of this function is to clear the objects from memory
     which need not be stored with xemacs when we dump out an
     executable. This is only done by `Fdump_emacs' or by
     `Fdump_emacs_data' respectively (both in `emacs.c'). The actual
     clearing is accomplished by making these objects unreachable and
     starting a garbage collection. The function is only used while
     building xemacs.

  3. In function `Feval / eval' in file `eval.c'. Each time the well
     known and often used function eval is called to evaluate a form,
     one of the first things that could happen, is a potential call of
     `garbage_collect_1'. There exist three global variables,
     `consing_since_gc' (counts the created cons-cells since the last
     garbage collection), `gc_cons_threshold' (a specified threshold
     after which a garbage collection occurs) and `always_gc'. If
     `always_gc' is set or if the threshold is exceeded, the garbage
     collection will start.

  4. In function `Ffuncall / funcall' in file `eval.c'. This function
     evaluates calls of elisp functions and works according to `Feval'.

   The upshot is that garbage collection can basically occur everywhere
`Feval', respectively `Ffuncall', is used - either directly or through
another function. Since calls to these two functions are hidden in
various other functions, many calls to `garbage_collect_1' are not
obviously foreseeable, and therefore unexpected. Instances where they
are used that are worth remembering are various elisp commands, as for
example `or', `and', `if', `cond', `while', `setq', etc., miscellaneous
`gui_item_...' functions, everything related to `eval' (`Feval_buffer',
`call0', ...) and inside `Fsignal'. The latter is used to handle
signals, as for example the ones raised by every `QUIT'-macro triggered
after pressing Ctrl-g.


File: internals.info,  Node: garbage_collect_1,  Next: mark_object,  Prev: Invocation,  Up: Garbage Collection - Step by Step

19.4.2 `garbage_collect_1'
--------------------------

We can now describe exactly what happens after the invocation takes
place.
  1. There are several cases in which the garbage collector is left
     immediately: when we are already garbage collecting
     (`gc_in_progress'), when the garbage collection is somehow
     forbidden (`gc_currently_forbidden'), when we are currently
     displaying something (`in_display') or when we are preparing for
     the armageddon of the whole system (`preparing_for_armageddon').

  2. Next the correct frame in which to put all the output occurring
     during garbage collecting is determined. In order to be able to
     restore the old display's state after displaying the message, some
     data about the current cursor position has to be saved. The
     variables `pre_gc_cursor' and `cursor_changed' take care of that.

  3. The state of `gc_currently_forbidden' must be restored after the
     garbage collection, no matter what happens during the process. We
     accomplish this by `record_unwind_protect'ing the suitable function
     `restore_gc_inhibit' together with the current value of
     `gc_currently_forbidden'.

  4. If we are concurrently running an interactive xemacs session, the
     next step is simply to show the garbage collector's cursor/message.

  5. The following steps are the intrinsic steps of the garbage
     collector, therefore `gc_in_progress' is set.

  6. For debugging purposes, it is possible to copy the current C stack
     frame. However, this seems to be a currently unused feature.

  7. Before actually starting to go over all live objects, references to
     objects that are no longer used are pruned. We only have to do
     this for events (`clear_event_resource') and for specifiers
     (`cleanup_specifiers').

  8. Now the mark phase begins and marks all accessible elements. In
     order to start from all slots that serve as roots of
     accessibility, the function `mark_object' is called for each root
     individually to go out from there to mark all reachable objects.
     All roots that are traversed are shown in their processed order:
        * all constant symbols and static variables that are registered
          via `staticpro' in the dynarr `staticpros'.  *Note Adding
          Global Lisp Variables::.

        * all Lisp objects that are created in C functions and that
          must be protected from freeing them. They are registered in
          the global list `gcprolist'.  *Note GCPROing::.

        * all local variables (i.e. their name fields `symbol' and old
          values `old_values') that are bound during the evaluation by
          the Lisp engine. They are stored in `specbinding' structs
          pushed on a stack called `specpdl'.  *Note Dynamic Binding;
          The specbinding Stack; Unwind-Protects::.

        * all catch blocks that the Lisp engine encounters during the
          evaluation cause the creation of structs `catchtag' inserted
          in the list `catchlist'. Their tag (`tag') and value (`val'
          fields are freshly created objects and therefore have to be
          marked.  *Note Catch and Throw::.

        * every function application pushes new structs `backtrace' on
          the call stack of the Lisp engine (`backtrace_list'). The
          unique parts that have to be marked are the fields for each
          function (`function') and all their arguments (`args').
          *Note Evaluation::.

        * all objects that are used by the redisplay engine that must
          not be freed are marked by a special function called
          `mark_redisplay' (in `redisplay.c').

        * all objects created for profiling purposes are allocated by C
          functions instead of using the lisp allocation mechanisms. In
          order to receive the right ones during the sweep phase, they
          also have to be marked manually. That is done by the function
          `mark_profiling_info'

  9. Hash tables in XEmacs belong to a kind of special objects that
     make use of a concept often called 'weak pointers'.  To make a
     long story short, these kind of pointers are not followed during
     the estimation of the live objects during garbage collection.  Any
     object referenced only by weak pointers is collected anyway, and
     the reference to it is cleared. In hash tables there are different
     usage patterns of them, manifesting in different types of hash
     tables, namely 'non-weak', 'weak', 'key-weak' and 'value-weak'
     (internally also 'key-car-weak' and 'value-car-weak') hash tables,
     each clearing entries depending on different conditions. More
     information can be found in the documentation to the function
     `make-hash-table'.

     Because there are complicated dependency rules about when and what
     to mark while processing weak hash tables, the standard `marker'
     method is only active if it is marking non-weak hash tables. As
     soon as a weak component is in the table, the hash table entries
     are ignored while marking. Instead their marking is done each
     separately by the function `finish_marking_weak_hash_tables'. This
     function iterates over each hash table entry `hentries' for each
     weak hash table in `Vall_weak_hash_tables'. Depending on the type
     of a table, the appropriate action is performed.  If a table is
     acting as `HASH_TABLE_KEY_WEAK', and a key already marked,
     everything reachable from the `value' component is marked. If it is
     acting as a `HASH_TABLE_VALUE_WEAK' and the value component is
     already marked, the marking starts beginning only from the `key'
     component.  If it is a `HASH_TABLE_KEY_CAR_WEAK' and the car of
     the key entry is already marked, we mark both the `key' and
     `value' components.  Finally, if the table is of the type
     `HASH_TABLE_VALUE_CAR_WEAK' and the car of the value components is
     already marked, again both the `key' and the `value' components
     get marked.

     Again, there are lists with comparable properties called weak
     lists. There exist different peculiarities of their types called
     `simple', `assoc', `key-assoc' and `value-assoc'. You can find
     further details about them in the description to the function
     `make-weak-list'. The scheme of their marking is similar: all weak
     lists are listed in `Qall_weak_lists', therefore we iterate over
     them. The marking is advanced until we hit an already marked pair.
     Then we know that during a former run all the rest has been marked
     completely. Again, depending on the special type of the weak list,
     our jobs differ. If it is a `WEAK_LIST_SIMPLE' and the elem is
     marked, we mark the `cons' part. If it is a `WEAK_LIST_ASSOC' and
     not a pair or a pair with both marked car and cdr, we mark the
     `cons' and the `elem'. If it is a `WEAK_LIST_KEY_ASSOC' and not a
     pair or a pair with a marked car of the elem, we mark the `cons'
     and the `elem'. Finally, if it is a `WEAK_LIST_VALUE_ASSOC' and
     not a pair or a pair with a marked cdr of the elem, we mark both
     the `cons' and the `elem'.

     Since, by marking objects in reach from weak hash tables and weak
     lists, other objects could get marked, this perhaps implies
     further marking of other weak objects, both finishing functions
     are redone as long as yet unmarked objects get freshly marked.

 10. After completing the special marking for the weak hash tables and
     for the weak lists, all entries that point to objects that are
     going to be swept in the further process are useless, and
     therefore have to be removed from the table or the list.

     The function `prune_weak_hash_tables' does the job for weak hash
     tables. Totally unmarked hash tables are removed from the list
     `Vall_weak_hash_tables'. The other ones are treated more carefully
     by scanning over all entries and removing one as soon as one of
     the components `key' and `value' is unmarked.

     The same idea applies to the weak lists. It is accomplished by
     `prune_weak_lists': An unmarked list is pruned from
     `Vall_weak_lists' immediately. A marked list is treated more
     carefully by going over it and removing just the unmarked pairs.

 11. The function `prune_specifiers' checks all listed specifiers held
     in `Vall_specifiers' and removes the ones from the lists that are
     unmarked.

 12. All syntax tables are stored in a list called
     `Vall_syntax_tables'. The function `prune_syntax_tables' walks
     through it and unlinks the tables that are unmarked.

 13. Next, we will attack the complete sweeping - the function
     `gc_sweep' which holds the predominance.

 14. First, all the variables with respect to garbage collection are
     reset. `consing_since_gc' - the counter of the created cells since
     the last garbage collection - is set back to 0, and
     `gc_in_progress' is not `true' anymore.

 15. In case the session is interactive, the displayed cursor and
     message are removed again.

 16. The state of `gc_inhibit' is restored to the former value by
     unwinding the stack.

 17. A small memory reserve is always held back that can be reached by
     `breathing_space'. If nothing more is left, we create a new reserve
     and exit.


File: internals.info,  Node: mark_object,  Next: gc_sweep,  Prev: garbage_collect_1,  Up: Garbage Collection - Step by Step

19.4.3 `mark_object'
--------------------

The first thing that is checked while marking an object is whether the
object is a real Lisp object `Lisp_Type_Record' or just an integer or a
character. Integers and characters are the only two types that are
stored directly - without another level of indirection, and therefore
they don't have to be marked and collected.  *Note How Lisp Objects Are
Represented in C::.

   The second case is the one we have to handle. It is the one when we
are dealing with a pointer to a Lisp object. But, there exist also three
possibilities, that prevent us from doing anything while marking: The
object is read only which prevents it from being garbage collected,
i.e. marked (`C_READONLY_RECORD_HEADER'). The object in question is
already marked, and need not be marked for the second time (checked by
`MARKED_RECORD_HEADER_P'). If it is a special, unmarkable object
(`UNMARKABLE_RECORD_HEADER_P', apparently, these are objects that sit
in some const space, and can therefore not be marked, see
`this_one_is_unmarkable' in `alloc.c').

   Now, the actual marking is feasible. We do so by once using the macro
`MARK_RECORD_HEADER' to mark the object itself (actually the special
flag in the lrecord header), and calling its special marker "method"
`marker' if available. The marker method marks every other object that
is in reach from our current object. Note, that these marker methods
should not call `mark_object' recursively, but instead should return
the next object from where further marking has to be performed.

   In case another object was returned, as mentioned before, we
reiterate the whole `mark_object' process beginning with this next
object.


File: internals.info,  Node: gc_sweep,  Next: sweep_lcrecords_1,  Prev: mark_object,  Up: Garbage Collection - Step by Step

19.4.4 `gc_sweep'
-----------------

The job of this function is to free all unmarked records from memory. As
we know, there are different types of objects implemented and managed,
and consequently different ways to free them from memory.  *Note
Introduction to Allocation::.

   We start with all objects stored through `lcrecords'. All bulkier
objects are allocated and handled using that scheme of `lcrecords'.
Each object is `malloc'ed separately instead of placing it in one of
the contiguous frob blocks. All types that are currently stored using
`lcrecords''s  `alloc_lcrecord' and `make_lcrecord_list' are the types:
vectors, buffers, char-table, char-table-entry, console, weak-list,
database, device, ldap, hash-table, command-builder, extent-auxiliary,
extent-info, face, coding-system, frame, image-instance, glyph,
popup-data, gui-item, keymap, charset, color_instance, font_instance,
opaque, opaque-list, process, range-table, specifier,
symbol-value-buffer-local, symbol-value-lisp-magic,
symbol-value-varalias, toolbar-button, tooltalk-message,
tooltalk-pattern, window, and window-configuration. We take care of
them in the fist place in order to be able to handle and to finalize
items stored in them more easily. The function `sweep_lcrecords_1' as
described below is doing the whole job for us.  For a description about
the internals: *Note lrecords::.

   Our next candidates are the other objects that behave quite
differently than everything else: the strings. They consists of two
parts, a fixed-size portion (`struct Lisp_String') holding the string's
length, its property list and a pointer to the second part, and the
actual string data, which is stored in string-chars blocks comparable to
frob blocks. In this block, the data is not only freed, but also a
compression of holes is made, i.e. all strings are relocated together.
*Note String::. This compacting phase is performed by the function
`compact_string_chars', the actual sweeping by the function
`sweep_strings' is described below.

   After that, the other types are swept step by step using functions
`sweep_conses', `sweep_bit_vectors_1', `sweep_compiled_functions',
`sweep_floats', `sweep_symbols', `sweep_extents', `sweep_markers' and
`sweep_extents'.  They are the fixed-size types cons, floats,
compiled-functions, symbol, marker, extent, and event stored in
so-called "frob blocks", and therefore we can basically do the same on
every type objects, using the same macros, especially defined only to
handle everything with respect to fixed-size blocks. The only fixed-size
type that is not handled here are the fixed-size portion of strings,
because we took special care of them earlier.

   The only big exceptions are bit vectors stored differently and
therefore treated differently by the function `sweep_bit_vectors_1'
described later.

   At first, we need some brief information about how these fixed-size
types are managed in general, in order to understand how the sweeping
is done. They have all a fixed size, and are therefore stored in big
blocks of memory - allocated at once - that can hold a certain amount
of objects of one type. The macro `DECLARE_FIXED_TYPE_ALLOC' creates
the suitable structures for every type. More precisely, we have the
block struct (holding a pointer to the previous block `prev' and the
objects in `block[]'), a pointer to current block
(`current_..._block)') and its last index (`current_..._block_index'),
and a pointer to the free list that will be created. Also a macro
`FIXED_TYPE_FROM_BLOCK' plus some related macros exists that are used
to obtain a new object, either from the free list
`ALLOCATE_FIXED_TYPE_1' if there is an unused object of that type
stored or by allocating a completely new block using
`ALLOCATE_FIXED_TYPE_FROM_BLOCK'.

   The rest works as follows: all of them define a macro `UNMARK_...'
that is used to unmark the object. They define a macro
`ADDITIONAL_FREE_...' that defines additional work that has to be done
when converting an object from in use to not in use (so far, only
markers use it in order to unchain them). Then, they all call the macro
`SWEEP_FIXED_TYPE_BLOCK' instantiated with their type name and their
struct name.

   This call in particular does the following: we go over all blocks
starting with the current moving towards the oldest.  For each block,
we look at every object in it. If the object already freed (checked
with `FREE_STRUCT_P' using the first pointer of the object), or if it is
set to read only (`C_READONLY_RECORD_HEADER_P', nothing must be done.
If it is unmarked (checked with `MARKED_RECORD_HEADER_P'), it is put in
the free list and set free (using the macro `FREE_FIXED_TYPE',
otherwise it stays in the block, but is unmarked (by `UNMARK_...').
While going through one block, we note if the whole block is empty. If
so, the whole block is freed (using `xfree') and the free list state is
set to the state it had before handling this block.


File: internals.info,  Node: sweep_lcrecords_1,  Next: compact_string_chars,  Prev: gc_sweep,  Up: Garbage Collection - Step by Step

19.4.5 `sweep_lcrecords_1'
--------------------------

After nullifying the complete lcrecord statistics, we go over all
lcrecords two separate times. They are all chained together in a list
with a head called `all_lcrecords'.

   The first loop calls for each object its `finalizer' method, but only
in the case that it is not read only (`C_READONLY_RECORD_HEADER_P)', it
is not already marked (`MARKED_RECORD_HEADER_P'), it is not already in
a free list (list of freed objects, field `free') and finally it owns a
finalizer method.

   The second loop actually frees the appropriate objects again by
iterating through the whole list. In case an object is read only or
marked, it has to persist, otherwise it is manually freed by calling
`xfree'. During this loop, the lcrecord statistics are kept up to date
by calling `tick_lcrecord_stats' with the right arguments,


File: internals.info,  Node: compact_string_chars,  Next: sweep_strings,  Prev: sweep_lcrecords_1,  Up: Garbage Collection - Step by Step

19.4.6 `compact_string_chars'
-----------------------------

The purpose of this function is to compact all the data parts of the
strings that are held in so-called `string_chars_block', i.e. the
strings that do not exceed a certain maximal length.

   The procedure with which this is done is as follows. We are keeping
two positions in the `string_chars_block's using two pointer/integer
pairs, namely `from_sb'/`from_pos' and `to_sb'/`to_pos'. They stand for
the actual positions, from where to where, to copy the actually handled
string.

   While going over all chained `string_char_block's and their held
strings, staring at `first_string_chars_block', both pointers are
advanced and eventually a string is copied from `from_sb' to `to_sb',
depending on the status of the pointed at strings.

   More precisely, we can distinguish between the following actions.
   * The string at `from_sb''s position could be marked as free, which
     is indicated by an invalid pointer to the pointer that should
     point back to the fixed size string object, and which is checked by
     `FREE_STRUCT_P'. In this case, the `from_sb'/`from_pos' is
     advanced to the next string, and nothing has to be copied.

   * Also, if a string object itself is unmarked, nothing has to be
     copied. We likewise advance the `from_sb'/`from_pos' pair as
     described above.

   * In all other cases, we have a marked string at hand. The string
     data must be moved from the from-position to the to-position. In
     case there is not enough space in the actual `to_sb'-block, we
     advance this pointer to the beginning of the next block before
     copying. In case the from and to positions are different, we
     perform the actual copying using the library function `memmove'.

   After compacting, the pointer to the current `string_chars_block',
sitting in `current_string_chars_block', is reset on the last block to
which we moved a string, i.e. `to_block', and all remaining blocks (we
know that they just carry garbage) are explicitly `xfree'd.


File: internals.info,  Node: sweep_strings,  Next: sweep_bit_vectors_1,  Prev: compact_string_chars,  Up: Garbage Collection - Step by Step

19.4.7 `sweep_strings'
----------------------

The sweeping for the fixed sized string objects is essentially exactly
the same as it is for all other fixed size types. As before, the freeing
into the suitable free list is done by using the macro
`SWEEP_FIXED_SIZE_BLOCK' after defining the right macros
`UNMARK_string' and `ADDITIONAL_FREE_string'. These two definitions are
a little bit special compared to the ones used for the other fixed size
types.

   `UNMARK_string' is defined the same way except some additional code
used for updating the bookkeeping information.

   For strings, `ADDITIONAL_FREE_string' has to do something in
addition: in case, the string was not allocated in a
`string_chars_block' because it exceeded the maximal length, and
therefore it was `malloc'ed separately, we know also `xfree' it
explicitly.


File: internals.info,  Node: sweep_bit_vectors_1,  Prev: sweep_strings,  Up: Garbage Collection - Step by Step

19.4.8 `sweep_bit_vectors_1'
----------------------------

Bit vectors are also one of the rare types that are `malloc'ed
individually. Consequently, while sweeping, all further needless bit
vectors must be freed by hand. This is done, as one might imagine, the
expected way: since they are all registered in a list called
`all_bit_vectors', all elements of that list are traversed, all
unmarked bit vectors are unlinked by calling `xfree' and all of them
become unmarked.  In addition, the bookkeeping information used for
garbage collector's output purposes is updated.


File: internals.info,  Node: Integers and Characters,  Next: Allocation from Frob Blocks,  Prev: Garbage Collection - Step by Step,  Up: Allocation of Objects in XEmacs Lisp

19.5 Integers and Characters
============================

Integer and character Lisp objects are created from integers using the
macros `XSETINT()' and `XSETCHAR()' or the equivalent functions
`make_int()' and `make_char()'. (These are actually macros on most
systems.)  These functions basically just do some moving of bits
around, since the integral value of the object is stored directly in
the `Lisp_Object'.

   `XSETINT()' and the like will truncate values given to them that are
too big; i.e. you won't get the value you expected but the tag bits
will at least be correct.


File: internals.info,  Node: Allocation from Frob Blocks,  Next: lrecords,  Prev: Integers and Characters,  Up: Allocation of Objects in XEmacs Lisp

19.6 Allocation from Frob Blocks
================================

The uninitialized memory required by a `Lisp_Object' of a particular
type is allocated using `ALLOCATE_FIXED_TYPE()'.  This only occurs
inside of the lowest-level object-creating functions in `alloc.c':
`Fcons()', `make_float()', `Fmake_byte_code()', `Fmake_symbol()',
`allocate_extent()', `allocate_event()', `Fmake_marker()', and
`make_uninit_string()'.  The idea is that, for each type, there are a
number of frob blocks (each 2K in size); each frob block is divided up
into object-sized chunks.  Each frob block will have some of these
chunks that are currently assigned to objects, and perhaps some that are
free. (If a frob block has nothing but free chunks, it is freed at the
end of the garbage collection cycle.)  The free chunks are stored in a
free list, which is chained by storing a pointer in the first four bytes
of the chunk. (Except for the free chunks at the end of the last frob
block, which are handled using an index which points past the end of the
last-allocated chunk in the last frob block.)  `ALLOCATE_FIXED_TYPE()'
first tries to retrieve a chunk from the free list; if that fails, it
calls `ALLOCATE_FIXED_TYPE_FROM_BLOCK()', which looks at the end of the
last frob block for space, and creates a new frob block if there is
none. (There are actually two versions of these macros, one of which is
more defensive but less efficient and is used for error-checking.)


File: internals.info,  Node: lrecords,  Next: Low-level allocation,  Prev: Allocation from Frob Blocks,  Up: Allocation of Objects in XEmacs Lisp

19.7 lrecords
=============

[see `lrecord.h']

   All lrecords have at the beginning of their structure a `struct
lrecord_header'.  This just contains a type number and some flags,
including the mark bit.  All builtin type numbers are defined as
constants in `enum lrecord_type', to allow the compiler to generate
more efficient code for `TYPEP'.  The type number, thru the
`lrecord_implementation_table', gives access to a `struct
lrecord_implementation', which is a structure containing method pointers
and such.  There is one of these for each type, and it is a global,
constant, statically-declared structure that is declared in the
`DEFINE_LRECORD_IMPLEMENTATION()' macro.

   Simple lrecords (of type (b) above) just have a `struct
lrecord_header' at their beginning.  lcrecords, however, actually have a
`struct lcrecord_header'.  This, in turn, has a `struct lrecord_header'
at its beginning, so sanity is preserved; but it also has a pointer
used to chain all lcrecords together, and a special ID field used to
distinguish one lcrecord from another. (This field is used only for
debugging and could be removed, but the space gain is not significant.)

   Simple lrecords are created using `ALLOCATE_FIXED_TYPE()', just like
for other frob blocks.  The only change is that the implementation
pointer must be initialized correctly. (The implementation structure for
an lrecord, or rather the pointer to it, is named `lrecord_float',
`lrecord_extent', `lrecord_buffer', etc.)

   lcrecords are created using `alloc_lcrecord()'.  This takes a size
to allocate and an implementation pointer. (The size needs to be passed
because some lcrecords, such as window configurations, are of variable
size.) This basically just `malloc()'s the storage, initializes the
`struct lcrecord_header', and chains the lcrecord onto the head of the
list of all lcrecords, which is stored in the variable `all_lcrecords'.
The calls to `alloc_lcrecord()' generally occur in the lowest-level
allocation function for each lrecord type.

   Whenever you create an lrecord, you need to call either
`DEFINE_LRECORD_IMPLEMENTATION()' or
`DEFINE_LRECORD_SEQUENCE_IMPLEMENTATION()'.  This needs to be specified
in a `.c' file, at the top level.  What this actually does is define
and initialize the implementation structure for the lrecord. (And
possibly declares a function `error_check_foo()' that implements the
`XFOO()' macro when error-checking is enabled.)  The arguments to the
macros are the actual type name (this is used to construct the C
variable name of the lrecord implementation structure and related
structures using the `##' macro concatenation operator), a string that
names the type on the Lisp level (this may not be the same as the C
type name; typically, the C type name has underscores, while the Lisp
string has dashes), various method pointers, and the name of the C
structure that contains the object.  The methods are used to
encapsulate type-specific information about the object, such as how to
print it or mark it for garbage collection, so that it's easy to add
new object types without having to add a specific case for each new
type in a bunch of different places.

   The difference between `DEFINE_LRECORD_IMPLEMENTATION()' and
`DEFINE_LRECORD_SEQUENCE_IMPLEMENTATION()' is that the former is used
for fixed-size object types and the latter is for variable-size object
types.  Most object types are fixed-size; some complex types, however
(e.g. window configurations), are variable-size.  Variable-size object
types have an extra method, which is called to determine the actual
size of a particular object of that type.  (Currently this is only used
for keeping allocation statistics.)

   For the purpose of keeping allocation statistics, the allocation
engine keeps a list of all the different types that exist.  Note that,
since `DEFINE_LRECORD_IMPLEMENTATION()' is a macro that is specified at
top-level, there is no way for it to initialize the global data
structures containing type information, like
`lrecord_implementations_table'.  For this reason a call to
`INIT_LRECORD_IMPLEMENTATION' must be added to the same source file
containing `DEFINE_LRECORD_IMPLEMENTATION', but instead of to the top
level, to one of the init functions, typically `syms_of_FOO.c'.
`INIT_LRECORD_IMPLEMENTATION' must be called before an object of this
type is used.

   The type number is also used to index into an array holding the
number of objects of each type and the total memory allocated for
objects of that type.  The statistics in this array are computed during
the sweep stage.  These statistics are returned by the call to
`garbage-collect'.

   Note that for every type defined with a `DEFINE_LRECORD_*()' macro,
there needs to be a `DECLARE_LRECORD_IMPLEMENTATION()' somewhere in a
`.h' file, and this `.h' file needs to be included by `inline.c'.

   Furthermore, there should generally be a set of `XFOOBAR()',
`FOOBARP()', etc. macros in a `.h' (or occasionally `.c') file.  To
create one of these, copy an existing model and modify as necessary.

   *Please note:* If you define an lrecord in an external
dynamically-loaded module, you must use `DECLARE_EXTERNAL_LRECORD',
`DEFINE_EXTERNAL_LRECORD_IMPLEMENTATION', and
`DEFINE_EXTERNAL_LRECORD_SEQUENCE_IMPLEMENTATION' instead of the
non-EXTERNAL forms. These macros will dynamically add new type numbers
to the global enum that records them, whereas the non-EXTERNAL forms
assume that the programmer has already inserted the correct type numbers
into the enum's code at compile-time.

   The various methods in the lrecord implementation structure are:

  1. A "mark" method.  This is called during the marking stage and
     passed a function pointer (usually the `mark_object()' function),
     which is used to mark an object.  All Lisp objects that are
     contained within the object need to be marked by applying this
     function to them.  The mark method should also return a Lisp
     object, which should be either `nil' or an object to mark. (This
     can be used in lieu of calling `mark_object()' on the object, to
     reduce the recursion depth, and consequently should be the most
     heavily nested sub-object, such as a long list.)

     *Please note:* When the mark method is called, garbage collection
     is in progress, and special precautions need to be taken when
     accessing objects; see section (B) above.

     If your mark method does not need to do anything, it can be `NULL'.

  2. A "print" method.  This is called to create a printed
     representation of the object, whenever `princ', `prin1', or the
     like is called.  It is passed the object, a stream to which the
     output is to be directed, and an `escapeflag' which indicates
     whether the object's printed representation should be "escaped" so
     that it is readable. (This corresponds to the difference between
     `princ' and `prin1'.) Basically, "escaped" means that strings will
     have quotes around them and confusing characters in the strings
     such as quotes, backslashes, and newlines will be backslashed; and
     that special care will be taken to make symbols print in a
     readable fashion (e.g. symbols that look like numbers will be
     backslashed).  Other readable objects should perhaps pass
     `escapeflag' on when sub-objects are printed, so that readability
     is preserved when necessary (or if not, always pass in a 1 for
     `escapeflag').  Non-readable objects should in general ignore
     `escapeflag', except that some use it as an indication that more
     verbose output should be given.

     Sub-objects are printed using `print_internal()', which takes
     exactly the same arguments as are passed to the print method.

     Literal C strings should be printed using `write_c_string()', or
     `write_string_1()' for non-null-terminated strings.

     Functions that do not have a readable representation should check
     the `print_readably' flag and signal an error if it is set.

     If you specify NULL for the print method, the
     `default_object_printer()' will be used.

  3. A "finalize" method.  This is called at the beginning of the sweep
     stage on lcrecords that are about to be freed, and should be used
     to perform any extra object cleanup.  This typically involves
     freeing any extra `malloc()'ed memory associated with the object,
     releasing any operating-system and window-system resources
     associated with the object (e.g. pixmaps, fonts), etc.

     The finalize method can be NULL if nothing needs to be done.

     WARNING #1: The finalize method is also called at the end of the
     dump phase; this time with the for_disksave parameter set to
     non-zero.  The object is _not_ about to disappear, so you have to
     make sure to _not_ free any extra `malloc()'ed memory if you're
     going to need it later.  (Also, signal an error if there are any
     operating-system and window-system resources here, because they
     can't be dumped.)

     Finalize methods should, as a rule, set to zero any pointers after
     they've been freed, and check to make sure pointers are not zero
     before freeing.  Although I'm pretty sure that finalize methods
     are not called twice on the same object (except for the
     `for_disksave' proviso), we've gotten nastily burned in some cases
     by not doing this.

     WARNING #2: The finalize method is _only_ called for lcrecords,
     _not_ for simply lrecords.  If you need a finalize method for
     simple lrecords, you have to stick it in the
     `ADDITIONAL_FREE_foo()' macro in `alloc.c'.

     WARNING #3: Things are in an _extremely_ bizarre state when
     `ADDITIONAL_FREE_foo()' is called, so you have to be incredibly
     careful when writing one of these functions.  See the comment in
     `gc_sweep()'.  If you ever have to add one of these, consider
     using an lcrecord or dealing with the problem in a different
     fashion.

  4. An "equal" method.  This compares the two objects for similarity,
     when `equal' is called.  It should compare the contents of the
     objects in some reasonable fashion.  It is passed the two objects
     and a "depth" value, which is used to catch circular objects.  To
     compare sub-Lisp-objects, call `internal_equal()' and bump the
     depth value by one.  If this value gets too high, a
     `circular-object' error will be signaled.

     If this is NULL, objects are `equal' only when they are `eq', i.e.
     identical.

  5. A "hash" method.  This is used to hash objects when they are to be
     compared with `equal'.  The rule here is that if two objects are
     `equal', they _must_ hash to the same value; i.e. your hash
     function should use some subset of the sub-fields of the object
     that are compared in the "equal" method.  If you specify this
     method as `NULL', the object's pointer will be used as the hash,
     which will _fail_ if the object has an `equal' method, so don't do
     this.

     To hash a sub-Lisp-object, call `internal_hash()'.  Bump the depth
     by one, just like in the "equal" method.

     To convert a Lisp object directly into a hash value (using its
     pointer), use `LISP_HASH()'.  This is what happens when the hash
     method is NULL.

     To hash two or more values together into a single value, use
     `HASH2()', `HASH3()', `HASH4()', etc.

  6. "getprop", "putprop", "remprop", and "plist" methods.  These are
     used for object types that have properties.  I don't feel like
     documenting them here.  If you create one of these objects, you
     have to use different macros to define them, i.e.
     `DEFINE_LRECORD_IMPLEMENTATION_WITH_PROPS()' or
     `DEFINE_LRECORD_SEQUENCE_IMPLEMENTATION_WITH_PROPS()'.

  7. A "size_in_bytes" method, when the object is of variable-size.
     (i.e. declared with a `_SEQUENCE_IMPLEMENTATION' macro.)  This
     should simply return the object's size in bytes, exactly as you
     might expect.  For an example, see the methods for window
     configurations and opaques.


File: internals.info,  Node: Low-level allocation,  Next: Cons,  Prev: lrecords,  Up: Allocation of Objects in XEmacs Lisp

19.8 Low-level allocation
=========================

Memory that you want to allocate directly should be allocated using
`xmalloc()' rather than `malloc()'.  This implements error-checking on
the return value, and once upon a time did some more vital stuff (i.e.
`BLOCK_INPUT', which is no longer necessary).  Free using `xfree()',
and realloc using `xrealloc()'.  Note that `xmalloc()' will do a
non-local exit if the memory can't be allocated. (Many functions,
however, do not expect this, and thus XEmacs will likely crash if this
happens.  *This is a bug.*  If you can, you should strive to make your
function handle this OK.  However, it's difficult in the general
circumstance, perhaps requiring extra unwind-protects and such.)

   Note that XEmacs provides two separate replacements for the standard
`malloc()' library function.  These are called "old GNU malloc"
(`malloc.c') and "new GNU malloc" (`gmalloc.c'), respectively.  New GNU
malloc is better in pretty much every way than old GNU malloc, and
should be used if possible.  (It used to be that on some systems, the
old one worked but the new one didn't.  I think this was due
specifically to a bug in SunOS, which the new one now works around; so
I don't think the old one ever has to be used any more.) The primary
difference between both of these mallocs and the standard system malloc
is that they are much faster, at the expense of increased space.  The
basic idea is that memory is allocated in fixed chunks of powers of
two.  This allows for basically constant malloc time, since the various
chunks can just be kept on a number of free lists. (The standard system
malloc typically allocates arbitrary-sized chunks and has to spend some
time, sometimes a significant amount of time, walking the heap looking
for a free block to use and cleaning things up.)  The new GNU malloc
improves on things by allocating large objects in chunks of 4096 bytes
rather than in ever larger powers of two, which results in ever larger
wastage.  There is a slight speed loss here, but it's of doubtful
significance.

   NOTE: Apparently there is a third-generation GNU malloc that is
significantly better than the new GNU malloc, and should probably be
included in XEmacs.

   There is also the relocating allocator, `ralloc.c'.  This actually
moves blocks of memory around so that the `sbrk()' pointer shrunk and
virtual memory released back to the system.  On some systems, this is a
big win.  On all systems, it causes a noticeable (and sometimes huge)
speed penalty, so I turn it off by default.  `ralloc.c' only works with
the new GNU malloc in `gmalloc.c'.  There are also two versions of
`ralloc.c', one that uses `mmap()' rather than block copies to move
data around.  This purports to be faster, although that depends on the
amount of data that would have had to be block copied and the
system-call overhead for `mmap()'.  I don't know exactly how this
works, except that the relocating-allocation routines are pretty much
used only for the memory allocated for a buffer, which is the biggest
consumer of space, esp. of space that may get freed later.

   Note that the GNU mallocs have some "memory warning" facilities.
XEmacs taps into them and issues a warning through the standard warning
system, when memory gets to 75%, 85%, and 95% full.  (On some systems,
the memory warnings are not functional.)

   Allocated memory that is going to be used to make a Lisp object is
created using `allocate_lisp_storage()'.  This just calls `xmalloc()'.
It used to verify that the pointer to the memory can fit into a Lisp
word, before the current Lisp object representation was introduced.
`allocate_lisp_storage()' is called by `alloc_lcrecord()',
`ALLOCATE_FIXED_TYPE()', and the vector and bit-vector creation
routines.  These routines also call `INCREMENT_CONS_COUNTER()' at the
appropriate times; this keeps statistics on how much memory is
allocated, so that garbage-collection can be invoked when the threshold
is reached.


File: internals.info,  Node: Cons,  Next: Vector,  Prev: Low-level allocation,  Up: Allocation of Objects in XEmacs Lisp

19.9 Cons
=========

Conses are allocated in standard frob blocks.  The only thing to note
is that conses can be explicitly freed using `free_cons()' and
associated functions `free_list()' and `free_alist()'.  This
immediately puts the conses onto the cons free list, and decrements the
statistics on memory allocation appropriately.  This is used to good
effect by some extremely commonly-used code, to avoid generating extra
objects and thereby triggering GC sooner.  However, you have to be
_extremely_ careful when doing this.  If you mess this up, you will get
BADLY BURNED, and it has happened before.


File: internals.info,  Node: Vector,  Next: Bit Vector,  Prev: Cons,  Up: Allocation of Objects in XEmacs Lisp

19.10 Vector
============

As mentioned above, each vector is `malloc()'ed individually, and all
are threaded through the variable `all_vectors'.  Vectors are marked
strangely during garbage collection, by kludging the size field.  Note
that the `struct Lisp_Vector' is declared with its `contents' field
being a _stretchy_ array of one element.  It is actually `malloc()'ed
with the right size, however, and access to any element through the
`contents' array works fine.


File: internals.info,  Node: Bit Vector,  Next: Symbol,  Prev: Vector,  Up: Allocation of Objects in XEmacs Lisp

19.11 Bit Vector
================

Bit vectors work exactly like vectors, except for more complicated code
to access an individual bit, and except for the fact that bit vectors
are lrecords while vectors are not. (The only difference here is that
there's an lrecord implementation pointer at the beginning and the tag
field in bit vector Lisp words is "lrecord" rather than "vector".)


File: internals.info,  Node: Symbol,  Next: Marker,  Prev: Bit Vector,  Up: Allocation of Objects in XEmacs Lisp

19.12 Symbol
============

Symbols are also allocated in frob blocks.  Symbols in the awful
horrible obarray structure are chained through their `next' field.

   Remember that `intern' looks up a symbol in an obarray, creating one
if necessary.


File: internals.info,  Node: Marker,  Next: String,  Prev: Symbol,  Up: Allocation of Objects in XEmacs Lisp

19.13 Marker
============

Markers are allocated in frob blocks, as usual.  They are kept in a
buffer unordered, but in a doubly-linked list so that they can easily
be removed. (Formerly this was a singly-linked list, but in some cases
garbage collection took an extraordinarily long time due to the O(N^2)
time required to remove lots of markers from a buffer.) Markers are
removed from a buffer in the finalize stage, in
`ADDITIONAL_FREE_marker()'.


File: internals.info,  Node: String,  Next: Compiled Function,  Prev: Marker,  Up: Allocation of Objects in XEmacs Lisp

19.14 String
============

As mentioned above, strings are a special case.  A string is logically
two parts, a fixed-size object (containing the length, property list,
and a pointer to the actual data), and the actual data in the string.
The fixed-size object is a `struct Lisp_String' and is allocated in
frob blocks, as usual.  The actual data is stored in special
"string-chars blocks", which are 8K blocks of memory.
Currently-allocated strings are simply laid end to end in these
string-chars blocks, with a pointer back to the `struct Lisp_String'
stored before each string in the string-chars block.  When a new string
needs to be allocated, the remaining space at the end of the last
string-chars block is used if there's enough, and a new string-chars
block is created otherwise.

   There are never any holes in the string-chars blocks due to the
string compaction and relocation that happens at the end of garbage
collection.  During the sweep stage of garbage collection, when objects
are reclaimed, the garbage collector goes through all string-chars
blocks, looking for unused strings.  Each chunk of string data is
preceded by a pointer to the corresponding `struct Lisp_String', which
indicates both whether the string is used and how big the string is,
i.e. how to get to the next chunk of string data.  Holes are compressed
by block-copying the next string into the empty space and relocating the
pointer stored in the corresponding `struct Lisp_String'.  *This means
you have to be careful with strings in your code.* See the section
above on `GCPRO'ing.

   Note that there is one situation not handled: a string that is too
big to fit into a string-chars block.  Such strings, called "big
strings", are all `malloc()'ed as their own block. (#### Although it
would make more sense for the threshold for big strings to be somewhat
lower, e.g. 1/2 or 1/4 the size of a string-chars block.  It seems that
this was indeed the case formerly--indeed, the threshold was set at
1/8--but Mly forgot about this when rewriting things for 19.8.)

   Note also that the string data in string-chars blocks is padded as
necessary so that proper alignment constraints on the `struct
Lisp_String' back pointers are maintained.

   Finally, strings can be resized.  This happens in Mule when a
character is substituted with a different-length character, or during
modeline frobbing. (You could also export this to Lisp, but it's not
done so currently.) Resizing a string is a potentially tricky process.
If the change is small enough that the padding can absorb it, nothing
other than a simple memory move needs to be done.  Keep in mind,
however, that the string can't shrink too much because the offset to the
next string in the string-chars block is computed by looking at the
length and rounding to the nearest multiple of four or eight.  If the
string would shrink or expand beyond the correct padding, new string
data needs to be allocated at the end of the last string-chars block and
the data moved appropriately.  This leaves some dead string data, which
is marked by putting a special marker of 0xFFFFFFFF in the `struct
Lisp_String' pointer before the data (there's no real `struct
Lisp_String' to point to and relocate), and storing the size of the dead
string data (which would normally be obtained from the now-non-existent
`struct Lisp_String') at the beginning of the dead string data gap.
The string compactor recognizes this special 0xFFFFFFFF marker and
handles it correctly.


File: internals.info,  Node: Compiled Function,  Prev: String,  Up: Allocation of Objects in XEmacs Lisp

19.15 Compiled Function
=======================

Not yet documented.


File: internals.info,  Node: The Lisp Reader and Compiler,  Next: Evaluation; Stack Frames; Bindings,  Prev: Allocation of Objects in XEmacs Lisp,  Up: Top

20 The Lisp Reader and Compiler
*******************************

Not yet documented.


File: internals.info,  Node: Evaluation; Stack Frames; Bindings,  Next: Symbols and Variables,  Prev: The Lisp Reader and Compiler,  Up: Top

21 Evaluation; Stack Frames; Bindings
*************************************

* Menu:

* Evaluation::
* Dynamic Binding; The specbinding Stack; Unwind-Protects::
* Simple Special Forms::
* Catch and Throw::
* Error Trapping::


File: internals.info,  Node: Evaluation,  Next: Dynamic Binding; The specbinding Stack; Unwind-Protects,  Prev: Evaluation; Stack Frames; Bindings,  Up: Evaluation; Stack Frames; Bindings

21.1 Evaluation
===============

`Feval()' evaluates the form (a Lisp object) that is passed to it.
Note that evaluation is only non-trivial for two types of objects:
symbols and conses.  A symbol is evaluated simply by calling
`symbol-value' on it and returning the value.

   Evaluating a cons means calling a function.  First, `eval' checks to
see if garbage-collection is necessary, and calls `garbage_collect_1()'
if so.  It then increases the evaluation depth by 1 (`lisp_eval_depth',
which is always less than `max_lisp_eval_depth') and adds an element to
the linked list of `struct backtrace''s (`backtrace_list').  Each such
structure contains a pointer to the function being called plus a list
of the function's arguments.  Originally these values are stored
unevalled, and as they are evaluated, the backtrace structure is
updated.  Garbage collection pays attention to the objects pointed to
in the backtrace structures (garbage collection might happen while a
function is being called or while an argument is being evaluated, and
there could easily be no other references to the arguments in the
argument list; once an argument is evaluated, however, the unevalled
version is not needed by eval, and so the backtrace structure is
changed).

   At this point, the function to be called is determined by looking at
the car of the cons (if this is a symbol, its function definition is
retrieved and the process repeated).  The function should then consist
of either a `Lisp_Subr' (built-in function written in C), a
`Lisp_Compiled_Function' object, or a cons whose car is one of the
symbols `autoload', `macro' or `lambda'.

   If the function is a `Lisp_Subr', the lisp object points to a
`struct Lisp_Subr' (created by `DEFUN()'), which contains a pointer to
the C function, a minimum and maximum number of arguments (or possibly
the special constants `MANY' or `UNEVALLED'), a pointer to the symbol
referring to that subr, and a couple of other things.  If the subr
wants its arguments `UNEVALLED', they are passed raw as a list.
Otherwise, an array of evaluated arguments is created and put into the
backtrace structure, and either passed whole (`MANY') or each argument
is passed as a C argument.

   If the function is a `Lisp_Compiled_Function',
`funcall_compiled_function()' is called.  If the function is a lambda
list, `funcall_lambda()' is called.  If the function is a macro, [.....
fill in] is done.  If the function is an autoload, `do_autoload()' is
called to load the definition and then eval starts over [explain this
more].

   When `Feval()' exits, the evaluation depth is reduced by one, the
debugger is called if appropriate, and the current backtrace structure
is removed from the list.

   Both `funcall_compiled_function()' and `funcall_lambda()' need to go
through the list of formal parameters to the function and bind them to
the actual arguments, checking for `&rest' and `&optional' symbols in
the formal parameters and making sure the number of actual arguments is
correct.  `funcall_compiled_function()' can do this a little more
efficiently, since the formal parameter list can be checked for sanity
when the compiled function object is created.

   `funcall_lambda()' simply calls `Fprogn' to execute the code in the
lambda list.

   `funcall_compiled_function()' calls the real byte-code interpreter
`execute_optimized_program()' on the byte-code instructions, which are
converted into an internal form for faster execution.

   When a compiled function is executed for the first time by
`funcall_compiled_function()', or during the dump phase of building
XEmacs, the byte-code instructions are converted from a `Lisp_String'
(which is inefficient to access, especially in the presence of MULE)
into a `Lisp_Opaque' object containing an array of unsigned char, which
can be directly executed by the byte-code interpreter.  At this time
the byte code is also analyzed for validity and transformed into a more
optimized form, so that `execute_optimized_program()' can really fly.

   Here are some of the optimizations performed by the internal
byte-code transformer:
  1. References to the `constants' array are checked for out-of-range
     indices, so that the byte interpreter doesn't have to.

  2. References to the `constants' array that will be used as a Lisp
     variable are checked for being correct non-constant (i.e. not `t',
     `nil', or `keywordp') symbols, so that the byte interpreter
     doesn't have to.

  3. The maximum number of variable bindings in the byte-code is
     pre-computed, so that space on the `specpdl' stack can be
     pre-reserved once for the whole function execution.

  4. All byte-code jumps are relative to the current program counter
     instead of the start of the program, thereby saving a register.

  5. One-byte relative jumps are converted from the byte-code form of
     unsigned chars offset by 127 to machine-friendly signed chars.

   Of course, this transformation of the `instructions' should not be
visible to the user, so `Fcompiled_function_instructions()' needs to
know how to convert the optimized opaque object back into a Lisp string
that is identical to the original string from the `.elc' file.
(Actually, the resulting string may (rarely) contain slightly
different, yet equivalent, byte code.)

   `Ffuncall()' implements Lisp `funcall'.  `(funcall fun x1 x2 x3
...)' is equivalent to `(eval (list fun (quote x1) (quote x2) (quote
x3) ...))'.  `Ffuncall()' contains its own code to do the evaluation,
however, and is very similar to `Feval()'.

   From the performance point of view, it is worth knowing that most of
the time in Lisp evaluation is spent executing `Lisp_Subr' and
`Lisp_Compiled_Function' objects via `Ffuncall()' (not `Feval()').

   `Fapply()' implements Lisp `apply', which is very similar to
`funcall' except that if the last argument is a list, the result is the
same as if each of the arguments in the list had been passed separately.
`Fapply()' does some business to expand the last argument if it's a
list, then calls `Ffuncall()' to do the work.

   `apply1()', `call0()', `call1()', `call2()', and `call3()' call a
function, passing it the argument(s) given (the arguments are given as
separate C arguments rather than being passed as an array).  `apply1()'
uses `Fapply()' while the others use `Ffuncall()' to do the real work.


File: internals.info,  Node: Dynamic Binding; The specbinding Stack; Unwind-Protects,  Next: Simple Special Forms,  Prev: Evaluation,  Up: Evaluation; Stack Frames; Bindings

21.2 Dynamic Binding; The specbinding Stack; Unwind-Protects
============================================================

     struct specbinding
     {
       Lisp_Object symbol;
       Lisp_Object old_value;
       Lisp_Object (*func) (Lisp_Object); /* for unwind-protect */
     };

   `struct specbinding' is used for local-variable bindings and
unwind-protects.  `specpdl' holds an array of `struct specbinding''s,
`specpdl_ptr' points to the beginning of the free bindings in the
array, `specpdl_size' specifies the total number of binding slots in
the array, and `max_specpdl_size' specifies the maximum number of
bindings the array can be expanded to hold.  `grow_specpdl()' increases
the size of the `specpdl' array, multiplying its size by 2 but never
exceeding `max_specpdl_size' (except that if this number is less than
400, it is first set to 400).

   `specbind()' binds a symbol to a value and is used for local
variables and `let' forms.  The symbol and its old value (which might
be `Qunbound', indicating no prior value) are recorded in the specpdl
array, and `specpdl_size' is increased by 1.

   `record_unwind_protect()' implements an "unwind-protect", which,
when placed around a section of code, ensures that some specified
cleanup routine will be executed even if the code exits abnormally
(e.g. through a `throw' or quit).  `record_unwind_protect()' simply
adds a new specbinding to the `specpdl' array and stores the
appropriate information in it.  The cleanup routine can either be a C
function, which is stored in the `func' field, or a `progn' form, which
is stored in the `old_value' field.

   `unbind_to()' removes specbindings from the `specpdl' array until
the specified position is reached.  Each specbinding can be one of
three types:

  1. an unwind-protect with a C cleanup function (`func' is not 0, and
     `old_value' holds an argument to be passed to the function);

  2. an unwind-protect with a Lisp form (`func' is 0, `symbol' is
     `nil', and `old_value' holds the form to be executed with
     `Fprogn()'); or

  3. a local-variable binding (`func' is 0, `symbol' is not `nil', and
     `old_value' holds the old value, which is stored as the symbol's
     value).


File: internals.info,  Node: Simple Special Forms,  Next: Catch and Throw,  Prev: Dynamic Binding; The specbinding Stack; Unwind-Protects,  Up: Evaluation; Stack Frames; Bindings

21.3 Simple Special Forms
=========================

`or', `and', `if', `cond', `progn', `prog1', `prog2', `setq', `quote',
`function', `let*', `let', `while'

   All of these are very simple and work as expected, calling `Feval()'
or `Fprogn()' as necessary and (in the case of `let' and `let*') using
`specbind()' to create bindings and `unbind_to()' to undo the bindings
when finished.

   Note that, with the exception of `Fprogn', these functions are
typically called in real life only in interpreted code, since the byte
compiler knows how to convert calls to these functions directly into
byte code.


File: internals.info,  Node: Catch and Throw,  Next: Error Trapping,  Prev: Simple Special Forms,  Up: Evaluation; Stack Frames; Bindings

21.4 Catch and Throw
====================

     struct catchtag
     {
       Lisp_Object tag;
       Lisp_Object val;
       struct catchtag *next;
       struct gcpro *gcpro;
       jmp_buf jmp;
       struct backtrace *backlist;
       int lisp_eval_depth;
       int pdlcount;
     };

   `catch' is a Lisp function that places a catch around a body of
code.  A catch is a means of non-local exit from the code.  When a catch
is created, a tag is specified, and executing a `throw' to this tag
will exit from the body of code caught with this tag, and its value will
be the value given in the call to `throw'.  If there is no such call,
the code will be executed normally.

   Information pertaining to a catch is held in a `struct catchtag',
which is placed at the head of a linked list pointed to by `catchlist'.
`internal_catch()' is passed a C function to call (`Fprogn()' when
Lisp `catch' is called) and arguments to give it, and places a catch
around the function.  Each `struct catchtag' is held in the stack frame
of the `internal_catch()' instance that created the catch.

   `internal_catch()' is fairly straightforward.  It stores into the
`struct catchtag' the tag name and the current values of
`backtrace_list', `lisp_eval_depth', `gcprolist', and the offset into
the `specpdl' array, sets a jump point with `_setjmp()' (storing the
jump point into the `struct catchtag'), and calls the function.
Control will return to `internal_catch()' either when the function
exits normally or through a `_longjmp()' to this jump point.  In the
latter case, `throw' will store the value to be returned into the
`struct catchtag' before jumping.  When it's done, `internal_catch()'
removes the `struct catchtag' from the catchlist and returns the proper
value.

   `Fthrow()' goes up through the catchlist until it finds one with a
matching tag.  It then calls `unbind_catch()' to restore everything to
what it was when the appropriate catch was set, stores the return value
in the `struct catchtag', and jumps (with `_longjmp()') to its jump
point.

   `unbind_catch()' removes all catches from the catchlist until it
finds the correct one.  Some of the catches might have been placed for
error-trapping, and if so, the appropriate entries on the handlerlist
must be removed (see "errors").  `unbind_catch()' also restores the
values of `gcprolist', `backtrace_list', and `lisp_eval', and calls
`unbind_to()' to undo any specbindings created since the catch.


File: internals.info,  Node: Error Trapping,  Prev: Catch and Throw,  Up: Evaluation; Stack Frames; Bindings

21.5 Error Trapping
===================

call_trapping_problems():
-------------------------

This is equivalent to (*fun) (arg), except that various conditions can
be trapped or inhibited, according to FLAGS.

   * If FLAGS does not contain NO_INHIBIT_ERRORS, when an error occurs,
     the error is caught and a warning is issued, specifying the
     specific error that occurred and a backtrace.  In that case,
     WARNING_STRING should be given, and will be printed at the
     beginning of the error to indicate where the error occurred.

   * If FLAGS does not contain NO_INHIBIT_THROWS, all attempts to
     `throw' out of the function being called are trapped, and a warning
     issued. (Again, WARNING_STRING should be given.)

   * If FLAGS contains INHIBIT_WARNING_ISSUE, no warnings are issued;
     this applies to recursive invocations of call_trapping_problems,
     too.

   * If FLAGS contains POSTPONE_WARNING_ISSUE, no warnings are issued;
     but values useful for generating a warning are still computed (in
     particular, the backtrace), so that the calling function can issue
     a warning.

   * If FLAGS contains ISSUE_WARNINGS_AT_DEBUG_LEVEL, warnings will be
     issued, but at level `debug', which normally is below the minimum
     specified by `log-warning-minimum-level', meaning such warnings
     will be ignored entirely.  The user can change this variable,
     however, to see the warnings.)

     Note: If neither of NO_INHIBIT_THROWS or NO_INHIBIT_ERRORS is
     given, you are *guaranteed* that there will be no non-local exits
     out of this function.

   * If FLAGS contains INHIBIT_QUIT, QUIT using C-g is inhibited.  (This
     is *rarely* a good idea.  Unless you use NO_INHIBIT_ERRORS, QUIT is
     automatically caught as well, and treated as an error; you can
     check for this using EQ (problems->error_conditions, Qquit).

   * If FLAGS contains UNINHIBIT_QUIT, QUIT checking will be explicitly
     turned on. (It will abort the code being called, but will still be
     trapped and reported as an error, unless NO_INHIBIT_ERRORS is
     given.) This is useful when QUIT checking has been turned off by a
     higher-level caller.

   * If FLAGS contains INHIBIT_GC, garbage collection is inhibited.
     This is useful for Lisp called within redisplay, for example.

   * If FLAGS contains
     INHIBIT_EXISTING_PERMANENT_DISPLAY_OBJECT_DELETION, Lisp code is
     not allowed to delete any window, buffers, frames, devices, or
     consoles that were already in existence at the time this function
     was called. (However, it's perfectly legal for code to create a new
     buffer and then delete it.)

     #### It might be useful to have a flag that inhibits deletion of a
     specific permanent display object and everything it's attached to
     (e.g. a window, and the buffer, frame, device, and console it's
     attached to.

   * If FLAGS contains INHIBIT_EXISTING_BUFFER_TEXT_MODIFICATION, Lisp
     code is not allowed to modify the text of any buffers that were
     already in existence at the time this function was called.
     (However, it's perfectly legal for code to create a new buffer and
     then modify its text.)

          [These last two flags are implemented using global variables
          Vdeletable_permanent_display_objects and Vmodifiable_buffers,
          which keep track of a list of all buffers or permanent display
          objects created since the last time one of these flags was
          set.  The code that deletes buffers, etc. and modifies
          buffers checks

            1. if the corresponding flag is set (through the global
               variable inhibit_flags or its accessor function
               get_inhibit_flags()), and

            2. if the object to be modified or deleted is not in the
               appropriate list.

          If so, it signals an error.

          Recursive calls to call_trapping_problems() are allowed.  In
          the case of the two flags mentioned above, the current values
          of the global variables are stored in an unwind-protect, and
          they're reset to nil.]

   * If FLAGS contains INHIBIT_ENTERING_DEBUGGER, the debugger will not
     be entered if an error occurs inside the Lisp code being called,
     even when the user has requested an error.  In such case, a warning
     is issued stating that access to the debugger is denied, unless
     INHIBIT_WARNING_ISSUE has also been supplied.  This is useful when
     calling Lisp code inside redisplay, in menu callbacks, etc. because
     in such cases either the display is in an inconsistent state or
     doing window operations is explicitly forbidden by the OS, and the
     debugger would causes visual changes on the screen and might create
     another frame.

   * If FLAGS contains INHIBIT_ANY_CHANGE_AFFECTING_REDISPLAY, no
     changes of any sort to extents, faces, glyphs, buffer text,
     specifiers relating to display, other variables relating to
     display, splitting, deleting, or resizing windows or frames,
     deleting buffers, windows, frames, devices, or consoles, etc. is
     allowed.  This is for things called absolutely in the middle of
     redisplay, which expects things to be *exactly* the same after the
     call as before.  This isn't completely implemented and needs to be
     thought out some more to determine exactly what its semantics are.
     For the moment, turning on this flag also turns on

        - INHIBIT_EXISTING_PERMANENT_DISPLAY_OBJECT_DELETION

        - INHIBIT_EXISTING_BUFFER_TEXT_MODIFICATION

        - INHIBIT_ENTERING_DEBUGGER

        - INHIBIT_WARNING_ISSUE

        - INHIBIT_GC

   * #### The following five flags are defined, but unimplemented:

     #define INHIBIT_EXISTING_CODING_SYSTEM_DELETION (1<<6) #define
     INHIBIT_EXISTING_CHARSET_DELETION (1<<7) #define
     INHIBIT_PERMANENT_DISPLAY_OBJECT_CREATION (1<<8) #define
     INHIBIT_CODING_SYSTEM_CREATION (1<<9) #define
     INHIBIT_CHARSET_CREATION (1<<10)

   * FLAGS containing CALL_WITH_SUSPENDED_ERRORS is a sign that
     call_with_suspended_errors() was invoked.  This exists only for
     debugging purposes - often we want to break when a signal happens,
     but ignore signals from call_with_suspended_errors(), because they
     occur often and for legitimate reasons.

   If PROBLEM is non-zero, it should be a pointer to a structure into
which exact information about any occurring problems (either an error
or an attempted throw past this boundary).

   If a problem occurred and aborted operation (error, quit, or invalid
throw), Qunbound is returned.  Otherwise the return value from the call
to (*fun) (arg) is returned.


File: internals.info,  Node: Symbols and Variables,  Next: Buffers,  Prev: Evaluation; Stack Frames; Bindings,  Up: Top

22 Symbols and Variables
************************

* Menu:

* Introduction to Symbols::
* Obarrays::
* Symbol Values::


File: internals.info,  Node: Introduction to Symbols,  Next: Obarrays,  Prev: Symbols and Variables,  Up: Symbols and Variables

22.1 Introduction to Symbols
============================

A symbol is basically just an object with four fields: a name (a
string), a value (some Lisp object), a function (some Lisp object), and
a property list (usually a list of alternating keyword/value pairs).
What makes symbols special is that there is usually only one symbol with
a given name, and the symbol is referred to by name.  This makes a
symbol a convenient way of calling up data by name, i.e. of implementing
variables. (The variable's value is stored in the "value slot".)
Similarly, functions are referenced by name, and the definition of the
function is stored in a symbol's "function slot".  This means that
there can be a distinct function and variable with the same name.  The
property list is used as a more general mechanism of associating
additional values with particular names, and once again the namespace is
independent of the function and variable namespaces.


File: internals.info,  Node: Obarrays,  Next: Symbol Values,  Prev: Introduction to Symbols,  Up: Symbols and Variables

22.2 Obarrays
=============

The identity of symbols with their names is accomplished through a
structure called an obarray, which is just a poorly-implemented hash
table mapping from strings to symbols whose name is that string. (I say
"poorly implemented" because an obarray appears in Lisp as a vector
with some hidden fields rather than as its own opaque type.  This is an
Emacs Lisp artifact that should be fixed.)

   Obarrays are implemented as a vector of some fixed size (which should
be a prime for best results), where each "bucket" of the vector
contains one or more symbols, threaded through a hidden `next' field in
the symbol.  Lookup of a symbol in an obarray, and adding a symbol to
an obarray, is accomplished through standard hash-table techniques.

   The standard Lisp function for working with symbols and obarrays is
`intern'.  This looks up a symbol in an obarray given its name; if it's
not found, a new symbol is automatically created with the specified
name, added to the obarray, and returned.  This is what happens when the
Lisp reader encounters a symbol (or more precisely, encounters the name
of a symbol) in some text that it is reading.  There is a standard
obarray called `obarray' that is used for this purpose, although the
Lisp programmer is free to create his own obarrays and `intern' symbols
in them.

   Note that, once a symbol is in an obarray, it stays there until
something is done about it, and the standard obarray `obarray' always
stays around, so once you use any particular variable name, a
corresponding symbol will stay around in `obarray' until you exit
XEmacs.

   Note that `obarray' itself is a variable, and as such there is a
symbol in `obarray' whose name is `"obarray"' and which contains
`obarray' as its value.

   Note also that this call to `intern' occurs only when in the Lisp
reader, not when the code is executed (at which point the symbol is
already around, stored as such in the definition of the function).

   You can create your own obarray using `make-vector' (this is
horrible but is an artifact) and intern symbols into that obarray.
Doing that will result in two or more symbols with the same name.
However, at most one of these symbols is in the standard `obarray': You
cannot have two symbols of the same name in any particular obarray.
Note that you cannot add a symbol to an obarray in any fashion other
than using `intern': i.e. you can't take an existing symbol and put it
in an existing obarray.  Nor can you change the name of an existing
symbol. (Since obarrays are vectors, you can violate the consistency of
things by storing directly into the vector, but let's ignore that
possibility.)

   Usually symbols are created by `intern', but if you really want, you
can explicitly create a symbol using `make-symbol', giving it some
name.  The resulting symbol is not in any obarray (i.e. it is
"uninterned"), and you can't add it to any obarray.  Therefore its
primary purpose is as a symbol to use in macros to avoid namespace
pollution.  It can also be used as a carrier of information, but cons
cells could probably be used just as well.

   You can also use `intern-soft' to look up a symbol but not create a
new one, and `unintern' to remove a symbol from an obarray.  This
returns the removed symbol. (Remember: You can't put the symbol back
into any obarray.) Finally, `mapatoms' maps over all of the symbols in
an obarray.


File: internals.info,  Node: Symbol Values,  Prev: Obarrays,  Up: Symbols and Variables

22.3 Symbol Values
==================

The value field of a symbol normally contains a Lisp object.  However,
a symbol can be "unbound", meaning that it logically has no value.
This is internally indicated by storing a special Lisp object, called
"the unbound marker" and stored in the global variable `Qunbound'.  The
unbound marker is of a special Lisp object type called
"symbol-value-magic".  It is impossible for the Lisp programmer to
directly create or access any object of this type.

   *You must not let any "symbol-value-magic" object escape to the Lisp
level.*  Printing any of these objects will cause the message `INTERNAL
EMACS BUG' to appear as part of the print representation.  (You may see
this normally when you call `debug_print()' from the debugger on a Lisp
object.) If you let one of these objects escape to the Lisp level, you
will violate a number of assumptions contained in the C code and make
the unbound marker not function right.

   When a symbol is created, its value field (and function field) are
set to `Qunbound'.  The Lisp programmer can restore these conditions
later using `makunbound' or `fmakunbound', and can query to see whether
the value of function fields are "bound" (i.e. have a value other than
`Qunbound') using `boundp' and `fboundp'.  The fields are set to a
normal Lisp object using `set' (or `setq') and `fset'.

   Other symbol-value-magic objects are used as special markers to
indicate variables that have non-normal properties.  This includes any
variables that are tied into C variables (setting the variable magically
sets some global variable in the C code, and likewise for retrieving the
variable's value), variables that magically tie into slots in the
current buffer, variables that are buffer-local, etc.  The
symbol-value-magic object is stored in the value cell in place of a
normal object, and the code to retrieve a symbol's value (i.e.
`symbol-value') knows how to do special things with them.  This means
that you should not just fetch the value cell directly if you want a
symbol's value.

   The exact workings of this are rather complex and involved and are
well-documented in comments in `buffer.c', `symbols.c', and `lisp.h'.


File: internals.info,  Node: Buffers,  Next: Text,  Prev: Symbols and Variables,  Up: Top

23 Buffers
**********

* Menu:

* Introduction to Buffers::     A buffer holds a block of text such as a file.
* Buffer Lists::                Keeping track of all buffers.
* Markers and Extents::         Tagging locations within a buffer.
* The Buffer Object::           The Lisp object corresponding to a buffer.


File: internals.info,  Node: Introduction to Buffers,  Next: Buffer Lists,  Prev: Buffers,  Up: Buffers

23.1 Introduction to Buffers
============================

A buffer is logically just a Lisp object that holds some text.  In
this, it is like a string, but a buffer is optimized for frequent
insertion and deletion, while a string is not.  Furthermore:

  1. Buffers are "permanent" objects, i.e. once you create them, they
     remain around, and need to be explicitly deleted before they go
     away.

  2. Each buffer has a unique name, which is a string.  Buffers are
     normally referred to by name.  In this respect, they are like
     symbols.

  3. Buffers have a default insertion position, called "point".
     Inserting text (unless you explicitly give a position) goes at
     point, and moves point forward past the text.  This is what is
     going on when you type text into Emacs.

  4. Buffers have lots of extra properties associated with them.

  5. Buffers can be "displayed".  What this means is that there exist a
     number of "windows", which are objects that correspond to some
     visible section of your display, and each window has an associated
     buffer, and the current contents of the buffer are shown in that
     section of the display.  The redisplay mechanism (which takes care
     of doing this) knows how to look at the text of a buffer and come
     up with some reasonable way of displaying this.  Many of the
     properties of a buffer control how the buffer's text is displayed.

  6. One buffer is distinguished and called the "current buffer".  It is
     stored in the variable `current_buffer'.  Buffer operations operate
     on this buffer by default.  When you are typing text into a
     buffer, the buffer you are typing into is always `current_buffer'.
     Switching to a different window changes the current buffer.  Note
     that Lisp code can temporarily change the current buffer using
     `set-buffer' (often enclosed in a `save-excursion' so that the
     former current buffer gets restored when the code is finished).
     However, calling `set-buffer' will NOT cause a permanent change in
     the current buffer.  The reason for this is that the top-level
     event loop sets `current_buffer' to the buffer of the selected
     window, each time it finishes executing a user command.

   Make sure you understand the distinction between "current buffer"
and "buffer of the selected window", and the distinction between
"point" of the current buffer and "window-point" of the selected
window. (This latter distinction is explained in detail in the section
on windows.)


File: internals.info,  Node: Buffer Lists,  Next: Markers and Extents,  Prev: Introduction to Buffers,  Up: Buffers

23.2 Buffer Lists
=================

Recall earlier that buffers are "permanent" objects, i.e.  that they
remain around until explicitly deleted.  This entails that there is a
list of all the buffers in existence.  This list is actually an
assoc-list (mapping from the buffer's name to the buffer) and is stored
in the global variable `Vbuffer_alist'.

   The order of the buffers in the list is important: the buffers are
ordered approximately from most-recently-used to least-recently-used.
Switching to a buffer using `switch-to-buffer', `pop-to-buffer', etc.
and switching windows using `other-window', etc.  usually brings the
new current buffer to the front of the list.  `switch-to-buffer',
`other-buffer', etc. look at the beginning of the list to find an
alternative buffer to suggest.  You can also explicitly move a buffer
to the end of the list using `bury-buffer'.

   In addition to the global ordering in `Vbuffer_alist', each frame
has its own ordering of the list.  These lists always contain the same
elements as in `Vbuffer_alist' although possibly in a different order.
`buffer-list' normally returns the list for the selected frame.  This
allows you to work in separate frames without things interfering with
each other.

   The standard way to look up a buffer given a name is `get-buffer',
and the standard way to create a new buffer is `get-buffer-create',
which looks up a buffer with a given name, creating a new one if
necessary.  These operations correspond exactly with the symbol
operations `intern-soft' and `intern', respectively.  You can also
force a new buffer to be created using `generate-new-buffer', which
takes a name and (if necessary) makes a unique name from this by
appending a number, and then creates the buffer.  This is basically
like the symbol operation `gensym'.


File: internals.info,  Node: Markers and Extents,  Next: The Buffer Object,  Prev: Buffer Lists,  Up: Buffers

23.3 Markers and Extents
========================

Among the things associated with a buffer are things that are logically
attached to certain buffer positions.  This can be used to keep track
of a buffer position when text is inserted and deleted, so that it
remains at the same spot relative to the text around it; to assign
properties to particular sections of text; etc.  There are two such
objects that are useful in this regard: they are "markers" and
"extents".

   A "marker" is simply a flag placed at a particular buffer position,
which is moved around as text is inserted and deleted.  Markers are
used for all sorts of purposes, such as the `mark' that is the other
end of textual regions to be cut, copied, etc.

   An "extent" is similar to two markers plus some associated
properties, and is used to keep track of regions in a buffer as text is
inserted and deleted, and to add properties (e.g. fonts) to particular
regions of text.  The external interface of extents is explained
elsewhere.

   The important thing here is that markers and extents simply contain
buffer positions in them as integers, and every time text is inserted or
deleted, these positions must be updated.  In order to minimize the
amount of shuffling that needs to be done, the positions in markers and
extents (there's one per marker, two per extent) are stored in
Membpos's.  This means that they only need to be moved when the text is
physically moved in memory; since the gap structure tries to minimize
this, it also minimizes the number of marker and extent indices that
need to be adjusted.  Look in `insdel.c' for the details of how this
works.

   One other important distinction is that markers are "temporary"
while extents are "permanent".  This means that markers disappear as
soon as there are no more pointers to them, and correspondingly, there
is no way to determine what markers are in a buffer if you are just
given the buffer.  Extents remain in a buffer until they are detached
(which could happen as a result of text being deleted) or the buffer is
deleted, and primitives do exist to enumerate the extents in a buffer.


File: internals.info,  Node: The Buffer Object,  Prev: Markers and Extents,  Up: Buffers

23.4 The Buffer Object
======================

Buffers contain fields not directly accessible by the Lisp programmer.
We describe them here, naming them by the names used in the C code.
Many are accessible indirectly in Lisp programs via Lisp primitives.

`name'
     The buffer name is a string that names the buffer.  It is
     guaranteed to be unique.  *Note Buffer Names: (lispref)Buffer
     Names.

`save_modified'
     This field contains the time when the buffer was last saved, as an
     integer.  *Note Buffer Modification: (lispref)Buffer Modification.

`modtime'
     This field contains the modification time of the visited file.  It
     is set when the file is written or read.  Every time the buffer is
     written to the file, this field is compared to the modification
     time of the file.  *Note Buffer Modification: (lispref)Buffer
     Modification.

`auto_save_modified'
     This field contains the time when the buffer was last auto-saved.

`last_window_start'
     This field contains the `window-start' position in the buffer as of
     the last time the buffer was displayed in a window.

`undo_list'
     This field points to the buffer's undo list.  *Note Undo:
     (lispref)Undo.

`syntax_table_v'
     This field contains the syntax table for the buffer.  *Note Syntax
     Tables: (lispref)Syntax Tables.

`downcase_table'
     This field contains the conversion table for converting text to
     lower case.  *Note Case Tables: (lispref)Case Tables.

`upcase_table'
     This field contains the conversion table for converting text to
     upper case.  *Note Case Tables: (lispref)Case Tables.

`case_canon_table'
     This field contains the conversion table for canonicalizing text
     for case-folding search.  *Note Case Tables: (lispref)Case Tables.

`case_eqv_table'
     This field contains the equivalence table for case-folding search.
     *Note Case Tables: (lispref)Case Tables.

`display_table'
     This field contains the buffer's display table, or `nil' if it
     doesn't have one.  *Note Display Tables: (lispref)Display Tables.

`markers'
     This field contains the chain of all markers that currently point
     into the buffer.  Deletion of text in the buffer, and motion of
     the buffer's gap, must check each of these markers and perhaps
     update it.  *Note Markers: (lispref)Markers.

`backed_up'
     This field is a flag that tells whether a backup file has been
     made for the visited file of this buffer.

`mark'
     This field contains the mark for the buffer.  The mark is a marker,
     hence it is also included on the list `markers'.  *Note The Mark:
     (lispref)The Mark.

`mark_active'
     This field is non-`nil' if the buffer's mark is active.

`local_var_alist'
     This field contains the association list describing the variables
     local in this buffer, and their values, with the exception of
     local variables that have special slots in the buffer object.
     (Those slots are omitted from this table.)  *Note Buffer-Local
     Variables: (lispref)Buffer-Local Variables.

`modeline_format'
     This field contains a Lisp object which controls how to display
     the mode line for this buffer.  *Note Modeline Format:
     (lispref)Modeline Format.

`base_buffer'
     This field holds the buffer's base buffer (if it is an indirect
     buffer), or `nil'.


File: internals.info,  Node: Text,  Next: Multilingual Support,  Prev: Buffers,  Up: Top

24 Text
*******

* Menu:

* The Text in a Buffer::        Representation of the text in a buffer.
* Ibytes and Ichars::           Representation of individual characters.
* Byte-Char Position Conversion::
* Searching and Matching::      Higher-level algorithms.


File: internals.info,  Node: The Text in a Buffer,  Next: Ibytes and Ichars,  Prev: Text,  Up: Text

24.1 The Text in a Buffer
=========================

The text in a buffer consists of a sequence of zero or more characters.
A "character" is an integer that logically represents a letter,
number, space, or other unit of text.  Most of the characters that you
will typically encounter belong to the ASCII set of characters, but
there are also characters for various sorts of accented letters,
special symbols, Chinese and Japanese ideograms (i.e. Kanji, Katakana,
etc.), Cyrillic and Greek letters, etc.  The actual number of possible
characters is quite large.

   For now, we can view a character as some non-negative integer that
has some shape that defines how it typically appears (e.g. as an
uppercase A). (The exact way in which a character appears depends on the
font used to display the character.) The internal type of characters in
the C code is an `Ichar'; this is just an `int', but using a symbolic
type makes the code clearer.

   Between every character in a buffer is a "buffer position" or
"character position".  We can speak of the character before or after a
particular buffer position, and when you insert a character at a
particular position, all characters after that position end up at new
positions.  When we speak of the character "at" a position, we really
mean the character after the position.  (This schizophrenia between a
buffer position being "between" two characters and "on" a character is
rampant in Emacs.)

   Buffer positions are numbered starting at 1.  This means that
position 1 is before the first character, and position 0 is not valid.
If there are N characters in a buffer, then buffer position N+1 is
after the last one, and position N+2 is not valid.

   The internal makeup of the Ichar integer varies depending on whether
we have compiled with MULE support.  If not, the Ichar integer is an
8-bit integer with possible values from 0 - 255.  0 - 127 are the
standard ASCII characters, while 128 - 255 are the characters from the
ISO-8859-1 character set.  If we have compiled with MULE support, an
Ichar is a 19-bit integer, with the various bits having meanings
according to a complex scheme that will be detailed later.  The
characters numbered 0 - 255 still have the same meanings as for the
non-MULE case, though.

   Internally, the text in a buffer is represented in a fairly simple
fashion: as a contiguous array of bytes, with a "gap" of some size in
the middle.  Although the gap is of some substantial size in bytes,
there is no text contained within it: From the perspective of the text
in the buffer, it does not exist.  The gap logically sits at some buffer
position, between two characters (or possibly at the beginning or end of
the buffer).  Insertion of text in a buffer at a particular position is
always accomplished by first moving the gap to that position (i.e.
through some block moving of text), then writing the text into the
beginning of the gap, thereby shrinking the gap.  If the gap shrinks
down to nothing, a new gap is created. (What actually happens is that a
new gap is "created" at the end of the buffer's text, which requires
nothing more than changing a couple of indices; then the gap is "moved"
to the position where the insertion needs to take place by moving up in
memory all the text after that position.)  Similarly, deletion occurs
by moving the gap to the place where the text is to be deleted, and
then simply expanding the gap to include the deleted text.
("Expanding" and "shrinking" the gap as just described means just that
the internal indices that keep track of where the gap is located are
changed.)

   Note that the total amount of memory allocated for a buffer text
never decreases while the buffer is live.  Therefore, if you load up a
20-megabyte file and then delete all but one character, there will be a
20-megabyte gap, which won't get any smaller (except by inserting
characters back again).  Once the buffer is killed, the memory allocated
for the buffer text will be freed, but it will still be sitting on the
heap, taking up virtual memory, and will not be released back to the
operating system. (However, if you have compiled XEmacs with rel-alloc,
the situation is different.  In this case, the space _will_ be released
back to the operating system.  However, this tends to result in a
noticeable speed penalty.)

   Astute readers may notice that the text in a buffer is represented as
an array of _bytes_, while (at least in the MULE case) an Ichar is a
19-bit integer, which clearly cannot fit in a byte.  This means (of
course) that the text in a buffer uses a different representation from
an Ichar: specifically, the 19-bit Ichar becomes a series of one to
four bytes.  The conversion between these two representations is complex
and will be described later.

   In the non-MULE case, everything is very simple: An Ichar is an
8-bit value, which fits neatly into one byte.

   If we are given a buffer position and want to retrieve the character
at that position, we need to follow these steps:

  1. Pretend there's no gap, and convert the buffer position into a
     "byte index" that indexes to the appropriate byte in the buffer's
     stream of textual bytes.  By convention, byte indices begin at 1,
     just like buffer positions.  In the non-MULE case, byte indices
     and buffer positions are identical, since one character equals one
     byte.

  2. Convert the byte index into a "memory index", which takes the gap
     into account.  The memory index is a direct index into the block of
     memory that stores the text of a buffer.  This basically just
     involves checking to see if the byte index is past the gap, and if
     so, adding the size of the gap to it.  By convention, memory
     indices begin at 1, just like buffer positions and byte indices,
     and when referring to the position that is "at" the gap, we always
     use the memory position at the _beginning_, not at the end, of the
     gap.

  3. Fetch the appropriate bytes at the determined memory position.

  4. Convert these bytes into an Ichar.

   In the non-Mule case, (3) and (4) boil down to a simple one-byte
memory access.

   Note that we have defined three types of positions in a buffer:

  1. "buffer positions" or "character positions", typedef `Charbpos'

  2. "byte indices", typedef `Bytebpos'

  3. "memory indices", typedef `Membpos'

   All three typedefs are just `int's, but defining them this way makes
things a lot clearer.

   Most code works with buffer positions.  In particular, all Lisp code
that refers to text in a buffer uses buffer positions.  Lisp code does
not know that byte indices or memory indices exist.

   Finally, we have a typedef for the bytes in a buffer.  This is a
`Ibyte', which is an unsigned char.  Referring to them as Ibytes
underscores the fact that we are working with a string of bytes in the
internal Emacs buffer representation rather than in one of a number of
possible alternative representations (e.g. EUC-encoded text, etc.).


File: internals.info,  Node: Ibytes and Ichars,  Next: Byte-Char Position Conversion,  Prev: The Text in a Buffer,  Up: Text

24.2 Ibytes and Ichars
======================

Not yet documented.


File: internals.info,  Node: Byte-Char Position Conversion,  Next: Searching and Matching,  Prev: Ibytes and Ichars,  Up: Text

24.3 Byte-Char Position Conversion
==================================

Oct 2004:

   This is what I wrote when describing the previous algorithm:

     The basic algorithm we use is to keep track of a known region of
     characters in each buffer, all of which are of the same width.  We
     keep track of the boundaries of the region in both Charbpos and
     Bytebpos coordinates and also keep track of the char width, which
     is 1 - 4 bytes.  If the position we're translating is not in the
     known region, then we invoke a function to update the known region
     to surround the position in question.  This assumes locality of
     reference, which is usually the case.

     Note that the function to update the known region can be simple or
     complicated depending on how much information we cache.  In
     addition to the known region, we always cache the correct
     conversions for point, BEGV, and ZV, and in addition to this we
     cache 16 positions where the conversion is known.  We only look in
     the cache or update it when we need to move the known region more
     than a certain amount (currently 50 chars), and then we throw away
     a "random" value and replace it with the newly calculated value.

     Finally, we maintain an extra flag that tracks whether the buffer
     is entirely ASCII, to speed up the conversions even more.  This
     flag is actually of dubious value because in an entirely-ASCII
     buffer the known region will always span the entire buffer (in
     fact, we update the flag based on this fact), and so all we're
     saving is a few machine cycles.

     A potentially smarter method than what we do with known regions and
     cached positions would be to keep some sort of pseudo-extent layer
     over the buffer; maybe keep track of the charbpos/bytebpos
     correspondence at the beginning of each line, which would allow us
     to do a binary search over the pseudo-extents to narrow things
     down to the correct line, at which point you could use a linear
     movement method.  This would also mesh well with efficiently
     implementing a line-numbering scheme.  However, you have to weigh
     the amount of time spent updating the cache vs. the savings that
     result from it.  In reality, we modify the buffer far less often
     than we access it, so a cache of this sort that provides
     guaranteed LOG (N) performance (or perhaps N * LOG (N), if we set a
     maximum on the cache size) would indeed be a win, particularly in
     very large buffers.  If we ever implement this, we should probably
     set a reasonably high minimum below which we use the old method,
     because the time spent updating the fancy cache would likely
     become dominant when making buffer modifications in smaller
     buffers.

     Note also that we have to multiply or divide by the char width in
     order to convert the positions.  We do some tricks to avoid ever
     actually having to do a multiply or divide, because that is
     typically an expensive operation (esp. divide).  Multiplying or
     dividing by 1, 2, or 4 can be implemented simply as a shift left
     or shift right, and we keep track of a shifter value (0, 1, or 2)
     indicating how much to shift.  Multiplying by 3 can be implemented
     by doubling and then adding the original value.  Dividing by 3,
     alas, cannot be implemented in any simple shift/subtract method,
     as far as I know; so we just do a table lookup.  For simplicity,
     we use a table of size 128K, which indexes the "divide-by-3"
     values for the first 64K non-negative numbers. (Note that we can
     increase the size up to 384K, i.e. indexing the first 192K
     non-negative numbers, while still using shorts in the array.) This
     also means that the size of the known region can be at most 64K for
     width-three characters.

   Unfortunately, it turned out that the implementation had serious
problems which had never been corrected.  In particular, the known
region had a large tendency to become zero-length and stay that way.

   So I decided to port the algorithm from FSF 21.3, in markers.c.

   This algorithm is fairly simple.  Instead of using markers I kept
the cache array of known positions from the previous implementation.

   Basically, we keep a number of positions cached:

   * the actual end of the buffer

   * the beginning and end of the accessible region

   * the value of point

   * the position of the gap

   * the last value we computed

   * a set of positions that are "far away" from previously computed
     positions (5000 chars currently; #### perhaps should be smaller)

   For each position, we `CONSIDER()' it.  This means:

   * If the position is what we're looking for, return it directly.

   * Starting with the beginning and end of the buffer, we successively
     compute the smallest enclosing range of known positions.  If at any
     point we discover that this range has the same byte and char length
     (i.e. is entirely single-byte), then our computation is trivial.

   * If at any point we get a small enough range (50 chars currently),
     stop considering further positions.

   Otherwise, once we have an enclosing range, see which side is
closer, and iterate until we find the desired value.  As an
optimization, I replaced the simple loop in FSF with the use of
`bytecount_to_charcount()', `charcount_to_bytecount()',
`bytecount_to_charcount_down()', or `charcount_to_bytecount_down()'.
(The latter two I added for this purpose.)  These scan 4 or 8 bytes at
a time through purely single-byte characters.

   If the amount we had to scan was more than our "far away" distance
(5000 characters, see above), then cache the new position.

   #### Things to do:

   * Look at the most recent GNU Emacs to see whether anything has
     changed.

   * Think about whether it makes sense to try to implement some sort of
     known region or list of "known regions", like we had before.  This
     would be a region of entirely single-byte characters that we can
     check very quickly. (Previously I used a range of same-width
     characters of any size; but this adds extra complexity and slows
     down the scanning, and is probably not worth it.) As part of the
     scanning process in `bytecount_to_charcount()' et al, we skip over
     chunks of entirely single-byte chars, so it should be easy to
     remember the last one.  Presumably what we should do is keep track
     of the largest known surrounding entirely-single-byte region for
     each of the cache positions as well as perhaps the last-cached
     position.  We want to be careful not to get bitten by the previous
     problem of having the known region getting reset too often.  If we
     implement this, we might well want to continue scanning some
     distance past the desired position (maybe 300-1000 bytes) if we are
     in a single-byte range so that we won't end up expanding the known
     range one position at a time and entering the function each time.

   * Think about whether it makes sense to keep the position cache
     sorted.  This would allow it to be larger and finer-grained in its
     positions.  Note that with FSF's use of markers, they were sorted,
     but this was not really made good use of.  With an array, we can
     do binary searching to quickly find the smallest range.  We would
     probably want to make use of the gap-array code in extents.c.

   Note that FSF's algorithm checked *ALL* markers, not just the ones
cached by this algorithm.  This includes markers created by the user as
well as both ends of any overlays.  We could do similarly, and our
extents could keep both byte and character positions rather than just
the former.  (But this would probably be overkill.  We should just use
our cache instead.  Any place an extent was set was surely already
visited by the char<->byte conversion routines.)


File: internals.info,  Node: Searching and Matching,  Prev: Byte-Char Position Conversion,  Up: Text

24.4 Searching and Matching
===========================

Very incomplete, limited to a brief introduction.

   People find the searching and matching code difficult to understand.
And indeed, the details are hard.  However, the basic structures are not
so complex.  First, there's a hard question with a simple answer.  What
about Mule?  The answer here is that it turns out that Mule characters
can be matched byte by byte, so neither the search code nor the regular
expression code need take much notice of it at all!  Of course, we add
some special features (such as regular expressions that match only
certain charsets), but these do not require new concepts.  The main
exception is that wild-card matches in Mule have to be careful to
swallow whole characters.  This is handled using the same basic macros
that are used for buffer and string movements.

   This will also be true if a UTF-8 representation is used for the
internal encoding.

   The complex algorithms for searching are for simple string searches.
In particular, the algorithm used for fast string searching is
Boyer-Moore.  This algorithm is based on the idea that if you have a
mismatch at a given position, you can precompute where to restart the
search.  This typically means that you can often make many fewer than N
character comparisons, where N is the position at which the match is
found, or the size of the text if it contains no match.  That's fast!
But it's not easy.  You must "compile" the search string into a jump
table.  See the source, `search.c', for more information.

   Emacs changes the basic algorithms somewhat in order to handle
case-insensitive searches without a full-blown regular expression.

   Regular expressions, on the other hand, have a trivial search
implementation: try a match at each position.  (Under POSIX rules, it's
a bit more complex, because POSIX requires that you find the _longest_
match in the text.  This means you keep a record of the best match so
far, and find all the matches.)

   The matching code for regular expressions is quite complex.  First,
the regular expression itself is compiled.  There are two basic
approaches that could be taken.  The first is to compile the expression
into tables to drive a generic finite automaton emulator.  This is the
approach given in many textbooks (Sedgewick's _Algorithms_ and Aho,
Sethi, and Ullmann's _Compilers: Principles, Techniques, and Tools_, aka
"The Dragon Book") as well as being used by the `lex' family of lexical
analysis engines.

   Emacs uses a somewhat different technique.  The expression is
compiled into a form of bytecode, which is interpreted by a special
interpreter.  The interpreter itself basically amounts to an inline
implementation of the finite automaton emulator.  The advantage of this
technique is that it's easier to add special features, such as control
of case-sensitivity via a global variable.

   The compiler is not treated here.  See the source, `regex.c'.  The
interpreter, although it is divided into several functions, and looks
fearsomely complex, is actually quite simple in concept.  However,
basically what you're doing there is a strcmp on steroids, right?

     int
     strcmp (char *p,            /* pattern pointer */
             char *b)            /* buffer pointer  */
     {
       while (*p++ == *b++)
         ;
       return *(--p) - *(--b);   /* oops, we overshot */
     }

   Really, it's no harder than that.  (A bit of a white lie, OK?)

   How does the regexp code generalize this?

  1. Depending on the pattern, `*b' may have a general relationship to
     `*p'.  _I.e._, direct comparison against `*p' is generalized to
     include checks for set membership, and context dependent
     properties.  This depends on `&*b'.  Of course that's meaningless
     in C, so we use `b' directly, instead.

  2. Although to ensure the algorithm terminates, `b' must advance step
     by step, `p' can branch and jump.

  3. The information returned is much greater, including information
     about subexpressions.

   We'll ignore (3).  (2) is mostly interesting when compiling the
regular expression.  Now we have

     enum operator_t {
       accept = 0,
       exact,
       any,
       range,
       group,       /* actually, these are probably */
       repeat,      /* turned into conditional code */
       /* etc */
     };

     enum status_t {
       working = 0,
       matched,
       mismatch,
       end_of_buffer,
       error
       };

     struct pattern {
       enum operator_t operator;
       char char_value;
       boolean range_table[256];
       /* etc, etc */
       };

     char *p,  /* pattern pointer */
          *b;  /* buffer pointer */

     enum status_t
     match (struct pattern *p, char *b)
     {
       enum status_t done = working;

       while (!(done = match_1_operator (p, b)))
         {
           struct pattern *p1 = p;
           p = next_p (p, b);
           b = next_b (p1, b);
         }
       return done;
     }

   This format exposes the underlying finite automaton.

   All of them have the following structure, except that the `next_*'
functions decide where to jump (for `p') and whether or not to
increment (for `b'), rather than checking for satisfaction of a
matching condition.

     enum status_t
     match_1_operator (pattern *p, char *b)
     {
       if (! *b) return end_of_buffer;
       switch (p->operator)
         {
         case accept:
           return matched;
         case exact:
           if (*b != p->char_value) return mismatch; else break;
         case any:
           break;
         case range:
           /* range_table is computed in the regexp_compile function */
           if (! p->range_table[*b]) return mismatch;
         /* etc, etc */
         }
       return working;
     }

   Grouping, repetition, and alternation are handled by compiling the
subexpression and calling `match (p->subpattern, b)' recursively.

   In terms of reading the actual code, there are five optimizations
(obfuscations, if you like) that have been done.

  1. An explicit "failure stack" has been substituted for recursion.

  2. The `match_1_operator', `next_p', and `next_b' functions are
     actually inlined into the `match' function for efficiency.  Then
     the pointer movement is interspersed with the matching operations.

  3. If the operator uses buffer context, the buffer pointer movement is
     sometimes implicit in the operations retrieving the context.

  4. Some cases are combined into short preparation for individual
     cases, and a "fall-through" into combined code for several cases.

  5. The `pattern' type is not an explicit `struct'.  Instead, the data
     (including, _e.g._, `range_table') is inlined into the compiled
     bytecode.  This leads to bizarre code in the interpreter like

          case range:
            p += *(p + 1); break;

     in `next_p', because the compiled pattern is laid out

          ..., 'range', count, first_8_flags, second_8_flags, ..., next_op, ...

   But if you keep your eye on the "switch in a loop" structure, you
should be able to understand the parts you need.


File: internals.info,  Node: Multilingual Support,  Next: Consoles; Devices; Frames; Windows,  Prev: Text,  Up: Top

25 Multilingual Support
***********************

_NOTE_: There is a great deal of overlapping and redundant information
in this chapter.  Ben wrote introductions to Mule issues a number of
times, each time not realizing that he had already written another
introduction previously.  Hopefully, in time these will all be
integrated.

   _NOTE_: The information at the top of the source file `text.c' is
more complete than the following, and there is also a list of all other
places to look for text/I18N-related info.  Also look in `text.h' for
info about the DFC and Eistring API's.

   Recall that there are two primary ways that text is represented in
XEmacs.  The "buffer" representation sees the text as a series of bytes
(Ibytes), with a variable number of bytes used per character.  The
"character" representation sees the text as a series of integers
(Ichars), one per character.  The character representation is a cleaner
representation from a theoretical standpoint, and is thus used in many
cases when lots of manipulations on a string need to be done.  However,
the buffer representation is the standard representation used in both
Lisp strings and buffers, and because of this, it is the "default"
representation that text comes in.  The reason for using this
representation is that it's compact and is compatible with ASCII.

* Menu:

* Introduction to Multilingual Issues #1::
* Introduction to Multilingual Issues #2::
* Introduction to Multilingual Issues #3::
* Introduction to Multilingual Issues #4::
* Character Sets::
* Encodings::
* Internal Mule Encodings::
* Byte/Character Types; Buffer Positions; Other Typedefs::
* Internal Text API's::
* Coding for Mule::
* CCL::
* Microsoft Windows-Related Multilingual Issues::
* Modules for Internationalization::


File: internals.info,  Node: Introduction to Multilingual Issues #1,  Next: Introduction to Multilingual Issues #2,  Prev: Multilingual Support,  Up: Multilingual Support

25.1 Introduction to Multilingual Issues #1
===========================================

There is an introduction to these issues in the Lisp Reference manual.
*Note Internationalization Terminology: (lispref)Internationalization
Terminology.  Among other documentation that may be of interest to
internals programmers is ISO-2022 (*note ISO 2022: (lispref)ISO 2022.)
and CCL (*note CCL: (lispref)CCL.)


File: internals.info,  Node: Introduction to Multilingual Issues #2,  Next: Introduction to Multilingual Issues #3,  Prev: Introduction to Multilingual Issues #1,  Up: Multilingual Support

25.2 Introduction to Multilingual Issues #2
===========================================

Introduction
------------

This document covers a number of design issues, problems and proposals
with regards to XEmacs MULE.  At first we present some definitions and
some aspects of the design that have been agreed upon.  Then we present
some issues and problems that need to be addressed, and then I include a
proposal of mine to address some of these issues.  When there are other
proposals, for example from Olivier, these will be appended to the end
of this document.

Definitions and Design Basics
-----------------------------

First, "text" is defined to be a series of characters which together
defines an utterance or partial utterance in some language.  Generally,
this language is a human language, but it may also be a computer
language if the computer language uses a representation close enough to
that of human languages for it to also make sense to call its
representation text.  Text is opposed to "binary", which is a sequence
of bytes, representing machine-readable but not human-readable data.  A
"byte" is merely a number within a predefined range, which nowadays is
nearly always zero to 255.  A "character" is a unit of text.  What makes
one character different from another is not always clear-cut.  It is
generally related to the appearance of the character, although perhaps
not any possible appearance of that character, but some sort of ideal
appearance that is assigned to a character.  Whether two characters
that look very similar are actually the same depends on various factors
such as political ones, such as whether the characters are used to mean
similar sorts of things, or behave similarly in similar contexts.  In
any case, it is not always clearly defined whether two characters are
actually the same or not.  In practice, however, this is more or less
agreed upon.

   A "character set" is just that, a set of one or more characters.
The set is unique in that there will not be more than one instance of
the same character in a character set, and logically is unordered,
although an order is often imposed or suggested for the characters in
the character set.  We can also define an "order" on a character set,
which is a way of assigning a unique number, or possibly a pair of
numbers, or a triplet of numbers, or even a set of four or more numbers
to each character in the character set.  The combination of an order in
the character set results in an "ordered character set".  In an ordered
character set, there is an upper limit and a lower limit on the
possible values that a character, or that any number within the set of
numbers assigned to a character, can take.  However, the lower limit
does not have to start at zero or one, or anywhere else in particular,
nor does the upper limit have to end anywhere particular, and there may
be gaps within these ranges such that particular numbers or sets of
numbers do not have a corresponding character, even though they are
within the upper and lower limits.  For example, "ASCII" defines a very
standard ordered character set.  It is normally defined to be 94
characters in the range 33 through 126 inclusive on both ends, with
every possible character within this range being actually present in the
character set.

   Sometimes the ASCII character set is extended to include what are
called "non-printing characters".  Non-printing characters are
characters which instead of really being displayed in a more or less
rectangular block, like all other characters, instead indicate certain
functions typically related to either control of the display upon which
the characters are being displayed, or have some effect on a
communications channel that may be currently open and transmitting
characters, or may change the meaning of future characters as they are
being decoded, or some other similar function.  You might say that
non-printing characters are somewhat of a hack because they are a
special exception to the standard concept of a character as being a
printed glyph that has some direct correspondence in the non-computer
world.

   With non-printing characters in mind, the 94-character ordered
character set called ASCII is often extended into a 96-character
ordered character set, also often called ASCII, which includes in
addition to the 94 characters already mentioned, two non-printing
characters, one called space and assigned the number 32, just below the
bottom of the previous range, and another called "delete" or "rubout",
which is given number 127 just above the end of the previous range.
Thus to reiterate, the result is a 96-character ordered character set,
whose characters take the values from 32 to 127 inclusive.  Sometimes
ASCII is further extended to contain 32 more non-printing characters,
which are given the numbers zero through 31 so that the result is a
128-character ordered character set with characters numbered zero
through 127, and with many non-printing characters.  Another way to
look at this, and the way that is normally taken by XEmacs MULE, is
that the characters that would be in the range 30 through 31 in the
most extended definition of ASCII, instead form their own ordered
character set, which is called "control zero", and consists of 32
characters in the range zero through 31.  A similar ordered character
set called "control one" is also created, and it contains 32 more
non-printing characters in the range 128 through 159.  Note that none
of these three ordered character sets overlaps in any of the numbers
they are assigned to their characters, so they can all be used at once.
Note further that the same character can occur in more than one
character set.  This was shown above, for example, in two different
ordered character sets we defined, one of which we could have called
"ASCII", and the other "ASCII-extended", to show that it had extended
by two non-printable characters.  Most of the characters in these two
character sets are shared and present in both of them.

   Note that there is no restriction on the size of the character set,
or on the numbers that are assigned to characters in an ordered
character set.  It is often extremely useful to represent a sequence of
characters as a sequence of bytes, where a byte as defined above is a
number in the range zero to 255.  An "encoding" does precisely this.
It is simply a mapping from a sequence of characters, possibly
augmented with information indicating the character set that each of
these characters belongs to, to a sequence of bytes which represents
that sequence of characters and no other - which is to say the mapping
is reversible.

   A "coding system" is a set of rules for encoding a sequence of
characters augmented with character set information into a sequence of
bytes, and later performing the reverse operation.  It is frequently
possible to group coding systems into classes or types based on common
features.  Typically, for example, a particular coding system class may
contain a base coding system which specifies some of the rules, but
leaves the rest unspecified.  Individual members of the coding system
class are formed by starting with the base coding system, and
augmenting it with additional rules to produce a particular coding
system, what you might think of as a sort of variation within a theme.

XEmacs Specific Definitions
---------------------------

First of all, in XEmacs, the concept of character is a little different
from the general definition given above.  For one thing, the character
set that a character belongs to may or may not be an inherent part of
the character itself.  In other words, the same character occurring in
two different character sets may appear in XEmacs as two different
characters.  This is generally the case now, but we are attempting to
move in the other direction.  Different proposals may have different
ideas about exactly the extent to which this change will be carried out.
The general trend, though, is to represent all information about a
character other than the character itself, using text properties
attached to the character.  That way two instances of the same character
will look the same to lisp code that merely retrieves the character, and
does not also look at the text properties of that character.  Everyone
involved is in agreement in doing it this way with all Latin characters,
and in fact for all characters other than Chinese, Japanese, and Korean
ideographs.  For those, there may be a difference of opinion.

   A second difference between the general definition of character and
the XEmacs usage of character is that each character is assigned a
unique number that distinguishes it from all other characters in the
world, or at the very least, from all other characters currently
existing anywhere inside the current XEmacs invocation.  (If there is a
case where the weaker statement applies, but not the stronger
statement, it would possibly be with composite characters and any other
such characters that are created on the sly.)

   This unique number is called the "character representation" of the
character, and its particular details are a matter of debate.  There is
the current standard in use that it is undoubtedly going to change.
What has definitely been agreed upon is that it will be an integer, more
specifically a positive integer, represented with less than or equal to
31 bits on a 32-bit architecture, and possibly up to 63 bits on a 64-bit
architecture, with the proviso that any characters that whose
representation would fit in a 64-bit architecture, but not on a 32-bit
architecture, would be used only for composite characters, and others
that would satisfy the weak uniqueness property mentioned above, but not
with the strong uniqueness property.

   At this point, it is useful to talk about the different
representations that a sequence of characters can take.  The simplest
representation is simply as a sequence of characters, and this is
called the "Lisp representation" of text, because it is the
representation that Lisp programs see.  Other representations include
the external representation, which refers to any encoding of the
sequence of characters, using the definition of encoding mentioned
above.  Typically, text in the external representation is used outside
of XEmacs, for example in files, e-mail messages, web sites, and the
like.  Another representation for a sequence of characters is what I
will call the "byte representation", and it represents the way that
XEmacs internally represents text in a buffer, or in a string.
Potentially, the representation could be different between a buffer and
a string, and then the terms "buffer byte representation" and "string
byte representation" would be used, but in practice I don't think this
will occur.  It will be possible, of course, for buffers and strings, or
particular buffers and particular strings, to contain different
sub-representations of a single representation.  For example, Olivier's
1-2-4 proposal allows for three sub-representations of his internal byte
representation, allowing for 1 byte, 2 bytes, and 4 byte width
characters respectively.  A particular string may be in one
sub-representation, and a particular buffer in another
sub-representation, but overall both are following the same byte
representation.  I do not use the term "internal representation" here,
as many people have, because it is potentially ambiguous.

   Another representation is called the "array of characters
representation".  This is a representation on the C-level in which the
sequence of text is represented, not using the byte representation, but
by using an array of characters, each represented using the character
representation.  This sort of representation is often used by redisplay
because it is more convenient to work with than any of the other
internal representations.

   The term "binary representation" may also be heard.  Binary
representation is used to represent binary data.  When binary data is
represented in the lisp representation, an equivalence is simply set up
between bytes zero through 255, and characters zero through 255.  These
characters come from four character sets, which are from bottom to top,
control zero, ASCII, control 1, and Latin 1.  Together, they comprise
256 characters, and are a good mapping for the 256 possible bytes in a
binary representation.  Binary representation could also be used to
refer to an external representation of the binary data, which is a
simple direct byte-to-byte representation.  No internal representation
should ever be referred to as a binary representation because of
ambiguity.  The terms character set/encoding system were defined
generally, above.  In XEmacs, the equivalent concepts exist, although
character set has been shortened to charset, and in fact represents
specifically an ordered character set.  For each possible charset, and
for each possible coding system, there is an associated object in
XEmacs.  These objects will be of type charset and coding system,
respectively.  Charsets and coding systems are divided into classes, or
"types", the normal term under XEmacs, and all possible charsets
encoding systems that may be defined must be in one of these types.  If
you need to create a charset or coding system that is not one of these
types, you will have to modify the C code to support this new type.
Some of the existing or soon-to-be-created types are, or will be,
generic enough so that this shouldn't be an issue.  Note also that the
byte encoding for text and the character coding of a character are
closely related.  You might say that ideally each is the simplest
equivalent of the other given the general constraints on each
representation.

   To be specific, in the current MULE representation,

  1. Characters encode both the character itself and the character set
     that it comes from.  These character sets are always assumed to be
     representable as an ordered character set of size 96 or of size 96
     by 96, or the trivially-related sizes 94 and 94 by 94.  The only
     allowable exceptions are the control zero and control one character
     sets, which are of size 32.  Character sets which do not naturally
     have a compatible ordering such as this are shoehorned into an
     ordered character set, or possibly two ordered character sets of a
     compatible size.

  2. The variable width byte representation was deliberately chosen to
     allow scanning text forwards and backwards efficiently.  This
     necessitated defining the possible bytes into three ranges which
     we shall call A, B, and C.  Range A is used exclusively for
     single-byte characters, which is to say characters that are
     representing using only one contiguous byte.  Multi-byte
     characters are always represented by using one byte from Range B,
     followed by one or more bytes from Range C.  What this means is
     that bytes that begin a character are unequivocally distinguished
     from bytes that do not begin a character, and therefore there is
     never a problem scaling backwards and finding the beginning of a
     character.  Know that UTF8 adopts a proposal that is very similar
     in spirit in that it uses separate ranges for the first byte of a
     multi byte sequence, and the following bytes in multi-byte
     sequence.

  3. Given the fact that all ordered character sets allowed were
     essentially 96 characters per dimension, it made perfect sense to
     make Range C comprise 96 bytes.  With a little more tweaking, the
     currently-standard MULE byte representation was created, and was
     drafted from this.

  4. The MULE byte representation defined four basic representations for
     characters, which would take up from one to four bytes,
     respectively.  The MULE character representation thus had the
     following constraints:
       1. Character numbers zero through 255 should represent the
          characters that binary values zero through 255 would be
          mapped onto.  (Note: this was not the case in Kenichi Handa's
          version of this representation, but I changed it.)

       2. The four sub-classes of representation in the MULE byte
          representation should correspond to four contiguous
          non-overlapping ranges of characters.

       3. The algorithmic conversion between the single character
          represented in the byte representation and in the character
          representation should be as easy as possible.

       4. Given the previous constraints, the character representation
          should be as compact as possible, which is to say it should
          use the least number of bits possible.

   So you see that the entire structure of the byte and character
representations stemmed from a very small number of basic choices,
which were

  1. the choice to encode character set information in a character

  2. the choice to assume that all character sets would have an order
     imposed upon them with 96 characters per one or two dimensions.
     (This is less arbitrary than it seems-it follows ISO-2022)

  3. the choice to use a variable width byte representation.

   What this means is that you cannot really separate the byte
representation, the character representation, and the assumptions made
about characters and whether they represent character sets from each
other.  All of these are closely intertwined, and for purposes of
simplicity, they should be designed together.  If you change one
representation without changing another, you are in essence creating a
completely new design with its own attendant problems-since your new
design is likely to be quite complex and not very coherent with regards
to the translation between the character and byte representations, you
are likely to run into problems.


File: internals.info,  Node: Introduction to Multilingual Issues #3,  Next: Introduction to Multilingual Issues #4,  Prev: Introduction to Multilingual Issues #2,  Up: Multilingual Support

25.3 Introduction to Multilingual Issues #3
===========================================

In XEmacs, Mule is a code word for the support for input handling and
display of multi-lingual text.  This section provides an overview of how
this support impacts the C and Lisp code in XEmacs.  It is important for
anyone who works on the C or the Lisp code, especially on the C code, to
be aware of these issues, even if they don't work directly on code that
implements multi-lingual features, because there are various general
procedures that need to be followed in order to write Mule-compliant
code.  (The specifics of these procedures are documented elsewhere in
this manual.)

   There are four primary aspects of Mule support:

  1. internal handling and representation of multi-lingual text.

  2. conversion between the internal representation of text and the
     various external representations in which multi-lingual text is
     encoded, such as Unicode representations (including mostly fixed
     width encodings such as UCS-2/UTF-16 and UCS-4 and variable width
     ASCII conformant encodings, such as UTF-7 and UTF-8); the various
     ISO2022 representations, which typically use escape sequences to
     switch between different character sets (such as Compound Text,
     used under X Windows; JIS, used specifically for encoding
     Japanese; and EUC, a non-modal encoding used for Japanese, Korean,
     and certain other languages); Microsoft's multi-byte encodings
     (such as Shift-JIS); various simple encodings for particular 8-bit
     character sets (such as Latin-1 and Latin-2, and encodings (such
     as koi8 and Alternativny) for Cyrillic); and others.  This
     conversion needs to happen both for text in files and text sent to
     or retrieved from system API calls.  It even needs to happen for
     external binary data because the internal representation does not
     represent binary data simply as a sequence of bytes as it is
     represented externally.

  3. Proper display of multi-lingual characters.

  4. Input of multi-lingual text using the keyboard.

   These four aspects are for the most part independent of each other.

Characters, Character Sets, and Encodings
-----------------------------------------

A "character" (which is, BTW, a surprisingly complex concept) is, in a
written representation of text, the most basic written unit that has a
meaning of its own.  It's comparable to a phoneme when analyzing words
in spoken speech (for example, the sound of `t' in English, which in
fact has different pronunciations in different words - aspirated in
`time', unaspirated in `stop', unreleased or even pronounced as a
glottal stop in `button', etc. - but logically is a single concept).
Like a phoneme, a character is an abstract concept defined by its
_meaning_.  The character `lowercase f', for example, can always be
used to represent the first letter in the word `fill', regardless of
whether it's drawn upright or italic, whether the `fi' combination is
drawn as a single ligature, whether there are serifs on the bottom of
the vertical stroke, etc. (These different appearances of a single
character are often called "graphs" or "glyphs".) Our concern when
representing text is on representing the abstract characters, and not
on their exact appearance.

   A "character set" (or "charset"), as we define it, is a set of
characters, each with an associated number (or set of numbers - see
below), called a "code point".  It's important to understand that a
character is not defined by any number attached to it, but by its
meaning.  For example, ASCII and EBCDIC are two charsets containing
exactly the same characters (lowercase and uppercase letters, numbers 0
through 9, particular punctuation marks) but with different numberings.
The `comma' character in ASCII and EBCDIC, for instance, is the same
character despite having a different numbering.  Conversely, when
comparing ASCII and JIS-Roman, which look the same except that the
latter has a yen sign substituted for the backslash, we would say that
the backslash and yen sign are *not* the same characters, despite having
the same number (95) and despite the fact that all other characters are
present in both charsets, with the same numbering.  ASCII and JIS-Roman,
then, do _not_ have exactly the same characters in them (ASCII has a
backslash character but no yen-sign character, and vice-versa for
JIS-Roman), unlike ASCII and EBCDIC, even though the numberings in ASCII
and JIS-Roman are closer.

   It's also important to distinguish between charsets and encodings.
For a simple charset like ASCII, there is only one encoding normally
used - each character is represented by a single byte, with the same
value as its code point.  For more complicated charsets, however,
things are not so obvious.  Unicode version 2, for example, is a large
charset with thousands of characters, each indexed by a 16-bit number,
often represented in hex, e.g. 0x05D0 for the Hebrew letter "aleph".
One obvious encoding uses two bytes per character (actually two
encodings, depending on which of the two possible byte orderings is
chosen).  This encoding is convenient for internal processing of
Unicode text; however, it's incompatible with ASCII, so a different
encoding, e.g. UTF-8, is usually used for external text, for example
files or e-mail.  UTF-8 represents Unicode characters with one to three
bytes (often extended to six bytes to handle characters with up to
31-bit indices).  Unicode characters 00 to 7F (identical with ASCII)
are directly represented with one byte, and other characters with two
or more bytes, each in the range 80 to FF.

   In general, a single encoding may be able to represent more than one
charset.

Internal Representation of Text
-------------------------------

In an ASCII or single-European-character-set world, life is very simple.
There are 256 characters, and each character is represented using the
numbers 0 through 255, which fit into a single byte.  With a few
exceptions (such as case-changing operations or syntax classes like
'whitespace'), "text" is simply an array of indices into a font.  You
can get different languages simply by choosing fonts with different
8-bit character sets (ISO-8859-1, -2, special-symbol fonts, etc.), and
everything will "just work" as long as anyone else receiving your text
uses a compatible font.

   In the multi-lingual world, however, it is much more complicated.
There are a great number of different characters which are organized in
a complex fashion into various character sets.  The representation to
use is not obvious because there are issues of size versus speed to
consider.  In fact, there are in general two kinds of representations to
work with: one that represents a single character using an integer
(possibly a byte), and the other representing a single character as a
sequence of bytes.  The former representation is normally called fixed
width, and the other variable width. Both representations represent
exactly the same characters, and the conversion from one representation
to the other is governed by a specific formula (rather than by table
lookup) but it may not be simple.  Most C code need not, and in fact
should not, know the specifics of exactly how the representations work.
In fact, the code must not make assumptions about the representations.
This means in particular that it must use the proper macros for
retrieving the character at a particular memory location, determining
how many characters are present in a particular stretch of text, and
incrementing a pointer to a particular character to point to the
following character, and so on.  It must not assume that one character
is stored using one byte, or even using any particular number of bytes.
It must not assume that the number of characters in a stretch of text
bears any particular relation to a number of bytes in that stretch.  It
must not assume that the character at a particular memory location can
be retrieved simply by dereferencing the memory location, even if a
character is known to be ASCII or is being compared with an ASCII
character, etc.  Careful coding is required to be Mule clean.  The
biggest work of adding Mule support, in fact, is converting all of the
existing code to be Mule clean.

   Lisp code is mostly unaffected by these concerns.  Text in strings
and buffers appears simply as a sequence of characters regardless of
whether Mule support is present.  The biggest difference with older
versions of Emacs, as well as current versions of GNU Emacs, is that
integers and characters are no longer equivalent, but are separate Lisp
Object types.

Conversion Between Internal and External Representations
--------------------------------------------------------

All text needs to be converted to an external representation before
being sent to a function or file, and all text retrieved from a
function of file needs to be converted to the internal representation.
This conversion needs to happen as close to the source or destination
of the text as possible.  No operations should ever be performed on
text encoded in an external representation other than simple copying,
because no assumptions can reliably be made about the format of this
text.  You cannot assume, for example, that the end of text is
terminated by a null byte. (For example, if the text is Unicode, it
will have many null bytes in it.)  You cannot find the next "slash"
character by searching through the bytes until you find a byte that
looks like a "slash" character, because it might actually be the second
byte of a Kanji character.  Furthermore, all text in the internal
representation must be converted, even if it is known to be completely
ASCII, because the external representation may not be ASCII compatible
(for example, if it is Unicode).

   The place where C code needs to be the most careful is when calling
external API functions.  It is easy to forget that all text passed to or
retrieved from these functions needs to be converted.  This includes
text in structures passed to or retrieved from these functions and all
text that is passed to a callback function that is called by the system.

   Macros are provided to perform conversions to or from external text.
These macros are called TO_EXTERNAL_FORMAT and TO_INTERNAL_FORMAT
respectively.  These macros accept input in various forms, for example,
Lisp strings, buffers, lstreams, raw data, and can return data in
multiple formats, including both `malloc()'ed and `alloca()'ed data.
The use of `alloca()'ed data here is particularly important because, in
general, the returned data will not be used after making the API call,
and as a result, using `alloca()'ed data provides a very cheap and easy
to use method of allocation.

   These macros take a coding system argument which indicates the
nature of the external encoding.  A coding system is an object that
encapsulates the structures of a particular external encoding and the
methods required to convert to and from this encoding.  A facility
exists to create coding system aliases, which in essence gives a single
coding system two different names.  It is effectively used in XEmacs to
provide a layer of abstraction on top of the actual coding systems.
For example, the coding system alias "file-name" points to whichever
coding system is currently used for encoding and decoding file names as
passed to or retrieved from system calls.  In general, the actual
encoding will differ from system to system, and also on the particular
locale that the user is in.  The use of the file-name alias effectively
hides that implementation detail on top of that abstract interface
layer which provides a unified set of coding systems which are
consistent across all operating environments.

   The choice of which coding system to use in a particular conversion
macro requires some thought.  In general, you should choose a
lower-level actual coding system when the very design of the APIs you
are working with call for that particular coding system.  In all other
cases, you should find the least general abstract coding system (i.e.
coding system alias) that applies to your specific situation.  Only use
the most general coding systems, such as native, when there is simply
nothing else that is more appropriate.  By doing things this way, you
allow the user more control over how the encoding actually works,
because the user is free to map the abstracted coding system names onto
to different actual coding systems.

   Some common coding systems are:

`ctext'
     Compound Text, which is the standard encoding under X Windows,
     which is used for clipboard data and possibly other data.  (ctext
     is a coding system of type ISO2022.)

`mswindows-unicode'
     this is used for representing text passed to MS Window API calls
     with arguments that need to be in Unicode format.
     (mswindows-unicode is a coding system of type UTF-16)

`ms-windows-multi-byte'
     this is used for representing text passed to MS Windows API calls
     with arguments that need to be in multi-byte format.  Note that
     there are very few if any examples of such calls.

`mswindows-tstr'
     this is used for representing text passed to any MS Windows API
     calls that declare their argument as LPTSTR, or LPCTSTR.  This is
     the vast majority of system calls and automatically translates
     either to mswindows-unicode or mswindows-multi-byte, depending on
     the presence or absence of the UNICODE preprocessor constant.  (If
     we compile XEmacs with this preprocessor constant, then all API
     calls use Unicode for all text passed to or received from these
     API calls.)

`terminal'
     used for text sent to or read from a text terminal in the absence
     of a more specific coding system (calls to window-system specific
     APIs should use the appropriate window-specific coding system if
     it makes sense to do so.)

`file-name'
     used when specifying the names of files in the absence of a more
     specific encoding, such as ms-windows-tstr.

`native'
     the most general coding system for specifying text passed to system
     calls.  This generally translates to whatever coding system is
     specified by the current locale.  This should only be used when
     none of the coding systems mentioned above are appropriate.

Proper Display of Multilingual Text
-----------------------------------

There are two things required to get this working correctly.  One is
selecting the correct font, and the other is encoding the text according
to the encoding used for that specific font, or the window-system
specific text display API.  Generally each separate character set has a
different font associated with it, which is specified by name and each
font has an associated encoding into which the characters must be
translated.  (this is the case on X Windows, at least; on Windows there
is a more general mechanism).  Both the specific font for a charset and
the encoding of that font are system dependent.  Currently there is a
way of specifying these two properties under X Windows (using the
registry and ccl properties of a character set) but not for other window
systems.  A more general system needs to be implemented to allow these
characteristics to be specified for all Windows systems.

   Another issue is making sure that the necessary fonts for displaying
various character sets are installed on the system.  Currently, XEmacs
provides, on its web site, X Windows fonts for a number of different
character sets that can be installed by users.  This isn't done yet for
Windows, but it should be.

Inputting of Multilingual Text
------------------------------

This is a rather complicated issue because there are many paradigms
defined for inputting multi-lingual text, some of which are specific to
particular languages, and any particular language may have many
different paradigms defined for inputting its text.  These paradigms are
encoded in input methods and there is a standard API for defining an
input method in XEmacs called LEIM, or Library of Emacs Input Methods.
Some of these input methods are written entirely in Elisp, and thus are
system-independent, while others require the aid either of an external
process, or of C level support that ties into a particular
system-specific input method API, for example, XIM under X Windows, or
the active keyboard layout and IME support under Windows.  Currently,
there is no support for any system-specific input methods under
Microsoft Windows, although this will change.


File: internals.info,  Node: Introduction to Multilingual Issues #4,  Next: Character Sets,  Prev: Introduction to Multilingual Issues #3,  Up: Multilingual Support

25.4 Introduction to Multilingual Issues #4
===========================================

The rest of the sections in this chapter consist of yet another
introduction to multilingual issues, duplicating the information in the
previous sections.


File: internals.info,  Node: Character Sets,  Next: Encodings,  Prev: Introduction to Multilingual Issues #4,  Up: Multilingual Support

25.5 Character Sets
===================

A "character set" (or "charset") is an ordered set of characters.  A
particular character in a charset is indexed using one or more
"position codes", which are non-negative integers.  The number of
position codes needed to identify a particular character in a charset
is called the "dimension" of the charset.  In XEmacs/Mule, all charsets
have dimension 1 or 2, and the size of all charsets (except for a few
special cases) is either 94, 96, 94 by 94, or 96 by 96.  The range of
position codes used to index characters from any of these types of
character sets is as follows:

     Charset type            Position code 1         Position code 2
     ------------------------------------------------------------
     94                      33 - 126                N/A
     96                      32 - 127                N/A
     94x94                   33 - 126                33 - 126
     96x96                   32 - 127                32 - 127

   Note that in the above cases position codes do not start at an
expected value such as 0 or 1.  The reason for this will become clear
later.

   For example, Latin-1 is a 96-character charset, and JISX0208 (the
Japanese national character set) is a 94x94-character charset.

   [Note that, although the ranges above define the _valid_ position
codes for a charset, some of the slots in a particular charset may in
fact be empty.  This is the case for JISX0208, for example, where (e.g.)
all the slots whose first position code is in the range 118 - 127 are
empty.]

   There are three charsets that do not follow the above rules.  All of
them have one dimension, and have ranges of position codes as follows:

     Charset name            Position code 1
     ------------------------------------
     ASCII                   0 - 127
     Control-1               0 - 31
     Composite               0 - some large number

   (The upper bound of the position code for composite characters has
not yet been determined, but it will probably be at least 16,383).

   ASCII is the union of two subsidiary character sets: Printing-ASCII
(the printing ASCII character set, consisting of position codes 33 -
126, like for a standard 94-character charset) and Control-ASCII (the
non-printing characters that would appear in a binary file with codes 0
- 32 and 127).

   Control-1 contains the non-printing characters that would appear in a
binary file with codes 128 - 159.

   Composite contains characters that are generated by overstriking one
or more characters from other charsets.

   Note that some characters in ASCII, and all characters in Control-1,
are "control" (non-printing) characters.  These have no printed
representation but instead control some other function of the printing
(e.g. TAB or 8 moves the current character position to the next tab
stop).  All other characters in all charsets are "graphic" (printing)
characters.

   When a binary file is read in, the bytes in the file are assigned to
character sets as follows:

     Bytes           Character set           Range
     --------------------------------------------------
     0 - 127         ASCII                   0 - 127
     128 - 159       Control-1               0 - 31
     160 - 255       Latin-1                 32 - 127

   This is a bit ad-hoc but gets the job done.


File: internals.info,  Node: Encodings,  Next: Internal Mule Encodings,  Prev: Character Sets,  Up: Multilingual Support

25.6 Encodings
==============

An "encoding" is a way of numerically representing characters from one
or more character sets.  If an encoding only encompasses one character
set, then the position codes for the characters in that character set
could be used directly.  This is not possible, however, if more than
one character set is to be used in the encoding.

   For example, the conversion detailed above between bytes in a binary
file and characters is effectively an encoding that encompasses the
three character sets ASCII, Control-1, and Latin-1 in a stream of 8-bit
bytes.

   Thus, an encoding can be viewed as a way of encoding characters from
a specified group of character sets using a stream of bytes, each of
which contains a fixed number of bits (but not necessarily 8, as in the
common usage of "byte").

   Here are descriptions of a couple of common encodings:

* Menu:

* Japanese EUC (Extended Unix Code)::
* JIS7::


File: internals.info,  Node: Japanese EUC (Extended Unix Code),  Next: JIS7,  Prev: Encodings,  Up: Encodings

25.6.1 Japanese EUC (Extended Unix Code)
----------------------------------------

This encompasses the character sets Printing-ASCII, Katakana-JISX0201
(half-width katakana, the right half of JISX0201), Japanese-JISX0208,
and Japanese-JISX0212.

   Note that Printing-ASCII and Katakana-JISX0201 are 94-character
charsets, while Japanese-JISX0208 and Japanese-JISX0212 are
94x94-character charsets.

   The encoding is as follows:

     Character set            Representation (PC=position-code)
     -------------            --------------
     Printing-ASCII           PC1
     Katakana-JISX0201        0x8E       | PC1 + 0x80
     Japanese-JISX0208        PC1 + 0x80 | PC2 + 0x80
     Japanese-JISX0212        PC1 + 0x80 | PC2 + 0x80

   Note that there are other versions of EUC for other Asian languages.
EUC in general is characterized by

  1. row-column encoding,

  2. big-endian (row-first) ordering, and

  3. ASCII compatibility in variable width forms.


File: internals.info,  Node: JIS7,  Prev: Japanese EUC (Extended Unix Code),  Up: Encodings

25.6.2 JIS7
-----------

This encompasses the character sets Printing-ASCII, Latin-JISX0201 (the
left half of JISX0201; this character set is very similar to
Printing-ASCII and is a 94-character charset), Japanese-JISX0208, and
Katakana-JISX0201.  It uses 7-bit bytes.

   Unlike EUC, this is a "modal" encoding, which means that there are
multiple states that the encoding can be in, which affect how the bytes
are to be interpreted.  Special sequences of bytes (called "escape
sequences") are used to change states.

   The encoding is as follows:

     Character set              Representation (PC=position-code)
     -------------              --------------
     Printing-ASCII             PC1
     Latin-JISX0201             PC1
     Katakana-JISX0201          PC1
     Japanese-JISX0208          PC1 | PC2


     Escape sequence   ASCII equivalent   Meaning
     ---------------   ----------------   -------
     0x1B 0x28 0x4A    ESC ( J            invoke Latin-JISX0201
     0x1B 0x28 0x49    ESC ( I            invoke Katakana-JISX0201
     0x1B 0x24 0x42    ESC $ B            invoke Japanese-JISX0208
     0x1B 0x28 0x42    ESC ( B            invoke Printing-ASCII

   Initially, Printing-ASCII is invoked.


File: internals.info,  Node: Internal Mule Encodings,  Next: Byte/Character Types; Buffer Positions; Other Typedefs,  Prev: Encodings,  Up: Multilingual Support

25.7 Internal Mule Encodings
============================

In XEmacs/Mule, each character set is assigned a unique number, called a
"leading byte".  This is used in the encodings of a character.  Leading
bytes are in the range 0x80 - 0xFF (except for ASCII, which has a
leading byte of 0), although some leading bytes are reserved.

   Charsets whose leading byte is in the range 0x80 - 0x9F are called
"official" and are used for built-in charsets.  Other charsets are
called "private" and have leading bytes in the range 0xA0 - 0xFF; these
are user-defined charsets.

   More specifically:

     Character set                Leading byte
     -------------                ------------
     ASCII                        0 (0x7F in arrays indexed by leading byte)
     Composite                    0x8D
     Dimension-1 Official         0x80 - 0x8C/0x8D
                                    (0x8E is free)
     Control                      0x8F
     Dimension-2 Official         0x90 - 0x99
                                    (0x9A - 0x9D are free)
     Dimension-1 Private Marker   0x9E
     Dimension-2 Private Marker   0x9F
     Dimension-1 Private          0xA0 - 0xEF
     Dimension-2 Private          0xF0 - 0xFF

   There are two internal encodings for characters in XEmacs/Mule.  One
is called "string encoding" and is an 8-bit encoding that is used for
representing characters in a buffer or string.  It uses 1 to 4 bytes per
character.  The other is called "character encoding" and is a 19-bit
encoding that is used for representing characters individually in a
variable.

   (In the following descriptions, we'll ignore composite characters for
the moment.  We also give a general (structural) overview first,
followed later by the exact details.)

* Menu:

* Internal String Encoding::
* Internal Character Encoding::


File: internals.info,  Node: Internal String Encoding,  Next: Internal Character Encoding,  Prev: Internal Mule Encodings,  Up: Internal Mule Encodings

25.7.1 Internal String Encoding
-------------------------------

ASCII characters are encoded using their position code directly.  Other
characters are encoded using their leading byte followed by their
position code(s) with the high bit set.  Characters in private character
sets have their leading byte prefixed with a "leading byte prefix",
which is either 0x9E or 0x9F. (No character sets are ever assigned these
leading bytes.) Specifically:

     Character set           Encoding (PC=position-code, LB=leading-byte)
     -------------           --------
     ASCII                   PC-1 |
     Control-1               LB   |  PC1 + 0xA0 |
     Dimension-1 official    LB   |  PC1 + 0x80 |
     Dimension-1 private     0x9E |  LB         | PC1 + 0x80 |
     Dimension-2 official    LB   |  PC1 + 0x80 | PC2 + 0x80 |
     Dimension-2 private     0x9F |  LB         | PC1 + 0x80 | PC2 + 0x80

   The basic characteristic of this encoding is that the first byte of
all characters is in the range 0x00 - 0x9F, and the second and
following bytes of all characters is in the range 0xA0 - 0xFF.  This
means that it is impossible to get out of sync, or more specifically:

  1. Given any byte position, the beginning of the character it is
     within can be determined in constant time.

  2. Given any byte position at the beginning of a character, the
     beginning of the next character can be determined in constant time.

  3. Given any byte position at the beginning of a character, the
     beginning of the previous character can be determined in constant
     time.

  4. Textual searches can simply treat encoded strings as if they were
     encoded in a one-byte-per-character fashion rather than the actual
     multi-byte encoding.

   None of the standard non-modal encodings meet all of these
conditions.  For example, EUC satisfies only (2) and (3), while
Shift-JIS and Big5 (not yet described) satisfy only (2). (All non-modal
encodings must satisfy (2), in order to be unambiguous.)


File: internals.info,  Node: Internal Character Encoding,  Prev: Internal String Encoding,  Up: Internal Mule Encodings

25.7.2 Internal Character Encoding
----------------------------------

One 19-bit word represents a single character.  The word is separated
into three fields:

     Bit number:     18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
                     <------------> <------------------> <------------------>
     Field:                1                  2                    3

   Note that fields 2 and 3 hold 7 bits each, while field 1 holds 5
bits.

     Character set           Field 1         Field 2         Field 3
     -------------           -------         -------         -------
     ASCII                      0               0              PC1
        range:                                                   (00 - 7F)
     Control-1                  0               1              PC1
        range:                                                   (00 - 1F)
     Dimension-1 official       0            LB - 0x7F         PC1
        range:                                    (01 - 0D)      (20 - 7F)
     Dimension-1 private        0            LB - 0x80         PC1
        range:                                    (20 - 6F)      (20 - 7F)
     Dimension-2 official    LB - 0x8F         PC1             PC2
        range:                    (01 - 0A)       (20 - 7F)      (20 - 7F)
     Dimension-2 private     LB - 0xE1         PC1             PC2
        range:                    (0F - 1E)       (20 - 7F)      (20 - 7F)
     Composite                 0x1F             ?               ?

   Note that character codes 0 - 255 are the same as the "binary
encoding" described above.

   Most of the code in XEmacs knows nothing of the representation of a
character other than that values 0 - 255 represent ASCII, Control 1,
and Latin 1.

   *WARNING WARNING WARNING*: The Boyer-Moore code in `search.c', and
the code in `search_buffer()' that determines whether that code can be
used, knows that "field 3" in a character always corresponds to the
last byte in the textual representation of the character. (This is
important because the Boyer-Moore algorithm works by looking at the
last byte of the search string and &&#### finish this.


File: internals.info,  Node: Byte/Character Types; Buffer Positions; Other Typedefs,  Next: Internal Text API's,  Prev: Internal Mule Encodings,  Up: Multilingual Support

25.8 Byte/Character Types; Buffer Positions; Other Typedefs
===========================================================

* Menu:

* Byte Types::
* Different Ways of Seeing Internal Text::
* Buffer Positions::
* Other Typedefs::
* Usage of the Various Representations::
* Working With the Various Representations::


File: internals.info,  Node: Byte Types,  Next: Different Ways of Seeing Internal Text,  Prev: Byte/Character Types; Buffer Positions; Other Typedefs,  Up: Byte/Character Types; Buffer Positions; Other Typedefs

25.8.1 Byte Types
-----------------

Stuff pointed to by a char * or unsigned char * will nearly always be
one of the following types:

   - a) [Ibyte] pointer to internally-formatted text

   - b) [Extbyte] pointer to text in some external format, which can be
                 defined as all formats other than the internal one

   - c) [Ascbyte] pure ASCII text

   - d) [Binbyte] binary data that is not meant to be interpreted as
     text

   - e) [Rawbyte] general data in memory, where we don't care about
     whether              it's text or binary

   - f) [Boolbyte] a zero or a one

   - g) [Bitbyte] a byte used for bit fields

   - h) [Chbyte] null-semantics `char *'; used when casting an argument
     to             an external API where the the other types may not be
                appropriate

   Types (b), (c), (f) and (h) are defined as `char', while the others
are `unsigned char'.  This is for maximum safety (signed characters are
dangerous to work with) while maintaining as much compatibility with
external API's and string constants as possible.

   We also provide versions of the above types defined with different
underlying C types, for API compatibility.  These use the following
prefixes:

     C = plain char, when the base type is unsigned
     U = unsigned
     S = signed

   (Formerly I had a comment saying that type (e) "should be replaced
with void *".  However, there are in fact many places where an unsigned
char * might be used - e.g. for ease in pointer computation, since void
* doesn't allow this, and for compatibility with external API's.)

   Note that these typedefs are purely for documentation purposes; from
the C code's perspective, they are exactly equivalent to `char *',
`unsigned char *', etc., so you can freely use them with library
functions declared as such.

   Using these more specific types rather than the general ones helps
avoid the confusions that occur when the semantics of a char * or
unsigned char * argument being studied are unclear.  Furthermore, by
requiring that ALL uses of `char' be replaced with some other type as
part of the Mule-ization process, we can use a search for `char' as a
way of finding code that has not been properly Mule-ized yet.


File: internals.info,  Node: Different Ways of Seeing Internal Text,  Next: Buffer Positions,  Prev: Byte Types,  Up: Byte/Character Types; Buffer Positions; Other Typedefs

25.8.2 Different Ways of Seeing Internal Text
---------------------------------------------

There are various ways of representing internal text.  The two primary
ways are as an "array" of individual characters; the other is as a
"stream" of bytes.  In the ASCII world, where there are only 255
characters at most, things are easy because each character fits into a
byte.  In general, however, this is not true - see the above discussion
of characters vs. encodings.

   In some cases, it's also important to distinguish between a stream
representation as a series of bytes and as a series of textual units.
This is particularly important wrt Unicode.  The UTF-16 representation
(sometimes referred to, rather sloppily, as simply the "Unicode" format)
represents text as a series of 16-bit units.  Mostly, each unit
corresponds to a single character, but not necessarily, as characters
outside of the range 0-65535 (the BMP or "Basic Multilingual Plane" of
Unicode) require two 16-bit units, through the mechanism of
"surrogates".  When a series of 16-bit units is serialized into a byte
stream, there are at least two possible representations, little-endian
and big-endian, and which one is used may depend on the native format of
16-bit integers in the CPU of the machine that XEmacs is running on.
(Similarly, UTF-32 is logically a representation with 32-bit textual
units.)

   Specifically:

   - UTF-8 has 1-byte (8-bit) units.

   - UTF-16 has 2-byte (16-bit) units.

   - UTF-32 has 4-byte (32-bit) units.

   - XEmacs-internal encoding (the old "Mule" encoding) has 1-byte
     (8-bit) units.

   - UTF-7 technically has 7-bit units that are within the "mail-safe"
     range (ASCII 32 - 126 plus a few control characters), but normally
     is encoded in an 8-bit stream. (UTF-7 is also a modal encoding,
     since it has a normal mode where printable ASCII characters
     represent themselves and a shifted mode, introduced with a plus
     sign, where a base-64 encoding is used.)

   - UTF-5 technically has 7-bit units (normally encoded in an 8-bit
     stream, like UTF-7), but only uses uppercase A-V and 0-9, and only
     encodes 4 bits worth of data per character.  UTF-5 is meant for
     encoding Unicode inside of DNS names.

   Thus, we can imagine three levels in the representation of texual
data:

     series of characters -> series of textual units -> series of bytes
            [Ichar]                 [Itext]                 [Ibyte]

   XEmacs has three corresponding typedefs:

   - An Ichar is an integer (at least 32-bit), representing a 31-bit
     character.

   - An Itext is an unsigned value, either 8, 16 or 32 bits, depending
     on the nature of the internal representation, and corresponding to
     a single textual unit.

   - An Ibyte is an `unsigned char', representing a single byte in a
     textual byte stream.

   Internal text in stream format can be simultaneously viewed as either
`Itext *' or `Ibyte *'.  The `Ibyte *' representation is convenient for
copying data from one place to another, because such routines usually
expect byte counts.  However, `Itext *' is much better for actually
working with the data.

   From a text-unit perspective, units 0 through 127 will always be
ASCII compatible, and data in Lisp strings (and other textual data
generated as a whole, e.g. from external conversion) will be followed
by a null-unit terminator.  From an `Ibyte *' perspective, however, the
encoding is only ASCII-compatible if it uses 1-byte units.

   Similarly to the different text representations, three integral count
types exist - Charcount, Textcount and Bytecount.

   NOTE: Despite the presence of the terminator, internal text itself
can have nulls in it! (Null text units, not just the null bytes present
in any UTF-16 encoding.) The terminator is present because in many cases
internal text is passed to routines that will ultimately pass the text
to library functions that cannot handle embedded nulls, e.g. functions
manipulating filenames, and it is a real hassle to have to pass the
length around constantly.  But this can lead to sloppy coding!  We need
to be careful about watching for nulls in places that are important,
e.g. manipulating string objects or passing data to/from the clipboard.

`Ibyte'
     The data in a buffer or string is logically made up of Ibyte
     objects, where a Ibyte takes up the same amount of space as a
     char. (It is declared differently, though, to catch invalid
     usages.) Strings stored using Ibytes are said to be in "internal
     format".  The important characteristics of internal format are

        - ASCII characters are represented as a single Ibyte, in the
          range 0 - 0x7f.

        - All other characters are represented as a Ibyte in the range
          0x80 - 0x9f followed by one or more Ibytes in the range 0xa0
          to 0xff.

     This leads to a number of desirable properties:

        - Given the position of the beginning of a character, you can
          find the beginning of the next or previous character in
          constant time.

        - When searching for a substring or an ASCII character within
          the string, you need merely use standard searching routines.

`Itext'
     #### Document me.

`Ichar'
     This typedef represents a single Emacs character, which can be
     ASCII, ISO-8859, or some extended character, as would typically be
     used for Kanji.  Note that the representation of a character as an
     Ichar is *not* the same as the representation of that same
     character in a string; thus, you cannot do the standard C trick of
     passing a pointer to a character to a function that expects a
     string.

     An Ichar takes up 19 bits of representation and (for code
     compatibility and such) is compatible with an int.  This
     representation is visible on the Lisp level.  The important
     characteristics of the Ichar representation are

        - values 0x00 - 0x7f represent ASCII.

        - values 0x80 - 0xff represent the right half of ISO-8859-1.

        - values 0x100 and up represent all other characters.

     This means that Ichar values are upwardly compatible with the
     standard 8-bit representation of ASCII/ISO-8859-1.

`Extbyte'
     Strings that go in or out of Emacs are in "external format",
     typedef'ed as an array of char or a char *.  There is more than
     one external format (JIS, EUC, etc.) but they all have similar
     properties.  They are modal encodings, which is to say that the
     meaning of particular bytes is not fixed but depends on what
     "mode" the string is currently in (e.g. bytes in the range 0 -
     0x7f might be interpreted as ASCII, or as Hiragana, or as 2-byte
     Kanji, depending on the current mode).  The mode starts out in
     ASCII/ISO-8859-1 and is switched using escape sequences - for
     example, in the JIS encoding, 'ESC $ B' switches to a mode where
     pairs of bytes in the range 0 - 0x7f are interpreted as Kanji
     characters.

     External-formatted data is generally desirable for passing data
     between programs because it is upwardly compatible with standard
     ASCII/ISO-8859-1 strings and may require less space than internal
     encodings such as the one described above.  In addition, some
     encodings (e.g. JIS) keep all characters (except the ESC used to
     switch modes) in the printing ASCII range 0x20 - 0x7e, which
     results in a much higher probability that the data will avoid
     being garbled in transmission.  Externally-formatted data is
     generally not very convenient to work with, however, and for this
     reason is usually converted to internal format before any work is
     done on the string.

     NOTE: filenames need to be in external format so that ISO-8859-1
     characters come out correctly.


File: internals.info,  Node: Buffer Positions,  Next: Other Typedefs,  Prev: Different Ways of Seeing Internal Text,  Up: Byte/Character Types; Buffer Positions; Other Typedefs

25.8.3 Buffer Positions
-----------------------

There are three possible ways to specify positions in a buffer.  All of
these are one-based: the beginning of the buffer is position or index
1, and 0 is not a valid position.

   As a "buffer position" (typedef Charbpos):

   This is an index specifying an offset in characters from the
beginning of the buffer.  Note that buffer positions are    logically
*between* characters, not on a character.  The    difference between
two buffer positions specifies the number of    characters between
those positions.  Buffer positions are the    only kind of position
externally visible to the user.

   As a "byte index" (typedef Bytebpos):

   This is an index over the bytes used to represent the characters
in the buffer.  If there is no Mule support, this is identical    to a
buffer position, because each character is represented    using one
byte.  However, with Mule support, many characters    require two or
more bytes for their representation, and so a    byte index may be
greater than the corresponding buffer    position.

   As a "memory index" (typedef Membpos):

   This is the byte index adjusted for the gap.  For positions
before the gap, this is identical to the byte index.  For    positions
after the gap, this is the byte index plus the gap    size.  There are
two possible memory indices for the gap    position; the memory index
at the beginning of the gap should    always be used, except in code
that deals with manipulating the    gap, where both indices may be
seen.  The address of the    character "at" (i.e. following) a
particular position can be    obtained from the formula

   buffer_start_address + memory_index(position) - 1

   except in the case of characters at the gap position.


File: internals.info,  Node: Other Typedefs,  Next: Usage of the Various Representations,  Prev: Buffer Positions,  Up: Byte/Character Types; Buffer Positions; Other Typedefs

25.8.4 Other Typedefs
---------------------

Charcount:    ---------      This typedef represents a count of
characters, such as      a character offset into a string or the number
of      characters between two positions in a buffer.  The
difference between two Charbpos's is a Charcount, and      character
positions in a string are represented using      a Charcount.

   Textcount:    ---------      #### Document me.

   Bytecount:    ---------      Similar to a Charcount but represents a
count of bytes.       The difference between two Bytebpos's is a
Bytecount.


File: internals.info,  Node: Usage of the Various Representations,  Next: Working With the Various Representations,  Prev: Other Typedefs,  Up: Byte/Character Types; Buffer Positions; Other Typedefs

25.8.5 Usage of the Various Representations
-------------------------------------------

Memory indices are used in low-level functions in insdel.c and for
extent endpoints and marker positions.  The reason for this is that
this way, the extents and markers don't need to be updated for most
insertions, which merely shrink the gap and don't move any characters
around in memory.

   (The beginning-of-gap memory index simplifies insertions w.r.t.
markers, because text usually gets inserted after markers.  For
extents, it is merely for consistency, because text can get inserted
either before or after an extent's endpoint depending on the
open/closedness of the endpoint.)

   Byte indices are used in other code that needs to be fast, such as
the searching, redisplay, and extent-manipulation code.

   Buffer positions are used in all other code.  This is because this
representation is easiest to work with (especially since Lisp code
always uses buffer positions), necessitates the fewest changes to
existing code, and is the safest (e.g. if the text gets shifted
underneath a buffer position, it will still point to a character; if
text is shifted under a byte index, it might point to the middle of a
character, which would be bad).

   Similarly, Charcounts are used in all code that deals with strings
except for code that needs to be fast, which used Bytecounts.

   Strings are always passed around internally using internal format.
Conversions between external format are performed at the time that the
data goes in or out of Emacs.


File: internals.info,  Node: Working With the Various Representations,  Prev: Usage of the Various Representations,  Up: Byte/Character Types; Buffer Positions; Other Typedefs

25.8.6 Working With the Various Representations
-----------------------------------------------

We write things this way because it's very important the
MAX_BYTEBPOS_GAP_SIZE_3 is a multiple of 3. (As it happens, 65535 is a
multiple of 3, but this may not always be the case. #### unfinished


File: internals.info,  Node: Internal Text API's,  Next: Coding for Mule,  Prev: Byte/Character Types; Buffer Positions; Other Typedefs,  Up: Multilingual Support

25.9 Internal Text API's
========================

*NOTE*: The most current documentation for these API's is in `text.h'.
In case of error, assume that file is correct and this one wrong.

* Menu:

* Basic internal-format API's::
* The DFC API::
* The Eistring API::


File: internals.info,  Node: Basic internal-format API's,  Next: The DFC API,  Prev: Internal Text API's,  Up: Internal Text API's

25.9.1 Basic internal-format API's
----------------------------------

These are simple functions and macros to convert between text
representation and characters, move forward and back in text, etc.

   #### Finish the rest of this.

   Use the following functions/macros on contiguous text in any of the
internal formats.  Those that take a format arg work on all internal
formats; the others work only on the default (variable-width under Mule)
format.  If the text you're operating on is known to come from a buffer,
use the buffer-level functions in buffer.h, which automatically know the
correct format and handle the gap.

   Some terminology:

   "itext" appearing in the macros means "internal-format text" - type
`Ibyte *'.  Operations on such pointers themselves, rather than on the
text being pointed to, have "itext" instead of "itext" in the macro
name.  "ichar" in the macro names means an Ichar - the representation
of a character as a single integer rather than a series of bytes, as
part of "itext".  Many of the macros below are for converting between
the two representations of characters.

   Note also that we try to consistently distinguish between an "Ichar"
and a Lisp character.  Stuff working with Lisp characters often just
says "char", so we consistently use "Ichar" when that's what we're
working with.


File: internals.info,  Node: The DFC API,  Next: The Eistring API,  Prev: Basic internal-format API's,  Up: Internal Text API's

25.9.2 The DFC API
------------------

This is for conversion between internal and external text.  Note that
there is also the "new DFC" API, which *returns* a pointer to the
converted text (in alloca space), rather than storing it into a
variable.

   The macros below are used for converting data between different
formats.  Generally, the data is textual, and the formats are related to
internationalization (e.g. converting between internal-format text and
UTF-8) - but the mechanism is general, and could be used for anything,
e.g. decoding gzipped data.

   In general, conversion involves a source of data, a sink, the
existing format of the source data, and the desired format of the sink.
The macros below, however, always require that either the source or
sink is internal-format text.  Therefore, in practice the conversions
below involve source, sink, an external format (specified by a coding
system), and the direction of conversion (internal->external or
vice-versa).

   Sources and sinks can be raw data (sized or unsized - when unsized,
input data is assumed to be null-terminated [double null-terminated for
Unicode-format data], and on output the length is not stored anywhere),
Lisp strings, Lisp buffers, lstreams, and opaque data objects.  When the
output is raw data, the result can be allocated either with `alloca()'
or `malloc()'. (There is currently no provision for writing into a fixed
buffer.  If you want this, use `alloca()' output and then copy the data
- but be careful with the size!  Unless you are very sure of the
encoding being used, upper bounds for the size are not in general
computable.)  The obvious restrictions on source and sink types apply
(e.g. Lisp strings are a source and sink only for internal data).

   All raw data outputted will contain an extra null byte (two bytes for
Unicode - currently, in fact, all output data, whether internal or
external, is double-null-terminated, but you can't count on this; see
below).  This means that enough space is allocated to contain the extra
nulls; however, these nulls are not reflected in the returned output
size.

   The most basic macros are TO_EXTERNAL_FORMAT and TO_INTERNAL_FORMAT.
These can be used to convert between any kinds of sources or sinks.
However, 99% of conversions involve raw data or Lisp strings as both
source and sink, and usually data is output as `alloca()' rather than
`malloc()'.  For this reason, convenience macros are defined for many
types of conversions involving raw data and/or Lisp strings, especially
when the output is an `alloca()'ed string. (When the destination is a
Lisp_String, there are other functions that should be used instead -
`build_ext_string()' and `make_ext_string()', for example.) The
convenience macros are of two types - the older kind that store the
result into a specified variable, and the newer kind that return the
result.  The newer kind of macros don't exist when the output is sized
data, because that would have two return values.  NOTE: All convenience
macros are ultimately defined in terms of TO_EXTERNAL_FORMAT and
TO_INTERNAL_FORMAT.  Thus, any comments below about the workings of
these macros also apply to all convenience macros.

     TO_EXTERNAL_FORMAT (source_type, source, sink_type, sink, codesys)
     TO_INTERNAL_FORMAT (source_type, source, sink_type, sink, codesys)

   Typical use is

        TO_EXTERNAL_FORMAT (LISP_STRING, str, C_STRING_MALLOC, ptr, Qfile_name);

   which means that the contents of the lisp string STR are written to
a malloc'ed memory area which will be pointed to by PTR, after the
function returns.  The conversion will be done using the `file-name'
coding system (which will be controlled by the user indirectly by
setting or binding the variable `file-name-coding-system').

   Some sources and sinks require two C variables to specify.  We use
some preprocessor magic to allow different source and sink types, and
even different numbers of arguments to specify different types of
sources and sinks.

   So we can have a call that looks like

        TO_INTERNAL_FORMAT (DATA, (ptr, len),
                            MALLOC, (ptr, len),
                            coding_system);

   The parenthesized argument pairs are required to make the
preprocessor magic work.

   NOTE: GC is inhibited during the entire operation of these macros.
This is because frequently the data to be converted comes from strings
but gets passed in as just DATA, and GC may move around the string
data.  If we didn't inhibit GC, there'd have to be a lot of messy
recoding, alloca-copying of strings and other annoying stuff.

   The source or sink can be specified in one of these ways:

     DATA,   (ptr, len),    // input data is a fixed buffer of size len
     ALLOCA, (ptr, len),    // output data is in a `ALLOCA()'ed buffer of size len
     MALLOC, (ptr, len),    // output data is in a `malloc()'ed buffer of size len
     C_STRING_ALLOCA, ptr,  // equivalent to ALLOCA (ptr, len_ignored) on output
     C_STRING_MALLOC, ptr,  // equivalent to MALLOC (ptr, len_ignored) on output
     C_STRING,     ptr,     // equivalent to DATA, (ptr, strlen/wcslen (ptr))
                            // on input (the Unicode version is used when correct)
     LISP_STRING,  string,  // input or output is a Lisp_Object of type string
     LISP_BUFFER,  buffer,  // output is written to (point) in lisp buffer
     LISP_LSTREAM, lstream, // input or output is a Lisp_Object of type lstream
     LISP_OPAQUE,  object,  // input or output is a Lisp_Object of type opaque

   When specifying the sink, use lvalues, since the macro will assign
to them, except when the sink is an lstream or a lisp buffer.

   For the sink types `ALLOCA' and `C_STRING_ALLOCA', the resulting
text is stored in a stack-allocated buffer, which is automatically
freed on returning from the function.  However, the sink types `MALLOC'
and `C_STRING_MALLOC' return `xmalloc()'ed memory.  The caller is
responsible for freeing this memory using `xfree()'.

   The macros accept the kinds of sources and sinks appropriate for
internal and external data representation.  See the type_checking_assert
macros below for the actual allowed types.

   Since some sources and sinks use one argument (a Lisp_Object) to
specify them, while others take a (pointer, length) pair, we use some C
preprocessor trickery to allow pair arguments to be specified by
parenthesizing them, as in the examples above.

   Anything prefixed by dfc_ (`data format conversion') is private.
They are only used to implement these macros.

   [[Using C_STRING* is appropriate for using with external APIs that
take null-terminated strings.  For internal data, we should try to be
'\0'-clean - i.e. allow arbitrary data to contain embedded '\0'.

   Sometime in the future we might allow output to C_STRING_ALLOCA or
C_STRING_MALLOC _only_ with `TO_EXTERNAL_FORMAT()', not
`TO_INTERNAL_FORMAT()'.]]

   The above comments are not true.  Frequently (most of the time, in
fact), external strings come as zero-terminated entities, where the
zero-termination is the only way to find out the length.  Even in cases
where you can get the length, most of the time the system will still
use the null to signal the end of the string, and there will still be
no way to either send in or receive a string with embedded nulls.  In
such situations, it's pointless to track the length because null bytes
can never be in the string.  We have a lot of operations that make it
easy to operate on zero-terminated strings, and forcing the user the
deal with the length everywhere would only make the code uglier and
more complicated, for no gain. -ben

   There is no problem using the same lvalue for source and sink.

   Also, when pointers are required, the code (currently at least) is
lax and allows any pointer types, either in the source or the sink.
This makes it possible, e.g., to deal with internal format data held in
char *'s or external format data held in WCHAR * (i.e. Unicode).

   Finally, whenever storage allocation is called for, extra space is
allocated for a terminating zero, and such a zero is stored in the
appropriate place, regardless of whether the source data was specified
using a length or was specified as zero-terminated.  This allows you to
freely pass the resulting data, no matter how obtained, to a routine
that expects zero termination (modulo, of course, that any embedded
zeros in the resulting text will cause truncation).  In fact, currently
two embedded zeros are allocated and stored after the data result.
This is to allow for the possibility of storing a Unicode value on
output, which needs the two zeros.  Currently, however, the two zeros
are stored regardless of whether the conversion is internal or external
and regardless of whether the external coding system is in fact
Unicode.  This behavior may change in the future, and you cannot rely
on this - the most you can rely on is that sink data in Unicode format
will have two terminating nulls, which combine to form one Unicode null
character.

   NOTE: You might ask, why are these not written as functions that
*RETURN* the converted string, since that would allow them to be used
much more conveniently, without having to constantly declare temporary
variables?  The answer is that in fact I originally did write the
routines that way, but that required either

   * (a) calling `alloca()' inside of a function call, or

   * (b) using expressions separated by commas and a global temporary
     variable, or

   * (c) using the GCC extension ({ ... }).

   Turned out that all of the above had bugs, all caused by GCC (hence
the comments about "those GCC wankers" and "ream gcc up the ass").  As
for (a), some versions of GCC (especially on Intel platforms), which had
buggy implementations of `alloca()' that couldn't handle being called
inside of a function call - they just decremented the stack right in the
middle of pushing args.  Oops, crash with stack trashing, very bad.  (b)
was an attempt to fix (a), and that led to further GCC crashes, esp.
when you had two such calls in a single subexpression, because GCC
couldn't be counted upon to follow even a minimally reasonable order of
execution.  True, you can't count on one argument being evaluated
before another, but GCC would actually interleave them so that the temp
var got stomped on by one while the other was accessing it.  So I tried
(c), which was problematic because that GCC extension has more bugs in
it than a termite's nest.

   So reluctantly I converted to the current way.  Now, that was awhile
ago (c. 1994), and it appears that the bug involving alloca in function
calls has long since been fixed.  More recently, I defined the new-dfc
routines down below, which DO allow exactly such convenience of
returning your args rather than store them in temp variables, and I
also wrote a configure check to see whether `alloca()' causes crashes
inside of function calls, and if so use the portable `alloca()'
implementation in alloca.c.  If you define TEST_NEW_DFC, the old
routines get written in terms of the new ones, and I've had a beta put
out with this on and it appeared to this appears to cause no problems -
so we should consider switching, and feel no compunctions about writing
further such function- like `alloca()' routines in lieu of
statement-like ones. -ben


File: internals.info,  Node: The Eistring API,  Prev: The DFC API,  Up: Internal Text API's

25.9.3 The Eistring API
-----------------------

(This API is currently under-used) When doing simple things with
internal text, the basic internal-format API's are enough.  But to do
things like delete or replace a substring, concatenate various strings,
etc. is difficult to do cleanly because of the allocation issues.  The
Eistring API is designed to deal with this, and provides a clean way of
modifying and building up internal text. (Note that the former lack of
this API has meant that some code uses Lisp strings to do similar
manipulations, resulting in excess garbage and increased garbage
collection.)

   NOTE: The Eistring API is (or should be) Mule-correct even without
an ASCII-compatible internal representation.

     #### NOTE: This is a work in progress.  Neither the API nor especially
     the implementation is finished.

     NOTE: An Eistring is a structure that makes it easy to work with
     internally-formatted strings of data.  It provides operations similar
     in feel to the standard `strcpy()', `strcat()', `strlen()', etc., but

     (a) it is Mule-correct
     (b) it does dynamic allocation so you never have to worry about size
         restrictions
     (c) it comes in an `ALLOCA()' variety (all allocation is stack-local,
         so there is no need to explicitly clean up) as well as a `malloc()'
         variety
     (d) it knows its own length, so it does not suffer from standard null
         byte brain-damage -- but it null-terminates the data anyway, so
         it can be passed to standard routines
     (e) it provides a much more powerful set of operations and knows about
         all the standard places where string data might reside: Lisp_Objects,
         other Eistrings, Ibyte * data with or without an explicit length,
         ASCII strings, Ichars, etc.
     (f) it provides easy operations to convert to/from externally-formatted
         data, and is easier to use than the standard TO_INTERNAL_FORMAT
         and TO_EXTERNAL_FORMAT macros. (An Eistring can store both the internal
         and external version of its data, but the external version is only
         initialized or changed when you call `eito_external()'.)

     The idea is to make it as easy to write Mule-correct string manipulation
     code as it is to write normal string manipulation code.  We also make
     the API sufficiently general that it can handle multiple internal data
     formats (e.g. some fixed-width optimizing formats and a default variable
     width format) and allows for *ANY* data format we might choose in the
     future for the default format, including UCS2. (In other words, we can't
     assume that the internal format is ASCII-compatible and we can't assume
     it doesn't have embedded null bytes.  We do assume, however, that any
     chosen format will have the concept of null-termination.) All of this is
     hidden from the user.

     #### It is really too bad that we don't have a real object-oriented
     language, or at least a language with polymorphism!


      **********************************************
      *                 Declaration                *
      **********************************************

     To declare an Eistring, either put one of the following in the local
     variable section:

     DECLARE_EISTRING (name);
          Declare a new Eistring and initialize it to the empy string.  This
          is a standard local variable declaration and can go anywhere in the
          variable declaration section.  NAME itself is declared as an
          Eistring *, and its storage declared on the stack.

     DECLARE_EISTRING_MALLOC (name);
          Declare and initialize a new Eistring, which uses `malloc()'ed
          instead of `ALLOCA()'ed data.  This is a standard local variable
          declaration and can go anywhere in the variable declaration
          section.  Once you initialize the Eistring, you will have to free
          it using `eifree()' to avoid memory leaks.  You will need to use this
          form if you are passing an Eistring to any function that modifies
          it (otherwise, the modified data may be in stack space and get
          overwritten when the function returns).

     or use

     Eistring ei;
     void eiinit (Eistring *ei);
     void eiinit_malloc (Eistring *einame);
          If you need to put an Eistring elsewhere than in a local variable
          declaration (e.g. in a structure), declare it as shown and then
          call one of the init macros.

     Also note:

     void eifree (Eistring *ei);
          If you declared an Eistring to use `malloc()' to hold its data,
          or converted it to the heap using `eito_malloc()', then this
          releases any data in it and afterwards resets the Eistring
          using `eiinit_malloc()'.  Otherwise, it just resets the Eistring
          using `eiinit()'.


      **********************************************
      *                 Conventions                *
      **********************************************

      - The names of the functions have been chosen, where possible, to
        match the names of `str*()' functions in the standard C API.
      -


      **********************************************
      *               Initialization               *
      **********************************************

     void eireset (Eistring *eistr);
          Initialize the Eistring to the empty string.

     void eicpy_* (Eistring *eistr, ...);
          Initialize the Eistring from somewhere:

     void eicpy_ei (Eistring *eistr, Eistring *eistr2);
          ... from another Eistring.
     void eicpy_lstr (Eistring *eistr, Lisp_Object lisp_string);
          ... from a Lisp_Object string.
     void eicpy_ch (Eistring *eistr, Ichar ch);
          ... from an Ichar (this can be a conventional C character).

     void eicpy_lstr_off (Eistring *eistr, Lisp_Object lisp_string,
                          Bytecount off, Charcount charoff,
                          Bytecount len, Charcount charlen);
          ... from a section of a Lisp_Object string.
     void eicpy_lbuf (Eistring *eistr, Lisp_Object lisp_buf,
          	    Bytecount off, Charcount charoff,
          	    Bytecount len, Charcount charlen);
          ... from a section of a Lisp_Object buffer.
     void eicpy_raw (Eistring *eistr, const Ibyte *data, Bytecount len);
          ... from raw internal-format data in the default internal format.
     void eicpy_rawz (Eistring *eistr, const Ibyte *data);
          ... from raw internal-format data in the default internal format
          that is "null-terminated" (the meaning of this depends on the nature
          of the default internal format).
     void eicpy_raw_fmt (Eistring *eistr, const Ibyte *data, Bytecount len,
                         Internal_Format intfmt, Lisp_Object object);
          ... from raw internal-format data in the specified format.
     void eicpy_rawz_fmt (Eistring *eistr, const Ibyte *data,
                          Internal_Format intfmt, Lisp_Object object);
          ... from raw internal-format data in the specified format that is
          "null-terminated" (the meaning of this depends on the nature of
          the specific format).
     void eicpy_c (Eistring *eistr, const Ascbyte *c_string);
          ... from an ASCII null-terminated string.  Non-ASCII characters in
          the string are *ILLEGAL* (read `abort()' with error-checking defined).
     void eicpy_c_len (Eistring *eistr, const Ascbyte *c_string, len);
          ... from an ASCII string, with length specified.  Non-ASCII characters
          in the string are *ILLEGAL* (read `abort()' with error-checking defined).
     void eicpy_ext (Eistring *eistr, const Extbyte *extdata,
                     Lisp_Object codesys);
          ... from external null-terminated data, with coding system specified.
     void eicpy_ext_len (Eistring *eistr, const Extbyte *extdata,
                         Bytecount extlen, Lisp_Object codesys);
          ... from external data, with length and coding system specified.
     void eicpy_lstream (Eistring *eistr, Lisp_Object lstream);
          ... from an lstream; reads data till eof.  Data must be in default
          internal format; otherwise, interpose a decoding lstream.


      **********************************************
      *    Getting the data out of the Eistring    *
      **********************************************

     Ibyte *eidata (Eistring *eistr);
          Return a pointer to the raw data in an Eistring.  This is NOT
          a copy.

     Lisp_Object eimake_string (Eistring *eistr);
          Make a Lisp string out of the Eistring.

     Lisp_Object eimake_string_off (Eistring *eistr,
                                    Bytecount off, Charcount charoff,
          			  Bytecount len, Charcount charlen);
          Make a Lisp string out of a section of the Eistring.

     void eicpyout_alloca (Eistring *eistr, LVALUE: Ibyte *ptr_out,
                           LVALUE: Bytecount len_out);
          Make an `ALLOCA()' copy of the data in the Eistring, using the
          default internal format.  Due to the nature of `ALLOCA()', this
          must be a macro, with all lvalues passed in as parameters.
          (More specifically, not all compilers correctly handle using
          `ALLOCA()' as the argument to a function call -- GCC on x86
          didn't used to, for example.) A pointer to the `ALLOCA()'ed data
          is stored in PTR_OUT, and the length of the data (not including
          the terminating zero) is stored in LEN_OUT.

     void eicpyout_alloca_fmt (Eistring *eistr, LVALUE: Ibyte *ptr_out,
                               LVALUE: Bytecount len_out,
                               Internal_Format intfmt, Lisp_Object object);
          Like `eicpyout_alloca()', but converts to the specified internal
          format. (No formats other than FORMAT_DEFAULT are currently
          implemented, and you get an assertion failure if you try.)

     Ibyte *eicpyout_malloc (Eistring *eistr, Bytecount *intlen_out);
          Make a `malloc()' copy of the data in the Eistring, using the
          default internal format.  This is a real function.  No lvalues
          passed in.  Returns the new data, and stores the length (not
          including the terminating zero) using INTLEN_OUT, unless it's
          a NULL pointer.

     Ibyte *eicpyout_malloc_fmt (Eistring *eistr, Internal_Format intfmt,
                                   Bytecount *intlen_out, Lisp_Object object);
          Like `eicpyout_malloc()', but converts to the specified internal
          format. (No formats other than FORMAT_DEFAULT are currently
          implemented, and you get an assertion failure if you try.)


      **********************************************
      *             Moving to the heap             *
      **********************************************

     void eito_malloc (Eistring *eistr);
          Move this Eistring to the heap.  Its data will be stored in a
          `malloc()'ed block rather than the stack.  Subsequent changes to
          this Eistring will `realloc()' the block as necessary.  Use this
          when you want the Eistring to remain in scope past the end of
          this function call.  You will have to manually free the data
          in the Eistring using `eifree()'.

     void eito_alloca (Eistring *eistr);
          Move this Eistring back to the stack, if it was moved to the
          heap with `eito_malloc()'.  This will automatically free any
          heap-allocated data.



      **********************************************
      *            Retrieving the length           *
      **********************************************

     Bytecount eilen (Eistring *eistr);
          Return the length of the internal data, in bytes.  See also
          `eiextlen()', below.
     Charcount eicharlen (Eistring *eistr);
          Return the length of the internal data, in characters.


      **********************************************
      *           Working with positions           *
      **********************************************

     Bytecount eicharpos_to_bytepos (Eistring *eistr, Charcount charpos);
          Convert a char offset to a byte offset.
     Charcount eibytepos_to_charpos (Eistring *eistr, Bytecount bytepos);
          Convert a byte offset to a char offset.
     Bytecount eiincpos (Eistring *eistr, Bytecount bytepos);
          Increment the given position by one character.
     Bytecount eiincpos_n (Eistring *eistr, Bytecount bytepos, Charcount n);
          Increment the given position by N characters.
     Bytecount eidecpos (Eistring *eistr, Bytecount bytepos);
          Decrement the given position by one character.
     Bytecount eidecpos_n (Eistring *eistr, Bytecount bytepos, Charcount n);
          Deccrement the given position by N characters.


      **********************************************
      *    Getting the character at a position     *
      **********************************************

     Ichar eigetch (Eistring *eistr, Bytecount bytepos);
          Return the character at a particular byte offset.
     Ichar eigetch_char (Eistring *eistr, Charcount charpos);
          Return the character at a particular character offset.


      **********************************************
      *    Setting the character at a position     *
      **********************************************

     Ichar eisetch (Eistring *eistr, Bytecount bytepos, Ichar chr);
          Set the character at a particular byte offset.
     Ichar eisetch_char (Eistring *eistr, Charcount charpos, Ichar chr);
          Set the character at a particular character offset.


      **********************************************
      *               Concatenation                *
      **********************************************

     void eicat_* (Eistring *eistr, ...);
          Concatenate onto the end of the Eistring, with data coming from the
          same places as above:

     void eicat_ei (Eistring *eistr, Eistring *eistr2);
          ... from another Eistring.
     void eicat_c (Eistring *eistr, Ascbyte *c_string);
          ... from an ASCII null-terminated string.  Non-ASCII characters in
          the string are *ILLEGAL* (read `abort()' with error-checking defined).
     void eicat_raw (ei, const Ibyte *data, Bytecount len);
          ... from raw internal-format data in the default internal format.
     void eicat_rawz (ei, const Ibyte *data);
          ... from raw internal-format data in the default internal format
          that is "null-terminated" (the meaning of this depends on the nature
          of the default internal format).
     void eicat_lstr (ei, Lisp_Object lisp_string);
          ... from a Lisp_Object string.
     void eicat_ch (ei, Ichar ch);
          ... from an Ichar.

     All except the first variety are convenience functions.
     n the general case, create another Eistring from the source.)


      **********************************************
      *                Replacement                 *
      **********************************************

     void eisub_* (Eistring *eistr, Bytecount off, Charcount charoff,
          			  Bytecount len, Charcount charlen, ...);
          Replace a section of the Eistring, specifically:

     void eisub_ei (Eistring *eistr, Bytecount off, Charcount charoff,
          	  Bytecount len, Charcount charlen, Eistring *eistr2);
          ... with another Eistring.
     void eisub_c (Eistring *eistr, Bytecount off, Charcount charoff,
          	 Bytecount len, Charcount charlen, Ascbyte *c_string);
          ... with an ASCII null-terminated string.  Non-ASCII characters in
          the string are *ILLEGAL* (read `abort()' with error-checking defined).
     void eisub_ch (Eistring *eistr, Bytecount off, Charcount charoff,
          	  Bytecount len, Charcount charlen, Ichar ch);
          ... with an Ichar.

     void eidel (Eistring *eistr, Bytecount off, Charcount charoff,
                 Bytecount len, Charcount charlen);
          Delete a section of the Eistring.


      **********************************************
      *      Converting to an external format      *
      **********************************************

     void eito_external (Eistring *eistr, Lisp_Object codesys);
          Convert the Eistring to an external format and store the result
          in the string.  NOTE: Further changes to the Eistring will *NOT*
          change the external data stored in the string.  You will have to
          call `eito_external()' again in such a case if you want the external
          data.

     Extbyte *eiextdata (Eistring *eistr);
          Return a pointer to the external data stored in the Eistring as
          a result of a prior call to `eito_external()'.

     Bytecount eiextlen (Eistring *eistr);
          Return the length in bytes of the external data stored in the
          Eistring as a result of a prior call to `eito_external()'.


      **********************************************
      * Searching in the Eistring for a character  *
      **********************************************

     Bytecount eichr (Eistring *eistr, Ichar chr);
     Charcount eichr_char (Eistring *eistr, Ichar chr);
     Bytecount eichr_off (Eistring *eistr, Ichar chr, Bytecount off,
          		Charcount charoff);
     Charcount eichr_off_char (Eistring *eistr, Ichar chr, Bytecount off,
          		     Charcount charoff);
     Bytecount eirchr (Eistring *eistr, Ichar chr);
     Charcount eirchr_char (Eistring *eistr, Ichar chr);
     Bytecount eirchr_off (Eistring *eistr, Ichar chr, Bytecount off,
          		 Charcount charoff);
     Charcount eirchr_off_char (Eistring *eistr, Ichar chr, Bytecount off,
          		      Charcount charoff);


      **********************************************
      *   Searching in the Eistring for a string   *
      **********************************************

     Bytecount eistr_ei (Eistring *eistr, Eistring *eistr2);
     Charcount eistr_ei_char (Eistring *eistr, Eistring *eistr2);
     Bytecount eistr_ei_off (Eistring *eistr, Eistring *eistr2, Bytecount off,
          		   Charcount charoff);
     Charcount eistr_ei_off_char (Eistring *eistr, Eistring *eistr2,
          			Bytecount off, Charcount charoff);
     Bytecount eirstr_ei (Eistring *eistr, Eistring *eistr2);
     Charcount eirstr_ei_char (Eistring *eistr, Eistring *eistr2);
     Bytecount eirstr_ei_off (Eistring *eistr, Eistring *eistr2, Bytecount off,
          		    Charcount charoff);
     Charcount eirstr_ei_off_char (Eistring *eistr, Eistring *eistr2,
          			 Bytecount off, Charcount charoff);

     Bytecount eistr_c (Eistring *eistr, Ascbyte *c_string);
     Charcount eistr_c_char (Eistring *eistr, Ascbyte *c_string);
     Bytecount eistr_c_off (Eistring *eistr, Ascbyte *c_string, Bytecount off,
          		   Charcount charoff);
     Charcount eistr_c_off_char (Eistring *eistr, Ascbyte *c_string,
          		       Bytecount off, Charcount charoff);
     Bytecount eirstr_c (Eistring *eistr, Ascbyte *c_string);
     Charcount eirstr_c_char (Eistring *eistr, Ascbyte *c_string);
     Bytecount eirstr_c_off (Eistring *eistr, Ascbyte *c_string,
          		   Bytecount off, Charcount charoff);
     Charcount eirstr_c_off_char (Eistring *eistr, Ascbyte *c_string,
          			Bytecount off, Charcount charoff);


      **********************************************
      *                 Comparison                 *
      **********************************************

     int eicmp_* (Eistring *eistr, ...);
     int eicmp_off_* (Eistring *eistr, Bytecount off, Charcount charoff,
                      Bytecount len, Charcount charlen, ...);
     int eicasecmp_* (Eistring *eistr, ...);
     int eicasecmp_off_* (Eistring *eistr, Bytecount off, Charcount charoff,
                          Bytecount len, Charcount charlen, ...);
     int eicasecmp_i18n_* (Eistring *eistr, ...);
     int eicasecmp_i18n_off_* (Eistring *eistr, Bytecount off, Charcount charoff,
                               Bytecount len, Charcount charlen, ...);

          Compare the Eistring with the other data.  Return value same as
          from strcmp.  The `*' is either `ei' for another Eistring (in
          which case `...' is an Eistring), or `c' for a pure-ASCII string
          (in which case `...' is a pointer to that string).  For anything
          more complex, first create an Eistring out of the source.
          Comparison is either simple (`eicmp_...'), ASCII case-folding
          (`eicasecmp_...'), or multilingual case-folding
          (`eicasecmp_i18n_...').


     More specifically, the prototypes are:

     int eicmp_ei (Eistring *eistr, Eistring *eistr2);
     int eicmp_off_ei (Eistring *eistr, Bytecount off, Charcount charoff,
                       Bytecount len, Charcount charlen, Eistring *eistr2);
     int eicasecmp_ei (Eistring *eistr, Eistring *eistr2);
     int eicasecmp_off_ei (Eistring *eistr, Bytecount off, Charcount charoff,
                           Bytecount len, Charcount charlen, Eistring *eistr2);
     int eicasecmp_i18n_ei (Eistring *eistr, Eistring *eistr2);
     int eicasecmp_i18n_off_ei (Eistring *eistr, Bytecount off,
          		      Charcount charoff, Bytecount len,
          		      Charcount charlen, Eistring *eistr2);

     int eicmp_c (Eistring *eistr, Ascbyte *c_string);
     int eicmp_off_c (Eistring *eistr, Bytecount off, Charcount charoff,
                      Bytecount len, Charcount charlen, Ascbyte *c_string);
     int eicasecmp_c (Eistring *eistr, Ascbyte *c_string);
     int eicasecmp_off_c (Eistring *eistr, Bytecount off, Charcount charoff,
                          Bytecount len, Charcount charlen,
                          Ascbyte *c_string);
     int eicasecmp_i18n_c (Eistring *eistr, Ascbyte *c_string);
     int eicasecmp_i18n_off_c (Eistring *eistr, Bytecount off, Charcount charoff,
                               Bytecount len, Charcount charlen,
                               Ascbyte *c_string);


      **********************************************
      *         Case-changing the Eistring         *
      **********************************************

     void eilwr (Eistring *eistr);
          Convert all characters in the Eistring to lowercase.
     void eiupr (Eistring *eistr);
          Convert all characters in the Eistring to uppercase.


File: internals.info,  Node: Coding for Mule,  Next: CCL,  Prev: Internal Text API's,  Up: Multilingual Support

25.10 Coding for Mule
=====================

Although Mule support is not compiled by default in XEmacs, many people
are using it, and we consider it crucial that new code works correctly
with multibyte characters.  This is not hard; it is only a matter of
following several simple user-interface guidelines.  Even if you never
compile with Mule, with a little practice you will find it quite easy
to code Mule-correctly.

   Note that these guidelines are not necessarily tied to the current
Mule implementation; they are also a good idea to follow on the grounds
of code generalization for future I18N work.

* Menu:

* Character-Related Data Types::
* Working With Character and Byte Positions::
* Conversion to and from External Data::
* General Guidelines for Writing Mule-Aware Code::
* An Example of Mule-Aware Code::
* Mule-izing Code::


File: internals.info,  Node: Character-Related Data Types,  Next: Working With Character and Byte Positions,  Prev: Coding for Mule,  Up: Coding for Mule

25.10.1 Character-Related Data Types
------------------------------------

First, let's review the basic character-related datatypes used by
XEmacs.  Note that some of the separate `typedef's are not mandatory,
but they improve clarity of code a great deal, because one glance at
the declaration can tell the intended use of the variable.

`Ichar'
     An `Ichar' holds a single Emacs character.

     Obviously, the equality between characters and bytes is lost in
     the Mule world.  Characters can be represented by one or more
     bytes in the buffer, and `Ichar' is a C type large enough to hold
     any character.  (This currently isn't quite true for ISO 10646,
     which defines a character as a 31-bit non-negative quantity, while
     XEmacs characters are only 30-bits.  This is irrelevant, unless
     you are considering using the ISO 10646 private groups to support
     really large private character sets--in particular, the Mule
     character set!--in a version of XEmacs using Unicode internally.)

     Without Mule support, an `Ichar' is equivalent to an `unsigned
     char'.  [[This doesn't seem to be true; `lisp.h' unconditionally
     `typedef's `Ichar' to `int'.]]

`Ibyte'
     The data representing the text in a buffer or string is logically
     a set of `Ibyte's.

     XEmacs does not work with the same character formats all the time;
     when reading characters from the outside, it decodes them to an
     internal format, and likewise encodes them when writing.  `Ibyte'
     (in fact `unsigned char') is the basic unit of XEmacs internal
     buffers and strings format.  An `Ibyte *' is the type that points
     at text encoded in the variable-width internal encoding.

     One character can correspond to one or more `Ibyte's.  In the
     current Mule implementation, an ASCII character is represented by
     the same `Ibyte', and other characters are represented by a
     sequence of two or more `Ibyte's.  (This will also be true of an
     implementation using UTF-8 as the internal encoding.  In fact,
     only code that implements character code conversions and a very
     few macros used to implement motion by whole characters will
     notice the difference between UTF-8 and the Mule encoding.)

     Without Mule support, there are exactly 256 characters, implicitly
     Latin-1, and each character is represented using one `Ibyte', and
     there is a one-to-one correspondence between `Ibyte's and `Ichar's.

`Charxpos'

`Charbpos'
`Charcount'
     A `Charbpos' represents a character position in a buffer.  A
     `Charcount' represents a number (count) of characters.  Logically,
     subtracting two `Charbpos' values yields a `Charcount' value.
     When representing a character position in a string, we just use
     `Charcount' directly.  The reason for having a separate typedef for
     buffer positions is that they are 1-based, whereas string
     positions are 0-based and hence string counts and positions can be
     freely intermixed (a string position is equivalent to the count of
     characters from the beginning).  When representing a character
     position that could be either in a buffer or string (for example,
     in the extent code), `Charxpos' is used.  Although all of these
     are `typedef'ed to `EMACS_INT', we use them in preference to
     `EMACS_INT' to make it clear what sort of position is being used.

     `Charxpos', `Charbpos' and `Charcount' values are the only ones
     that are ever visible to Lisp.

`Bytexpos'
`Bytecount'
     A `Bytebpos' represents a byte position in a buffer.  A
     `Bytecount' represents the distance between two positions, in
     bytes.  Byte positions in strings use `Bytecount', and for byte
     positions that can be either in a buffer or string, `Bytexpos' is
     used.  The relationship between `Bytexpos', `Bytebpos' and
     `Bytecount' is the same as the relationship between `Charxpos',
     `Charbpos' and `Charcount'.

`Extbyte'
     When dealing with the outside world, XEmacs works with `Extbyte's,
     which are equivalent to `char'.  The distance between two
     `Extbyte's is a `Bytecount', since external text is a byte-by-byte
     encoding.  Extbytes occur mainly at the transition point between
     internal text and external functions.  XEmacs code should not, if
     it can possibly avoid it, do any actual manipulation using external
     text, since its format is completely unpredictable (it might not
     even be ASCII-compatible).


File: internals.info,  Node: Working With Character and Byte Positions,  Next: Conversion to and from External Data,  Prev: Character-Related Data Types,  Up: Coding for Mule

25.10.2 Working With Character and Byte Positions
-------------------------------------------------

Now that we have defined the basic character-related types, we can look
at the macros and functions designed for work with them and for
conversion between them.  Most of these macros are defined in
`buffer.h', and we don't discuss all of them here, but only the most
important ones.  Examining the existing code is the best way to learn
about them.

`MAX_ICHAR_LEN'
     This preprocessor constant is the maximum number of buffer bytes to
     represent an Emacs character in the variable width internal
     encoding.  It is useful when allocating temporary strings to keep
     a known number of characters.  For instance:

          {
            Charcount cclen;
            ...
            {
              /* Allocate place for CCLEN characters. */
              Ibyte *buf = (Ibyte *) alloca (cclen * MAX_ICHAR_LEN);
          ...

     If you followed the previous section, you can guess that,
     logically, multiplying a `Charcount' value with `MAX_ICHAR_LEN'
     produces a `Bytecount' value.

     In the current Mule implementation, `MAX_ICHAR_LEN' equals 4.
     Without Mule, it is 1.  In a mature Unicode-based XEmacs, it will
     also be 4 (since all Unicode characters can be encoded in UTF-8 in
     4 bytes or less), but some versions may use up to 6, in order to
     use the large private space provided by ISO 10646 to "mirror" the
     Mule code space.

`itext_ichar'
`set_itext_ichar'
     The `itext_ichar' macro takes a `Ibyte' pointer and returns the
     `Ichar' stored at that position.  If it were a function, its
     prototype would be:

          Ichar itext_ichar (Ibyte *p);

     `set_itext_ichar' stores an `Ichar' to the specified byte
     position.  It returns the number of bytes stored:

          Bytecount set_itext_ichar (Ibyte *p, Ichar c);

     It is important to note that `set_itext_ichar' is safe only for
     appending a character at the end of a buffer, not for overwriting a
     character in the middle.  This is because the width of characters
     varies, and `set_itext_ichar' cannot resize the string if it
     writes, say, a two-byte character where a single-byte character
     used to reside.

     A typical use of `set_itext_ichar' can be demonstrated by this
     example, which copies characters from buffer BUF to a temporary
     string of Ibytes.

          {
            Charbpos pos;
            for (pos = beg; pos < end; pos++)
              {
                Ichar c = BUF_FETCH_CHAR (buf, pos);
                p += set_itext_ichar (buf, c);
              }
          }

     Note how `set_itext_ichar' is used to store the `Ichar' and
     increment the counter, at the same time.

`INC_IBYTEPTR'
`DEC_IBYTEPTR'
     These two macros increment and decrement an `Ibyte' pointer,
     respectively.  They will adjust the pointer by the appropriate
     number of bytes according to the byte length of the character
     stored there.  Both macros assume that the memory address is
     located at the beginning of a valid character.

     Without Mule support, `INC_IBYTEPTR (p)' and `DEC_IBYTEPTR (p)'
     simply expand to `p++' and `p--', respectively.

`bytecount_to_charcount'
     Given a pointer to a text string and a length in bytes, return the
     equivalent length in characters.

          Charcount bytecount_to_charcount (Ibyte *p, Bytecount bc);

`charcount_to_bytecount'
     Given a pointer to a text string and a length in characters,
     return the equivalent length in bytes.

          Bytecount charcount_to_bytecount (Ibyte *p, Charcount cc);

`itext_n_addr'
     Return a pointer to the beginning of the character offset CC (in
     characters) from P.

          Ibyte *itext_n_addr (Ibyte *p, Charcount cc);


File: internals.info,  Node: Conversion to and from External Data,  Next: General Guidelines for Writing Mule-Aware Code,  Prev: Working With Character and Byte Positions,  Up: Coding for Mule

25.10.3 Conversion to and from External Data
--------------------------------------------

When an external function, such as a C library function, returns a
`char' pointer, you should almost never treat it as `Ibyte'.  This is
because these returned strings may contain 8bit characters which can be
misinterpreted by XEmacs, and cause a crash.  Likewise, when exporting
a piece of internal text to the outside world, you should always
convert it to an appropriate external encoding, lest the internal stuff
(such as the infamous \201 characters) leak out.

   The interface to conversion between the internal and external
representations of text are the numerous conversion macros defined in
`buffer.h'.  There used to be a fixed set of external formats supported
by these macros, but now any coding system can be used with them.  The
coding system alias mechanism is used to create the following logical
coding systems, which replace the fixed external formats.  The
(dontusethis-set-symbol-value-handler) mechanism was enhanced to make
this possible (more work on that is needed).

   Often useful coding systems:

`Qbinary'
     This is the simplest format and is what we use in the absence of a
     more appropriate format.  This converts according to the `binary'
     coding system:

       a. On input, bytes 0-255 are converted into (implicitly Latin-1)
          characters 0-255.  A non-Mule xemacs doesn't really know about
          different character sets and the fonts to display them, so
          the bytes can be treated as text in different 1-byte
          encodings by simply setting the appropriate fonts.  So in a
          sense, non-Mule xemacs is a multi-lingual editor if, for
          example, different fonts are used to display text in
          different buffers, faces, or windows.  The specifier
          mechanism gives the user complete control over this kind of
          behavior.

       b. On output, characters 0-255 are converted into bytes 0-255
          and other characters are converted into `~'.

`Qnative'
     Format used for the external Unix environment--`argv[]', stuff
     from `getenv()', stuff from the `/etc/passwd' file, etc.  This is
     encoded according to the encoding specified by the current locale.
     [[This is dangerous; current locale is user preference, and the
     system is probably going to be something else.  Is there anything
     we can do about it?]]

`Qfile_name'
     Format used for filenames.  This is normally the same as `Qnative',
     but the two should be distinguished for clarity and possible future
     separation - and also because `Qfile_name' can be changed using
     either the `file-name-coding-system' or `pathname-coding-system'
     (now obsolete) variables.

`Qctext'
     Compound-text format.  This is the standard X11 format used for
     data stored in properties, selections, and the like.  This is an
     8-bit no-lock-shift ISO2022 coding system.  This is a real coding
     system, unlike `Qfile_name', which is user-definable.

`Qmswindows_tstr'
     Used for external data in all MS Windows functions that are
     declared to accept data of type `LPTSTR' or `LPCSTR'.  This maps
     to either `Qmswindows_multibyte' (a locale-specific encoding, same
     as `Qnative') or `Qmswindows_unicode', depending on whether XEmacs
     is being run under Windows 9X or Windows NT/2000/XP.

   Many other coding systems are provided by default.

   There are two fundamental macros to convert between external and
internal format, as well as various convenience macros to simplify the
most common operations.

   `TO_INTERNAL_FORMAT' converts external data to internal format, and
`TO_EXTERNAL_FORMAT' converts the other way around.  The arguments each
of these receives are a source type, a source, a sink type, a sink, and
a coding system (or a symbol naming a coding system).

   A typical call looks like
     TO_EXTERNAL_FORMAT (LISP_STRING, str, C_STRING_MALLOC, ptr, Qfile_name);

   which means that the contents of the lisp string `str' are written
to a malloc'ed memory area which will be pointed to by `ptr', after the
function returns.  The conversion will be done using the `file-name'
coding system, which will be controlled by the user indirectly by
setting or binding the variable `file-name-coding-system'.

   Some sources and sinks require two C variables to specify.  We use
some preprocessor magic to allow different source and sink types, and
even different numbers of arguments to specify different types of
sources and sinks.

   So we can have a call that looks like
     TO_INTERNAL_FORMAT (DATA, (ptr, len),
                         MALLOC, (ptr, len),
                         coding_system);

   The parenthesized argument pairs are required to make the
preprocessor magic work.

   Here are the different source and sink types:

``DATA, (ptr, len),''
     input data is a fixed buffer of size LEN at address PTR

``ALLOCA, (ptr, len),''
     output data is placed in an `alloca()'ed buffer of size LEN
     pointed to by PTR

``MALLOC, (ptr, len),''
     output data is in a `malloc()'ed buffer of size LEN pointed to by
     PTR

``C_STRING_ALLOCA, ptr,''
     equivalent to `ALLOCA (ptr, len_ignored)' on output.

``C_STRING_MALLOC, ptr,''
     equivalent to `MALLOC (ptr, len_ignored)' on output

``C_STRING, ptr,''
     equivalent to `DATA, (ptr, strlen/wcslen (ptr))' on input

``LISP_STRING, string,''
     input or output is a Lisp_Object of type string

``LISP_BUFFER, buffer,''
     output is written to `(point)' in lisp buffer BUFFER

``LISP_LSTREAM, lstream,''
     input or output is a Lisp_Object of type lstream

``LISP_OPAQUE, object,''
     input or output is a Lisp_Object of type opaque

   A source type of `C_STRING' or a sink type of `C_STRING_ALLOCA' or
`C_STRING_MALLOC' is appropriate where the external API is not
'\0'-byte-clean - i.e. it expects strings to be terminated with a null
byte.  For external API's that are in fact '\0'-byte-clean, we should
of course not use these.

   The sinks to be specified must be lvalues, unless they are the lisp
object types `LISP_LSTREAM' or `LISP_BUFFER'.

   There is no problem using the same lvalue for source and sink.

   Garbage collection is inhibited during these conversion operations,
so it is OK to pass in data from Lisp strings using `XSTRING_DATA'.

   For the sink types `ALLOCA' and `C_STRING_ALLOCA', the resulting
text is stored in a stack-allocated buffer, which is automatically
freed on returning from the function.  However, the sink types `MALLOC'
and `C_STRING_MALLOC' return `xmalloc()'ed memory.  The caller is
responsible for freeing this memory using `xfree()'.

   Note that it doesn't make sense for `LISP_STRING' to be a source for
`TO_INTERNAL_FORMAT' or a sink for `TO_EXTERNAL_FORMAT'.  You'll get an
assertion failure if you try.

   99% of conversions involve raw data or Lisp strings as both source
and sink, and usually data is output as `alloca()', or sometimes
`xmalloc()'.  For this reason, convenience macros are defined for many
types of conversions involving raw data and/or Lisp strings, especially
when the output is an `alloca()'ed string. (When the destination is a
Lisp string, there are other functions that should be used instead -
`build_ext_string()' and `make_ext_string()', for example.) The
convenience macros are of two types - the older kind that store the
result into a specified variable, and the newer kind that return the
result.  The newer kind of macros don't exist when the output is sized
data, because that would have two return values.  NOTE: All convenience
macros are ultimately defined in terms of `TO_EXTERNAL_FORMAT' and
`TO_INTERNAL_FORMAT'.  Thus, any comments above about the workings of
these macros also apply to all convenience macros.

   A typical old-style convenience macro is

       C_STRING_TO_EXTERNAL (in, out, codesys);

   This is equivalent to

       TO_EXTERNAL_FORMAT (C_STRING, in, C_STRING_ALLOCA, out, codesys);

   but is easier to write and somewhat clearer, since it clearly
identifies the arguments without the clutter of having the preprocessor
types mixed in.

   The new-style equivalent is `NEW_C_STRING_TO_EXTERNAL (src,
codesys)', which _returns_ the converted data (still in `alloca()'
space).  This is far more convenient for most operations.


File: internals.info,  Node: General Guidelines for Writing Mule-Aware Code,  Next: An Example of Mule-Aware Code,  Prev: Conversion to and from External Data,  Up: Coding for Mule

25.10.4 General Guidelines for Writing Mule-Aware Code
------------------------------------------------------

This section contains some general guidance on how to write Mule-aware
code, as well as some pitfalls you should avoid.

_Never use `char' and `char *'._
     In XEmacs, the use of `char' and `char *' is almost always a
     mistake.  If you want to manipulate an Emacs character from "C",
     use `Ichar'.  If you want to examine a specific octet in the
     internal format, use `Ibyte'.  If you want a Lisp-visible
     character, use a `Lisp_Object' and `make_char'.  If you want a
     pointer to move through the internal text, use `Ibyte *'.  Also
     note that you almost certainly do not need `Ichar *'.  Other
     typedefs to clarify the use of `char' are `Char_ASCII',
     `Char_Binary', `UChar_Binary', and `CIbyte'.

_Be careful not to confuse `Charcount', `Bytecount', `Charbpos' and `Bytebpos'._
     The whole point of using different types is to avoid confusion
     about the use of certain variables.  Lest this effect be
     nullified, you need to be careful about using the right types.

_Always convert external data_
     It is extremely important to always convert external data, because
     XEmacs can crash if unexpected 8-bit sequences are copied to its
     internal buffers literally.

     This means that when a system function, such as `readdir', returns
     a string, you normally need to convert it using one of the
     conversion macros described in the previous chapter, before
     passing it further to Lisp.

     Actually, most of the basic system functions that accept
     '\0'-terminated string arguments, like `stat()' and `open()', have
     *encapsulated* equivalents that do the internal to external
     conversion themselves.  The encapsulated equivalents have a `qxe_'
     prefix and have string arguments of type `Ibyte *', and you can
     pass internally encoded data to them, often from a Lisp string
     using `XSTRING_DATA'. (A better design might be to provide
     versions that accept Lisp strings directly.)  [[Really?  Then
     they'd either take `Lisp_Object's and need to check type, or
     they'd take `Lisp_String's, and violate the rules about passing
     any of the specific Lisp types.]]

     Also note that many internal functions, such as `make_string',
     accept Ibytes, which removes the need for them to convert the data
     they receive.  This increases efficiency because that way external
     data needs to be decoded only once, when it is read.  After that,
     it is passed around in internal format.

_Do all work in internal format_
     External-formatted data is completely unpredictable in its format.
     It may be fixed-width Unicode (not even ASCII compatible); it may
     be a modal encoding, in which case some occurrences of (e.g.) the
     slash character may be part of two-byte Asian-language characters,
     and a naive attempt to split apart a pathname by slashes will
     fail; etc.  Internal-format text should be converted to external
     format only at the point where an external API is actually called,
     and the first thing done after receiving external-format text from
     an external API should be to convert it to internal text.


File: internals.info,  Node: An Example of Mule-Aware Code,  Next: Mule-izing Code,  Prev: General Guidelines for Writing Mule-Aware Code,  Up: Coding for Mule

25.10.5 An Example of Mule-Aware Code
-------------------------------------

As an example of Mule-aware code, we will analyze the `string'
function, which conses up a Lisp string from the character arguments it
receives.  Here is the definition, pasted from `alloc.c':

     DEFUN ("string", Fstring, 0, MANY, 0, /*
     Concatenate all the argument characters and make the result a string.
     */
            (int nargs, Lisp_Object *args))
     {
       Ibyte *storage = alloca_array (Ibyte, nargs * MAX_ICHAR_LEN);
       Ibyte *p = storage;

       for (; nargs; nargs--, args++)
         {
           Lisp_Object lisp_char = *args;
           CHECK_CHAR_COERCE_INT (lisp_char);
           p += set_itext_ichar (p, XCHAR (lisp_char));
         }
       return make_string (storage, p - storage);
     }

   Now we can analyze the source line by line.

   Obviously, string will be as long as there are arguments to the
function.  This is why we allocate `MAX_ICHAR_LEN' * NARGS bytes on the
stack, i.e. the worst-case number of bytes for NARGS `Ichar's to fit in
the string.

   Then, the loop checks that each element is a character, converting
integers in the process.  Like many other functions in XEmacs, this
function silently accepts integers where characters are expected, for
historical and compatibility reasons.  Unless you know what you are
doing, `CHECK_CHAR' will also suffice.  `XCHAR (lisp_char)' extracts
the `Ichar' from the `Lisp_Object', and `set_itext_ichar' stores it to
storage, increasing `p' in the process.

   Other instructive examples of correct coding under Mule can be found
all over the XEmacs code.  For starters, I recommend
`Fnormalize_menu_item_name' in `menubar.c'.  After you have understood
this section of the manual and studied the examples, you can proceed
writing new Mule-aware code.


File: internals.info,  Node: Mule-izing Code,  Prev: An Example of Mule-Aware Code,  Up: Coding for Mule

25.10.6 Mule-izing Code
-----------------------

A lot of code is written without Mule in mind, and needs to be made
Mule-correct or "Mule-ized".  There is really no substitute for
line-by-line analysis when doing this, but the following checklist can
help:

   * Check all uses of `XSTRING_DATA'.

   * Check all uses of `build_string' and `make_string'.

   * Check all uses of `tolower' and `toupper'.

   * Check object print methods.

   * Check for use of functions such as `write_c_string',
     `write_fmt_string', `stderr_out', `stdout_out'.

   * Check all occurrences of `char' and correct to one of the other
     typedefs described above.

   * Check all existing uses of `TO_EXTERNAL_FORMAT',
     `TO_INTERNAL_FORMAT', and any convenience macros (grep for
     `EXTERNAL_TO', `TO_EXTERNAL', and `TO_SIZED_EXTERNAL').

   * In Windows code, string literals may need to be encapsulated with
     `XETEXT'.


File: internals.info,  Node: CCL,  Next: Microsoft Windows-Related Multilingual Issues,  Prev: Coding for Mule,  Up: Multilingual Support

25.11 CCL
=========

     MACHINE CODE:

     The machine code consists of a vector of 32-bit words.
     The first such word specifies the start of the EOF section of the code;
     this is the code executed to handle any stuff that needs to be done
     (e.g. designating back to ASCII and left-to-right mode) after all
     other encoded/decoded data has been written out.  This is not used for
     charset CCL programs.

     REGISTER: 0..7  -- referred by RRR or rrr

     OPERATOR BIT FIELD (27-bit): XXXXXXXXXXXXXXX RRR TTTTT
             TTTTT (5-bit): operator type
             RRR (3-bit): register number
             XXXXXXXXXXXXXXXX (15-bit):
                     CCCCCCCCCCCCCCC: constant or address
                     000000000000rrr: register number

     AAAA:   00000 +
             00001 -
             00010 *
             00011 /
             00100 %
             00101 &
             00110 |
             00111 ~

             01000 <<
             01001 >>
             01010 <8
             01011 >8
             01100 //
             01101 not used
             01110 not used
             01111 not used

             10000 <
             10001 >
             10010 ==
             10011 <=
             10100 >=
             10101 !=

     OPERATORS:      TTTTT RRR XX..

     SetCS:          00000 RRR C...C      RRR = C...C
     SetCL:          00001 RRR .....      RRR = c...c
                     c.............c
     SetR:           00010 RRR ..rrr      RRR = rrr
     SetA:           00011 RRR ..rrr      RRR = array[rrr]
                     C.............C      size of array = C...C
                     c.............c      contents = c...c

     Jump:           00100 000 c...c      jump to c...c
     JumpCond:       00101 RRR c...c      if (!RRR) jump to c...c
     WriteJump:      00110 RRR c...c      Write1 RRR, jump to c...c
     WriteReadJump:  00111 RRR c...c      Write1, Read1 RRR, jump to c...c
     WriteCJump:     01000 000 c...c      Write1 C...C, jump to c...c
                     C...C
     WriteCReadJump: 01001 RRR c...c      Write1 C...C, Read1 RRR,
                     C.............C      and jump to c...c
     WriteSJump:     01010 000 c...c      WriteS, jump to c...c
                     C.............C
                     S.............S
                     ...
     WriteSReadJump: 01011 RRR c...c      WriteS, Read1 RRR, jump to c...c
                     C.............C
                     S.............S
                     ...
     WriteAReadJump: 01100 RRR c...c      WriteA, Read1 RRR, jump to c...c
                     C.............C      size of array = C...C
                     c.............c      contents = c...c
                     ...
     Branch:         01101 RRR C...C      if (RRR >= 0 && RRR < C..)
                     c.............c      branch to (RRR+1)th address
     Read1:          01110 RRR ...        read 1-byte to RRR
     Read2:          01111 RRR ..rrr      read 2-byte to RRR and rrr
     ReadBranch:     10000 RRR C...C      Read1 and Branch
                     c.............c
                     ...
     Write1:         10001 RRR .....      write 1-byte RRR
     Write2:         10010 RRR ..rrr      write 2-byte RRR and rrr
     WriteC:         10011 000 .....      write 1-char C...CC
                     C.............C
     WriteS:         10100 000 .....      write C..-byte of string
                     C.............C
                     S.............S
                     ...
     WriteA:         10101 RRR .....      write array[RRR]
                     C.............C      size of array = C...C
                     c.............c      contents = c...c
                     ...
     End:            10110 000 .....      terminate the execution

     SetSelfCS:      10111 RRR C...C      RRR AAAAA= C...C
                     ..........AAAAA
     SetSelfCL:      11000 RRR .....      RRR AAAAA= c...c
                     c.............c
                     ..........AAAAA
     SetSelfR:       11001 RRR ..Rrr      RRR AAAAA= rrr
                     ..........AAAAA
     SetExprCL:      11010 RRR ..Rrr      RRR = rrr AAAAA c...c
                     c.............c
                     ..........AAAAA
     SetExprR:       11011 RRR ..rrr      RRR = rrr AAAAA Rrr
                     ............Rrr
                     ..........AAAAA
     JumpCondC:      11100 RRR c...c      if !(RRR AAAAA C..) jump to c...c
                     C.............C
                     ..........AAAAA
     JumpCondR:      11101 RRR c...c      if !(RRR AAAAA rrr) jump to c...c
                     ............rrr
                     ..........AAAAA
     ReadJumpCondC:  11110 RRR c...c      Read1 and JumpCondC
                     C.............C
                     ..........AAAAA
     ReadJumpCondR:  11111 RRR c...c      Read1 and JumpCondR
                     ............rrr
                     ..........AAAAA


File: internals.info,  Node: Microsoft Windows-Related Multilingual Issues,  Next: Modules for Internationalization,  Prev: CCL,  Up: Multilingual Support

25.12 Microsoft Windows-Related Multilingual Issues
===================================================

* Menu:

* Microsoft Documentation::
* Locales::
* More about code pages::
* More about locales::
* Unicode support under Windows::
* The golden rules of writing Unicode-safe code::
* The format of the locale in setlocale()::
* Random other Windows I18N docs::


File: internals.info,  Node: Microsoft Documentation,  Next: Locales,  Prev: Microsoft Windows-Related Multilingual Issues,  Up: Microsoft Windows-Related Multilingual Issues

25.12.1 Microsoft Documentation
-------------------------------

Documentation on international support in Windows is scattered
throughout MSDN.  Here are some good places to look:

  1. C Runtime (CRT) intl support

       1. Visual Tools and Languages -> Visual Studio 6.0 Documentation
          -> Visual C++ Documentation -> Using Visual C++ -> Run-Time
          Library Reference -> Internationalization

       2. Visual Tools and Languages -> Visual Studio 6.0 Documentation
          -> Visual C++ Documentation -> Using Visual C++ -> Run-Time
          Library Reference -> Global Constants -> Locale Categories

       3. Visual Tools and Languages -> Visual Studio 6.0 Documentation
          -> Visual C++ Documentation -> Using Visual C++ -> Run-Time
          Library Reference -> Appendixes -> Language and
          Country/Region Strings

       4. Visual Tools and Languages -> Visual Studio 6.0 Documentation
          -> Visual C++ Documentation -> Using Visual C++ -> Run-Time
          Library Reference -> Appendixes -> Generic-Text Mappings

       5. Function documentation for various functions: Visual Tools
          and Languages -> Visual Studio 6.0 Documentation -> Visual
          C++ Documentation -> Using Visual C++ -> Run-Time Library
          Reference -> Alphabetic Function Reference e.g. _setmbcp(),
          setlocale(), strcoll functions

  2. Win32 API intl support

       1. Platform SDK Documentation -> Base Services -> International
          Features

       2. Platform SDK Documentation -> User Interface Services ->
          Windows User Interface -> User Input -> Keyboard Input ->
          Character Messages -> International Features

       3. Backgrounders -> Windows Platform -> Windows 2000 ->
          International Support in Microsoft Windows 2000

  3. Microsoft Layer for Unicode

     Platform SDK Documentation -> Windows API -> Windows 95/98/Me
     Programming -> Windows 95/98/Me Overviews -> Microsoft Layer for
     Unicode on Windows 95/98/Me Systems

  4. Look in the CRT sources!  They come with VC++.  See win32.c.


File: internals.info,  Node: Locales,  Next: More about code pages,  Prev: Microsoft Documentation,  Up: Microsoft Windows-Related Multilingual Issues

25.12.2 Locales, code pages, and other concepts of "language"
-------------------------------------------------------------

First, make sure you clearly understand the difference between the C
runtime library (CRT) and the Win32 API!  See win32.c.

   There are various different ways of representing the vague concept
of "language", and it can be very confusing.  So:

   * The CRT library has the concept of "locale", which is a
     combination of language and country, and which controls the way
     currency and dates are displayed, the encoding of data, etc.

   * XEmacs has the concept of "language environment", more or less
     like a locale; although currently in most cases it just refers to
     the language, and no sub-language distinctions are made.
     (Exceptions are with Chinese, which has different language
     environments for Taiwan and mainland China, due to the different
     encodings and writing systems.)

   * Windows has a number of different language concepts:

       1. There are "languages" and "sublanguages", which correspond to
          the languages and countries of the C library - e.g.
          LANG_ENGLISH and SUBLANG_ENGLISH_US.  These are identified by
          8-bit integers, called the "primary language identifier" and
          "sublanguage identifier", respectively.  These are combined
          into a 16-bit integer or "language identifier" by
          MAKELANGID().

       2. The language identifier in turn is combined with a "sort
          identifier" (and optionally a "sort version") to yield a
          32-bit integer called a "locale identifier" (type LCID),
          which identifies locales - the primary means of
          distinguishing language/regional settings and similar to C
          library locales.

       3. A "code page" combines the XEmacs concepts of "charset" and
          "coding system".  It logically encompasses

             - a set of supported characters

             - an enumeration associating each character with a code
               point, which is a number or number pair; there may be
               disjoint ranges of numbers supported

             - a way of encoding a series of characters into a string
               of bytes

          Note that the first two properties correspond to an XEmacs
          "charset" and the latter an XEmacs "coding system".

          Traditional encodings are either simple one-byte encodings, or
          combination one-byte/two-byte encodings (aka MBCS encodings,
          where MBCS stands for "Multibyte Character Set") with the
          following properties:

             - all characters are encoded as a one-byte or two-byte
               sequence

             - the encoding is stateless (non-modal)

             - the lower 128 bytes are compatible with ASCII

             - in the higher bytes, the value of the first byte ("lead
               byte") determines whether a second byte follows

             - the values used for second bytes may overlap those used
               for first bytes, and (in some encodings) include values
               in the low half; thus, moving backwards is hard, and
               pure-ASCII algorithms (e.g. finding the next slash) will
               fail unless rewritten to be MBCS-aware (neither of these
               problems exist in UTF-8 or in the XEmacs internal string
               encoding)

          Recent code pages, however, do not necessarily follow these
          properties - code pages have been expanded to include
          arbitrary encodings, such as UTF-8 (may have more than two
          bytes per character) and ISO-2022-JP (complex modal encoding).

       4. Every Windows locale has four associated code pages: ANSI (an
          international standard or some Microsoft-created
          approximation; the native code page under Windows), OEM (a
          DOS encoding, still used in the FAT file system), Mac (an
          encoding used on the Macintosh) and EBCDIC (a
          non-ASCII-compatible encoding used on IBM mainframes,
          originally based on the BCD or "binary-coded decimal"
          encoding of numbers).  All code pages associated with a
          locale follow (as far as I know) the properties listed above
          for traditional code pages.  More than one locale can share a
          code page - e.g. all the Western European languages, including
          English, do.

       5. Windows also has an "input locale identifier" (aka "keyboard
          layout id") or HKL, which is a 32-bit integer composed of the
          16-bit language identifier and a 16-bit "device identifier",
          which originally specified a particular keyboard layout (e.g.
          the locale "US English" can have the QWERTY layout, the
          Dvorak layout, etc.), but has been expanded to include
          speech-to-text converters and other non-keyboard ways of
          inputting text.  Note that both the HKL and LCID share the
          language identifier in the lower 16 bits, and in both cases a
          0 in the upper 16 bits means "default" (sort order or
          device), providing a way to convert between HKL's, LCID's, and
          language identifiers (i.e. language/sublanguage pairs).  The
          default keyboard layout for a language is (as far as I can
          determine) established using the Regional Settings control
          panel applet, where you can add input locales as combinations
          of language (actually language/sublanguage) and layout;
          presumably if you list only one input locale with a
          particular language, the corresponding layout is the default
          for that language.  But what if you list more than one?  You
          can specify a single default input locale, but there appears
          to be no way to do so on a per-language basis.


File: internals.info,  Node: More about code pages,  Next: More about locales,  Prev: Locales,  Up: Microsoft Windows-Related Multilingual Issues

25.12.3 More about code pages
-----------------------------

Here is what MSDN says about code pages (article "Code Pages"):

     A code page is a character set, which can include numbers,
     punctuation marks, and other glyphs. Different languages and
     locales may use different code pages. For example, ANSI code page
     1252 is used for American English and most European languages; OEM
     code page 932 is used for Japanese Kanji.

     A code page can be represented in a table as a mapping of
     characters to single-byte values or multibyte values. Many code
     pages share the ASCII character set for characters in the range
     0x00 ?0x7F.

     The Microsoft run-time library uses the following types of code
     pages:

     - System-default ANSI code page. By default, at startup the
     run-time system automatically sets the multibyte code page to the
     system-default ANSI code page, which is obtained from the operating
     system. The call

     setlocale ( LC_ALL, "" );

     also sets the locale to the system-default ANSI code page.

     - Locale code page. The behavior of a number of run-time routines
     is dependent on the current locale setting, which includes the
     locale code page. (For more information, see Locale-Dependent
     Routines.) By default, all locale-dependent routines in the
     Microsoft run-time library use the code page that corresponds to
     the ¡ë?locale. At run-time you can change or query the locale code
     page in use with a call to setlocale.

     - Multibyte code page. The behavior of most of the
     multibyte-character routines in the run-time library depends on
     the current multibyte code page setting. By default, these
     routines use the system-default ANSI code page. At run-time you
     can query and change the multibyte code page with _getmbcp and
     _setmbcp, respectively.

     - The "C" locale is defined by ANSI to correspond to the locale in
     which C programs have traditionally executed. The code page for the
     "C" locale (¡ë?code page) corresponds to the ASCII character set.
     For example, in the "C" locale, islower returns true for the
     values 0x61 ?0x7A only. In another locale, islower may return true
     for these as well as other values, as defined by that locale.

     Under "Locale-Dependent Routines" we notice the following setlocale
     dependencies:

     atof, atoi, atol (LC_NUMERIC) is Routines (LC_CTYPE) isleadbyte
     (LC_CTYPE) localeconv (LC_MONETARY, LC_NUMERIC) MB_CUR_MAX
     (LC_CTYPE) _mbccpy (LC_CTYPE) _mbclen (LC_CTYPE) mblen (LC_CTYPE )
     _mbstrlen (LC_CTYPE) mbstowcs (LC_CTYPE) mbtowc (LC_CTYPE) printf
     (LC_NUMERIC, for radix character output) scanf (LC_NUMERIC, for
     radix character recognition) setlocale/_wsetlocale (Not applicable)
     strcoll (LC_COLLATE) _stricoll/_wcsicoll (LC_COLLATE)
     _strncoll/_wcsncoll (LC_COLLATE) _strnicoll/_wcsnicoll (LC_COLLATE)
     strftime, wcsftime (LC_TIME) _strlwr (LC_CTYPE)
     strtod/wcstod/strol/wcstol/strtoul/wcstoul (LC_NUMERIC, for radix
     character recognition) _strupr (LC_CTYPE) strxfrm/wcsxfrm
     (LC_COLLATE) tolower/towlower (LC_CTYPE) toupper/towupper
     (LC_CTYPE) wcstombs (LC_CTYPE) wctomb (LC_CTYPE) _wtoi/_wtol
     (LC_NUMERIC)

   NOTE: The above documentation doesn't clearly explain the "locale
code page" and "multibyte code page".  These are two different values,
maintained respectively in the CRT global variables __lc_codepage and
__mbcodepage.  Calling e.g. setlocale (LC_ALL, "JAPANESE") sets *ONLY*
__lc_codepage to 932 (the code page for Japanese), and leaves
__mbcodepage unchanged (usually 1252, i.e. Windows-ANSI).  You'd have to
call _setmbcp() to change __mbcodepage.  Figuring out from the
documentation which routines use which code page is not so obvious.
But:

   * from "Interpretation of Multibyte-Character Sequences" it appears
     that all "multibyte-character routines" use the multibyte code
     page except for mblen(), _mbstrlen(), mbstowcs(), mbtowc(),
     wcstombs(), and wctomb().

   * from "_setmbcp": "The multibyte code page also affects
     multibyte-character processing by the following run-time library
     routines: _exec functions _mktemp _stat _fullpath _spawn functions
     _tempnam _makepath _splitpath tmpnam.  In addition, all run-time
     library routines that receive multibyte-character argv or envp
     program arguments as parameters (such as the _exec and _spawn
     families) process these strings according to the multibyte code
     page. Hence these routines are also affected by a call to _setmbcp
     that changes the multibyte code page."

   Summary: from looking at the CRT source (which comes with VC++) and
carefully looking through the docs, it appears that:

   * the "locale code page" is used by all of the routines listed above
     under "Locale-Dependent Routines" (EXCEPT _mbccpy() and _mbclen()),
     as well as any other place that converts between multibyte and
     Unicode strings, e.g. the startup code.

   * the "multibyte code page" is used in all of the *mb*() routines
     except mblen(), _mbstrlen(), mbstowcs(), mbtowc(), wcstombs(), and
     wctomb(); also _exec*(), _spawn*(), _mktemp(), _stat(),
     _fullpath(), _tempnam(), _makepath(), _splitpath(), tmpnam(), and
     similar functions without the leading underscore.


File: internals.info,  Node: More about locales,  Next: Unicode support under Windows,  Prev: More about code pages,  Up: Microsoft Windows-Related Multilingual Issues

25.12.4 More about locales
--------------------------

In addition to the locale defined by the CRT, Windows (i.e. the Win32
API) defines various locales:

   * The system-default locale is the locale defined under "Language
     settings for the system" in the "Regional Options" control panel.
     This is NOT user-specific, and changing it requires a reboot (at
     least under Windows 2000).  The ANSI code page of the
     system-default locale is returned by GetACP(), and you can specify
     this code page in calls e.g. to MultiByteToWideChar with the
     constant CP_ACP.

   * The user-default locale is the locale defined under "Settings for
     the current user" in the "Regional Options" control panel.

   * There is a thread-local locale set by SetThreadLocale. #### What
     is this used for?

   The Win32 API has a bunch of multibyte functions - all of those that
end with ...A(), and on which we spend so much effort in
intl-encap-win32.c.  These appear to ALWAYS use the ANSI code page of
the system-default locale (GetACP(), CP_ACP).  Note that this applies
also, for example, to the encoding of filenames in all file-handling
routines, including the CRT ones such as open(), because they pass their
args unchanged to the Win32 API.


File: internals.info,  Node: Unicode support under Windows,  Next: The golden rules of writing Unicode-safe code,  Prev: More about locales,  Up: Microsoft Windows-Related Multilingual Issues

25.12.5 Unicode support under Windows
-------------------------------------

Basically, the whole concept of locales and code pages is broken,
because it is extremely messy to support and does not allow for
documents that use multiple languages simultaneously.  Unicode was
designed in response to this, the idea being to create a single
character set that could be used to encode all the world's languages.
Windows has supported Unicode since the beginning of the Win32 API.
Internally, every code page has an associated table to convert the
characters of that code page to and from Unicode, and the Win32 API
itself probably (perhaps always) uses Unicode internally.

   Under Windows there are two different versions of all library
routines that accept or return text, those that handle Unicode text and
those handling "multibyte" text, i.e. variable-width ASCII-compatible
text in some national format such as EUC or Shift-JIS.  Because Windows
95 basically doesn't support Unicode but Windows NT does, and Microsoft
doesn't provide any way of writing a single binary that will work on
both systems and still use Unicode when it's available (although see
below, Microsoft Layer for Unicode), we need to provide a way of
run-time conditionalizing so you could have one binary for both
systems.  "Unicode-splitting" refers to writing code that will handle
this properly.  This means using Qmswindows_tstr as the external
conversion format, calling the appropriate qxe...() Unicode-split
version of library functions, and doing other things in certain cases,
e.g. when a qxe() function is not present.

   Unicode support also requires that the various Windows API's be
"Unicode-encapsulated", so that they automatically call the ANSI or
Unicode version of the API call appropriately and handle the size
differences in structures.  What this means is:

   * first, note that Windows already provides a sort of encapsulation
     of all API's that deal with text.  All such API's are underlyingly
     provided in two versions, with an A or W suffix (ANSI or "wide"
     i.e. Unicode), and the compile-time constant UNICODE controls
     which is selected by the unsuffixed API.  Same thing happens with
     structures, and also with types, where the generic types have
     names beginning with T - TCHAR, LPTSTR, etc..  Unfortunately, this
     is compile-time only, not run-time, so not sufficient. (Creating
     the necessary run-time encoding is not conceptually difficult, but
     very time-consuming to write.  It adds no significant overhead,
     and the only reason it's not standard in Windows is conscious
     marketing attempts by Microsoft to cripple Windows 95.  FUCK
     MICROSOFT!  They even describe in a KnowledgeBase article exactly
     how to create such an API [although we don't exactly follow their
     procedure], and point out its usefulness; the procedure is also
     described more generally in Nadine Kano's book on Win32
     internationalization - written SIX YEARS AGO!  Obviously Microsoft
     has such an API available internally.)

   * what we do is provide an encapsulation of each standard Windows
     API call that is split into A and W versions.  current theory is
     to avoid all preprocessor games; so we name the function with a
     prefix - "qxe" currently - and require callers to use the prefixed
     name.  Callers need to explicitly use the W version of all
     structures, and convert text themselves using Qmswindows_tstr.
     the qxe encapsulated version will automatically call the
     appropriate A or W version depending on whether we're running on
     9x or NT (you can force use of the A calls on NT, e.g. for testing
     purposes, using the command- line switch -nuni aka
     -no-unicode-lib-calls), and copy data between W and A versions of
     the structures as necessary.

   * We require the caller to handle the actual translation of text to
     avoid possible overflow when dealing with fixed-size Windows
     structures.  There are no such problems when copying data between
     the A and W versions because ANSI text is never larger than its
     equivalent Unicode representation.

   NOTE NOTE NOTE: As of August 2001, Microsoft (finally!  See my nasty
comment above) released their own Unicode-encapsulation library, called
Microsoft Layer for Unicode on Windows 95/98/Me Systems.  It tries to be
more transparent than we are, in that

   * its routines do ANSI/Unicode string translation, while we don't,
     for efficiency (we already have to do internal/external conversion
     so it's no extra burden to do the proper conversion directly
     rather than always converting to Unicode and then doing a second
     conversion to ANSI as necessary)

   * rather than requiring separately-named routines (qxeFooBar), they
     physically override the existing routines at the link level.  it
     also appears that they do this BADLY, in that if you link with the
     MLU, you get an application that runs ONLY on Win9x!!! (hint - use
     GetProcAddress()).  there's still no way to create a single binary!
     fucking losers.

   * they assume you compile with UNICODE defined, so there's no need
     for the application to explicitly use ...W structures, as we
     require.

   * they also intercept windows procedures to deal with notify
     messages as necessary, which we don't do yet.

   * they (of course) don't use Extbyte.

   at some point (especially when they fix the single-binary problem!),
we should consider switching.  for the meantime, we'll stick with what
i've already written.  perhaps we should think about adopting some of
the greater transparency they have; but i opted against transparency on
purpose, to make the code easier to follow for someone who's not
familiar with it.  until our library is really complete and bug-free,
we should think twice before doing this.

   According to Microsoft documentation, only the following functions
are provided under Windows 9x to support Unicode (see MSDN page "Windows
95/98/Me General Limitations"):

   EnumResourceLanguagesW EnumResourceNamesW EnumResourceTypesW
ExtTextOutW FindResourceW FindResourceExW GetCharWidthW GetCommandLineW
GetTextExtentPointW GetTextExtentPoint32W lstrcatW lstrcpyW lstrlenW
MessageBoxW MessageBoxExW MultiByteToWideChar TextOutW
WideCharToMultiByte

   also maybe GetTextExtentExPoint? (KB Q125671 "Unicode Functions
Supported by Windows 95")

   Q210341 says this in addition:

     SUMMARY:

     Although Windows 95 is an eight-bit ANSI, or for Far East Windows,
     a Multibyte (MBCS) character set operating system, it implements a
     few Unicode functions. Windows 98 has added support for a few more
     functions and there are techniques to implement additional Unicode
     support.

     MORE INFORMATION:

     Windows 95 is natively an eight-bit character code operating
     system. That is, it fundamentally processes all character strings
     one byte at a time. Far East versions of Windows 95 are called
     Multibyte Character Set (MBCS) systems because they use a signal
     or lead byte combined with a second trailing byte to expand the
     character code range beyond the 256 limitation of a one-byte
     representation.

     The Unicode standard offers application developers an opportunity
     to work with text without the limitations of character set based
     systems. For more information on the Unicode standard see the
     "References" section of this article. Windows NT is a fully Unicode
     capable operating system so it may be desirable to write software
     that supports Unicode on Windows 95.

     Even though Windows 95 and Windows 98 are not Unicode based, they
     do provide some limited Unicode functionality. Drawing of Unicode
     text is possible because the TrueType fonts that are used by
     Windows are encoded using Unicode. Therefore, a small subset of
     Win32 functions have wide character (Unicode) equivalents that are
     implemented in Windows 95. To review the list of these functions
     that was first published for Windows 95 see the white paper listed
     in the "References" section of this article.

     The Quick Info information in the Platform SDK describes the
     following wide character functions as implemented on Windows 95:

     [same list as above minus GetTextExtentExPoint, and minus
     lstrcpy/lstrcat]

     For Windows 98, there have been two more functions implemented:

     [lstrcpyW/lstrcatW]

     Also available to applications on Windows 95 and later is the
     CF_UNICODETEXT clipboard format for exchanging/converting Unicode
     text across the clipboard. See Nadine Kano's book listed in the
     "References" section of this article.

     With this API subset, an application can read, write, display, and
     convert Unicode data. However, in some cases an application
     developer working with Unicode may find a need to work directly
     with the glyphs in the TrueType font file.

     Such a case arises if a software developer would like to use the
     services of the GetGlyphOutline() function. Unfortunately, there
     is no wide character implementation of this function on Windows
     95. However, this function does work with TrueType glyph indices
     so the solution is convert the Unicode character code to a glyph
     index.

     A developer might also want to take advantage of the TrueType Open
     tables of a font to perform ligature or contextual glyph
     substitution. To do this, the application would need to work with
     glyph indices. See the "References" section of this article for
     more information on converting Unicode to glyph indices.

     REFERENCES:

     For additional information about Unicode and the GetGlyphOutline
     function, click the article number below to view the article in the
     Microsoft Knowledge Base:

     241358 PRB: The GetGlyphOutlineW Function Fails on Windows 95 and
     Windows 98

     For additional information about converting Unicode character
     codes, click the article number below to view the article in the
     Microsoft Knowledge Base:

     241020 HOWTO: Translate Unicode Character Codes to TrueType Glyph
     Indices in Windows 95

     For information on writing applications for world wide markets,
     please see the following book:

     Developing International Software for Windows 95 and Windows NT by
     Nadine Kano.  ISBN 1-55615-840-8 Microsoft Press.  Also available
     on MSDN in the Books section.

     Background white paper: Differences in Win32 API Implementations
     Among Windows Operating Systems by Noel Nyman.

     Available on MSDN in the Windows Platform Guidelines section

   However, the C runtime library provides some additional support
(according to the CRT sources, as the docs are not very clear on this):

   * wmain() is completely supported, and appropriate Unicode-formatted
     argv and envp will always be passed.

   * Likewise, wWinMain() is completely supported. (NOTE: The docs are
     not at all clear on how these various entry points interact, and
     implies that a windows-subsystem program "must" use WinMain(),
     while a console- subsystem program "must" use main(), and a
     program compiled with UNICODE (which we don't, see above) "must"
     use the w*() versions, while a program not compiled this way
     "must" use the plain versions.  In fact it appears that the CRT
     provides four different compiler entry points, namely
     w?(main|WinMain)CRTStartup, and we simply choose the one we like
     using the appropriate link flag.

   * _wenviron, _wputenv

   NOTE:

   * wsetargv.obj uses routines that were buggily left out of MSVCRT;
     anyway, from looking at the source, it does NOT correctly work
     under Win 9x as it blindly calls the Unicode version of
     Unicode-split API's such as FindFirstFile)

   * the w*() file routines are *NOT* supported - or at least, they
     blindly call the ...W() versions of the Win32 API calls.


File: internals.info,  Node: The golden rules of writing Unicode-safe code,  Next: The format of the locale in setlocale(),  Prev: Unicode support under Windows,  Up: Microsoft Windows-Related Multilingual Issues

25.12.6 The golden rules of writing Unicode-safe code
-----------------------------------------------------

   * There are no preprocessor games going on.

   * Do not set the UNICODE constant.

   * You need to change your code to call the Windows API prefixed with
     "qxe" functions (when they exist) and use the ...W structs instead
     of the generic ones.  String arguments in the qxe functions are of
     type Extbyte *.

   * You code is responsible for conversion of text arguments.  We try
     to handle everything else - the argument differences, the copying
     back and forth of structures, etc.  Use Qmswindows_tstr and macros
     such as C_STRING_TO_TSTR.  You are also responsible for
     interpreting and specifying string sizes, which have not been
     changed.  Usually these are in characters, meaning you need to
     divide by XETCHAR_SIZE. (But, some functions want sizes in bytes,
     even with Unicode strings.  Look in the documentation.) Use XETEXT
     when specifying string constants, so that they show up in Unicode
     as necessary.

   * If you need to process external strings (in general you should not
     do this; do all your manipulations in internal format and convert
     at the point of entry into or exit from the function), use the
     xet...() functions.

   * If you have to declare a fixed array to hold a string coming from
     Windows (and hence either multibyte or Unicode), declare it of type
     Extbyte[] and multiply the size by MAX_XETCHAR_SIZE.


File: internals.info,  Node: The format of the locale in setlocale(),  Next: Random other Windows I18N docs,  Prev: The golden rules of writing Unicode-safe code,  Up: Microsoft Windows-Related Multilingual Issues

25.12.7 The format of the locale in setlocale()
-----------------------------------------------

It appears that under Unix the standard format for the string in
setlocale() involves two-letter language and country abbreviations, e.g.
ja or ja_jp or ja_jp.euc for Japanese.  Windows (MSDN article "Language
Strings" in the run-time reference appendix, see doc list above) speaks
of "(primary) language" and "sublanguage" (usually a country, but in the
case of Chinese the sublanguage is "simplified" or "traditional").  It
is highly flexible in what it takes, and thankfully it canonicalizes the
result to a unique form "Language_Country.Encoding".  It allows (note
that all specifications can be in any case):

   * the full "language_country.encoding" specification or just
     language_country", in which case the default encoding will be
     chosen.

   * a three-letter acronym, consisting of the ISO-standard two-letter
     language abbreviation followed by a third letter indicating the
     sublanguage.

   * just a language name, e.g. "dutch", standing for the combination of
     the language with "default" as sublanguage, referring to the
     default (often "prototypical") country for that language (in this
     case the Netherlands).  You can abbreviate the name by removing
     any number of letters from the end.  Ambiguity is not a problem:
     Even specifying just a single letter is valid providing any
     language starting with that letter exists, but the result may not
     be what you want (e.g. "c" maps to "catalan", not "chinese",
     "czech", etc.).  The way of resolving ambiguity appears fairly
     random - it's not alphabetical ("a" maps to "arabic" not
     "albanian").

   * a combination of language and sublanguage separated by a hyphen,
     e.g. "dutch-belgian"; note that the sublanguage designator in this
     case is NOT necessarily the same as the country, e.g. "belgian" vs.
     "belgium".  "dutch-belgium" (or even "dutch-belg") does *NOT* get
     you the right result, but returns "Dutch_Netherlands.1252"
     instead!  This is because, although you may not abbreviate the
     result, Windows accepts any unknown value in the sublanguage field
     and treats it as equivalent to "default".  Note also that the if
     the sublanguage name has underscores in it, you need to change
     them to spaces, e.g.  "spanish-dominican republic".

   * sometimes, just a sublanguage name, e.g. "belgian", standing for
     the combination of one of the languages spoken in that region and
     the sublanguage of the region - in this case Dutch.  Note that
     there is no guarantee of "protypicality" in this case in choice of
     language!  You could hardly say that Dutch (aka Flemish) is more
     prototypical of Belgium than French.  You cannot abbreviate this
     form, if it's allowed at all.

   In addition:

   * note further that you are not limited to the language/sublanguage
     combinations predefined by Windows.  You can set weird combinations
     like "Chinese_Kenya.1255" (Chinese spoken in Kenya, represented by
     Windows-1255, i.e. Hebrew!) and Windows don't complain, despite the
     language-encoding inconsistency.  You can also make up a weird
     combination and leave out the encoding, e.g. "Chinese_Qatar", which
     maps to "Chinese_Qatar.1256", where Windows-1256 is Arabic - i.e.
     it appears to be choosing the encoding based on a default for the
     country.

   * note also that the names for countries are often not what you
     expect.  "urdu_pakistan" fails, and just "urdu" shows why, as it
     maps to "Urdu_Islamic Republic of Pakistan.1256".  That is, some
     countries exist in their full name, and the canonicalized form
     with underscore is not very forgiving in its handling of country
     specifications.  Similarly, Uzbekistan is "Republic of
     Uzbekistan", and "China" is "People's Republic of China" - but in
     this latter case, unlike the other two, just "China" works as an
     alias, e.g. "uzbek_china" maps to "Uzbek_People's Republic of
     China.936".

   * note that just the two-letter ISO language code is NOT allowed.
     Sometimes you'll get lucky (e.g. "fr" does map to "france"), but
     sometimes you'll get no match (e.g. "pl"), and sometimes you'll get
     really unlucky in that the call will succeed but with the wrong
     language (e.g. "es" maps to "estonian", not "spanish").

   As an example, MSDN article "Language Strings" indicates that German
(default) can be specified using "deu" or "german"; German (Austrian)
with "dea" or "german-austrian"; German (Swiss) with "des",
"german-swiss", or "swiss"; French (Swiss) with "french-swiss" or "frs";
and English (USA) with "american", "american english",
"american-english", "english-american", "english-us", "english-usa",
"enu", "us", or "usa".  This is not, of course, an exhaustive list even
for just the given locales - just "english" works in practice because
English (Default) maps to English (USA). (#### Is this always the case?)

   Given the canonicalization, we don't have to worry too much about the
different kinds of inputs to setlocale() - unlike for Unix, where no
canonicalization is usually performed, the particular locales that
exist vary tremendously from OS to OS, and we need to parse the
uncanonicalized locale spec, directly from the user, to figure out the
encoding to use, making various guesses if not enough information is
present.  Yuck!  The tricky thing under Windows is figuring how to deal
with the sublang.  It appears that the trick of simply passing the text
of the manifest constant itself of the sublang, with appropriate
hacking (e.g. of underscore to space), works most of the time.


File: internals.info,  Node: Random other Windows I18N docs,  Prev: The format of the locale in setlocale(),  Up: Microsoft Windows-Related Multilingual Issues

25.12.8 Random other Windows I18N docs
--------------------------------------

Introduction to Internationalization Issues in the Win32 API

   Abstract: This page provides an overview of the aspects of the Win32
internationalization API that are relevant to XEmacs, including the
basic distinction between multibyte and Unicode encodings. Also
included are pointers to how XEmacs should make use of this API.

   The Win32 API is quite well-designed in its handling of strings
encoded for various character sets. The API is geared around the idea
that two different methods of encoding strings should be supported.
These methods are called multibyte and Unicode, respectively. The
multibyte encoding is compatible with ASCII strings and is a more
efficient representation when dealing with strings containing primarily
ASCII characters, but it has a great number of serious deficiencies and
limitations, including that it is very difficult and error-prone to
work with strings in this encoding, and any particular string in a
multibyte encoding can only contain characters from a very limited
number of character sets. The Unicode encoding rectifies all of these
deficiencies, but it is not compatible with ASCII strings (in other
words, an existing program will not be able to handle the encoded
strings unless it is explicitly modified to do so), and it takes up
twice as much memory space as multibyte encodings when encoding a
purely ASCII string.

   Multibyte encodings use a variable number of bytes (either one or
two) to represent characters. ASCII characters are also represented by a
single byte with its high bit not set, and non-ASCII characters are
represented by one or two bytes, the first of which always has its high
bit set. (The second byte, when it exists, may or may not have its high
bit set.) There is no single multibyte encoding. Instead, there is
generally one encoding per non-ASCII character set. Such an encoding is
capable of representing (besides ASCII characters, of course) only
characters from one (or possibly two) particular character sets.

   Multibyte encoding makes processing of strings very difficult. For
example, given a pointer to the beginning of a character within a
string, finding the pointer to the beginning of the previous character
may require backing up all the way to the beginning of the string, and
then moving forward. Also, an operation such as separating out the
components of a path by searching for backslashes will fail if it's
implemented in the simplest (but not multibyte-aware) fashion, because
it may find what appears to be a backslash, but which is actually the
second byte of a two-byte character. Also, the limited number of
character sets that any particular multibyte encoding can represent
means that loss of data is likely if a string is converted from the
XEmacs internal format into a multibyte format.

   For these reasons, the C code in XEmacs should never do any sort of
work with multibyte encoded strings (or with strings in any external
encoding for that matter). Strings should always be maintained in the
internal encoding, which is predictable, and converted to an external
encoding only at the point where the string moves from the XEmacs C
code and enters a system library function. Similarly, when a string is
returned from a system library function, it should be immediately
converted into the internal coding before any operations are done on it.

   Unicode, unlike multibyte encodings, is a fixed-width encoding where
every character is represented using 16 bits. It is also capable of
encoding all the characters from all the character sets in common use
in the world. The predictability and completeness of the Unicode
encoding makes it a very good encoding for strings that may contain
characters from many character sets mixed up with each other. At the
same time, of course, it is incompatible with routines that expect
ASCII characters and also incompatible with general string manipulation
routines, which will encounter a great number of what would appear to
be embedded nulls in the string. It also takes twice as much room to
encode strings containing primarily ASCII characters. This is why
XEmacs does not use Unicode or similar encoding internally for buffers.

   The Win32 API cleverly deals with the issue of 8 bit vs. 16 bit
characters by declaring a type called TCHAR which specifies a generic
character, either 8 bits or 16 bits. Generally TCHAR is defined to be
the same as the simple C type char, unless the preprocessor constant
UNICODE is defined, in which case TCHAR is defined to be WCHAR, which
is a 16 bit type. Nearly all functions in the Win32 API that take
strings are defined to take strings that are actually arrays of TCHARs.
There is a type LPTSTR which is defined to be a string of TCHARs and
another type LPCTSTR which is a const string of TCHARs. The theory is
that any program that uses TCHARs exclusively to represent characters
and does not make assumptions about the size of a TCHAR or the way that
the characters are encoded should work transparently regardless of
whether the UNICODE preprocessor constant is defined, which is to say,
regardless of whether 8 bit multibyte or 16 bit Unicode characters are
being used. The way that this is actually implemented is that every
Win32 API function that takes a string as an argument actually maps to
one of two functions which are suffixed with an A (which stands for
ANSI, and means multibyte strings) or W (which stands for wide, and
means Unicode strings). The mapping is, of course, controlled by the
same UNICODE preprocessor constant. Generally all structures containing
strings in them actually map to one of two different kinds of
structures, with either an A or a W suffix after the structure name.

   Unfortunately, not all of the implementations of the Win32 API
implement all of the functionality described above. In particular,
Windows 95 does not implement very much Unicode functionality. It does
implement functions to convert multibyte-encoded strings to and from
Unicode strings, and provides Unicode versions of certain low-level
functions like ExtTextOut(). In fact, all of the rest of the Unicode
versions of API functions are just stubs that return an error.
Conversely, all versions of Windows NT completely implement all the
Unicode functionality, but some versions (especially versions before
Windows NT 4.0) don't implement much of the multibyte functionality.
For this reason, as well as for general code cleanliness, XEmacs needs
to be written in such a way that it works with or without the UNICODE
preprocessor constant being defined.

   Getting XEmacs to run when all strings are Unicode primarily involves
removing any assumptions made about the size of characters. Remember
what I said earlier about how the point of conversion between
internally and externally encoded strings should occur at the point of
entry or exit into or out of a library function. With this in mind, an
externally encoded string in XEmacs can be treated simply as an
arbitrary sequence of bytes of some length which has no particular
relationship to the length of the string in the internal encoding.

   Use Qnative for Unix conversion, Qmswindows_tstr for Windows ...

   String constants that are to be passed directly to Win32 API
functions, such as the names of window classes, need to be bracketed in
their definition with a call to the macro XETEXT. This appropriately
makes a string of either regular or wide chars, which is to say this
string may be prepended with an L (causing it to be a wide string)
depending on XEUNICODE_P.


File: internals.info,  Node: Modules for Internationalization,  Prev: Microsoft Windows-Related Multilingual Issues,  Up: Multilingual Support

25.13 Modules for Internationalization
======================================

     `mule-canna.c'
     `mule-ccl.c'
     `mule-charset.c'
     `mule-charset.h'
     `file-coding.c'
     `file-coding.h'
     `mule-coding.c'
     `mule-mcpath.c'
     `mule-mcpath.h'
     `mule-wnnfns.c'
     `mule.c'

   These files implement the MULE (Asian-language) support.  Note that
MULE actually provides a general interface for all sorts of languages,
not just Asian languages (although they are generally the most
complicated to support).  This code is still in beta.

   `mule-charset.*' and `file-coding.*' provide the heart of the XEmacs
MULE support.  `mule-charset.*' implements the "charset" Lisp object
type, which encapsulates a character set (an ordered one- or
two-dimensional set of characters, such as US ASCII or JISX0208 Japanese
Kanji).

   `file-coding.*' implements the "coding-system" Lisp object type,
which encapsulates a method of converting between different encodings.
An encoding is a representation of a stream of characters, possibly
from multiple character sets, using a stream of bytes or words, and
defines (e.g.) which escape sequences are used to specify particular
character sets, how the indices for a character are converted into bytes
(sometimes this involves setting the high bit; sometimes complicated
rearranging of the values takes place, as in the Shift-JIS encoding),
etc.  It also contains some generic coding system implementations, such
as the binary (no-conversion) coding system and a sample gzip coding
system.

   `mule-coding.c' contains the implementations of text coding systems.

   `mule-ccl.c' provides the CCL (Code Conversion Language)
interpreter.  CCL is similar in spirit to Lisp byte code and is used to
implement converters for custom encodings.

   `mule-canna.c' and `mule-wnnfns.c' implement interfaces to external
programs used to implement the Canna and WNN input methods,
respectively.  This is currently in beta.

   `mule-mcpath.c' provides some functions to allow for pathnames
containing extended characters.  This code is fragmentary, obsolete, and
completely non-working.  Instead, `pathname-coding-system' is used to
specify conversions of names of files and directories.  The standard C
I/O functions like `open()' are wrapped so that conversion occurs
automatically.

   `mule.c' contains a few miscellaneous things.  It currently seems to
be unused and probably should be removed.

     `intl.c'

   This provides some miscellaneous internationalization code for
implementing message translation and interfacing to the Ximp input
method.  None of this code is currently working.

     `iso-wide.h'

   This contains leftover code from an earlier implementation of
Asian-language support, and is not currently used.


File: internals.info,  Node: Consoles; Devices; Frames; Windows,  Next: The Redisplay Mechanism,  Prev: Multilingual Support,  Up: Top

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

* Menu:

* Introduction to Consoles; Devices; Frames; Windows::
* Point::
* Window Hierarchy::
* The Window Object::
* Modules for the Basic Displayable Lisp Objects::


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

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


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

26.2 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'.


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

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

