Section 644: Packaging

We’re essentially done with the parts of 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, 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 \vbox 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.

NOTE

EXACTLY AND ADDITIONAL are not in the file constants.h, and are kept alongside NATURAL in builder.h.

builder.h
// << Start file |builder.h|, 1381 >>

#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|

Section 645

The parameters to hpack and vpack correspond to ’s primitives like ‘\hbox to 300pt’, ‘\hbox spread 10pt’; note that ‘\hbox’ with no dimension following it is equivalent to ‘\hbox spread 0pt’. 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 \csname appears.

subroutines.c
// scans a box specification and left brace
void scan_spec(int c, bool three_codes) {
    int s; // temporarily saved value
    int spec_code;
    if (three_codes) {
        s = saved(0);
    }
    if (scan_keyword("to")) {
        spec_code = EXACTLY;
    }
    else if (scan_keyword("spread")) {
        spec_code = ADDITIONAL;
    }
    else {
        spec_code = ADDITIONAL;
        cur_val = 0;
        goto found;
    }
    scan_normal_dimen;
found:
    if (three_codes) {
        saved(0) = s;
        incr(save_ptr);
    }
    saved(0) = spec_code;
    saved(1) = cur_val;
    save_ptr += 2;
    new_save_level(c);
    scan_left_brace();
}

Section 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 \badness.

⟨ Global variables 13 ⟩+≡

scaled total_stretch[4], total_shrink[4]; // glue found by |hpack| or |vpack|
int last_badness; // badness of the most recently packaged box

Section 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 ⟩+≡

pointer adjust_tail; // tail of adjustment list

Section 648

⟨ Set initial values of key variables 21 ⟩+≡

adjust_tail = null;
last_badness = 0;

Section 649

Here now is hpack, which contains few if any surprises.

packaging.c
// << Start file |packaging.c|, 1382 >>

pointer hpack(pointer p, scaled w, small_number m) {
    pointer r;              // the box node that will be returned
    pointer q;              // trails behind |p|
    scaled h, d, x;         // height, depth, and natural width
    scaled s;               // shift amount
    pointer g;              // points to a glue specification
    int o;                  // order of infinity
    internal_font_number f; // the font in a |CHAR_NODE|
    memory_word i;          // font information about a |CHAR_NODE|
    eight_bits hd;          // height and depth indices for a character
    
    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) {
        // << 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) {
        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 >>
    return r;
}

Section 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.

Section 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 ⟩≡

reswitch:
while (is_char_node(p)) {
    // << Incorporate character dimensions into the dimensions of the hbox that will contain it, then move to the next node, 654 >>
}
if (p != null) {
    switch (type(p)) {
    case HLIST_NODE:
    case VLIST_NODE:
    case RULE_NODE:
    case UNSET_NODE:
        // << Incorporate box dimensions into the dimensions of the hbox that will contain it, 653 >>
        break;
    
    case INS_NODE:
    case MARK_NODE:
    case ADJUST_NODE:
        if (adjust_tail != null) {
            // << Transfer node |p| to the adjustment list, 655 >>
        }
        break;
    
    case WHATSIT_NODE:
        // << Incorporate a whatsit node into an hbox, 1360 >>
        break;
    
    case GLUE_NODE:
        // << Incorporate glue into the horizontal totals, 656 >>
        break;
    
    case KERN_NODE:
    case MATH_NODE:
        x += width(p);
        break;
    
    case LIGATURE_NODE:
        // << Make node |p| look like a |CHAR_NODE| and |goto reswitch|, 652 >>
    
    default:
        do_nothing;
    }
    p = link(p);
}

This code is used in section 649.

Section 652

⟨ Make node p look like a CHAR_NODE and goto reswitch 652 ⟩≡

mem[LIG_TRICK] = mem[lig_char(p)];
link(LIG_TRICK) = link(p);
p = LIG_TRICK;
goto reswitch;

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

Section 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 ⟩≡

x += width(p);
if (type(p) >= RULE_NODE) {
    s = 0;
}
else {
    s = shift_amount(p);
}
if (height(p) - s > h) {
    h = height(p) - s;
}
if (depth(p) + s > d) {
    d = depth(p) + s;
}

