Section 980: The page builder

When $T E X$ 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 \topskip 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 \skip 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.

constants.h

#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

⟨ Global variables 13 ⟩+≡

pointer page_tail;       // the final node on the current page
int     page_contents;   // what is on the current page so far?
scaled  page_max_depth;  // maximum box depth on page being built
pointer best_page_break; // break here to get the best page known so far
int     least_page_cost; // the score for this currently best page
scaled  best_size;       // its |page_goal|

Section 981

The page builder has another data structure to keep track of insertions. This is a list of four-word 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, ‘\insert 250’ would correspond to a node whose subtype is 250 (the same as the subtype field of the relevant INS_NODE). These subtype fields are in increasing order, and subtype(PAGE_INS_HEAD) = 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 height-plus-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 $T E X$ 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 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.

constants.h

#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

builder.h

#define broken_ptr(X)   link((X) + 1) // an insertion for this class will break here if anywhere
#define broken_ins(X)   info((X) + 1) // this insertion might break at |broken_ptr|
#define last_ins_ptr(X) link((X) + 2) // the most recent insertion for this |subtype|
#define best_ins_ptr(X) info((X) + 2) // the optimum most recent insertion

⟨ Initialize the special list heads and constant nodes 790 ⟩+≡

subtype(PAGE_INS_HEAD) = 255;
type(PAGE_INS_HEAD) = SPLIT_UP;
link(PAGE_INS_HEAD) = PAGE_INS_HEAD;

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

builder.h

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

scaled  page_so_far[8];   // height and glue of the current page
pointer last_glue;        // used to implement \lastskip
int     last_penalty;     // used to implement \lastpenalty
scaled  last_kern;        // used to implement \lastkern
int     insert_penalties; // sum of the penalties for insertions that were held over

Section 983

⟨ Put each of TeX’s primitives into the hash table 226 ⟩+≡

primitive("pagegoal", SET_PAGE_DIMEN, 0);
primitive("pagetotal", SET_PAGE_DIMEN, 1);
primitive("pagestretch", SET_PAGE_DIMEN, 2);
primitive("pagefilstretch", SET_PAGE_DIMEN, 3);
primitive("pagefillstretch", SET_PAGE_DIMEN, 4);
primitive("pagefilllstretch", SET_PAGE_DIMEN, 5);
primitive("pageshrink", SET_PAGE_DIMEN, 6);
primitive("pagedepth", SET_PAGE_DIMEN, 7);

Section 984

⟨ Cases of print_cmd_chr for symbolic printing of primitives 227 ⟩+≡

case SET_PAGE_DIMEN:
    switch (chr_code) {
    case 0:
        print_esc("pagegoal");
        break;
    
    case 1:
        print_esc("pagetotal");
        break;

    case 2:
        print_esc("pagestretch");
        break;
    
    case 3:
        print_esc("pagefilstretch");
        break;

    case 4:
        print_esc("pagefillstretch");
        break;

    case 5:
        print_esc("pagefilllstretch");
        break;

    case 6:
        print_esc("pageshrink");
        break;
    
    default:
        print_esc("pagedepth");
    }

    break;

Section 985

io.h

#define print_plus(X, Y)                    \
    do {                                    \
        if (page_so_far[(X)] != 0) {        \
            print(" plus ");                \
            print_scaled(page_so_far[(X)]); \
            print((Y));                     \
        }                                   \
    } while (0)

other_printing.c

void print_totals() {
    print_scaled(page_total);
    print_plus(2, "");
    print_plus(3, "fil");
    print_plus(4, "fill");
    print_plus(5, "filll");
    if (page_shrink != 0) {
        print(" minus ");
        print_scaled(page_shrink);
    }
}

Section 986

⟨ Show the status of the current page 986 ⟩≡

