330  PART 40: PRE-HYPHENATION  TEX82 §891

891. Pre-hyphenation. When the line-breaking routine is unable to find a feasible sequence of breakpoints, it makes a second pass over the paragraph, attempting to hyphenate the hyphenatable words. The goal of hyphenation is to insert discretionary material into the paragraph so that there are more potential places to break.

The general rules for hyphenation are somewhat complex and technical, because we want to be able to hyphenate words that are preceded or followed by punctuation marks, and because we want the rules to work for languages other than English. We also must contend with the fact that hyphens might radically alter the ligature and kerning structure of a word.

A sequence of characters will be considered for hyphenation only if it belongs to a “potentially hyphenatable part” of the current paragraph. This is a sequence of nodes p_{0}p_{1} … p_{m} where p_{0} is a glue node, p_{1} … p_{m−1} are either character or ligature or whatsit or implicit kern nodes, and p_{m} is a glue or penalty or insertion or adjust or mark or whatsit or explicit kern node. (Therefore hyphenation is disabled by boxes, math formulas, and discretionary nodes already inserted by the user.) The ligature nodes among p_{1} … p_{m−1} are effectively expanded into the original non-ligature characters; the kern nodes and whatsits are ignored. Each character c is now classified as either a nonletter (if lc code(c) = 0), a lowercase letter (if lc code(c) = c), or an uppercase letter (otherwise); an uppercase letter is treated as if it were lc code(c) for purposes of hyphenation. The characters generated by p_{1} … p_{m−1} may begin with nonletters; let c_{1} be the first letter that is not in the middle of a ligature. Whatsit nodes preceding c_{1} are ignored; a whatsit found after c_{1} will be the terminating node p_{m}. All characters that do not have the same font as c_{1} will be treated as nonletters. The hyphen char for that font must be between 0 and 255, otherwise hyphenation will not be attempted. TEX looks ahead for as many consecutive letters c_{1} … c_{n} as possible; however, n must be less than 64, so a character that would otherwise be c_{64} is effectively not a letter. Furthermore c_{n} must not be in the middle of a ligature. In this way we obtain a string of letters c_{1} … c_{n} that are generated by nodes p_{a} … p_{b}, where 1 ≤ a ≤ b + 1 ≤ m. If n ≥ l hyf + r hyf , this string qualifies for hyphenation; however, uc hyph must be positive, if c_{1} is uppercase.

The hyphenation process takes place in three stages. First, the candidate sequence c_{1} … c_{n} is found; then potential positions for hyphens are determined by referring to hyphenation tables; and finally, the nodes p_{a} … p_{b} are replaced by a new sequence of nodes that includes the discretionary breaks found.

Fortunately, we do not have to do all this calculation very often, because of the way it has been taken out of TEX’s inner loop. For example, when the second edition of the author’s 700-page book Seminumerical Algorithms was typeset by TEX, only about 1.2 hyphenations needed to be tried per paragraph, since the line breaking algorithm needed to use two passes on only about 5 per cent of the paragraphs. ⟨ Initialize for hyphenating a paragraph 891 ⟩ ≡

begin init if trie not ready then init trie;

tini

cur lang ← init cur lang ; l hyf ← init l hyf ; r hyf ← init r hyf ;

end

This code is used in section 863.

§892  TEX82  PART 40: PRE-HYPHENATION 331

892. The letters c_{1} … c_{n} that are candidates for hyphenation are placed into an array called hc; the number n is placed into hn; pointers to nodes p_{a−1} and p_{b} in the description above are placed into variables ha and hb; and the font number is placed into hf . ⟨ Global variables 13 ⟩ +≡ hc: array [0 . . 65] of 0 . . 256; { word to be hyphenated } hn: small number ; { the number of positions occupied in hc } ha, hb: pointer ; { nodes ha . . hb should be replaced by the hyphenated result } hf : internal font number ; { font number of the letters in hc } hu: array [0 . . 63] of 0 . . 256; { like hc, before conversion to lowercase } hyf char : integer ; { hyphen character of the relevant font } cur lang , init cur lang : ASCII code; { current hyphenation table of interest } l hyf , r hyf , init l hyf , init r hyf : integer ; { limits on fragment sizes } hyf bchar : halfword ; { boundary character after c_{n} }

893. Hyphenation routines need a few more local variables. ⟨ Local variables for line breaking 862 ⟩ +≡ j: small number ; { an index into hc or hu } c: 0 . . 255; { character being considered for hyphenation }

894. When the following code is activated, the line break procedure is in its second pass, and cur p points to a glue node. ⟨ Try to hyphenate the following word 894 ⟩ ≡

