1% align.w 2% 3% Copyright 2009-2010 Taco Hoekwater <taco@@luatex.org> 4% 5% This file is part of LuaTeX. 6% 7% LuaTeX is free software; you can redistribute it and/or modify it under 8% the terms of the GNU General Public License as published by the Free 9% Software Foundation; either version 2 of the License, or (at your 10% option) any later version. 11% 12% LuaTeX is distributed in the hope that it will be useful, but WITHOUT 13% ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14% FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15% License for more details. 16% 17% You should have received a copy of the GNU General Public License along 18% with LuaTeX; if not, see <http://www.gnu.org/licenses/>. 19 20\def\<#1>{$#1$} 21 22@ @c 23 24 25#include "ptexlib.h" 26 27@ @c 28void fin_align(void); 29void init_row(void); 30void init_col(void); 31 32#define noDEBUG 33 34#define end_template_token (cs_token_flag+frozen_end_template) 35 36#define prev_depth cur_list.prev_depth_field 37#define space_factor cur_list.space_factor_field 38#define incompleat_noad cur_list.incompleat_noad_field 39 40#define every_cr equiv(every_cr_loc) 41#define display_indent dimen_par(display_indent_code) 42#define max_depth dimen_par(max_depth_code) 43#define pdf_ignored_dimen dimen_par(pdf_ignored_dimen_code) 44#define overfull_rule dimen_par(overfull_rule_code) 45 46@ It's sort of a miracle whenever \.{\\halign} and \.{\\valign} work, because 47they cut across so many of the control structures of \TeX. 48 49Therefore the 50present page is probably not the best place for a beginner to start reading 51this program; it is better to master everything else first. 52 53Let us focus our thoughts on an example of what the input might be, in order 54to get some idea about how the alignment miracle happens. The example doesn't 55do anything useful, but it is sufficiently general to indicate all of the 56special cases that must be dealt with; please do not be disturbed by its 57apparent complexity and meaninglessness. 58$$\vbox{\halign{\.{#}\hfil\cr 59{}\\tabskip 2pt plus 3pt\cr 60{}\\halign to 300pt\{u1\#v1\&\cr 61\hskip 50pt\\tabskip 1pt plus 1fil u2\#v2\&\cr 62\hskip 50pt u3\#v3\\cr\cr 63\hskip 25pt a1\&\\omit a2\&\\vrule\\cr\cr 64\hskip 25pt \\noalign\{\\vskip 3pt\}\cr 65\hskip 25pt b1\\span b2\\cr\cr 66\hskip 25pt \\omit\&c2\\span\\omit\\cr\}\cr}}$$ 67Here's what happens: 68 69\yskip 70(0) When `\.{\\halign to 300pt\{}' is scanned, the |scan_spec| routine 71places the 300pt dimension onto the |save_stack|, and an |align_group| 72code is placed above it. This will make it possible to complete the alignment 73when the matching `\.\}' is found. 74 75(1) The preamble is scanned next. Macros in the preamble are not expanded, 76@^preamble@> 77except as part of a tabskip specification. For example, if \.{u2} had been 78a macro in the preamble above, it would have been expanded, since \TeX\ 79must look for `\.{minus...}' as part of the tabskip glue. A ``preamble list'' 80is constructed based on the user's preamble; in our case it contains the 81following seven items: 82$$\vbox{\halign{\.{#}\hfil\qquad&(#)\hfil\cr 83{}\\glue 2pt plus 3pt&the tabskip preceding column 1\cr 84{}\\alignrecord, width $-\infty$&preamble info for column 1\cr 85{}\\glue 2pt plus 3pt&the tabskip between columns 1 and 2\cr 86{}\\alignrecord, width $-\infty$&preamble info for column 2\cr 87{}\\glue 1pt plus 1fil&the tabskip between columns 2 and 3\cr 88{}\\alignrecord, width $-\infty$&preamble info for column 3\cr 89{}\\glue 1pt plus 1fil&the tabskip following column 3\cr}}$$ 90These ``alignrecord'' entries have the same size as an |unset_node|, 91since they will later be converted into such nodes. These alignrecord 92nodes have no |depth| field; this is split into |u_part| and |v_part|, 93and they point to token lists for the templates of the alignment. For 94example, the |u_part| field in the first alignrecord points to the 95token list `\.{u1}', i.e., the template preceding the `\.\#' for 96column~1. Furthermore, They have a |span_ptr| instead of a |node_attr| 97field, and these |span_ptr| fields are initially set to the value 98|end_span|, for reasons explained below. 99 100(2) \TeX\ now looks at what follows the \.{\\cr} that ended the preamble. 101It is not `\.{\\noalign}' or `\.{\\omit}', so this input is put back to 102be read again, and the template `\.{u1}' is fed to the scanner. Just 103before reading `\.{u1}', \TeX\ goes into restricted horizontal mode. 104Just after reading `\.{u1}', \TeX\ will see `\.{a1}', and then (when the 105{\.\&} is sensed) \TeX\ will see `\.{v1}'. Then \TeX\ scans an |endv| 106token, indicating the end of a column. At this point an |unset_node| is 107created, containing the contents of the current hlist (i.e., `\.{u1a1v1}'). 108The natural width of this unset node replaces the |width| field of the 109alignrecord for column~1; in general, the alignrecords will record the 110maximum natural width that has occurred so far in a given column. 111 112(3) Since `\.{\\omit}' follows the `\.\&', the templates for column~2 113are now bypassed. Again \TeX\ goes into restricted horizontal mode and 114makes an |unset_node| from the resulting hlist; but this time the 115hlist contains simply `\.{a2}'. The natural width of the new unset box 116is remembered in the |width| field of the alignrecord for column~2. 117 118(4) A third |unset_node| is created for column 3, using essentially the 119mechanism that worked for column~1; this unset box contains `\.{u3\\vrule 120v3}'. The vertical rule in this case has running dimensions that will later 121extend to the height and depth of the whole first row, since each |unset_node| 122in a row will eventually inherit the height and depth of its enclosing box. 123 124(5) The first row has now ended; it is made into a single unset box 125comprising the following seven items: 126$$\vbox{\halign{\hbox to 325pt{\qquad\.{#}\hfil}\cr 127{}\\glue 2pt plus 3pt\cr 128{}\\unsetbox for 1 column: u1a1v1\cr 129{}\\glue 2pt plus 3pt\cr 130{}\\unsetbox for 1 column: a2\cr 131{}\\glue 1pt plus 1fil\cr 132{}\\unsetbox for 1 column: u3\\vrule v3\cr 133{}\\glue 1pt plus 1fil\cr}}$$ 134The width of this unset row is unimportant, but it has the correct height 135and depth, so the correct baselineskip glue will be computed as the row 136is inserted into a vertical list. 137 138(6) Since `\.{\\noalign}' follows the current \.{\\cr}, \TeX\ appends 139additional material (in this case \.{\\vskip 3pt}) to the vertical list. 140While processing this material, \TeX\ will be in internal vertical 141mode, and |no_align_group| will be on |save_stack|. 142 143(7) The next row produces an unset box that looks like this: 144$$\vbox{\halign{\hbox to 325pt{\qquad\.{#}\hfil}\cr 145{}\\glue 2pt plus 3pt\cr 146{}\\unsetbox for 2 columns: u1b1v1u2b2v2\cr 147{}\\glue 1pt plus 1fil\cr 148{}\\unsetbox for 1 column: {\rm(empty)}\cr 149{}\\glue 1pt plus 1fil\cr}}$$ 150The natural width of the unset box that spans columns 1~and~2 is stored 151in a ``span node,'' which we will explain later; the |span_ptr| field of the 152alignrecord for column~1 now points to the new span node, and the |span_ptr| 153of the span node points to |end_span|. 154 155(8) The final row produces the unset box 156$$\vbox{\halign{\hbox to 325pt{\qquad\.{#}\hfil}\cr 157{}\\glue 2pt plus 3pt\cr 158{}\\unsetbox for 1 column: {\rm(empty)}\cr 159{}\\glue 2pt plus 3pt\cr 160{}\\unsetbox for 2 columns: u2c2v2\cr 161{}\\glue 1pt plus 1fil\cr}}$$ 162A new span node is attached to the alignrecord for column 2. 163 164(9) The last step is to compute the true column widths and to change all the 165unset boxes to hboxes, appending the whole works to the vertical list that 166encloses the \.{\\halign}. The rules for deciding on the final widths of 167each unset column box will be explained below. 168 169\yskip\noindent 170Note that as \.{\\halign} is being processed, we fearlessly give up control 171to the rest of \TeX. At critical junctures, an alignment routine is 172called upon to step in and do some little action, but most of the time 173these routines just lurk in the background. It's something like 174post-hypnotic suggestion. 175 176 177 178@ We have mentioned that alignrecords contain no |height| or |depth| fields. 179Their |glue_sign| and |glue_order| are pre-empted as well, since it 180is necessary to store information about what to do when a template ends. 181This information is called the |extra_info| field. 182 183@c 184#define u_part(A) vlink((A)+depth_offset) /* pointer to \<u_j> token list */ 185#define v_part(A) vinfo((A)+depth_offset) /* pointer to \<v_j> token list */ 186#define span_ptr(A) vinfo((A)+1) /* column spanning list */ 187#define extra_info(A) vinfo((A)+list_offset) /* info to remember during template */ 188 189 190@ Alignments can occur within alignments, so a small stack is used to access 191the alignrecord information. At each level we have a |preamble| pointer, 192indicating the beginning of the preamble list; a |cur_align| pointer, 193indicating the current position in the preamble list; a |cur_span| pointer, 194indicating the value of |cur_align| at the beginning of a sequence of 195spanned columns; a |cur_loop| pointer, indicating the tabskip glue before 196an alignrecord that should be copied next if the current list is extended; 197and the |align_state| variable, which indicates the nesting of braces so 198that \.{\\cr} and \.{\\span} and tab marks are properly intercepted. 199There also are pointers |cur_head| and |cur_tail| to the head and tail 200of a list of adjustments being moved out from horizontal mode to 201vertical~mode, and alike |cur_pre_head| and |cur_pre_tail| for pre-adjust 202lists. 203 204The current values of these nine quantities appear in global variables; 205when they have to be pushed down, they are stored in 6-word nodes, and 206|align_ptr| points to the topmost such node. 207 208@c 209#define preamble vlink(align_head) /* the current preamble list */ 210 211pointer cur_align = null; /* current position in preamble list */ 212pointer cur_span = null; /* start of currently spanned columns in preamble list */ 213pointer cur_loop = null; /* place to copy when extending a periodic preamble */ 214pointer align_ptr = null; /* most recently pushed-down alignment stack node */ 215pointer cur_head = null, cur_tail = null; /* adjustment list pointers */ 216pointer cur_pre_head = null, cur_pre_tail = null; /* pre-adjustment list pointers */ 217 218/* The |align_state| and |preamble| variables are initialized elsewhere. */ 219 220@ Alignment stack maintenance is handled by a pair of trivial routines 221called |push_alignment| and |pop_alignment|. 222 223@c 224static void push_alignment(void) 225{ 226 pointer p; /* the new alignment stack node */ 227 p = new_node(align_stack_node, 0); 228 vinfo(p + 1) = align_ptr; 229 vlink(p + 1) = cur_align; 230 vinfo(p + 2) = preamble; 231 vlink(p + 2) = cur_span; 232 vinfo(p + 3) = cur_loop; 233 vlink(p + 3) = align_state; 234 vinfo(p + 4) = cur_head; 235 vlink(p + 4) = cur_tail; 236 vinfo(p + 5) = cur_pre_head; 237 vlink(p + 5) = cur_pre_tail; 238 align_ptr = p; 239 cur_head = new_node(temp_node, 0); 240 cur_pre_head = new_node(temp_node, 0); 241} 242 243static void pop_alignment(void) 244{ 245 pointer p; /* the top alignment stack node */ 246 flush_node(cur_head); 247 flush_node(cur_pre_head); 248 p = align_ptr; 249 cur_pre_tail = vlink(p + 5); 250 cur_pre_head = vinfo(p + 5); 251 cur_tail = vlink(p + 4); 252 cur_head = vinfo(p + 4); 253 align_state = vlink(p + 3); 254 cur_loop = vinfo(p + 3); 255 cur_span = vlink(p + 2); 256 preamble = vinfo(p + 2); 257 cur_align = vlink(p + 1); 258 align_ptr = vinfo(p + 1); 259 flush_node(p); 260} 261 262 263@ \TeX\ has eight procedures that govern alignments: |init_align| and 264|fin_align| are used at the very beginning and the very end; |init_row| and 265|fin_row| are used at the beginning and end of individual rows; |init_span| 266is used at the beginning of a sequence of spanned columns (possibly involving 267only one column); |init_col| and |fin_col| are used at the beginning and 268end of individual columns; and |align_peek| is used after \.{\\cr} to see 269whether the next item is \.{\\noalign}. 270 271We shall consider these routines in the order they are first used during 272the course of a complete \.{\\halign}, namely |init_align|, |align_peek|, 273|init_row|, |init_span|, |init_col|, |fin_col|, |fin_row|, |fin_align|. 274 275 276@ The preamble is copied directly, except that \.{\\tabskip} causes a change 277to the tabskip glue, thereby possibly expanding macros that immediately 278follow it. An appearance of \.{\\span} also causes such an expansion. 279 280Note that if the preamble contains `\.{\\global\\tabskip}', the `\.{\\global}' 281token survives in the preamble and the `\.{\\tabskip}' defines new 282tabskip glue (locally). 283 284@c 285static void get_preamble_token(void) 286{ 287 RESTART: 288 get_token(); 289 while ((cur_chr == span_code) && (cur_cmd == tab_mark_cmd)) { 290 get_token(); /* this token will be expanded once */ 291 if (cur_cmd > max_command_cmd) { 292 expand(); 293 get_token(); 294 } 295 } 296 if (cur_cmd == endv_cmd) 297 fatal_error("(interwoven alignment preambles are not allowed)"); 298 if ((cur_cmd == assign_glue_cmd) 299 && (cur_chr == glue_base + tab_skip_code)) { 300 scan_optional_equals(); 301 scan_glue(glue_val_level); 302 if (int_par(global_defs_code) > 0) 303 geq_define(glue_base + tab_skip_code, glue_ref_cmd, cur_val); 304 else 305 eq_define(glue_base + tab_skip_code, glue_ref_cmd, cur_val); 306 goto RESTART; 307 } 308} 309 310 311 312@ When \.{\\halign} or \.{\\valign} has been scanned in an appropriate 313mode, \TeX\ calls |init_align|, whose task is to get everything off to a 314good start. This mostly involves scanning the preamble and putting its 315information into the preamble list. 316@^preamble@> 317 318@c 319void init_align(void) 320{ 321 /* label done, done1, done2, continue; */ 322 pointer save_cs_ptr; /* |warning_index| value for error messages */ 323 pointer p, r; /* for short-term temporary use */ 324 save_cs_ptr = cur_cs; /* \.{\\halign} or \.{\\valign}, usually */ 325 push_alignment(); 326 align_state = -1000000; /* enter a new alignment level */ 327 328 /* When \.{\\halign} is used as a displayed formula, there should be 329 no other pieces of mlists present. */ 330 331 if ((cur_list.mode_field == mmode) 332 && ((cur_list.tail_field != cur_list.head_field) 333 || (incompleat_noad != null))) { 334 const char *hlp[] = 335 { "Displays can use special alignments (like \\eqalignno)", 336 "only if nothing but the alignment itself is between $$'s.", 337 "So I've deleted the formulas that preceded this alignment.", 338 NULL 339 }; 340 tex_error("Improper \\halign inside $$'s", hlp); 341 flush_math(); 342 } 343 push_nest(); /* enter a new semantic level */ 344 /* In vertical modes, |prev_depth| already has the correct value. But 345 if we are in |mmode| (displayed formula mode), we reach out to the 346 enclosing vertical mode for the |prev_depth| value that produces the 347 correct baseline calculations. */ 348 if (cur_list.mode_field == mmode) { 349 cur_list.mode_field = -vmode; 350 prev_depth = nest[nest_ptr - 2].prev_depth_field; 351 } else if (cur_list.mode_field > 0) { 352 cur_list.mode_field = -(cur_list.mode_field); 353 } 354 scan_spec(align_group); 355 /* Scan the preamble */ 356 preamble = null; 357 cur_align = align_head; 358 cur_loop = null; 359 scanner_status = aligning; 360 warning_index = save_cs_ptr; 361 align_state = -1000000; 362 /* at this point, |cur_cmd=left_brace| */ 363 while (true) { 364 /* Append the current tabskip glue to the preamble list */ 365 r = new_param_glue(tab_skip_code); 366 vlink(cur_align) = r; 367 cur_align = vlink(cur_align); 368 369 if (cur_cmd == car_ret_cmd) 370 break; /* \.{\\cr} ends the preamble */ 371 372 /* Scan preamble text until |cur_cmd| is |tab_mark| or |car_ret| */ 373 /* Scan the template \<u_j>, putting the resulting token list in |hold_token_head| */ 374 /* Spaces are eliminated from the beginning of a template. */ 375 376 p = hold_token_head; 377 token_link(p) = null; 378 while (1) { 379 get_preamble_token(); 380 if (cur_cmd == mac_param_cmd) 381 break; 382 if ((cur_cmd <= car_ret_cmd) && (cur_cmd >= tab_mark_cmd) 383 && (align_state == -1000000)) { 384 if ((p == hold_token_head) && (cur_loop == null) 385 && (cur_cmd == tab_mark_cmd)) { 386 cur_loop = cur_align; 387 } else { 388 const char *hlp[] = 389 { "There should be exactly one # between &'s, when an", 390 "\\halign or \\valign is being set up. In this case you had", 391 "none, so I've put one in; maybe that will work.", 392 NULL 393 }; 394 back_input(); 395 tex_error("Missing # inserted in alignment preamble", hlp); 396 break; 397 } 398 } else if ((cur_cmd != spacer_cmd) || (p != hold_token_head)) { 399 r = get_avail(); 400 token_link(p) = r; 401 p = token_link(p); 402 token_info(p) = cur_tok; 403 } 404 } 405 r = new_node(align_record_node, 0); 406 vlink(cur_align) = r; 407 cur_align = vlink(cur_align); /* a new alignrecord */ 408 span_ptr(cur_align) = end_span; 409 width(cur_align) = null_flag; 410 u_part(cur_align) = token_link(hold_token_head); 411 /* Scan the template \<v_j>, putting the resulting token list in |hold_token_head| */ 412 413 p = hold_token_head; 414 token_link(p) = null; 415 while (1) { 416 CONTINUE: 417 get_preamble_token(); 418 if ((cur_cmd <= car_ret_cmd) && (cur_cmd >= tab_mark_cmd) 419 && (align_state == -1000000)) 420 break; 421 if (cur_cmd == mac_param_cmd) { 422 const char *hlp[] = 423 { "There should be exactly one # between &'s, when an", 424 "\\halign or \\valign is being set up. In this case you had", 425 "more than one, so I'm ignoring all but the first.", 426 NULL 427 }; 428 tex_error("Only one # is allowed per tab", hlp); 429 goto CONTINUE; 430 } 431 r = get_avail(); 432 token_link(p) = r; 433 p = token_link(p); 434 token_info(p) = cur_tok; 435 } 436 r = get_avail(); 437 token_link(p) = r; 438 p = token_link(p); 439 token_info(p) = end_template_token; /* put \.{\\endtemplate} at the end */ 440 441 v_part(cur_align) = token_link(hold_token_head); 442 } 443 scanner_status = normal; 444 445 new_save_level(align_group); 446 if (every_cr != null) 447 begin_token_list(every_cr, every_cr_text); 448 align_peek(); /* look for \.{\\noalign} or \.{\\omit} */ 449} 450 451 452@ The tricky part about alignments is getting the templates into the 453scanner at the right time, and recovering control when a row or column 454is finished. 455 456We usually begin a row after each \.{\\cr} has been sensed, unless that 457\.{\\cr} is followed by \.{\\noalign} or by the right brace that terminates 458the alignment. The |align_peek| routine is used to look ahead and do 459the right thing; it either gets a new row started, or gets a \.{\\noalign} 460started, or finishes off the alignment. 461 462@c 463void align_peek(void) 464{ 465 RESTART: 466 align_state = 1000000; 467 do { 468 get_x_or_protected(); 469 } while (cur_cmd == spacer_cmd); 470 if (cur_cmd == no_align_cmd) { 471 scan_left_brace(); 472 new_save_level(no_align_group); 473 if (cur_list.mode_field == -vmode) 474 normal_paragraph(); 475 } else if (cur_cmd == right_brace_cmd) { 476 fin_align(); 477 } else if ((cur_cmd == car_ret_cmd) && (cur_chr == cr_cr_code)) { 478 goto RESTART; /* ignore \.{\\crcr} */ 479 } else { 480 init_row(); /* start a new row */ 481 init_col(); /* start a new column and replace what we peeked at */ 482 } 483} 484 485 486@ The parameter to |init_span| is a pointer to the alignrecord where the 487next column or group of columns will begin. A new semantic level is 488entered, so that the columns will generate a list for subsequent packaging. 489 490@c 491static void init_span(pointer p) 492{ 493 push_nest(); 494 if (cur_list.mode_field == -hmode) { 495 space_factor = 1000; 496 } else { 497 prev_depth = pdf_ignored_dimen; 498 normal_paragraph(); 499 } 500 cur_span = p; 501} 502 503 504@ To start a row (i.e., a `row' that rhymes with `dough' but not with `bough'), 505we enter a new semantic level, copy the first tabskip glue, and change 506from internal vertical mode to restricted horizontal mode or vice versa. 507The |space_factor| and |prev_depth| are not used on this semantic level, 508but we clear them to zero just to be tidy. 509 510@c 511void init_row(void) 512{ 513 push_nest(); 514 cur_list.mode_field = (-hmode - vmode) - cur_list.mode_field; 515 if (cur_list.mode_field == -hmode) 516 space_factor = 0; 517 else 518 prev_depth = 0; 519 tail_append(new_glue(glue_ptr(preamble))); 520 subtype(cur_list.tail_field) = tab_skip_code + 1; 521 cur_align = vlink(preamble); 522 cur_tail = cur_head; 523 cur_pre_tail = cur_pre_head; 524 init_span(cur_align); 525} 526 527 528@ When a column begins, we assume that |cur_cmd| is either |omit| or else 529the current token should be put back into the input until the \<u_j> 530template has been scanned. (Note that |cur_cmd| might be |tab_mark| or 531|car_ret|.) We also assume that |align_state| is approximately 1000000 at 532this time. We remain in the same mode, and start the template if it is 533called for. 534 535@c 536void init_col(void) 537{ 538 extra_info(cur_align) = cur_cmd; 539 if (cur_cmd == omit_cmd) 540 align_state = 0; 541 else { 542 back_input(); 543 begin_token_list(u_part(cur_align), u_template); 544 } /* now |align_state=1000000| */ 545} 546 547 548@ The scanner sets |align_state| to zero when the \<u_j> template ends. When 549a subsequent \.{\\cr} or \.{\\span} or tab mark occurs with |align_state=0|, 550the scanner activates the following code, which fires up the \<v_j> template. 551We need to remember the |cur_chr|, which is either |cr_cr_code|, |cr_code|, 552|span_code|, or a character code, depending on how the column text has ended. 553 554This part of the program had better not be activated when the preamble 555to another alignment is being scanned, or when no alignment preamble is active. 556 557@c 558void insert_vj_template(void) 559{ 560 if ((scanner_status == aligning) || (cur_align == null)) 561 fatal_error("(interwoven alignment preambles are not allowed)"); 562 cur_cmd = extra_info(cur_align); 563 extra_info(cur_align) = cur_chr; 564 if (cur_cmd == omit_cmd) 565 begin_token_list(omit_template, v_template); 566 else 567 begin_token_list(v_part(cur_align), v_template); 568 align_state = 1000000; 569} 570 571/* Determine the stretch order */ 572#define determine_stretch_order() do { \ 573 if (total_stretch[filll]!=0) o=filll; \ 574 else if (total_stretch[fill]!=0) o=fill; \ 575 else if (total_stretch[fil]!=0) o=fil; \ 576 else if (total_stretch[sfi]!=0) o=sfi; \ 577 else o=normal; \ 578 } while (0) 579 580 581/* Determine the shrink order */ 582#define determine_shrink_order() do { \ 583 if (total_shrink[filll]!=0) o=filll; \ 584 else if (total_shrink[fill]!=0) o=fill; \ 585 else if (total_shrink[fil]!=0) o=fil; \ 586 else if (total_shrink[sfi]!=0) o=sfi; \ 587 else o=normal; \ 588 } while (0) 589 590 591 592@ When the |endv| command at the end of a \<v_j> template comes through the 593scanner, things really start to happen; and it is the |fin_col| routine 594that makes them happen. This routine returns |true| if a row as well as a 595column has been finished. 596 597@c 598boolean fin_col(void) 599{ 600 pointer p; /* the alignrecord after the current one */ 601 pointer q, r; /* temporary pointers for list manipulation */ 602 pointer s; /* a new span node */ 603 pointer u; /* a new unset box */ 604 scaled w; /* natural width */ 605 unsigned char o; /* order of infinity */ 606 halfword n; /* span counter */ 607 if (cur_align == null) 608 confusion("endv"); 609 q = vlink(cur_align); 610 if (q == null) 611 confusion("endv"); 612 if (align_state < 500000) 613 fatal_error("(interwoven alignment preambles are not allowed)"); 614 p = vlink(q); 615 /* If the preamble list has been traversed, check that the row has ended */ 616 if ((p == null) && (extra_info(cur_align) < cr_code)) { 617 if (cur_loop != null) { 618 /* Lengthen the preamble periodically */ 619 r = new_node(align_record_node, 0); 620 vlink(q) = r; 621 p = vlink(q); /* a new alignrecord */ 622 span_ptr(p) = end_span; 623 width(p) = null_flag; 624 cur_loop = vlink(cur_loop); 625 626 /* Copy the templates from node |cur_loop| into node |p| */ 627 q = hold_token_head; 628 r = u_part(cur_loop); 629 while (r != null) { 630 s = get_avail(); 631 token_link(q) = s; 632 q = token_link(q); 633 token_info(q) = token_info(r); 634 r = token_link(r); 635 } 636 token_link(q) = null; 637 u_part(p) = token_link(hold_token_head); 638 q = hold_token_head; 639 r = v_part(cur_loop); 640 while (r != null) { 641 s = get_avail(); 642 token_link(q) = s; 643 q = token_link(q); 644 token_info(q) = token_info(r); 645 r = token_link(r); 646 } 647 token_link(q) = null; 648 v_part(p) = token_link(hold_token_head); 649 650 cur_loop = vlink(cur_loop); 651 r = new_glue(glue_ptr(cur_loop)); 652 vlink(p) = r; 653 } else { 654 const char *hlp[] = 655 { "You have given more \\span or & marks than there were", 656 "in the preamble to the \\halign or \\valign now in progress.", 657 "So I'll assume that you meant to type \\cr instead.", 658 NULL 659 }; 660 extra_info(cur_align) = cr_code; 661 tex_error("Extra alignment tab has been changed to \\cr", hlp); 662 } 663 } 664 if (extra_info(cur_align) != span_code) { 665 unsave(); 666 new_save_level(align_group); 667 /* Package an unset box for the current column and record its width */ 668 if (cur_list.mode_field == -hmode) { 669 adjust_tail = cur_tail; 670 pre_adjust_tail = cur_pre_tail; 671 u = filtered_hpack(cur_list.head_field, cur_list.tail_field, 0, 672 additional, align_set_group, -1); 673 w = width(u); 674 cur_tail = adjust_tail; 675 adjust_tail = null; 676 cur_pre_tail = pre_adjust_tail; 677 pre_adjust_tail = null; 678 } else { 679 u = filtered_vpackage(vlink(cur_list.head_field), 0, additional, 0, 680 align_set_group, -1); 681 w = height(u); 682 } 683 n = min_quarterword; /* this represents a span count of 1 */ 684 if (cur_span != cur_align) { 685 /* Update width entry for spanned columns */ 686 q = cur_span; 687 do { 688 incr(n); 689 q = vlink(vlink(q)); 690 } while (q != cur_align); 691 if (n > max_quarterword) 692 confusion("too many spans"); /* this can happen, but won't */ 693 q = cur_span; 694 while (span_span(span_ptr(q)) < n) { 695 q = span_ptr(q); 696 } 697 if (span_span(span_ptr(q)) > n) { 698 s = new_span_node(span_ptr(q), n, w); 699 span_ptr(q) = s; 700 } else if (width(span_ptr(q)) < w) { 701 width(span_ptr(q)) = w; 702 } 703 704 } else if (w > width(cur_align)) { 705 width(cur_align) = w; 706 } 707 type(u) = unset_node; 708 span_count(u) = (quarterword) n; 709 determine_stretch_order(); 710 glue_order(u) = o; 711 glue_stretch(u) = total_stretch[o]; 712 determine_shrink_order(); 713 glue_sign(u) = o; 714 glue_shrink(u) = total_shrink[o]; 715 pop_nest(); 716 vlink(cur_list.tail_field) = u; 717 cur_list.tail_field = u; 718 719 /* Copy the tabskip glue between columns */ 720 tail_append(new_glue(glue_ptr(vlink(cur_align)))); 721 subtype(cur_list.tail_field) = tab_skip_code + 1; 722 723 if (extra_info(cur_align) >= cr_code) { 724 return true; 725 } 726 init_span(p); 727 } 728 align_state = 1000000; 729 do { 730 get_x_or_protected(); 731 } while (cur_cmd == spacer_cmd); 732 cur_align = p; 733 init_col(); 734 return false; 735} 736 737 738 739@ A span node is a 3-word record containing |width|, |span_span|, and 740|span_ptr| fields. The |span_span| field indicates the number of 741spanned columns; the |span_ptr| field points to a span node for the same 742starting column, having a greater extent of spanning, or to 743|end_span|, which has the largest possible |span_span| field; the |width| 744field holds the largest natural width corresponding to a particular 745set of spanned columns. 746 747A list of the maximum widths so far, for spanned columns starting at a 748given column, begins with the |span_ptr| field of the alignrecord for 749that column. The code has to make sure that there is room for 750|span_ptr| in both the alignrecord and the span nodes, which is why 751|span_ptr| replaces |node_attr|. 752@^data structure assumptions@> 753 754The |new_span_node| function is defined in |texnodes.c|. 755 756@c 757#ifndef span_span 758# define span_span(A) vlink((A)+1) /* that is normally |alink| */ 759#endif 760 761 762@ At the end of a row, we append an unset box to the current vlist (for 763\.{\\halign}) or the current hlist (for \.{\\valign}). This unset box 764contains the unset boxes for the columns, separated by the tabskip glue. 765Everything will be set later. 766 767@c 768void fin_row(void) 769{ 770 pointer p; /* the new unset box */ 771 if (cur_list.mode_field == -hmode) { 772 p = filtered_hpack(cur_list.head_field, cur_list.tail_field, 0, 773 additional, fin_row_group, -1); 774 pop_nest(); 775 if (cur_pre_head != cur_pre_tail) 776 append_list(cur_pre_head, cur_pre_tail); 777 append_to_vlist(p); 778 if (cur_head != cur_tail) 779 append_list(cur_head, cur_tail); 780 } else { 781 p = filtered_vpackage(vlink(cur_list.head_field), 0, additional, 782 max_depth, fin_row_group, -1); 783 pop_nest(); 784 vlink(cur_list.tail_field) = p; 785 cur_list.tail_field = p; 786 space_factor = 1000; 787 } 788 type(p) = unset_node; 789 glue_stretch(p) = 0; 790 if (every_cr != null) 791 begin_token_list(every_cr, every_cr_text); 792 align_peek(); 793 /* note that |glue_shrink(p)=0| since |glue_shrink==shift_amount| */ 794} 795 796 797@ Finally, we will reach the end of the alignment, and we can breathe a 798sigh of relief that memory hasn't overflowed. All the unset boxes will now be 799set so that the columns line up, taking due account of spanned columns. 800 801@c 802void fin_align(void) 803{ 804 pointer p, q, r, s, u, v, rr; /* registers for the list operations */ 805 scaled t, w; /* width of column */ 806 scaled o; /* shift offset for unset boxes */ 807 halfword n; /* matching span amount */ 808 scaled rule_save; /* temporary storage for |overfull_rule| */ 809 halfword pd; /* temporary storage for |prev_depth| */ 810 if (cur_group != align_group) 811 confusion("align1"); 812 unsave(); /* that |align_group| was for individual entries */ 813 if (cur_group != align_group) 814 confusion("align0"); 815 unsave(); /* that |align_group| was for the whole alignment */ 816 if (nest[nest_ptr - 1].mode_field == mmode) 817 o = display_indent; 818 else 819 o = 0; 820 /* Go through the preamble list, determining the column widths and 821 * changing the alignrecords to dummy unset boxes 822 */ 823 824/* It's time now to dismantle the preamble list and to compute the column 825widths. Let $w_{ij}$ be the maximum of the natural widths of all entries 826that span columns $i$ through $j$, inclusive. The alignrecord for column~$i$ 827contains $w_{ii}$ in its |width| field, and there is also a linked list of 828the nonzero $w_{ij}$ for increasing $j$, accessible via the |info| field; 829these span nodes contain the value $j-i+|min_quarterword|$ in their 830|link| fields. The values of $w_{ii}$ were initialized to |null_flag|, which 831we regard as $-\infty$. 832 833The final column widths are defined by the formula 834$$w_j=\max_{1\L i\L j}\biggl( w_{ij}-\sum_{i\L k<j}(t_k+w_k)\biggr),$$ 835where $t_k$ is the natural width of the tabskip glue between columns 836$k$ and~$k+1$. However, if $w_{ij}=-\infty$ for all |i| in the range 837|1<=i<=j| (i.e., if every entry that involved column~|j| also involved 838column~|j+1|), we let $w_j=0$, and we zero out the tabskip glue after 839column~|j|. 840 841\TeX\ computes these values by using the following scheme: First $w_1=w_{11}$. 842Then replace $w_{2j}$ by $\max(w_{2j},w_{1j}-t_1-w_1)$, for all $j>1$. 843Then $w_2=w_{22}$. Then replace $w_{3j}$ by $\max(w_{3j},w_{2j}-t_2-w_2)$ 844for all $j>2$; and so on. If any $w_j$ turns out to be $-\infty$, its 845value is changed to zero and so is the next tabskip. 846*/ 847 q = vlink(preamble); 848 do { 849 flush_list(u_part(q)); 850 flush_list(v_part(q)); 851 p = vlink(vlink(q)); 852 if (width(q) == null_flag) { 853 /* Nullify |width(q)| and the tabskip glue following this column */ 854 width(q) = 0; 855 r = vlink(q); 856 s = glue_ptr(r); 857 if (s != zero_glue) { 858 add_glue_ref(zero_glue); 859 delete_glue_ref(s); 860 glue_ptr(r) = zero_glue; 861 } 862 } 863 if (span_ptr(q) != end_span) { 864 /* Merge the widths in the span nodes of |q| with those of |p|, 865 destroying the span nodes of |q| */ 866 /* 867 Merging of two span-node lists is a typical exercise in the manipulation of 868 linearly linked data structures. The essential invariant in the following 869 |repeat| loop is that we want to dispense with node |r|, in |q|'s list, 870 and |u| is its successor; all nodes of |p|'s list up to and including |s| 871 have been processed, and the successor of |s| matches |r| or precedes |r| 872 or follows |r|, according as |link(r)=n| or |link(r)>n| or |link(r)<n|. 873 */ 874 t = width(q) + width(glue_ptr(vlink(q))); 875 r = span_ptr(q); 876 s = end_span; 877 span_ptr(s) = p; 878 n = min_quarterword + 1; 879 do { 880 width(r) = width(r) - t; 881 u = span_ptr(r); 882 while (span_span(r) > n) { 883 s = span_ptr(s); 884 n = span_span(span_ptr(s)) + 1; 885 } 886 if (span_span(r) < n) { 887 span_ptr(r) = span_ptr(s); 888 span_ptr(s) = r; 889 decr(span_span(r)); 890 s = r; 891 } else { 892 if (width(r) > width(span_ptr(s))) 893 width(span_ptr(s)) = width(r); 894 flush_node(r); 895 } 896 r = u; 897 } while (r != end_span); 898 } 899 type(q) = unset_node; 900 span_count(q) = min_quarterword; 901 height(q) = 0; 902 depth(q) = 0; 903 glue_order(q) = normal; 904 glue_sign(q) = normal; 905 glue_stretch(q) = 0; 906 glue_shrink(q) = 0; 907 q = p; 908 } while (q != null); 909 910 /* Package the preamble list, to determine the actual tabskip glue amounts, 911 and let |p| point to this prototype box */ 912 /* Now the preamble list has been converted to a list of alternating unset 913 boxes and tabskip glue, where the box widths are equal to the final 914 column sizes. In case of \.{\\valign}, we change the widths to heights, 915 so that a correct error message will be produced if the alignment is 916 overfull or underfull. 917 */ 918 919 decr(save_ptr); 920 pack_begin_line = -cur_list.ml_field; 921 if (cur_list.mode_field == -vmode) { 922 rule_save = overfull_rule; 923 overfull_rule = 0; /* prevent rule from being packaged */ 924 p = hpack(preamble, saved_value(0), saved_level(0), -1); 925 overfull_rule = rule_save; 926 } else { 927 q = vlink(preamble); 928 do { 929 height(q) = width(q); 930 width(q) = 0; 931 q = vlink(vlink(q)); 932 } while (q != null); 933 p = filtered_vpackage(preamble, saved_value(0), saved_level(0), 934 max_depth, preamble_group, -1); 935 q = vlink(preamble); 936 do { 937 width(q) = height(q); 938 height(q) = 0; 939 q = vlink(vlink(q)); 940 } while (q != null); 941 } 942 pack_begin_line = 0; 943 944 /* Set the glue in all the unset boxes of the current list */ 945 q = vlink(cur_list.head_field); 946 s = cur_list.head_field; 947 while (q != null) { 948 if (!is_char_node(q)) { 949 if (type(q) == unset_node) { 950 /* Set the unset box |q| and the unset boxes in it */ 951 /* The unset box |q| represents a row that contains one or more unset boxes, 952 depending on how soon \.{\\cr} occurred in that row. */ 953 954 if (cur_list.mode_field == -vmode) { 955 type(q) = hlist_node; 956 subtype(q) = HLIST_SUBTYPE_ALIGNROW; 957 width(q) = width(p); 958 } else { 959 type(q) = vlist_node; 960 subtype(q) = HLIST_SUBTYPE_ALIGNROW; 961 height(q) = height(p); 962 } 963 glue_order(q) = glue_order(p); 964 glue_sign(q) = glue_sign(p); 965 glue_set(q) = glue_set(p); 966 shift_amount(q) = o; 967 r = vlink(list_ptr(q)); 968 assert (type(r) == unset_node); 969 s = vlink(list_ptr(p)); 970 do { 971 /* Set the glue in node |r| and change it from an unset node */ 972 /* A box made from spanned columns will be followed by tabskip glue nodes and 973 by empty boxes as if there were no spanning. This permits perfect alignment 974 of subsequent entries, and it prevents values that depend on floating point 975 arithmetic from entering into the dimensions of any boxes. 976 */ 977 n = span_count(r); 978 t = width(s); 979 w = t; 980 u = hold_head; 981 while (n > min_quarterword) { 982 decr(n); 983 /* Append tabskip glue and an empty box to list |u|, 984 and update |s| and |t| as the prototype nodes are passed */ 985 986 s = vlink(s); 987 v = glue_ptr(s); 988 vlink(u) = new_glue(v); 989 u = vlink(u); 990 subtype(u) = tab_skip_code + 1; 991 t = t + width(v); 992 if (glue_sign(p) == stretching) { 993 if (stretch_order(v) == glue_order(p)) 994 t = t + 995 round(float_cast(glue_set(p)) * 996 float_cast(stretch(v))); 997 } else if (glue_sign(p) == shrinking) { 998 if (shrink_order(v) == glue_order(p)) 999 t = t - 1000 round(float_cast(glue_set(p)) * 1001 float_cast(shrink(v))); 1002 } 1003 s = vlink(s); 1004 rr = new_null_box(); 1005 vlink(u) = rr; 1006 u = vlink(u); 1007 t = t + width(s); 1008 subtype(u) = HLIST_SUBTYPE_ALIGNCELL; 1009 if (cur_list.mode_field == -vmode) { 1010 width(u) = width(s); 1011 } else { 1012 type(u) = vlist_node; 1013 height(u) = width(s); 1014 } 1015 1016 } 1017 if (cur_list.mode_field == -vmode) { 1018 /* Make the unset node |r| into an |hlist_node| of width |w|, 1019 setting the glue as if the width were |t| */ 1020 1021 height(r) = height(q); 1022 depth(r) = depth(q); 1023 if (t == width(r)) { 1024 glue_sign(r) = normal; 1025 glue_order(r) = normal; 1026 set_glue_ratio_zero(glue_set(r)); 1027 } else if (t > width(r)) { 1028 glue_sign(r) = stretching; 1029 if (glue_stretch(r) == 0) 1030 set_glue_ratio_zero(glue_set(r)); 1031 else 1032 glue_set(r) = 1033 unfloat((double) (t - width(r)) / 1034 glue_stretch(r)); 1035 } else { 1036 glue_order(r) = glue_sign(r); 1037 glue_sign(r) = shrinking; 1038 if (glue_shrink(r) == 0) 1039 set_glue_ratio_zero(glue_set(r)); 1040 else if ((glue_order(r) == normal) 1041 && (width(r) - t > glue_shrink(r))) 1042 set_glue_ratio_one(glue_set(r)); 1043 else 1044 glue_set(r) = 1045 unfloat((double) (width(r) - t) / 1046 glue_shrink(r)); 1047 } 1048 width(r) = w; 1049 type(r) = hlist_node; 1050 subtype(r) = HLIST_SUBTYPE_ALIGNCELL; 1051 1052 } else { 1053 /* Make the unset node |r| into a |vlist_node| of height |w|, 1054 setting the glue as if the height were |t| */ 1055 1056 width(r) = width(q); 1057 if (t == height(r)) { 1058 glue_sign(r) = normal; 1059 glue_order(r) = normal; 1060 set_glue_ratio_zero(glue_set(r)); 1061 } else if (t > height(r)) { 1062 glue_sign(r) = stretching; 1063 if (glue_stretch(r) == 0) 1064 set_glue_ratio_zero(glue_set(r)); 1065 else 1066 glue_set(r) = 1067 unfloat((t - height(r)) / glue_stretch(r)); 1068 } else { 1069 glue_order(r) = glue_sign(r); 1070 glue_sign(r) = shrinking; 1071 if (glue_shrink(r) == 0) 1072 set_glue_ratio_zero(glue_set(r)); 1073 else if ((glue_order(r) == normal) 1074 && (height(r) - t > glue_shrink(r))) 1075 set_glue_ratio_one(glue_set(r)); 1076 else 1077 glue_set(r) = 1078 unfloat((height(r) - t) / glue_shrink(r)); 1079 } 1080 height(r) = w; 1081 type(r) = vlist_node; 1082 subtype(r) = HLIST_SUBTYPE_ALIGNCELL; 1083 1084 } 1085 /* subtype(r) = 0; */ 1086 shift_amount(r) = 0; 1087 if (u != hold_head) { /* append blank boxes to account for spanned nodes */ 1088 vlink(u) = vlink(r); 1089 vlink(r) = vlink(hold_head); 1090 r = u; 1091 } 1092 1093 r = vlink(vlink(r)); 1094 s = vlink(vlink(s)); 1095 } while (r != null); 1096 1097 } else if (type(q) == rule_node) { 1098 /* Make the running dimensions in rule |q| extend to the 1099 boundaries of the alignment */ 1100 if (is_running(width(q))) 1101 width(q) = width(p); 1102 if (is_running(height(q))) 1103 height(q) = height(p); 1104 if (is_running(depth(q))) 1105 depth(q) = depth(p); 1106 if (o != 0) { 1107 r = vlink(q); 1108 vlink(q) = null; 1109 q = hpack(q, 0, additional, -1); 1110 shift_amount(q) = o; 1111 subtype(q) = HLIST_SUBTYPE_ALIGNCELL; 1112 vlink(q) = r; 1113 vlink(s) = q; 1114 } 1115 } 1116 } 1117 s = q; 1118 q = vlink(q); 1119 } 1120 flush_node_list(p); 1121 pop_alignment(); 1122 /* Insert the current list into its environment */ 1123 /* We now have a completed alignment, in the list that starts at |cur_list.head_field| 1124 and ends at |cur_list.tail_field|. This list will be merged with the one that encloses 1125 it. (In case the enclosing mode is |mmode|, for displayed formulas, 1126 we will need to insert glue before and after the display; that part of the 1127 program will be deferred until we're more familiar with such operations.) 1128 */ 1129 pd = cur_list.prev_depth_field; 1130 p = vlink(cur_list.head_field); 1131 q = cur_list.tail_field; 1132 pop_nest(); 1133 if (cur_list.mode_field == mmode) { 1134 finish_display_alignment(p, q, pd); 1135 } else { 1136 cur_list.prev_depth_field = pd; /* aux:=aux_save; */ 1137 vlink(cur_list.tail_field) = p; 1138 if (p != null) 1139 cur_list.tail_field = q; 1140 if (cur_list.mode_field == vmode) { 1141 if (!output_active) 1142 // lua_node_filter_s(buildpage_filter_callback, "alignment"); 1143 lua_node_filter_s(buildpage_filter_callback,lua_key_index(alignment)); 1144 build_page(); 1145 } 1146 } 1147} 1148 1149 1150 1151@ The token list |omit_template| just referred to is a constant token 1152list that contains the special control sequence \.{\\endtemplate} only. 1153 1154@c 1155void initialize_alignments(void) 1156{ 1157 token_info(omit_template) = end_template_token; /* |link(omit_template)=null| */ 1158 span_span(end_span) = max_quarterword + 1; 1159 span_ptr(end_span) = null; 1160} 1161