360  PART 44: BREAKING VERTICAL LISTS INTO PAGES  TEX82 §967

967. Breaking vertical lists into pages. The vsplit procedure, which implements TEX’s operation, is considerably simpler than line break because it doesn’t have to worry about hyphenation, and because its mission is to discover a single break instead of an optimum sequence of breakpoints. But before we get into the details of vsplit , we need to consider a few more basic things.

968. A subroutine called prune page top takes a pointer to a vlist and returns a pointer to a modified vlist in which all glue, kern, and penalty nodes have been deleted before the first box or rule node. However, the first box or rule is actually preceded by a newly created glue node designed so that the topmost baseline will be at distance split top skip from the top, whenever this is possible without backspacing.

In this routine and those that follow, we make use of the fact that a vertical list contains no character nodes, hence the type field exists for each node in the list. function prune page top(p : pointer ): pointer ; { adjust top after page break }

var prev p: pointer ; { lags one step behind p }

q: pointer ; { temporary variable for list manipulation } begin prev p ← temp head ; link (temp head ) ← p; while p ≠ null do

case type(p) of

hlist node, vlist node, rule node: ⟨ Insert glue for split top skip and set p ← null 969 ⟩; whatsit node, mark node, ins node: begin prev p ← p; p ← link (prev p);

end; glue node, kern node, penalty node: begin q ← p; p ← link (q); link (q) ← null ; link (prev p) ← p;

flush node list (q);

end; othercases confusion( ) endcases;

prune page top ← link (temp head );

end;

969. ⟨ Insert glue for split top skip and set p ← null 969 ⟩ ≡

begin q ← new skip param(split top skip code); link (prev p) ← q; link (q) ← p;