if (PAGE_HEAD != page_tail) {
    print_nl("### current page:");
    if (output_active) {
        print(" (held over for next output)");
    }
    show_box(link(PAGE_HEAD));
    if (page_contents > EMPTY) {
        print_nl("total height ");
        print_totals();
        print_nl(" goal height ");
        print_scaled(page_goal);
        r = link(PAGE_INS_HEAD);
        while (r != PAGE_INS_HEAD) {
            print_ln();
            print_esc("insert");
            t = subtype(r);
            print_int(t);
            print(" adds ");
            if (count(t) == 1000) {
                t = height(r);
            }
            else {
                t = x_over_n(height(r), 1000)*count(t);
            }
            print_scaled(t);
            if (type(r) == SPLIT_UP) {
                q = PAGE_HEAD;
                t = 0;
                do {
                    q = link(q);
                    if (type(q) == INS_NODE && subtype(q) == subtype(r)) {
                        incr(t);
                    }
                } while (q != broken_ins(r));
                print(", #");
                print_int(t);
                print(" might split");
            }
            r = link(r);
        }
    }
}

Section 987

Here is a procedure that is called when the page_contents is changing from EMPTY to INSERTS_ONLY or BOX_THERE.

builder.h

#define set_page_so_far_zero(X) page_so_far[(X)] = 0

page_builder.c

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

void freeze_page_specs(small_number s) {
    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;
#ifdef STAT
    if (tracing_pages > 0) {
        begin_diagnostic();
        print_nl("\%\% goal height=");
        print_scaled(page_goal);
        print(", max depth=");
        print_scaled(page_max_depth);
        end_diagnostic(false);
    }
#endif
}

Section 988

Pages are built by appending nodes to the current list in $T E X$ ’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 $T E X$ 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 $T E X$ ’s vertical mode.

When $T E X$ 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;

Section 989

The global variable output_active is true during the time the user’s output routine is driving $T E X$ .

⟨ Global variables 13 ⟩+≡

bool output_active; // are we in the midst of an output routine?

Section 990

⟨ Set initial values of key variables 21 ⟩+≡

output_active = false;
insert_penalties = 0;

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

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

page_builder.c

void box_error(eight_bits n) {
    error();
    begin_diagnostic();
    print_nl("The following box has been deleted:");
    show_box(box(n));
    end_diagnostic(true);
    flush_node_list(box(n));
    box(n) = null;
}

Section 993

The following procedure guarantees that a given box register does not contain an \hbox.

page_builder.c

void ensure_vbox(eight_bits n) {
    pointer p; // the box register contents
    p = box(n);
    if (p != null && type(p) == HLIST_NODE) {
        print_err("Insertions can only be added to a vbox");
        help3("Tut tut: You're trying to \\insert into a")
            ("\\box register that now contains an \\hbox.")
            ("Proceed, and I'll discard its present contents.");
        box_error(n);
    }
}

Section 994

$T E X$ is not always in vertical mode at the time build_page is called; the current mode reflects what $T E X$ 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 $T E X$ ’s central control point.

page_builder.c

// << Declare the procedure called |fire_up|, 1012 >>

// append contributions to the current page
void build_page() {
    pointer p;          // the node being appended
    pointer q, r;       // nodes being examined
    int b, c;           // badness and cost of current page
    int pi = 0;         // penalty to be added to the badness
    int n;              // insertion box number
    scaled delta, h, w; // sizes used for insertion calculations
    
    if (link(CONTRIB_HEAD) == null || output_active) {
        return;
    }
    do {
continue_lbl:
        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 >>
    } while (link(CONTRIB_HEAD) != null);
    
    // << Make the contribution list empty by setting its tail to |CONTRIB_HEAD|, 995 >>
}

Section 995

builder.h

#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) {
    tail = CONTRIB_HEAD; // vertical mode
}
else {
    contrib_tail = CONTRIB_HEAD; // other modes
}

Section 996

⟨ Update the values of last_glue, last_penalty, and last_kern 996 ⟩≡

if (last_glue != MAX_HALFWORD) {
    delete_glue_ref(last_glue);
}
last_penalty = 0;
last_kern = 0;
if (type(p) == GLUE_NODE) {
    last_glue = glue_ptr(p);
    add_glue_ref(last_glue);
}
else {
    last_glue = MAX_HALFWORD;
    if (type(p) == PENALTY_NODE) {
        last_penalty = penalty(p);
    }
    else if (type(p) == KERN_NODE) {
        last_kern = width(p);
    }
}

