From 71bdb35d52747e6d7d9f55df4524d57c2966be94 Mon Sep 17 00:00:00 2001 From: "Jeffrey H. Kingston" Date: Tue, 14 Sep 2010 19:21:41 +0000 Subject: Lout 3.17. git-svn-id: http://svn.savannah.nongnu.org/svn/lout/trunk@2 9365b830-b601-4143-9ba8-b4a8e2c3339c --- doc/design/s6_2 | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) create mode 100644 doc/design/s6_2 (limited to 'doc/design/s6_2') diff --git a/doc/design/s6_2 b/doc/design/s6_2 new file mode 100644 index 0000000..2df5478 --- /dev/null +++ b/doc/design/s6_2 @@ -0,0 +1,79 @@ +@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 -- cgit