This code is used in section 651.

Section 654

The following code is part of ’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 ⟩≡

f = font(p);
i = char_info(f, character(p));
hd = height_depth(i);
x += char_width(f, i);
s = char_height(f, hd);
if (s > h) {
    h = s;
}
s = char_depth(f, hd);
if (s > d) {
    d = s;
}
p = link(p);

This code is used in section 651.

Section 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 ⟩≡

while (link(q) != p) {
    q = link(q);
}
if (type(p) == ADJUST_NODE) {
    link(adjust_tail) = adjust_ptr(p);
    while (link(adjust_tail) != null) {
        adjust_tail = link(adjust_tail);
    }
    p = link(p);
    free_node(link(q), SMALL_NODE_SIZE);
}
else {
    link(adjust_tail) = p;
    adjust_tail = p;
    p = link(p);
}
link(q) = p;
p = q;

This code is used in section 651.

Section 656

⟨ Incorporate glue into the horizontal totals 656 ⟩≡

g = glue_ptr(p);
x += width(g);
o = stretch_order(g);
total_stretch[o] += stretch(g);
o = shrink_order(g);
total_shrink[o] += shrink(g);
if (subtype(p) >= A_LEADERS) {
    g = leader_ptr(p);
    if (height(g) > h) {
        h = height(g);
    }
    if (depth(g) > d) {
        d = depth(g);
    }
}

This code is used in section 651.

Section 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) {
    w = x + w;
}
width(r) = w;
x = w - x; // now |x| is the excess to be made up
if (x == 0) {
    glue_sign(r) = NORMAL;
    glue_order(r) = NORMAL;
    set_glue_ratio_zero(glue_set(r));
    return r;
}
else if (x > 0) {
    // << 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.

Section 658

⟨ Determine horizontal glue stretch setting, then return or goto common_ending 658 ⟩≡

// << Determine the stretch order, 659 >>
glue_order(r) = o;
glue_sign(r) = STRETCHING;
if (total_stretch[o] != 0) {
    glue_set(r) = (double)x / total_stretch[o];
}
else {
    glue_sign(r) = NORMAL;
    set_glue_ratio_zero(glue_set(r)); // there's nothing to stretch
}
if (o == NORMAL && list_ptr(r) != null) {
    // << Report an underfull hbox and |goto common_ending|, if this box is sufficiently bad, 660 >>
}
return r;

This code is used in section 657.

Section 659

⟨ Determine the stretch order 659 ⟩≡

if (total_stretch[FILLL] != 0) {
    o = FILLL;
}
else if (total_stretch[FILL] != 0) {
    o = FILL;
}
else if (total_stretch[FIL] != 0) {
    o = FIL;
}
else {
    o = NORMAL;
}

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

Section 660

⟨ Report an underfull hbox and goto common_ending, if this box is sufficiently bad 660 ⟩≡

last_badness = badness(x, total_stretch[NORMAL]);
if (last_badness > hbadness) {
    print_ln();
    if (last_badness > 100) {
        print_nl("Underfull");
    }
    else {
        print_nl("Loose");
    }
    print(" \\hbox (badness ");
    print_int(last_badness);
    goto common_ending;
}

This code is used in section 658.

Section 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 ⟩+≡

int pack_begin_line; // source file line where the current paragraph or alignment began; a negative value denotes alignment

Section 662

⟨ Set initial values of key variables 21 ⟩+≡

pack_begin_line = 0;

Section 663

⟨ Finish issuing a diagnostic message for an overfull or underfull hbox 663 ⟩≡

if (output_active) {
    print(") has occurred while \\output is active");
}
else {
    if (pack_begin_line != 0) {
        if (pack_begin_line > 0) {
            print(") in paragraph at lines ");
        }
        else {
            print(") in alignment at lines ");
        }
        print_int(abs(pack_begin_line));
        print("--");
    }
    else {
        print(") detected at line ");
    }
    print_int(line);
}
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.

Section 664

⟨ Determine horizontal glue shrink setting, then return or goto common_ending 664 ⟩≡

// << Determine the shrink order, 665 >>
glue_order(r) = o;
glue_sign(r) = SHRINKING;
if (total_shrink[o] != 0) {
    glue_set(r) = (double)(-x) / total_shrink[o];
}
else {
    glue_sign(r) = NORMAL;
    set_glue_ratio_zero(glue_set(r)); // there's nothing to shrink
}
if (total_shrink[o] < -x
    && o == NORMAL
    && list_ptr(r) != null)
{
    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 >>
}
else if (o == NORMAL && list_ptr(r) != null) {
    // << Report a tight hbox and |goto common_ending|, if this box is sufficiently bad, 667 >>
}
return r;

This code is used in section 657.

Section 665

⟨ Determine the shrink order 665 ⟩≡

if (total_shrink[FILLL] != 0) {
    o = FILLL;
}
else if (total_shrink[FILL] != 0) {
    o = FILL;
}
else if (total_shrink[FIL] != 0) {
    o = FIL;
}
else {
    o = NORMAL;
}

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

Section 666

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

if (-x - total_shrink[NORMAL] > hfuzz || hbadness < 100) {
    if (overfull_rule > 0 && -x - total_shrink[NORMAL] > hfuzz) {
        while (link(q) != null) {
            q = link(q);
        }
        link(q) = new_rule();
        width(link(q)) = overfull_rule;
    }
    print_ln();
    print_nl("Overfull \\hbox (");
    print_scaled(-x - total_shrink[NORMAL]);
    print("pt too wide");
    goto common_ending;
}

This code is used in section 664.

Section 667

⟨ Report a tight hbox and goto common_ending, if this box is sufficiently bad 667 ⟩≡

last_badness = badness(-x, total_shrink[NORMAL]);
if (last_badness > hbadness) {
    print_ln();
    print_nl("Tight \\hbox (badness ");
    print_int(last_badness);
    goto common_ending;
}

This code is used in section 664.

Section 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.

builder.h
// special case of unconstrained depth
#define vpack(...) vpackage(__VA_ARGS__, MAX_DIMEN)
packaging.c
pointer vpackage(pointer p, scaled h, small_number m, scaled l) {
    pointer r;      // the box node that will be returned
    scaled w, d, x; // width, depth, and natural height
    scaled s;       // shift amount
    pointer g;      // points to a glue specification
    int o;          // order of infinity
    
    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) {
        // << 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) {
        x = x + d - l;
        depth(r) = l;
    }
    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 >>
    return r;
}