Section 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) {
    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:

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

Section 999

⟨ Recycle node p 999 ⟩≡

link(CONTRIB_HEAD) = link(p);
link(p) = null;
flush_node_list(p);

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

switch (type(p)) {
case HLIST_NODE:
case VLIST_NODE:
case RULE_NODE:
    if (page_contents < BOX_THERE) {
        // << Initialize the current page, insert the \topskip 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 >>
    }
    break;

case WHATSIT_NODE:
    // << Prepare to move whatsit |p| to the current page, then |goto contribute|, 1364 >>

case GLUE_NODE:
    if (page_contents < BOX_THERE) {
        goto done1;
    }
    else if (precedes_break(page_tail)) {
        pi = 0;
    }
    else {
        goto update_heights;
    }
    break;

case KERN_NODE:
    if (page_contents < BOX_THERE) {
        goto done1;
    }
    else if (link(p) == null) {
        return;
    }
    else if (type(link(p)) == GLUE_NODE) {
        pi = 0;
    }
    else {
        goto update_heights;
    }
    break;

case PENALTY_NODE:
    if (page_contents < BOX_THERE) {
        goto done1;
    }
    else {
        pi = penalty(p);
    }
    break;

case MARK_NODE:
    goto contribute;

case INS_NODE:
    // << Append an insertion to the current page and |goto contribute|, 1008 >>

default:
    confusion("page");
}

Section 1001

⟨ Initialize the current page, insert the \topskip glue ahead of p, and goto continue 1001 ⟩≡

if (page_contents == EMPTY) {
    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)) {
    width(temp_ptr) -= height(p);
}
else {
    width(temp_ptr) = 0;
}
link(q) = p;
link(CONTRIB_HEAD) = q;
goto continue_lbl;

Section 1002

⟨ Prepare to move a box or rule node to the current page, then goto contribute 1002 ⟩≡

page_total += page_depth + height(p);
page_depth = depth(p);
goto contribute;

Section 1003

⟨ Make sure that page_max_depth is not exceeded 1003 ⟩≡

if (page_depth > page_max_depth) {
    page_total += page_depth - page_max_depth;
    page_depth = page_max_depth;
}

Section 1004

⟨ Update the current page measurements with respect to the glue or kern specified by node p 1004 ⟩≡

if (type(p) == KERN_NODE) {
    q = p;
}
else {
    q = glue_ptr(p);
    page_so_far[2 + stretch_order(q)] += stretch(q);
    page_shrink += shrink(q);
    if (shrink_order(q) != NORMAL && shrink(q) != 0) {
        print_err("Infinite glue shrinkage found on current page");
        help4("The page about to be output contains some infinitely")
            ("shrinkable glue, e.g., `\\vss' or `\\vskip 0pt minus 1fil'.")
            ("Such glue doesn't belong there; but you can safely proceed,")
            ("since the offensive shrinkability has been made finite.");
        error();
        r = new_spec(q);
        shrink_order(r) = NORMAL;
        delete_glue_ref(q);
        glue_ptr(p) = r;
        q = r;
    }
}
page_total += page_depth + width(q);
page_depth = 0;

Section 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) {
    // << Compute the badness, |b|, of the current page, using |AWFUL_BAD| if the box is too full, 1007 >>
    if (b < AWFUL_BAD) {
        if (pi <= EJECT_PENALTY) {
            c = pi;
        }
        else if (b < INF_BAD) {
            c = b + pi + insert_penalties;
        }
        else {
            c = DEPLORABLE;
        }
    }
    else {
        c = b;
    }
    if (insert_penalties >= 10000) {
        c = AWFUL_BAD;
    }

#ifdef STAT
    if (tracing_pages > 0) {
        // << Display the page break cost, 1006 >>
    }
#endif

    if (c <= least_page_cost) {
        best_page_break = p;
        best_size = page_goal;
        least_page_cost = c;
        r = link(PAGE_INS_HEAD);
        while (r != PAGE_INS_HEAD) {
            best_ins_ptr(r) = last_ins_ptr(r);
            r = link(r);
        }
    }
    if (c == AWFUL_BAD || pi <= EJECT_PENALTY) {
        fire_up(p); // output the current page at the best place
        if (output_active) {
            return; // user's output routine will act
        }
        goto done; // the page has been shipped out by default output routine
    }
}