begin prev s ← cur p; s ← link (prev s );

if s ≠ null then begin ⟨ Skip to node ha, or goto done1 if no hyphenation should be attempted 896 ⟩; if l hyf + r hyf > 63 then goto done1 ; ⟨ Skip to node hb, putting letters into hu and hc 897 ⟩; ⟨ Check that the nodes following hb permit hyphenation and that at least l hyf + r hyf letters have

been found, otherwise goto done1 899 ⟩; hyphenate; end;

done1 : end

This code is used in section 866.

895. ⟨ Declare subprocedures for line break 826 ⟩ +≡ ⟨ Declare the function called reconstitute 906 ⟩ procedure hyphenate;

label common ending , done, found , found1 , found2 , not found , exit ;

var ⟨ Local variables for hyphenation 901 ⟩

begin ⟨ Find hyphen locations for the word in hc, or return 923 ⟩;

⟨ If no hyphens were found, return 902 ⟩;

⟨ Replace nodes ha . . hb by a sequence of nodes that includes the discretionary hyphens 903 ⟩; exit : end; 896. The first thing we need to do is find the node ha just before the first letter. ⟨ Skip to node ha, or goto done1 if no hyphenation should be attempted 896 ⟩ ≡

loop begin if is char node(s) then begin c ← qo(character (s)); hf ← font (s); end

else if type(s) = ligature node then if lig ptr (s) = null then goto continue else begin q ← lig ptr (s); c ← qo(character (q)); hf ← font (q);

end else if (type(s) = kern node) ∧ (subtype(s) = normal ) then goto continue

else if type(s) = whatsit node then begin ⟨ Advance past a whatsit node in the pre-hyphenation loop 1363 ⟩; goto continue; end

else goto done1 ; if lc code(c) ≠ 0 then

if (lc code(c) = c) ∨ (uc hyph > 0) then goto done2 else goto done1 ;

continue: prev s ← s; s ← link (prev s );

end; done2 : hyf char ← hyphen char [hf ];

if hyf char < 0 then goto done1 ; if hyf char > 255 then goto done1 ; ha ← prev s

This code is used in section 894.

897. The word to be hyphenated is now moved to the hu and hc arrays. ⟨ Skip to node hb, putting letters into hu and hc 897 ⟩ ≡

hn ← 0; loop begin if is char node(s) then

begin if font (s) ≠ hf then goto done3 ; hyf bchar ← character (s); c ← qo(hyf bchar ); if lc code(c) = 0 then goto done3 ; if hn = 63 then goto done3 ; hb ← s; incr (hn); hu[hn] ← c; hc[hn] ← lc code(c); hyf bchar ← non char ; end

else if type(s) = ligature node then ⟨ Move the characters of a ligature node to hu and hc; but goto

done3 if they are not all letters 898 ⟩ else if (type(s) = kern node) ∧ (subtype(s) = normal ) then

begin hb ← s; hyf bchar ← font bchar [hf ]; end

else goto done3 ; s ← link (s); end;

done3 :

This code is used in section 894.

898. We let j be the index of the character being stored when a ligature node is being expanded, since we do not want to advance hn until we are sure that the entire ligature consists of letters. Note that it is possible to get to done3 with hn = 0 and hb not set to any value. ⟨ Move the characters of a ligature node to hu and hc; but goto done3 if they are not all letters 898 ⟩ ≡

begin if font (lig char (s)) ≠ hf then goto done3 ; j ← hn; q ← lig ptr (s); if q > null then hyf bchar ← character (q); while q > null do

begin c ← qo(character (q));

if lc code(c) = 0 then goto done3 ; if j = 63 then goto done3 ; incr (j); hu[j] ← c; hc[j] ← lc code(c); q ← link (q); end;

hb ← s; hn ← j; if odd (subtype(s)) then hyf bchar ← font bchar [hf ] else hyf bchar ← non char ; end

This code is used in section 897.

899. ⟨ Check that the nodes following hb permit hyphenation and that at least l hyf + r hyf letters have

been found, otherwise goto done1 899 ⟩ ≡ if hn < l hyf + r hyf then goto done1 ; { l hyf and r hyf are ≥ 1 } loop begin if ¬(is char node(s)) then

case type(s) of

ligature node: do nothing ;

kern node: if subtype(s) ≠ normal then goto done4 ;

whatsit node, glue node, penalty node, ins node, adjust node, mark node: goto done4 ;

othercases goto done1

endcases; s ← link (s); end;

done4 :

This code is used in section 894.