366  PART 45: THE PAGE BUILDER  TEX82 §980

980. The page builder. When TEX appends new material to its main vlist in vertical mode, it uses a method something like vsplit to decide where a page ends, except that the calculations are done “on line” as new items come in. The main complication in this process is that insertions must be put into their boxes and removed from the vlist, in a more-or-less optimum manner.

We shall use the term “current page” for that part of the main vlist that is being considered as a candidate for being broken off and sent to the user’s output routine. The current page starts at link (page head ), and it ends at page tail . We have page head = page tail if this list is empty.

Utter chaos would reign if the user kept changing page specifications while a page is being constructed, so the page builder keeps the pertinent specifications frozen as soon as the page receives its first box or insertion. The global variable page contents is empty when the current page contains only mark nodes and content-less whatsit nodes; it is inserts only if the page contains only insertion nodes in addition to marks and whatsits. Glue nodes, kern nodes, and penalty nodes are discarded until a box or rule node appears, at which time page contents changes to box there. As soon as page contents becomes non-empty , the current vsize and max depth are squirreled away into page goal and page max depth; the latter values will be used until the page has been forwarded to the user’s output routine. The adjustment is made when page contents changes to box there.

Although page goal starts out equal to vsize, it is decreased by the scaled natural height-plus-depth of the insertions considered so far, and by the corrections for those insertions. Therefore it represents the size into which the non-inserted material should fit, assuming that all insertions in the current page have been made.

The global variables best page break and least page cost correspond respectively to the local variables best place and least cost in the vert break routine that we have already studied; i.e., they record the location and value of the best place currently known for breaking the current page. The value of page goal at the time of the best break is stored in best size.

define inserts only = 1 { page contents when an insert node has been contributed, but no boxes } define box there = 2 { page contents when a box or rule has been contributed }

§981  TEX82  PART 45: THE PAGE BUILDER 367

⟨ Global variables 13 ⟩ +≡ page tail : pointer ; { the final node on the current page } page contents : empty . . box there; { what is on the current page so far? } page max depth: scaled ; { maximum box depth on page being built } best page break : pointer ; { break here to get the best page known so far } least page cost : integer ; { the score for this currently best page } best size: scaled ; { its page goal } 981. The page builder has another data structure to keep track of insertions. This is a list of fourword nodes, starting and ending at page ins head . That is, the first element of the list is node r_{1} = link (page ins head ); node r_{j} is followed by r_{j+1} = link (r_{j}); and if there are n items we have r_{n+1} = page ins head . The subtype field of each node in this list refers to an insertion number; for example, ‘ ’ would correspond to a node whose subtype is qi (250) (the same as the subtype field of the relevant ins node). These subtype fields are in increasing order, and subtype(page ins head ) = qi (255), so page ins head serves as a convenient sentinel at the end of the list. A record is present for each insertion number that appears in the current page.

The type field in these nodes distinguishes two possibilities that might occur as we look ahead before deciding on the optimum page break. If type(r) = inserting , then height (r) contains the total of the heightplus-depth dimensions of the box and all its inserts seen so far. If type(r) = split up, then no more insertions will be made into this box, because at least one previous insertion was too big to fit on the current page; broken ptr (r) points to the node where that insertion will be split, if TEX decides to split it, broken ins (r) points to the insertion node that was tentatively split, and height (r) includes also the natural height plus depth of the part that would be split off.

In both cases, last ins ptr (r) points to the last ins node encountered for box qo(subtype(r)) that would be at least partially inserted on the next page; and best ins ptr (r) points to the last such ins node that should actually be inserted, to get the page with minimum badness among all page breaks considered so far. We have best ins ptr (r) = null if and only if no insertion for this box should be made to produce this optimum page.

The data structure definitions here use the fact that the height field appears in the fourth word of a box node.

define page ins node size = 4 { number of words for a page insertion node }

define inserting = 0 { an insertion class that has not yet overflowed }

define split up = 1 { an overflowed insertion class }