Section 1006

⟨ Display the page break cost 1006 ⟩≡

begin_diagnostic();
print_nl("\%");
print(" t=");
print_totals();
print(" g=");
print_scaled(page_goal);
print(" b=");
if (b == AWFUL_BAD) {
    print_char('*');
}
else {
    print_int(b);
}
print(" p=");
print_int(pi);
print(" c=");
if (c == AWFUL_BAD) {
    print_char('*');
}
else {
    print_int(c);
}
if (c <= least_page_cost) {
    print_char('#');
}
end_diagnostic(false);

Section 1007

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

if (page_total < page_goal) {
    if (page_so_far[3] != 0
        || page_so_far[4] != 0
        || page_so_far[5] != 0)
    {
        b = 0;
    }
    else {
        b = badness(page_goal - page_total, page_so_far[2]);
    }
}
else if (page_total - page_goal > page_shrink) {
    b = AWFUL_BAD;
}
else {
    b = badness(page_total - page_goal, page_shrink);
}

Section 1008

⟨ Append an insertion to the current page and goto contribute 1008 ⟩≡

if (page_contents == EMPTY) {
    freeze_page_specs(INSERTS_ONLY);
}
n = subtype(p);
r = PAGE_INS_HEAD;
while (n >= subtype(link(r))) {
    r = link(r);
}
if (subtype(r) != n) {
    // << Create a page insertion node with |subtype(r) = n|, and include the glue correction for box |n| in the current page state, 1009 >>
}
if (type(r) == SPLIT_UP) {
    insert_penalties += float_cost(p);
}
else {
    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) {
        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))
    {
        page_goal -= h;
        height(r) += height(p);
    }
    else {
        // << Find the best way to split the insertion, and change |type(r)| to |SPLIT_UP|, 1010 >>
    }
}
goto contribute;

Section 1009

We take note of the value of \skip n and the height plus depth of \box n only when the first \insert n node is encountered for a new page. A user who changes the contents of \box n after that first \insert n had better be either extremely careful or extremely lucky, or both.

⟨ Create a page insertion node with subtype(r) = n, and include the glue correction for box n in the current page state 1009 ⟩≡

q = get_node(PAGE_INS_NODE_SIZE);
link(q) = link(r);
link(r) = q;
r = q;
subtype(r) = n;
type(r) = INSERTING;
ensure_vbox(n);
if (box(n) == null) {
    height(r) = 0;
}
else {
    height(r) = height(box(n)) + depth(box(n));
}
best_ins_ptr(r) = null;
q = skip(n);
if (count(n) == 1000) {
    h = height(r);
}
else {
    h = x_over_n(height(r), 1000)*count(n);
}
page_goal -= h + width(q);
page_so_far[2 + stretch_order(q)] += stretch(q);
page_shrink += shrink(q);
if (shrink_order(q) != NORMAL && shrink(q) != 0) {
    print_err("Infinite glue shrinkage inserted from ");
    print_esc("skip");
    print_int(n);
    help3("The correction glue for page breaking with insertions")
        ("must have finite shrinkability. But you may proceed,")
        ("since the offensive shrinkability has been made finite.");
    error();
}

Section 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 \dimen 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 \count n over 1000.) Now we will choose the best way to break the vlist of the insertion, using the same criteria as in the \vsplit operation.

⟨ Find the best way to split the insertion, and change type(r) to SPLIT_UP 1010 ⟩≡

if (count(n) <= 0) {
    w = MAX_DIMEN;
}
else {
    w = page_goal - page_total - page_depth;
    if (count(n) != 1000) {
        w = x_over_n(w, count(n))*1000;
    }
}
if (w > dimen(n) - height(r)) {
    w = dimen(n) - height(r);
}
q = vert_break(ins_ptr(p), w, depth(p));
height(r) += best_height_plus_depth;

#ifdef STAT
if (tracing_pages > 0) {
    // << Display the insertion split cost, 1011 >>
}
#endif

