§644  TEX82  PART 33: PACKAGING 239

644. Packaging. We’re essentially done with the parts of TEX that are concerned with the input (get next ) and the output (ship out ). So it’s time to get heavily into the remaining part, which does the real work of typesetting.

After lists are constructed, TEX wraps them up and puts them into boxes. Two major subroutines are given the responsibility for this task: hpack applies to horizontal lists (hlists) and vpack applies to vertical lists (vlists). The main duty of hpack and vpack is to compute the dimensions of the resulting boxes, and to adjust the glue if one of those dimensions is pre-specified. The computed sizes normally enclose all of the material inside the new box; but some items may stick out if negative glue is used, if the box is overfull, or if a includes other boxes that have been shifted left.

The subroutine call hpack (p, w, m) returns a pointer to an hlist node for a box containing the hlist that starts at p. Parameter w specifies a width; and parameter m is either ‘exactly ’ or ‘additional ’. Thus, hpack (p, w, exactly ) produces a box whose width is exactly w, while hpack (p, w, additional ) yields a box whose width is the natural width plus w. It is convenient to define a macro called ‘natural ’ to cover the most common case, so that we can say hpack (p, natural ) to get a box that has the natural width of list p.

Similarly, vpack (p, w, m) returns a pointer to a vlist node for a box containing the vlist that starts at p. In this case w represents a height instead of a width; the parameter m is interpreted as in hpack .

define exactly = 0 { a box dimension is pre-specified }

define additional = 1 { a box dimension is increased from the natural one }

define natural ≡ 0, additional { shorthand for parameters to hpack and vpack }

645. The parameters to hpack and vpack correspond to TEX’s primitives like ‘ ’, ‘ ’; note that ‘ ’ with no dimension following it is equivalent to ‘ ’. The scan spec subroutine scans such constructions in the user’s input, including the mandatory left brace that follows them, and it puts the specification onto save stack so that the desired box can later be obtained by executing the following code:

save ptr ← save ptr − 2; hpack (p, saved (1), saved (0)).

Special care is necessary to ensure that the special save stack codes are placed just below the new group code, because scanning can change save stack when appears. procedure scan spec(c : group code; three codes : boolean); { scans a box specification and left brace }

label found ;

var s: integer ; { temporarily saved value }

spec code: exactly . . additional ; begin if three codes then s ← saved (0); if scan keyword ( ) then spec code ← exactly else if scan keyword ( ) then spec code ← additional

else begin spec code ← additional ; cur val ← 0; goto found ;

end; scan normal dimen;

found : if three codes then begin saved (0) ← s; incr (save ptr ); end;

240  PART 33: PACKAGING  TEX82 §646

saved (0) ← spec code; saved (1) ← cur val ; save ptr ← save ptr + 2; new save level (c); scan left brace; end; 646. To figure out the glue setting, hpack and vpack determine how much stretchability and shrinkability are present, considering all four orders of infinity. The highest order of infinity that has a nonzero coefficient is then used as if no other orders were present.

For example, suppose that the given list contains six glue nodes with the respective stretchabilities 3pt, 8fill, 5fil, 6pt, −3fil, −8fill. Then the total is essentially 2fil; and if a total additional space of 6pt is to be achieved by stretching, the actual amounts of stretch will be 0pt, 0pt, 15pt, 0pt, −9pt, and 0pt, since only ‘fil’ glue will be considered. (The ‘fill’ glue is therefore not really stretching infinitely with respect to ‘fil’; nobody would actually want that to happen.)

The arrays total stretch and total shrink are used to determine how much glue of each kind is present. A global variable last badness is used to implement . ⟨ Global variables 13 ⟩ +≡ total stretch, total shrink : array [glue ord ] of scaled ; { glue found by hpack or vpack } last badness : integer ; { badness of the most recently packaged box }

647. If the global variable adjust tail is non-null, the hpack routine also removes all occurrences of ins node, mark node, and adjust node items and appends the resulting material onto the list that ends at location adjust tail . ⟨ Global variables 13 ⟩ +≡ adjust tail : pointer ; { tail of adjustment list }

648. ⟨ Set initial values of key variables 21 ⟩ +≡ adjust tail ← null ; last badness ← 0;

649. Here now is hpack , which contains few if any surprises. function hpack (p : pointer ; w : scaled ; m : small number ): pointer ;

label reswitch, common ending , exit ;

