diff options
Diffstat (limited to 'doc/design/s5_2')
| -rw-r--r-- | doc/design/s5_2 | 372 |
1 files changed, 372 insertions, 0 deletions
diff --git a/doc/design/s5_2 b/doc/design/s5_2 new file mode 100644 index 0000000..a81630d --- /dev/null +++ b/doc/design/s5_2 @@ -0,0 +1,372 @@ +@SubSection + @Tag { flushing } + @Title { The galley flushing algorithm } +@Begin +@PP +Galley components are promoted one by one into the point of appearance in +the dynamic parent galley, then carried along with it, ultimately to the +root galley and the output file. This process is called @I galley +{@I flushing}: the galleys are rivers running together to the sea, and +each component is a drop of water. +@PP +Here is a snapshot of a small dynamic tree, based on the @Code "@PageList" +definitions of Section {@NumberOf recursion}: +@ID @Fig { + +@I 10p @Font { output file } A:: @Box linestyle { noline } margin { 0c } + +||2c + +{ +@I 10p @Font { root galley } +//0.2c +B:: @Box margin { 0c } linestyle { noline } +// +@LittlePage { +|0.5rt - 1 - +//1.2vx &2m A small +//1.2vx @Code "@Galley" * C:: @Box margin { 0.01c } linestyle { noline } +//1rt @Code "@FootSect" +} +// +@Box margin { 0.3c } 2.8c @Wide 8p @Font @Code "@PageList 2" +} + +||2c + +{ +//0.9c @I 10p @Font { body text } +//0.2c D:: @Box margin { 0.3c } 2.8c @Wide 8p @Font paragraph +// @Box margin { 0.3c } 2.8c @Wide 8p @Font { of text. } +// @Box margin { 0.3c } 2.8c @Wide @Code 8p @Font "@Input" +} + +// @Arrow from { B@W } to { A@E } +// @Arrow from { D@W } to { C@E } + +} +The components of the body text galley are lines, except for the special +receptive symbol @Code "@Input" which is a placeholder for as yet unread +input (Section {@NumberOf lookahead}). The components of the root galley are +pages, except for the concluding unexpanded invocation of {@Code "@PageList"}, +which is an inexhaustible source of more pages, expanded on demand. +@PP +The concrete data structure used by Basser Lout permits the galley +flushing algorithm to navigate the dynamic tree and find significant +features quickly: +@ID 10p @Font @Fig maxlabels { 100 } { + +A:: @Ellipse @I { HEAD } + +||1.5c + +@OneCol @OneRow { +B:: @Ellipse @I { RECEIVING * } +// @Arrow from { A@CTR ++ {A@CTR @Angle B@W A@CIRCUM} } to { B@W } +//0.6c +C:: @Ellipse @I { RECEPTIVE } +// @Arrow from { A@CTR ++ {A@CTR @Angle C@W A@CIRCUM} } to { C@W } +//0.6c +D:: @Box margin { 0c } linestyle { noline } +// @Arrow from { A@CTR ++ {A@CTR @Angle D@NW A@CIRCUM} } to { D@NW } +// +@LittlePage { +|0.5rt - 1 - +//1.2vx &2m A small +//1.2vx E:: @Box margin { 0c } linestyle { noline } @Code "@Galley " +//1rt F:: @Box margin { 0c } linestyle { noline } @Code "@FootSect " +} +// @FunnyArrow arrow { forward } from { B@E } to { E@E } +// @FunnyArrow arrow { forward } from { C@E } to { F@E } +//0.6c +C:: @Ellipse @I { GAP } +// @Arrow from { A@CTR ++ {A@CTR @Angle C@W A@CIRCUM} } to { C@W } +//0.6c +C:: @Ellipse @I { RECEPTIVE } +// @Arrow from { A@CTR ++ {A@CTR @Angle C@W A@CIRCUM} } to { C@W } +//0.6c +D:: @Box margin { 0.3c } 2.8c @Wide 8p @Font @Code "@PageList 2" +// @Arrow from { A@CTR ++ {A@CTR @Angle D@NW A@CIRCUM} } to { D@NW } +// @FunnyArrow from { C@E } to { D@W ++ { 1.8 cm 0 } } +} + +||1.0c + +A:: @Ellipse @I { HEAD } +& @Arrow from { B@E } to { A@W } + +||1.5c + +@OneCol @OneRow { +B:: @Box margin { 0.3c } 2.8c @Wide 8p @Font paragraph +// @Arrow from { A@CTR ++ {A@CTR @Angle B@W A@CIRCUM} } to { B@W } +//0.6c +B:: @Ellipse @I { GAP } +// @Arrow from { A@CTR ++ {A@CTR @Angle B@W A@CIRCUM} } to { B@W } +//0.6c +B:: @Box margin { 0.3c } 2.8c @Wide 8p @Font { of text. } +// @Arrow from { A@CTR ++ {A@CTR @Angle B@NW A@CIRCUM} } to { B@NW } +//0.6c +B:: @Ellipse @I { GAP } +// @Arrow from { A@CTR ++ {A@CTR @Angle B@W A@CIRCUM} } to { B@W } +//0.6c +B:: @Ellipse @I { RECEPTIVE } +// @Arrow from { A@CTR ++ {A@CTR @Angle B@W A@CIRCUM} } to { B@W } +//0.6c +C:: @Box margin { 0.3c } 2.8c @Wide 8p @Font @Code "@Input" +// @Arrow from { A@CTR ++ {A@CTR @Angle C@NW A@CIRCUM} } to { C@NW } +// @FunnyArrow from { B@E } to { C@W ++ { 1.2 cm 0 } } +} + +} +Each galley has a @Eq { HEAD } node whose children are its component +objects, separated by @Eq { GAP } nodes recording the inter-component +gaps. +@PP +Each component is preceded by zero or more @I {galley index nodes} of +various types. Every receptive symbol has a @Eq { RECEPTIVE } index pointing +to it, so that it can be found without searching through its +component. If the symbol is currently the target of a galley, it has a +@Eq { RECEIVING } index instead which is also linked to the incoming +galley. Galleys that are currently without a target are linked to the +dynamic tree by @Eq { UNATTACHED } galley indexes, either just after their +most recent target if there has been one, or else at their point of +invocation. +@PP +Each galley should be thought of as a concurrent process, although the +implementation in C uses coroutines implemented by procedures. A galley +may promote its first component only if it has a target, sufficient space +is available at the target to receive the component, and the component +contains no receptive symbols. This last condition seems to be the key +to galley synchronization: it forces a bottom-up promotion regime, +preventing pages from flushing to output before text flushes into them, +for example. +@PP +Each galley contains a number of binary semaphores, shown as asterisks +in our snapshots when set. At any given moment, a galley process is +either running or else is suspended on one of its own semaphores. The +@Eq { HEAD } node contains a semaphore which is set when the galley has tried +to find a target and failed. Each receptive symbol has a semaphore +which is set when that symbol is preventing the first component from +being promoted. +@PP +For example, in the snapshot at the beginning of this section, the root +galley is suspended on the @Code "@Galley" symbol, but the text galley +is running. It will suspend on the @Code "@Input" symbol after the +first two components are promoted. +@PP +Every galley {@I G}, be it a list of pages, body text, a footnote, or +whatever, executes the following algorithm in parallel with every other +galley: +@DP +1. Initially @I G is unattached. Search forwards or backwards from its +@Eq { UNATTACHED } index as required, to find a receptive symbol @I S which +can expand to reveal a target for {@I G}. +@DP +2. If no @I S can be found, suspend on the attachment semaphore. Resume +later from step 1. +@DP +3. Expand @I S to reveal the target of {@I G}. Preserve {@I S}'s +semaphore by moving it to the first receptive symbol within the +expansion of {@I S}. +@DP +4. Calculate the available width and height at the target, and if +@I G is still a pure parse tree, use the environment attached to @I G +and the style information from the target to evaluate @I G as in +Section {@NumberOf functional}. +@DP +5. Examine the components of @I G one by one. For each component there +are three possibilities: +@PP +@I ACCEPT. If the component fits into the available space, and has +no other problems, then promote it into the target. If this is the +first component promoted into this target, and @I G is a forcing +galley (Section {@NumberOf lookahead}), delete every receptive symbol +preceding the target in the parent galley. If @I G is the root galley, +render the component on the output file and dispose it; +@PP +@I REJECT. If the component is too large for the available space, or a +@Eq { FOLLOWS } index (described below) forbids its promotion into this +target, then detach @I G from the target. If this was the first component +at this target, @I S has been a complete failure, so undo step 3 (Basser +Lout is not able to undo step 4); otherwise delete the target. Return to +step 1 and continue immediately; +@PP +@I SUSPEND. If the component contains a receptive symbol, it cannot be +promoted yet. If this symbol is the target of a galley that was written +to an auxiliary file on a previous run, read in that galley and flush +it. Otherwise suspend on the receptive symbol's semaphore; resume later +from step 4. +@DP +6. Terminate when the galley is empty. +@DP +At various points in this algorithm, receptive symbols (and their +semaphores) are deleted in the dynamic parent galley, possibly +permitting it to resume flushing. When this happens, Basser Lout resumes +the parent immediately after @I G suspends or terminates. Also, +whenever a component is promoted, any child galleys connected to +it by @Eq { UNATTACHED } indexes must be resumed, since these +galleys may be able to find a target now. A good example of this +situation occurs when a line of body text with one or more footnotes +is promoted onto a page. Basser Lout gives priority to such children, +suspending @I G while each is given a chance to flush. +@PP +Basser Lout searches for the first target of @I G only in regions of the +dynamic tree that will clearly precede or follow {@I G}'s invocation +point in the final printed document, whichever is specified in the +@Code into clause; subsequent targets are sought later in the same +galley as the first. An exception to this rule, whose necessity will +be made clear later, is that a first @Code following target will be +sought within a dynamic sibling galley preceding {@I G}'s invocation +point: +@ID 10p @Font @Fig { + +{ +@I { dynamic parent } +//0.2c +@Box 2.8c @Wide 4.5c @High +{ + //0.5c A:: @Box margin { 0c } linestyle { noline } @Code "@XTarget" + //1.0c C:: @Box margin { 0c } linestyle { noline } @Eq { UNATTACHED } + //1.3c @Code "@XTarget" +} +} + +||1.5c + +{ +//0.6c +B:: @Box margin {0c} linestyle {noline} @Code "X into { @XTarget&&following }" +//0.2c +@Box 2.8c @Wide 1.5c @High { //0.8c @Code "@GTarget" } +//1.0c +D:: @Box margin {0c} linestyle {noline} @Code "G into { @GTarget&&following }" +//0.2c +@Box 2.8c @Wide 2.5c @High {} +} + +// @Arrow from { A@E ++ {0.2 cm 0} } to { B@W -- {0.2 cm 0} } +// @Arrow from { C@E ++ {0.2 cm 0} } to { D@W -- {0.2 cm 0} } + +} +Here @I G will find the @Code "@GTarget" target within {@I X}. This is +dangerous, since if the first component of @I G is then promoted via +@I X into the first {@Code "@XTarget"} rather than into the second, +{@I G}'s target will not appear later in the final printed document than +its invocation point, as required by the @Code into clause. +@PP +Accordingly, when such a target is chosen, two special galley indexes +are inserted and linked together: a @Eq { PRECEDES } index at {@I G}'s +invocation point, and a @Eq { FOLLOWS } index at the first component of +{@I G}. The algorithm checks before promoting any @Eq { FOLLOWS } index +that its promotion would not place it earlier than the corresponding +@Eq { PRECEDES } index in the same galley, and rejects the component if +it would. Since @Eq { PRECEDES } and @Eq { FOLLOWS } indexes are rarely used, +this check can be implemented by linear search. +@PP +When two components are separated by {@Code "/"}, as opposed to the more +usual {@Code "//"}, each influences the horizontal position of the +other. Because of this, the @I SUSPEND action is in fact taken if a +receptive symbol occurs in any component separated from the first by +{@Code "/"} operators only. Again, linear search forwards to the first +{@Code "//"} suffices for this check. +@PP +A good illustration of these unusual cases is afforded by the +@Code "@Align" symbols from the standard DocumentLayout package. These +are used to produce displayed equations, aligned on their equals signs +despite being separated by arbitrary body text. +@PP +The @Code "@Align" symbols are packaged neatly for the convenience of +the non-expert user, but we will show just the essence of the +implementation here. First, an @Code "@AlignList" galley is created +which contains an infinite supply of @Code "@AlignPlace" receptive +symbols separated by @Code "/" operators: +@ID @Fig { + +{ +@I { body text galley } +//0.2c +@Box 2.8c @Wide 4.0c @High +{ //1.5c + A:: @Box margin { 0c } linestyle { noline } @Code "@Galley" +} +} + +||1.5c + +{ +//2.4c +B:: @Box margin { 0c } linestyle { noline } @Code "@AlignList" +//0.2c +@Box { + @Code "@AlignPlace" +//1vx @Code "@AlignPlace" +//1vx @Code "..." +//1vx @Code "@EndAlignList" +} + +} + +// @Arrow from { A@E ++ {0.2 cm 0} } to { B@W -- {0.2 cm 0} } +} +Then equations like +@ID @ShowMarks @Eq { f(x) ^= g(x) + 2 } +are created and sent to @Code "@AlignPlace&&following" targets. They +collect in the @Code "@AlignList" galley and are aligned there: +@ID @Fig { + +{ +@I { body text galley } +//0.2c +@Box 2.8c @Wide 4.0c @High +{ //1.5c + A:: @Box margin { 0c } linestyle { noline } @Code "@Galley" +} +} + +||1.5c + +{ +//2.4c +B:: @Box margin { 0c } linestyle { noline } @Code "@AlignList" +//0.2c +@Box { + @Line linestyle { dashed } from { xmark ysize } to { xmark 0 } + { + @Eq { f(x) ^= g(x) + 2 } + /1vx @Eq { f(x) - g(x) ^= 2 } + /1vx @Code "..." + /1vx @Code "@EndAlignList" + } +} + +} + +// @Arrow from { A@E ++ {0.2 cm 0} } to { B@W -- {0.2 cm 0} } +} +The @Code "@AlignList" galley does not flush, because its first +component is connected to a receptive symbol by @Code "/" operators. +@PP +After the last equation, an empty forcing galley is sent to +{@Code "@EndAlignList"}, deleting the two remaining receptive symbols from +the @Code "@AlignList" galley and permitting it to flush. @Eq { FOLLOWS } +indexes ensure that each equation finds a target placed in the body text +just after its point of invocation, so the equations return, aligned, to +approximately the points where they were invoked. Notice that the flushing +of body text is suspended until the list of equations is completed, as it +must be, since the horizontal position of the first equation cannot +be known until the last equation is added to the list. +@PP +Layout quality can occasionally be improved by rejecting a component +that could be promoted -- for example, a component of body text that +carries a footnote too large to fit on the current page. Since Lout +does not specify how breaking decisions are made, beyond the basic +constraints imposed by available space and @Code into clauses, in +principle such high quality breaking could be added to the +implementation with no change to the language. However, the +generality of the galley flushing algorithm, and its already +considerable complexity, make this a daunting problem in practice, +although a fascinating one. @TeX [9], with its unnested +set of `floating insertions' clearly identifiable as each page is begun, +has the advantage in this respect. +@End @SubSection |