define broken ptr (#) ≡ link (# + 1) { an insertion for this class will break here if anywhere } define broken ins (#) ≡ info(# + 1) { this insertion might break at broken ptr } define last ins ptr (#) ≡ link (# + 2) { the most recent insertion for this subtype } define best ins ptr (#) ≡ info(# + 2) { the optimum most recent insertion }

⟨ Initialize the special list heads and constant nodes 790 ⟩ +≡ subtype(page ins head ) ← qi (255); type(page ins head ) ← split up; link (page ins head ) ← page ins head ; 982. An array page so far records the heights and depths of everything on the current page. This array contains six scaled numbers, like the similar arrays already considered in line break and vert break ; and it also contains page goal and page depth, since these values are all accessible to the user via set page dimen commands. The value of page so far [1] is also called page total . The stretch and shrink components of the corrections for each insertion are included in page so far , but the natural space components of these corrections are not, since they have been subtracted from page goal .

The variable page depth records the depth of the current page; it has been adjusted so that it is at most page max depth. The variable last glue points to the glue specification of the most recent node contributed from the contribution list, if this was a glue node; otherwise last glue = max halfword . (If the contribution list is nonempty, however, the value of last glue is not necessarily accurate.) The variables last penalty and last kern are similar. And finally, insert penalties holds the sum of the penalties associated with all split and floating insertions.

define page goal ≡ page so far [0] { desired height of information on page being built }

define page total ≡ page so far [1] { height of the current page }

define page shrink ≡ page so far [6] { shrinkability of the current page }

define page depth ≡ page so far [7] { depth of the current page } ⟨ Global variables 13 ⟩ +≡ page so far : array [0 . . 7] of scaled ; { height and glue of the current page } last glue: pointer ; { used to implement } last penalty : integer ; { used to implement } last kern: scaled ; { used to implement } insert penalties : integer ; { sum of the penalties for held-over insertions }

983. ⟨ Put each of TEX’s primitives into the hash table 226 ⟩ +≡

primitive(  , set page dimen, 0); primitive(  , set page dimen, 1);
primitive(  , set page dimen, 2); primitive(  , set page dimen, 3);
primitive(  , set page dimen, 4); primitive(  , set page dimen, 5);
primitive(  , set page dimen, 6); primitive(  , set page dimen, 7);

984. ⟨ Cases of print cmd chr for symbolic printing of primitives 227 ⟩ +≡ set page dimen: case chr code of

0: print esc( );

1: print esc( );

2: print esc( );

3: print esc( );

4: print esc( );

5: print esc( );

6: print esc( );

othercases print esc( )

endcases; 985. define print plus end (#) ≡ print (#); end

define print plus (#) ≡

if page so far [#] ≠ 0 then

begin print ( ␣ ␣ ); print scaled (page so far [#]); print plus end

procedure print totals ; begin print scaled (page total ); print plus (2)( ); print plus (3)( ); print plus (4)( ); print plus (5)( ); if page shrink ≠ 0 then

begin print ( ␣ ␣ ); print scaled (page shrink );

end; end;

986. ⟨ Show the status of the current page 986 ⟩ ≡

if page head ≠ page tail then begin print nl ( ###␣ ␣ ); if output active then print ( ␣ ␣ ␣ ␣ ␣ ); show box (link (page head )); if page contents > empty then

begin print nl ( ␣ ␣ ); print totals ; print nl ( ␣ ␣ ␣ ); print scaled (page goal ); r ← link (page ins head ); while r ≠ page ins head do

begin print ln; print esc( ); t ← qo(subtype(r)); print int (t); print ( ␣ ␣ ); t ← x over n(height (r), 1000) ∗ count (t); print scaled (t); if type(r) = split up then

begin q ← page head ; t ← 0;

repeat q ← link (q);

if (type(q) = ins node) ∧ (subtype(q) = subtype(r)) then incr (t); until q = broken ins (r); print ( ␣# ); print int (t); print ( ␣ ␣ ); end; r ← link (r); end; end;

end

This code is used in section 218.

987. Here is a procedure that is called when the page contents is changing from empty to inserts only or box there.

define set page so far zero(#) ≡ page so far [#] ← 0 procedure freeze page specs (s : small number );

begin page contents ← s; page goal ← vsize; page max depth ← max depth; page depth ← 0; do all six (set page so far zero); least page cost ← awful bad ; stat if tracing pages > 0 then

begin begin diagnostic; print nl ( %%␣ ␣ ); print scaled (page goal ); print ( ␣ ␣ ); print scaled (page max depth); end diagnostic(false); end; tats

end; 988. Pages are built by appending nodes to the current list in TEX’s vertical mode, which is at the outermost level of the semantic nest. This vlist is split into two parts; the “current page” that we have been talking so much about already, and the “contribution list” that receives new nodes as they are created. The current page contains everything that the page builder has accounted for in its data structures, as described above, while the contribution list contains other things that have been generated by other parts of TEX but have not yet been seen by the page builder. The contribution list starts at link (contrib head ), and it ends at the current node in TEX’s vertical mode.

When TEX has appended new material in vertical mode, it calls the procedure build page, which tries to catch up by moving nodes from the contribution list to the current page. This procedure will succeed in its goal of emptying the contribution list, unless a page break is discovered, i.e., unless the current page has grown to the point where the optimum next page break has been determined. In the latter case, the nodes after the optimum break will go back onto the contribution list, and control will effectively pass to the user’s output routine.

We make type(page head ) = glue node, so that an initial glue node on the current page will not be considered a valid breakpoint. ⟨ Initialize the special list heads and constant nodes 790 ⟩ +≡

type(page head ) ← glue node; subtype(page head ) ← normal ;

989. The global variable output active is true during the time the user’s output routine is driving TEX. ⟨ Global variables 13 ⟩ +≡ output active: boolean; { are we in the midst of an output routine? }

990. ⟨ Set initial values of key variables 21 ⟩ +≡ output active ← false; insert penalties ← 0;

991. The page builder is ready to start a fresh page if we initialize the following state variables. (However, the page insertion list is initialized elsewhere.) ⟨ Start a new current page 991 ⟩ ≡

page contents ← empty ; page tail ← page head ; link (page head ) ← null ;

last glue ← max halfword ; last penalty ← 0; last kern ← 0; page depth ← 0; page max depth ← 0

This code is used in sections 215 and 1017.

992. At certain times box 255 is supposed to be void (i.e., null ), or an insertion box is supposed to be ready to accept a vertical list. If not, an error message is printed, and the following subroutine flushes the unwanted contents, reporting them to the user. procedure box error (n : eight bits );

begin error ; begin diagnostic; print nl ( ␣ ␣ ␣ ␣ ␣ );

show box (box (n)); end diagnostic(true); flush node list (box (n)); box (n) ← null ;

end; 993. The following procedure guarantees that a given box register does not contain an . procedure ensure vbox (n : eight bits );

var p: pointer ; { the box register contents } begin p ← box (n); if p ≠ null then

if type(p) = hlist node then

begin print err (  ␣   ␣    ␣  ␣     ␣  ␣ ␣  );

    help3 (  ␣    ␣   ´ ␣      ␣  ␣       ␣    ␣ )
    (  ␣        ␣    ␣   ␣        ␣  ␣  )

(  ␣   ␣ ´ ␣       ␣   ␣       ␣  ); box error (n);

end; end;

994. TEX is not always in vertical mode at the time build page is called; the current mode reflects what TEX should return to, after the contribution list has been emptied. A call on build page should be immediately followed by ‘goto big switch’, which is TEX’s central control point.

define contribute = 80 { go here to link a node into the current page } ⟨ Declare the procedure called fire up 1012 ⟩ procedure build page; { append contributions to the current page }

label exit , done, done1 , continue, contribute, update heights ; var p: pointer ; { the node being appended }

q, r: pointer ; { nodes being examined }

b, c: integer ; { badness and cost of current page }

pi : integer ; { penalty to be added to the badness }

n: min quarterword . . 255; { insertion box number }

delta, h, w: scaled ; { sizes used for insertion calculations } begin if (link (contrib head ) = null ) ∨ output active then return; repeat continue: p ← link (contrib head );

⟨ Update the values of last glue, last penalty , and last kern 996 ⟩;

⟨ Move node p to the current page; if it is time for a page break, put the nodes following the break

back onto the contribution list, and return to the user’s output routine if there is one 997 ⟩; until link (contrib head ) = null ; ⟨ Make the contribution list empty by setting its tail to contrib head 995 ⟩;

exit : end;

995. define contrib tail ≡ nest [0].tail field { tail of the contribution list } ⟨ Make the contribution list empty by setting its tail to contrib head 995 ⟩ ≡

if nest ptr = 0 then tail ← contrib head { vertical mode } else contrib tail ← contrib head { other modes }

This code is used in section 994.

996. ⟨ Update the values of last glue, last penalty , and last kern 996 ⟩ ≡ if last glue ≠ max halfword then delete glue ref (last glue); last penalty ← 0; last kern ← 0; if type(p) = glue node then

begin last glue ← glue ptr (p); add glue ref (last glue); end

else begin last glue ← max halfword ; if type(p) = penalty node then last penalty ← penalty (p) else if type(p) = kern node then last kern ← width(p); end

This code is used in section 994.

997. The code here is an example of a many-way switch into routines that merge together in different places. Some people call this unstructured programming, but the author doesn’t see much wrong with it, as long as the various labels have a well-understood meaning. ⟨ Move node p to the current page; if it is time for a page break, put the nodes following the break back

onto the contribution list, and return to the user’s output routine if there is one 997 ⟩ ≡ ⟨ If the current page is empty and node p is to be deleted, goto done1 ; otherwise use node p to update

the state of the current page; if this node is an insertion, goto contribute; otherwise if this node is not a legal breakpoint, goto contribute or update heights ; otherwise set pi to the penalty associated with this breakpoint 1000 ⟩;

⟨ Check if node p is a new champion breakpoint; then if it is time for a page break, prepare for output,

and either fire up the user’s output routine and return or ship out the page and goto done 1005 ⟩; if (type(p) < glue node) ∨ (type(p) > kern node) then goto contribute;

update heights : ⟨ Update the current page measurements with respect to the glue or kern specified by

node p 1004 ⟩; contribute: ⟨ Make sure that page max depth is not exceeded 1003 ⟩;

⟨ Link node p into the current page and goto done 998 ⟩; done1 : ⟨ Recycle node p 999 ⟩; done:

This code is used in section 994.

998. ⟨ Link node p into the current page and goto done 998 ⟩ ≡ link (page tail ) ← p; page tail ← p; link (contrib head ) ← link (p); link (p) ← null ; goto done

This code is used in section 997.

999. ⟨ Recycle node p 999 ⟩ ≡ link (contrib head ) ← link (p); link (p) ← null ; flush node list (p)

This code is used in section 997.

1000. The title of this section is already so long, it seems best to avoid making it more accurate but still longer, by mentioning the fact that a kern node at the end of the contribution list will not be contributed until we know its successor. ⟨ If the current page is empty and node p is to be deleted, goto done1 ; otherwise use node p to update the

state of the current page; if this node is an insertion, goto contribute; otherwise if this node is not a legal breakpoint, goto contribute or update heights ; otherwise set pi to the penalty associated with this breakpoint 1000 ⟩ ≡

case type(p) of hlist node, vlist node, rule node: if page contents < box there then

⟨ Initialize the current page, insert the glue ahead of p, and goto continue 1001 ⟩ else ⟨ Prepare to move a box or rule node to the current page, then goto contribute 1002 ⟩;

whatsit node: ⟨ Prepare to move whatsit p to the current page, then goto contribute 1364 ⟩; glue node: if page contents < box there then goto done1

else if precedes break (page tail ) then pi ← 0

else goto update heights ; kern node: if page contents < box there then goto done1

else if link (p) = null then return

else if type(link (p)) = glue node then pi ← 0

else goto update heights ; penalty node: if page contents < box there then goto done1 else pi ← penalty (p); mark node: goto contribute; ins node: ⟨ Append an insertion to the current page and goto contribute 1008 ⟩; othercases confusion( ) endcases

This code is used in section 997.

1001. ⟨ Initialize the current page, insert the glue ahead of p, and goto continue 1001 ⟩ ≡ begin if page contents = empty then freeze page specs (box there) else page contents ← box there; q ← new skip param(top skip code); { now temp ptr = glue ptr (q) } if width(temp ptr ) > height (p) then width(temp ptr ) ← width(temp ptr ) − height (p) else width(temp ptr ) ← 0; link (q) ← p; link (contrib head ) ← q; goto continue; end

This code is used in section 1000.

1002. ⟨ Prepare to move a box or rule node to the current page, then goto contribute 1002 ⟩ ≡ begin page total ← page total + page depth + height (p); page depth ← depth(p); goto contribute; end

This code is used in section 1000.

1003. ⟨ Make sure that page max depth is not exceeded 1003 ⟩ ≡

if page depth > page max depth then begin page total ← page total + page depth − page max depth; page depth ← page max depth; end;

This code is used in section 997.

1004. ⟨ Update the current page measurements with respect to the glue or kern specified by node p 1004 ⟩ ≡ if type(p) = kern node then q ← p else begin q ← glue ptr (p);

page so far [2 + stretch order (q)] ← page so far [2 + stretch order (q)] + stretch(q); page shrink ← page shrink + shrink (q); if (shrink order (q) ≠ normal ) ∧ (shrink (q) ≠ 0) then

begin

print err (  ␣    ␣         ␣     ␣  ␣       ␣  );

help4 (  ␣    ␣     ␣  ␣  ␣      ␣        ␣    ␣  )
(  ␣     ␣     ␣`     ´ ␣  ␣` ␣   ␣     ␣  ´  )
(  ␣    ␣     ´ ␣      ␣      ␣   ␣   ␣   ␣      ␣  )

(  ␣   ␣         ␣            ␣   ␣    ␣    ␣  ); error ; r ← new spec(q);

shrink order (r) ← normal ; delete glue ref (q); glue ptr (p) ← r; q ← r; end;

end; page total ← page total + page depth + width(q); page depth ← 0

This code is used in section 997.

1005. ⟨ Check if node p is a new champion breakpoint; then if it is time for a page break, prepare for output, and either fire up the user’s output routine and return or ship out the page and goto

done 1005 ⟩ ≡

if pi < inf penalty then begin ⟨ Compute the badness, b, of the current page, using awful bad if the box is too full 1007 ⟩; if b < awful bad then

if pi ≤ eject penalty then c ← pi else if b < inf bad then c ← b + pi + insert penalties

else c ← deplorable else c ← b; if insert penalties ≥ 10000 then c ← awful bad ; stat if tracing pages > 0 then ⟨ Display the page break cost 1006 ⟩; tats if c ≤ least page cost then

begin best page break ← p; best size ← page goal ; least page cost ← c; r ← link (page ins head ); while r ≠ page ins head do

begin best ins ptr (r) ← last ins ptr (r); r ← link (r); end;

end; if (c = awful bad ) ∨ (pi ≤ eject penalty ) then

begin fire up(p); { output the current page at the best place } if output active then return; { user’s output routine will act } goto done; { the page has been shipped out by default output routine } end;

end

This code is used in section 997.

1006. ⟨ Display the page break cost 1006 ⟩ ≡ begin begin diagnostic; print nl ( % ); print ( ␣ ); print totals ; print ( ␣ ); print scaled (page goal ); print ( ␣ ); if b = awful bad then print char ( ) else print int (b); print ( ␣ ); print int (pi ); print ( ␣ ); if c = awful bad then print char ( ) else print int (c); if c ≤ least page cost then print char ( # ); end diagnostic(false); end

This code is used in section 1005.

1007. ⟨ Compute the badness, b, of the current page, using awful bad if the box is too full 1007 ⟩ ≡

if page total < page goal then if (page so far [3] ≠ 0) ∨ (page so far [4] ≠ 0) ∨ (page so far [5] ≠ 0) then b ← 0 else b ← badness (page goal − page total , page so far [2])

else if page total − page goal > page shrink then b ← awful bad

else b ← badness (page total − page goal , page shrink )

This code is used in section 1005.

1008. ⟨ Append an insertion to the current page and goto contribute 1008 ⟩ ≡ begin if page contents = empty then freeze page specs (inserts only ); n ← subtype(p); r ← page ins head ; while n ≥ subtype(link (r)) do r ← link (r); n ← qo(n); if subtype(r) ≠ qi (n) then ⟨ Create a page insertion node with subtype(r) = qi (n), and include the glue

correction for box n in the current page state 1009 ⟩; if type(r) = split up then insert penalties ← insert penalties + float cost (p) else begin last ins ptr (r) ← p; delta ← page goal − page total − page depth + page shrink ;

{ this much room is left if we shrink the maximum } if count (n) = 1000 then h ← height (p) else h ← x over n(height (p), 1000) ∗ count (n); { this much room is needed } if ((h ≤ 0) ∨ (h ≤ delta)) ∧ (height (p) + height (r) ≤ dimen(n)) then

begin page goal ← page goal − h; height (r) ← height (r) + height (p); end

else ⟨ Find the best way to split the insertion, and change type(r) to split up 1010 ⟩; end;

goto contribute; end

This code is used in section 1000.

1009. We take note of the value of  n and the height plus depth of  n only when the first

n node is encountered for a new page. A user who changes the contents of n after that first n had better be either extremely careful or extremely lucky, or both. ⟨ Create a page insertion node with subtype(r) = qi (n), and include the glue correction for box n in the

current page state 1009 ⟩ ≡ begin q ← get node(page ins node size); link (q) ← link (r); link (r) ← q; r ← q; subtype(r) ← qi (n); type(r) ← inserting ; ensure vbox (n); if box (n) = null then height (r) ← 0 else height (r) ← height (box (n)) + depth(box (n)); best ins ptr (r) ← null ; q ← skip(n); if count (n) = 1000 then h ← height (r) else h ← x over n(height (r), 1000) ∗ count (n); page goal ← page goal − h − width(q); page so far [2 + stretch order (q)] ← page so far [2 + stretch order (q)] + stretch(q); page shrink ← page shrink + shrink (q); if (shrink order (q) ≠ normal ) ∧ (shrink (q) ≠ 0) then

begin print err (  ␣    ␣         ␣        ␣    ␣ ); print esc(  ); print int (n);

  help3 (  ␣          ␣    ␣   ␣    ␣        ␣    ␣  )
  (  ␣    ␣      ␣             ␣   ␣   ␣   ␣  )

(  ␣   ␣         ␣            ␣   ␣    ␣    ␣  ); error ;

end; end

This code is used in section 1008.

1010. Here is the code that will split a long footnote between pages, in an emergency. The current situation deserves to be recapitulated: Node p is an insertion into box n; the insertion will not fit, in its entirety, either because it would make the total contents of box n greater than n, or because it would make the incremental amount of growth h greater than the available space delta, or both. (This amount h has been weighted by the insertion scaling factor, i.e., by n over 1000.) Now we will choose the best way to break the vlist of the insertion, using the same criteria as in the operation. ⟨ Find the best way to split the insertion, and change type(r) to split up 1010 ⟩ ≡

begin if count (n) ≤ 0 then w ← max dimen else begin w ← page goal − page total − page depth;

if count (n) ≠ 1000 then w ← x over n(w, count (n)) ∗ 1000;

end; if w > dimen(n) − height (r) then w ← dimen(n) − height (r); q ← vert break (ins ptr (p), w, depth(p)); height (r) ← height (r) + best height plus depth; stat if tracing pages > 0 then ⟨ Display the insertion split cost 1011 ⟩; tats if count (n) ≠ 1000 then best height plus depth ← x over n(best height plus depth, 1000) ∗ count (n); page goal ← page goal − best height plus depth; type(r) ← split up; broken ptr (r) ← q; broken ins (r) ← p; if q = null then insert penalties ← insert penalties + eject penalty else if type(q) = penalty node then insert penalties ← insert penalties + penalty (q); end

This code is used in section 1008.

1011. ⟨ Display the insertion split cost 1011 ⟩ ≡ begin begin diagnostic; print nl ( %␣ ); print int (n); print ( ␣ ␣ ); print scaled (w); print char ( ); print scaled (best height plus depth); print ( ␣ ); if q = null then print int (eject penalty ) else if type(q) = penalty node then print int (penalty (q))

else print char ( ); end diagnostic(false); end

This code is used in section 1010.

1012. When the page builder has looked at as much material as could appear before the next page break, it makes its decision. The break that gave minimum badness will be used to put a completed “page” into box 255, with insertions appended to their other boxes.

We also set the values of top mark , first mark , and bot mark . The program uses the fact that bot mark ≠ null implies first mark ≠ null ; it also knows that bot mark = null implies top mark = first mark = null .

The fire up subroutine prepares to output the current page at the best place; then it fires up the user’s output routine, if there is one, or it simply ships out the page. There is one parameter, c, which represents the node that was being contributed to the page when the decision to force an output was made. ⟨ Declare the procedure called fire up 1012 ⟩ ≡ procedure fire up(c : pointer );

label exit ; var p, q, r, s: pointer ; { nodes being examined and/or changed }

prev p: pointer ; { predecessor of p }

n: min quarterword . . 255; { insertion box number }

wait : boolean; { should the present insertion be held over? }

save vbadness : integer ; { saved value of vbadness }

save vfuzz : scaled ; { saved value of vfuzz }

save split top skip: pointer ; { saved value of split top skip } begin ⟨ Set the value of output penalty 1013 ⟩; if bot mark ≠ null then

begin if top mark ≠ null then delete token ref (top mark );

top mark ← bot mark ; add token ref (top mark ); delete token ref (first mark ); first mark ← null ; end;

⟨ Put the optimal current page into box 255, update first mark and bot mark , append insertions to their

boxes, and put the remaining nodes back on the contribution list 1014 ⟩; if (top mark ≠ null ) ∧ (first mark = null ) then

begin first mark ← top mark ; add token ref (top mark );

end; if output routine ≠ null then

if dead cycles ≥ max dead cycles then

⟨ Explain that too many dead cycles have occurred in a row 1024 ⟩ else ⟨ Fire up the user’s output routine and return 1025 ⟩;

⟨ Perform the default output routine 1023 ⟩; exit : end;

This code is used in section 994.

1013. ⟨ Set the value of output penalty 1013 ⟩ ≡

if type(best page break ) = penalty node then begin geq word define(int base + output penalty code, penalty (best page break )); penalty (best page break ) ← inf penalty ; end

else geq word define(int base + output penalty code, inf penalty )

This code is used in section 1012.

1014. As the page is finally being prepared for output, pointer p runs through the vlist, with prev p trailing behind; pointer q is the tail of a list of insertions that are being held over for a subsequent page. ⟨ Put the optimal current page into box 255, update first mark and bot mark , append insertions to their

boxes, and put the remaining nodes back on the contribution list 1014 ⟩ ≡ if c = best page break then best page break ← null ; { c not yet linked in } ⟨ Ensure that box 255 is empty before output 1015 ⟩; insert penalties ← 0; { this will count the number of insertions held over } save split top skip ← split top skip; if holding inserts ≤ 0 then ⟨ Prepare all the boxes involved in insertions to act as queues 1018 ⟩; q ← hold head ; link (q) ← null ; prev p ← page head ; p ← link (prev p); while p ≠ best page break do

begin if type(p) = ins node then

begin if holding inserts ≤ 0 then ⟨ Either insert the material specified by node p into the

appropriate box, or hold it for the next page; also delete node p from the current page 1020 ⟩; end

else if type(p) = mark node then ⟨ Update the values of first mark and bot mark 1016 ⟩; prev p ← p; p ← link (prev p); end;

split top skip ← save split top skip; ⟨ Break the current page at node p, put it in box 255, and put the

remaining nodes on the contribution list 1017 ⟩; ⟨ Delete the page-insertion nodes 1019 ⟩

This code is used in section 1012.

1015. ⟨ Ensure that box 255 is empty before output 1015 ⟩ ≡

if box (255) ≠ null then

begin print err ( ); print esc(  ); print (  ␣  ␣   ␣  );

  help2 (  ␣       ´ ␣   ␣       ␣      ␣  ␣       ␣  )

(  ␣   ␣ ´ ␣       ␣   ␣       ␣  ); box error (255);

end

This code is used in section 1014.

1016. ⟨ Update the values of first mark and bot mark 1016 ⟩ ≡

begin if first mark = null then begin first mark ← mark ptr (p); add token ref (first mark ); end;

if bot mark ≠ null then delete token ref (bot mark ); bot mark ← mark ptr (p); add token ref (bot mark ); end

This code is used in section 1014.

1017. When the following code is executed, the current page runs from node link (page head ) to node prev p, and the nodes from p to page tail are to be placed back at the front of the contribution list. Furthermore the heldover insertions appear in a list from link (hold head ) to q; we will put them into the current page list for safekeeping while the user’s output routine is active. We might have q = hold head ; and p = null if and only if prev p = page tail . Error messages are suppressed within vpackage, since the box might appear to be overfull or underfull simply because the stretch and shrink from the registers for inserts are not actually present in the box. ⟨ Break the current page at node p, put it in box 255, and put the remaining nodes on the contribution

list 1017 ⟩ ≡ if p ≠ null then

begin if link (contrib head ) = null then if nest ptr = 0 then tail ← page tail else contrib tail ← page tail ;

link (page tail ) ← link (contrib head ); link (contrib head ) ← p; link (prev p) ← null ; end;

save vbadness ← vbadness ; vbadness ← inf bad ; save vfuzz ← vfuzz ; vfuzz ← max dimen;

{ inhibit error messages } box (255) ← vpackage(link (page head ), best size, exactly , page max depth); vbadness ← save vbadness ; vfuzz ← save vfuzz ; if last glue ≠ max halfword then delete glue ref (last glue); ⟨ Start a new current page 991 ⟩; { this sets last glue ← max halfword } if q ≠ hold head then

begin link (page head ) ← link (hold head ); page tail ← q;

end

This code is used in section 1014.

1018. If many insertions are supposed to go into the same box, we want to know the position of the last node in that box, so that we don’t need to waste time when linking further information into it. The last ins ptr fields of the page insertion nodes are therefore used for this purpose during the packaging phase. ⟨ Prepare all the boxes involved in insertions to act as queues 1018 ⟩ ≡

begin r ← link (page ins head );

while r ≠ page ins head do

begin if best ins ptr (r) ≠ null then begin n ← qo(subtype(r)); ensure vbox (n); if box (n) = null then box (n) ← new null box ; p ← box (n) + list offset ; while link (p) ≠ null do p ← link (p); last ins ptr (r) ← p; end; r ← link (r); end;

end

This code is used in section 1014.

1019. ⟨ Delete the page-insertion nodes 1019 ⟩ ≡ r ← link (page ins head ); while r ≠ page ins head do

begin q ← link (r); free node(r, page ins node size); r ← q;

end; link (page ins head ) ← page ins head

This code is used in section 1014.

1020. We will set best ins ptr ← null and package the box corresponding to insertion node r, just after making the final insertion into that box. If this final insertion is ‘split up’, the remainder after splitting and pruning (if any) will be carried over to the next page. ⟨ Either insert the material specified by node p into the appropriate box, or hold it for the next page; also

delete node p from the current page 1020 ⟩ ≡ begin r ← link (page ins head ); while subtype(r) ≠ subtype(p) do r ← link (r); if best ins ptr (r) = null then wait ← true else begin wait ← false; s ← last ins ptr (r); link (s) ← ins ptr (p);

if best ins ptr (r) = p then ⟨ Wrap up the box specified by node r, splitting node p if called for; set

wait ← true if node p holds a remainder after splitting 1021 ⟩ else begin while link (s) ≠ null do s ← link (s);

last ins ptr (r) ← s;

end; end;

⟨ Either append the insertion node p after node q, and remove it from the current page, or delete

node(p) 1022 ⟩; end

This code is used in section 1014.

1021. ⟨ Wrap up the box specified by node r, splitting node p if called for; set wait ← true if node p

holds a remainder after splitting 1021 ⟩ ≡ begin if type(r) = split up then

if (broken ins (r) = p) ∧ (broken ptr (r) ≠ null ) then begin while link (s) ≠ broken ptr (r) do s ← link (s); link (s) ← null ; split top skip ← split top ptr (p); ins ptr (p) ← prune page top(broken ptr (r)); if ins ptr (p) ≠ null then

begin temp ptr ← vpack (ins ptr (p), natural ); height (p) ← height (temp ptr ) + depth(temp ptr ); free node(temp ptr , box node size); wait ← true; end; end;

best ins ptr (r) ← null ; n ← qo(subtype(r)); temp ptr ← list ptr (box (n)); free node(box (n), box node size); box (n) ← vpack (temp ptr , natural ); end

This code is used in section 1020.

1022. ⟨ Either append the insertion node p after node q, and remove it from the current page, or delete

node(p) 1022 ⟩ ≡ link (prev p) ← link (p); link (p) ← null ;

if wait then

begin link (q) ← p; q ← p; incr (insert penalties );

end else begin delete glue ref (split top ptr (p)); free node(p, ins node size);

end; p ← prev p

This code is used in section 1020.

1023. The list of heldover insertions, running from link (page head ) to page tail , must be moved to the contribution list when the user has specified no output routine. ⟨ Perform the default output routine 1023 ⟩ ≡

begin if link (page head ) ≠ null then

begin if link (contrib head ) = null then

if nest ptr = 0 then tail ← page tail else contrib tail ← page tail else link (page tail ) ← link (contrib head ); link (contrib head ) ← link (page head ); link (page head ) ← null ; page tail ← page head ; end;

ship out (box (255)); box (255) ← null ; end

This code is used in section 1012.

1024. ⟨ Explain that too many dead cycles have occurred in a row 1024 ⟩ ≡

begin print err (  ␣  ); print int (dead cycles ); print ( ␣          ␣    ␣  );

help3 ( ´ ␣         ␣    ␣    ␣       ␣  ␣     ␣  ␣     ␣    ␣  )
(  ␣  ␣ ´ ␣        ␣       ␣   ␣       ␣    ␣  )
(  ␣             ␣  ␣   ␣    ␣  ␣  ␣  ␣    ␣  ); error ;

end

This code is used in section 1012.

1025. ⟨ Fire up the user’s output routine and return 1025 ⟩ ≡ begin output active ← true; incr (dead cycles ); push nest ; mode ← −vmode; prev depth ← ignore depth; mode line ← −line; begin token list (output routine, output text ); new save level (output group); normal paragraph; scan left brace; return; end

This code is used in section 1012.

1026. When the user’s output routine finishes, it has constructed a vlist in internal vertical mode, and TEX will do the following: ⟨ Resume the page builder after an output routine has come to an end 1026 ⟩ ≡

begin if (loc ≠ null ) ∨ ((token type ≠ output text ) ∧ (token type ≠ backed up)) then

⟨ Recover from an unbalanced output routine 1027 ⟩; end token list ; { conserve stack space in case more outputs are triggered } end graf ; unsave; output active ← false; insert penalties ← 0; ⟨ Ensure that box 255 is empty after output 1028 ⟩; if tail ≠ head then { current list goes after heldover insertions }

begin link (page tail ) ← link (head ); page tail ← tail ;

end; if link (page head ) ≠ null then { and both go before heldover contributions }

begin if link (contrib head ) = null then contrib tail ← page tail ;

link (page tail ) ← link (contrib head ); link (contrib head ) ← link (page head ); link (page head ) ← null ; page tail ← page head ; end;

pop nest ; build page; end

This code is used in section 1100.

1027. ⟨ Recover from an unbalanced output routine 1027 ⟩ ≡

begin print err (  ␣      ␣  );

help2 (  ␣      ␣      ␣       ␣   ␣          ␣ ´ ␣      ␣ ´  )

( ␣ ´ ␣ ␣ ␣ ␣ ␣ ␣ ); error ; repeat get token; until loc = null ; end { loops forever if reading from a file, since null = min halfword ≤ 0 }

This code is used in section 1026.

1028. ⟨ Ensure that box 255 is empty after output 1028 ⟩ ≡

if box (255) ≠ null then

begin print err (  ␣       ␣    ´ ␣   ␣   ␣  ␣ ); print esc(  ); print int (255);
help3 (  ␣       ␣        ␣      ␣     ␣  )

  (  ␣  ␣      ␣`  ´  )

(  ␣ ´ ␣       ␣   ␣       ␣  ); box error (255);

end

This code is used in section 1026.