§768  TEX82  PART 37: ALIGNMENT 285
768. Alignment. It’s sort of a miracle whenever  and  work, because they cut across

so many of the control structures of TEX.

Therefore the present page is probably not the best place for a beginner to start reading this program; it is better to master everything else first.

Let us focus our thoughts on an example of what the input might be, in order to get some idea about how the alignment miracle happens. The example doesn’t do anything useful, but it is sufficiently general to indicate all of the special cases that must be dealt with; please do not be disturbed by its apparent complexity and meaninglessness.

                         #
                                   #
                                   #

Here’s what happens:

(0) When ‘ ’ is scanned, the scan spec routine places the 300pt dimension onto the save stack , and an align group code is placed above it. This will make it possible to complete the alignment when the matching ‘ ’ is found.

(1) The preamble is scanned next. Macros in the preamble are not expanded, except as part of a tabskip specification. For example, if had been a macro in the preamble above, it would have been expanded, since TEX must look for ‘ ’ as part of the tabskip glue. A “preamble list” is constructed based on the user’s preamble; in our case it contains the following seven items:

(the tabskip preceding column 1)
−∞  (preamble info for column 1)
(the tabskip between columns 1 and 2)
−∞  (preamble info for column 2)
(the tabskip between columns 2 and 3)
−∞  (preamble info for column 3)
(the tabskip following column 3)

These “alignrecord” entries have the same size as an unset node, since they will later be converted into such nodes. However, at the moment they have no type or subtype fields; they have info fields instead, and these info fields are initially set to the value end span, for reasons explained below. Furthermore, the alignrecord nodes have no height or depth fields; these are renamed u part and v part , and they point to token lists for the templates of the alignment. For example, the u part field in the first alignrecord points to the token list ‘ ’, i.e., the template preceding the ‘#’ for column 1.

(2) TEX now looks at what follows the that ended the preamble. It is not ‘ ’ or ‘ ’, so this input is put back to be read again, and the template ‘ ’ is fed to the scanner. Just before reading ‘ ’, TEX goes into restricted horizontal mode. Just after reading ‘ ’, TEX will see ‘ ’, and then (when the is sensed) TEX will see ‘ ’. Then TEX scans an endv token, indicating the end of a column. At this point an unset node is created, containing the contents of the current hlist (i.e., ‘ ’). The natural width of this unset node replaces the width field of the alignrecord for column 1; in general, the alignrecords will record the maximum natural width that has occurred so far in a given column.

(3) Since ‘ ’ follows the ‘ ’, the templates for column 2 are now bypassed. Again TEX goes into restricted horizontal mode and makes an unset node from the resulting hlist; but this time the hlist contains simply ‘ ’. The natural width of the new unset box is remembered in the width field of the alignrecord for column 2.

286  PART 37: ALIGNMENT  TEX82 §768

(4) A third unset node is created for column 3, using essentially the mechanism that worked for column 1; this unset box contains ‘ ’. The vertical rule in this case has running dimensions that will later extend to the height and depth of the whole first row, since each unset node in a row will eventually inherit the height and depth of its enclosing box.

(5) The first row has now ended; it is made into a single unset box comprising the following seven items:

The width of this unset row is unimportant, but it has the correct height and depth, so the correct baselineskip glue will be computed as the row is inserted into a vertical list.

(6) Since ‘ ’ follows the current , TEX appends additional material (in this case ) to the vertical list. While processing this material, TEX will be in internal vertical mode, and no align group will be on save stack .

(7) The next row produces an unset box that looks like this:

(empty)

The natural width of the unset box that spans columns 1 and 2 is stored in a “span node,” which we will explain later; the info field of the alignrecord for column 1 now points to the new span node, and the info of the span node points to end span.

(8) The final row produces the unset box

(empty)

A new span node is attached to the alignrecord for column 2.

(9) The last step is to compute the true column widths and to change all the unset boxes to hboxes, appending the whole works to the vertical list that encloses the . The rules for deciding on the final widths of each unset column box will be explained below. Note that as is being processed, we fearlessly give up control to the rest of TEX. At critical junctures, an alignment routine is called upon to step in and do some little action, but most of the time these routines just lurk in the background. It’s something like post-hypnotic suggestion.

769. We have mentioned that alignrecords contain no height or depth fields. Their glue sign and glue order are pre-empted as well, since it is necessary to store information about what to do when a template ends. This information is called the extra info field.