var r: pointer ; { the box node that will be returned } q: pointer ; { trails behind p } h, d, x: scaled ; { height, depth, and natural width } s: scaled ; { shift amount } g: pointer ; { points to a glue specification } o: glue ord ; { order of infinity } f: internal font number ; { the font in a char node } i: four quarters ; { font information about a char node } hd : eight bits ; { height and depth indices for a character }

begin last badness ← 0; r ← get node(box node size); type(r) ← hlist node;

subtype(r) ← min quarterword ; shift amount (r) ← 0; q ← r + list offset ; link (q) ← p;

h ← 0; ⟨ Clear dimensions to zero 650 ⟩;

while p ≠ null do ⟨ Examine node p in the hlist, taking account of its effect on the dimensions of the

new box, or moving it to the adjustment list; then advance p to the next node 651 ⟩; if adjust tail ≠ null then link (adjust tail ) ← null ; height (r) ← h; depth(r) ← d; ⟨ Determine the value of width(r) and the appropriate glue setting; then return or goto

common ending 657 ⟩;

common ending : ⟨ Finish issuing a diagnostic message for an overfull or underfull hbox 663 ⟩; exit : hpack ← r;

end; 650. ⟨ Clear dimensions to zero 650 ⟩ ≡

d ← 0; x ← 0; total stretch[normal ] ← 0; total shrink [normal ] ← 0; total stretch[fil ] ← 0; total shrink [fil ] ← 0; total stretch[fill ] ← 0; total shrink [fill ] ← 0; total stretch[filll ] ← 0; total shrink [filll ] ← 0

This code is used in sections 649 and 668.

651. ⟨ Examine node p in the hlist, taking account of its effect on the dimensions of the new box, or

moving it to the adjustment list; then advance p to the next node 651 ⟩ ≡ begin reswitch: while is char node(p) do ⟨ Incorporate character dimensions into the dimensions of the

hbox that will contain it, then move to the next node 654 ⟩; if p ≠ null then

begin case type(p) of

hlist node, vlist node, rule node, unset node: ⟨ Incorporate box dimensions into the dimensions of the

hbox that will contain it 653 ⟩; ins node, mark node, adjust node: if adjust tail ≠ null then

⟨ Transfer node p to the adjustment list 655 ⟩; whatsit node: ⟨ Incorporate a whatsit node into an hbox 1360 ⟩; glue node: ⟨ Incorporate glue into the horizontal totals 656 ⟩; kern node, math node: x ← x + width(p); ligature node: ⟨ Make node p look like a char node and goto reswitch 652 ⟩;

othercases do nothing

endcases;

p ← link (p);

end; end

This code is used in section 649.

652. ⟨ Make node p look like a char node and goto reswitch 652 ⟩ ≡ begin mem[lig trick ] ← mem[lig char (p)]; link (lig trick ) ← link (p); p ← lig trick ; goto reswitch; end

This code is used in sections 622, 651, and 1147.

653. The code here implicitly uses the fact that running dimensions are indicated by null flag , which will be ignored in the calculations because it is a highly negative number. ⟨ Incorporate box dimensions into the dimensions of the hbox that will contain it 653 ⟩ ≡

begin x ← x + width(p); if type(p) ≥ rule node then s ← 0 else s ← shift amount (p); if height (p) − s > h then h ← height (p) − s; if depth(p) + s > d then d ← depth(p) + s; end

This code is used in section 651.

654. The following code is part of TEX’s inner loop; i.e., adding another character of text to the user’s input will cause each of these instructions to be exercised one more time. ⟨ Incorporate character dimensions into the dimensions of the hbox that will contain it, then move to the

next node 654 ⟩ ≡ begin f ← font (p); i ← char info(f)(character (p)); hd ← height depth(i); x ← x + char width(f)(i); s ← char height (f)(hd ); if s > h then h ← s; s ← char depth(f)(hd ); if s > d then d ← s; p ← link (p); end

This code is used in section 651.

655. Although node q is not necessarily the immediate predecessor of node p, it always points to some node in the list preceding p. Thus, we can delete nodes by moving q when necessary. The algorithm takes linear time, and the extra computation does not intrude on the inner loop unless it is necessary to make a deletion. ⟨ Transfer node p to the adjustment list 655 ⟩ ≡

begin while link (q) ≠ p do q ← link (q); if type(p) = adjust node then

begin link (adjust tail ) ← adjust ptr (p);

while link (adjust tail ) ≠ null do adjust tail ← link (adjust tail );

p ← link (p); free node(link (q), small node size);

end else begin link (adjust tail ) ← p; adjust tail ← p; p ← link (p);