Section 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 ⟩≡

if (is_char_node(p)) {
    confusion("vpack");
}
else {
    switch (type(p)) {
    case HLIST_NODE:
    case VLIST_NODE:
    case RULE_NODE:
    case UNSET_NODE:
        // << Incorporate box dimensions into the dimensions of the vbox that will contain it, 670 >>
        break;
    
    case WHATSIT_NODE:
        // << Incorporate a whatsit node into a vbox, 1359 >>
        break;
    
    case GLUE_NODE:
        // << Incorporate glue into the vertical totals, 671 >>
        break;
    
    case KERN_NODE:
        x += d + width(p);
        d = 0;
        break;
    
    default:
        do_nothing;
    }
}
p = link(p);

This code is used in section 668.

Section 670

⟨ Incorporate box dimensions into the dimensions of the vbox that will contain it 670 ⟩≡

x += d + height(p);
d = depth(p);
if (type(p) >= RULE_NODE) {
    s = 0;
}
else {
    s = shift_amount(p);
}
if (width(p) + s > w) {
    w = width(p) + s;
}

This code is used in section 669.

Section 671

⟨ Incorporate glue into the vertical totals 671 ⟩≡

x += d;
d = 0;
g = glue_ptr(p);
x += width(g);
o = stretch_order(g);
total_stretch[o] += stretch(g);
o = shrink_order(g);
total_shrink[o] += shrink(g);
if (subtype(p) >= A_LEADERS) {
    g = leader_ptr(p);
    if (width(g) > w) {
        w = width(g);
    }
}

This code is used in section 669.