define u part (#) ≡ mem[# + height offset ].int { pointer to ⟨u_{j}⟩ token list }

define v part (#) ≡ mem[# + depth offset ].int { pointer to ⟨v_{j}⟩ token list }

define extra info(#) ≡ info(# + list offset ) { info to remember during template } 770. Alignments can occur within alignments, so a small stack is used to access the alignrecord information. At each level we have a preamble pointer, indicating the beginning of the preamble list; a cur align pointer, indicating the current position in the preamble list; a cur span pointer, indicating the value of cur align at the beginning of a sequence of spanned columns; a cur loop pointer, indicating the tabskip glue before an alignrecord that should be copied next if the current list is extended; and the align state variable, which indicates the nesting of braces so that and and tab marks are properly intercepted. There also are pointers cur head and cur tail to the head and tail of a list of adjustments being moved out from horizontal mode to vertical mode.

The current values of these seven quantities appear in global variables; when they have to be pushed down, they are stored in 5-word nodes, and align ptr points to the topmost such node.

define preamble ≡ link (align head ) { the current preamble list }

define align stack node size = 5 { number of mem words to save alignment states } ⟨ Global variables 13 ⟩ +≡ cur align: pointer ; { current position in preamble list } cur span: pointer ; { start of currently spanned columns in preamble list } cur loop: pointer ; { place to copy when extending a periodic preamble } align ptr : pointer ; { most recently pushed-down alignment stack node } cur head , cur tail : pointer ; { adjustment list pointers }

771. The align state and preamble variables are initialized elsewhere. ⟨ Set initial values of key variables 21 ⟩ +≡

align ptr ← null ; cur align ← null ; cur span ← null ; cur loop ← null ; cur head ← null ; cur tail ← null ;

772. Alignment stack maintenance is handled by a pair of trivial routines called push alignment and pop alignment . procedure push alignment ;

var p: pointer ; { the new alignment stack node }

begin p ← get node(align stack node size); link (p) ← align ptr ; info(p) ← cur align;

llink (p) ← preamble; rlink (p) ← cur span; mem[p + 2].int ← cur loop; mem[p + 3].int ← align state; info(p + 4) ← cur head ; link (p + 4) ← cur tail ; align ptr ← p; cur head ← get avail ; end;

procedure pop alignment ; var p: pointer ; { the top alignment stack node } begin free avail (cur head ); p ← align ptr ; cur tail ← link (p + 4); cur head ← info(p + 4); align state ← mem[p + 3].int ; cur loop ← mem[p + 2].int ; cur span ← rlink (p); preamble ← llink (p); cur align ← info(p); align ptr ← link (p); free node(p, align stack node size); end;

773. TEX has eight procedures that govern alignments: init align and fin align are used at the very beginning and the very end; init row and fin row are used at the beginning and end of individual rows; init span is used at the beginning of a sequence of spanned columns (possibly involving only one column); init col and fin col are used at the beginning and end of individual columns; and align peek is used after to see whether the next item is .

We shall consider these routines in the order they are first used during the course of a complete , namely init align, align peek , init row , init span, init col , fin col , fin row , fin align.

774. When  or  has been scanned in an appropriate mode, TEX calls init align, whose

task is to get everything off to a good start. This mostly involves scanning the preamble and putting its information into the preamble list. ⟨ Declare the procedure called get preamble token 782 ⟩ procedure align peek ; forward ; procedure normal paragraph; forward ; procedure init align;

label done, done1 , done2 , continue; var save cs ptr : pointer ; { warning index value for error messages }

p: pointer ; { for short-term temporary use } begin save cs ptr ← cur cs ; { or , usually } push alignment ; align state ← −1000000; { enter a new alignment level } ⟨ Check for improper alignment in displayed math 776 ⟩; push nest ; { enter a new semantic level } ⟨ Change current mode to −vmode for , −hmode for 775 ⟩; scan spec(align group, false); ⟨ Scan the preamble and record it in the preamble list 777 ⟩; new save level (align group); if every cr ≠ null then begin token list (every cr , every cr text ); align peek ; { look for or } end;

775. In vertical modes, prev depth already has the correct value. But if we are in mmode (displayed formula mode), we reach out to the enclosing vertical mode for the prev depth value that produces the correct baseline calculations. ⟨ Change current mode to −vmode for , −hmode for 775 ⟩ ≡

if mode = mmode then begin mode ← −vmode; prev depth ← nest [nest ptr − 2].aux field .sc; end

else if mode > 0 then negate(mode)

This code is used in section 774.

776. When is used as a displayed formula, there should be no other pieces of mlists present. ⟨ Check for improper alignment in displayed math 776 ⟩ ≡

if (mode = mmode) ∧ ((tail ≠ head ) ∨ (incompleat noad ≠ null )) then

begin print err (  ␣ ); print esc(  ); print ( ␣      ␣$$´ );
help3 (  ␣   ␣   ␣       ␣          ␣     ␣  )

  (  ␣  ␣       ␣   ␣   ␣         ␣      ␣  ␣       ␣$$´  )

( ␣ ´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ); error ; flush math; end

This code is used in section 774.

777. ⟨ Scan the preamble and record it in the preamble list 777 ⟩ ≡ preamble ← null ; cur align ← align head ; cur loop ← null ; scanner status ← aligning ; warning index ← save cs ptr ; align state ← −1000000; { at this point, cur cmd = left brace } loop begin ⟨ Append the current tabskip glue to the preamble list 778 ⟩;

if cur cmd = car ret then goto done; { ends the preamble }

⟨ Scan preamble text until cur cmd is tab mark or car ret , looking for changes in the tabskip glue;

append an alignrecord to the preamble list 779 ⟩; end;

done: scanner status ← normal

This code is used in section 774.

778. ⟨ Append the current tabskip glue to the preamble list 778 ⟩ ≡ link (cur align) ← new param glue(tab skip code); cur align ← link (cur align)

This code is used in section 777.

779. ⟨ Scan preamble text until cur cmd is tab mark or car ret , looking for changes in the tabskip glue;

append an alignrecord to the preamble list 779 ⟩ ≡ ⟨ Scan the template ⟨u_{j}⟩, putting the resulting token list in hold head 783 ⟩; link (cur align) ← new null box ; cur align ← link (cur align); { a new alignrecord } info(cur align) ← end span; width(cur align) ← null flag ; u part (cur align) ← link (hold head ); ⟨ Scan the template ⟨v_{j}⟩, putting the resulting token list in hold head 784 ⟩; v part (cur align) ← link (hold head )

This code is used in section 777.

780. We enter ‘ ’ into eqtb with tab mark as its command code, and with span code as the command modifier. This makes TEX interpret it essentially the same as an alignment delimiter like ‘ ’, yet it is recognizably different when we need to distinguish it from a normal delimiter. It also turns out to be useful to give a special cr code to ‘ ’, and an even larger cr cr code to ‘ ’.

The end of a template is represented by two “frozen” control sequences called . The first has the command code end template, which is > outer call , so it will not easily disappear in the presence of errors. The get x token routine converts the first into the second, which has endv as its command code.

define span code = 256 { distinct from any character } define cr code = 257 { distinct from span code and from any character } define cr cr code = cr code + 1 { this distinguishes from } define end template token ≡ cs token flag + frozen end template

⟨ Put each of TEX’s primitives into the hash table 226 ⟩ +≡ primitive( , tab mark , span code);

primitive(  , car ret , cr code); text (frozen cr ) ←  ; eqtb[frozen cr ] ← eqtb[cur val ];
primitive(  , car ret , cr cr code); text (frozen end template) ←  ;

text (frozen endv ) ← ; eq type(frozen endv ) ← endv ; equiv (frozen endv ) ← null list ; eq level (frozen endv ) ← level one; eqtb[frozen end template] ← eqtb[frozen endv ]; eq type(frozen end template) ← end template;

781. ⟨ Cases of print cmd chr for symbolic printing of primitives 227 ⟩ +≡ tab mark : if chr code = span code then print esc( )

else chr cmd ( ␣ ␣ ␣ ); car ret : if chr code = cr code then print esc( )

else print esc( ); 782. The preamble is copied directly, except that causes a change to the tabskip glue, thereby possibly expanding macros that immediately follow it. An appearance of also causes such an expansion.

Note that if the preamble contains ‘ ’, the ‘ ’ token survives in the preamble and the ‘ ’ defines new tabskip glue (locally). ⟨ Declare the procedure called get preamble token 782 ⟩ ≡ procedure get preamble token;

label restart ; begin restart : get token; while (cur chr = span code) ∧ (cur cmd = tab mark ) do

begin get token; { this token will be expanded once } if cur cmd > max command then

begin expand ; get token;

end; end;

if cur cmd = endv then fatal error ( ␣ ␣ ␣ ␣ ␣ ); if (cur cmd = assign glue) ∧ (cur chr = glue base + tab skip code) then

begin scan optional equals ; scan glue(glue val ); if global defs > 0 then geq define(glue base + tab skip code, glue ref , cur val ) else eq define(glue base + tab skip code, glue ref , cur val ); goto restart ; end;

end;

This code is used in section 774.

783. Spaces are eliminated from the beginning of a template. ⟨ Scan the template ⟨u_{j}⟩, putting the resulting token list in hold head 783 ⟩ ≡

p ← hold head ; link (p) ← null ; loop begin get preamble token;

if cur cmd = mac param then goto done1 ; if (cur cmd ≤ car ret ) ∧ (cur cmd ≥ tab mark ) ∧ (align state = −1000000) then

if (p = hold head ) ∧ (cur loop = null ) ∧ (cur cmd = tab mark ) then cur loop ← cur align

else begin print err (  ␣#␣        ␣  ␣         ␣  );

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

(  ␣  ␣ ´ ␣   ␣   ␣   ␣     ␣    ␣    ␣  ); back error ; goto done1 ;

end else if (cur cmd ≠ spacer ) ∨ (p ≠ hold head ) then

begin link (p) ← get avail ; p ← link (p); info(p) ← cur tok ;

end; end;

done1 :

This code is used in section 779.

784. ⟨ Scan the template ⟨v_{j}⟩, putting the resulting token list in hold head 784 ⟩ ≡ p ← hold head ; link (p) ← null ; loop begin continue: get preamble token;

if (cur cmd ≤ car ret ) ∧ (cur cmd ≥ tab mark ) ∧ (align state = −1000000) then goto done2 ; if cur cmd = mac param then

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

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

(  ␣    ␣    ␣  ␣ ´ ␣        ␣   ␣   ␣   ␣  ); error ; goto continue;

end; link (p) ← get avail ; p ← link (p); info(p) ← cur tok ; end;

done2 : link (p) ← get avail ; p ← link (p); info(p) ← end template token { put at the end }

This code is used in section 779.

785. The tricky part about alignments is getting the templates into the scanner at the right time, and recovering control when a row or column is finished.

We usually begin a row after each has been sensed, unless that is followed by or by the right brace that terminates the alignment. The align peek routine is used to look ahead and do the right thing; it either gets a new row started, or gets a started, or finishes off the alignment. ⟨ Declare the procedure called align peek 785 ⟩ ≡ procedure align peek ;

label restart ;

begin restart : align state ← 1000000; ⟨ Get the next non-blank non-call token 406 ⟩;

if cur cmd = no align then begin scan left brace; new save level (no align group); if mode = −vmode then normal paragraph; end

else if cur cmd = right brace then fin align

else if (cur cmd = car ret ) ∧ (cur chr = cr cr code) then goto restart { ignore }

else begin init row ; { start a new row } init col ; { start a new column and replace what we peeked at } end;

end;

This code is used in section 800.

786. To start a row (i.e., a ‘row’ that rhymes with ‘dough’ but not with ‘bough’), we enter a new semantic level, copy the first tabskip glue, and change from internal vertical mode to restricted horizontal mode or vice versa. The space factor and prev depth are not used on this semantic level, but we clear them to zero just to be tidy. ⟨ Declare the procedure called init span 787 ⟩ procedure init row ;

begin push nest ; mode ← (−hmode − vmode) − mode;

if mode = −hmode then space factor ← 0 else prev depth ← 0;

tail append (new glue(glue ptr (preamble))); subtype(tail ) ← tab skip code + 1;

cur align ← link (preamble); cur tail ← cur head ; init span(cur align);

end; 787. The parameter to init span is a pointer to the alignrecord where the next column or group of columns will begin. A new semantic level is entered, so that the columns will generate a list for subsequent packaging. ⟨ Declare the procedure called init span 787 ⟩ ≡ procedure init span(p : pointer );

begin push nest ;

if mode = −hmode then space factor ← 1000

else begin prev depth ← ignore depth; normal paragraph;

end; cur span ← p; end;

This code is used in section 786.

788. When a column begins, we assume that cur cmd is either omit or else the current token should be put back into the input until the ⟨u_{j}⟩ template has been scanned. (Note that cur cmd might be tab mark or car ret .) We also assume that align state is approximately 1000000 at this time. We remain in the same mode, and start the template if it is called for. procedure init col ;

begin extra info(cur align) ← cur cmd ;

if cur cmd = omit then align state ← 0

else begin back input ; begin token list (u part (cur align), u template);

end; { now align state = 1000000 } end;

789. The scanner sets align state to zero when the ⟨u_{j}⟩ template ends. When a subsequent or or tab mark occurs with align state = 0, the scanner activates the following code, which fires up the ⟨v_{j}⟩ template. We need to remember the cur chr , which is either cr cr code, cr code, span code, or a character code, depending on how the column text has ended.

This part of the program had better not be activated when the preamble to another alignment is being scanned. ⟨ Insert the ⟨v_{j}⟩ template and goto restart 789 ⟩ ≡

begin if scanner status = aligning then

fatal error ( ␣ ␣ ␣ ␣ ␣ ); cur cmd ← extra info(cur align); extra info(cur align) ← cur chr ; if cur cmd = omit then begin token list (omit template, v template) else begin token list (v part (cur align), v template); align state ← 1000000; goto restart ; end

This code is used in section 342.

790. The token list omit template just referred to is a constant token list that contains the special control sequence only. ⟨ Initialize the special list heads and constant nodes 790 ⟩ ≡

info(omit template) ← end template token; { link (omit template) = null }

See also sections 797, 820, 981, and 988. This code is used in section 164.

791. When the endv command at the end of a ⟨v_{j}⟩ template comes through the scanner, things really start to happen; and it is the fin col routine that makes them happen. This routine returns true if a row as well as a column has been finished. function fin col : boolean;

label exit ; var p: pointer ; { the alignrecord after the current one }

q, r: pointer ; { temporary pointers for list manipulation }

s: pointer ; { a new span node }

u: pointer ; { a new unset box }

w: scaled ; { natural width }

o: glue ord ; { order of infinity }

n: halfword ; { span counter } begin if cur align = null then confusion( ); q ← link (cur align); if q = null then confusion( ); if align state < 500000 then fatal error ( ␣ ␣ ␣ ␣ ␣ ); p ← link (q); ⟨ If the preamble list has been traversed, check that the row has ended 792 ⟩; if extra info(cur align) ≠ span code then

begin unsave; new save level (align group);

⟨ Package an unset box for the current column and record its width 796 ⟩;

⟨ Copy the tabskip glue between columns 795 ⟩;

if extra info(cur align) ≥ cr code then begin fin col ← true; return; end;

init span(p);

end; align state ← 1000000; ⟨ Get the next non-blank non-call token 406 ⟩; cur align ← p; init col ; fin col ← false;

exit : end;

792. ⟨ If the preamble list has been traversed, check that the row has ended 792 ⟩ ≡

if (p = null ) ∧ (extra info(cur align) < cr code) then if cur loop ≠ null then ⟨ Lengthen the preamble periodically 793 ⟩

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

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

( ␣ ´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ); extra info(cur align) ← cr code; error ; end

This code is used in section 791.

793. ⟨ Lengthen the preamble periodically 793 ⟩ ≡ begin link (q) ← new null box ; p ← link (q); { a new alignrecord } info(p) ← end span; width(p) ← null flag ; cur loop ← link (cur loop); ⟨ Copy the templates from node cur loop into node p 794 ⟩; cur loop ← link (cur loop); link (p) ← new glue(glue ptr (cur loop)); end

This code is used in section 792.

794. ⟨ Copy the templates from node cur loop into node p 794 ⟩ ≡ q ← hold head ; r ← u part (cur loop); while r ≠ null do

begin link (q) ← get avail ; q ← link (q); info(q) ← info(r); r ← link (r);

end; link (q) ← null ; u part (p) ← link (hold head ); q ← hold head ; r ← v part (cur loop); while r ≠ null do

begin link (q) ← get avail ; q ← link (q); info(q) ← info(r); r ← link (r);

end; link (q) ← null ; v part (p) ← link (hold head )

This code is used in section 793.

795. ⟨ Copy the tabskip glue between columns 795 ⟩ ≡ tail append (new glue(glue ptr (link (cur align)))); subtype(tail ) ← tab skip code + 1

This code is used in section 791.

796. ⟨ Package an unset box for the current column and record its width 796 ⟩ ≡

begin if mode = −hmode then begin adjust tail ← cur tail ; u ← hpack (link (head ), natural ); w ← width(u); cur tail ← adjust tail ; adjust tail ← null ; end

else begin u ← vpackage(link (head ), natural , 0); w ← height (u);

end; n ← min quarterword ; { this represents a span count of 1 } if cur span ≠ cur align then ⟨ Update width entry for spanned columns 798 ⟩ else if w > width(cur align) then width(cur align) ← w; type(u) ← unset node; span count (u) ← n; ⟨ Determine the stretch order 659 ⟩; glue order (u) ← o; glue stretch(u) ← total stretch[o]; ⟨ Determine the shrink order 665 ⟩; glue sign(u) ← o; glue shrink (u) ← total shrink [o]; pop nest ; link (tail ) ← u; tail ← u; end

This code is used in section 791.

797. A span node is a 2-word record containing width, info, and link fields. The link field is not really a link, it indicates the number of spanned columns; the info field points to a span node for the same starting column, having a greater extent of spanning, or to end span, which has the largest possible link field; the width field holds the largest natural width corresponding to a particular set of spanned columns.

A list of the maximum widths so far, for spanned columns starting at a given column, begins with the info field of the alignrecord for that column.

define span node size = 2 { number of mem words for a span node } ⟨ Initialize the special list heads and constant nodes 790 ⟩ +≡

link (end span) ← max quarterword + 1; info(end span) ← null ; 798. ⟨ Update width entry for spanned columns 798 ⟩ ≡

begin q ← cur span; repeat incr (n); q ← link (link (q)); until q = cur align; if n > max quarterword then confusion( ␣ ); { this can happen, but won’t } q ← cur span; while link (info(q)) < n do q ← info(q); if link (info(q)) > n then

begin s ← get node(span node size); info(s) ← info(q); link (s) ← n; info(q) ← s; width(s) ← w; end

else if width(info(q)) < w then width(info(q)) ← w; end

This code is used in section 796.

799. At the end of a row, we append an unset box to the current vlist (for ) or the current hlist (for ). This unset box contains the unset boxes for the columns, separated by the tabskip glue. Everything will be set later. procedure fin row ;

var p: pointer ; { the new unset box } begin if mode = −hmode then

begin p ← hpack (link (head ), natural ); pop nest ; append to vlist (p);

if cur head ≠ cur tail then begin link (tail ) ← link (cur head ); tail ← cur tail ; end;

end else begin p ← vpack (link (head ), natural ); pop nest ; link (tail ) ← p; tail ← p; space factor ← 1000;

end; type(p) ← unset node; glue stretch(p) ← 0; if every cr ≠ null then begin token list (every cr , every cr text ); align peek ; end; { note that glue shrink (p) = 0 since glue shrink ≡ shift amount } 800. Finally, we will reach the end of the alignment, and we can breathe a sigh of relief that memory hasn’t overflowed. All the unset boxes will now be set so that the columns line up, taking due account of spanned columns. procedure do assignments ; forward ; procedure resume after display ; forward ; procedure build page; forward ; procedure fin align;

var p, q, r, s, u, v: pointer ; { registers for the list operations } t, w: scaled ; { width of column } o: scaled ; { shift offset for unset boxes } n: halfword ; { matching span amount } rule save: scaled ; { temporary storage for overfull rule } aux save: memory word ; { temporary storage for aux }

begin if cur group ≠ align group then confusion( ); unsave; { that align group was for individual entries } if cur group ≠ align group then confusion( ); unsave; { that align group was for the whole alignment } if nest [nest ptr − 1].mode field = mmode then o ← display indent else o ← 0; ⟨ Go through the preamble list, determining the column widths and changing the alignrecords to dummy

unset boxes 801 ⟩; ⟨ Package the preamble list, to determine the actual tabskip glue amounts, and let p point to this

prototype box 804 ⟩; ⟨ Set the glue in all the unset boxes of the current list 805 ⟩; flush node list (p); pop alignment ; ⟨ Insert the current list into its environment 812 ⟩; end;

⟨ Declare the procedure called align peek 785 ⟩ 801. It’s time now to dismantle the preamble list and to compute the column widths. Let w_{ij} be the maximum of the natural widths of all entries that span columns i through j, inclusive. The alignrecord for column i contains w_{ii} in its width field, and there is also a linked list of the nonzero w_{ij} for increasing j, accessible via the info field; these span nodes contain the value j − i − 1 + min quarterword in their link fields. The values of w_{ii} were initialized to null flag , which we regard as −∞.

The final column widths are defined by the formula

w_{j} = max_{1≤i≤j}(w_{ij} − ∑_{i≤k<j}(t_{k} + w_{k})),

where t_{k} is the natural width of the tabskip glue between columns k and k + 1. However, if w_{ij} = −∞ for all i in the range 1 ≤ i ≤ j (i.e., if every entry that involved column j also involved column j + 1), we let w_{j} = 0, and we zero out the tabskip glue after column j.

TEX computes these values by using the following scheme: First w_{1} = w_{11}. Then replace w_{2j} by max(w_{2j}, w_{1j} − t_{1} − w_{1}), for all j > 1. Then w_{2} = w_{22}. Then replace w_{3j} by max(w_{3j}, w_{2j} − t_{2} − w_{2}) for all j > 2; and so on. If any w_{j} turns out to be −∞, its value is changed to zero and so is the next tabskip. ⟨ Go through the preamble list, determining the column widths and changing the alignrecords to dummy

unset boxes 801 ⟩ ≡ q ← link (preamble); repeat flush list (u part (q)); flush list (v part (q)); p ← link (link (q));

if width(q) = null flag then ⟨ Nullify width(q) and the tabskip glue following this column 802 ⟩; if info(q) ≠ end span then

⟨ Merge the widths in the span nodes of q with those of p, destroying the span nodes of q 803 ⟩; type(q) ← unset node; span count (q) ← min quarterword ; height (q) ← 0; depth(q) ← 0; glue order (q) ← normal ; glue sign(q) ← normal ; glue stretch(q) ← 0; glue shrink (q) ← 0; q ← p;

until q = null

This code is used in section 800.

802. ⟨ Nullify width(q) and the tabskip glue following this column 802 ⟩ ≡ begin width(q) ← 0; r ← link (q); s ← glue ptr (r); if s ≠ zero glue then

begin add glue ref (zero glue); delete glue ref (s); glue ptr (r) ← zero glue;

end; end

This code is used in section 801.

803. Merging of two span-node lists is a typical exercise in the manipulation of linearly linked data structures. The essential invariant in the following repeat loop is that we want to dispense with node r, in q’s list, and u is its successor; all nodes of p’s list up to and including s have been processed, and the successor of s matches r or precedes r or follows r, according as link (r) = n or link (r) > n or link (r) < n. ⟨ Merge the widths in the span nodes of q with those of p, destroying the span nodes of q 803 ⟩ ≡

begin t ← width(q) + width(glue ptr (link (q))); r ← info(q); s ← end span; info(s) ← p; n ← min quarterword + 1; repeat width(r) ← width(r) − t; u ← info(r);

while link (r) > n do begin s ← info(s); n ← link (info(s)) + 1; end;

if link (r) < n then begin info(r) ← info(s); info(s) ← r; decr (link (r)); s ← r; end

else begin if width(r) > width(info(s)) then width(info(s)) ← width(r); free node(r, span node size); end;

r ← u; until r = end span; end

This code is used in section 801.

804. Now the preamble list has been converted to a list of alternating unset boxes and tabskip glue, where the box widths are equal to the final column sizes. In case of , we change the widths to heights, so that a correct error message will be produced if the alignment is overfull or underfull. ⟨ Package the preamble list, to determine the actual tabskip glue amounts, and let p point to this prototype

box 804 ⟩ ≡ save ptr ← save ptr − 2; pack begin line ← −mode line; if mode = −vmode then

begin rule save ← overfull rule; overfull rule ← 0; { prevent rule from being packaged } p ← hpack (preamble, saved (1), saved (0)); overfull rule ← rule save; end

else begin q ← link (preamble); repeat height (q) ← width(q); width(q) ← 0; q ← link (link (q)); until q = null ; p ← vpack (preamble, saved (1), saved (0)); q ← link (preamble); repeat width(q) ← height (q); height (q) ← 0; q ← link (link (q)); until q = null ; end;

pack begin line ← 0

This code is used in section 800.

805. ⟨ Set the glue in all the unset boxes of the current list 805 ⟩ ≡ q ← link (head ); s ← head ; while q ≠ null do

begin if ¬is char node(q) then if type(q) = unset node then ⟨ Set the unset box q and the unset boxes in it 807 ⟩ else if type(q) = rule node then

⟨ Make the running dimensions in rule q extend to the boundaries of the alignment 806 ⟩; s ← q; q ← link (q); end

This code is used in section 800.

806. ⟨ Make the running dimensions in rule q extend to the boundaries of the alignment 806 ⟩ ≡ begin if is running (width(q)) then width(q) ← width(p); if is running (height (q)) then height (q) ← height (p); if is running (depth(q)) then depth(q) ← depth(p); if o ≠ 0 then

begin r ← link (q); link (q) ← null ; q ← hpack (q, natural ); shift amount (q) ← o; link (q) ← r; link (s) ← q; end;

end

This code is used in section 805.

807. The unset box q represents a row that contains one or more unset boxes, depending on how soon occurred in that row. ⟨ Set the unset box q and the unset boxes in it 807 ⟩ ≡

begin if mode = −vmode then begin type(q) ← hlist node; width(q) ← width(p); end

else begin type(q) ← vlist node; height (q) ← height (p);

end; glue order (q) ← glue order (p); glue sign(q) ← glue sign(p); glue set (q) ← glue set (p); shift amount (q) ← o; r ← link (list ptr (q)); s ← link (list ptr (p)); repeat ⟨ Set the glue in node r and change it from an unset node 808 ⟩;

r ← link (link (r)); s ← link (link (s)); until r = null ; end

This code is used in section 805.

808. A box made from spanned columns will be followed by tabskip glue nodes and by empty boxes as if there were no spanning. This permits perfect alignment of subsequent entries, and it prevents values that depend on floating point arithmetic from entering into the dimensions of any boxes. ⟨ Set the glue in node r and change it from an unset node 808 ⟩ ≡

n ← span count (r); t ← width(s); w ← t; u ← hold head ; while n > min quarterword do

begin decr (n); ⟨ Append tabskip glue and an empty box to list u, and update s and t as the prototype

nodes are passed 809 ⟩; end;

if mode = −vmode then

⟨ Make the unset node r into an hlist node of width w, setting the glue as if the width were t 810 ⟩ else ⟨ Make the unset node r into a vlist node of height w, setting the glue as if the height were t 811 ⟩; shift amount (r) ← 0; if u ≠ hold head then { append blank boxes to account for spanned nodes }

begin link (u) ← link (r); link (r) ← link (hold head ); r ← u;

end

This code is used in section 807.

809. ⟨ Append tabskip glue and an empty box to list u, and update s and t as the prototype nodes are

passed 809 ⟩ ≡ s ← link (s); v ← glue ptr (s); link (u) ← new glue(v); u ← link (u); subtype(u) ← tab skip code + 1; t ← t + width(v); if glue sign(p) = stretching then

begin if stretch order (v) = glue order (p) then t ← t + round (float (glue set (p)) ∗ stretch(v)); end

else if glue sign(p) = shrinking then begin if shrink order (v) = glue order (p) then t ← t − round (float (glue set (p)) ∗ shrink (v)); end;

s ← link (s); link (u) ← new null box ; u ← link (u); t ← t + width(s); if mode = −vmode then width(u) ← width(s) else begin type(u) ← vlist node; height (u) ← width(s);

end

This code is used in section 808.

810. ⟨ Make the unset node r into an hlist node of width w, setting the glue as if the width were t 810 ⟩ ≡ begin height (r) ← height (q); depth(r) ← depth(q); if t = width(r) then

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

else if t > width(r) then begin glue sign(r) ← stretching ; if glue stretch(r) = 0 then set glue ratio zero(glue set (r)) else glue set (r) ← unfloat ((t − width(r))/glue stretch(r)); end

else begin glue order (r) ← glue sign(r); glue sign(r) ← shrinking ; if glue shrink (r) = 0 then set glue ratio zero(glue set (r)) else if (glue order (r) = normal ) ∧ (width(r) − t > glue shrink (r)) then

set glue ratio one(glue set (r)) else glue set (r) ← unfloat ((width(r) − t)/glue shrink (r));

end; width(r) ← w; type(r) ← hlist node; end

This code is used in section 808.

811. ⟨ Make the unset node r into a vlist node of height w, setting the glue as if the height were t 811 ⟩ ≡ begin width(r) ← width(q); if t = height (r) then

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

else if t > height (r) then begin glue sign(r) ← stretching ; if glue stretch(r) = 0 then set glue ratio zero(glue set (r)) else glue set (r) ← unfloat ((t − height (r))/glue stretch(r)); end

else begin glue order (r) ← glue sign(r); glue sign(r) ← shrinking ; if glue shrink (r) = 0 then set glue ratio zero(glue set (r)) else if (glue order (r) = normal ) ∧ (height (r) − t > glue shrink (r)) then

set glue ratio one(glue set (r)) else glue set (r) ← unfloat ((height (r) − t)/glue shrink (r));

end; height (r) ← w; type(r) ← vlist node; end

This code is used in section 808.

812. We now have a completed alignment, in the list that starts at head and ends at tail . This list will be merged with the one that encloses it. (In case the enclosing mode is mmode, for displayed formulas, we will need to insert glue before and after the display; that part of the program will be deferred until we’re more familiar with such operations.)

In horizontal mode, the clang part of aux is undefined; an over-cautious Pascal runtime system may complain about this. ⟨ Insert the current list into its environment 812 ⟩ ≡

aux save ← aux ; p ← link (head ); q ← tail ; pop nest ; if mode = mmode then ⟨ Finish an alignment in a display 1206 ⟩ else begin aux ← aux save; link (tail ) ← p;

if p ≠ null then tail ← q;

if mode = vmode then build page;

end

This code is used in section 800.