if (count(n) != 1000) {
  best_height_plus_depth = x_over_n(best_height_plus_depth, 1000)*count(n);
}
page_goal -= best_height_plus_depth;
type(r) = SPLIT_UP;
broken_ptr(r) = q;
broken_ins(r) = p;
if (q == null) {
    insert_penalties += EJECT_PENALTY;
}
else if (type(q) == PENALTY_NODE) {
    insert_penalties += penalty(q);
}

Section 1011

⟨ Display the insertion split cost 1011 ⟩≡

begin_diagnostic();
print_nl("\% split");
print_int(n);
print(" to ");
print_scaled(w);
print_char(',');
print_scaled(best_height_plus_depth);
print(" p=");
if (q == null) {
    print_int(EJECT_PENALTY);
}
else if (type(q) == PENALTY_NODE) {
    print_int(penalty(q));
}
else {
    print_char('0');
}
end_diagnostic(false);

Section 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 $\neq =$ null implies first_mark $\neq =$ 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 ⟩≡

void fire_up(pointer c) {
    pointer p, q, r, s;          // nodes being examined and/or changed
    pointer prev_p;              // predecessor of |p|
    int n;                       // insertion box number
    bool wait;                   // should the present insertion be held over?
    int save_vbadness;           // saved value of |vbadness|
    scaled save_vfuzz;           // saved value of |vfuzz|
    pointer save_split_top_skip; // saved value of |split_top_skip|
    
    // << Set the value of |output_penalty|, 1013 >>
    if (bot_mark != null) {
        if (top_mark != null) {
            delete_token_ref(top_mark);
        }
        top_mark = bot_mark;
        add_token_ref(top_mark);
        delete_token_ref(first_mark);
        first_mark = null;
    }

    // << 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) {
        first_mark = top_mark;
        add_token_ref(top_mark);
    }
    if (output_routine != null) {
        if (dead_cycles >= max_dead_cycles) {
            // << 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 >>
}

Section 1013

⟨ Set the value of output_penalty 1013 ⟩≡

if (type(best_page_break) == PENALTY_NODE) {
    geq_word_define(INT_BASE + OUTPUT_PENALTY_CODE, penalty(best_page_break));
    penalty(best_page_break) = INF_PENALTY;
}
else {
    geq_word_define(INT_BASE + OUTPUT_PENALTY_CODE, INF_PENALTY);
}

Section 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) {
    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) {
    // << 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) {
    if (type(p) == INS_NODE) {
        if (holding_inserts <= 0) {
            // << 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 >>
        }
    }
    else if (type(p) == MARK_NODE) {
        // << Update the values of |first_mark| and |bot_mark|, 1016 >>
    }
    prev_p = p;
    p = link(prev_p);
}
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 >>

Section 1015

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

if (box(255) != null) {
    print_err("");
    print_esc("box");
    print("255 is not void");
    help2("You shouldn't use \\box255 except in \\output routines.")
        ("Proceed, and I'll discard its present contents.");
    box_error(255);
}

Section 1016

⟨ Update the values of first_mark and bot_mark 1016 ⟩≡

if (first_mark == null) {
    first_mark = mark_ptr(p);
    add_token_ref(first_mark);
}
if (bot_mark != null) {
    delete_token_ref(bot_mark);
}
bot_mark = mark_ptr(p);
add_token_ref(bot_mark);

Section 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 \skip 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) {
    if (link(CONTRIB_HEAD) == null) {
        if (nest_ptr == 0) {
            tail = page_tail;
        }
        else {
            contrib_tail = page_tail;
        }
    }
    link(page_tail) = link(CONTRIB_HEAD);
    link(CONTRIB_HEAD) = p;
    link(prev_p) = null;
}
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) {
    delete_glue_ref(last_glue);
}
// this sets |last_glue = MAX_HALFWORD|:
// << Start a new current page, 991 >>
if (q != HOLD_HEAD) {
    link(PAGE_HEAD) = link(HOLD_HEAD);
    page_tail = q;
}

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

r = link(PAGE_INS_HEAD);
while (r != PAGE_INS_HEAD) {
    if (best_ins_ptr(r) != null) {
        n = subtype(r);
        ensure_vbox(n);
        if (box(n) == null) {
            box(n) = new_null_box();
        }
        p = box(n) + LIST_OFFSET;
        while (link(p) != null) {
            p = link(p);
        }
        last_ins_ptr(r) = p;
    }
    r = link(r);
}

