1% linebreak.w 2% 3% Copyright 2006-2008 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 26@ We come now to what is probably the most interesting algorithm of \TeX: 27the mechanism for choosing the ``best possible'' breakpoints that yield 28the individual lines of a paragraph. \TeX's line-breaking algorithm takes 29a given horizontal list and converts it to a sequence of boxes that are 30appended to the current vertical list. In the course of doing this, it 31creates a special data structure containing three kinds of records that are 32not used elsewhere in \TeX. Such nodes are created while a paragraph is 33being processed, and they are destroyed afterwards; thus, the other parts 34of \TeX\ do not need to know anything about how line-breaking is done. 35 36The method used here is based on an approach devised by Michael F. Plass and 37@^Plass, Michael Frederick@> 38@^Knuth, Donald Ervin@> 39the author in 1977, subsequently generalized and improved by the same two 40people in 1980. A detailed discussion appears in {\sl SOFTWARE---Practice 41\AM\ Experience \bf11} (1981), 1119--1184, where it is shown that the 42line-breaking problem can be regarded as a special case of the problem of 43computing the shortest path in an acyclic network. The cited paper includes 44numerous examples and describes the history of line breaking as it has been 45practiced by printers through the ages. The present implementation adds two 46new ideas to the algorithm of 1980: Memory space requirements are considerably 47reduced by using smaller records for inactive nodes than for active ones, 48and arithmetic overflow is avoided by using ``delta distances'' instead of 49keeping track of the total distance from the beginning of the paragraph to the 50current point. 51 52The |line_break| procedure should be invoked only in horizontal mode; it 53leaves that mode and places its output into the current vlist of the 54enclosing vertical mode (or internal vertical mode). 55There is one explicit parameter: |d| is true for partial paragraphs 56preceding display math mode; in this case the amount of additional 57penalty inserted before the final line is |display_widow_penalty| 58instead of |widow_penalty|. 59 60There are also a number of implicit parameters: The hlist to be broken 61starts at |vlink(head)|, and it is nonempty. The value of |prev_graf| in the 62enclosing semantic level tells where the paragraph should begin in the 63sequence of line numbers, in case hanging indentation or \.{\\parshape} 64are in use; |prev_graf| is zero unless this paragraph is being continued 65after a displayed formula. Other implicit parameters, such as the 66|par_shape_ptr| and various penalties to use for hyphenation, etc., appear 67in |eqtb|. 68 69After |line_break| has acted, it will have updated the current vlist and the 70value of |prev_graf|. Furthermore, the global variable |just_box| will 71point to the final box created by |line_break|, so that the width of this 72line can be ascertained when it is necessary to decide whether to use 73|above_display_skip| or |above_display_short_skip| before a displayed formula. 74 75@c 76halfword just_box; /* the |hlist_node| for the last line of the new paragraph */ 77 78 79@ In it's complete form, |line_break| is a rather lengthy 80procedure---sort of a small world unto itself---we must build it up 81little by little. Below you see only the general outline. 82 83The main task performed here is to move the list from |head| to 84|temp_head| and go into the enclosing semantic level. We also append 85the \.{\\parfillskip} glue to the end of the paragraph, removing a 86space (or other glue node) if it was there, since spaces usually 87precede blank lines and instances of `\.{\$\$}'. The |par_fill_skip| 88is preceded by an infinite penalty, so it will never be considered as 89a potential breakpoint. 90 91That code assumes that a |glue_node| and a |penalty_node| occupy the 92same number of |mem|~words. 93@^data structure assumptions@> 94 95Most other processing is delegated to external functions. 96 97@c 98void line_break(boolean d, int line_break_context) 99{ 100 int paragraph_dir = 0; /* main direction of paragraph */ 101 halfword final_par_glue; 102 halfword start_of_par; 103 int callback_id; 104 pack_begin_line = cur_list.ml_field; /* this is for over/underfull box messages */ 105 alink(temp_head) = null; /* hh-ls */ 106 vlink(temp_head) = vlink(cur_list.head_field); 107 new_hyphenation(temp_head, cur_list.tail_field); 108 cur_list.tail_field = new_ligkern(temp_head, cur_list.tail_field); 109 if (is_char_node(cur_list.tail_field)) { 110 tail_append(new_penalty(inf_penalty)); 111 } else if (type(cur_list.tail_field) != glue_node) { 112 tail_append(new_penalty(inf_penalty)); 113 } else { 114 type(cur_list.tail_field) = penalty_node; 115 delete_glue_ref(glue_ptr(cur_list.tail_field)); 116 if (leader_ptr(cur_list.tail_field) != null) 117 flush_node_list(leader_ptr(cur_list.tail_field)); 118 penalty(cur_list.tail_field) = inf_penalty; 119 } 120 final_par_glue = new_param_glue(par_fill_skip_code); 121 couple_nodes(cur_list.tail_field, final_par_glue); 122 cur_list.tail_field = vlink(cur_list.tail_field); 123#ifdef DEBUG 124 { 125 int n = temp_head; 126 fprintf(stdout, "pre_linebreak_filter status:\n"); 127 while (n) { 128 fprintf(stdout, " %s node %d\n", 129 get_node_name(type(n), subtype(n)), (int) n); 130 n = vlink(n); 131 } 132 } 133#endif 134 lua_node_filter(pre_linebreak_filter_callback, 135 line_break_context, temp_head, 136 addressof(cur_list.tail_field)); 137 last_line_fill = cur_list.tail_field; 138 pop_nest(); 139 start_of_par = cur_list.tail_field; 140#ifdef DEBUG 141 { 142 int n = temp_head; 143 fprintf(stdout, "pre_linebreak_filter returned:\n"); 144 while (n) { 145 fprintf(stdout, " %s node %d\n", 146 get_node_name(type(n), subtype(n)), (int) n); 147 n = vlink(n); 148 } 149 } 150#endif 151 callback_id = callback_defined(linebreak_filter_callback); 152 if (callback_id > 0) { 153 callback_id = 154 lua_linebreak_callback(d, temp_head, 155 addressof(cur_list.tail_field)); 156 if (callback_id > 0) { 157 /* find the correct value for the |just_box| */ 158 halfword box_search = cur_list.tail_field; 159 just_box = null; 160 if (box_search != null) { 161 do { 162 if (type(box_search) == hlist_node) { 163 just_box = box_search; 164 } 165 box_search = vlink(box_search); 166 } while (box_search != null); 167 } 168 if (just_box == null) { 169 help3 170 ("A linebreaking routine should return a non-empty list of nodes", 171 "and at least one of those has to be a \\hbox.", 172 "Sorry, I cannot recover from this."); 173 print_err("Invalid linebreak_filter"); 174 succumb(); 175 } 176 } else { 177 if (int_par(tracing_paragraphs_code) > 0) { 178 begin_diagnostic(); 179 tprint_nl 180 ("Lua linebreak_filter failed, reverting to default on line "); 181 print_int(line); 182 end_diagnostic(true); 183 } 184 } 185 } 186 if (callback_id == 0) { 187 if ((!is_char_node(vlink(temp_head))) 188 && ((type(vlink(temp_head)) == whatsit_node) 189 && (subtype(vlink(temp_head)) == local_par_node))) 190 paragraph_dir = local_par_dir(vlink(temp_head)); 191 else 192 assert(0); /* |paragraph_dir = 0|; */ 193 ext_do_line_break(paragraph_dir, 194 int_par(pretolerance_code), 195 int_par(tracing_paragraphs_code), 196 int_par(tolerance_code), 197 dimen_par(emergency_stretch_code), 198 int_par(looseness_code), 199 int_par(hyphen_penalty_code), 200 int_par(ex_hyphen_penalty_code), 201 int_par(pdf_adjust_spacing_code), 202 equiv(par_shape_loc), 203 int_par(adj_demerits_code), 204 int_par(pdf_protrude_chars_code), 205 int_par(line_penalty_code), 206 int_par(last_line_fit_code), 207 int_par(double_hyphen_demerits_code), 208 int_par(final_hyphen_demerits_code), 209 dimen_par(hang_indent_code), 210 dimen_par(hsize_code), 211 int_par(hang_after_code), 212 glue_par(left_skip_code), 213 glue_par(right_skip_code), 214 dimen_par(pdf_each_line_height_code), 215 dimen_par(pdf_each_line_depth_code), 216 dimen_par(pdf_first_line_height_code), 217 dimen_par(pdf_last_line_depth_code), 218 equiv(inter_line_penalties_loc), 219 int_par(inter_line_penalty_code), 220 int_par(club_penalty_code), 221 equiv(club_penalties_loc), 222 (d ? equiv(display_widow_penalties_loc) : equiv(widow_penalties_loc)), 223 (d ? int_par(display_widow_penalty_code) : int_par(widow_penalty_code)), 224 int_par(broken_penalty_code), 225 final_par_glue, dimen_par(pdf_ignored_dimen_code)); 226 } 227 lua_node_filter(post_linebreak_filter_callback, 228 line_break_context, start_of_par, 229 addressof(cur_list.tail_field)); 230 pack_begin_line = 0; 231} 232 233 234@ Glue nodes in a horizontal list that is being paragraphed are not supposed to 235 include ``infinite'' shrinkability; that is why the algorithm maintains 236 four registers for stretching but only one for shrinking. If the user tries to 237 introduce infinite shrinkability, the shrinkability will be reset to finite 238 and an error message will be issued. A boolean variable |no_shrink_error_yet| 239 prevents this error message from appearing more than once per paragraph. 240 241@c 242#define check_shrinkage(a) \ 243 if ((shrink_order((a))!=normal)&&(shrink((a))!=0)) \ 244 a=finite_shrink((a)) 245 246static boolean no_shrink_error_yet; /*have we complained about infinite shrinkage? */ 247 248static halfword finite_shrink(halfword p) 249{ /* recovers from infinite shrinkage */ 250 halfword q; /*new glue specification */ 251 const char *hlp[] = { 252 "The paragraph just ended includes some glue that has", 253 "infinite shrinkability, e.g., `\\hskip 0pt minus 1fil'.", 254 "Such glue doesn't belong there---it allows a paragraph", 255 "of any length to fit on one line. But it's safe to proceed,", 256 "since the offensive shrinkability has been made finite.", 257 NULL 258 }; 259 if (no_shrink_error_yet) { 260 no_shrink_error_yet = false; 261 tex_error("Infinite glue shrinkage found in a paragraph", hlp); 262 } 263 q = new_spec(p); 264 shrink_order(q) = normal; 265 delete_glue_ref(p); 266 return q; 267} 268 269@ A pointer variable |cur_p| runs through the given horizontal list as we look 270 for breakpoints. This variable is global, since it is used both by |line_break| 271 and by its subprocedure |try_break|. 272 273 Another global variable called |threshold| is used to determine the feasibility 274 of individual lines: breakpoints are feasible if there is a way to reach 275 them without creating lines whose badness exceeds |threshold|. (The 276 badness is compared to |threshold| before penalties are added, so that 277 penalty values do not affect the feasibility of breakpoints, except that 278 no break is allowed when the penalty is 10000 or more.) If |threshold| 279 is 10000 or more, all legal breaks are considered feasible, since the 280 |badness| function specified above never returns a value greater than~10000. 281 282 Up to three passes might be made through the paragraph in an attempt to find at 283 least one set of feasible breakpoints. On the first pass, we have 284 |threshold=pretolerance| and |second_pass=final_pass=false|. 285 If this pass fails to find a 286 feasible solution, |threshold| is set to |tolerance|, |second_pass| is set 287 |true|, and an attempt is made to hyphenate as many words as possible. 288 If that fails too, we add |emergency_stretch| to the background 289 stretchability and set |final_pass=true|. 290 291@c 292static boolean second_pass; /* is this our second attempt to break this paragraph? */ 293static boolean final_pass; /*is this our final attempt to break this paragraph? */ 294static int threshold; /* maximum badness on feasible lines */ 295 296/* maximum fill level for |hlist_stack|*/ 297#define max_hlist_stack 512 /* maybe good if larger than |2 * 298 max_quarterword|, so that box nesting 299 level would overflow first */ 300 301/* stack for |find_protchar_left()| and |find_protchar_right()| */ 302static halfword hlist_stack[max_hlist_stack]; 303 304/* fill level for |hlist_stack| */ 305static short hlist_stack_level = 0; 306 307@ @c 308static void push_node(halfword p) 309{ 310 if (hlist_stack_level >= max_hlist_stack) 311 pdf_error("push_node", "stack overflow"); 312 hlist_stack[hlist_stack_level++] = p; 313} 314 315static halfword pop_node(void) 316{ 317 if (hlist_stack_level <= 0) /* would point to some bug */ 318 pdf_error("pop_node", "stack underflow (internal error)"); 319 return hlist_stack[--hlist_stack_level]; 320} 321 322@ @c 323static int max_stretch_ratio = 0; /*maximal stretch ratio of expanded fonts */ 324static int max_shrink_ratio = 0; /*maximal shrink ratio of expanded fonts */ 325static int cur_font_step = 0; /*the current step of expanded fonts */ 326 327 328static boolean check_expand_pars(internal_font_number f) 329{ 330 int m; 331 332 if ((font_step(f) == 0) 333 || ((font_max_stretch(f) == 0) && (font_max_shrink(f) == 0))) 334 return false; 335 if (cur_font_step < 0) 336 cur_font_step = font_step(f); 337 else if (cur_font_step != font_step(f)) 338 pdf_error("font expansion", 339 "using fonts with different step of expansion in one paragraph is not allowed"); 340 m = font_max_stretch(f); 341 if (m != 0) { 342 if (max_stretch_ratio < 0) 343 max_stretch_ratio = m; 344 else if (max_stretch_ratio != m) 345 pdf_error("font expansion", 346 "using fonts with different limit of expansion in one paragraph is not allowed"); 347 } 348 m = font_max_shrink(f); 349 if (m != 0) { 350 if (max_shrink_ratio < 0) 351 max_shrink_ratio = -m; 352 else if (max_shrink_ratio != -m) 353 pdf_error("font expansion", 354 "using fonts with different limit of expansion in one paragraph is not allowed"); 355 } 356 return true; 357} 358 359@ searches left to right from list head |l|, returns 1st non-skipable item 360 361@c 362/*public*/ halfword find_protchar_left(halfword l, boolean d) 363{ 364 halfword t; 365 boolean run; 366 if ((vlink(l) != null) && (type(l) == hlist_node) && (width(l) == 0) 367 && (height(l) == 0) && (depth(l) == 0) && (list_ptr(l) == null)) { 368 l = vlink(l); /*for paragraph start with \.{\\parindent} = 0pt */ 369 } else if (d) { 370 while ((vlink(l) != null) && (!(is_char_node(l) || non_discardable(l)))) { 371 l = vlink(l); /* std.\ discardables at line break, \TeX book, p 95 */ 372 } 373 } 374 hlist_stack_level = 0; 375 run = true; 376 do { 377 t = l; 378 while (run && (type(l) == hlist_node) && (list_ptr(l) != null)) { 379 push_node(l); 380 l = list_ptr(l); 381 } 382 while (run && cp_skipable(l)) { 383 while ((vlink(l) == null) && (hlist_stack_level > 0)) { 384 l = pop_node(); /* don't visit this node again */ 385 run = false; 386 } 387 if (vlink(l) != null) 388 l = vlink(l); 389 else if (hlist_stack_level == 0) 390 run = false; 391 } 392 } while (t != l); 393 return l; 394} 395 396 397@ searches right to left from list tail |r| to head |l|, returns 1st non-skipable item 398 399@c 400/*public*/ halfword find_protchar_right(halfword l, halfword r) 401{ 402 halfword t; 403 boolean run; 404 if (r == null) 405 return null; 406 hlist_stack_level = 0; 407 run = true; 408 do { 409 t = r; 410 while (run && (type(r) == hlist_node) && (list_ptr(r) != null)) { 411 push_node(l); 412 push_node(r); 413 l = list_ptr(r); 414 r = l; 415 while (vlink(r) != null) { 416 halfword s = r; 417 r = vlink(r); 418 alink(r) = s; 419 } 420 } 421 while (run && cp_skipable(r)) { 422 while ((r == l) && (hlist_stack_level > 0)) { 423 r = pop_node(); /* don't visit this node again */ 424 l = pop_node(); 425 } 426 if ((r != l) && (r != null)) { 427 if (alink(r) != null) { 428 assert(vlink(alink(r)) == r); 429 r = alink(r); 430 } else { /* this is the input: \.{\\leavevmode\\penalty-10000\\penalty-10000} (bug \#268) */ 431 run = false; 432 } 433 } else if ((r == l) && (hlist_stack_level == 0)) 434 run = false; 435 } 436 } while (t != r); 437 return r; 438} 439 440@ @c 441#define left_pw(a) char_pw((a), left_side) 442#define right_pw(a) char_pw((a), right_side) 443 444@ When looking for optimal line breaks, \TeX\ creates a ``break node'' for 445 each break that is {\sl feasible}, in the sense that there is a way to end 446 a line at the given place without requiring any line to stretch more than 447 a given tolerance. A break node is characterized by three things: the position 448 of the break (which is a pointer to a |glue_node|, |math_node|, |penalty_node|, 449 or |disc_node|); the ordinal number of the line that will follow this 450 breakpoint; and the fitness classification of the line that has just 451 ended, i.e., |tight_fit|, |decent_fit|, |loose_fit|, or |very_loose_fit|. 452 453@c 454typedef enum { 455 very_loose_fit = 0, /* fitness classification for lines stretching more than 456 their stretchability */ 457 loose_fit, /* fitness classification for lines stretching 0.5 to 1.0 of their 458 stretchability */ 459 decent_fit, /* fitness classification for all other lines */ 460 tight_fit /* fitness classification for lines shrinking 0.5 to 1.0 of their 461 shrinkability */ 462} fitness_value; 463 464 465@ The algorithm essentially determines the best possible way to achieve 466 each feasible combination of position, line, and fitness. Thus, it answers 467 questions like, ``What is the best way to break the opening part of the 468 paragraph so that the fourth line is a tight line ending at such-and-such 469 a place?'' However, the fact that all lines are to be the same length 470 after a certain point makes it possible to regard all sufficiently large 471 line numbers as equivalent, when the looseness parameter is zero, and this 472 makes it possible for the algorithm to save space and time. 473 474 An ``active node'' and a ``passive node'' are created in |mem| for each 475 feasible breakpoint that needs to be considered. Active nodes are three 476 words long and passive nodes are two words long. We need active nodes only 477 for breakpoints near the place in the paragraph that is currently being 478 examined, so they are recycled within a comparatively short time after 479 they are created. 480 481@ An active node for a given breakpoint contains six fields: 482 483|vlink| points to the next node in the list of active nodes; the 484last active node has |vlink=active|. 485 486|break_node| points to the passive node associated with this 487breakpoint. 488 489|line_number| is the number of the line that follows this 490breakpoint. 491 492|fitness| is the fitness classification of the line ending at this 493breakpoint. 494 495|type| is either |hyphenated_node| or |unhyphenated_node|, depending on 496whether this breakpoint is a |disc_node|. 497 498|total_demerits| is the minimum possible sum of demerits over all 499lines leading from the beginning of the paragraph to this breakpoint. 500 501The value of |vlink(active)| points to the first active node on a vlinked list 502of all currently active nodes. This list is in order by |line_number|, 503except that nodes with |line_number>easy_line| may be in any order relative 504to each other. 505 506@c 507void initialize_active(void) 508{ 509 type(active) = hyphenated_node; 510 line_number(active) = max_halfword; 511 subtype(active) = 0; /* the |subtype| is never examined */ 512} 513 514@ The passive node for a given breakpoint contains EIGHT fields: 515 516|vlink| points to the passive node created just before this one, 517if any, otherwise it is |null|. 518 519|cur_break| points to the position of this breakpoint in the 520horizontal list for the paragraph being broken. 521 522|prev_break| points to the passive node that should precede this 523one in an optimal path to this breakpoint. 524 525|serial| is equal to |n| if this passive node is the |n|th 526one created during the current pass. (This field is used only when 527printing out detailed statistics about the line-breaking calculations.) 528 529|passive_pen_inter| holds the current \.{\\localinterlinepenalty} 530 531|passive_pen_broken| holds the current \.{\\localbrokenpenalty} 532 533There is a global variable called |passive| that points to the most 534recently created passive node. Another global variable, |printed_node|, 535is used to help print out the paragraph when detailed information about 536the line-breaking computation is being displayed. 537 538@c 539static halfword passive; /* most recent node on passive list */ 540static halfword printed_node; /*most recent node that has been printed */ 541static halfword pass_number; /*the number of passive nodes allocated on this pass */ 542 543 544@ The active list also contains ``delta'' nodes that help the algorithm 545compute the badness of individual lines. Such nodes appear only between two 546active nodes, and they have |type=delta_node|. If |p| and |r| are active nodes 547and if |q| is a delta node between them, so that |vlink(p)=q| and |vlink(q)=r|, 548then |q| tells the space difference between lines in the horizontal list that 549start after breakpoint |p| and lines that start after breakpoint |r|. In 550other words, if we know the length of the line that starts after |p| and 551ends at our current position, then the corresponding length of the line that 552starts after |r| is obtained by adding the amounts in node~|q|. A delta node 553contains seven scaled numbers, since it must record the net change in glue 554stretchability with respect to all orders of infinity. The natural width 555difference appears in |mem[q+1].sc|; the stretch differences in units of 556pt, sfi, fil, fill, and filll appear in |mem[q+2..q+6].sc|; and the shrink 557difference appears in |mem[q+7].sc|. The |subtype| field of a delta node 558is not used. 559 560Actually, we have two more fields that are used by |pdftex|. 561 562 563As the algorithm runs, it maintains a set of seven delta-like registers 564for the length of the line following the first active breakpoint to the 565current position in the given hlist. When it makes a pass through the 566active list, it also maintains a similar set of seven registers for the 567length following the active breakpoint of current interest. A third set 568holds the length of an empty line (namely, the sum of \.{\\leftskip} and 569\.{\\rightskip}); and a fourth set is used to create new delta nodes. 570 571When we pass a delta node we want to do operations like 572$$\hbox{\ignorespaces|for 573k:=1 to 7 do cur_active_width[k]:=cur_active_width[k]+mem[q+k].sc|};$$ and we 574want to do this without the overhead of |for| loops. The |do_all_six| 575macro makes such six-tuples convenient. 576 577@c 578static scaled active_width[10] = { 0 }; /*distance from first active node to~|cur_p| */ 579static scaled background[10] = { 0 }; /*length of an ``empty'' line */ 580static scaled break_width[10] = { 0 }; /*length being computed after current break */ 581 582static boolean auto_breaking; /*make |auto_breaking| accessible out of |line_break| */ 583 584@ Let's state the principles of the delta nodes more precisely and concisely, 585 so that the following programs will be less obscure. For each legal 586 breakpoint~|p| in the paragraph, we define two quantities $\alpha(p)$ and 587 $\beta(p)$ such that the length of material in a line from breakpoint~|p| 588 to breakpoint~|q| is $\gamma+\beta(q)-\alpha(p)$, for some fixed $\gamma$. 589 Intuitively, $\alpha(p)$ and $\beta(q)$ are the total length of material from 590 the beginning of the paragraph to a point ``after'' a break at |p| and to a 591 point ``before'' a break at |q|; and $\gamma$ is the width of an empty line, 592 namely the length contributed by \.{\\leftskip} and \.{\\rightskip}. 593 594 Suppose, for example, that the paragraph consists entirely of alternating 595 boxes and glue skips; let the boxes have widths $x_1\ldots x_n$ and 596 let the skips have widths $y_1\ldots y_n$, so that the paragraph can be 597 represented by $x_1y_1\ldots x_ny_n$. Let $p_i$ be the legal breakpoint 598 at $y_i$; then $\alpha(p_i)=x_1+y_1+\cdots+x_i+y_i$, and $\beta(p_i)= 599 x_1+y_1+\cdots+x_i$. To check this, note that the length of material from 600 $p_2$ to $p_5$, say, is $\gamma+x_3+y_3+x_4+y_4+x_5=\gamma+\beta(p_5) 601 -\alpha(p_2)$. 602 603 The quantities $\alpha$, $\beta$, $\gamma$ involve glue stretchability and 604 shrinkability as well as a natural width. If we were to compute $\alpha(p)$ 605 and $\beta(p)$ for each |p|, we would need multiple precision arithmetic, and 606 the multiprecise numbers would have to be kept in the active nodes. 607 \TeX\ avoids this problem by working entirely with relative differences 608 or ``deltas.'' Suppose, for example, that the active list contains 609 $a_1\,\delta_1\,a_2\,\delta_2\,a_3$, where the |a|'s are active breakpoints 610 and the $\delta$'s are delta nodes. Then $\delta_1=\alpha(a_1)-\alpha(a_2)$ 611 and $\delta_2=\alpha(a_2)-\alpha(a_3)$. If the line breaking algorithm is 612 currently positioned at some other breakpoint |p|, the |active_width| array 613 contains the value $\gamma+\beta(p)-\alpha(a_1)$. If we are scanning through 614 the list of active nodes and considering a tentative line that runs from 615 $a_2$ to~|p|, say, the |cur_active_width| array will contain the value 616 $\gamma+\beta(p)-\alpha(a_2)$. Thus, when we move from $a_2$ to $a_3$, 617 we want to add $\alpha(a_2)-\alpha(a_3)$ to |cur_active_width|; and this 618 is just $\delta_2$, which appears in the active list between $a_2$ and 619 $a_3$. The |background| array contains $\gamma$. The |break_width| array 620 will be used to calculate values of new delta nodes when the active 621 list is being updated. 622 623 624@ The heart of the line-breaking procedure is `|try_break|', a subroutine 625 that tests if the current breakpoint |cur_p| is feasible, by running 626 through the active list to see what lines of text can be made from active 627 nodes to~|cur_p|. If feasible breaks are possible, new break nodes are 628 created. If |cur_p| is too far from an active node, that node is 629 deactivated. 630 631 The parameter |pi| to |try_break| is the penalty associated 632 with a break at |cur_p|; we have |pi=eject_penalty| if the break is forced, 633 and |pi=inf_penalty| if the break is illegal. 634 635 The other parameter, |break_type|, is set to |hyphenated_node| or |unhyphenated_node|, 636 depending on whether or not the current break is at a |disc_node|. The 637 end of a paragraph is also regarded as `|hyphenated_node|'; this case is 638 distinguishable by the condition |cur_p=null|. 639 640 641@c 642static int internal_pen_inter; /* running \.{\\localinterlinepenalty} */ 643static int internal_pen_broken; /* running \.{\\localbrokenpenalty} */ 644static halfword internal_left_box; /* running \.{\\localleftbox} */ 645static int internal_left_box_width; /* running \.{\\localleftbox} width */ 646static halfword init_internal_left_box; /* running \.{\\localleftbox} */ 647static int init_internal_left_box_width; /* running \.{\\localleftbox} width */ 648static halfword internal_right_box; /* running \.{\\localrightbox} */ 649static int internal_right_box_width; /* running \.{\\localrightbox} width */ 650 651static scaled disc_width[10] = { 0 }; /* the length of discretionary material preceding a break */ 652 653@ As we consider various ways to end a line at |cur_p|, in a given line number 654 class, we keep track of the best total demerits known, in an array with 655 one entry for each of the fitness classifications. For example, 656 |minimal_demerits[tight_fit]| contains the fewest total demerits of feasible 657 line breaks ending at |cur_p| with a |tight_fit| line; |best_place[tight_fit]| 658 points to the passive node for the break before~|cur_p| that achieves such 659 an optimum; and |best_pl_line[tight_fit]| is the |line_number| field in the 660 active node corresponding to |best_place[tight_fit]|. When no feasible break 661 sequence is known, the |minimal_demerits| entries will be equal to 662 |awful_bad|, which is $2^{30}-1$. Another variable, |minimum_demerits|, 663 keeps track of the smallest value in the |minimal_demerits| array. 664 665@c 666static int minimal_demerits[4]; /* best total demerits known for current 667 line class and position, given the fitness */ 668static int minimum_demerits; /* best total demerits known for current line class 669 and position */ 670static halfword best_place[4]; /* how to achieve |minimal_demerits| */ 671static halfword best_pl_line[4]; /*corresponding line number */ 672 673 674 675@ The length of lines depends on whether the user has specified 676\.{\\parshape} or \.{\\hangindent}. If |par_shape_ptr| is not null, it 677points to a $(2n+1)$-word record in |mem|, where the |vinfo| in the first 678word contains the value of |n|, and the other $2n$ words contain the left 679margins and line lengths for the first |n| lines of the paragraph; the 680specifications for line |n| apply to all subsequent lines. If 681|par_shape_ptr=null|, the shape of the paragraph depends on the value of 682|n=hang_after|; if |n>=0|, hanging indentation takes place on lines |n+1|, 683|n+2|, \dots, otherwise it takes place on lines 1, \dots, $\vert 684n\vert$. When hanging indentation is active, the left margin is 685|hang_indent|, if |hang_indent>=0|, else it is 0; the line length is 686$|hsize|-\vert|hang_indent|\vert$. The normal setting is 687|par_shape_ptr=null|, |hang_after=1|, and |hang_indent=0|. 688Note that if |hang_indent=0|, the value of |hang_after| is irrelevant. 689@^length of lines@> @^hanging indentation@> 690 691@c 692static halfword easy_line; /*line numbers |>easy_line| are equivalent in break nodes */ 693static halfword last_special_line; /*line numbers |>last_special_line| all have the same width */ 694static scaled first_width; /*the width of all lines |<=last_special_line|, if 695 no \.{\\parshape} has been specified */ 696static scaled second_width; /*the width of all lines |>last_special_line| */ 697static scaled first_indent; /*left margin to go with |first_width| */ 698static scaled second_indent; /*left margin to go with |second_width| */ 699 700static halfword best_bet; /*use this passive node and its predecessors */ 701static int fewest_demerits; /*the demerits associated with |best_bet| */ 702static halfword best_line; /*line number following the last line of the new paragraph */ 703static int actual_looseness; /*the difference between |line_number(best_bet)| 704 and the optimum |best_line| */ 705static int line_diff; /*the difference between the current line number and 706 the optimum |best_line| */ 707 708 709 710@ \TeX\ makes use of the fact that |hlist_node|, |vlist_node|, 711 |rule_node|, |ins_node|, |mark_node|, |adjust_node|, 712 |disc_node|, |whatsit_node|, and |math_node| are at the low end of the 713 type codes, by permitting a break at glue in a list if and only if the 714 |type| of the previous node is less than |math_node|. Furthermore, a 715 node is discarded after a break if its type is |math_node| or~more. 716 717@c 718#define do_all_six(a) a(1);a(2);a(3);a(4);a(5);a(6);a(7) 719#define do_seven_eight(a) if (pdf_adjust_spacing > 1) { a(8);a(9); } 720#define do_all_eight(a) do_all_six(a); do_seven_eight(a) 721#define do_one_seven_eight(a) a(1); do_seven_eight(a) 722 723#define store_background(a) {active_width[a]=background[a];} 724 725#define kern_break() { \ 726 if ((!is_char_node(vlink(cur_p))) && auto_breaking) \ 727 if (type(vlink(cur_p))==glue_node) \ 728 ext_try_break(0,unhyphenated_node, line_break_dir, pdf_adjust_spacing, \ 729 par_shape_ptr, adj_demerits, \ 730 tracing_paragraphs, pdf_protrude_chars, \ 731 line_penalty, last_line_fit, \ 732 double_hyphen_demerits, final_hyphen_demerits,first_p,cur_p); \ 733 if (type(cur_p)!=math_node) active_width[1]+=width(cur_p); \ 734 else active_width[1]+=surround(cur_p); \ 735 } 736 737#define clean_up_the_memory() { \ 738 q=vlink(active); \ 739 while (q!=active) { \ 740 cur_p=vlink(q); \ 741 if (type(q)==delta_node) flush_node(q); \ 742 else flush_node(q); \ 743 q=cur_p; \ 744 } \ 745 q=passive; \ 746 while (q!=null) { \ 747 cur_p=vlink(q); \ 748 flush_node(q); \ 749 q=cur_p; \ 750 } \ 751 } 752 753static boolean do_last_line_fit; /* special algorithm for last line of paragraph? */ 754static scaled fill_width[4]; /* infinite stretch components of |par_fill_skip| */ 755static scaled best_pl_short[4]; /* |shortfall| corresponding to |minimal_demerits| */ 756static scaled best_pl_glue[4]; /*corresponding glue stretch or shrink */ 757 758#define reset_disc_width(a) disc_width[(a)] = 0 759 760#define add_disc_width_to_break_width(a) break_width[(a)] += disc_width[(a)] 761#define sub_disc_width_from_active_width(a) active_width[(a)] -= disc_width[(a)] 762 763#define add_char_shrink(a,b) a += char_shrink((b)) 764#define add_char_stretch(a,b) a += char_stretch((b)) 765#define sub_char_shrink(a,b) a -= char_shrink((b)) 766#define sub_char_stretch(a,b) a -= char_stretch((b)) 767 768#define add_kern_shrink(a,b) a += kern_shrink((b)) 769#define add_kern_stretch(a,b) a += kern_stretch((b)) 770#define sub_kern_shrink(a,b) a -= kern_shrink((b)) 771#define sub_kern_stretch(a,b) a -= kern_stretch((b)) 772 773 774@ This function is used to add the width of a list of nodes 775(from a discretionary) to one of the width arrays. 776 777 778Replacement texts and discretionary texts are supposed to contain 779only character nodes, kern nodes, and box or rule nodes. 780 781@c 782static void add_to_widths(halfword s, int line_break_dir, 783 int pdf_adjust_spacing, scaled * widths) 784{ 785 while (s != null) { 786 if (is_char_node(s)) { 787 widths[1] += pack_width(line_break_dir, dir_TRT, s, true); 788 if ((pdf_adjust_spacing > 1) && check_expand_pars(font(s))) { 789 set_prev_char_p(s); 790 add_char_stretch(widths[8], s); 791 add_char_shrink(widths[9], s); 792 }; 793 } else { 794 switch (type(s)) { 795 case hlist_node: 796 case vlist_node: 797 widths[1] += pack_width(line_break_dir, box_dir(s), s, false); 798 break; 799 case kern_node: 800 if ((pdf_adjust_spacing > 1) && (subtype(s) == normal)) { 801 add_kern_stretch(widths[8], s); 802 add_kern_shrink(widths[9], s); 803 } 804 /* fall through */ 805 case rule_node: 806 widths[1] += width(s); 807 break; 808 case disc_node: /* TH temp */ 809 break; 810 default: 811 confusion("add_disc_widths"); 812 } 813 } 814 s = vlink(s); 815 } 816} 817 818@ This function is used to substract the width of a list of nodes 819(from a discretionary) from one of the width arrays. 820It is used only once, but deserves it own function because of orthogonality 821with the |add_to_widths| function. 822 823@c 824static void sub_from_widths(halfword s, int line_break_dir, 825 int pdf_adjust_spacing, scaled * widths) 826{ 827 while (s != null) { 828 /* Subtract the width of node |s| from |break_width|; */ 829 if (is_char_node(s)) { 830 widths[1] -= pack_width(line_break_dir, dir_TRT, s, true); 831 if ((pdf_adjust_spacing > 1) && check_expand_pars(font(s))) { 832 set_prev_char_p(s); 833 sub_char_stretch(widths[8], s); 834 sub_char_shrink(widths[9], s); 835 } 836 } else { 837 switch (type(s)) { 838 case hlist_node: 839 case vlist_node: 840 widths[1] -= pack_width(line_break_dir, box_dir(s), s, false); 841 break; 842 case kern_node: 843 if ((pdf_adjust_spacing > 1) && (subtype(s) == normal)) { 844 sub_kern_stretch(widths[8], s); 845 sub_kern_shrink(widths[9], s); 846 } 847 /* fall through */ 848 case rule_node: 849 widths[1] -= width(s); 850 break; 851 case disc_node: /* TH temp */ 852 break; 853 default: 854 confusion("sub_disc_widths"); 855 break; 856 } 857 } 858 s = vlink(s); 859 } 860} 861 862 863@ When we insert a new active node for a break at |cur_p|, suppose this 864 new node is to be placed just before active node |a|; then we essentially 865 want to insert `$\delta\,|cur_p|\,\delta^\prime$' before |a|, where 866 $\delta=\alpha(a)-\alpha(|cur_p|)$ and $\delta^\prime=\alpha(|cur_p|)-\alpha(a)$ 867 in the notation explained above. The |cur_active_width| array now holds 868 $\gamma+\beta(|cur_p|)-\alpha(a)$; so $\delta$ can be obtained by 869 subtracting |cur_active_width| from the quantity $\gamma+\beta(|cur_p|)- 870 \alpha(|cur_p|)$. The latter quantity can be regarded as the length of a 871 line ``from |cur_p| to |cur_p|''; we call it the |break_width| at |cur_p|. 872 873 The |break_width| is usually negative, since it consists of the background 874 (which is normally zero) minus the width of nodes following~|cur_p| that are 875 eliminated after a break. If, for example, node |cur_p| is a glue node, the 876 width of this glue is subtracted from the background; and we also look 877 ahead to eliminate all subsequent glue and penalty and kern and math 878 nodes, subtracting their widths as well. 879 880 Kern nodes do not disappear at a line break unless they are |explicit|. 881 882@c 883static void 884compute_break_width(int break_type, int line_break_dir, int pdf_adjust_spacing, 885 halfword p 886 /*, halfword s */ ) 887{ 888 halfword s; /* glue and other 'whitespace' to be skipped after a break 889 * used if unhyphenated, or |post_break==empty| */ 890 s = p; 891 if (break_type > unhyphenated_node && p != null) { 892 /*Compute the discretionary |break_width| values; */ 893 /* When |p| is a discretionary break, the length of a line 894 ``from |p| to |p|'' has to be defined properly so 895 that the other calculations work out. Suppose that the 896 pre-break text at |p| has length $l_0$, the post-break 897 text has length $l_1$, and the replacement text has length 898 |l|. Suppose also that |q| is the node following the 899 replacement text. Then length of a line from |p| to |q| 900 will be computed as $\gamma+\beta(q)-\alpha(|p|)$, where 901 $\beta(q)=\beta(|p|)-l_0+l$. The actual length will be 902 the background plus $l_1$, so the length from |p| to 903 |p| should be $\gamma+l_0+l_1-l$. If the post-break text 904 of the discretionary is empty, a break may also discard~|q|; 905 in that unusual case we subtract the length of~|q| and any 906 other nodes that will be discarded after the discretionary 907 break. 908 909 TH: I don't quite understand the above remarks. 910 911 The value of $l_0$ need not be computed, since |line_break| 912 will put it into the global variable |disc_width| before 913 calling |try_break|. 914 */ 915 /* In case of nested discretionaries, we always follow the no-break 916 path, as we are talking about the breaking on {\it this} position. 917 */ 918 919 sub_from_widths(vlink_no_break(p), line_break_dir, pdf_adjust_spacing, 920 break_width); 921 add_to_widths(vlink_post_break(p), line_break_dir, pdf_adjust_spacing, 922 break_width); 923 do_one_seven_eight(add_disc_width_to_break_width); 924 if (vlink_post_break(p) == null) { 925 s = vlink(p); /* no |post_break|: 'skip' any 'whitespace' following */ 926 } else { 927 s = null; 928 } 929 } 930 while (s != null) { 931 switch (type(s)) { 932 case glue_node: 933 /*Subtract glue from |break_width|; */ 934 { 935 halfword v = glue_ptr(s); 936 break_width[1] -= width(v); 937 break_width[2 + stretch_order(v)] -= stretch(v); 938 break_width[7] -= shrink(v); 939 } 940 break; 941 case penalty_node: 942 break; 943 case math_node: 944 break_width[1] -= surround(s); 945 break; 946 case kern_node: 947 if (subtype(s) != explicit) 948 return; 949 else 950 break_width[1] -= width(s); 951 break; 952 default: 953 return; 954 }; 955 s = vlink(s); 956 } 957} 958 959@ @c 960static void 961print_break_node(halfword q, fitness_value fit_class, 962 quarterword break_type, halfword cur_p) 963{ 964 /* Print a symbolic description of the new break node */ 965 tprint_nl("@@@@"); 966 print_int(serial(passive)); 967 tprint(": line "); 968 print_int(line_number(q) - 1); 969 print_char('.'); 970 print_int(fit_class); 971 if (break_type == hyphenated_node) 972 print_char('-'); 973 tprint(" t="); 974 print_int(total_demerits(q)); 975 if (do_last_line_fit) { 976 /*Print additional data in the new active node; */ 977 tprint(" s="); 978 print_scaled(active_short(q)); 979 if (cur_p == null) 980 tprint(" a="); 981 else 982 tprint(" g="); 983 print_scaled(active_glue(q)); 984 } 985 tprint(" -> @@"); 986 if (prev_break(passive) == null) 987 print_char('0'); 988 else 989 print_int(serial(prev_break(passive))); 990} 991 992@ @c 993static void 994print_feasible_break(halfword cur_p, pointer r, halfword b, int pi, 995 int d, boolean artificial_demerits) 996{ 997 /* Print a symbolic description of this feasible break; */ 998 if (printed_node != cur_p) { 999 /* Print the list between |printed_node| and |cur_p|, then 1000 set |printed_node:=cur_p|; */ 1001 tprint_nl(""); 1002 if (cur_p == null) { 1003 short_display(vlink(printed_node)); 1004 } else { 1005 halfword save_link = vlink(cur_p); 1006 vlink(cur_p) = null; 1007 tprint_nl(""); 1008 short_display(vlink(printed_node)); 1009 vlink(cur_p) = save_link; 1010 } 1011 printed_node = cur_p; 1012 } 1013 tprint_nl("@@"); 1014 if (cur_p == null) { 1015 tprint_esc("par"); 1016 } else if (type(cur_p) != glue_node) { 1017 if (type(cur_p) == penalty_node) 1018 tprint_esc("penalty"); 1019 else if (type(cur_p) == disc_node) 1020 tprint_esc("discretionary"); 1021 else if (type(cur_p) == kern_node) 1022 tprint_esc("kern"); 1023 else 1024 tprint_esc("math"); 1025 } 1026 tprint(" via @@"); 1027 if (break_node(r) == null) 1028 print_char('0'); 1029 else 1030 print_int(serial(break_node(r))); 1031 tprint(" b="); 1032 if (b > inf_bad) 1033 print_char('*'); 1034 else 1035 print_int(b); 1036 tprint(" p="); 1037 print_int(pi); 1038 tprint(" d="); 1039 if (artificial_demerits) 1040 print_char('*'); 1041 else 1042 print_int(d); 1043} 1044 1045@ @c 1046#define add_disc_width_to_active_width(a) active_width[a] += disc_width[a] 1047#define update_width(a) cur_active_width[a] += varmem[(r+(a))].cint 1048 1049#define set_break_width_to_background(a) break_width[a]=background[(a)] 1050 1051#define convert_to_break_width(a) \ 1052 varmem[(prev_r+(a))].cint = varmem[(prev_r+(a))].cint-cur_active_width[(a)]+break_width[(a)] 1053 1054#define store_break_width(a) active_width[(a)]=break_width[(a)] 1055 1056#define new_delta_to_break_width(a) \ 1057 varmem[(q+(a))].cint=break_width[(a)]-cur_active_width[(a)] 1058 1059#define new_delta_from_break_width(a) \ 1060 varmem[(q+(a))].cint=cur_active_width[(a)]-break_width[(a)] 1061 1062#define copy_to_cur_active(a) cur_active_width[(a)]=active_width[(a)] 1063 1064#define combine_two_deltas(a) varmem[(prev_r+(a))].cint += varmem[(r+(a))].cint 1065#define downdate_width(a) cur_active_width[(a)] -= varmem[(prev_r+(a))].cint 1066#define update_active(a) active_width[(a)]+=varmem[(r+(a))].cint 1067 1068#define total_font_stretch cur_active_width[8] 1069#define total_font_shrink cur_active_width[9] 1070 1071#define cal_margin_kern_var(a) { \ 1072 character(cp) = character((a)); \ 1073 font(cp) = font((a)); \ 1074 do_subst_font(cp, 1000); \ 1075 if (font(cp) != font((a))) \ 1076 margin_kern_stretch += (left_pw((a)) - left_pw(cp)); \ 1077 font(cp) = font((a)); \ 1078 do_subst_font(cp, -1000); \ 1079 if (font(cp) != font((a))) \ 1080 margin_kern_shrink += (left_pw(cp) - left_pw((a))); \ 1081 } 1082 1083static void 1084ext_try_break(int pi, 1085 quarterword break_type, 1086 int line_break_dir, 1087 int pdf_adjust_spacing, 1088 int par_shape_ptr, 1089 int adj_demerits, 1090 int tracing_paragraphs, 1091 int pdf_protrude_chars, 1092 int line_penalty, 1093 int last_line_fit, 1094 int double_hyphen_demerits, 1095 int final_hyphen_demerits, halfword first_p, halfword cur_p) 1096{ 1097 /* labels: |CONTINUE,DEACTIVATE,FOUND,NOT_FOUND|; */ 1098 pointer r; /* runs through the active list */ 1099 scaled margin_kern_stretch; 1100 scaled margin_kern_shrink; 1101 halfword lp, rp, cp; 1102 halfword prev_r; /* stays a step behind |r| */ 1103 halfword prev_prev_r; /*a step behind |prev_r|, if |type(prev_r)=delta_node| */ 1104 halfword old_l; /* maximum line number in current equivalence class of lines */ 1105 boolean no_break_yet; /* have we found a feasible break at |cur_p|? */ 1106 halfword q; /*points to a new node being created */ 1107 halfword l; /*line number of current active node */ 1108 boolean node_r_stays_active; /*should node |r| remain in the active list? */ 1109 scaled line_width; /*the current line will be justified to this width */ 1110 fitness_value fit_class; /*possible fitness class of test line */ 1111 halfword b; /*badness of test line */ 1112 int d; /*demerits of test line */ 1113 boolean artificial_demerits; /*has |d| been forced to zero? */ 1114 1115 scaled shortfall; /*used in badness calculations */ 1116 scaled g; /*glue stretch or shrink of test line, adjustment for last line */ 1117 scaled cur_active_width[10] = { 0 }; /*distance from current active node */ 1118 1119 line_width = 0; 1120 g = 0; 1121 prev_prev_r = null; 1122 /*Make sure that |pi| is in the proper range; */ 1123 if (pi >= inf_penalty) { 1124 return; /* this breakpoint is inhibited by infinite penalty */ 1125 } else if (pi <= -inf_penalty) { 1126 pi = eject_penalty; /*this breakpoint will be forced */ 1127 } 1128 1129 no_break_yet = true; 1130 prev_r = active; 1131 old_l = 0; 1132 do_all_eight(copy_to_cur_active); 1133 1134 while (1) { 1135 r = vlink(prev_r); 1136 /* If node |r| is of type |delta_node|, update |cur_active_width|, 1137 set |prev_r| and |prev_prev_r|, then |goto continue|; */ 1138 /* The following code uses the fact that |type(active)<>delta_node| */ 1139 if (type(r) == delta_node) { 1140 do_all_eight(update_width); /* IMPLICIT ,r */ 1141 prev_prev_r = prev_r; 1142 prev_r = r; 1143 continue; 1144 } 1145 /* If a line number class has ended, create new active nodes for 1146 the best feasible breaks in that class; then |return| 1147 if |r=active|, otherwise compute the new |line_width|; */ 1148 /* The first part of the following code is part of \TeX's inner loop, so 1149 we don't want to waste any time. The current active node, namely node |r|, 1150 contains the line number that will be considered next. At the end of the 1151 list we have arranged the data structure so that |r=active| and 1152 |line_number(active)>old_l|. 1153 */ 1154 l = line_number(r); 1155 if (l > old_l) { /* now we are no longer in the inner loop */ 1156 if ((minimum_demerits < awful_bad) 1157 && ((old_l != easy_line) || (r == active))) { 1158 /*Create new active nodes for the best feasible breaks just found */ 1159 /* It is not necessary to create new active nodes having |minimal_demerits| 1160 greater than 1161 |minimum_demerits+abs(adj_demerits)|, since such active nodes will never 1162 be chosen in the final paragraph breaks. This observation allows us to 1163 omit a substantial number of feasible breakpoints from further consideration. 1164 */ 1165 if (no_break_yet) { 1166 no_break_yet = false; 1167 do_all_eight(set_break_width_to_background); 1168 compute_break_width(break_type, line_break_dir, 1169 pdf_adjust_spacing, cur_p); 1170 } 1171 /* Insert a delta node to prepare for breaks at |cur_p|; */ 1172 /* We use the fact that |type(active)<>delta_node|. */ 1173 if (type(prev_r) == delta_node) { /* modify an existing delta node */ 1174 do_all_eight(convert_to_break_width); /* IMPLICIT |prev_r| */ 1175 } else if (prev_r == active) { /* no delta node needed at the beginning */ 1176 do_all_eight(store_break_width); 1177 } else { 1178 q = new_node(delta_node, 0); 1179 vlink(q) = r; 1180 do_all_eight(new_delta_to_break_width); /* IMPLICIT q */ 1181 vlink(prev_r) = q; 1182 prev_prev_r = prev_r; 1183 prev_r = q; 1184 } 1185 1186 if (abs(adj_demerits) >= awful_bad - minimum_demerits) 1187 minimum_demerits = awful_bad - 1; 1188 else 1189 minimum_demerits += abs(adj_demerits); 1190 for (fit_class = very_loose_fit; fit_class <= tight_fit; 1191 fit_class++) { 1192 if (minimal_demerits[fit_class] <= minimum_demerits) { 1193 /* Insert a new active node from |best_place[fit_class]| 1194 to |cur_p|; */ 1195 /* When we create an active node, we also create the corresponding 1196 passive node. 1197 */ 1198 q = new_node(passive_node, 0); 1199 vlink(q) = passive; 1200 passive = q; 1201 cur_break(q) = cur_p; 1202 incr(pass_number); 1203 serial(q) = pass_number; 1204 prev_break(q) = best_place[fit_class]; 1205 /*Here we keep track of the subparagraph penalties in the break nodes */ 1206 passive_pen_inter(q) = internal_pen_inter; 1207 passive_pen_broken(q) = internal_pen_broken; 1208 passive_last_left_box(q) = internal_left_box; 1209 passive_last_left_box_width(q) = 1210 internal_left_box_width; 1211 if (prev_break(q) != null) { 1212 passive_left_box(q) = 1213 passive_last_left_box(prev_break(q)); 1214 passive_left_box_width(q) = 1215 passive_last_left_box_width(prev_break(q)); 1216 } else { 1217 passive_left_box(q) = init_internal_left_box; 1218 passive_left_box_width(q) = 1219 init_internal_left_box_width; 1220 } 1221 passive_right_box(q) = internal_right_box; 1222 passive_right_box_width(q) = internal_right_box_width; 1223 q = new_node(break_type, fit_class); 1224 break_node(q) = passive; 1225 line_number(q) = best_pl_line[fit_class] + 1; 1226 total_demerits(q) = minimal_demerits[fit_class]; 1227 if (do_last_line_fit) { 1228 /*Store additional data in the new active node */ 1229 /* Here we save these data in the active node 1230 representing a potential line break. */ 1231 active_short(q) = best_pl_short[fit_class]; 1232 active_glue(q) = best_pl_glue[fit_class]; 1233 } 1234 vlink(q) = r; 1235 vlink(prev_r) = q; 1236 prev_r = q; 1237 if (tracing_paragraphs > 0) 1238 print_break_node(q, fit_class, break_type, cur_p); 1239 } 1240 minimal_demerits[fit_class] = awful_bad; 1241 } 1242 minimum_demerits = awful_bad; 1243 /* Insert a delta node to prepare for the next active node; */ 1244 /* When the following code is performed, we will have just inserted at 1245 least one active node before |r|, so |type(prev_r)<>delta_node|. 1246 */ 1247 if (r != active) { 1248 q = new_node(delta_node, 0); 1249 vlink(q) = r; 1250 do_all_eight(new_delta_from_break_width); /* IMPLICIT q */ 1251 vlink(prev_r) = q; 1252 prev_prev_r = prev_r; 1253 prev_r = q; 1254 } 1255 } 1256 if (r == active) 1257 return; 1258 /*Compute the new line width; */ 1259 /* When we come to the following code, we have just encountered 1260 the first active node~|r| whose |line_number| field contains 1261 |l|. Thus we want to compute the length of the $l\mskip1mu$th 1262 line of the current paragraph. Furthermore, we want to set 1263 |old_l| to the last number in the class of line numbers 1264 equivalent to~|l|. 1265 */ 1266 if (l > easy_line) { 1267 old_l = max_halfword - 1; 1268 line_width = second_width; 1269 } else { 1270 old_l = l; 1271 if (l > last_special_line) { 1272 line_width = second_width; 1273 } else if (par_shape_ptr == null) { 1274 line_width = first_width; 1275 } else { 1276 line_width = varmem[(par_shape_ptr + 2 * l + 1)].cint; 1277 } 1278 } 1279 } 1280 /* /If a line number class has ended, create new active nodes for 1281 the best feasible breaks in that class; then |return| 1282 if |r=active|, otherwise compute the new |line_width|; */ 1283 1284 /* Consider the demerits for a line from |r| to |cur_p|; 1285 deactivate node |r| if it should no longer be active; 1286 then |goto continue| if a line from |r| to |cur_p| is infeasible, 1287 otherwise record a new feasible break; */ 1288 artificial_demerits = false; 1289 shortfall = line_width - cur_active_width[1]; 1290 if (break_node(r) == null) 1291 shortfall -= init_internal_left_box_width; 1292 else 1293 shortfall -= passive_last_left_box_width(break_node(r)); 1294 shortfall -= internal_right_box_width; 1295 if (pdf_protrude_chars > 1) { 1296 halfword l1, o; 1297 l1 = (break_node(r) == null) ? first_p : cur_break(break_node(r)); 1298 if (cur_p == null) { 1299 o = null; 1300 } else { /* TODO |if (is_character_node(alink(cur_p)))| */ 1301 o = alink(cur_p); 1302 assert(vlink(o) == cur_p); 1303 } 1304 /* MAGIC: the disc could be a SELECT subtype, to we might need 1305 to get the last character as |pre_break| from either the 1306 |pre_break| list (if the previous INIT disc was taken), or the 1307 |no_break| (sic) list (if the previous INIT disc was not taken) 1308 1309 BUT: 1310 the last characters (hyphenation character) if these two list 1311 should always be the same anyway, so we just look at |pre_break|. 1312 */ 1313 /* let's look at the right margin first */ 1314 if ((cur_p != null) && (type(cur_p) == disc_node) 1315 && (vlink_pre_break(cur_p) != null)) { 1316 /* a |disc_node| with non-empty |pre_break|, protrude the last char of |pre_break| */ 1317 o = tlink_pre_break(cur_p); 1318 } else { 1319 o = find_protchar_right(l1, o); 1320 } 1321 /* now the left margin */ 1322 if ((l1 != null) && (type(l1) == disc_node) 1323 && (vlink_post_break(l1) != null)) { 1324 /* FIXME: first 'char' could be a disc! */ 1325 l1 = vlink_post_break(l1); /* protrude the first char */ 1326 } else { 1327 l1 = find_protchar_left(l1, true); 1328 } 1329 shortfall += (left_pw(l1) + right_pw(o)); 1330 } 1331 if ((shortfall != 0) && (pdf_adjust_spacing > 1)) { 1332 margin_kern_stretch = 0; 1333 margin_kern_shrink = 0; 1334 if (pdf_protrude_chars > 1) { 1335 /* Calculate variations of marginal kerns; */ 1336 lp = last_leftmost_char; 1337 rp = last_rightmost_char; 1338 cp = raw_glyph_node(); 1339 if (lp != null) { 1340 cal_margin_kern_var(lp); 1341 } 1342 if (rp != null) { 1343 cal_margin_kern_var(rp); 1344 } 1345 flush_node(cp); 1346 } 1347 if ((shortfall > 0) 1348 && ((total_font_stretch + margin_kern_stretch) > 0)) { 1349 if ((total_font_stretch + margin_kern_stretch) > shortfall) 1350 shortfall = ((total_font_stretch + margin_kern_stretch) / 1351 (max_stretch_ratio / cur_font_step)) / 2; 1352 else 1353 shortfall -= (total_font_stretch + margin_kern_stretch); 1354 } else if ((shortfall < 0) 1355 && ((total_font_shrink + margin_kern_shrink) > 0)) { 1356 if ((total_font_shrink + margin_kern_shrink) > -shortfall) 1357 shortfall = -((total_font_shrink + margin_kern_shrink) / 1358 (max_shrink_ratio / cur_font_step)) / 2; 1359 else 1360 shortfall += (total_font_shrink + margin_kern_shrink); 1361 } 1362 } 1363 if (shortfall > 0) { 1364 /* Set the value of |b| to the badness for stretching the line, 1365 and compute the corresponding |fit_class| */ 1366 1367 /* When a line must stretch, the available stretchability can be 1368 found in the subarray |cur_active_width[2..6]|, in units of 1369 points, sfi, fil, fill and filll. 1370 1371 The present section is part of \TeX's inner loop, and it is 1372 most often performed when the badness is infinite; therefore 1373 it is worth while to make a quick test for large width excess 1374 and small stretchability, before calling the |badness| 1375 subroutine. */ 1376 1377 if ((cur_active_width[3] != 0) || (cur_active_width[4] != 0) || 1378 (cur_active_width[5] != 0) || (cur_active_width[6] != 0)) { 1379 if (do_last_line_fit) { 1380 if (cur_p == null) { /* the last line of a paragraph */ 1381 /* Perform computations for last line and |goto found|; */ 1382 1383 /* Here we compute the adjustment |g| and badness |b| for 1384 a line from |r| to the end of the paragraph. When any 1385 of the criteria for adjustment is violated we fall 1386 through to the normal algorithm. 1387 1388 The last line must be too short, and have infinite 1389 stretch entirely due to |par_fill_skip|. */ 1390 if ((active_short(r) == 0) || (active_glue(r) <= 0)) 1391 /* previous line was neither stretched nor shrunk, or 1392 was infinitely bad */ 1393 goto NOT_FOUND; 1394 if ((cur_active_width[3] != fill_width[0]) || 1395 (cur_active_width[4] != fill_width[1]) || 1396 (cur_active_width[5] != fill_width[2]) || 1397 (cur_active_width[6] != fill_width[3])) 1398 /* infinite stretch of this line not entirely due to 1399 |par_fill_skip| */ 1400 goto NOT_FOUND; 1401 if (active_short(r) > 0) 1402 g = cur_active_width[2]; 1403 else 1404 g = cur_active_width[7]; 1405 if (g <= 0) 1406 /*no finite stretch resp.\ no shrink */ 1407 goto NOT_FOUND; 1408 arith_error = false; 1409 g = fract(g, active_short(r), active_glue(r), 1410 max_dimen); 1411 if (last_line_fit < 1000) 1412 g = fract(g, last_line_fit, 1000, max_dimen); 1413 if (arith_error) { 1414 if (active_short(r) > 0) 1415 g = max_dimen; 1416 else 1417 g = -max_dimen; 1418 } 1419 if (g > 0) { 1420 /*Set the value of |b| to the badness of the last line 1421 for stretching, compute the corresponding |fit_class, 1422 and |goto found|| */ 1423 /* These badness computations are rather similar to 1424 those of the standard algorithm, with the adjustment 1425 amount |g| replacing the |shortfall|. */ 1426 if (g > shortfall) 1427 g = shortfall; 1428 if (g > 7230584) { 1429 if (cur_active_width[2] < 1663497) { 1430 b = inf_bad; 1431 fit_class = very_loose_fit; 1432 goto FOUND; 1433 } 1434 } 1435 b = badness(g, cur_active_width[2]); 1436 if (b > 99) { 1437 fit_class = very_loose_fit; 1438 } else if (b > 12) { 1439 fit_class = loose_fit; 1440 } else { 1441 fit_class = decent_fit; 1442 } 1443 goto FOUND; 1444 } else if (g < 0) { 1445 /*Set the value of |b| to the badness of the last line 1446 for shrinking, compute the corresponding |fit_class, 1447 and |goto found||; */ 1448 if (-g > cur_active_width[7]) 1449 g = -cur_active_width[7]; 1450 b = badness(-g, cur_active_width[7]); 1451 if (b > 12) 1452 fit_class = tight_fit; 1453 else 1454 fit_class = decent_fit; 1455 goto FOUND; 1456 } 1457 } 1458 NOT_FOUND: 1459 shortfall = 0; 1460 } 1461 b = 0; 1462 fit_class = decent_fit; /* infinite stretch */ 1463 } else { 1464 if (shortfall > 7230584 && cur_active_width[2] < 1663497) { 1465 b = inf_bad; 1466 fit_class = very_loose_fit; 1467 } else { 1468 b = badness(shortfall, cur_active_width[2]); 1469 if (b > 99) { 1470 fit_class = very_loose_fit; 1471 } else if (b > 12) { 1472 fit_class = loose_fit; 1473 } else { 1474 fit_class = decent_fit; 1475 } 1476 } 1477 } 1478 } else { 1479 /* Set the value of |b| to the badness for shrinking the line, 1480 and compute the corresponding |fit_class|; */ 1481 /* Shrinkability is never infinite in a paragraph; we can shrink 1482 the line from |r| to |cur_p| by at most 1483 |cur_active_width[7]|. */ 1484 if (-shortfall > cur_active_width[7]) 1485 b = inf_bad + 1; 1486 else 1487 b = badness(-shortfall, cur_active_width[7]); 1488 if (b > 12) 1489 fit_class = tight_fit; 1490 else 1491 fit_class = decent_fit; 1492 } 1493 if (do_last_line_fit) { 1494 /* Adjust the additional data for last line; */ 1495 if (cur_p == null) 1496 shortfall = 0; 1497 if (shortfall > 0) { 1498 g = cur_active_width[2]; 1499 } else if (shortfall < 0) { 1500 g = cur_active_width[7]; 1501 } else { 1502 g = 0; 1503 } 1504 } 1505 FOUND: 1506 if ((b > inf_bad) || (pi == eject_penalty)) { 1507 /* Prepare to deactivate node~|r|, and |goto deactivate| unless 1508 there is a reason to consider lines of text from |r| to |cur_p| */ 1509 /* During the final pass, we dare not lose all active nodes, lest we lose 1510 touch with the line breaks already found. The code shown here makes 1511 sure that such a catastrophe does not happen, by permitting overfull 1512 boxes as a last resort. This particular part of \TeX\ was a source of 1513 several subtle bugs before the correct program logic was finally 1514 discovered; readers who seek to ``improve'' \TeX\ should therefore 1515 think thrice before daring to make any changes here. 1516 */ 1517 if (final_pass && (minimum_demerits == awful_bad) && 1518 (vlink(r) == active) && (prev_r == active)) { 1519 artificial_demerits = true; /* set demerits zero, this break is forced */ 1520 } else if (b > threshold) { 1521 goto DEACTIVATE; 1522 } 1523 node_r_stays_active = false; 1524 } else { 1525 prev_r = r; 1526 if (b > threshold) 1527 continue; 1528 node_r_stays_active = true; 1529 } 1530 /* Record a new feasible break; */ 1531 /* When we get to this part of the code, the line from |r| to |cur_p| is 1532 feasible, its badness is~|b|, and its fitness classification is 1533 |fit_class|. We don't want to make an active node for this break yet, 1534 but we will compute the total demerits and record them in the 1535 |minimal_demerits| array, if such a break is the current champion among 1536 all ways to get to |cur_p| in a given line-number class and fitness 1537 class. 1538 */ 1539 if (artificial_demerits) { 1540 d = 0; 1541 } else { 1542 /* Compute the demerits, |d|, from |r| to |cur_p|; */ 1543 d = line_penalty + b; 1544 if (abs(d) >= 10000) 1545 d = 100000000; 1546 else 1547 d = d * d; 1548 if (pi != 0) { 1549 if (pi > 0) { 1550 d += (pi * pi); 1551 } else if (pi > eject_penalty) { 1552 d -= (pi * pi); 1553 } 1554 } 1555 if ((break_type == hyphenated_node) && (type(r) == hyphenated_node)) { 1556 if (cur_p != null) 1557 d += double_hyphen_demerits; 1558 else 1559 d += final_hyphen_demerits; 1560 } 1561 if (abs(fit_class - fitness(r)) > 1) 1562 d = d + adj_demerits; 1563 } 1564 if (tracing_paragraphs > 0) 1565 print_feasible_break(cur_p, r, b, pi, d, artificial_demerits); 1566 d += total_demerits(r); /*this is the minimum total demerits 1567 from the beginning to |cur_p| via |r| */ 1568 if (d <= minimal_demerits[fit_class]) { 1569 minimal_demerits[fit_class] = d; 1570 best_place[fit_class] = break_node(r); 1571 best_pl_line[fit_class] = l; 1572 if (do_last_line_fit) { 1573 /* Store additional data for this feasible break; */ 1574 /* For each feasible break we record the shortfall and glue stretch or 1575 shrink (or adjustment). */ 1576 best_pl_short[fit_class] = shortfall; 1577 best_pl_glue[fit_class] = g; 1578 } 1579 if (d < minimum_demerits) 1580 minimum_demerits = d; 1581 } 1582 /* /Record a new feasible break */ 1583 if (node_r_stays_active) 1584 continue; /*|prev_r| has been set to |r| */ 1585 DEACTIVATE: 1586 /* Deactivate node |r|; */ 1587 /* When an active node disappears, we must delete an adjacent delta node if 1588 the active node was at the beginning or the end of the active list, or 1589 if it was surrounded by delta nodes. We also must preserve the property 1590 that |cur_active_width| represents the length of material from 1591 |vlink(prev_r)| to~|cur_p|. */ 1592 1593 vlink(prev_r) = vlink(r); 1594 flush_node(r); 1595 if (prev_r == active) { 1596 /*Update the active widths, since the first active node has been 1597 deleted */ 1598 /* The following code uses the fact that |type(active)<>delta_node|. 1599 If the active list has just become empty, we do not need to update the 1600 |active_width| array, since it will be initialized when an active 1601 node is next inserted. 1602 */ 1603 r = vlink(active); 1604 if (type(r) == delta_node) { 1605 do_all_eight(update_active); /* IMPLICIT r */ 1606 do_all_eight(copy_to_cur_active); 1607 vlink(active) = vlink(r); 1608 flush_node(r); 1609 } 1610 } else if (type(prev_r) == delta_node) { 1611 r = vlink(prev_r); 1612 if (r == active) { 1613 do_all_eight(downdate_width); /* IMPLICIT |prev_r| */ 1614 vlink(prev_prev_r) = active; 1615 flush_node(prev_r); 1616 prev_r = prev_prev_r; 1617 } else if (type(r) == delta_node) { 1618 do_all_eight(update_width); /* IMPLICIT ,r */ 1619 do_all_eight(combine_two_deltas); /* IMPLICIT r |prev_r| */ 1620 vlink(prev_r) = vlink(r); 1621 flush_node(r); 1622 } 1623 } 1624 } 1625} 1626 1627@ @c 1628void 1629ext_do_line_break(int paragraph_dir, 1630 int pretolerance, 1631 int tracing_paragraphs, 1632 int tolerance, 1633 scaled emergency_stretch, 1634 int looseness, 1635 int hyphen_penalty, 1636 int ex_hyphen_penalty, 1637 int pdf_adjust_spacing, 1638 halfword par_shape_ptr, 1639 int adj_demerits, 1640 int pdf_protrude_chars, 1641 int line_penalty, 1642 int last_line_fit, 1643 int double_hyphen_demerits, 1644 int final_hyphen_demerits, 1645 int hang_indent, 1646 int hsize, 1647 int hang_after, 1648 halfword left_skip, 1649 halfword right_skip, 1650 int pdf_each_line_height, 1651 int pdf_each_line_depth, 1652 int pdf_first_line_height, 1653 int pdf_last_line_depth, 1654 halfword inter_line_penalties_ptr, 1655 int inter_line_penalty, 1656 int club_penalty, 1657 halfword club_penalties_ptr, 1658 halfword widow_penalties_ptr, 1659 int widow_penalty, 1660 int broken_penalty, 1661 halfword final_par_glue, halfword pdf_ignored_dimen) 1662{ 1663 /* DONE,DONE1,DONE2,DONE3,DONE4,DONE5,CONTINUE; */ 1664 halfword cur_p, q, r, s; /* miscellaneous nodes of temporary interest */ 1665 int line_break_dir = paragraph_dir; 1666 1667 /* Get ready to start ... */ 1668 minimum_demerits = awful_bad; 1669 minimal_demerits[tight_fit] = awful_bad; 1670 minimal_demerits[decent_fit] = awful_bad; 1671 minimal_demerits[loose_fit] = awful_bad; 1672 minimal_demerits[very_loose_fit] = awful_bad; 1673 1674 /* We compute the values of |easy_line| and the other local variables relating 1675 to line length when the |line_break| procedure is initializing itself. */ 1676 if (par_shape_ptr == null) { 1677 if (hang_indent == 0) { 1678 last_special_line = 0; 1679 second_width = hsize; 1680 second_indent = 0; 1681 } else { 1682 /* Set line length parameters in preparation for hanging indentation */ 1683 /* We compute the values of |easy_line| and the other local variables relating 1684 to line length when the |line_break| procedure is initializing itself. */ 1685 last_special_line = abs(hang_after); 1686 if (hang_after < 0) { 1687 first_width = hsize - abs(hang_indent); 1688 if (hang_indent >= 0) 1689 first_indent = hang_indent; 1690 else 1691 first_indent = 0; 1692 second_width = hsize; 1693 second_indent = 0; 1694 } else { 1695 first_width = hsize; 1696 first_indent = 0; 1697 second_width = hsize - abs(hang_indent); 1698 if (hang_indent >= 0) 1699 second_indent = hang_indent; 1700 else 1701 second_indent = 0; 1702 } 1703 } 1704 } else { 1705 last_special_line = vinfo(par_shape_ptr + 1) - 1; 1706 second_indent = 1707 varmem[(par_shape_ptr + 2 * (last_special_line + 1))].cint; 1708 second_width = 1709 varmem[(par_shape_ptr + 2 * (last_special_line + 1) + 1)].cint; 1710 } 1711 if (looseness == 0) 1712 easy_line = last_special_line; 1713 else 1714 easy_line = max_halfword; 1715 1716 no_shrink_error_yet = true; 1717 check_shrinkage(left_skip); 1718 check_shrinkage(right_skip); 1719 q = left_skip; 1720 r = right_skip; 1721 background[1] = width(q) + width(r); 1722 background[2] = 0; 1723 background[3] = 0; 1724 background[4] = 0; 1725 background[5] = 0; 1726 background[6] = 0; 1727 background[2 + stretch_order(q)] = stretch(q); 1728 background[2 + stretch_order(r)] += stretch(r); 1729 background[7] = shrink(q) + shrink(r); 1730 if (pdf_adjust_spacing > 1) { 1731 background[8] = 0; 1732 background[9] = 0; 1733 max_stretch_ratio = -1; 1734 max_shrink_ratio = -1; 1735 cur_font_step = -1; 1736 set_prev_char_p(null); 1737 } 1738 /* Check for special treatment of last line of paragraph; */ 1739 /* The new algorithm for the last line requires that the stretchability 1740 |par_fill_skip| is infinite and the stretchability of |left_skip| plus 1741 |right_skip| is finite. 1742 */ 1743 do_last_line_fit = false; 1744 if (last_line_fit > 0) { 1745 q = glue_ptr(last_line_fill); 1746 if ((stretch(q) > 0) && (stretch_order(q) > normal)) { 1747 if ((background[3] == 0) && (background[4] == 0) && 1748 (background[5] == 0) && (background[6] == 0)) { 1749 do_last_line_fit = true; 1750 fill_width[0] = 0; 1751 fill_width[1] = 0; 1752 fill_width[2] = 0; 1753 fill_width[3] = 0; 1754 fill_width[stretch_order(q) - 1] = stretch(q); 1755 } 1756 } 1757 } 1758 /* DIR: Initialize |dir_ptr| for |line_break| */ 1759 if (dir_ptr != null) { 1760 flush_node_list(dir_ptr); 1761 dir_ptr = null; 1762 } 1763#if 0 1764 push_dir(paragraph_dir,dir_ptr); /* TODO what was the point of this? */ 1765#endif 1766 1767 /* Find optimal breakpoints; */ 1768 threshold = pretolerance; 1769 if (threshold >= 0) { 1770 if (tracing_paragraphs > 0) { 1771 begin_diagnostic(); 1772 tprint_nl("@@firstpass"); 1773 } 1774 second_pass = false; 1775 final_pass = false; 1776 } else { 1777 threshold = tolerance; 1778 second_pass = true; 1779 final_pass = (emergency_stretch <= 0); 1780 if (tracing_paragraphs > 0) 1781 begin_diagnostic(); 1782 } 1783 1784 while (1) { 1785 halfword first_p; 1786 halfword nest_stack[10]; 1787 int nest_index = 0; 1788 if (threshold > inf_bad) 1789 threshold = inf_bad; 1790 /* Create an active breakpoint representing the beginning of the paragraph */ 1791 q = new_node(unhyphenated_node, decent_fit); 1792 vlink(q) = active; 1793 break_node(q) = null; 1794 line_number(q) = cur_list.pg_field + 1; 1795 total_demerits(q) = 0; 1796 active_short(q) = 0; 1797 active_glue(q) = 0; 1798 vlink(active) = q; 1799 do_all_eight(store_background); 1800 passive = null; 1801 printed_node = temp_head; 1802 pass_number = 0; 1803 font_in_short_display = null_font; 1804 /* /Create an active breakpoint representing the beginning of the paragraph */ 1805 auto_breaking = true; 1806 cur_p = vlink(temp_head); 1807 /* LOCAL: Initialize with first |local_paragraph| node */ 1808 if ((cur_p != null) && (type(cur_p) == whatsit_node) 1809 && (subtype(cur_p) == local_par_node)) { 1810 alink(cur_p) = temp_head; /* this used to be an assert, but may as well force it */ 1811 internal_pen_inter = local_pen_inter(cur_p); 1812 internal_pen_broken = local_pen_broken(cur_p); 1813 init_internal_left_box = local_box_left(cur_p); 1814 init_internal_left_box_width = local_box_left_width(cur_p); 1815 internal_left_box = init_internal_left_box; 1816 internal_left_box_width = init_internal_left_box_width; 1817 internal_right_box = local_box_right(cur_p); 1818 internal_right_box_width = local_box_right_width(cur_p); 1819 } else { 1820 internal_pen_inter = 0; 1821 internal_pen_broken = 0; 1822 init_internal_left_box = null; 1823 init_internal_left_box_width = 0; 1824 internal_left_box = init_internal_left_box; 1825 internal_left_box_width = init_internal_left_box_width; 1826 internal_right_box = null; 1827 internal_right_box_width = 0; 1828 } 1829 /* /LOCAL: Initialize with first |local_paragraph| node */ 1830 set_prev_char_p(null); 1831 first_p = cur_p; 1832 /* to access the first node of paragraph as the first active node 1833 has |break_node=null| */ 1834 while ((cur_p != null) && (vlink(active) != active)) { 1835 /* |try_break| if |cur_p| is a legal breakpoint; on the 2nd pass, also look at |disc_node|s. */ 1836 1837 while (is_char_node(cur_p)) { 1838 /* Advance |cur_p| to the node following the present string of characters ; */ 1839 /* The code that passes over the characters of words in a paragraph is part of 1840 \TeX's inner loop, so it has been streamlined for speed. We use the fact that 1841 `\.{\\parfillskip}' glue appears at the end of each paragraph; it is therefore 1842 unnecessary to check if |vlink(cur_p)=null| when |cur_p| is a character node. 1843 */ 1844 active_width[1] += 1845 pack_width(line_break_dir, dir_TRT, cur_p, true); 1846 if ((pdf_adjust_spacing > 1) && check_expand_pars(font(cur_p))) { 1847 set_prev_char_p(cur_p); 1848 add_char_stretch(active_width[8], cur_p); 1849 add_char_shrink(active_width[9], cur_p); 1850 } 1851 cur_p = vlink(cur_p); 1852 while (cur_p == null && nest_index > 0) { 1853 cur_p = nest_stack[--nest_index]; 1854#ifdef DEBUG 1855 fprintf(stderr,"Node Pop %d [%d]\n",nest_index,(int)cur_p); 1856#endif 1857 } 1858 } 1859 if (cur_p == null) { /* TODO */ 1860 confusion("linebreak_tail"); 1861 } 1862 /* Determine legal breaks: As we move through the hlist, we need to keep 1863 the |active_width| array up to date, so that the badness of individual 1864 lines is readily calculated by |try_break|. It is convenient to use the 1865 short name |active_width[1]| for the component of active width that represents 1866 real width as opposed to glue. */ 1867 1868 switch (type(cur_p)) { 1869 case hlist_node: 1870 case vlist_node: 1871 active_width[1] += 1872 pack_width(line_break_dir, box_dir(cur_p), cur_p, false); 1873 break; 1874 case rule_node: 1875 active_width[1] += width(cur_p); 1876 break; 1877 case whatsit_node: 1878 /* Advance past a whatsit node in the |line_break| loop; */ 1879 switch (subtype(cur_p)) { 1880 case local_par_node: /* LOCAL: Advance past a |local_paragraph| node; */ 1881 internal_pen_inter = local_pen_inter(cur_p); 1882 internal_pen_broken = local_pen_broken(cur_p); 1883 internal_left_box = local_box_left(cur_p); 1884 internal_left_box_width = local_box_left_width(cur_p); 1885 internal_right_box = local_box_right(cur_p); 1886 internal_right_box_width = local_box_right_width(cur_p); 1887 break; 1888 case dir_node: /* DIR: Adjust the dir stack for the |line_break| routine; */ 1889 if (dir_dir(cur_p) >= 0) { 1890 line_break_dir = dir_dir(cur_p); 1891 push_dir_node(cur_p,dir_ptr); /* adds to |dir_ptr| */ 1892 } else { 1893 pop_dir_node(dir_ptr); 1894 if (dir_ptr != null) 1895 line_break_dir = dir_dir(dir_ptr); 1896 } 1897 break; 1898 case pdf_refxform_node: 1899 case pdf_refximage_node: 1900 active_width[1] += width(cur_p); 1901 } 1902 /* / Advance past a whatsit node in the |line_break| loop/; */ 1903 break; 1904 case glue_node: 1905 /* If node |cur_p| is a legal breakpoint, call |try_break|; 1906 then update the active widths by including the glue in 1907 |glue_ptr(cur_p)|; */ 1908 /* When node |cur_p| is a glue node, we look at the previous to 1909 see whether or not a breakpoint is legal at |cur_p|, as 1910 explained above. */ 1911 /* *INDENT-OFF* */ 1912 if (auto_breaking) { 1913 halfword prev_p = alink(cur_p); 1914 if (prev_p != temp_head && 1915 (is_char_node(prev_p) || 1916 precedes_break(prev_p) || 1917 ((type(prev_p) == kern_node) 1918 && (subtype(prev_p) != explicit)))) { 1919 ext_try_break(0, unhyphenated_node, line_break_dir, pdf_adjust_spacing, 1920 par_shape_ptr, adj_demerits, 1921 tracing_paragraphs, pdf_protrude_chars, 1922 line_penalty, last_line_fit, 1923 double_hyphen_demerits, 1924 final_hyphen_demerits, first_p, cur_p); 1925 } 1926 } 1927 /* *INDENT-ON* */ 1928 check_shrinkage(glue_ptr(cur_p)); 1929 q = glue_ptr(cur_p); 1930 active_width[1] += width(q); 1931 active_width[2 + stretch_order(q)] += stretch(q); 1932 active_width[7] += shrink(q); 1933 break; 1934 case kern_node: 1935 if (subtype(cur_p) == explicit) { 1936 kern_break(); 1937 } else { 1938 active_width[1] += width(cur_p); 1939 if ((pdf_adjust_spacing > 1) && (subtype(cur_p) == normal)) { 1940 add_kern_stretch(active_width[8], cur_p); 1941 add_kern_shrink(active_width[9], cur_p); 1942 } 1943 } 1944 break; 1945 case disc_node: 1946 /* |select_disc|s are handled by the leading |init_disc| */ 1947 if (subtype(cur_p) == select_disc) 1948 break; 1949 /* Try to break after a discretionary fragment, then |goto done5|; */ 1950 /* The following code knows that discretionary texts contain 1951 only character nodes, kern nodes, box nodes, and rule 1952 nodes. This branch differs a bit from older engines because in LuaTeX we 1953 already have hyphenated the list. This means that we need to skip 1954 automatic disc nodes. Of better, we need to treat discretionaries 1955 and explicit hyphens always, even in the first pass (HH). */ 1956 if (second_pass || subtype(cur_p) <= automatic_disc) { 1957 int actual_penalty = hyphen_penalty; 1958 if (subtype(cur_p) == automatic_disc) 1959 actual_penalty = ex_hyphen_penalty; 1960 s = vlink_pre_break(cur_p); 1961 do_one_seven_eight(reset_disc_width); 1962 if (s == null) { /* trivial pre-break */ 1963 ext_try_break(actual_penalty, hyphenated_node, 1964 line_break_dir, pdf_adjust_spacing, 1965 par_shape_ptr, adj_demerits, 1966 tracing_paragraphs, pdf_protrude_chars, 1967 line_penalty, last_line_fit, 1968 double_hyphen_demerits, 1969 final_hyphen_demerits, first_p, cur_p); 1970 } else { 1971 add_to_widths(s, line_break_dir, pdf_adjust_spacing, 1972 disc_width); 1973 do_one_seven_eight(add_disc_width_to_active_width); 1974 ext_try_break(actual_penalty, hyphenated_node, 1975 line_break_dir, pdf_adjust_spacing, 1976 par_shape_ptr, adj_demerits, 1977 tracing_paragraphs, pdf_protrude_chars, 1978 line_penalty, last_line_fit, 1979 double_hyphen_demerits, 1980 final_hyphen_demerits, first_p, cur_p); 1981 if (subtype(cur_p) == init_disc) { 1982 /* we should at two break points after the one we 1983 added above: 1984 \item1 which does a possible break in INIT's |post_break| 1985 \item2 which means the |no_break| actually was broken 1986 just a character later */ 1987 /* do the select-0 case 'f-f-i' */ 1988 assert(type(vlink(cur_p)) == disc_node && 1989 subtype(vlink(cur_p)) == select_disc); 1990 s = vlink_pre_break(vlink(cur_p)); 1991 add_to_widths(s, line_break_dir, pdf_adjust_spacing, 1992 disc_width); 1993 ext_try_break(actual_penalty, hyphenated_node, 1994 line_break_dir, pdf_adjust_spacing, 1995 par_shape_ptr, adj_demerits, 1996 tracing_paragraphs, 1997 pdf_protrude_chars, line_penalty, 1998 last_line_fit, double_hyphen_demerits, 1999 final_hyphen_demerits, first_p, 2000 vlink(cur_p)); 2001#if 0 2002 /* TODO this does not work */ 2003 /* go back to the starting situation */ 2004 do_one_seven_eight 2005 (sub_disc_width_from_active_width); 2006 do_one_seven_eight(reset_disc_width); 2007 /* add select |no_break| to |active_width| */ 2008 s = vlink_no_break(vlink(cur_p)); 2009 add_to_widths(s, line_break_dir, pdf_adjust_spacing, 2010 disc_width); 2011 ext_try_break(actual_penalty, hyphenated_node, 2012 line_break_dir, pdf_adjust_spacing, 2013 par_shape_ptr, adj_demerits, 2014 tracing_paragraphs, 2015 pdf_protrude_chars, line_penalty, 2016 last_line_fit, double_hyphen_demerits, 2017 final_hyphen_demerits, first_p, 2018 vlink(cur_p)); 2019#endif 2020 } 2021 do_one_seven_eight(sub_disc_width_from_active_width); 2022 } 2023 } 2024 s = vlink_no_break(cur_p); 2025 add_to_widths(s, line_break_dir, pdf_adjust_spacing, 2026 active_width); 2027 break; 2028 case math_node: 2029 auto_breaking = (subtype(cur_p) == after); 2030 kern_break(); 2031 break; 2032 case penalty_node: 2033 ext_try_break(penalty(cur_p), unhyphenated_node, line_break_dir, 2034 pdf_adjust_spacing, par_shape_ptr, adj_demerits, 2035 tracing_paragraphs, pdf_protrude_chars, 2036 line_penalty, last_line_fit, 2037 double_hyphen_demerits, final_hyphen_demerits, 2038 first_p, cur_p); 2039 break; 2040 case mark_node: 2041 case ins_node: 2042 case adjust_node: 2043 break; 2044 case glue_spec_node: 2045 fprintf(stdout, "\nfound a glue_spec in a paragraph!"); 2046 break; 2047 default: 2048 fprintf(stdout, "\ntype=%d", type(cur_p)); 2049 confusion("paragraph"); 2050 } 2051 cur_p = vlink(cur_p); 2052 while (cur_p == null && nest_index > 0) { 2053 cur_p = nest_stack[--nest_index]; 2054#ifdef DEBUG 2055 fprintf(stderr,"Node Pop %d [%d]\n",nest_index,(int)cur_p); 2056#endif 2057 } 2058 } 2059 if (cur_p == null) { 2060 /* Try the final line break at the end of the paragraph, 2061 and |goto done| if the desired breakpoints have been found */ 2062 2063 /* The forced line break at the paragraph's end will reduce the list of 2064 breakpoints so that all active nodes represent breaks at |cur_p=null|. 2065 On the first pass, we insist on finding an active node that has the 2066 correct ``looseness.'' On the final pass, there will be at least one active 2067 node, and we will match the desired looseness as well as we can. 2068 2069 The global variable |best_bet| will be set to the active node for the best 2070 way to break the paragraph, and a few other variables are used to 2071 help determine what is best. 2072 */ 2073 2074 ext_try_break(eject_penalty, hyphenated_node, line_break_dir, 2075 pdf_adjust_spacing, par_shape_ptr, adj_demerits, 2076 tracing_paragraphs, pdf_protrude_chars, line_penalty, 2077 last_line_fit, double_hyphen_demerits, 2078 final_hyphen_demerits, first_p, cur_p); 2079 if (vlink(active) != active) { 2080 /* Find an active node with fewest demerits; */ 2081 r = vlink(active); 2082 fewest_demerits = awful_bad; 2083 do { 2084 if (type(r) != delta_node) { 2085 if (total_demerits(r) < fewest_demerits) { 2086 fewest_demerits = total_demerits(r); 2087 best_bet = r; 2088 } 2089 } 2090 r = vlink(r); 2091 } while (r != active); 2092 best_line = line_number(best_bet); 2093 2094 /* /Find an active node with fewest demerits; */ 2095 if (looseness == 0) 2096 goto DONE; 2097 /*Find the best active node for the desired looseness; */ 2098 2099 /* The adjustment for a desired looseness is a slightly more complicated 2100 version of the loop just considered. Note that if a paragraph is broken 2101 into segments by displayed equations, each segment will be subject to the 2102 looseness calculation, independently of the other segments. 2103 */ 2104 r = vlink(active); 2105 actual_looseness = 0; 2106 do { 2107 if (type(r) != delta_node) { 2108 line_diff = line_number(r) - best_line; 2109 if (((line_diff < actual_looseness) 2110 && (looseness <= line_diff)) 2111 || ((line_diff > actual_looseness) 2112 && (looseness >= line_diff))) { 2113 best_bet = r; 2114 actual_looseness = line_diff; 2115 fewest_demerits = total_demerits(r); 2116 } else if ((line_diff == actual_looseness) && 2117 (total_demerits(r) < fewest_demerits)) { 2118 best_bet = r; 2119 fewest_demerits = total_demerits(r); 2120 } 2121 } 2122 r = vlink(r); 2123 } while (r != active); 2124 best_line = line_number(best_bet); 2125 2126 /* /Find the best active node for the desired looseness; */ 2127 if ((actual_looseness == looseness) || final_pass) 2128 goto DONE; 2129 } 2130 } 2131 2132 /* Clean up the memory by removing the break nodes; */ 2133 clean_up_the_memory(); 2134 /* /Clean up the memory by removing the break nodes; */ 2135 2136 if (!second_pass) { 2137 if (tracing_paragraphs > 0) 2138 tprint_nl("@@secondpass"); 2139 threshold = tolerance; 2140 second_pass = true; 2141 final_pass = (emergency_stretch <= 0); 2142 } else { /* if at first you do not succeed, \dots */ 2143 if (tracing_paragraphs > 0) 2144 tprint_nl("@@emergencypass"); 2145 background[2] += emergency_stretch; 2146 final_pass = true; 2147 } 2148 } 2149 2150 DONE: 2151 if (tracing_paragraphs > 0) { 2152 end_diagnostic(true); 2153 normalize_selector(); 2154 } 2155 if (do_last_line_fit) { 2156 /* Adjust the final line of the paragraph; */ 2157 /* Here we either reset |do_last_line_fit| or adjust the |par_fill_skip| glue. 2158 */ 2159 if (active_short(best_bet) == 0) { 2160 do_last_line_fit = false; 2161 } else { 2162 q = new_spec(glue_ptr(last_line_fill)); 2163 delete_glue_ref(glue_ptr(last_line_fill)); 2164 width(q) += (active_short(best_bet) - active_glue(best_bet)); 2165 stretch(q) = 0; 2166 glue_ptr(last_line_fill) = q; 2167 } 2168 } 2169 2170 /* Break the paragraph at the chosen...; */ 2171 /* Once the best sequence of breakpoints has been found (hurray), we call on the 2172 procedure |post_line_break| to finish the remainder of the work. 2173 (By introducing this subprocedure, we are able to keep |line_break| 2174 from getting extremely long.) 2175 */ 2176 2177 /* first thing |ext_post_line_break| does is reset |dir_ptr| */ 2178 flush_node_list(dir_ptr); 2179 dir_ptr = null; 2180 ext_post_line_break(paragraph_dir, 2181 right_skip, 2182 left_skip, 2183 pdf_protrude_chars, 2184 par_shape_ptr, 2185 pdf_adjust_spacing, 2186 pdf_each_line_height, 2187 pdf_each_line_depth, 2188 pdf_first_line_height, 2189 pdf_last_line_depth, 2190 inter_line_penalties_ptr, 2191 inter_line_penalty, 2192 club_penalty, 2193 club_penalties_ptr, 2194 widow_penalties_ptr, 2195 widow_penalty, 2196 broken_penalty, 2197 final_par_glue, 2198 best_bet, 2199 last_special_line, 2200 second_width, 2201 second_indent, first_width, first_indent, best_line, 2202 pdf_ignored_dimen); 2203 /* /Break the paragraph at the chosen... */ 2204 /* Clean up the memory by removing the break nodes; */ 2205 clean_up_the_memory(); 2206} 2207 2208@ @c 2209void get_linebreak_info (int *f, int *a) 2210{ 2211 *f = fewest_demerits; 2212 *a = actual_looseness; 2213} 2214