{ 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; p ← null ; end

This code is used in section 968.

§970  TEX82  PART 44: BREAKING VERTICAL LISTS INTO PAGES 361

970. The next subroutine finds the best place to break a given vertical list so as to obtain a box of height h, with maximum depth d. A pointer to the beginning of the vertical list is given, and a pointer to the optimum breakpoint is returned. The list is effectively followed by a forced break, i.e., a penalty node with the eject penalty ; if the best break occurs at this artificial node, the value null is returned.

An array of six scaled distances is used to keep track of the height from the beginning of the list to the current place, just as in line break . In fact, we use one of the same arrays, only changing its name to reflect its new significance.

define active height ≡ active width { new name for the six distance variables }

define cur height ≡ active height [1] { the natural height }

define set height zero(#) ≡ active height [#] ← 0 { initialize the height to zero }

define update heights = 90 { go here to record glue in the active height table } function vert break (p : pointer ; h, d : scaled ): pointer ; { finds optimum page break }

label done, not found , update heights ;

var prev p: pointer ; { if p is a glue node, type(prev p) determines whether p is a legal breakpoint } q, r: pointer ; { glue specifications } pi : integer ; { penalty value } b: integer ; { badness at a trial breakpoint } least cost : integer ; { the smallest badness plus penalties found so far } best place: pointer ; { the most recent break that leads to least cost } prev dp: scaled ; { depth of previous box in the list } t: small number ; { type of the node following a kern }

begin prev p ← p; { an initial glue node is not a legal breakpoint }

least cost ← awful bad ; do all six (set height zero); prev dp ← 0;

loop begin ⟨ If node p is a legal breakpoint, check if this break is the best known, and goto done if p is

null or if the page-so-far is already too full to accept more stuff 972 ⟩; prev p ← p; p ← link (prev p); end;

done: vert break ← best place; end;

971. A global variable best height plus depth will be set to the natural size of the box that corresponds to the optimum breakpoint found by vert break . (This value is used by the insertion-splitting algorithm of the page builder.) ⟨ Global variables 13 ⟩ +≡ best height plus depth: scaled ; { height of the best box, without stretching or shrinking } 972. A subtle point to be noted here is that the maximum depth d might be negative, so cur height and prev dp might need to be corrected even after a glue or kern node. ⟨ If node p is a legal breakpoint, check if this break is the best known, and goto done if p is null or if the

page-so-far is already too full to accept more stuff 972 ⟩ ≡ if p = null then pi ← eject penalty else ⟨ Use node p to update the current height and depth measurements; if this node is not a legal

breakpoint, goto not found or update heights , otherwise set pi to the associated penalty at the break 973 ⟩;

⟨ Check if node p is a new champion breakpoint; then goto done if p is a forced break or if the page-so-far

is already too full 974 ⟩; if (type(p) < glue node) ∨ (type(p) > kern node) then goto not found ;

update heights : ⟨ Update the current height and depth measurements with respect to a glue or kern

node p 976 ⟩; not found : if prev dp > d then

begin cur height ← cur height + prev dp − d; prev dp ← d;

end;

This code is used in section 970.

973. ⟨ Use node p to update the current height and depth measurements; if this node is not a legal breakpoint, goto not found or update heights , otherwise set pi to the associated penalty at the break 973 ⟩ ≡

case type(p) of hlist node, vlist node, rule node: begin

cur height ← cur height + prev dp + height (p); prev dp ← depth(p); goto not found ; end;

whatsit node: ⟨ Process whatsit p in vert break loop, goto not found 1365 ⟩; glue node: if precedes break (prev p) then pi ← 0

else goto update heights ; kern node: begin if link (p) = null then t ← penalty node

else t ← type(link (p));

if t = glue node then pi ← 0 else goto update heights ;

end; penalty node: pi ← penalty (p); mark node, ins node: goto not found ; othercases confusion( ) endcases

This code is used in section 972.

974. define deplorable ≡ 100000 { more than inf bad , but less than awful bad } ⟨ Check if node p is a new champion breakpoint; then goto done if p is a forced break or if the page-so-far

is already too full 974 ⟩ ≡ if pi < inf penalty then

begin ⟨ Compute the badness, b, using awful bad if the box is too full 975 ⟩; if b < awful bad then

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

else b ← deplorable; if b ≤ least cost then

begin best place ← p; least cost ← b; best height plus depth ← cur height + prev dp; end;

if (b = awful bad ) ∨ (pi ≤ eject penalty ) then goto done; end

This code is used in section 972.

975. ⟨ Compute the badness, b, using awful bad if the box is too full 975 ⟩ ≡

if cur height < h then if (active height [3] ≠ 0) ∨ (active height [4] ≠ 0) ∨ (active height [5] ≠ 0) then b ← 0 else b ← badness (h − cur height , active height [2])

else if cur height − h > active height [6] then b ← awful bad

else b ← badness (cur height − h, active height [6])

This code is used in section 974.

976. Vertical lists that are subject to the vert break procedure should not contain infinite shrinkability, since that would permit any amount of information to “fit” on one page. ⟨ Update the current height and depth measurements with respect to a glue or kern node p 976 ⟩ ≡

if type(p) = kern node then q ← p else begin q ← glue ptr (p);

active height [2 + stretch order (q)] ← active height [2 + stretch order (q)] + stretch(q); active height [6] ← active height [6] + 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; cur height ← cur height + prev dp + width(q); prev dp ← 0

This code is used in section 972.

977. Now we are ready to consider vsplit itself. Most of its work is accomplished by the two subroutines that we have just considered.

Given the number of a vlist box n, and given a desired page height h, the vsplit function finds the best initial segment of the vlist and returns a box for a page of height h. The remainder of the vlist, if any, replaces the original box, after removing glue and penalties and adjusting for split top skip. Mark nodes in the split-off box are used to set the values of split first mark and split bot mark ; we use the fact that split first mark = null if and only if split bot mark = null .

The original box becomes “void” if and only if it has been entirely extracted. The extracted box is “void” if and only if the original box was void (or if it was, erroneously, an hlist box). function vsplit (n : eight bits ; h : scaled ): pointer ; { extracts a page of height h from box n }

label exit , done; var v: pointer ; { the box to be split }

p: pointer ; { runs through the vlist }

q: pointer ; { points to where the break occurs } begin v ← box (n); if split first mark ≠ null then

begin delete token ref (split first mark ); split first mark ← null ; delete token ref (split bot mark ); split bot mark ← null ; end;

⟨ Dispense with trivial cases of void or bad boxes 978 ⟩; q ← vert break (list ptr (v), h, split max depth); ⟨ Look at all the marks in nodes before the break, and set the final link to null at the break 979 ⟩; q ← prune page top(q); p ← list ptr (v); free node(v, box node size); if q = null then box (n) ← null { the eq level of the box stays the same } else box (n) ← vpack (q, natural ); vsplit ← vpackage(p, h, exactly , split max depth);

exit : end;

978. ⟨ Dispense with trivial cases of void or bad boxes 978 ⟩ ≡

if v = null then begin vsplit ← null ; return; end;

if type(v) ≠ vlist node then

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

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

( ␣ ´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ␣ ␣ ␣ ); error ; vsplit ← null ; return; end

This code is used in section 977.

979. It’s possible that the box begins with a penalty node that is the “best” break, so we must be careful to handle this special case correctly. ⟨ Look at all the marks in nodes before the break, and set the final link to null at the break 979 ⟩ ≡

p ← list ptr (v); if p = q then list ptr (v) ← null else loop begin if type(p) = mark node then

if split first mark = null then begin split first mark ← mark ptr (p); split bot mark ← split first mark ; token ref count (split first mark ) ← token ref count (split first mark ) + 2; end

else begin delete token ref (split bot mark ); split bot mark ← mark ptr (p); add token ref (split bot mark ); end;

if link (p) = q then begin link (p) ← null ; goto done; end;

p ← link (p); end;

done:

This code is used in section 977.