end; link (q) ← p; p ← q; end

This code is used in section 651.

656. ⟨ Incorporate glue into the horizontal totals 656 ⟩ ≡ begin g ← glue ptr (p); x ← x + width(g); o ← stretch order (g); total stretch[o] ← total stretch[o] + stretch(g); o ← shrink order (g); total shrink [o] ← total shrink [o] + shrink (g); if subtype(p) ≥ a leaders then

begin g ← leader ptr (p);

if height (g) > h then h ← height (g);

if depth(g) > d then d ← depth(g);

end; end

This code is used in section 651.

657. When we get to the present part of the program, x is the natural width of the box being packaged. ⟨ Determine the value of width(r) and the appropriate glue setting; then return or goto

common ending 657 ⟩ ≡

if m = additional then w ← x + w; width(r) ← w; x ← w − x; { now x is the excess to be made up } if x = 0 then

begin glue sign(r) ← normal ; glue order (r) ← normal ; set glue ratio zero(glue set (r)); return; end

else if x > 0 then ⟨ Determine horizontal glue stretch setting, then return or goto common ending 658 ⟩

else ⟨ Determine horizontal glue shrink setting, then return or goto common ending 664 ⟩

This code is used in section 649.

658. ⟨ Determine horizontal glue stretch setting, then return or goto common ending 658 ⟩ ≡ begin ⟨ Determine the stretch order 659 ⟩; glue order (r) ← o; glue sign(r) ← stretching ; if total stretch[o] ≠ 0 then glue set (r) ← unfloat (x/total stretch[o]) else begin glue sign(r) ← normal ; set glue ratio zero(glue set (r)); { there’s nothing to stretch }

end; if o = normal then

if list ptr (r) ≠ null then

⟨ Report an underfull hbox and goto common ending , if this box is sufficiently bad 660 ⟩; return; end

This code is used in section 657.

659. ⟨ Determine the stretch order 659 ⟩ ≡ if total stretch[filll ] ≠ 0 then o ← filll else if total stretch[fill ] ≠ 0 then o ← fill

else if total stretch[fil ] ≠ 0 then o ← fil

else o ← normal

This code is used in sections 658, 673, and 796.

660. ⟨ Report an underfull hbox and goto common ending , if this box is sufficiently bad 660 ⟩ ≡ begin last badness ← badness (x, total stretch[normal ]); if last badness > hbadness then

begin print ln;

if last badness > 100 then print nl ( ) else print nl ( ); print ( ␣ ␣ ␣ ); print int (last badness ); goto common ending ; end;

end

This code is used in section 658.

661. In order to provide a decent indication of where an overfull or underfull box originated, we use a global variable pack begin line that is set nonzero only when hpack is being called by the paragraph builder or the alignment finishing routine. ⟨ Global variables 13 ⟩ +≡ pack begin line: integer ; { source file line where the current paragraph or alignment began; a negative

value denotes alignment }

662. ⟨ Set initial values of key variables 21 ⟩ +≡ pack begin line ← 0; 663. ⟨ Finish issuing a diagnostic message for an overfull or underfull hbox 663 ⟩ ≡

if output active then print ( ␣ ␣ ␣ ␣ ␣ ␣ ) else begin if pack begin line ≠ 0 then

begin if pack begin line > 0 then print ( ␣ ␣ ␣ ␣ ␣ )

else print ( ␣ ␣ ␣ ␣ ␣ ); print int (abs (pack begin line)); print ( ); end

else print ( ␣ ␣ ␣ ␣ );

print int (line);

end; print ln; font in short display ← null font ; short display (list ptr (r)); print ln; begin diagnostic; show box (r); end diagnostic(true)

This code is used in section 649.

664. ⟨ Determine horizontal glue shrink setting, then return or goto common ending 664 ⟩ ≡ begin ⟨ Determine the shrink order 665 ⟩; glue order (r) ← o; glue sign(r) ← shrinking ; if total shrink [o] ≠ 0 then glue set (r) ← unfloat ((−x)/total shrink [o]) else begin glue sign(r) ← normal ; set glue ratio zero(glue set (r)); { there’s nothing to shrink }

end; if (total shrink [o] < −x) ∧ (o = normal ) ∧ (list ptr (r) ≠ null ) then

begin last badness ← 1000000; set glue ratio one(glue set (r)); { use the maximum shrinkage } ⟨ Report an overfull hbox and goto common ending , if this box is sufficiently bad 666 ⟩; end

