coverage — ~bigbes/sr-ht-spec — 3cb1c03d — prosediff/token.go

Coverage
99.2% 128/129 statements
Δ
—
Blob
dc2f4eb
Uncovered L212-L213
1 package prosediff
2
3 import (
4 "strings"
5 "unicode"
6 "unicode/utf8"
7 )
8
9 // Token is one unit of the word-level diff.
10 //
11 // Whitespace is *not* a token. It survives only as Space, which records that
12 // some run of whitespace separated this token from the previous one. That is
13 // what makes reflow invisible: a paragraph rewrapped from 72 to 80 columns
14 // produces byte-for-byte the same token stream, because "\n" and " " both
15 // collapse to Space=true.
16 type Token struct {
17 Text string
18 Space bool
19 }
20
21 // Tokenize splits prose into words and punctuation.
22 //
23 // A word is a run of letters/digits, optionally joined by an internal
24 // apostrophe or hyphen ("don't", "word-level") or an internal dot between
25 // digits ("v5.19.1"). Every other non-space rune forms a token from its own
26 // repeated run, so "**" and "---" stay single tokens rather than exploding
27 // into markup noise.
28 548 func Tokenize(s string) []Token {
29 548 var out []Token
30 548 space := false
31 5379 for i := 0; i < len(s); {
32 5379 r, sz := utf8.DecodeRuneInString(s[i:])
33 5379 switch {
34 2283 case unicode.IsSpace(r):
35 2283 space = true
36 2283 i += sz
37 2675 case isWordRune(r):
38 2675 j := i
39 14654 for j < len(s) {
40 14654 r2, sz2 := utf8.DecodeRuneInString(s[j:])
41 14654 if isWordRune(r2) {
42 12275 j += sz2
43 12275 continue
44 }
45 2379 if isJoinRune(r2) && continuesWord(s, j+sz2, r2) {
46 71 j += sz2
47 71 continue
48 }
49 2308 break
50 }
51 2675 out = append(out, Token{Text: s[i:j], Space: space})
52 2675 space = false
53 2675 i = j
54 421 default:
55 421 j := i
56 703 for j < len(s) {
57 703 r2, sz2 := utf8.DecodeRuneInString(s[j:])
58 703 if r2 != r {
59 241 break
60 }
61 462 j += sz2
62 }
63 421 out = append(out, Token{Text: s[i:j], Space: space})
64 421 space = false
65 421 i = j
66 }
67 }
68 548 return out
69 }
70
71 17819 func isWordRune(r rune) bool {
72 17819 return unicode.IsLetter(r) || unicode.IsDigit(r) || r == '_'
73 17819 }
74
75 2379 func isJoinRune(r rune) bool { return r == '\'' || r == '-' || r == '.' || r == '’' }
76
77 // continuesWord reports whether the join rune at the previous position is
78 // followed by more word material (and, for a dot, by a digit — so "end." does
79 // not swallow the sentence terminator).
80 217 func continuesWord(s string, next int, join rune) bool {
81 217 if next >= len(s) {
82 127 return false
83 127 }
84 90 r, _ := utf8.DecodeRuneInString(s[next:])
85 90 if join == '.' {
86 21 return unicode.IsDigit(r)
87 21 }
88 69 return isWordRune(r)
89 }
90
91 // TokenTexts drops the spacing, leaving the comparable content.
92 327 func TokenTexts(toks []Token) []string {
93 327 out := make([]string, len(toks))
94 1956 for i, t := range toks {
95 1956 out[i] = t.Text
96 1956 }
97 327 return out
98 }
99
100 // Normalize collapses a block's source text to its token stream joined by
101 // single spaces. Two blocks with the same Normalize are the same prose,
102 // however they were wrapped.
103 205 func Normalize(s string) string {
104 205 return strings.Join(TokenTexts(Tokenize(s)), " ")
105 205 }
106
107 // Span is a run of word-level tokens sharing one Op, ready to render.
108 //
109 // Space says whether to emit a separating space before this span when the
110 // spans are rendered in order. An insertion that directly replaces a deletion
111 // carries Space=false, because the deletion before it already carried the
112 // separator; otherwise every one-word substitution would render as
113 // "[-old-] {+new+}".
114 type Span struct {
115 Op Op
116 Text string // tokens joined with single spaces
117 Space bool
118 }
119
120 // smallEqualRun is the character budget below which an unchanged run wedged
121 // between two changed runs is absorbed into the change. Without it, a rewrite
122 // that happens to keep a comma or an "a" produces shredded output like
123 // "[-x-]{+y+} , [-z-]{+w+}".
124 const smallEqualRun = 4
125
126 // DiffWords produces the inline edit script between two pieces of prose.
127 // Whitespace differences alone yield a single OpEqual span.
128 24 func DiffWords(oldText, newText string) []Span {
129 24 a := Tokenize(oldText)
130 24 b := Tokenize(newText)
131 24 in := newInterner()
132 24 script := diffInts(in.all(TokenTexts(a)), in.all(TokenTexts(b)))
133 24 script = absorbSmallEqualRuns(script, a)
134 24 return spans(deletesFirst(script), a, b)
135 24 }
136
137 // absorbSmallEqualRuns rewrites tiny equal runs that sit between two changed
138 // runs into delete+insert, so the surrounding change reads as one edit.
139 24 func absorbSmallEqualRuns(script []edit, a []Token) []edit {
140 24 if len(script) < 3 {
141 7 return script
142 7 }
143 // Position of each run in a, needed to measure the equal run's length.
144 17 posA := make([]int, len(script))
145 17 x := 0
146 69 for i, e := range script {
147 69 posA[i] = x
148 69 if e.op != OpInsert {
149 50 x += e.n
150 50 }
151 }
152 17 out := make([]edit, 0, len(script)+4)
153 69 for i, e := range script {
154 69 if e.op != OpEqual || i == 0 || i == len(script)-1 {
155 67 out = append(out, e)
156 67 continue
157 }
158 2 n := 0
159 4 for _, t := range a[posA[i] : posA[i]+e.n] {
160 4 n += len(t.Text)
161 4 }
162 2 if n >= smallEqualRun {
163 1 out = append(out, e)
164 1 continue
165 }
166 1 out = append(out, edit{OpDelete, e.n}, edit{OpInsert, e.n})
167 }
168 17 return coalesce(out)
169 }
170
171 // deletesFirst rewrites each changed region so all deletions precede all
172 // insertions, whichever order Myers happened to emit them in.
173 24 func deletesFirst(script []edit) []edit {
174 24 out := make([]edit, 0, len(script))
175 58 for i := 0; i < len(script); {
176 58 if script[i].op == OpEqual {
177 37 out = append(out, script[i])
178 37 i++
179 37 continue
180 }
181 21 del, ins := 0, 0
182 42 for ; i < len(script) && script[i].op != OpEqual; i++ {
183 42 if script[i].op == OpDelete {
184 20 del += script[i].n
185 22 } else {
186 22 ins += script[i].n
187 22 }
188 }
189 21 if del > 0 {
190 18 out = append(out, edit{OpDelete, del})
191 18 }
192 21 if ins > 0 {
193 20 out = append(out, edit{OpInsert, ins})
194 20 }
195 }
196 24 return out
197 }
198
199 // spans walks an edit script and materializes it into renderable runs.
200 24 func spans(script []edit, a, b []Token) []Span {
201 24 var out []Span
202 24 // space is passed in rather than read off toks[0] because an equal run
203 24 // exists on both sides at once and the two sides can disagree about the
204 24 // separator in front of it. A block that gains words at its head has
205 24 // Space=false on the old side's first token — nothing precedes it there —
206 24 // and Space=true on the new side's, where the inserted words do. Reading
207 24 // only the old side emitted "{+two words+}the rest" with the words run
208 24 // together; a renderer has no way to recover the separator, because the new
209 24 // side's flag never reached it.
210 75 emit := func(op Op, toks []Token, space bool) {
211 75 if len(toks) == 0 {
212 0 return
213 0 }
214 75 var sb strings.Builder
215 193 for i, t := range toks {
216 193 if i > 0 && t.Space {
217 110 sb.WriteByte(' ')
218 110 }
219 193 sb.WriteString(t.Text)
220 }
221 75 out = append(out, Span{Op: op, Text: sb.String(), Space: space})
222 }
223
224 24 i, j := 0, 0
225 75 for k := 0; k < len(script); k++ {
226 75 e := script[k]
227 75 // An insertion directly replacing a deletion must not re-announce
228 75 // the whitespace the deletion already carried, or every one-word
229 75 // substitution renders as "[-old-] {+new+}".
230 75 if e.op == OpInsert && k > 0 && script[k-1].op == OpDelete {
231 17 emit(OpInsert, b[j:j+e.n], false)
232 17 j += e.n
233 17 continue
234 }
235 58 switch e.op {
236 37 case OpEqual:
237 37 // Either side's separator is reason enough to emit one: the run is
238 37 // rendered once, between whatever precedes it on the old side and
239 37 // whatever precedes it on the new.
240 37 emit(OpEqual, a[i:i+e.n], a[i].Space || b[j].Space)
241 37 i += e.n
242 37 j += e.n
243 18 case OpDelete:
244 18 emit(OpDelete, a[i:i+e.n], a[i].Space)
245 18 i += e.n
246 3 case OpInsert:
247 3 emit(OpInsert, b[j:j+e.n], b[j].Space)
248 3 j += e.n
249 }
250 }
251 24 return out
252 }
253
254 // DiffLines is the code-fence path: line-oriented, whitespace-significant.
255 5 func DiffLines(oldLines, newLines []string) []Span {
256 5 in := newInterner()
257 5 script := diffInts(in.all(oldLines), in.all(newLines))
258 5 var out []Span
259 5 i, j := 0, 0
260 18 for _, e := range script {
261 18 switch e.op {
262 8 case OpEqual:
263 9 for n := 0; n < e.n; n++ {
264 9 out = append(out, Span{Op: OpEqual, Text: oldLines[i+n]})
265 9 }
266 8 i += e.n
267 8 j += e.n
268 5 case OpDelete:
269 5 for n := 0; n < e.n; n++ {
270 5 out = append(out, Span{Op: OpDelete, Text: oldLines[i+n]})
271 5 }
272 5 i += e.n
273 5 case OpInsert:
274 5 for n := 0; n < e.n; n++ {
275 5 out = append(out, Span{Op: OpInsert, Text: newLines[j+n]})
276 5 }
277 5 j += e.n
278 }
279 }
280 5 return out
281 }