@SubSection
    @Tag { cross.impl }
    @Title { Implementation of cross references }
@Begin
@PP
Before an object can be sized and printed, the values of any cross
references within it must be known.  If they refer to invocations that
have not yet been read, there is a problem.  Scribe [7]
solves it by capitalizing on the fact that documents are formatted
repeatedly during the drafting process.  All tagged invocations are
copied to an auxiliary file during the first run, and indexed for quick
retrieval on the second.  A new auxiliary file is written during the second
run, for retrieval on the third, and so on.  Cross references always lag
one run behind the rest of the document; a perfect copy may be produced
by formatting the same version twice, except in a few pathological cases
that fail to converge.
@PP
Cross referencing in Lout is implemented on top of a simple database
system.  Each database is either writable or readable but not both at
once, and holds a set of key-value entries:  the keys are @S ASCII
strings, and the values are Lout objects, possibly with environments,
written in Lout source.  Operations are provided for writing an entry,
converting from writable to readable, retrieval by key, and sequential
retrieval in key order.
@PP
The implementation, which is quite unsophisticated, employs one or more
@S ASCII {@I{ database files}}, containing the values, and one @S ASCII
{@I{ index file}} per database, containing the keys.  To write an entry,
the value is first appended to a database file, then a line like
@ID @Code "@Chapter&&intro  ch1.ld  57"
is appended to the index file, giving the file and offset where the value
is stored.  To convert from writable to readable, the index file is
sorted.  Then retrieval by key requires a binary search of the index
file and one seek into a database file, and sequential retrieval by key
is trivial.
@PP
This database system is used in several ways.  For an external database,
say of bibliographic references, the user creates the database file of
values (without environments), Lout creates the index file whenever it
cannot find one, and retrievals by key proceed as usual.  Cross
references with tags other than @Code preceding and @Code following are
treated as described above, by writing all tagged invocations (with
environments) to a single database, which is converted to readable at
the end of the run for retrievals on the next run.  Sorted galleys, such
as index entries, are written out indexed by target and key and retrieved
sequentially on the next run.  Unsorted galleys with preceding targets
which pop off the top of the root galley without finding a target, such
as entries in tables of contents, are treated similarly, except that they
are indexed by target and a sequence number that preserves their relative
order during the sort.
@PP
When Lout processes a multi-file document, one cross reference database
file is written for each input file, but they share a common index
file.  At end of run, the new index file is sorted and merged with the
old one in such a way as to preserve entries relating to files not read
on the current run.  This provides some support for piecemeal
formatting, but eventually the files must all be formatted together.
@PP
When a @Code preceding or @Code following cross reference is found,
it is attached to a galley index of type @Eq { CROSS_PREC } or
{@Eq { CROSS_FOLL }}, together with an automatically generated tag composed
of the current file name and a sequence number.  When a tagged
invocation is found, it is attached to a @Eq { CROSS_TARG } index.  These
galley indexes are carried along through the dynamic tree, and
eventually pop off the top of the root galley, at which point it is easy
to determine which cross references refer to which invocations, since
the indexes are now in final printed document order.  Each referenced
invocation is then written to the cross reference database, multiply indexed 
by the generated tags of the associated cross references.  On the next
run, when the same @Code preceding and @Code following cross references
are found, chances are good that the same tags will be generated, and
the appropriate values can be retrieved from the database immediately.
@PP
This approach was the genesis of the @Code "@Tagged" operator, whose
implementation is now immediate: for each @Code "@Tagged" operator we
produce one @Eq { CROSS_PREC } or @Eq { CROSS_FOLL } galley index,
replacing the generated tag with the right parameter of the @Code "@Tagged"
operator.  Nothing more is required.
@End @SubSection