334  PART 41: POST-HYPHENATION  TEX82 §900

900. Post-hyphenation. If a hyphen may be inserted between hc[j] and hc[j + 1], the hyphenation procedure will set hyf [j] to some small odd number. But before we look at TEX’s hyphenation procedure, which is independent of the rest of the line-breaking algorithm, let us consider what we will do with the hyphens it finds, since it is better to work on this part of the program before forgetting what ha and hb, etc., are all about. ⟨ Global variables 13 ⟩ +≡ hyf : array [0 . . 64] of 0 . . 9; { odd values indicate discretionary hyphens } init list : pointer ; { list of punctuation characters preceding the word } init lig : boolean; { does init list represent a ligature? } init lft : boolean; { if so, did the ligature involve a left boundary? }

901. ⟨ Local variables for hyphenation 901 ⟩ ≡ i, j, l: 0 . . 65; { indices into hc or hu } q, r, s: pointer ; { temporary registers for list manipulation } bchar : halfword ; { right boundary character of hyphenated word, or non char }

See also sections 912, 922, and 929. This code is used in section 895.

902. TEX will never insert a hyphen that has fewer than letters before it or fewer than after it; hence, a short word has comparatively little chance of being hyphenated. If no hyphens have been found, we can save time by not having to make any changes to the paragraph. ⟨ If no hyphens were found, return 902 ⟩ ≡

for j ← l hyf to hn − r hyf do

if odd (hyf [j]) then goto found1 ; return;

found1 :

This code is used in section 895.

§903  TEX82  PART 41: POST-HYPHENATION 335

903. If hyphens are in fact going to be inserted, TEX first deletes the subsequence of nodes between ha and hb. An attempt is made to preserve the effect that implicit boundary characters and punctuation marks had on ligatures inside the hyphenated word, by storing a left boundary or preceding character in hu[0] and by storing a possible right boundary in bchar . We set j ← 0 if hu[0] is to be part of the reconstruction; otherwise j ← 1. The variable s will point to the tail of the current hlist, and q will point to the node following hb, so that things can be hooked up after we reconstitute the hyphenated word. ⟨ Replace nodes ha . . hb by a sequence of nodes that includes the discretionary hyphens 903 ⟩ ≡

q ← link (hb); link (hb) ← null ; r ← link (ha); link (ha) ← null ; bchar ← hyf bchar ;

if is char node(ha) then if font (ha) ≠ hf then goto found2 else begin init list ← ha; init lig ← false; hu[0] ← qo(character (ha));

end else if type(ha) = ligature node then

if font (lig char (ha)) ≠ hf then goto found2

else begin init list ← lig ptr (ha); init lig ← true; init lft ← (subtype(ha) > 1); hu[0] ← qo(character (lig char (ha))); if init list = null then

if init lft then

begin hu[0] ← 256; init lig ← false;

end; { in this case a ligature will be reconstructed from scratch } free node(ha, small node size); end

else begin { no punctuation found; look for left boundary }

if ¬is char node(r) then

if type(r) = ligature node then

if subtype(r) > 1 then goto found2 ; j ← 1; s ← ha; init list ← null ; goto common ending ; end;

s ← cur p; { we have cur p ≠ ha because type(cur p) = glue node }

while link (s) ≠ ha do s ← link (s);

j ← 0; goto common ending ; found2 : s ← ha; j ← 0; hu[0] ← 256; init lig ← false; init list ← null ; common ending : flush node list (r);

⟨ Reconstitute nodes for the hyphenated word, inserting discretionary hyphens 913 ⟩;

flush list (init list )

This code is used in section 895.

904. We must now face the fact that the battle is not over, even though the hyphens have been found: The process of reconstituting a word can be nontrivial because ligatures might change when a hyphen is present. The TEXbook discusses the difficulties of the word “difficult”, and the discretionary material surrounding a hyphen can be considerably more complex than that. Suppose is a word in a font for which the only ligatures are , , , and . If this word permits hyphenation between and , the two patterns with and without hyphenation are and . Thus the insertion of a hyphen might cause effects to ripple arbitrarily far into the rest of the word. A further complication arises if additional hyphens appear together with such rippling, e.g., if the word in the example just given could also be hyphenated between and ; TEX avoids this by simply ignoring the additional hyphens in such weird cases.

