Source Browser ?

1/*
2    See license.txt in the root of this project.
3*/
4
5# include "luametatex.h"
6
7/*tex
8
9    It's sort of a miracle whenever |halign and |valign| work, because they cut across so many of
10    the control structures of \TEX. Therefore the present page is probably not the best place for
11    a beginner to start reading this program; it is better to master everything else first.
12
13    Let us focus our thoughts on an example of what the input might be, in order to get some idea
14    about how the alignment miracle happens. The example doesn't do anything useful, but it is
15    sufficiently general to indicate all of the special cases that must be dealt with; please do
16    not be disturbed by its apparent complexity and meaninglessness.
17
18    \starttyping
19    \tabskip 2pt plus 3pt
20    \halign to 300pt{u1#v1&
21    \hskip 50pt \tabskip 1pt plus 1fil u2#v2&
22    \hskip 50pt u3#v3\cr
23    \hskip 25pt a1&\omit a2&\vrule\cr
24    \hskip 25pt \noalign\{\vskip 3pt}
25    \hskip 25pt b1\span b2\cr
26    \hskip 25pt \omit&c2\span\omit\cr}
27    \stoptyping
28
29    Here's what happens:
30
31    \startitemize
32
33        \startitem
34            When |\halign to 300pt {}| is scanned, the |scan_align_spec| routine places the 300pt
35            dimension onto the |save_stack|, and an |align_group| code is placed above it. This
36            will make it possible to complete the alignment when the matching right brace is found.
37        \stopitem
38
39        \startitem
40            The preamble is scanned next. Macros in the preamble are not expanded, except as part
41            of a tabskip specification. For example, if |u2| had been a macro in the preamble above,
42            it would have been expanded, since \TEX\ must look for |minus ...| as part of the
43            tabskip glue. A preamble list is constructed based on the user's preamble; in our case
44            it contains the following seven items:
45
46            \starttabulate
47            \NC \type{\glue 2pt plus 3pt}              \NC the tabskip preceding column 1      \NC \NR
48            \NC \type{\alignrecord} of width $-\infty$ \NC preamble info for column 1          \NC \NR
49            \NC \type{\glue 2pt plus 3pt}              \NC the tabskip between columns 1 and 2 \NC \NR
50            \NC \type{\alignrecord} of width $-\infty$ \NC preamble info for column 2          \NC \NR
51            \NC \type{\glue 1pt plus 1fil}             \NC the tabskip between columns 2 and 3 \NC \NR
52            \NC \type{\alignrecord} of width $-\infty$ \NC preamble info for column 3          \NC \NR
53            \NC \type{\glue 1pt plus 1fil}             \NC the tabskip following column 3      \NC \NR
54            \stoptabulate
55
56            These \quote {alignrecord} entries have the same size as an |unset_node|, since they
57            will later be converted into such nodes. These alignrecord nodes have no |depth| field;
58            this is split into |u_part| and |v_part|, and they point to token lists for the
59            templates of the alignment. For example, the |u_part| field in the first alignrecord
60            points to the token list |u1|, i.e., the template preceding the \type {#} for column~1.
61            Furthermore, They have a |span_ptr| instead of a |node_attr| field, and these |span_ptr|
62            fields are initially set to the value |end_span|, for reasons explained below.
63        \stopitem
64
65        \startitem
66            \TEX\ now looks at what follows the |\cr| that ended the preamble. It is not |\noalign|
67            or |\omit|, so this input is put back to be read again, and the template |u1| is fed to
68            the scanner. Just before reading |u1|, \TeX\ goes into restricted horizontal mode. Just
69            after reading |u1|, \TEX\ will see |a1|, and then (when the |&| is sensed) \TEX\ will
70            see |v1|. Then \TEX\ scans an |end_template| token, indicating the end of a column. At
71            this point an |unset_node| is created, containing the contents of the current hlist
72            (i.e., |u1a1v1|). The natural width of this unset node replaces the |width| field of
73            the alignrecord for column~1; in general, the alignrecords will record the maximum
74            natural width that has occurred so far in a given column.
75        \stopitem
76
77        \startitem
78            Since |\omit| follows the |&|, the templates for column~2 are now bypassed. Again \TEX\
79            goes into restricted horizontal mode and makes an |unset_node| from the resulting hlist;
80            but this time the hlist contains simply |a2|. The natural width of the new unset box is
81            remembered in the |width| field of the alignrecord for column~2.
82        \stopitem
83
84        \startitem
85            A third |unset_node| is created for column 3, using essentially the mechanism that
86            worked for column~1; this unset box contains |u3\vrule v3|. The vertical rule in this
87            case has running dimensions that will later extend to the height and depth of the whole
88            first row, since each |unset_node| in a row will eventually inherit the height and depth
89            of its enclosing box.
90        \stopitem
91
92        \startitem
93            The first row has now ended; it is made into a single unset box comprising the following
94            seven items:
95
96            \starttyping
97            \glue 2pt plus 3pt
98            \unsetbox for 1 column: u1a1v1
99            \glue 2pt plus 3pt
100            \unsetbox for 1 column: a2
101            \glue 1pt plus 1fil
102            \unsetbox for 1 column: u3\vrule v3
103            \glue 1pt plus 1fil
104            \stoptyping
105
106            The width of this unset row is unimportant, but it has the correct height and depth, so
107            the correct baselineskip glue will be computed as the row is inserted into a vertical
108            list.
109        \stopitem
110
111        \startitem
112            Since |\noalign| follows the current |\cr|, \TEX\ appends additional material (in this
113            case |\vskip 3pt|) to the vertical list. While processing this material, \TeX\ will be
114            in internal vertical mode, and |no_align_group| will be on |save_stack|.
115        \stopitem
116
117        \startitem
118            The next row produces an unset box that looks like this:
119
120            \starttyping
121            \glue 2pt plus 3pt
122            \unsetbox for 2 columns: u1b1v1u2b2v2
123            \glue 1pt plus 1fil
124            \unsetbox for 1 column: {(empty)}
125            \glue 1pt plus 1fil
126            \stoptyping
127
128            The natural width of the unset box that spans columns 1~and~2 is stored in a \quote
129            {span node}, which we will explain later; the |span_ptr| field of the alignrecord for
130            column~1 now points to the new span node, and the |span_ptr| of the span node points to
131            |end_span|.
132        \stopitem
133
134        \startitem
135
136            The final row produces the unset box
137
138            \starttyping
139            \glue 2pt plus 3pt
140            \unsetbox for 1 column: (empty)
141            \glue 2pt plus 3pt
142            \unsetbox for 2 columns: u2c2v2
143            \glue 1pt plus 1fil
144            \stoptyping
145
146            A new span node is attached to the align record for column 2.
147        \stopitem
148
149        \startitem
150            The last step is to compute the true column widths and to change all the unset boxes to
151            hboxes, appending the whole works to the vertical list that encloses the |\halign|. The
152            rules for deciding on the final widths of each unset column box will be explained below.
153        \stopitem
154
155    \stopitemize
156
157    Note that as |\halign| is being processed, we fearlessly give up control to the rest of \TEX. At
158    critical junctures, an alignment routine is called upon to step in and do some little action, but
159    most of the time these routines just lurk in the background. It's something like post-hypnotic
160    suggestion.
161
162    We have mentioned that alignrecords contain no |height| or |depth| fields. Their |glue_sign| and
163    |glue_order| are pre-empted as well, since it is necessary to store information about what to do
164    when a template ends. This information is called the |extra_info| field.
165
166    Alignments can occur within alignments, so a small stack is used to access the alignrecord
167    information. At each level we have a |preamble| pointer, indicating the beginning of the
168    preamble list; a |cur_align| pointer, indicating the current position in the preamble list; a
169    |cur_span| pointer, indicating the value of |cur_align| at the beginning of a sequence of
170    spanned columns; a |cur_loop| pointer, indicating the tabskip glue before an alignrecord that
171    should be copied next if the current list is extended; and the |align_state| variable, which
172    indicates the nesting of braces so that |\cr| and |\span| and tab marks are properly
173    intercepted. There also are pointers |cur_head| and |cur_tail| to the head and tail of a list
174    of adjustments being moved out from horizontal mode to vertical~mode, and alike |cur_pre_head|
175    and |cur_pre_tail| for pre-adjust lists.
176
177    The current values of these nine quantities appear in global variables; when they have to be
178    pushed down, they are stored in 6-word nodes, and |align_ptr| points to the topmost such node.
179
180*/
181
182/*tex
183
184    So far, hardly anything has been added to the alignment code so the above, original \TEX\
185    the program documentation still applies. Of course we have callbacks. Attributes are a bit
186    complicating here. I experimented with some row and cell specific ones but grouping will always
187    make it messy. One never knows what a preamble injects. So leaving it as-is is better than a
188    subtoptimal solution with side effects. To mention one aspect: we have unset nodes that use the
189    attribute fields for other purposes and get adapted later on anyway. I'll look into it again
190    at some point.
191
192    Contrary to other mechanisms, there are not that many extensions. One is that we can nest
193    |\noalign| (so we don't need kludges at the macro level). The look ahead trickery has not been
194    changed but we might get some variants (we have protected macros so it's not as sensitive as
195    it was in the past.
196
197    The |\tabsize| feature is experimental and possibly a prelude to more. I played with that
198    when a test file (korean font table) was allocating so many nodes that I wondered if we could
199    limit that (and redundant boxes and glue are the only things we can do here). It actually
200    also saves a bit of runtime. This feature has not been tested yet with |\span| and |\omit|.
201
202    The |\noalign| command accepts a couple of keywords that specify options to be applied to the 
203    next row. These options are similar to the ones for boxes. 
204
205    Maybe: lefttabskip righttabskip middletabskip
206
207*/
208
209typedef enum align_options {
210    align_option_exactly  = 0x01, 
211    align_option_reverse  = 0x10, 
212    align_option_discard  = 0x20, 
213    align_option_noskips  = 0x40, 
214    align_option_callback = 0x80, 
215} align_options;
216
217/* Do we still need these .. we have a dedicated stack. */
218
219typedef enum saved_align_entries {
220    saved_align_mode_entry     = 0,
221    saved_align_amount_entry   = 0,
222    saved_align_callback_entry = 0,
223    saved_align_n_of_records   = 1,
224} saved_align_entries;
225
226# define saved_align_mode     saved_value_1(saved_align_mode_entry)
227# define saved_align_amount   saved_value_2(saved_align_amount_entry)
228# define saved_align_callback saved_value_3(saved_align_amount_entry)
229
230inline static void saved_alignment_initialize(void)
231{
232    saved_type(0) = saved_record_0;
233    saved_record(0) = alignment_save_type;
234}
235
236int tex_show_alignment_record(void)
237{
238    tex_print_str("alignment ");
239    switch (saved_type(0)) { 
240       case saved_record_0:
241            tex_print_format("mode %i, amount %p", saved_value_1(0), saved_value_2(0));
242            break;
243        default: 
244            return 0;
245    }
246    return 1;
247}
248
249typedef struct alignment_row_state { 
250    halfword orientation;
251    scaled   xoffset;
252    scaled   yoffset;
253    scaled   xmove;
254    scaled   ymove;
255    halfword shift;
256    halfword source;
257    halfword target;
258    halfword anchor;
259    halfword attrlist; 
260} alignment_row_state;
261
262typedef struct alignment_state_info {
263    halfword cur_align;             /*tex The current position in the preamble list. */
264    halfword cur_span;              /*tex The start of the currently spanned columns in the preamble list. */
265    halfword cur_loop;              /*tex A place to copy when extending a periodic preamble. */
266    halfword align_ptr;             /*tex The most recently pushed-down alignment stack node. */
267    halfword cur_post_adjust_head;  /*tex Adjustment list head pointer. */
268    halfword cur_post_adjust_tail;  /*tex Adjustment list tail pointer. */
269    halfword cur_pre_adjust_head;   /*tex Pre-adjustment list head pointer. */
270    halfword cur_pre_adjust_tail;   /*tex Pre-adjustment list tail pointer. */
271    halfword cur_post_migrate_head;
272    halfword cur_post_migrate_tail;
273    halfword cur_pre_migrate_head;
274    halfword cur_pre_migrate_tail;
275    halfword hold_token_head;       /*tex head of a temporary list of another kind */
276    halfword omit_template;         /*tex a constant token list */
277    halfword no_align_level;
278    halfword attr_list;
279    halfword cell_source;           
280    halfword wrap_source;           /*tex There's also a field in the row_state. */
281    halfword row_state_set;
282    halfword options;
283    halfword callback;
284    alignment_row_state row_state; 
285} alignment_state_info ;
286
287static alignment_state_info lmt_alignment_state = {
288    .cur_align             = null,
289    .cur_span              = null,
290    .cur_loop              = null,
291    .align_ptr             = null,
292    .cur_post_adjust_head  = null,
293    .cur_post_adjust_tail  = null,
294    .cur_pre_adjust_head   = null,
295    .cur_pre_adjust_tail   = null,
296    .cur_post_migrate_head = null,
297    .cur_post_migrate_tail = null,
298    .cur_pre_migrate_head  = null,
299    .cur_pre_migrate_tail  = null,
300    .hold_token_head       = null,  /*tex head of a temporary list of another kind */
301    .omit_template         = null,  /*tex a constant token list */
302    .no_align_level        = 0,
303    .attr_list             = null,
304    .cell_source           = 0,
305    .wrap_source           = 0,
306    .row_state_set         = 0, 
307    .options               = 0,
308    .callback              = 0,
309    .row_state = { 
310        .attrlist    = null,
311        .orientation = 0,
312        .xoffset     = 0,
313        .yoffset     = 0,
314        .xmove       = 0,
315        .ymove       = 0,
316        .shift       = 0,
317        .source      = 0,
318        .target      = 0,
319        .anchor      = 0,
320    }
321};
322
323int tex_in_alignment(void)
324{
325    return lmt_alignment_state.cur_loop ? 1 : 0;
326}
327
328static void tex_aux_wipe_row_state(void)
329{
330    lmt_alignment_state.row_state.attrlist = null;
331    lmt_alignment_state.row_state.orientation = 0;
332    lmt_alignment_state.row_state.xoffset = 0;
333    lmt_alignment_state.row_state.yoffset = 0;
334    lmt_alignment_state.row_state.xmove = 0;
335    lmt_alignment_state.row_state.ymove = 0;
336    lmt_alignment_state.row_state.shift = 0;
337    lmt_alignment_state.row_state.source = 0;
338    lmt_alignment_state.row_state.target = 0;
339    lmt_alignment_state.row_state.anchor = 0;
340    lmt_alignment_state.row_state_set = 0;
341}
342
343/*tex The current preamble list: */
344
345# define preamble node_next(align_head)
346
347/*tex We use them before we define them: */
348
349static void tex_aux_initialize_row    (void);
350static void tex_aux_initialize_column (void);
351static void tex_aux_finish_row        (void);
352static int  tex_aux_finish_column     (void);
353static void tex_aux_finish_align      (void);
354
355/*tex
356    We get |alignment_record| into |unset_node| and |unset_node| into |[hv]list_node|. And because
357    we can access the fields later on w emake sure that we wipe them. The box orientation field kind
358    of protects reading them but still it's nicer this way. In general in \LUATEX\ and \LUAMETATEX\
359    we need to be more careful because we expose fields.
360*/
361
362inline static void tex_aux_change_list_type(halfword n, quarterword type)
363{
364    node_type(n) = type;
365    box_w_offset(n) = 0;    /* box_glue_stretch    align_record_span_ptr   */
366    box_h_offset(n) = 0;    /* box_glue_shrink     align_record_extra_info */
367    box_d_offset(n) = 0;    /* box_span_count                              */
368    box_x_offset(n) = 0;    /*                     align_record_u_part     */
369    box_y_offset(n) = 0;    /*                     align_record_v_part     */
370 /* box_geometry(n) = 0; */ /* box_size                                    */
371    box_orientation(n) = 0; /* box_size                                    */
372}
373
374/*tex
375
376    The |align_state| and |preamble| variables are initialized elsewhere. Alignment stack
377    maintenance is handled by a pair of trivial routines called |push_alignment| and |pop_alignment|.
378
379    It makes not much sense to add support for an |attr| keyword to |\halign| and |\valign| because
380    then we need to decide if we tag rows or cells or both or come up with |cellattr| and |rowattr|
381    and such. But then it even makes sense to have explicit commands (in addition to the seperator)
382    to tags individual cells. It's too much hassle for now and the advantages are not that large.
383
384    This code has a history so changing it now is tricky. For instance we could the top of the align 
385    stack instead of the copied values. On the other hand, working with copies makes that we can 
386    mess with these. And the gain would be little anywya, if at all. 
387
388*/
389
390static void tex_aux_push_alignment(void)
391{
392    /*tex The new alignment stack node: */
393    halfword p = tex_new_node(align_stack_node, 0);
394    /* todo: just a memory copy */
395    align_stack_align_ptr(p) = lmt_alignment_state.align_ptr;
396    align_stack_cur_align(p) = lmt_alignment_state.cur_align;
397    align_stack_preamble(p) = preamble;
398    align_stack_cur_span(p) = lmt_alignment_state.cur_span;
399    align_stack_cur_loop(p) = lmt_alignment_state.cur_loop;
400    align_stack_align_state(p) = lmt_input_state.align_state;
401    align_stack_wrap_source(p) = lmt_alignment_state.wrap_source;
402    align_stack_no_align_level(p) = lmt_alignment_state.no_align_level;
403    align_stack_cur_post_adjust_head(p) = lmt_alignment_state.cur_post_adjust_head;
404    align_stack_cur_post_adjust_tail(p) = lmt_alignment_state.cur_post_adjust_tail;
405    align_stack_cur_pre_adjust_head(p) = lmt_alignment_state.cur_pre_adjust_head;
406    align_stack_cur_pre_adjust_tail(p) = lmt_alignment_state.cur_pre_adjust_tail;
407    align_stack_cur_post_migrate_head(p) = lmt_alignment_state.cur_post_migrate_head;
408    align_stack_cur_post_migrate_tail(p) = lmt_alignment_state.cur_post_migrate_tail;
409    align_stack_cur_pre_migrate_head(p) = lmt_alignment_state.cur_pre_migrate_head;
410    align_stack_cur_pre_migrate_tail(p) = lmt_alignment_state.cur_pre_migrate_tail;
411    align_stack_options(p) = lmt_alignment_state.options;
412    align_stack_attr_list(p) = lmt_alignment_state.attr_list;
413    align_stack_callback(p) = lmt_alignment_state.callback;
414    /* */
415    align_stack_row_attrlist(p) = lmt_alignment_state.row_state.attrlist;
416    align_stack_row_orientation(p) = lmt_alignment_state.row_state.orientation;
417    align_stack_row_yoffset(p) = lmt_alignment_state.row_state.xoffset;
418    align_stack_row_xoffset(p) = lmt_alignment_state.row_state.yoffset;
419    align_stack_row_ymove(p) = lmt_alignment_state.row_state.xmove;
420    align_stack_row_xmove(p) = lmt_alignment_state.row_state.ymove;
421    align_stack_row_shift(p) = lmt_alignment_state.row_state.shift;
422    align_stack_row_source(p) = lmt_alignment_state.row_state.source;
423    align_stack_row_target(p) = lmt_alignment_state.row_state.target;
424    align_stack_row_anchor(p) = lmt_alignment_state.row_state.anchor;
425    /* */
426    lmt_alignment_state.align_ptr = p;
427    lmt_alignment_state.cur_post_adjust_head = tex_new_temp_node();
428    lmt_alignment_state.cur_pre_adjust_head = tex_new_temp_node();
429    lmt_alignment_state.cur_post_migrate_head = tex_new_temp_node();
430    lmt_alignment_state.cur_pre_migrate_head = tex_new_temp_node();
431    /* */
432    lmt_alignment_state.cell_source = 0;
433    lmt_alignment_state.wrap_source = 0;
434 // lmt_alignment_state.options = 0;
435    /* todo: put in align_stack, also wipe attr if needed */
436    tex_aux_wipe_row_state();
437}
438
439static void tex_aux_pop_alignment(void)
440{
441    /*tex The top alignment stack node: */
442    halfword p = lmt_alignment_state.align_ptr;
443    tex_flush_node(lmt_alignment_state.cur_post_adjust_head);
444    tex_flush_node(lmt_alignment_state.cur_pre_adjust_head);
445    tex_flush_node(lmt_alignment_state.cur_post_migrate_head);
446    tex_flush_node(lmt_alignment_state.cur_pre_migrate_head);
447    lmt_alignment_state.align_ptr = align_stack_align_ptr(p);
448    lmt_alignment_state.cur_align = align_stack_cur_align(p);
449    preamble = align_stack_preamble(p);
450    lmt_alignment_state.cur_span = align_stack_cur_span(p);
451    lmt_alignment_state.cur_loop = align_stack_cur_loop(p);
452    lmt_input_state.align_state = align_stack_align_state(p);
453    lmt_alignment_state.wrap_source = align_stack_wrap_source(p);
454    lmt_alignment_state.no_align_level  = align_stack_no_align_level(p);
455    lmt_alignment_state.cur_post_adjust_head = align_stack_cur_post_adjust_head(p);
456    lmt_alignment_state.cur_post_adjust_tail = align_stack_cur_post_adjust_tail(p);
457    lmt_alignment_state.cur_pre_adjust_head = align_stack_cur_pre_adjust_head(p);
458    lmt_alignment_state.cur_pre_adjust_tail = align_stack_cur_pre_adjust_tail(p);
459    lmt_alignment_state.cur_post_migrate_head = align_stack_cur_post_migrate_head(p);
460    lmt_alignment_state.cur_post_migrate_tail = align_stack_cur_post_migrate_tail(p);
461    lmt_alignment_state.cur_pre_migrate_head = align_stack_cur_pre_migrate_head(p);
462    lmt_alignment_state.cur_pre_migrate_tail = align_stack_cur_pre_migrate_tail(p);
463    lmt_alignment_state.options = align_stack_options(p);
464    lmt_alignment_state.attr_list = align_stack_attr_list(p);
465    lmt_alignment_state.callback = align_stack_callback(p);
466    /* */
467    lmt_alignment_state.row_state.attrlist = align_stack_row_attrlist(p);    
468    lmt_alignment_state.row_state.orientation = align_stack_row_orientation(p);
469    lmt_alignment_state.row_state.xoffset = align_stack_row_yoffset(p);  
470    lmt_alignment_state.row_state.yoffset = align_stack_row_xoffset(p);     
471    lmt_alignment_state.row_state.xmove = align_stack_row_ymove(p);  
472    lmt_alignment_state.row_state.ymove = align_stack_row_xmove(p);     
473    lmt_alignment_state.row_state.shift = align_stack_row_shift(p);       
474    lmt_alignment_state.row_state.source = align_stack_row_source(p);      
475    lmt_alignment_state.row_state.target = align_stack_row_target(p);      
476    lmt_alignment_state.row_state.anchor = align_stack_row_anchor(p);      
477    /* */
478    tex_flush_node(p);
479}
480
481/*tex
482
483    \TEX\ has eight procedures that govern alignments: |initialize_align| and |finish_align| are
484    used at the  very beginning and the very end; |initialize_row| and |finish_row| are used at
485    the beginning and end of individual rows; |initialize_span| is used at the beginning of a
486    sequence of spanned columns (possibly involving only one column); |initialize_column| and
487    |finish_column| are used at the beginning and end of individual columns; and |align_peek| is
488    used after |\cr| to see whether the next item is |\noalign|.
489
490    We shall consider these routines in the order they are first used during the course of a
491    complete |\halign|, namely |initialize_align|, |align_peek|, |initialize_row|,
492    |initialize_span|, |initialize_column|, |finish_column|, |finish_row|, |finish_align|.
493
494    The preamble is copied directly, except that |\tabskip| causes a change to the tabskip glue,
495    thereby possibly expanding macros that immediately follow it. An appearance of |\span| also
496    causes such an expansion.
497
498    Note that if the preamble contains |\global\tabskip|, the |\global| token survives in the
499    preamble and the |\tabskip| defines new tabskip glue (locally).
500
501    We enter |\span| into |eqtb| with |tab_mark| as its command code, and with |span_code| as the
502    command modifier. This makes \TEX\ interpret it essentially the same as an alignment delimiter
503    like |&|, yet it is recognizably different when we need to distinguish it from a normal
504    delimiter. It also turns out to be useful to give a special |cr_code| to |\cr|, and an even
505    larger |cr_cr_code| to |\crcr|.
506
507    The end of a template is represented by two frozen control sequences called |\endtemplate|. The
508    first has the command code |end_template|, which is |> outer_call|, so it will not easily
509    disappear in the presence of errors. The |get_x_token| routine converts the first into the
510    second, which has |endv| as its command code.
511
512    The |cr_code| is distinct from |span_code| and from any character and |\crcr| differs from
513    |\cr|.
514*/
515
516/*
517    In \LUAMETATEX\ the code has been adapted a bit. Because we have some access to alignment
518    related properties (commands, lists, etc.) The command codes have been reshuffled and
519    combined. Instead of dedicated cmd codes, we have a shared cmd with subtypes. The logic
520    hasn't changed, just the triggering of actions. In theory there can be a performance penalty
521    (due to extra checking) but in practice that will not be noticed becasue this seldom happens.
522    The advange is that we have a uniform token interface. It also makes it possible to extend
523    the code.
524
525*/
526
527static void tex_aux_get_preamble_token(void)
528{
529  RESTART:
530    tex_get_token();
531    while (cur_cmd == alignment_cmd && cur_chr == span_code) {
532        /*tex This token will be expanded once. */
533        tex_get_token();
534        if (cur_cmd > max_command_cmd) {
535            tex_expand_current_token();
536            tex_get_token();
537        }
538    }
539    switch (cur_cmd) {
540        case end_template_cmd:
541            tex_alignment_interwoven_error(5);
542            break;
543        case internal_glue_cmd:
544            if (cur_chr == internal_glue_location(tab_skip_code)) {
545                halfword v = tex_scan_glue(glue_val_level, 1, 0);
546                if (global_defs_par > 0) {
547                    update_tex_tab_skip_global(v);
548                } else {
549                    update_tex_tab_skip_local(v);
550                }
551                goto RESTART;
552            } else {
553                break;
554            }
555        case internal_dimension_cmd:
556            if (cur_chr == internal_dimension_location(tab_size_code)) {
557                scaled v = tex_scan_dimension(0, 0, 0, 1, NULL);
558                tex_word_define(global_defs_par > 0 ? global_flag_bit : 0, internal_dimension_location(tab_size_code), v);
559                goto RESTART;
560            } else {
561                break;
562            }
563        case call_cmd:
564        case protected_call_cmd:
565        case semi_protected_call_cmd:
566        case constant_call_cmd:
567        case tolerant_call_cmd:
568        case tolerant_protected_call_cmd:
569        case tolerant_semi_protected_call_cmd:
570            if (has_eq_flag_bits(cur_cs, noaligned_flag_bit)) {
571                tex_expand_current_token();
572                goto RESTART;
573            } else {
574                break;
575            }
576    }
577}
578
579/*tex
580
581    When |\halign| or |\valign| has been scanned in an appropriate mode, \TEX\ calls
582    |initialize_align|, whose task is to get everything off to a good start. This mostly involves
583    scanning the preamble and putting its information into the preamble list.
584
585*/
586
587static void tex_aux_scan_align_spec(quarterword c)
588{
589    quarterword mode = packing_additional;
590    quarterword options = 0;
591    scaled amount = 0;
592    halfword callback = 0;
593    halfword attrlist = null;
594    bool brace = false;
595    while (1) {
596        cur_val = 0; /* why */
597        switch (tex_scan_character("acdnrtsACDNRTS", 1, 1, 1)) {
598            case 0:
599                goto DONE;
600            case 'a': case 'A':
601                if (tex_scan_mandate_keyword("attr", 1)) {
602                    attrlist = tex_scan_attribute(attrlist);
603                }
604                break;
605            case 'c': case 'C':
606                if (tex_scan_mandate_keyword("callback", 1)) {
607                    options |= align_option_callback;
608                    callback = tex_scan_integer(0, NULL);
609                }
610                break;
611            case 'd': case 'D':
612                if (tex_scan_mandate_keyword("discard", 1)) {
613                    options |= align_option_discard;
614                }
615                break;
616            case 'n': case 'N':
617                if (tex_scan_mandate_keyword("noskips", 1)) {
618                    options |= align_option_noskips;
619                }
620                break;
621            case 'r': case 'R':
622                if (tex_scan_mandate_keyword("reverse", 1)) {
623                    options |= align_option_reverse;
624                }
625                break;
626            case 't': case 'T':
627                if (tex_scan_mandate_keyword("to", 1)) {
628                    mode = packing_exactly;
629                    options |= align_option_exactly;
630                    amount = tex_scan_dimension(0, 0, 0, 0, NULL);
631                }
632                break;
633            case 's': case 'S':
634                if (tex_scan_mandate_keyword("spread", 1)) {
635                    mode = packing_additional;
636                    options &= (~ align_option_exactly);
637                    amount = tex_scan_dimension(0, 0, 0, 0, NULL);
638                }
639                break;
640            case '{':
641                brace = true;
642                goto DONE;
643            default:
644                goto DONE;
645        }
646    }
647  DONE:
648    if (! attrlist) {
649        attrlist = tex_current_attribute_list();
650    } 
651    if (options & align_option_noskips) {
652        options &= (~ align_option_discard);
653    }
654    /*tex Now we're referenced. We need to preserve this over the group. */
655    add_attribute_reference(attrlist);
656    saved_alignment_initialize();
657    saved_align_mode = mode;
658    saved_align_amount = amount;
659    saved_align_callback = callback;
660    lmt_save_state.save_stack_data.ptr += saved_align_n_of_records;
661    tex_new_save_level(c);
662    if (! brace) {
663        tex_scan_left_brace();
664    }
665    lmt_alignment_state.attr_list = attrlist;
666    lmt_alignment_state.options = options;
667    lmt_alignment_state.callback = callback;
668}
669
670/*tex
671
672    The tricky part about alignments is getting the templates into the scanner at the right time,
673    and recovering control when a row or column is finished.
674
675    We usually begin a row after each |\cr| has been sensed, unless that |\cr| is followed by
676    |\noalign| or by the right brace that terminates the alignment. The |align_peek| routine is
677    used to look ahead and do the right thing; it either gets a new row started, or gets a
678    |\noalign} started, or finishes off the alignment.
679
680*/
681
682static void tex_aux_align_peek(void);
683
684static void tex_aux_trace_no_align(const char *s)
685{
686    if (tracing_alignments_par > 0) {
687        tex_begin_diagnostic();
688        tex_print_format("[alignment: %s noalign, level %i]", s, lmt_alignment_state.no_align_level);
689        tex_end_diagnostic();
690    }
691}
692
693static void tex_aux_run_no_align(void)
694{
695    /* */
696    int brace = 0;
697    int done = lmt_alignment_state.row_state_set;
698    while (1) {
699        int add = 0;
700      AGAIN:
701        switch (tex_scan_character("atrsoxyATRSOXY", 1, 1, 1)) {
702            case 0:
703                goto DONE;
704            case 't': case 'T':
705                if (tex_scan_mandate_keyword("target", 1)) {
706                    lmt_alignment_state.row_state.target = tex_scan_integer(1, NULL);
707                    done = 1;
708                }
709                break;
710            case 'a': case 'A':
711                switch (tex_scan_character("ntdNTD", 0, 0, 0)) {
712                    case 'd': case 'D':
713                        if (tex_scan_mandate_keyword("add", 2)) {
714                            add = 1;
715                            goto AGAIN;
716                        }
717                        break;
718                    case 't': case 'T':
719                        if (tex_scan_mandate_keyword("attr", 2)) {
720                            halfword i = tex_scan_attribute_register_number();
721                            halfword v = tex_scan_integer(1, NULL);
722                            if (eq_value(register_attribute_location(i)) != v) {
723                                if (lmt_alignment_state.row_state.attrlist) {
724                                    lmt_alignment_state.row_state.attrlist = tex_patch_attribute_list(lmt_alignment_state.row_state.attrlist, i, v);
725                                } else if (lmt_alignment_state.attr_list) {
726                                    lmt_alignment_state.row_state.attrlist = tex_copy_attribute_list_set(lmt_alignment_state.attr_list, i, v);
727                                } else {
728                                    lmt_alignment_state.row_state.attrlist = tex_copy_attribute_list_set(tex_current_attribute_list(), i, v);
729                                }
730                                done = 1;
731                            }
732                        }
733                        break;
734                    case 'n': case 'N':
735                        if (tex_scan_mandate_keyword("anchor", 2)) {
736                            switch (tex_scan_character("sS", 0, 0, 0)) {
737                                case 's': case 'S':
738                                    lmt_alignment_state.row_state.anchor = tex_scan_anchors(0);
739                                    break;
740                                default:
741                                    lmt_alignment_state.row_state.anchor = tex_scan_anchor(0);
742                                    break;
743                            }
744                            done = 1;
745                        }
746                        break;
747                    default:
748                        tex_aux_show_keyword_error("attr|anchor|add");
749                        goto DONE;
750                }
751                break;
752            case 'r': case 'R':
753                if (tex_scan_mandate_keyword("reset", 1)) {
754                    tex_aux_wipe_row_state();
755                    done = 0;
756                }
757                break;
758            case 's': case 'S':
759                switch (tex_scan_character("hoHO", 0, 0, 0)) {
760                    case 'h': case 'H':
761                        if (tex_scan_mandate_keyword("shift", 2)) {
762                            lmt_alignment_state.row_state.shift = (add ? lmt_alignment_state.row_state.shift : 0) 
763                                + tex_scan_dimension(0, 0, 0, 0, NULL);
764                            done = 1;
765                        }
766                        break;
767                    case 'o': case 'O':
768                        if (tex_scan_mandate_keyword("source", 2)) {
769                            lmt_alignment_state.row_state.source = tex_scan_integer(1, NULL);
770                            done = 1;
771                        }
772                        break;
773                    default:
774                        tex_aux_show_keyword_error("shift|source");
775                        goto DONE;
776                }
777                break;
778            case 'o': case 'O':
779                if (tex_scan_mandate_keyword("orientation", 1)) {
780                    lmt_alignment_state.row_state.orientation = tex_scan_orientation(0);
781                    done = 1;
782                }
783                break;
784            case 'x': case 'X':
785                switch (tex_scan_character("omOM", 0, 0, 0)) {
786                    case 'o': case 'O' :
787                        if (tex_scan_mandate_keyword("xoffset", 2)) {
788                            lmt_alignment_state.row_state.xoffset = (add ? lmt_alignment_state.row_state.xoffset : 0) 
789                                + tex_scan_dimension(0, 0, 0, 0, NULL);
790                            done = 1;
791                        }
792                        break;
793                    case 'm': case 'M' :
794                        if (tex_scan_mandate_keyword("xmove", 2)) {
795                            lmt_alignment_state.row_state.xmove = (add ? lmt_alignment_state.row_state.xmove : 0) 
796                                + tex_scan_dimension(0, 0, 0, 0, NULL);
797                            done = 1;
798                        }
799                        break;
800                    default:
801                        tex_aux_show_keyword_error("xoffset|xmove");
802                        goto DONE;
803                }
804                break;
805            case 'y': case 'Y':
806                switch (tex_scan_character("omOM", 0, 0, 0)) {
807                    case 'o': case 'O' :
808                        if (tex_scan_mandate_keyword("yoffset", 2)) {
809                            lmt_alignment_state.row_state.yoffset = (add ? lmt_alignment_state.row_state.yoffset : 0) 
810                                + tex_scan_dimension(0, 0, 0, 0, NULL);
811                            done = 1;
812                        }
813                        break;
814                    case 'm': case 'M' :
815                        if (tex_scan_mandate_keyword("ymove", 2)) {
816                            lmt_alignment_state.row_state.ymove = (add ? lmt_alignment_state.row_state.ymove : 0) 
817                                + tex_scan_dimension(0, 0, 0, 0, NULL);
818                            done = 1;
819                        }
820                        break;
821                    default:
822                        tex_aux_show_keyword_error("yoffset|ymove");
823                        goto DONE;
824                }
825                break;
826            case '{':
827                brace = 1;
828                goto DONE;
829            default:
830                goto DONE;
831        }
832        add = 0;
833    }
834  DONE:
835    lmt_alignment_state.row_state_set = done;
836    /* */
837    if (! brace) {
838        tex_scan_left_brace();
839    }
840    tex_new_save_level(no_align_group);
841    ++lmt_alignment_state.no_align_level;
842    tex_aux_trace_no_align("entering");
843    if (cur_list.mode == internal_vmode) {
844        tex_normal_paragraph(no_align_par_context);
845    }
846}
847
848static int tex_aux_nested_no_align(void)
849{
850    int state = lmt_alignment_state.no_align_level > 0;
851    if (state) {
852        tex_scan_left_brace();
853        tex_new_save_level(no_align_group);
854        ++lmt_alignment_state.no_align_level;
855        tex_aux_trace_no_align("entering");
856        if (cur_list.mode == internal_vmode) {
857            tex_normal_paragraph(no_align_par_context);
858        }
859    }
860    return state;
861}
862
863void tex_finish_no_alignment_group(void)
864{
865    if (! tex_wrapped_up_paragraph(no_align_par_context, 0)) { /* needs testing */
866        tex_end_paragraph(no_align_group, no_align_par_context);
867        tex_aux_trace_no_align("leaving");
868        --lmt_alignment_state.no_align_level;
869        tex_unsave();
870        if (lmt_alignment_state.no_align_level == 0) {
871            tex_aux_align_peek();
872        }
873    }
874}
875
876static void tex_aux_align_peek(void)
877{
878  RESTART:
879    lmt_input_state.align_state = busy_alignment_state;
880  AGAIN:
881    tex_get_x_or_protected();
882    switch (cur_cmd) {
883        case spacer_cmd:
884            goto AGAIN;
885        case right_brace_cmd:
886            tex_aux_finish_align();
887            break;
888        case call_cmd:
889        case protected_call_cmd:
890        case semi_protected_call_cmd:
891        case constant_call_cmd:
892        case tolerant_call_cmd:
893        case tolerant_protected_call_cmd:
894        case tolerant_semi_protected_call_cmd:
895            if (has_eq_flag_bits(cur_cs, noaligned_flag_bit)) {
896                tex_expand_current_token();
897                goto RESTART;
898            } else {
899                goto NEXTROW;
900            }
901        case alignment_cmd:
902            switch (cur_chr) {
903                case cr_cr_code:
904                    /*tex Ignore |\crcr|. */
905                    goto RESTART;
906                case no_align_code:
907                    tex_aux_run_no_align();
908                    return;
909            }
910            // fall through
911        default:
912          NEXTROW:
913            /*tex Start a new row. */
914            tex_aux_initialize_row();
915            /*tex Start a new column and replace what we peeked at. */
916            tex_aux_initialize_column();
917            break;
918    }
919}
920
921/*tex
922*
923    Magick numbers are used to indicate the level of alignment. However, keep in  mind that in
924    \LUANETATEX\ the fundamental parts of the rendering are separated. Contrary to traditional
925    \TEX\ we don't have the interwoven hyphenation, ligature building, kerning, etc.\ code.
926
927    In the end we have a list starting and ending with tabskips and align records seperated by
928    such skips.
929
930*/
931
932void tex_run_alignment_initialize(void)
933{
934    halfword saved_cs = cur_cs;
935    tex_aux_push_alignment();
936    lmt_input_state.align_state = initial_alignment_state;
937    /*tex
938        When |\halign| is used as a displayed formula, there should be no other pieces of mlists
939        present.
940    */
941    if (cur_list.mode == mmode && ((cur_list.tail != cur_list.head) || cur_list.incomplete_noad)) {
942        tex_handle_error(
943            normal_error_type,
944            "Improper \\halign inside math mode",
945            "Displays can use special alignments (like \\eqalignno) only if nothing but the\n"
946            "alignment itself is in math mode. So I've deleted the formulas that preceded this\n"
947            "alignment."
948        );
949        tex_flush_math();
950    }
951    /*tex We enter a new semantic level. */
952    tex_push_nest();
953    /*tex
954        In vertical modes, |prev_depth| already has the correct value. But if we are in |mmode|
955        (displayed formula mode), we reach out to the enclosing vertical mode for the |prev_depth|
956        value that produces the correct baseline calculations.
957    */
958    if (cur_list.mode == mmode) {
959        cur_list.mode = internal_vmode;
960        cur_list.prev_depth = lmt_nest_state.nest[lmt_nest_state.nest_data.ptr - 2].prev_depth;
961    } else if (cur_list.mode > 0) {
962        cur_list.mode = -cur_list.mode;
963    }
964    /*tex This one also saves some in the state. */
965    tex_aux_scan_align_spec(align_group);
966    /*tex
967        Scan the preamble. Even when we ignore zero tabskips, we do store them in the list because
968        the machinery later on steps over them and checking for present glue makes the code
969        horrible. The overhead is small because it's only the preamble where we waste glues then.
970    */
971    preamble = null;
972    lmt_alignment_state.cur_align = align_head;
973    lmt_alignment_state.cur_loop = null;
974    lmt_input_state.scanner_status = scanner_is_aligning;
975    lmt_input_state.warning_index = saved_cs;
976    lmt_input_state.align_state = initial_alignment_state;
977    /*tex At this point, |cur_cmd = left_brace|. */
978    while (1) {
979        /*tex Append the current tabskip glue to the preamble list. */
980        halfword glue = tex_new_param_glue_node(tab_skip_code, tab_skip_glue);
981        if ((lmt_alignment_state.options & align_option_noskips) && tex_glue_is_zero(glue)) {
982            node_subtype(glue) = ignored_glue;
983        }
984        tex_couple_nodes(lmt_alignment_state.cur_align, glue);
985        lmt_alignment_state.cur_align = glue;
986        if (cur_cmd == alignment_cmd && (cur_chr == cr_code || cur_chr == cr_cr_code)) { /* Also cr_cr here? */
987            /*tex A |\cr| ends the preamble. */
988            break;
989        } else {
990            /*tex
991                Scan preamble text until |cur_cmd| is |tab_mark| or |car_ret| and then scan the
992                template |u_j|, putting the resulting token list in |hold_token_head|. Spaces are
993                eliminated from the beginning of a template.
994            */
995            halfword record = null;
996            halfword current = lmt_alignment_state.hold_token_head;
997            token_link(current) = null;
998            while (1) {
999                tex_aux_get_preamble_token();
1000                if ((cur_cmd == alignment_cmd && cur_chr == align_content_code) || cur_cmd == parameter_cmd) {
1001                    break;
1002                } else if ((cur_cmd == alignment_cmd || cur_cmd == alignment_tab_cmd) && (lmt_input_state.align_state == initial_alignment_state)) {
1003                    if ((current == lmt_alignment_state.hold_token_head) && (! lmt_alignment_state.cur_loop) && (cur_cmd == alignment_tab_cmd)) {
1004                        lmt_alignment_state.cur_loop = lmt_alignment_state.cur_align;
1005                    } else {
1006                        tex_back_input(cur_tok);
1007                        tex_handle_error(
1008                            normal_error_type,
1009                            "Missing # inserted in alignment preamble",
1010                            "There should be exactly one # between &'s, when an \\halign or \\valign is being\n"
1011                            "set up. In this case you had none, so I've put one in; maybe that will work."
1012                        );
1013                        break;
1014                    }
1015                } else if (cur_cmd != spacer_cmd || current != lmt_alignment_state.hold_token_head) {
1016                    current = tex_store_new_token(current, cur_tok);
1017                }
1018            }
1019            /*tex A new align record: */
1020            record = tex_new_node(align_record_node, 0);
1021            tex_couple_nodes(lmt_alignment_state.cur_align, record);
1022            lmt_alignment_state.cur_align = record;
1023            align_record_span_ptr(record) = end_span;
1024            box_width(record) = null_flag;
1025            align_record_pre_part(record) = token_link(lmt_alignment_state.hold_token_head);
1026            /*tex Scan the template |v_j|, putting the resulting token list in |hold_token_head|. */
1027            current = lmt_alignment_state.hold_token_head;
1028            token_link(current) = null;
1029            while (1) {
1030                tex_aux_get_preamble_token();
1031                if ((cur_cmd == alignment_cmd || cur_cmd == alignment_tab_cmd) && (lmt_input_state.align_state == initial_alignment_state)) {
1032                    break;
1033                } else if ((cur_cmd == alignment_cmd && cur_chr == align_content_code) || cur_cmd == parameter_cmd) {
1034                    tex_handle_error(
1035                        normal_error_type,
1036                        "Only one # is allowed per tab",
1037                        "There should be exactly one # between &'s, when an \\halign or \\valign is being\n"
1038                        "set up. In this case you had more than one, so I'm ignoring all but the first."
1039                    );
1040                } else {
1041                    current = tex_store_new_token(current, cur_tok);
1042                }
1043            }
1044            if (tab_size_par > 0) {
1045                box_size(record) = tab_size_par;
1046                set_box_package_state(record, package_dimension_size_set);
1047            } else {
1048                box_width(record) = null_flag;
1049            }
1050            /*tex Put |\endtemplate| at the end: */
1051            current = tex_store_new_token(current, deep_frozen_end_template_token);
1052            align_record_post_part(lmt_alignment_state.cur_align) = token_link(lmt_alignment_state.hold_token_head);
1053        }
1054    }
1055    if (tracing_alignments_par > 1) {
1056        tex_print_levels();
1057        tex_print_str("<alignment preamble>");
1058        tex_show_node_list(preamble, max_integer, max_integer);
1059    }
1060    if (lmt_alignment_state.options & align_option_callback) {
1061        lmt_alignment_callback(cur_list.head, preamble_pass_alignment_context, lmt_alignment_state.callback, lmt_alignment_state.attr_list, preamble);
1062    }
1063    lmt_input_state.scanner_status = scanner_is_normal;
1064    tex_new_save_level(align_group);
1065    if (every_cr_par) {
1066        tex_begin_token_list(every_cr_par, every_cr_text);
1067    }
1068    /*tex Look for |\noalign| or |\omit|. */
1069    tex_aux_align_peek();
1070}
1071
1072void tex_finish_alignment_group(void)
1073{
1074    tex_back_input(cur_tok);
1075    cur_tok = deep_frozen_cr_token;
1076    tex_handle_error(
1077        insert_error_type,
1078        "Missing \\cr inserted",
1079        "I'm guessing that you meant to end an alignment here."
1080    );
1081}
1082
1083/*tex
1084
1085    The parameter to |initialize_span| is a pointer to the alignrecord where the next column or group
1086    of columns will begin. A new semantic level is entered, so that the columns will generate a list
1087    for subsequent packaging.
1088
1089*/
1090
1091static void tex_aux_initialize_span(halfword p)
1092{
1093    tex_push_nest();
1094    if (cur_list.mode == restricted_hmode) {
1095        cur_list.space_factor = default_space_factor;
1096    } else {
1097        cur_list.prev_depth = ignore_depth_criterion_par;
1098        tex_normal_paragraph(span_par_context);
1099    }
1100    lmt_alignment_state.cur_span = p;
1101}
1102
1103/*tex
1104
1105    To start a row (i.e., a \quote {row} that rhymes with \quote {dough} but not with \quote
1106    {bough}), we enter a new semantic level, copy the first tabskip glue, and change from internal
1107    vertical mode to restricted horizontal mode or vice versa. The |space_factor| and |prev_depth|
1108    are not used on this semantic level, but we clear them to zero just to be tidy.
1109
1110*/
1111
1112static void tex_aux_initialize_row(void)
1113{
1114    tex_push_nest();
1115    cur_list.mode = (- hmode - vmode) - cur_list.mode; /* weird code : - 3 - cur_list.mode : so a buogus line */
1116    if (cur_list.mode == restricted_hmode) {                     
1117        cur_list.space_factor = 0;
1118    } else {
1119        cur_list.prev_depth = 0;
1120    }
1121    lmt_alignment_state.cur_align = preamble;
1122    if (node_subtype(preamble) != ignored_glue) {
1123        halfword glue = tex_new_glue_node(preamble, tab_skip_glue);
1124        tex_tail_append(glue);
1125        tex_attach_attribute_list_attribute(glue, lmt_alignment_state.attr_list);
1126    }
1127    lmt_alignment_state.cur_align = node_next(preamble);
1128    lmt_alignment_state.cur_post_adjust_tail = lmt_alignment_state.cur_post_adjust_head;
1129    lmt_alignment_state.cur_pre_adjust_tail = lmt_alignment_state.cur_pre_adjust_head;
1130    lmt_alignment_state.cur_post_migrate_tail = lmt_alignment_state.cur_post_migrate_head;
1131    lmt_alignment_state.cur_pre_migrate_tail = lmt_alignment_state.cur_pre_migrate_head;
1132    tex_aux_initialize_span(lmt_alignment_state.cur_align);
1133    /* todo: wipe attr */
1134}
1135
1136/*tex
1137
1138    When a column begins, we assume that |cur_cmd| is either |omit| or else the current token should
1139    be put back into the input until the \<u_j> template has been scanned. Note that |cur_cmd| might
1140    be |tab_mark| or |car_ret|. We also assume that |align_state| is approximately 1000000 at this
1141    time. We remain in the same mode, and start the template if it is called for.
1142
1143*/
1144
1145static void tex_aux_initialize_column(void)
1146{
1147    align_record_cmd(lmt_alignment_state.cur_align) = cur_cmd;
1148    align_record_chr(lmt_alignment_state.cur_align) = cur_chr;
1149    if (cur_cmd == alignment_cmd && cur_chr == omit_code) {
1150        lmt_input_state.align_state = 0;
1151    } else {
1152        tex_back_input(cur_tok);
1153        if (every_tab_par) {
1154            tex_begin_token_list(every_tab_par, every_tab_text);
1155        }
1156        tex_begin_token_list(align_record_pre_part(lmt_alignment_state.cur_align), template_pre_text);
1157    }
1158    /*tex Now |align_state = 1000000|, one of these magic numbers. */
1159}
1160
1161/*tex
1162
1163    The scanner sets |align_state| to zero when the |u_j| template ends. When a subsequent |\cr|
1164    or |\span| or tab mark occurs with |align_state=0|, the scanner activates the following code,
1165    which fires up the |v_j| template. We need to remember the |cur_chr|, which is either
1166    |cr_cr_code|, |cr_code|, |span_code|, or a character code, depending on how the column text has
1167    ended.
1168
1169    This part of the program had better not be activated when the preamble to another alignment is
1170    being scanned, or when no alignment preamble is active.
1171
1172*/
1173
1174void tex_insert_alignment_template(void)
1175{
1176    if (lmt_input_state.scanner_status == scanner_is_aligning || ! lmt_alignment_state.cur_align) {
1177        tex_alignment_interwoven_error(6);
1178    } else {
1179        /*tex in case of an |\omit| the gets discarded and is nowhere else referenced. */
1180        halfword cmd = align_record_cmd(lmt_alignment_state.cur_align);
1181        halfword chr = align_record_chr(lmt_alignment_state.cur_align);
1182        halfword tok = (cmd == alignment_cmd && chr == omit_code) ? lmt_alignment_state.omit_template : align_record_post_part(lmt_alignment_state.cur_align);
1183        align_record_cmd(lmt_alignment_state.cur_align) = cur_cmd;
1184        align_record_chr(lmt_alignment_state.cur_align) = cur_chr;
1185        tex_begin_token_list(tok, template_post_text);
1186        lmt_input_state.align_state = busy_alignment_state;
1187        lmt_alignment_state.cell_source = alignment_cell_source_par;
1188        if (alignment_wrap_source_par) {
1189            lmt_alignment_state.wrap_source = alignment_wrap_source_par;
1190        }
1191    }
1192}
1193
1194/*tex Determine the stretch or shrink order */
1195
1196inline static halfword tex_aux_determine_order(scaled *total)
1197{
1198    if      (total[filll_glue_order]) return filll_glue_order;
1199    else if (total[fill_glue_order])  return fill_glue_order;
1200    else if (total[fil_glue_order])   return fil_glue_order;
1201    else if (total[fi_glue_order])    return fi_glue_order;
1202    else                              return normal_glue_order;
1203}
1204
1205/*tex
1206
1207    A span node is a 3-word record containing |width|, |span_span|, and |span_ptr| fields. The
1208    |span_span| field indicates the number of spanned columns; the |span_ptr| field points to a
1209    span node for the same starting column, having a greater extent of spanning, or to |end_span|,
1210    which has the largest possible |span_span| field; the |width| field holds the largest natural
1211    width corresponding to a particular set of spanned columns.
1212
1213    A list of the maximum widths so far, for spanned columns starting at a given column, begins
1214    with the |span_ptr| field of the alignrecord for that column. The code has to make sure that
1215    there is room for |span_ptr| in both the align record and the span nodes, which is why
1216    |span_ptr| replaces |node_attr|.
1217
1218*/
1219
1220static halfword tex_aux_new_span_node(halfword n, int s, scaled w)
1221{
1222    halfword p = tex_new_node(span_node, 0);
1223    span_ptr(p) = n; /*tex This one overlaps with |alignment_record_ptr|. */
1224    span_span(p) = s;
1225    span_width(p) = w;
1226    return p;
1227}
1228
1229/*tex
1230
1231    When the |end_template| command at the end of a |v_j| template comes through the scanner,
1232    things really start to happen; and it is the |finialize_column| routine that makes them happen.
1233    This routine returns |true| if a row as well as a column has been finished.
1234
1235*/
1236
1237void tex_alignment_interwoven_error(int n)
1238{
1239    tex_formatted_error("alignment", "interwoven preambles are not allowed, case %d", n);
1240}
1241
1242halfword tex_alignment_hold_token_head(void)
1243{
1244    return lmt_alignment_state.hold_token_head;
1245}
1246
1247static int tex_aux_finish_column(void)
1248{
1249    if (! lmt_alignment_state.cur_align) {
1250        tex_confusion("end template, case 1");
1251    } else {
1252        halfword q = node_next(lmt_alignment_state.cur_align);
1253        if (! q) {
1254            tex_confusion("end template, case 2");
1255        } else if (lmt_input_state.align_state < interwoven_alignment_threshold) {
1256            tex_alignment_interwoven_error(1);
1257        } else {
1258            /*tex A few state variables. */
1259            halfword cmd = align_record_cmd(lmt_alignment_state.cur_align);
1260            halfword chr = align_record_chr(lmt_alignment_state.cur_align);
1261            /*tex
1262                We check the alignrecord after the current one. If the preamble list has been
1263                traversed, check that the row has ended.
1264            */
1265            halfword record = node_next(q);
1266            if (alignment_wrap_source_par) {
1267                lmt_alignment_state.wrap_source = alignment_wrap_source_par;
1268            }
1269            if (! record && ! ((cmd == alignment_cmd) && (chr == cr_code || chr == cr_cr_code))) {
1270                if (lmt_alignment_state.cur_loop) {
1271                    /*tex Lengthen the preamble periodically. A new align record: */
1272                    record = tex_new_node(align_record_node, 0);
1273                    tex_couple_nodes(q, record);
1274                    align_record_span_ptr(record) = end_span;
1275                    box_width(record) = null_flag;
1276                    lmt_alignment_state.cur_loop = node_next(lmt_alignment_state.cur_loop);
1277                    /*tex Copy the templates from node |cur_loop| into node |p|. */
1278                    {
1279                        halfword q = lmt_alignment_state.hold_token_head;
1280                        halfword r = align_record_pre_part(lmt_alignment_state.cur_loop);
1281                        while (r) {
1282                            q = tex_store_new_token(q, token_info(r));
1283                            r = token_link(r);
1284                        }
1285                        token_link(q) = null;
1286                        align_record_pre_part(record) = token_link(lmt_alignment_state.hold_token_head);
1287                    }
1288                    {
1289                        halfword q = lmt_alignment_state.hold_token_head;
1290                        halfword r = align_record_post_part(lmt_alignment_state.cur_loop);
1291                        while (r) {
1292                            q = tex_store_new_token(q, token_info(r));
1293                            r = token_link(r);
1294                        }
1295                        token_link(q) = null;
1296                        align_record_post_part(record) = token_link(lmt_alignment_state.hold_token_head);
1297                    }
1298                    lmt_alignment_state.cur_loop = node_next(lmt_alignment_state.cur_loop);
1299                    {
1300                        halfword glue = tex_new_glue_node(lmt_alignment_state.cur_loop, tab_skip_glue);
1301                        if ((lmt_alignment_state.options & align_option_noskips) && tex_glue_is_zero(glue)) {
1302                            node_subtype(glue) = ignored_glue;
1303                        }
1304                        tex_couple_nodes(record, glue);
1305                    }
1306                } else {
1307                    chr = cr_code;
1308                    align_record_chr(lmt_alignment_state.cur_align) = chr;
1309                    tex_handle_error(
1310                        normal_error_type,
1311                        "Extra alignment tab has been changed to \\cr",
1312                        "You have given more \\span or & marks than there were in the preamble to the\n"
1313                        "\\halign or \\valign now in progress. So I'll assume that you meant to type \\cr\n"
1314                        "instead."
1315                    );
1316                }
1317            }
1318            if (! (cmd == alignment_cmd && chr == span_code)) {
1319                /*tex a new unset box */
1320                halfword cell = null;
1321                /*tex natural width */
1322                scaled width = 0;
1323                scaled size = 0;
1324                int state = 0;
1325                int packing = packing_additional;
1326                /*tex The span counter. */
1327                halfword spans = 0;
1328                tex_unsave();
1329                tex_new_save_level(align_group);
1330                /*tex Package an unset box for the current column and record its width. */
1331                state = has_box_package_state(lmt_alignment_state.cur_align, package_dimension_size_set);
1332                if (state) {
1333                    size = box_size(lmt_alignment_state.cur_align);
1334                    packing = packing_exactly;
1335                }
1336                if (cur_list.mode == restricted_hmode) {
1337                    lmt_packaging_state.post_adjust_tail = lmt_alignment_state.cur_post_adjust_tail;
1338                    lmt_packaging_state.pre_adjust_tail = lmt_alignment_state.cur_pre_adjust_tail;
1339                    lmt_packaging_state.post_migrate_tail = lmt_alignment_state.cur_post_migrate_tail;
1340                    lmt_packaging_state.pre_migrate_tail = lmt_alignment_state.cur_pre_migrate_tail;
1341                    cell = tex_filtered_hpack(cur_list.head, cur_list.tail, size, packing, align_set_group, direction_unknown, 0, null, 0, 0);
1342                    width = box_width(cell);
1343                    lmt_alignment_state.cur_post_adjust_tail = lmt_packaging_state.post_adjust_tail;
1344                    lmt_alignment_state.cur_pre_adjust_tail = lmt_packaging_state.pre_adjust_tail;
1345                    lmt_alignment_state.cur_post_migrate_tail = lmt_packaging_state.post_migrate_tail;
1346                    lmt_alignment_state.cur_pre_migrate_tail = lmt_packaging_state.pre_migrate_tail;
1347                    lmt_packaging_state.post_adjust_tail = null;
1348                    lmt_packaging_state.pre_adjust_tail = null;
1349                    lmt_packaging_state.post_migrate_tail = null;
1350                    lmt_packaging_state.pre_migrate_tail = null;
1351                } else {
1352                    cell = tex_filtered_vpack(node_next(cur_list.head), size, packing, 0, align_set_group, direction_unknown, 0, null, 0, 0, NULL);
1353                    width = box_height(cell);
1354                }
1355                if (lmt_alignment_state.cell_source) {
1356                    box_source_anchor(cell) = lmt_alignment_state.cell_source;
1357                    tex_set_box_geometry(cell, anchor_geometry);
1358                }
1359                tex_attach_attribute_list_attribute(cell, lmt_alignment_state.attr_list);
1360                if (lmt_alignment_state.cur_span != lmt_alignment_state.cur_align) {
1361                    /*tex Update width entry for spanned columns. */
1362                    halfword ptr = lmt_alignment_state.cur_span;
1363                    do {
1364                        ++spans;
1365                        ptr = node_next(node_next(ptr));
1366                    } while (ptr != lmt_alignment_state.cur_align);
1367                    if (spans > max_quarterword) {
1368                        /*tex This can happen, but won't. */
1369                        tex_confusion("too many spans");
1370                    }
1371                    ptr = lmt_alignment_state.cur_span;
1372                    while (span_span(align_record_span_ptr(ptr)) < spans) {
1373                        ptr = align_record_span_ptr(ptr);
1374                    }
1375                    if (span_span(align_record_span_ptr(ptr)) > spans) {
1376                        halfword span = tex_aux_new_span_node(align_record_span_ptr(ptr), spans, width);
1377                        align_record_span_ptr(ptr) = span;
1378                    } else if (span_width(align_record_span_ptr(ptr)) < width) {
1379                        span_width(align_record_span_ptr(ptr)) = width;
1380                    }
1381                } else if (width > box_width(lmt_alignment_state.cur_align)) {
1382                    box_width(lmt_alignment_state.cur_align) = width;
1383                }
1384                tex_aux_change_list_type(cell, unset_node);
1385                box_span_count(cell) = spans;
1386                if (! state) {
1387                    halfword order = tex_aux_determine_order(lmt_packaging_state.total_stretch);
1388                    box_glue_order(cell) = order;
1389                    box_glue_stretch(cell) = lmt_packaging_state.total_stretch[order];
1390                    order = tex_aux_determine_order(lmt_packaging_state.total_shrink);
1391                    box_glue_sign(cell) = order; /* hm, sign */
1392                    box_glue_shrink(cell) = lmt_packaging_state.total_shrink[order];
1393                }
1394                tex_pop_nest();
1395                tex_tail_append(cell);
1396                /*tex Copy the tabskip glue between columns. */
1397                if (node_subtype(node_next(lmt_alignment_state.cur_align)) != ignored_glue) {
1398                    halfword glue = tex_new_glue_node(node_next(lmt_alignment_state.cur_align), tab_skip_glue);
1399                    tex_attach_attribute_list_attribute(cell, lmt_alignment_state.attr_list);
1400                    tex_tail_append(glue);
1401                }
1402                if (cmd == alignment_cmd && (chr == cr_code || chr == cr_cr_code)) {
1403                    return 1;
1404                } else {
1405                    tex_aux_initialize_span(record);
1406                }
1407            }
1408            lmt_input_state.align_state = busy_alignment_state;
1409            do {
1410                tex_get_x_or_protected();
1411            } while (cur_cmd == spacer_cmd);
1412            lmt_alignment_state.cur_align = record;
1413            tex_aux_initialize_column();
1414        }
1415    }
1416    return 0;
1417}
1418
1419/*tex
1420
1421    At the end of a row, we append an unset box to the current vlist (for |\halign|) or the current
1422    hlist (for |\valign|). This unset box contains the unset boxes for the columns, separated by
1423    the tabskip glue. Everything will be set later.
1424
1425*/
1426
1427static void tex_aux_finish_row(void)
1428{
1429    halfword row;
1430    if (cur_list.mode == restricted_hmode) {
1431        row = tex_filtered_hpack(cur_list.head, cur_list.tail, 0, packing_additional, finish_row_group, direction_unknown, 0, null, 0, 0);
1432        tex_pop_nest();
1433        if (lmt_alignment_state.cur_pre_adjust_head != lmt_alignment_state.cur_pre_adjust_tail) {
1434            tex_inject_adjust_list(lmt_alignment_state.cur_pre_adjust_head, 0, null, NULL);
1435        }
1436        if (lmt_alignment_state.cur_pre_migrate_head != lmt_alignment_state.cur_pre_migrate_tail) {
1437            tex_append_list(lmt_alignment_state.cur_pre_migrate_head, lmt_alignment_state.cur_pre_migrate_tail);
1438        }
1439        tex_append_to_vlist(row, lua_key_index(alignment), NULL);
1440        if (lmt_alignment_state.cur_post_migrate_head != lmt_alignment_state.cur_post_migrate_tail) {
1441            tex_append_list(lmt_alignment_state.cur_post_migrate_head, lmt_alignment_state.cur_post_migrate_tail);
1442        }
1443        if (lmt_alignment_state.cur_post_adjust_head != lmt_alignment_state.cur_post_adjust_tail) {
1444            tex_inject_adjust_list(lmt_alignment_state.cur_post_adjust_head, 0, null, NULL);
1445        }
1446    } else {
1447        row = tex_filtered_vpack(node_next(cur_list.head), 0, packing_additional, max_depth_par, finish_row_group, direction_unknown, 0, null, 0, 0, NULL);
1448        tex_pop_nest();
1449        tex_tail_append(row);
1450        cur_list.space_factor = default_space_factor;
1451    }
1452    /*tex 
1453        Currently this one can be overloaded by the one set on the row via the noalign trickery
1454        which is probably okay. 
1455    */
1456    if (lmt_alignment_state.wrap_source) {
1457        box_source_anchor(row) = lmt_alignment_state.wrap_source;
1458        box_geometry(row) |= anchor_geometry;
1459    }
1460    /* 
1461        This also wipes (list) fields that we might set below, like |xoffset| that is used for 
1462        specific alignments purposes. 
1463    */
1464    tex_aux_change_list_type(row, unset_node);
1465    /* */
1466    tex_attach_attribute_list_attribute(row, lmt_alignment_state.row_state.attrlist ? 
1467        lmt_alignment_state.row_state.attrlist : lmt_alignment_state.attr_list);
1468    /*tex 
1469        The next blob of code duplicates some of packaging code but because we fetch from different
1470        fields we cannot share. Maybe, when I add this kind of features to other mechanisms (how 
1471        about cells!) then the next code will become some helper. 
1472    */
1473    if (lmt_alignment_state.row_state_set) { 
1474        halfword orientation = lmt_alignment_state.row_state.orientation;
1475        halfword anchor = lmt_alignment_state.row_state.anchor;
1476        scaled shift = lmt_alignment_state.row_state.shift;
1477        halfword source = lmt_alignment_state.row_state.source;
1478        halfword target = lmt_alignment_state.row_state.target;
1479        scaled xoffset = lmt_alignment_state.row_state.xoffset;
1480        scaled yoffset = lmt_alignment_state.row_state.yoffset;
1481        scaled xmove = lmt_alignment_state.row_state.xmove;
1482        scaled ymove = lmt_alignment_state.row_state.ymove;
1483        singleword geometry = box_geometry(row);
1484        /* */
1485        if (xoffset || yoffset || xmove || ymove) {
1486            geometry |= offset_geometry;
1487        }
1488        if (orientation) {
1489            geometry |= orientation_geometry;
1490        }
1491        /* */
1492        if (tex_has_geometry(geometry, offset_geometry) || tex_has_geometry(geometry, orientation_geometry)) {
1493            scaled wd = box_width(row);
1494            scaled ht = box_height(row);
1495            scaled dp = box_depth(row);
1496            if (xmove) {
1497                xoffset = tex_aux_checked_dimension1(xoffset + xmove);
1498                wd = tex_aux_checked_dimension2(wd + xmove);
1499                set_box_package_state(row, package_dimension_size_set); /* safeguard */
1500            }
1501            if (ymove) {
1502                yoffset = tex_aux_checked_dimension1(yoffset + ymove);
1503                ht = tex_aux_checked_dimension2(ht + ymove);
1504                dp = tex_aux_checked_dimension2(dp - ymove);
1505            }
1506            box_w_offset(row) = wd;
1507            box_h_offset(row) = ht;
1508            box_d_offset(row) = dp;
1509            switch (orientationonly(orientation)) {
1510                case 0 : /*   0 */
1511                    break;
1512                case 2 : /* 180 */
1513                    box_height(row) = dp;
1514                    box_depth(row) = ht;
1515                    geometry |= orientation_geometry;
1516                    break;
1517                case 1 : /*  90 */
1518                case 3 : /* 270 */
1519                    box_width(row) = ht + dp;
1520                    box_height(row) = wd;
1521                    box_depth(row) = 0;
1522                    geometry |= orientation_geometry;
1523                    break;
1524                case 4 : /*   0 */
1525                    box_height(row) = ht + dp;
1526                    box_depth(row) = 0;
1527                    geometry |= orientation_geometry;
1528                    break;
1529                case 5 : /* 180 */
1530                    box_height(row) = 0;
1531                    box_depth(row) = ht + dp;
1532                    geometry |= orientation_geometry;
1533                    break;
1534                default :
1535                    break;
1536            }
1537            if (xoffset || yoffset) {
1538                box_x_offset(row) = xoffset;
1539                box_y_offset(row) = yoffset;
1540                geometry |= offset_geometry;
1541            }
1542        }
1543        if (shift) { 
1544            box_shift_amount(row) = shift;
1545        }
1546        if (source || target) {
1547            box_source_anchor(row) = source;
1548            box_target_anchor(row) = target;
1549            geometry |= anchor_geometry;
1550        }
1551        box_anchor(row) = anchor;
1552        box_orientation(row) = orientation;
1553        box_geometry(row) = (singleword) geometry;
1554    }
1555    /*tex
1556        We no longer need the row state so best wipe it now! Then we're ready for the next row. 
1557    */
1558    tex_aux_wipe_row_state();
1559    /* */
1560    if (every_cr_par) {
1561        tex_begin_token_list(every_cr_par, every_cr_text);
1562    }
1563    tex_aux_align_peek();
1564    /*tex Note that |glue_shrink(p) = 0| since |glue_shrink == shift_amount|. */
1565}
1566
1567/*tex
1568
1569    Finally, we will reach the end of the alignment, and we can breathe a sigh of relief that
1570    memory hasn't overflowed. All the unset boxes will now be set so that the columns line up,
1571    taking due account of spanned columns.
1572
1573    Normalizing by stripping zero tabskips makes the lists a little smaller which then is easier
1574    on later processing. But is is an option. We could actually not inject zero skips at all but
1575    then the code starts deviating too much. In some cases it can save a lot of zero glue nodes
1576    but we allocate them initially anyway. We don't save runtime here. (Some day I'll play a bit
1577    more with this and then probably also implement some pending extensions.)
1578
1579*/
1580
1581static void tex_aux_strip_zero_tab_skips(halfword q)
1582{
1583    halfword h = box_list(q);
1584    halfword t = h;
1585    while (t) {
1586        halfword n = node_next(t);
1587        if (node_type(t) == glue_node && node_subtype(t) == tab_skip_glue && tex_glue_is_zero(t)) {
1588            tex_try_couple_nodes(node_prev(t),n);
1589            if (t == h) {
1590                /*tex We only come here once. */
1591                h = n;
1592                box_list(q) = h;
1593            }
1594            tex_flush_node(t);
1595        }
1596        t = n;
1597    }
1598}
1599
1600/*tex 
1601    We currently have a mix of states but maybe some day we will exposer the save stack and then it
1602    is handy to have the state values there. So for now I keep this (as reminder). 
1603*/
1604
1605static void tex_aux_finish_align(void)
1606{
1607    /*tex a shared register for the list operations (others are localized) */
1608    halfword preroll;
1609    /*tex shift offset for unset boxes */
1610    scaled offset = 0;
1611    /*tex something new */
1612    halfword reverse = lmt_alignment_state.options & align_option_reverse;
1613    halfword callback = lmt_alignment_state.options & align_option_callback;
1614    halfword discard = normalize_line_mode_permitted(normalize_line_mode_par, discard_zero_tab_skips_mode) || (lmt_alignment_state.options & align_option_discard);
1615    /*tex The |align_group| was for individual entries: */
1616    if (cur_group != align_group) {
1617        tex_confusion("align, case 1");
1618    }
1619    tex_unsave();
1620    /*tex The |align_group| was for the whole alignment: */
1621    if (cur_group != align_group) {
1622        tex_confusion("align, case 2");
1623    }
1624    tex_unsave();
1625    if (lmt_nest_state.nest[lmt_nest_state.nest_data.ptr - 1].mode == mmode) {
1626        offset = display_indent_par;
1627    }
1628    lmt_save_state.save_stack_data.ptr -= saved_align_n_of_records;
1629    lmt_packaging_state.pack_begin_line = -cur_list.mode_line;
1630    /*tex
1631        All content is available now so this is a perfect spot for some processing. However, we
1632        cannot mess with the unset boxes (as these can have special properties). The main reason
1633        for some postprocessing can be to align (vertically) at a specific location in a cell
1634        but then we also need to process twice (and adapt the width in the preamble record).
1635
1636        We flush the tokenlists so that in principle we can access the align record nodes as normal
1637        lists.
1638    */
1639    halfword amount = saved_align_amount;
1640    halfword mode = saved_align_mode;
1641 /* halfword callback = saved_align_callback; */ /* also in state record */
1642    {
1643        halfword q = node_next(preamble);
1644        do {
1645            tex_flush_token_list(align_record_pre_part(q));
1646            tex_flush_token_list(align_record_post_part(q));
1647            align_record_pre_part(q) = null;
1648            align_record_post_part(q) = null;
1649            q = node_next(node_next(q));
1650        } while (q);
1651    }
1652    if (callback) {
1653        lmt_alignment_callback(cur_list.head, preroll_pass_alignment_context, lmt_alignment_state.callback, lmt_alignment_state.attr_list, preamble);
1654    }
1655    /*tex
1656
1657        Go through the preamble list, determining the column widths and changing the alignrecords
1658        to dummy unset boxes.
1659
1660        It's time now to dismantle the preamble list and to compute the column widths. Let $w_{ij}$
1661        be the maximum of the natural widths of all entries that span columns $i$ through $j$,
1662        inclusive. The alignrecord for column~$i$ contains  $w_{ii}$ in its |width| field, and there
1663        is also a linked list of the nonzero $w_{ij}$ for increasing $j$, accessible via the |info|
1664        field; these span nodes contain the value $j-i+|min_quarterword|$ in their |link| fields.
1665        The values of $w_{ii}$ were initialized to |null_flag|, which we regard as $-\infty$.
1666
1667        The final column widths are defined by the formula $$ w_j = \max_{1\L i\L j} \biggl( w_{ij}
1668        - \sum_{i\L k < j}(t_k + w_k) \biggr), $$ where $t_k$ is the natural width of the tabskip
1669        glue between columns $k$ and~$k + 1$. However, if $w_{ij} = -\infty$ for all $i$ in the
1670        range $1 <= i <= j$ (i.e., if every entry that involved column~$j$ also involved column~$j
1671        + 1$), we let $w_j = 0$, and we zero out the tabskip glue after column~$j$.
1672
1673        \TEX\ computes these values by using the following scheme: First $w_1 = w_{11}$. Then
1674        replace $w_{2j}$ by $\max(w_{2j}, w_{1j} - t_1 - w_1)$, for all $j > 1$. Then $w_2 =
1675        w_{22}$. Then replace $w_{3j}$ by $\max(w_{3j}, w_{2j} - t_2 - w_2)$ for all $j > 2$; and
1676        so on. If any $w_j$ turns out to be $-\infty$, its value is changed to zero and so is the
1677        next tabskip.
1678
1679    */
1680    {
1681        halfword q = node_next(preamble);
1682        do {
1683            /* So |q| and |p| point to alignment nodes that become unset ones. */
1684            halfword p = node_next(node_next(q));
1685            if (box_width(q) == null_flag) {
1686                /*tex Nullify |width(q)| and the tabskip glue following this column. */
1687                box_width(q) = 0;
1688                tex_reset_glue_to_zero(node_next(q));
1689            }
1690            if (align_record_span_ptr(q) != end_span) {
1691                /*tex
1692
1693                    Merge the widths in the span nodes of |q| with those of |p|, destroying the
1694                    span nodes of |q|.
1695
1696                    Merging of two span-node lists is a typical exercise in the manipulation of
1697                    linearly linked data structures. The essential invariant in the following
1698                    |repeat| loop is that we want to dispense with node |r|, in |q|'s list, and
1699                    |u| is its successor; all nodes of |p|'s list up to and including |s| have
1700                    been processed, and the successor of |s| matches |r| or precedes |r| or follows
1701                    |r|, according as |link(r) = n| or |link(r) > n| or |link(r) < n|.
1702
1703                */
1704                halfword t = box_width(q) + glue_amount(node_next(q));
1705                halfword n = 1;
1706                halfword r = align_record_span_ptr(q);
1707                halfword s = end_span;
1708                align_record_span_ptr(s) = p;
1709                do {
1710                    halfword u = align_record_span_ptr(r);
1711                    span_width(r) -= t;
1712                    while (span_span(r) > n) {
1713                        s = align_record_span_ptr(s);
1714                        n = span_span(align_record_span_ptr(s)) + 1;
1715                    }
1716                    if (span_span(r) < n) {
1717                        align_record_span_ptr(r) = align_record_span_ptr(s);
1718                        align_record_span_ptr(s) = r;
1719                        --span_span(r);
1720                        s = r;
1721                    } else {
1722                        if (span_width(r) > span_width(align_record_span_ptr(s))) {
1723                            span_width(align_record_span_ptr(s)) = span_width(r);
1724                        }
1725                        tex_flush_node(r);
1726                    }
1727                    r = u;
1728                } while (r != end_span);
1729            }
1730            tex_aux_change_list_type(q, unset_node);
1731            box_glue_order(q) = normal_glue_order;
1732            box_glue_sign(q) = normal_glue_sign;
1733            box_height(q) = 0;
1734            box_depth(q) = 0;
1735            q = p;
1736        } while (q);
1737    }
1738    if (callback) {
1739        lmt_alignment_callback(cur_list.head, package_pass_alignment_context, lmt_alignment_state.callback, lmt_alignment_state.attr_list, preamble);
1740    }
1741    /*tex
1742
1743        Package the preamble list, to determine the actual tabskip glue amounts, and let |p| point
1744        to this prototype box.
1745
1746        Now the preamble list has been converted to a list of alternating unset boxes and tabskip
1747        glue, where the box widths are equal to the final column sizes. In case of |\valign|, we
1748        change the widths to heights, so that a correct error message will be produced if the
1749        alignment is overfull or underfull.
1750
1751    */
1752    if (cur_list.mode == internal_vmode) {
1753        halfword rule_save = overfull_rule_par;
1754        /*tex Prevent the rule from being packaged. */
1755        overfull_rule_par = 0; 
1756        preroll = tex_hpack(preamble, amount, mode, direction_unknown, holding_none_option, box_limit_none);
1757        overfull_rule_par = rule_save;
1758    } else {
1759        halfword unset = node_next(preamble);
1760        do {
1761            box_height(unset) = box_width(unset);
1762            box_width(unset) = 0;
1763            unset = node_next(node_next(unset));
1764        } while (unset);
1765        /* why filtered here ... */
1766        preroll = tex_filtered_vpack(preamble, amount, mode, max_depth_par, preamble_group, direction_unknown, 0, 0, 0, holding_none_option, NULL);
1767        /* ... so we'll do this soon instead: */
1768     /* preroll = tex_vpack(preamble, saved_value(saved_align_specification), saved_extra(saved_align_specification), max_depth_par, direction_unknown, migrate_all_option); */
1769        unset = node_next(preamble);
1770        do {
1771            box_width(unset) = box_height(unset);
1772            box_height(unset) = 0;
1773            unset = node_next(node_next(unset));
1774        } while (unset);
1775    }
1776    lmt_packaging_state.pack_begin_line = 0;
1777    /*tex
1778        Here we set the glue in all the unset boxes of the current list based on the prerolled
1779        preamble.
1780    */
1781    {
1782        halfword rowptr = node_next(cur_list.head);
1783        while (rowptr) {
1784            switch (node_type(rowptr)) {
1785                 case unset_node:
1786                    {
1787                        /*tex
1788                            We set the unset box |q| and the unset boxes in it. The unset box |q|
1789                            represents a row that contains one or more unset boxes, depending on
1790                            how soon |\cr| occurred in that row.
1791
1792                            We also reset some fields but this needs checking because we never set
1793                            set them in these unset boxes but in the preamble ones.
1794                        */
1795                        halfword preptr;
1796                        halfword colptr;
1797                        if (cur_list.mode == internal_vmode) {
1798                         /* tex_aux_change_list_type(rowptr, hlist_node); */ /* too much, needs checking */
1799                            node_type(rowptr) = hlist_node;
1800                            box_width(rowptr) = box_width(preroll);
1801                        } else {
1802                         /* tex_aux_change_list_type(rowptr, vlist_node); */ /* too much, needs checking */
1803                            node_type(rowptr) = vlist_node;
1804                            box_height(rowptr) = box_height(preroll);
1805                        }
1806                        node_subtype(rowptr) = align_row_list;
1807                        box_glue_order(rowptr) = box_glue_order(preroll);
1808                        box_glue_sign(rowptr) = box_glue_sign(preroll);
1809                        box_glue_set(rowptr) = box_glue_set(preroll);
1810                        box_shift_amount(rowptr) = offset;
1811                        colptr = box_list(rowptr);
1812                        preptr = box_list(preroll);
1813                        if (node_type(colptr) == glue_node) {
1814                            colptr = node_next(colptr);
1815                        }
1816                        if (node_type(preptr) == glue_node) {
1817                            preptr = node_next(preptr);
1818                        }
1819                        if (node_type(colptr) != unset_node) {
1820                            tex_formatted_error("alignment", "bad box");
1821                        }
1822                        do {
1823                            /*tex
1824                                We set the glue in node |r| and change it from an unset node. A box
1825                                made from spanned columns will be followed by tabskip glue nodes
1826                                and by empty boxes as if there were no spanning. This permits
1827                                perfect alignment of subsequent entries, and it prevents values
1828                                that depend on floating point arithmetic from entering into the
1829                                dimensions of any boxes.
1830                            */
1831                            halfword spans = box_span_count(colptr);
1832                            scaled total = box_width(preptr);
1833                            scaled width = total; /*tex The width of a column. */
1834                            halfword tail = hold_head;
1835                            int state = has_box_package_state(preptr, package_dimension_size_set);
1836                            /*tex
1837                                When we have a span we need to add dummies. We append tabskip glue
1838                                and an empty box to list |u|, and update |s| and |t| as the
1839                                prototype nodes are passed. We could shortcut some code when we
1840                                have zero skips but we seldom end up in this branch anyway.
1841                            */
1842                            while (spans > 0) {
1843                                --spans;
1844                                preptr = node_next(preptr);
1845                                if (node_subtype(preptr) != ignored_glue) {
1846                                 /* halfword glue = tex_new_glue_node(preptr, tab_skip_glue); */
1847                                    halfword glue = tex_new_glue_node(preptr, node_subtype(preptr));
1848                                    tex_try_couple_nodes(tail, glue);
1849                                    tex_attach_attribute_list_attribute(glue, lmt_alignment_state.attr_list);
1850                                    total += glue_amount(preptr);
1851                                    /*tex The |glueratio| case is redundant, anyway ... */
1852                                    switch (box_glue_sign(preroll)) {
1853                                        case stretching_glue_sign:
1854                                            if (glue_stretch_order(preptr) == box_glue_order(preroll)) {
1855                                                total += glueround((glueratio) (box_glue_set(preroll)) * (glueratio) (glue_stretch(preptr)));
1856                                            }
1857                                            break;
1858                                        case shrinking_glue_sign:
1859                                            if (glue_shrink_order(preptr) == box_glue_order(preroll)) {
1860                                                total -= glueround((glueratio) (box_glue_set(preroll)) * (glueratio) (glue_shrink(preptr)));
1861                                            }
1862                                            break;
1863                                    }
1864                                    tail = glue;
1865                                    /*tex Move on to the box. */
1866                                }
1867                                preptr = node_next(preptr);
1868                                {
1869                                    halfword box = tex_new_null_box_node(cur_list.mode == internal_vmode ? hlist_node : vlist_node, align_cell_list);
1870                                    tex_couple_nodes(tail, box);
1871                                    tex_attach_attribute_list_attribute(box, lmt_alignment_state.attr_list);
1872                                    total += box_width(preptr);
1873                                    if (cur_list.mode == internal_vmode) {
1874                                        box_width(box) = box_width(preptr);
1875                                    } else {
1876                                        box_height(box) = box_width(preptr);
1877                                    }
1878                                    tail = box;
1879                                }
1880                            }
1881                            if (cur_list.mode == internal_vmode) {
1882                                /*tex
1883                                    Make the unset node |r| into an |hlist_node| of width |w|,
1884                                    setting the glue as if the width were |t|.
1885                                */
1886                                box_height(colptr) = box_height(rowptr);
1887                                box_depth(colptr) = box_depth(rowptr);
1888                                if (! state) {
1889                                    if (total == box_width(colptr)) {
1890                                        box_glue_sign(colptr) = normal_glue_sign;
1891                                        box_glue_order(colptr) = normal_glue_order;
1892                                        box_glue_set(colptr) = 0.0;
1893                                    } else if (total > box_width(colptr)) {
1894                                        box_glue_sign(colptr) = stretching_glue_sign;
1895                                        if (box_glue_stretch(colptr) == 0) {
1896                                            box_glue_set(colptr) = 0.0;
1897                                        } else {
1898                                            box_glue_set(colptr) = (glueratio) ( ( (glueratio) total - (glueratio) box_width(colptr) ) / ( (glueratio) box_glue_stretch(colptr) ) );
1899                                        }
1900                                    } else {
1901                                        box_glue_order(colptr) = box_glue_sign(colptr);
1902                                        box_glue_sign(colptr) = shrinking_glue_sign;
1903                                        if (box_glue_shrink(colptr) == 0) {
1904                                            box_glue_set(colptr) = 0.0;
1905                                        } else if ((box_glue_order(colptr) == normal_glue_order) && (box_width(colptr) - total > box_glue_shrink(colptr))) {
1906                                            box_glue_set(colptr) = 1.0;
1907                                        } else {
1908                                            box_glue_set(colptr) = (glueratio) ( ( (glueratio) box_width(colptr) - (glueratio) total ) / ( (glueratio) box_glue_shrink(colptr) ) );
1909                                        }
1910                                    }
1911                                }
1912                                box_width(colptr) = width;
1913                                tex_aux_change_list_type(colptr, hlist_node);
1914                                node_subtype(colptr) = align_cell_list;
1915                            } else {
1916                                /*tex
1917                                    Make the unset node |r| into a |vlist_node| of height |w|,
1918                                    setting the glue as if the height were |t|.
1919                                */
1920                                box_width(colptr) = box_width(rowptr);
1921                                if (! state) {
1922                                    if (total == box_height(colptr)) {
1923                                        box_glue_sign(colptr) = normal_glue_sign;
1924                                        box_glue_order(colptr) = normal_glue_order;
1925                                        box_glue_set(colptr) = 0.0;
1926                                    } else if (total > box_height(colptr)) {
1927                                        box_glue_sign(colptr) = stretching_glue_sign;
1928                                        if (box_glue_stretch(colptr) == 0) {
1929                                            box_glue_set(colptr) = 0.0;
1930                                        } else {
1931                                            box_glue_set(colptr) = (glueratio) ( ( (glueratio) total - (glueratio) box_height(colptr) ) / ( (glueratio) box_glue_stretch(colptr) ) );
1932                                        }
1933                                    } else {
1934                                        box_glue_order(colptr) = box_glue_sign(colptr);
1935                                        box_glue_sign(colptr) = shrinking_glue_sign;
1936                                        if (box_glue_shrink(colptr) == 0) {
1937                                            box_glue_set(colptr) = 0.0;
1938                                        } else if ((box_glue_order(colptr) == normal_glue_order) && (box_height(colptr) - total > box_glue_shrink(colptr))) {
1939                                            box_glue_set(colptr) = 1.0;
1940                                        } else {
1941                                            box_glue_set(colptr) = (glueratio) ( ( (glueratio) box_height(colptr) - (glueratio) total) / ( (glueratio) box_glue_shrink(colptr) ) );
1942                                        }
1943                                    }
1944                                }
1945                                box_height(colptr) = width;
1946                                tex_aux_change_list_type(colptr, vlist_node);
1947                                node_subtype(colptr) = align_cell_list;
1948                            }
1949                            box_shift_amount(colptr) = 0;
1950                            if (tail != hold_head) {
1951                                /*tex Append blank boxes to account for spanned nodes. */
1952                                tex_try_couple_nodes(tail, node_next(colptr));
1953                                tex_try_couple_nodes(colptr, node_next(hold_head));
1954                                colptr = tail;
1955                            }
1956                            colptr = node_next(colptr);
1957                            preptr = node_next(preptr);
1958                            if (node_type(colptr) == glue_node) {
1959                                colptr = node_next(colptr);
1960                            }
1961                            if (node_type(preptr) == glue_node) {
1962                                preptr = node_next(preptr);
1963                            }
1964                        } while (colptr);
1965                        if (discard) {
1966                            tex_aux_strip_zero_tab_skips(rowptr);
1967                        }
1968                        if (reverse) {
1969                            box_list(rowptr) = tex_reversed_node_list(box_list(rowptr));
1970                        }
1971                        if (has_box_package_state(rowptr, package_dimension_size_set)) {
1972                            if (box_w_offset(rowptr) > box_width(rowptr)) {
1973                                box_width(rowptr) = box_w_offset(rowptr); 
1974                            }
1975                        }
1976                    }
1977                    break;
1978                case rule_node:
1979                    {
1980                        /*tex
1981                            Make the running dimensions in rule |q| extend to the boundaries of the
1982                            alignment.
1983                        */
1984                        if (rule_width(rowptr) == null_flag) {
1985                            rule_width(rowptr) = box_width(preroll);
1986                        }
1987                        if (rule_height(rowptr) == null_flag) {
1988                            rule_height(rowptr) = box_height(preroll);
1989                        }
1990                        if (rule_depth(rowptr) == null_flag) {
1991                            rule_depth(rowptr) = box_depth(preroll);
1992                        }
1993                        /*tex We could use offset fields in rule instead. */
1994                        if (offset) {
1995                            halfword prv = node_prev(rowptr);
1996                            halfword nxt = node_next(rowptr);
1997                            halfword box = null;
1998                            node_prev(rowptr) = null;
1999                            node_next(rowptr) = null;
2000                            box = tex_hpack(rowptr, 0, packing_additional, direction_unknown, holding_none_option, box_limit_none);
2001                            tex_attach_attribute_list_attribute(box, rowptr);
2002                            box_shift_amount(box) = offset;
2003                            node_subtype(box) = align_cell_list; /*tex This is not really a cell. */
2004                         // node_subtype(box) = unknown_list;    /*tex So maybe we will do this. */
2005                            tex_try_couple_nodes(prv, box);
2006                            tex_try_couple_nodes(box, nxt);
2007                            rowptr = box;
2008                        }
2009                    }
2010                    break;
2011                default:
2012                    /*tex
2013                        When we're in a |\halign| we get the rows (the |unset_node|s) while the
2014                        rules are horizontal ones. Furthermore we can get (vertical) glues and
2015                        whatever else got kicked in between the rows, but all that is (currently)
2016                        not processed.
2017                    */
2018                    break;
2019            }
2020            rowptr = node_next(rowptr);
2021        }
2022    }
2023    if (callback) {
2024        lmt_alignment_callback(cur_list.head, wrapup_pass_alignment_context, lmt_alignment_state.callback, lmt_alignment_state.attr_list, preamble);
2025    }
2026    tex_flush_node_list(preroll);
2027    delete_attribute_reference(lmt_alignment_state.attr_list);
2028    tex_aux_pop_alignment();
2029    /*tex
2030        We now have a completed alignment, in the list that starts at |cur_list.head| and ends at
2031        |cur_list.tail|. This list will be merged with the one that encloses it. (In case the
2032        enclosing mode is |mmode|, for displayed formulas, we will need to insert glue before and
2033        after the display; that part of the program will be deferred until we're more familiar with
2034        such operations.)
2035    */
2036    {
2037        scaled prevdepth = cur_list.prev_depth;
2038        halfword head = node_next(cur_list.head);
2039        halfword tail = cur_list.tail;
2040        tex_pop_nest();
2041        if (cur_list.mode == mmode) {
2042            tex_finish_display_alignment(head, tail, prevdepth);
2043        } else {
2044            cur_list.prev_depth = prevdepth;
2045            if (head) {
2046                tex_tail_append(head);
2047                cur_list.tail = tail;
2048            }
2049            if (cur_list.mode == vmode) {
2050                tex_build_page(alignment_page_context, 0);
2051            }
2052        }
2053    }
2054}
2055
2056/*tex
2057
2058    The token list |omit_template| just referred to is a constant token list that contains the
2059    special control sequence |\endtemplate| only.
2060
2061*/
2062
2063void tex_initialize_alignments(void)
2064{
2065    lmt_alignment_state.hold_token_head = tex_get_available_token(null);
2066    lmt_alignment_state.omit_template = tex_get_available_token(deep_frozen_end_template_token);
2067    span_span(end_span) = max_quarterword + 1;
2068    align_record_span_ptr(end_span) = null;
2069}
2070
2071/*tex
2072*
2073    We no longer store |hold_token_head| and |omit_template| in the format file. It is a bit
2074    cleaner to just initialize them. So we free them.
2075
2076*/
2077
2078void tex_cleanup_alignments(void)
2079{
2080    tex_put_available_token(lmt_alignment_state.hold_token_head);
2081    tex_put_available_token(lmt_alignment_state.omit_template);
2082    lmt_alignment_state.hold_token_head = null;
2083    lmt_alignment_state.omit_template = null;
2084    delete_attribute_reference(lmt_alignment_state.attr_list);
2085    lmt_alignment_state.attr_list = null;
2086}
2087
2088/*tex
2089
2090    We've now covered most of the abuses of |\halign| and |\valign|. Let's take a look at what
2091    happens when they are used correctly.
2092
2093    An |align_group| code is supposed to remain on the |save_stack| during an entire alignment,
2094    until |finish_align| removes it.
2095
2096    A devious user might force an |end_template| command to occur just about anywhere; we must
2097    defeat such hacks.
2098
2099*/
2100
2101void tex_run_alignment_end_template(void)
2102{
2103    lmt_input_state.base_ptr = lmt_input_state.input_stack_data.ptr;
2104    lmt_input_state.input_stack[lmt_input_state.base_ptr] = lmt_input_state.cur_input;
2105    while ((  lmt_input_state.input_stack[lmt_input_state.base_ptr].index != template_post_text )
2106        && (! lmt_input_state.input_stack[lmt_input_state.base_ptr].loc)
2107        && (  lmt_input_state.input_stack[lmt_input_state.base_ptr].state == token_list_state)) {
2108        --lmt_input_state.base_ptr;
2109    }
2110    if (lmt_input_state.input_stack[lmt_input_state.base_ptr].index != template_post_text) {
2111        tex_alignment_interwoven_error(2);
2112    } else if (lmt_input_state.input_stack[lmt_input_state.base_ptr].loc)  {
2113        tex_alignment_interwoven_error(3);
2114    } else if (lmt_input_state.input_stack[lmt_input_state.base_ptr].state != token_list_state) {
2115        tex_alignment_interwoven_error(4);
2116    } else if (cur_group == align_group) {
2117        if (! tex_wrapped_up_paragraph(align_par_context, 0)) { /* needs testing */
2118            tex_end_paragraph(align_group, align_par_context);
2119            if (tex_aux_finish_column()) {
2120                tex_aux_finish_row();
2121            }
2122        }
2123    } else {
2124        tex_off_save();
2125    }
2126}
2127
2128/*tex
2129
2130    When |\cr| or |\span| or a tab mark comes through the scanner into |main_control|, it might be
2131    that the user has foolishly inserted one of them into something that has nothing to do with
2132    alignment. But it is far more likely that a left brace or right brace has been omitted, since
2133    |get_next| takes actions appropriate to alignment only when |\cr| or |\span| or tab marks occur
2134    with |align_state = 0|. The following program attempts to make an appropriate recovery.
2135
2136    As an experiment we support nested |\noalign| usage but we do keep the braces so there is still
2137    grouping. We don't flag these groups as |no_align_group| because then we need to do more work
2138    and it's not worth the trouble. One can actually argue for not doing that anyway.
2139
2140    I might now rename the next one to |run_alignment| (and then also a companion as we have two
2141    cases of usage).
2142
2143*/
2144
2145void tex_run_alignment_error(void)
2146{
2147    int cmd = cur_cmd;
2148    int chr = cur_chr;
2149    if (cmd == alignment_cmd && chr == no_align_code) {
2150        if (! tex_aux_nested_no_align()) {
2151            tex_handle_error(
2152                normal_error_type,
2153                "Misplaced \\noalign",
2154                "I expect to see \\noalign only after the \\cr of an alignment. Proceed, and I'll\n"
2155                "ignore this case."
2156            );
2157        }
2158    } else if (abs(lmt_input_state.align_state) > 2) {
2159        /*tex
2160            Express consternation over the fact that no alignment is in progress. In traditional
2161            \TEX\ the ampersand case will show a specific tab help, while in case of another
2162            character a more generic message is shown.
2163
2164            We go for consistency here, so a little patch:
2165        */
2166        switch (cmd) {
2167            case alignment_tab_cmd:
2168                tex_handle_error(normal_error_type, "Misplaced %C", cmd, chr,
2169                    "I can't figure out why you would want to use a tab mark here. If some right brace\n"
2170                    "up above has ended a previous alignment prematurely, you're probably due for more\n"
2171                    "error messages."
2172                );
2173                break;
2174            default:
2175                tex_handle_error(normal_error_type, "Misplaced %C", cmd, chr,
2176                    "I can't figure out why you would want to use a tab mark or \\cr or \\span just\n"
2177                    "now. If something like a right brace up above has ended a previous alignment\n"
2178                    "prematurely, you're probably due for more error messages."
2179                );
2180                break;
2181        }
2182    } else {
2183        const char * helpinfo =
2184            "I've put in what seems to be necessary to fix the current column of the current\n"
2185            "alignment. Try to go on, since this might almost work.";
2186        tex_back_input(cur_tok);
2187        if (lmt_input_state.align_state < 0) {
2188            ++lmt_input_state.align_state;
2189            cur_tok = left_brace_token + '{';
2190            tex_handle_error(
2191                insert_error_type,
2192                "Missing { inserted",
2193                helpinfo
2194            );
2195        } else {
2196            --lmt_input_state.align_state;
2197            cur_tok = right_brace_token + '}';
2198            switch (cmd) {
2199                case alignment_cmd:
2200                    tex_handle_error(
2201                        insert_error_type,
2202                        "Missing } inserted, unexpected ",
2203                        cmd, chr,
2204                        helpinfo
2205                    );
2206                    break;
2207                case alignment_tab_cmd:
2208                    tex_handle_error(
2209                        insert_error_type,
2210                        "Missing } inserted, unexpected tab character (normally &)",
2211                        helpinfo
2212                    );
2213                    break;
2214            }
2215        }
2216    }
2217}
2218