Section 1019

⟨ Delete the page-insertion nodes 1019 ⟩≡

r = link(PAGE_INS_HEAD);
while (r != PAGE_INS_HEAD) {
    q = link(r);
    free_node(r, PAGE_INS_NODE_SIZE);
    r = q;
}
link(PAGE_INS_HEAD) = PAGE_INS_HEAD;

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

r = link(PAGE_INS_HEAD);
while (subtype(r) != subtype(p)) {
    r = link(r);
}
if (best_ins_ptr(r) == null) {
    wait = true;
}
else {
    wait = false;
    s = last_ins_ptr(r);
    link(s) = ins_ptr(p);
    if (best_ins_ptr(r) == p) {
        // << 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 {
        while (link(s) != null) {
            s = link(s);
        }
        last_ins_ptr(r) = s;
    }
}
// << Either append the insertion node |p| after node |q|, and remove it from the current page, or delete |node(p)|, 1022 >>

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

if (type(r) == SPLIT_UP
    && broken_ins(r) == p
    && broken_ptr(r) != null)
{
    while (link(s) != broken_ptr(r)) {
        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) {
        temp_ptr = vpack(ins_ptr(p), NATURAL);
        height(p) = height(temp_ptr) + depth(temp_ptr);
        free_node(temp_ptr, BOX_NODE_SIZE);
        wait = true;
    }
}
best_ins_ptr(r) = null;
n = subtype(r);
temp_ptr = list_ptr(box(n));
free_node(box(n), BOX_NODE_SIZE);
box(n) = vpack(temp_ptr, NATURAL);

Section 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) {
    link(q) = p;
    q = p;
    incr(insert_penalties);
}
else {
    delete_glue_ref(split_top_ptr(p));
    free_node(p, INS_NODE_SIZE);
}
p = prev_p;

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

if (link(PAGE_HEAD) != null) {
    if (link(CONTRIB_HEAD) == null) {
        if (nest_ptr == 0) {
            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;
}
ship_out(box(255));
box(255) = null;

Section 1024

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

print_err("Output loop---");
print_int(dead_cycles);
print(" consecutive dead cycles");
help3("I've concluded that your \\output is awry; it never does a")
    ("\\shipout, so I'm shipping \\box255 out myself. Next time")
    ("increase \\maxdeadcycles if you want me to be more patient!");
error();

Section 1025

⟨ Fire up the user’s output routine and return 1025 ⟩≡

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;

Section 1026

When the user’s output routine finishes, it has constructed a vlist in internal vertical mode, and $T E X$ will do the following:

⟨ Resume the page builder after an output routine has come to an end 1026 ⟩≡

if (loc != null
    || (token_type != OUTPUT_TEXT && token_type != BACKED_UP))
{
    // << 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) {
    // current list goes after heldover insertions
    link(page_tail) = link(head);
    page_tail = tail;
}
if (link(PAGE_HEAD) != null) {
    // and both go before heldover contributions
    if (link(CONTRIB_HEAD) == null) {
        contrib_tail = page_tail;
    }
    link(page_tail) = link(CONTRIB_HEAD);
    link(CONTRIB_HEAD) = link(PAGE_HEAD);
    link(PAGE_HEAD) = null;
    page_tail = PAGE_HEAD;
}
pop_nest();
build_page();

Section 1027

⟨ Recover from an unbalanced output routine 1027 ⟩≡

print_err("Unbalanced output routine");
help2("Your sneaky output routine has problematic {'s and/or }'s.")
    ("I can't handle that very well; good luck.");
error();
do {
    get_token();
} while (loc != null);
// loops forever if reading from a file, since |null = MIN_HALFWORD <= 0|

Section 1028

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

if (box(255) != null) {
    print_err("Output routine didn't use all of ");
    print_esc("box");
    print_int(255);
    help3("Your \\output commands should empty \\box255,")
        ("e.g., by saying `\\shipout\\box255'.")
        ("Proceed; I'll discard its present contents.");
    box_error(255);
}

TeX in C