nx_hyphen.nx source
↩ module page · 285 lines · 13624 B
1// nx_hyphen.nx -- LIANG HYPHENATION (the algorithm behind TeX's \hyphenation), integer-exact.
2//
3// WHY: nx_kp_break optimises the breakpoints it is GIVEN. Knuth-Plass in TeX is strictly stronger than the
4// version I shipped first, because TeX also gets to break INSIDE words -- hyphenation points are extra
5// candidate breaks fed into the same optimisation. Without them a narrow column has too few places to break
6// and even an optimal breaker is forced into loose lines. This organ supplies those points.
7//
8// HOW (Liang 1983): wrap the word in dots (".hyphenation."), slide every pattern over it, and where a pattern
9// matches, its digits vote on the inter-letter positions it covers. Each position takes the MAXIMUM vote it
10// receives. An ODD final value means "a break is allowed here", even means "not allowed". Odd/even rather
11// than a threshold is what lets a later, longer, more specific pattern VETO a shorter general one -- the
12// mechanism that makes the pattern set composable instead of order-dependent.
13//
14// ★ SCOPE, STATED PLAINLY RATHER THAN IMPLIED: TeX's English pattern file holds 4447 patterns. This organ
15// ships a SUBSET (see HY_PAT below). The gate therefore proves two DIFFERENT things and keeps them apart:
16// (a) the ALGORITHM is correct -- it reproduces the exact expected points for words the loaded patterns
17// cover, and it correctly refuses the ones they veto. That is a pass/fail claim.
18// (b) COVERAGE over a wider word list is REPORTED AS A NUMBER with no verdict attached, because a subset
19// cannot honestly be graded against a bar nobody calibrated.
20// Reporting (b) as a verdict is how a partial capability starts being counted as a whole one.
21//
22// nx_hyphen word <word> -- show the hyphenation points
23// nx_hyphen selftest -- the gate
24// license_tier: ORIGINAL
25import "nx_gate_verdict.nx"
26import "nx_syscalls.nx"
27
28const HY_MAXW: i64 = 64
29const HY_MAXPOS: i64 = 80
30const HY_NPAT: i64 = 41
31const HY_MIN_HEAD: i64 = 2 // never break with fewer than 2 letters before the hyphen (\lefthyphenmin)
32const HY_MIN_TAIL: i64 = 3 // ... nor fewer than 3 after (\righthyphenmin). TeX's English defaults.
33
34func hy_puts(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
35func hy_num(v: i64) -> i64 {
36 if v == 0 { sys_write(1, "0" as *u8, 1); return 0 }
37 var m: i64 = v
38 if m < 0 { sys_write(1, "-" as *u8, 1); m = 0 - m }
39 let t: *u8 = sys_mmap(32); var k: i64 = 0
40 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
41 let o: *u8 = sys_mmap(32); var w: i64 = 0; var q: i64 = k - 1
42 while q >= 0 { o[w] = t[q]; w = w + 1; q = q - 1 }
43 sys_write(1, o, w); return 0
44}
45func hy_slen(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } return n }
46func hy_seq(a: *u8, b: *u8) -> i64 {
47 var i: i64 = 0
48 while 1 == 1 { if (a[i] as i64) != (b[i] as i64) { return 0 } if (a[i] as i64) == 0 { return 1 } i = i + 1 }
49 return 0
50}
51
52// A REAL subset of TeX's hyphen.tex, verbatim. '.' anchors a word boundary; digits are the votes.
53func hy_pattern(i: i64) -> *u8 {
54 if i == 0 { return "hy3ph" as *u8 }
55 if i == 1 { return "he2n" as *u8 }
56 if i == 2 { return "hena4" as *u8 }
57 if i == 3 { return "4hena" as *u8 }
58 if i == 4 { return "2io" as *u8 }
59 if i == 5 { return "o2n" as *u8 }
60 if i == 6 { return "1na" as *u8 }
61 if i == 7 { return "n2at" as *u8 }
62 if i == 8 { return "1tio" as *u8 }
63 if i == 9 { return "2ti2o" as *u8 }
64 if i == 10 { return "n1c" as *u8 }
65 if i == 11 { return "3ca" as *u8 }
66 if i == 12 { return "1ci" as *u8 }
67 if i == 13 { return "2l1m" as *u8 }
68 if i == 14 { return "1mu" as *u8 }
69 if i == 15 { return "u1ta" as *u8 }
70 if i == 16 { return "4ne1ous" as *u8 }
71 if i == 17 { return "1pu" as *u8 }
72 if i == 18 { return "1te" as *u8 }
73 if i == 19 { return "2t1er" as *u8 }
74 if i == 20 { return "1ra" as *u8 }
75 if i == 21 { return "1ry" as *u8 }
76 if i == 22 { return "4l1i" as *u8 }
77 if i == 23 { return "1li4ty" as *u8 }
78 if i == 24 { return "1bi" as *u8 }
79 if i == 25 { return "a1bl" as *u8 }
80 if i == 26 { return "2b1le" as *u8 }
81 if i == 27 { return "1su" as *u8 }
82 if i == 28 { return "2s1tr" as *u8 }
83 if i == 29 { return "1de" as *u8 }
84 if i == 30 { return "2d1er" as *u8 }
85 if i == 31 { return "1pe" as *u8 }
86 if i == 32 { return "2p1er" as *u8 }
87 if i == 33 { return "1fi" as *u8 }
88 if i == 34 { return "1ga" as *u8 }
89 if i == 35 { return "1ve" as *u8 }
90 if i == 36 { return "e1ment" as *u8 }
91 if i == 37 { return "2m1ent" as *u8 }
92 if i == 38 { return ".un1" as *u8 }
93 if i == 39 { return "3ing" as *u8 }
94 // hen5at is the pattern that actually produces the SECOND break in Liang's worked example. Without it
95 // the word came back "hy-phenation" -- the algorithm was right and the pattern set was short. Keeping
96 // those two failure causes distinguishable is the whole reason the gate separates correctness from
97 // coverage: a missing pattern must never read as a broken implementation.
98 if i == 40 { return "hen5at" as *u8 }
99 return "" as *u8
100}
101
102// lowercase copy of word wrapped in dots -> work[]; returns its length.
103func hy_prepare(word: *u8, work: *u8) -> i64 {
104 var o: i64 = 0
105 work[o] = 46 as u8; o = o + 1
106 var i: i64 = 0
107 while word[i] != (0 as u8) {
108 if o >= HY_MAXW - 2 { break }
109 var c: i64 = word[i] as i64
110 if c >= 65 { if c <= 90 { c = c + 32 } }
111 work[o] = c as u8; o = o + 1
112 i = i + 1
113 }
114 work[o] = 46 as u8; o = o + 1
115 work[o] = 0 as u8
116 return o
117}
118
119// Apply every pattern; pos[k] ends up holding the winning vote BETWEEN work[k-1] and work[k].
120func hy_apply(work: *u8, wn: i64, pos: *i64) -> i64 {
121 var k: i64 = 0
122 while k <= wn { pos[k] = 0; k = k + 1 }
123 var p: i64 = 0
124 while p < HY_NPAT {
125 let pat: *u8 = hy_pattern(p)
126 let pl: i64 = hy_slen(pat)
127 if pl > 0 {
128 // strip digits out of the pattern to get the letters it matches on, remembering each digit's slot
129 let letters: *u8 = sys_mmap(HY_MAXW)
130 let digits: *i64 = sys_mmap(8 * HY_MAXW) as *i64
131 var li: i64 = 0
132 var d: i64 = 0
133 while d <= HY_MAXW - 1 { digits[d] = 0; d = d + 1 }
134 var q: i64 = 0
135 while q < pl {
136 let c: i64 = pat[q] as i64
137 if c >= 48 { if c <= 57 { digits[li] = c - 48; q = q + 1 } }
138 if q < pl {
139 let c2: i64 = pat[q] as i64
140 var isdig: i64 = 0
141 if c2 >= 48 { if c2 <= 57 { isdig = 1 } }
142 if isdig == 0 { letters[li] = c2 as u8; li = li + 1; q = q + 1 }
143 }
144 }
145 letters[li] = 0 as u8
146 // slide it over the dotted word
147 var s: i64 = 0
148 while s + li <= wn {
149 var hit: i64 = 1
150 var t: i64 = 0
151 while t < li { if (work[s+t] as i64) != (letters[t] as i64) { hit = 0; break } t = t + 1 }
152 if hit == 1 {
153 var g: i64 = 0
154 while g <= li {
155 let at: i64 = s + g
156 if at <= wn { if digits[g] > pos[at] { pos[at] = digits[g] } }
157 g = g + 1
158 }
159 }
160 s = s + 1
161 }
162 }
163 p = p + 1
164 }
165 return 0
166}
167
168// Emit the word with '-' at every legal break. Returns the number of break points found.
169func hy_points(word: *u8, out: *u8) -> i64 {
170 let work: *u8 = sys_mmap(HY_MAXW)
171 let pos: *i64 = sys_mmap(8 * HY_MAXPOS) as *i64
172 let wn: i64 = hy_prepare(word, work)
173 hy_apply(work, wn, pos)
174 let letters: i64 = wn - 2
175 var o: i64 = 0
176 var n: i64 = 0
177 var i: i64 = 0
178 while i < letters {
179 out[o] = work[i + 1]; o = o + 1
180 // the gap AFTER letter i corresponds to work index i+2
181 let v: i64 = pos[i + 2]
182 var odd: i64 = 0
183 if (v % 2) == 1 { odd = 1 }
184 // \lefthyphenmin / \righthyphenmin: a hyphen with one letter stranded either side is worse than a
185 // loose line, so these are hard limits rather than preferences.
186 let before: i64 = i + 1
187 let after: i64 = letters - before
188 if before < HY_MIN_HEAD { odd = 0 }
189 if after < HY_MIN_TAIL { odd = 0 }
190 if odd == 1 { if i < letters - 1 { out[o] = 45 as u8; o = o + 1; n = n + 1 } }
191 i = i + 1
192 }
193 out[o] = 0 as u8
194 return n
195}
196
197func hy_selftest() -> i64 {
198 gv_head("nx_hyphen -- is Liang's algorithm implemented correctly, and how far does the pattern set reach?" as *u8)
199 let ctr: *i64 = gv_ctr()
200 let buf: *u8 = sys_mmap(HY_MAXW * 2)
201
202 // (a) ALGORITHM CORRECTNESS -- pass/fail. These words are covered by the loaded patterns, and the
203 // expected output is the textbook result of Liang's own worked example.
204 hy_points("hyphenation" as *u8, buf)
205 hy_puts(" hyphenation -> " as *u8); hy_puts(buf); hy_puts("\n" as *u8)
206 var t1: i64 = 0
207 if hy_seq(buf, "hy-phen-ation" as *u8) == 1 { t1 = 1 }
208 gv_check("Liang's own worked example gives hy-phen-ation exactly" as *u8, t1, ctr)
209
210 // ODD-BEATS-EVEN is the mechanism, so it needs its own tooth: `hena4`/`4hena` exist precisely to VETO a
211 // break that shorter patterns would otherwise allow. If a threshold had been used instead of parity,
212 // this word would break wrongly and every composite pattern set would be order-dependent.
213 // The veto to test is he2n's: it puts an EVEN vote in the e|n gap, so "phe-nation" must NOT appear.
214 // (An earlier version of this tooth looked for "n-a" -- but that is a break TeX DOES make, so the tooth
215 // was asserting the opposite of the truth and would have failed the correct implementation.)
216 var vetoed: i64 = 1
217 var z: i64 = 0
218 while buf[z] != (0 as u8) {
219 if (buf[z] as i64) == 45 { if (buf[z-1] as i64) == 101 { if (buf[z+1] as i64) == 110 { vetoed = 0 } } }
220 z = z + 1
221 }
222 gv_check("he2n's even vote vetoes a break between e and n (parity, not a threshold)" as *u8, vetoed, ctr)
223
224 // MIN-HEAD / MIN-TAIL are correctness, not taste: a stranded letter is never acceptable.
225 let short_ok: *u8 = sys_mmap(HY_MAXW * 2)
226 hy_points("onto" as *u8, short_ok)
227 hy_puts(" onto -> " as *u8); hy_puts(short_ok); hy_puts("\n" as *u8)
228 var nostrand: i64 = 1
229 if (short_ok[1] as i64) == 45 { nostrand = 0 }
230 var zz: i64 = 0
231 var lastdash: i64 = 0 - 9
232 while short_ok[zz] != (0 as u8) { if (short_ok[zz] as i64) == 45 { lastdash = zz } zz = zz + 1 }
233 if lastdash > 0 { if zz - lastdash - 1 < HY_MIN_TAIL { nostrand = 0 } }
234 gv_check("no break strands fewer than 2 letters before or 3 after" as *u8, nostrand, ctr)
235
236 // NEG-CONTROL: a word the patterns do not cover must come back with NO breaks rather than guesses.
237 // A hyphenator that invents points is far worse than one that declines -- a wrong hyphen is a visible
238 // error in the text, while a missing one only costs a slightly looser line.
239 let none: *u8 = sys_mmap(HY_MAXW * 2)
240 let nb: i64 = hy_points("xqzwj" as *u8, none)
241 hy_puts(" xqzwj (uncovered) -> " as *u8); hy_puts(none); hy_puts(" breaks=" as *u8); hy_num(nb); hy_puts("\n" as *u8)
242 var declines: i64 = 0
243 if nb == 0 { declines = 1 }
244 gv_check("neg-control-uncovered-word: an unmatched word gets NO invented break points" as *u8, declines, ctr)
245
246 // (b) COVERAGE -- REPORTED, NEVER GRADED. A 40-pattern subset of 4447 cannot be held to a bar nobody
247 // calibrated, and dressing a subset in a GREEN verdict is how partial capability gets counted as whole.
248 let words: *i64 = sys_mmap(8 * 12) as *i64
249 words[0] = "hyphenation" as i64
250 words[1] = "computer" as i64
251 words[2] = "algorithm" as i64
252 words[3] = "typography" as i64
253 words[4] = "document" as i64
254 words[5] = "management" as i64
255 words[6] = "unstructured" as i64
256 words[7] = "probability" as i64
257 var withbreaks: i64 = 0
258 var i: i64 = 0
259 hy_puts(" coverage sample (REPORTED, not graded):\n" as *u8)
260 while i < 8 {
261 let n: i64 = hy_points(words[i] as *u8, buf)
262 hy_puts(" " as *u8); hy_puts(buf); hy_puts(" breaks=" as *u8); hy_num(n); hy_puts("\n" as *u8)
263 if n > 0 { withbreaks = withbreaks + 1 }
264 i = i + 1
265 }
266 hy_puts(" COVERAGE: " as *u8); hy_num(withbreaks); hy_puts(" of 8 words got at least one break, from " as *u8)
267 hy_num(HY_NPAT); hy_puts(" of TeX's 4447 patterns. This figure carries NO verdict.\n" as *u8)
268
269 return gv_verdict("HYPHEN" as *u8, ctr, "Liang parity-vote algorithm proven correct; pattern coverage reported as a subset, not graded" as *u8)
270}
271
272func main(argc: i64, argv: *i64) -> i64 {
273 if argc < 2 { hy_puts("usage: nx_hyphen word <word> | selftest\n" as *u8); sys_exit(2); return 2 }
274 let verb: *u8 = argv[1] as *u8
275 if hy_seq(verb, "selftest" as *u8) == 1 { let rc: i64 = hy_selftest(); sys_exit(rc); return rc }
276 if hy_seq(verb, "word" as *u8) == 1 {
277 if argc < 3 { hy_puts("usage: nx_hyphen word <word>\n" as *u8); sys_exit(2); return 2 }
278 let buf: *u8 = sys_mmap(HY_MAXW * 2)
279 let n: i64 = hy_points(argv[2] as *u8, buf)
280 hy_puts("HYPHEN " as *u8); hy_puts(buf); hy_puts(" points=" as *u8); hy_num(n); hy_puts("\n" as *u8)
281 sys_exit(0); return 0
282 }
283 hy_puts("usage: nx_hyphen word <word> | selftest\n" as *u8)
284 sys_exit(2); return 2
285}