Still further complications arise in the presence of ligatures that do not delete the original characters. When punctuation precedes the word being hyphenated, TEX’s method is not perfect under all possible scenarios, because punctuation marks and letters can propagate information back and forth. For example, suppose the original pre-hyphenation pair changes to via a ligature, which changes to via a ligature; if p_{a−1} = and p_{a} = , the reconstitution procedure isn’t smart enough to obtain again. In such cases the font designer should include a ligature that goes from to .

905. The processing is facilitated by a subroutine called reconstitute. Given a string of characters x_{j} … x_{n}, there is a smallest index m ≥ j such that the “translation” of x_{j} … x_{n} by ligatures and kerning has the form y_{1} … y_{t} followed by the translation of x_{m+1} … x_{n}, where y_{1} … y_{t} is some nonempty sequence of character, ligature, and kern nodes. We call x_{j} … x_{m} a “cut prefix” of x_{j} … x_{n}. For example, if x_{1}x_{2}x_{3} = , and if the font contains ‘fl’ as a ligature and a kern between ‘fl’ and ‘y’, then m = 2, y = 2, and y_{1} will be a ligature node for ‘fl’ followed by an appropriate kern node y_{2}. In the most common case, x_{j} forms no ligature with x_{j+1} and we simply have m = j, y_{1} = x_{j}. If m < n we can repeat the procedure on x_{m+1} … x_{n} until the entire translation has been found.

The reconstitute function returns the integer m and puts the nodes y_{1} … y_{t} into a linked list starting at link (hold head ), getting the input x_{j} … x_{n} from the hu array. If x_{j} = 256, we consider x_{j} to be an implicit left boundary character; in this case j must be strictly less than n. There is a parameter bchar , which is either 256 or an implicit right boundary character assumed to be present just following x_{n}. (The value hu[n + 1] is never explicitly examined, but the algorithm imagines that bchar is there.)

If there exists an index k in the range j ≤ k ≤ m such that hyf [k] is odd and such that the result of reconstitute would have been different if x_{k+1} had been hchar , then reconstitute sets hyphen passed to the smallest such k. Otherwise it sets hyphen passed to zero.

A special convention is used in the case j = 0: Then we assume that the translation of hu[0] appears in a special list of charnodes starting at init list ; moreover, if init lig is true, then hu[0] will be a ligature character, involving a left boundary if init lft is true. This facility is provided for cases when a hyphenated word is preceded by punctuation (like single or double quotes) that might affect the translation of the beginning of the word. ⟨ Global variables 13 ⟩ +≡ hyphen passed : small number ; { first hyphen in a ligature, if any }

906. ⟨ Declare the function called reconstitute 906 ⟩ ≡ function reconstitute(j, n : small number ; bchar , hchar : halfword ): small number ;

label continue, done;

var p: pointer ; { temporary register for list manipulation } t: pointer ; { a node being appended to } q: four quarters ; { character information or a lig/kern instruction } cur rh: halfword ; { hyphen character for ligature testing } test char : halfword ; { hyphen or other character for ligature testing } w: scaled ; { amount of kerning } k: font index ; { position of current lig/kern instruction }

begin hyphen passed ← 0; t ← hold head ; w ← 0; link (hold head ) ← null ;

{ at this point ligature present = lft hit = rt hit = false } ⟨ Set up data structures with the cursor following position j 908 ⟩;

continue: ⟨ If there’s a ligature or kern at the cursor position, update the data structures, possibly

advancing j; continue until the cursor moves 909 ⟩; ⟨ Append a ligature and/or kern to the translation; goto continue if the stack of inserted ligatures is

nonempty 910 ⟩; reconstitute ← j; end;

