1% postlinebreak.w 2% 3% Copyright 2006-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@ @c 21 22 23#include "ptexlib.h" 24 25@ So far we have gotten a little way into the |line_break| routine, having 26covered its important |try_break| subroutine. Now let's consider the 27rest of the process. 28 29The main loop of |line_break| traverses the given hlist, 30starting at |vlink(temp_head)|, and calls |try_break| at each legal 31breakpoint. A variable called |auto_breaking| is set to true except 32within math formulas, since glue nodes are not legal breakpoints when 33they appear in formulas. 34 35The current node of interest in the hlist is pointed to by |cur_p|. Another 36variable, |prev_p|, is usually one step behind |cur_p|, but the real 37meaning of |prev_p| is this: If |type(cur_p)=glue_node| then |cur_p| is a legal 38breakpoint if and only if |auto_breaking| is true and |prev_p| does not 39point to a glue node, penalty node, explicit kern node, or math node. 40 41@ The total number of lines that will be set by |post_line_break| 42is |best_line-prev_graf-1|. The last breakpoint is specified by 43|break_node(best_bet)|, and this passive node points to the other breakpoints 44via the |prev_break| links. The finishing-up phase starts by linking the 45relevant passive nodes in forward order, changing |prev_break| to 46|next_break|. (The |next_break| fields actually reside in the same memory 47space as the |prev_break| fields did, but we give them a new name because 48of their new significance.) Then the lines are justified, one by one. 49 50The |post_line_break| must also keep an dir stack, so that it can 51output end direction instructions at the ends of lines 52and begin direction instructions at the beginnings of lines. 53 54@c 55#define next_break prev_break /*new name for |prev_break| after links are reversed */ 56 57/* the ints are actually halfwords */ 58void ext_post_line_break(int paragraph_dir, 59 int right_skip, 60 int left_skip, 61 int pdf_protrude_chars, 62 halfword par_shape_ptr, 63 int pdf_adjust_spacing, 64 int pdf_each_line_height, 65 int pdf_each_line_depth, 66 int pdf_first_line_height, 67 int pdf_last_line_depth, 68 halfword inter_line_penalties_ptr, 69 int inter_line_penalty, 70 int club_penalty, 71 halfword club_penalties_ptr, 72 halfword widow_penalties_ptr, 73 int widow_penalty, 74 int broken_penalty, 75 halfword final_par_glue, 76 halfword best_bet, 77 halfword last_special_line, 78 scaled second_width, 79 scaled second_indent, 80 scaled first_width, 81 scaled first_indent, halfword best_line, 82 halfword pdf_ignored_dimen) 83{ 84 85 boolean have_directional = true; 86 halfword q, r; /* temporary registers for list manipulation */ 87 halfword k; 88 scaled w; 89 boolean glue_break; /* was a break at glue? */ 90 boolean disc_break; /*was the current break at a discretionary node? */ 91 boolean post_disc_break; /*and did it have a nonempty post-break part? */ 92 scaled cur_width; /*width of line number |cur_line| */ 93 scaled cur_indent; /*left margin of line number |cur_line| */ 94 int pen; /*use when calculating penalties between lines */ 95 halfword cur_p; /* |cur_p|, but localized */ 96 halfword cur_line; /*the current line number being justified */ 97 98 dir_ptr = cur_list.dirs_field; 99 /* Reverse the links of the relevant passive nodes, setting |cur_p| to 100 the first breakpoint; */ 101 /* The job of reversing links in a list is conveniently regarded as the job 102 of taking items off one stack and putting them on another. In this case we 103 take them off a stack pointed to by |q| and having |prev_break| fields; 104 we put them on a stack pointed to by |cur_p| and having |next_break| fields. 105 Node |r| is the passive node being moved from stack to stack. 106 */ 107 q = break_node(best_bet); 108#if 0 109 used_discs = used_disc(best_bet); 110#endif 111 /* |has_direction| */ 112 cur_p = null; 113 do { 114 r = q; 115 q = prev_break(q); 116 next_break(r) = cur_p; 117 cur_p = r; 118 } while (q != null); 119 /* |cur_p| is now the first breakpoint; */ 120 121 cur_line = cur_list.pg_field + 1; /* prevgraf+1 */ 122 123 do { 124 /* Justify the line ending at breakpoint |cur_p|, and append it to the 125 current vertical list, together with associated penalties and other 126 insertions; */ 127 /* The current line to be justified appears in a horizontal list starting 128 at |vlink(temp_head)| and ending at |cur_break(cur_p)|. If |cur_break(cur_p)| is 129 a glue node, we reset the glue to equal the |right_skip| glue; otherwise 130 we append the |right_skip| glue at the right. If |cur_break(cur_p)| is a 131 discretionary node, we modify the list so that the discretionary break 132 is compulsory, and we set |disc_break| to |true|. We also append 133 the |left_skip| glue at the left of the line, unless it is zero. */ 134 135#if 0 136 tprint("BEGIN OF LINE "); 137 print_int(cur_break(cur_p)); 138 breadth_max = 100000; 139 depth_threshold = 100000; 140 show_node_list(temp_head); 141#endif 142 143 /* DIR: Insert dir nodes at the beginning of the current line; */ 144 for (q = dir_ptr; q != null; q = vlink(q)) { 145 halfword tmp = new_dir(dir_dir(q)); 146 halfword nxt = vlink(temp_head); 147 delete_attribute_ref(node_attr(tmp)); 148 node_attr(tmp) = node_attr(temp_head); 149 add_node_attr_ref(node_attr(tmp)); 150 couple_nodes(temp_head, tmp); 151 try_couple_nodes(tmp, nxt); /* \.{\\break}\.{\\par} */ 152 } 153 if (dir_ptr != null) { 154 flush_node_list(dir_ptr); 155 dir_ptr = null; 156 } 157 158 /* Modify the end of the line to reflect the nature of the break and to 159 include \.{\\rightskip}; also set the proper value of |disc_break|; */ 160 /* At the end of the following code, |q| will point to the final node on the 161 list about to be justified. In the meanwhile |r| will point to the 162 node we will use to insert end-of-line stuff after. |q==null| means 163 we use the final position of |r| */ 164 r = cur_break(cur_p); 165 q = null; 166 disc_break = false; 167 post_disc_break = false; 168 glue_break = false; 169 170 if (r == null) { 171 for (r = temp_head; vlink(r) != null; r = vlink(r)); 172 if (r == final_par_glue) { 173 /* This should almost always be true... */ 174 /* TODO assert ? */ 175 q = r; 176 /* |q| refers to the last node of the line (and paragraph) */ 177 r = alink(r); 178 } 179 /* |r| refers to the node after which the dir nodes should be closed */ 180 } else if (type(r) == glue_node) { 181 delete_glue_ref(glue_ptr(r)); 182 glue_ptr(r) = right_skip; 183 subtype(r) = right_skip_code + 1; 184 incr(glue_ref_count(right_skip)); 185 glue_break = true; 186 /* |q| refers to the last node of the line */ 187 q = r; 188 r = alink(r); 189 assert(vlink(r) == q); 190 /* |r| refers to the node after which the dir nodes should be closed */ 191 } else if (type(r) == disc_node) { 192 halfword a = alink(r); 193 halfword v = vlink(r); 194 assert(a != null); 195 assert(v != null); 196 switch (subtype(r)) { 197 case select_disc: 198 if (vlink_pre_break(r) != null) { 199 flush_node_list(vlink_pre_break(r)); 200 vlink_pre_break(r) = null; 201 tlink_pre_break(r) = null; 202 } 203 if (vlink_no_break(r) != null) { 204 couple_nodes(a, vlink_no_break(r)); 205 couple_nodes(tlink_no_break(r), r); 206 vlink_no_break(r) = null; 207 tlink_no_break(r) = null; 208 } 209 210 assert(type(a) == disc_node && subtype(a) == init_disc); 211 flush_node_list(vlink_no_break(a)); 212 vlink_no_break(a) = null; 213 tlink_no_break(a) = null; 214 flush_node_list(vlink_pre_break(a)); 215 vlink_pre_break(a) = null; 216 tlink_pre_break(a) = null; 217 flush_node_list(vlink_post_break(a)); 218 vlink_post_break(a) = null; 219 tlink_post_break(a) = null; 220 221 break; 222 case init_disc: 223 assert(type(v) == disc_node && subtype(v) == select_disc); 224 subtype(v) = syllable_disc; /* not special any more */ 225 flush_node_list(vlink_no_break(v)); 226 vlink_no_break(v) = vlink_post_break(r); 227 tlink_no_break(v) = tlink_post_break(r); 228 vlink_post_break(r) = null; 229 tlink_post_break(r) = null; 230 default: 231 if (vlink_no_break(r) != null) { 232 flush_node_list(vlink_no_break(r)); 233 vlink_no_break(r) = null; 234 tlink_no_break(r) = null; 235 } 236 if (vlink_pre_break(r) != null) { 237 couple_nodes(a, vlink_pre_break(r)); 238 couple_nodes(tlink_pre_break(r), r); 239 vlink_pre_break(r) = null; 240 tlink_pre_break(r) = null; 241 } 242 } 243 if (vlink_post_break(r) != null) { 244 couple_nodes(r, vlink_post_break(r)); 245 couple_nodes(tlink_post_break(r), v); 246 vlink_post_break(r) = null; 247 tlink_post_break(r) = null; 248 post_disc_break = true; 249 } 250 disc_break = true; 251 } else if (type(r) == kern_node) { 252 width(r) = 0; 253 } else if (type(r) == math_node) { 254 surround(r) = 0; 255 } 256 257 /* DIR: Adjust the dir stack based on dir nodes in this line; */ 258 /* TODO what about the previousparagraph ??? */ 259 if (have_directional) { 260 halfword e; 261 halfword p; 262 for (e = vlink(temp_head); e != null && e != cur_break(cur_p); 263 e = vlink(e)) { 264 if (type(e) != whatsit_node || subtype(e) != dir_node) 265 continue; 266 if (dir_dir(e) >= 0) { 267 dir_ptr = do_push_dir_node(dir_ptr, e); 268 } else if (dir_ptr != null 269 && dir_dir(dir_ptr) == (dir_dir(e) + 64)) { 270 dir_ptr = do_pop_dir_node(dir_ptr); 271 } 272 } 273 assert(e == cur_break(cur_p)); 274 275 /* DIR: Insert dir nodes at the end of the current line; */ 276 e = vlink(r); 277 for (p = dir_ptr; p != null; p = vlink(p)) { 278 halfword s = new_dir(dir_dir(p) - 64); 279 delete_attribute_ref(node_attr(s)); 280 node_attr(s) = node_attr(r); 281 add_node_attr_ref(node_attr(s)); 282 couple_nodes(r, s); 283 try_couple_nodes(s, e); 284 r = s; 285 } 286 } 287 if (passive_right_box(cur_p) != null) { 288 /* TODO: CHECK has |s| below a |alink| ? */ 289 halfword s = copy_node_list(passive_right_box(cur_p)); 290 halfword e = vlink(r); 291 couple_nodes(r, s); 292 try_couple_nodes(s, e); 293 r = s; 294 } 295 if (q == null) { 296 q = r; 297 } 298 /* Now [q] refers to the last node on the line */ 299 300 /* FIXME from this point on we no longer keep alink() valid */ 301 302 /* at this point |q| is the rightmost breakpoint; the only exception is 303 the case of a discretionary break with non-empty |pre_break|, then |q| 304 has been changed to the last node of the |pre_break| list */ 305 /* If the par ends with a \break command, the last line is utterly empty. 306 That is the case of |q==temp_head| */ 307 if (q != temp_head && pdf_protrude_chars > 0) { 308 halfword p, ptmp; 309 if (disc_break && (is_char_node(q) || (type(q) != disc_node))) { 310 p = q; /* |q| has been reset to the last node of |pre_break| */ 311 ptmp = p; 312 } else { 313 p = alink(q); /* get |vlink(p) = q| */ 314 assert(vlink(p) == q); 315 ptmp = p; 316 } 317 p = find_protchar_right(vlink(temp_head), p); 318 w = char_pw(p, right_side); 319 if (w != 0) { /* we have found a marginal kern, append it after |ptmp| */ 320 k = new_margin_kern(-w, last_rightmost_char, right_side); 321 delete_attribute_ref(node_attr(k)); 322 node_attr(k) = node_attr(p); 323 add_node_attr_ref(node_attr(k)); 324 try_couple_nodes(k, vlink(ptmp)); 325 couple_nodes(ptmp,k); 326 if (ptmp == q) 327 q = vlink(q); 328 } 329 } 330 /* if |q| was not a breakpoint at glue and has been reset to |rightskip| 331 then we append |rightskip| after |q| now */ 332 if (!glue_break) { 333 /* Put the \.{\\rightskip} glue after node |q|; */ 334 halfword r1 = new_glue((right_skip == null ? null : copy_node(right_skip))); 335 glue_ref_count(glue_ptr(r1)) = null; 336 subtype(r1) = right_skip_code+1; 337 try_couple_nodes(r1,vlink(q)); 338 delete_attribute_ref(node_attr(r1)); 339 node_attr(r1) = node_attr(q); 340 add_node_attr_ref(node_attr(r1)); 341 couple_nodes(q,r1); 342 q = r1; 343 } 344 345 /* /Modify the end of the line to reflect the nature of the break and to 346 include \.{\\rightskip}; also set the proper value of |disc_break|; */ 347 348 /* Put the \.{\\leftskip} glue at the left and detach this line; */ 349 /* The following code begins with |q| at the end of the list to be 350 justified. It ends with |q| at the beginning of that list, and with 351 |vlink(temp_head)| pointing to the remainder of the paragraph, if any. */ 352 r = vlink(q); 353 vlink(q) = null; 354 355 q = vlink(temp_head); 356 try_couple_nodes(temp_head, r); 357 if (passive_left_box(cur_p) != null && passive_left_box(cur_p) != 0) { 358 /* omega bits: */ 359 halfword s; 360 r = copy_node_list(passive_left_box(cur_p)); 361 s = vlink(q); 362 couple_nodes(r,q); 363 q = r; 364 if ((cur_line == cur_list.pg_field + 1) && (s != null)) { 365 if (type(s) == hlist_node) { 366 if (list_ptr(s) == null) { 367 q = vlink(q); 368 try_couple_nodes(r,vlink(s)); 369 try_couple_nodes(s, r); 370 } 371 } 372 } 373 } 374 /*at this point |q| is the leftmost node; all discardable nodes have been discarded */ 375 if (pdf_protrude_chars > 0) { 376 halfword p; 377 p = q; 378 p = find_protchar_left(p, false); /* no more discardables */ 379 w = char_pw(p, left_side); 380 if (w != 0) { 381 k = new_margin_kern(-w, last_leftmost_char, left_side); 382 delete_attribute_ref(node_attr(k)); 383 node_attr(k) = node_attr(q); 384 add_node_attr_ref(node_attr(k)); 385 couple_nodes(k,q); 386 q = k; 387 } 388 } 389 if (left_skip != zero_glue) { 390 r = new_glue(copy_node(left_skip)); 391 glue_ref_count(glue_ptr(r)) = null; 392 subtype(r) = left_skip_code+1; 393 delete_attribute_ref(node_attr(r)); 394 node_attr(r) = node_attr(q); 395 add_node_attr_ref(node_attr(r)); 396 couple_nodes(r,q); 397 q = r; 398 } 399 /* /Put the \.{\\leftskip} glue at the left and detach this line; */ 400 401 /* Call the packaging subroutine, setting |just_box| to the justified box; */ 402 /* Now |q| points to the hlist that represents the current line of the 403 paragraph. We need to compute the appropriate line width, pack the 404 line into a box of this size, and shift the box by the appropriate 405 amount of indentation. */ 406 if (cur_line > last_special_line) { 407 cur_width = second_width; 408 cur_indent = second_indent; 409 } else if (par_shape_ptr == null) { 410 cur_width = first_width; 411 cur_indent = first_indent; 412 } else { 413 cur_indent = varmem[(par_shape_ptr + 2 * cur_line)].cint; 414 cur_width = varmem[(par_shape_ptr + 2 * cur_line + 1)].cint; 415 } 416 adjust_tail = adjust_head; 417 pre_adjust_tail = pre_adjust_head; 418 if (pdf_adjust_spacing > 0) { 419 just_box = hpack(q, cur_width, cal_expand_ratio, paragraph_dir); 420 } else { 421 just_box = hpack(q, cur_width, exactly, paragraph_dir); 422 } 423 shift_amount(just_box) = cur_indent; 424 subtype(just_box) = HLIST_SUBTYPE_LINE; 425 /* /Call the packaging subroutine, setting |just_box| to the justified box; */ 426 427 /* Append the new box to the current vertical list, followed by the list of 428 special nodes taken out of the box by the packager; */ 429 if (pdf_each_line_height != pdf_ignored_dimen) 430 height(just_box) = pdf_each_line_height; 431 if (pdf_each_line_depth != pdf_ignored_dimen) 432 depth(just_box) = pdf_each_line_depth; 433 if ((pdf_first_line_height != pdf_ignored_dimen) 434 && (cur_line == cur_list.pg_field + 1)) 435 height(just_box) = pdf_first_line_height; 436 if ((pdf_last_line_depth != pdf_ignored_dimen) 437 && (cur_line + 1 == best_line)) 438 depth(just_box) = pdf_last_line_depth; 439 440 if ((vlink(contrib_head) != null)) 441 if (!output_active) 442 lua_node_filter_s(buildpage_filter_callback, lua_key_index(pre_box)); 443 if (pre_adjust_head != pre_adjust_tail) { 444 append_list(pre_adjust_head, pre_adjust_tail); 445 if (!output_active) 446 lua_node_filter_s(buildpage_filter_callback, lua_key_index(pre_adjust)); 447 } 448 pre_adjust_tail = null; 449 append_to_vlist(just_box); 450 if (!output_active) 451 lua_node_filter_s(buildpage_filter_callback, lua_key_index(box)); 452 if (adjust_head != adjust_tail) { 453 append_list(adjust_head, adjust_tail); 454 if (!output_active) 455 lua_node_filter_s(buildpage_filter_callback, lua_key_index(adjust)); 456 } 457 adjust_tail = null; 458 459 /* /Append the new box to the current vertical list, followed by the list of 460 special nodes taken out of the box by the packager; */ 461 462 /* Append a penalty node, if a nonzero penalty is appropriate */ 463 /* Penalties between the lines of a paragraph come from club and widow lines, 464 from the |inter_line_penalty| parameter, and from lines that end at 465 discretionary breaks. Breaking between lines of a two-line paragraph gets 466 both club-line and widow-line penalties. The local variable |pen| will 467 be set to the sum of all relevant penalties for the current line, except 468 that the final line is never penalized. */ 469 if (cur_line + 1 != best_line) { 470 q = inter_line_penalties_ptr; 471 if (q != null) { 472 r = cur_line; 473 if (r > penalty(q)) 474 r = penalty(q); 475 pen = penalty(q + r); 476 } else { 477 if (passive_pen_inter(cur_p) != 0) { 478 pen = passive_pen_inter(cur_p); 479 } else { 480 pen = inter_line_penalty; 481 } 482 } 483 q = club_penalties_ptr; 484 if (q != null) { 485 r = cur_line - cur_list.pg_field; /* prevgraf */ 486 if (r > penalty(q)) 487 r = penalty(q); 488 pen += penalty(q + r); 489 } else if (cur_line == cur_list.pg_field + 1) { /* prevgraf */ 490 pen += club_penalty; 491 } 492 q = widow_penalties_ptr; 493 if (q != null) { 494 r = best_line - cur_line - 1; 495 if (r > penalty(q)) 496 r = penalty(q); 497 pen += penalty(q + r); 498 } else if (cur_line + 2 == best_line) { 499 pen += widow_penalty; 500 } 501 if (disc_break) { 502 if (passive_pen_broken(cur_p) != 0) { 503 pen += passive_pen_broken(cur_p); 504 } else { 505 pen += broken_penalty; 506 } 507 } 508 if (pen != 0) { 509 r = new_penalty(pen); 510 couple_nodes(cur_list.tail_field, r); 511 cur_list.tail_field = r; 512 } 513 } 514 /* /Append a penalty node, if a nonzero penalty is appropriate */ 515 516 /* /Justify the line ending at breakpoint |cur_p|, and append it to the 517 current vertical list, together with associated penalties and other 518 insertions; */ 519 incr(cur_line); 520 cur_p = next_break(cur_p); 521 if (cur_p != null && !post_disc_break) { 522 /* Prune unwanted nodes at the beginning of the next line; */ 523 /* Glue and penalty and kern and math nodes are deleted at the 524 beginning of a line, except in the anomalous case that the 525 node to be deleted is actually one of the chosen 526 breakpoints. Otherwise the pruning done here is designed to 527 match the lookahead computation in |try_break|, where the 528 |break_width| values are computed for non-discretionary 529 breakpoints. */ 530 r = temp_head; 531 if (experimental_code[1]) { 532 /* hh-ls: This is a first step to improving symmetry and consistency in the node 533 list. This is normally no issue in tex, but in callbacks it matters. */ 534 535 /* Normally we have a matching math open and math close node but when we cross a line 536 the open node is removed, including any glue or penalties following it. This is however 537 not that nice for callbacks that rely on symmetry. Of course this only counts for one 538 liners, as we can still have only a begin or end node on a line. The end_of_math lua 539 helper is made robust against this although there you should be aware of the fact that 540 one can end up in the middle of math in callbacks that don't work on whole paragraphs, 541 but at least this branch makes sure that some proper analysis is possible. (todo: check 542 if math glyphs have the subtype marked done). */ 543 544 halfword m = null ; 545 halfword mp, mn, rn ; 546 while (1) { 547 q = vlink(r); 548 if (! q) { 549 /* unlikely */ 550 break; 551 } else if (q == cur_break(cur_p)) { 552 /* quit */ 553 break; 554 } else if (type(q) == glyph_node) { 555 /* quit: is > math_code */ 556 break; 557 } else if (type(q) == math_node) { 558 /* we want to keep symmetry */ 559 surround(q) = 0 ; 560 // fprintf(stdout,"KEEP MATH NODE\n"); 561 m = q ; 562 } else if (type(q) == kern_node && subtype(q) != explicit) { 563 /* quit: so we keep \kern but also auto kerns */ 564 break; 565 } if (non_discardable(q)) { 566 /* quit: < math_node */ 567 break; 568 } else { 569 /* skip: glue, penalty, (font)kern, noads, temp stuff, all kind of left-overs */ 570 } 571 r = q; 572 } 573 if (m != null) { 574 if (r == m) { 575 /* [a] [b] [m=r] => [a] [b=r] */ 576 r = alink(m) ; 577 } else { 578 /* [a] [b] [m] [c] [r] [rn] => [a] [b] [c] [r] [m] [rn] */ 579 mp = alink(m) ; 580 mn = vlink(m) ; 581 rn = vlink(r) ; 582 vlink(r) = m ; 583 alink(m) = r ; 584 if (rn) { 585 alink(rn) = m ; 586 vlink(m) = rn ; 587 } 588 vlink(mp) = mn ; 589 alink(mn) = mp ; 590 } 591 } 592 } else { 593 while (1) { 594 q = vlink(r); 595 if (q == cur_break(cur_p) || is_char_node(q)) 596 break; 597 if (!((type(q) == whatsit_node) && (subtype(q) == local_par_node))) { 598 if (non_discardable(q) || (type(q) == kern_node && subtype(q) != explicit)) 599 break; 600 } 601 r = q; 602 } 603 } 604 if (r != temp_head) { 605 vlink(r) = null; 606 flush_node_list(vlink(temp_head)); 607 try_couple_nodes(temp_head, q); 608 } 609 } 610 } while (cur_p != null); 611 if ((cur_line != best_line) || (vlink(temp_head) != null)) 612 confusion("line breaking"); 613 cur_list.pg_field = best_line - 1; /* prevgraf */ 614 cur_list.dirs_field = dir_ptr; /* |dir_save| */ 615 dir_ptr = null; 616} 617