Section 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) {
    h += x;
}
height(r) = h;
x = h - x; // now |x| is the excess to be made up
if (x == 0) {
    glue_sign(r) = NORMAL;
    glue_order(r) = NORMAL;
    set_glue_ratio_zero(glue_set(r));
    return r;
}
else if (x > 0) {
    // << 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.

Section 673

⟨ Determine vertical glue stretch setting, then return or goto common_ending 673 ⟩≡

// << Determine the stretch order, 659 >>
glue_order(r) = o;
glue_sign(r) = STRETCHING;
if (total_stretch[o] != 0) {
    glue_set(r) = (double)x / total_stretch[o];
}
else {
    glue_sign(r) = NORMAL;
    set_glue_ratio_zero(glue_set(r)); // there's nothing to stretch
}
if (o == NORMAL && list_ptr(r) != null) {
    // << Report an underfull vbox and |goto common_ending|, if this box is sufficiently bad, 674 >>
}
return r;

This code is used in section 672.

Section 674

⟨ Report an underfull vbox and goto common_ending, if this box is sufficiently bad 674 ⟩≡

last_badness = badness(x, total_stretch[NORMAL]);
if (last_badness > vbadness) {
    print_ln();
    if (last_badness > 100) {
        print_nl("Underfull");
    }
    else {
        print_nl("Loose");
    }
    print(" \\vbox (badness ");
    print_int(last_badness);
    goto common_ending;
}

This code is used in section 673.

Section 675

⟨ Finish issuing a diagnostic message for an overfull or underfull vbox 675 ⟩≡

if (output_active) {
    print(") has occurred while \\output is active");
}
else {
    if (pack_begin_line != 0) {
        // it's actually negative
        print(") in alignment at lines ");
        print_int(abs(pack_begin_line));
        print("--");
    }
    else {
        print(") detected at line ");
    }
    print_int(line);
    print_ln();
}
begin_diagnostic();
show_box(r);
end_diagnostic(true);

This code is used in section 668.

Section 676

⟨ Determine vertical glue shrink setting, then return or goto common_ending 676 ⟩≡

// << Determine the shrink order, 665 >>
glue_order(r) = o;
glue_sign(r) = SHRINKING;
if (total_shrink[o] != 0) {
    glue_set(r) = (double)(-x) / total_shrink[o];
}
else {
    glue_sign(r) = NORMAL;
    set_glue_ratio_zero(glue_set(r)); // there's nothing to shrink
}
if (total_shrink[o] < -x
    && o == NORMAL
    && list_ptr(r) != null)
{
    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 >>
}
else if (o == NORMAL && list_ptr(r) != null) {
    // << Report a tight vbox and |goto common_ending|, if this box is sufficiently bad, 678 >>
}
return r;

This code is used in section 672.

Section 677

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

if (-x - total_shrink[NORMAL] > vfuzz || vbadness < 100) {
    print_ln();
    print_nl("Overfull \\vbox (");
    print_scaled(-x - total_shrink[NORMAL]);
    print("pt too high");
    goto common_ending;
}

This code is used in section 676.

Section 678

⟨ Report a tight vbox and goto common_ending, if this box is sufficiently bad 678 ⟩≡

last_badness = badness(-x, total_shrink[NORMAL]);
if (last_badness > vbadness) {
    print_ln();
    print_nl("Tight \\vbox (badness ");
    print_int(last_badness);
    goto common_ending;
}

This code is used in section 676.

Section 679

When a box is being appended to the current vertical list, the baselineskip calculation is handled by the append_to_vlist routine.

packaging.c
void append_to_vlist(pointer b) {
    scaled d; // deficiency of space between baselines
    pointer p; // a new glue node
    if (prev_depth > IGNORE_DEPTH) {
        d = width(baseline_skip) - prev_depth - height(b);
        if (d < line_skip_limit) {
            p = new_param_glue(LINE_SKIP_CODE);
        }
        else {
            p = new_skip_param(BASELINE_SKIP_CODE);
            width(temp_ptr) = d; // |temp_ptr = glue_ptr(p)|
        }
        link(tail) = p;
        tail = p;
    }
    link(tail) = b;
    tail = b;
    prev_depth = depth(b);
}