else if o = normal then

if list ptr (r) ≠ null then

⟨ Report a tight hbox and goto common ending , if this box is sufficiently bad 667 ⟩; return; end

This code is used in section 657.

665. ⟨ Determine the shrink order 665 ⟩ ≡ if total shrink [filll ] ≠ 0 then o ← filll else if total shrink [fill ] ≠ 0 then o ← fill

else if total shrink [fil ] ≠ 0 then o ← fil

else o ← normal

This code is used in sections 664, 676, and 796.

666. ⟨ Report an overfull hbox and goto common ending , if this box is sufficiently bad 666 ⟩ ≡

if (−x − total shrink [normal ] > hfuzz ) ∨ (hbadness < 100) then

begin if (overfull rule > 0) ∧ (−x − total shrink [normal ] > hfuzz ) then begin while link (q) ≠ null do q ← link (q); link (q) ← new rule; width(link (q)) ← overfull rule; end;

print ln; print nl ( ␣ ␣ ); print scaled (−x − total shrink [normal ]); print ( ␣ ␣ ); goto common ending ; end

This code is used in section 664.

667. ⟨ Report a tight hbox and goto common ending , if this box is sufficiently bad 667 ⟩ ≡ begin last badness ← badness (−x, total shrink [normal ]); if last badness > hbadness then

begin print ln; print nl ( ␣ ␣ ␣ ); print int (last badness ); goto common ending ; end;

end

This code is used in section 664.

668. The vpack subroutine is actually a special case of a slightly more general routine called vpackage, which has four parameters. The fourth parameter, which is max dimen in the case of vpack , specifies the maximum depth of the page box that is constructed. The depth is first computed by the normal rules; if it exceeds this limit, the reference point is simply moved down until the limiting depth is attained.