This code is used in section 895.

907. The reconstitution procedure shares many of the global data structures by which TEX has processed the words before they were hyphenated. There is an implied “cursor” between characters cur l and cur r ; these characters will be tested for possible ligature activity. If ligature present then cur l is a ligature character formed from the original characters following cur q in the current translation list. There is a “ligature stack” between the cursor and character j + 1, consisting of pseudo-ligature nodes linked together by their link fields. This stack is normally empty unless a ligature command has created a new character that will need to be processed later. A pseudo-ligature is a special node having a character field that represents a potential ligature and a lig ptr field that points to a char node or is null . We have

cur r = \{ \begin{matrix}character (lig stack ), & if lig stack > null ; \\ qi (hu[j+1]), & if lig stack = null and j < n; \\ bchar, & if lig stack = null and j = n. \end{matrix}

⟨ Global variables 13 ⟩ +≡ cur l , cur r : halfword ; { characters before and after the cursor } cur q : pointer ; { where a ligature should be detached } lig stack : pointer ; { unfinished business to the right of the cursor } ligature present : boolean; { should a ligature node be made for cur l ? } lft hit , rt hit : boolean; { did we hit a ligature with a boundary character? }

908. define append charnode to t (#) ≡ begin link (t) ← get avail ; t ← link (t); font (t) ← hf ; character (t) ← #; end

define set cur r ≡ begin if j < n then cur r ← qi (hu[j + 1]) else cur r ← bchar ; if odd (hyf [j]) then cur rh ← hchar else cur rh ← non char ; end

⟨ Set up data structures with the cursor following position j 908 ⟩ ≡ cur l ← qi (hu[j]); cur q ← t; if j = 0 then

begin ligature present ← init lig ; p ← init list ; if ligature present then lft hit ← init lft ; while p > null do

begin append charnode to t (character (p)); p ← link (p); end; end

else if cur l < non char then append charnode to t (cur l ); lig stack ← null ; set cur r

This code is used in section 906.

909. We may want to look at the lig/kern program twice, once for a hyphen and once for a normal letter. (The hyphen might appear after the letter in the program, so we’d better not try to look for both at once.) ⟨ If there’s a ligature or kern at the cursor position, update the data structures, possibly advancing j;

continue until the cursor moves 909 ⟩ ≡ if cur l = non char then

begin k ← bchar label [hf ]; if k = non address then goto done else q ← font info[k].qqqq ; end

else begin q ← char info(hf )(cur l ); if char tag (q) ≠ lig tag then goto done; k ← lig kern start (hf )(q); q ← font info[k].qqqq ; if skip byte(q) > stop flag then

begin k ← lig kern restart (hf )(q); q ← font info[k].qqqq ; end;

end; { now k is the starting address of the lig/kern program } if cur rh < non char then test char ← cur rh else test char ← cur r ; loop begin if next char (q) = test char then

if skip byte(q) ≤ stop flag then

if cur rh < non char then begin hyphen passed ← j; hchar ← non char ; cur rh ← non char ; goto continue; end

else begin if hchar < non char then

if odd (hyf [j]) then begin hyphen passed ← j; hchar ← non char ; end;

if op byte(q) < kern flag then

⟨ Carry out a ligature replacement, updating the cursor structure and possibly advancing j;

goto continue if the cursor doesn’t advance, otherwise goto done 911 ⟩; w ← char kern(hf )(q); goto done; { this kern will be inserted below } end;

if skip byte(q) ≥ stop flag then if cur rh = non char then goto done else begin cur rh ← non char ; goto continue;

end; k ← k + qo(skip byte(q)) + 1; q ← font info[k].qqqq ; end;

done:

This code is used in section 906.

910. define wrap lig (#) ≡

if ligature present then

begin p ← new ligature(hf , cur l , link (cur q ));

if lft hit then

begin subtype(p) ← 2; lft hit ← false; end;

if # then

if lig stack = null then begin incr (subtype(p)); rt hit ← false; end;

link (cur q ) ← p; t ← p; ligature present ← false; end

define pop lig stack ≡

begin if lig ptr (lig stack ) > null then begin link (t) ← lig ptr (lig stack ); { this is a charnode for hu[j + 1] } t ← link (t); incr (j); end;

p ← lig stack ; lig stack ← link (p); free node(p, small node size); if lig stack = null then set cur r else cur r ← character (lig stack ); end { if lig stack isn’t null we have cur rh = non char }

⟨ Append a ligature and/or kern to the translation; goto continue if the stack of inserted ligatures is

nonempty 910 ⟩ ≡ wrap lig (rt hit ); if w ≠ 0 then

begin link (t) ← new kern(w); t ← link (t); w ← 0; end;

if lig stack > null then begin cur q ← t; cur l ← character (lig stack ); ligature present ← true; pop lig stack ; goto continue; end

This code is used in section 906.

911. ⟨ Carry out a ligature replacement, updating the cursor structure and possibly advancing j; goto

continue if the cursor doesn’t advance, otherwise goto done 911 ⟩ ≡ begin if cur l = non char then lft hit ← true; if j = n then

if lig stack = null then rt hit ← true; check interrupt ; { allow a way out in case there’s an infinite ligature loop } case op byte(q) of qi (1), qi (5): begin cur l ← rem byte(q); { , }

ligature present ← true; end;

qi (2), qi (6): begin cur r ← rem byte(q); { . } if lig stack > null then character (lig stack ) ← cur r else begin lig stack ← new lig item(cur r );

if j = n then bchar ← non char

else begin p ← get avail ; lig ptr (lig stack ) ← p; character (p) ← qi (hu[j + 1]); font (p) ← hf ;

end; end;

end; qi (3): begin cur r ← rem byte(q); { }

p ← lig stack ; lig stack ← new lig item(cur r ); link (lig stack ) ← p; end;

qi (7), qi (11): begin wrap lig (false); { , } cur q ← t; cur l ← rem byte(q); ligature present ← true; end;

othercases begin cur l ← rem byte(q); ligature present ← true; { } if lig stack > null then pop lig stack else if j = n then goto done

else begin append charnode to t (cur r ); incr (j); set cur r ;

end; end

endcases; if op byte(q) > qi (4) then

if op byte(q) ≠ qi (7) then goto done; goto continue; end

This code is used in section 909.

912. Okay, we’re ready to insert the potential hyphenations that were found. When the following program is executed, we want to append the word hu[1 . . hn] after node ha, and node q should be appended to the result. During this process, the variable i will be a temporary index into hu; the variable j will be an index to our current position in hu; the variable l will be the counterpart of j, in a discretionary branch; the variable r will point to new nodes being created; and we need a few new local variables: ⟨ Local variables for hyphenation 901 ⟩ +≡ major tail , minor tail : pointer ;

{ the end of lists in the main and discretionary branches being reconstructed } c: ASCII code; { character temporarily replaced by a hyphen } c loc: 0 . . 63; { where that character came from } r count : integer ; { replacement count for discretionary } hyf node: pointer ; { the hyphen, if it exists } 913. When the following code is performed, hyf [0] and hyf [hn] will be zero. ⟨ Reconstitute nodes for the hyphenated word, inserting discretionary hyphens 913 ⟩ ≡

repeat l ← j; j ← reconstitute(j, hn, bchar , qi (hyf char )) + 1;

if hyphen passed = 0 then begin link (s) ← link (hold head ); while link (s) > null do s ← link (s); if odd (hyf [j − 1]) then

begin l ← j; hyphen passed ← j − 1; link (hold head ) ← null ; end; end;

if hyphen passed > 0 then ⟨ Create and append a discretionary node as an alternative to the

unhyphenated word, and continue to develop both branches until they become equivalent 914 ⟩;

until j > hn;

link (s) ← q

This code is used in section 903.

914. In this repeat loop we will insert another discretionary if hyf [j −1] is odd, when both branches of the previous discretionary end at position j − 1. Strictly speaking, we aren’t justified in doing this, because we don’t know that a hyphen after j − 1 is truly independent of those branches. But in almost all applications we would rather not lose a potentially valuable hyphenation point. (Consider the word ‘difficult’, where the letter ‘c’ is in position j.)

define advance major tail ≡ begin major tail ← link (major tail ); incr (r count ); end

⟨ Create and append a discretionary node as an alternative to the unhyphenated word, and continue to

develop both branches until they become equivalent 914 ⟩ ≡ repeat r ← get node(small node size); link (r) ← link (hold head ); type(r) ← disc node; major tail ← r;

r count ← 0;

while link (major tail ) > null do advance major tail ;

i ← hyphen passed ; hyf [i] ← 0; ⟨ Put the characters hu[l . . i] and a hyphen into pre break (r) 915 ⟩; ⟨ Put the characters hu[i + 1 . .] into post break (r), appending to this list and to major tail until

synchronization has been achieved 916 ⟩; ⟨ Move pointer s to the end of the current list, and set replace count (r) appropriately 918 ⟩; hyphen passed ← j − 1; link (hold head ) ← null ;

until ¬odd (hyf [j − 1])

This code is used in section 913.

915. The new hyphen might combine with the previous character via ligature or kern. At this point we have l − 1 ≤ i < j and i < hn. ⟨ Put the characters hu[l . . i] and a hyphen into pre break (r) 915 ⟩ ≡

minor tail ← null ; pre break (r) ← null ; hyf node ← new character (hf , hyf char ); if hyf node ≠ null then

begin incr (i); c ← hu[i]; hu[i] ← hyf char ; free avail (hyf node); end;

while l ≤ i do begin l ← reconstitute(l, i, font bchar [hf ], non char ) + 1; if link (hold head ) > null then

begin if minor tail = null then pre break (r) ← link (hold head )

else link (minor tail ) ← link (hold head );

minor tail ← link (hold head );

while link (minor tail ) > null do minor tail ← link (minor tail ); end;

end; if hyf node ≠ null then

begin hu[i] ← c; { restore the character in the hyphen position } l ← i; decr (i); end

This code is used in section 914.

916. The synchronization algorithm begins with l = i + 1 ≤ j. ⟨ Put the characters hu[i + 1 . .] into post break (r), appending to this list and to major tail until

synchronization has been achieved 916 ⟩ ≡ minor tail ← null ; post break (r) ← null ; c loc ← 0; if bchar label [hf ] ≠ non address then { put left boundary at beginning of new line }

begin decr (l); c ← hu[l]; c loc ← l; hu[l] ← 256; end;

while l < j do

begin repeat l ← reconstitute(l, hn, bchar , non char ) + 1;

if c loc > 0 then begin hu[c loc] ← c; c loc ← 0; end;

if link (hold head ) > null then begin if minor tail = null then post break (r) ← link (hold head ) else link (minor tail ) ← link (hold head ); minor tail ← link (hold head ); while link (minor tail ) > null do minor tail ← link (minor tail ); end;

until l ≥ j; while l > j do ⟨ Append characters of hu[j . .] to major tail , advancing j 917 ⟩; end

This code is used in section 914.

917. ⟨ Append characters of hu[j . .] to major tail , advancing j 917 ⟩ ≡ begin j ← reconstitute(j, hn, bchar , non char ) + 1; link (major tail ) ← link (hold head ); while link (major tail ) > null do advance major tail ; end

This code is used in section 916.

918. Ligature insertion can cause a word to grow exponentially in size. Therefore we must test the size of r count here, even though the hyphenated text was at most 63 characters long. ⟨ Move pointer s to the end of the current list, and set replace count (r) appropriately 918 ⟩ ≡

if r count > 127 then { we have to forget the discretionary hyphen } begin link (s) ← link (r); link (r) ← null ; flush node list (r); end

else begin link (s) ← r; replace count (r) ← r count ;

end; s ← major tail

This code is used in section 914.