define vpack (#) ≡ vpackage(#, max dimen) { special case of unconstrained depth } function vpackage(p : pointer ; h : scaled ; m : small number ; l : scaled ): pointer ;

label common ending , exit ; var r: pointer ; { the box node that will be returned }

w, d, x: scaled ; { width, depth, and natural height }

s: scaled ; { shift amount }

g: pointer ; { points to a glue specification }

o: glue ord ; { order of infinity } begin last badness ← 0; r ← get node(box node size); type(r) ← vlist node; subtype(r) ← min quarterword ; shift amount (r) ← 0; list ptr (r) ← p; w ← 0; ⟨ Clear dimensions to zero 650 ⟩; while p ≠ null do ⟨ Examine node p in the vlist, taking account of its effect on the dimensions of the

new box; then advance p to the next node 669 ⟩; width(r) ← w; if d > l then

begin x ← x + d − l; depth(r) ← l;

end else depth(r) ← d; ⟨ Determine the value of height (r) and the appropriate glue setting; then return or goto

common ending 672 ⟩;

common ending : ⟨ Finish issuing a diagnostic message for an overfull or underfull vbox 675 ⟩; exit : vpackage ← r;

end;

669. ⟨ Examine node p in the vlist, taking account of its effect on the dimensions of the new box; then

advance p to the next node 669 ⟩ ≡ begin if is char node(p) then confusion( ) else case type(p) of

hlist node, vlist node, rule node, unset node: ⟨ Incorporate box dimensions into the dimensions of the

vbox that will contain it 670 ⟩; whatsit node: ⟨ Incorporate a whatsit node into a vbox 1359 ⟩; glue node: ⟨ Incorporate glue into the vertical totals 671 ⟩; kern node: begin x ← x + d + width(p); d ← 0;

end;

othercases do nothing

endcases; p ← link (p); end

This code is used in section 668.

670. ⟨ Incorporate box dimensions into the dimensions of the vbox that will contain it 670 ⟩ ≡ begin x ← x + d + height (p); d ← depth(p); if type(p) ≥ rule node then s ← 0 else s ← shift amount (p); if width(p) + s > w then w ← width(p) + s; end

This code is used in section 669.

671. ⟨ Incorporate glue into the vertical totals 671 ⟩ ≡ begin x ← x + d; d ← 0; g ← glue ptr (p); x ← x + width(g); o ← stretch order (g); total stretch[o] ← total stretch[o] + stretch(g); o ← shrink order (g); total shrink [o] ← total shrink [o] + shrink (g); if subtype(p) ≥ a leaders then

begin g ← leader ptr (p);

if width(g) > w then w ← width(g);

end; end

This code is used in section 669.

672. When we get to the present part of the program, x is the natural height of the box being packaged. ⟨ Determine the value of height (r) and the appropriate glue setting; then return or goto

common ending 672 ⟩ ≡

if m = additional then h ← x + h; height (r) ← h; x ← h − x; { now x is the excess to be made up } if x = 0 then

begin glue sign(r) ← normal ; glue order (r) ← normal ; set glue ratio zero(glue set (r)); return; end

else if x > 0 then ⟨ Determine vertical glue stretch setting, then return or goto common ending 673 ⟩

else ⟨ Determine vertical glue shrink setting, then return or goto common ending 676 ⟩

This code is used in section 668.

673. ⟨ Determine vertical glue stretch setting, then return or goto common ending 673 ⟩ ≡ begin ⟨ Determine the stretch order 659 ⟩; glue order (r) ← o; glue sign(r) ← stretching ; if total stretch[o] ≠ 0 then glue set (r) ← unfloat (x/total stretch[o]) else begin glue sign(r) ← normal ; set glue ratio zero(glue set (r)); { there’s nothing to stretch }

end; if o = normal then

if list ptr (r) ≠ null then

⟨ Report an underfull vbox and goto common ending , if this box is sufficiently bad 674 ⟩; return; end

This code is used in section 672.

674. ⟨ Report an underfull vbox and goto common ending , if this box is sufficiently bad 674 ⟩ ≡ begin last badness ← badness (x, total stretch[normal ]); if last badness > vbadness then

begin print ln;

if last badness > 100 then print nl ( ) else print nl ( );

print ( ␣ ␣ ␣ ); print int (last badness ); goto common ending ;

end; end

This code is used in section 673.

675. ⟨ Finish issuing a diagnostic message for an overfull or underfull vbox 675 ⟩ ≡ if output active then print ( ␣ ␣ ␣ ␣ ␣ ␣ ) else begin if pack begin line ≠ 0 then { it’s actually negative }

begin print ( ␣ ␣ ␣ ␣ ␣ ); print int (abs (pack begin line)); print ( ); end

else print ( ␣ ␣ ␣ ␣ );

print int (line); print ln;

end; begin diagnostic; show box (r); end diagnostic(true)

This code is used in section 668.

676. ⟨ Determine vertical glue shrink setting, then return or goto common ending 676 ⟩ ≡ begin ⟨ Determine the shrink order 665 ⟩; glue order (r) ← o; glue sign(r) ← shrinking ; if total shrink [o] ≠ 0 then glue set (r) ← unfloat ((−x)/total shrink [o]) else begin glue sign(r) ← normal ; set glue ratio zero(glue set (r)); { there’s nothing to shrink }

end; if (total shrink [o] < −x) ∧ (o = normal ) ∧ (list ptr (r) ≠ null ) then

begin last badness ← 1000000; set glue ratio one(glue set (r)); { use the maximum shrinkage } ⟨ Report an overfull vbox and goto common ending , if this box is sufficiently bad 677 ⟩; end

else if o = normal then

if list ptr (r) ≠ null then

⟨ Report a tight vbox and goto common ending , if this box is sufficiently bad 678 ⟩; return; end

This code is used in section 672.

677. ⟨ Report an overfull vbox and goto common ending , if this box is sufficiently bad 677 ⟩ ≡

if (−x − total shrink [normal ] > vfuzz ) ∨ (vbadness < 100) then begin print ln; print nl ( ␣ ␣ ); print scaled (−x − total shrink [normal ]); print ( ␣ ␣ ); goto common ending ; end

This code is used in section 676.

678. ⟨ Report a tight vbox and goto common ending , if this box is sufficiently bad 678 ⟩ ≡ begin last badness ← badness (−x, total shrink [normal ]); if last badness > vbadness then

begin print ln; print nl ( ␣ ␣ ␣ ); print int (last badness ); goto common ending ; end;

end

This code is used in section 676.

679. When a box is being appended to the current vertical list, the baselineskip calculation is handled by the append to vlist routine. procedure append to vlist (b : pointer );

var d: scaled ; { deficiency of space between baselines }

p: pointer ; { a new glue specification } begin if prev depth > ignore depth then

begin d ← width(baseline skip) − prev depth − height (b); if d < line skip limit then p ← new param glue(line skip code) else begin p ← new skip param(baseline skip code); width(temp ptr ) ← d; { temp ptr = glue ptr (p) }

end; link (tail ) ← p; tail ← p; end;

link (tail ) ← b; tail ← b; prev depth ← depth(b); end;