Left: | ||
Right: |
LEFT | RIGHT |
---|---|
1 // Copyright 2011 The Go Authors. All rights reserved. | 1 // Copyright 2011 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 package strings | 5 package strings |
6 | 6 |
7 import "io" | 7 import "io" |
8 | 8 |
9 // A Replacer replaces a list of strings with replacements. | 9 // A Replacer replaces a list of strings with replacements. |
10 type Replacer struct { | 10 type Replacer struct { |
(...skipping 15 matching lines...) Expand all Loading... | |
26 m[b>>5] |= uint32(1 << (b & 31)) | 26 m[b>>5] |= uint32(1 << (b & 31)) |
27 } | 27 } |
28 | 28 |
29 // NewReplacer returns a new Replacer from a list of old, new string pairs. | 29 // NewReplacer returns a new Replacer from a list of old, new string pairs. |
30 // Replacements are performed in order, without overlapping matches. | 30 // Replacements are performed in order, without overlapping matches. |
31 func NewReplacer(oldnew ...string) *Replacer { | 31 func NewReplacer(oldnew ...string) *Replacer { |
32 if len(oldnew)%2 == 1 { | 32 if len(oldnew)%2 == 1 { |
33 panic("strings.NewReplacer: odd argument count") | 33 panic("strings.NewReplacer: odd argument count") |
34 } | 34 } |
35 | 35 |
36 // Possible implementations. | |
37 var ( | |
38 bb byteReplacer | |
39 bs byteStringReplacer | |
40 ) | |
41 | |
42 allNewBytes := true | 36 allNewBytes := true |
43 for i := 0; i < len(oldnew); i += 2 { | 37 for i := 0; i < len(oldnew); i += 2 { |
44 » » old, new := oldnew[i], oldnew[i+1] | 38 » » if len(oldnew[i]) != 1 { |
45 » » if len(old) != 1 { | 39 » » » return &Replacer{r: makeGenericReplacer(oldnew)} |
46 » » » return &Replacer{r: buildGenReplacer(oldnew)} | 40 » » } |
47 » » } | 41 » » if len(oldnew[i+1]) != 1 { |
48 » » if len(new) != 1 { | |
49 allNewBytes = false | 42 allNewBytes = false |
50 } | 43 } |
51 | |
52 // byte -> string | |
53 bs.old.set(old[0]) | |
54 bs.new[old[0]] = []byte(new) | |
55 | |
56 // byte -> byte | |
57 if allNewBytes { | |
58 bb.old.set(old[0]) | |
59 bb.new[old[0]] = new[0] | |
60 } | |
61 } | 44 } |
62 | 45 |
63 if allNewBytes { | 46 if allNewBytes { |
64 » » return &Replacer{r: &bb} | 47 » » bb := &byteReplacer{} |
65 » } | 48 » » for i := 0; i < len(oldnew); i += 2 { |
66 » return &Replacer{r: &bs} | 49 » » » o, n := oldnew[i][0], oldnew[i+1][0] |
50 » » » if bb.old[o>>5]&uint32(1<<(o&31)) != 0 { | |
51 » » » » // Later old->new maps do not override previous ones with the same old string. | |
52 » » » » continue | |
53 » » » } | |
54 » » » bb.old.set(o) | |
55 » » » bb.new[o] = n | |
56 » » } | |
57 » » return &Replacer{r: bb} | |
58 » } | |
59 | |
60 » bs := &byteStringReplacer{} | |
61 » for i := 0; i < len(oldnew); i += 2 { | |
62 » » o, new := oldnew[i][0], oldnew[i+1] | |
63 » » if bs.old[o>>5]&uint32(1<<(o&31)) != 0 { | |
64 » » » // Later old->new maps do not override previous ones wit h the same old string. | |
65 » » » continue | |
66 » » } | |
67 » » bs.old.set(o) | |
68 » » bs.new[o] = []byte(new) | |
69 » } | |
70 » return &Replacer{r: bs} | |
67 } | 71 } |
68 | 72 |
69 // Replace returns a copy of s with all replacements performed. | 73 // Replace returns a copy of s with all replacements performed. |
70 func (r *Replacer) Replace(s string) string { | 74 func (r *Replacer) Replace(s string) string { |
71 return r.r.Replace(s) | 75 return r.r.Replace(s) |
72 } | 76 } |
73 | 77 |
74 // WriteString writes s to w with all replacements performed. | 78 // WriteString writes s to w with all replacements performed. |
75 func (r *Replacer) WriteString(w io.Writer, s string) (n int, err error) { | 79 func (r *Replacer) WriteString(w io.Writer, s string) (n int, err error) { |
76 return r.r.WriteString(w, s) | 80 return r.r.WriteString(w, s) |
77 } | 81 } |
78 | 82 |
79 // Used to implement generic replacer. | 83 // trieNode is a node in a lookup trie for prioritized key/value pairs. Keys |
80 type trie struct { | 84 // and values may be empty. For example, the trie containing keys "ax", "ay", |
81 » // The value at this node. | 85 // "bcbc", "x" and "xy" could have eight nodes: |
86 // | |
87 // n0 - | |
88 // n1 a- | |
89 // n2 .x+ | |
90 // n3 .y+ | |
91 // n4 b- | |
92 // n5 .cbc+ | |
93 // n6 x+ | |
94 // n7 .y+ | |
95 // | |
96 // n0 is the root node, and its children are n1, n4 and n6; n1's children are | |
97 // n2 and n3; n4's child is n5; n6's child is n7. Nodes n0, n1 and n4 (marked | |
98 // with a trailing "-") are partial keys, and nodes n2, n3, n5, n6 and n7 | |
99 // (marked with a trailing "+") are complete keys. | |
100 type trieNode struct { | |
101 » // value is the value of the trie node's key/value pair. It is empty if | |
102 » // this node is not a complete key. | |
82 value string | 103 value string |
83 » // Priority of this match vs superstrings. Higher is better, and 0 is | 104 » // priority is the priority (higher is more important) of the trie node' s |
84 » // nonterminal. | 105 » // key/value pair; keys are not necessarily matched shortest- or longest - |
106 » // first. Priority is positive if this node is a complete key, and zero | |
107 » // otherwise. In the example above, positive/zero priorities are marked | |
108 » // with a trailing "+" or "-". | |
85 priority int | 109 priority int |
86 » // Next byte lookup table. | 110 |
87 » next [256]*trie | 111 » // A trie node may have zero, one or more child nodes: |
88 } | 112 » // * if the remaining fields are zero, there are no children. |
89 | 113 » // * if prefix and next are non-zero, there is one child in next |
nigeltao
2012/09/17 01:49:24
Trailing full stop, and ditto on the next line.
| |
90 func (t *trie) add(key, val string, priority int) { | 114 » // * if table is non-zero, it defines all the children |
91 » if len(key) == 0 { | 115 » // |
92 » » t.value = val | 116 » // Prefixes are preferred over tables when there is one child, but the |
93 » » t.priority = priority | 117 » // root node always uses a table for lookup efficiency. |
118 | |
119 » // prefix is the difference in keys between this trie node and the next. | |
120 » // In the example above, node n4 has prefix "cbc" and n4's next node is n5. | |
121 » // Node n5 has no children and so has zero prefix, next and table fields . | |
122 » prefix string | |
123 » next *trieNode | |
124 | |
125 » // table is a lookup table indexed by the next byte in the key, after | |
126 » // remapping that byte through genericReplacer.mapping to create a dense | |
127 » // index. In the example above, the keys only use 'a', 'b', 'c', 'x' and | |
128 » // 'y', which remap to 0, 1, 2, 3 and 4. All other bytes remap to 5, and | |
129 » // genericReplacer.tableSize will be 5. Node n0's table will be | |
130 » // []*trieNode{ 0:n1, 1:n4, 3:n6 }, where the 0, 1 and 3 are the remappe d | |
131 » // 'a', 'b' and 'x'. | |
132 » table []*trieNode | |
133 } | |
134 | |
135 func (t *trieNode) add(key, val string, priority int, r *genericReplacer) { | |
136 » if key == "" { | |
137 » » if t.priority == 0 { | |
138 » » » t.value = val | |
139 » » » t.priority = priority | |
140 » » } | |
94 return | 141 return |
95 } | 142 } |
96 | 143 |
97 » b := key[0] | 144 » if t.prefix != "" { |
98 » if t.next[b] == nil { | 145 » » // Need to split the prefix among multiple nodes. |
99 » » t.next[b] = new(trie) | 146 » » var n int // length of the longest common prefix |
100 » } | 147 » » for ; n < len(t.prefix) && n < len(key); n++ { |
101 » next := t.next[b] | 148 » » » if t.prefix[n] != key[n] { |
102 | 149 » » » » break |
103 » next.add(key[1:], val, priority) | 150 » » » } |
104 } | 151 » » } |
105 | 152 » » if n == len(t.prefix) { |
106 func (t *trie) lookup(s string) (val string, keylen int, found bool) { | 153 » » » t.next.add(key[n:], val, priority, r) |
154 » » } else if n == 0 { | |
155 » » » // First byte differs, start a new lookup table here. L ooking up | |
156 » » » // what is crrently t.prefix[0] will lead to prefixNode, and | |
nigeltao
2012/09/17 01:49:24
Typo in currently.
| |
157 » » » // looking up key[0] will lead to keyNode. | |
158 » » » var prefixNode *trieNode | |
159 » » » if len(t.prefix) == 1 { | |
160 » » » » prefixNode = t.next | |
161 » » » } else { | |
162 » » » » prefixNode = &trieNode{ | |
163 » » » » » prefix: t.prefix[1:], | |
164 » » » » » next: t.next, | |
165 » » » » } | |
166 » » » } | |
167 » » » keyNode := new(trieNode) | |
168 » » » t.table = make([]*trieNode, r.tableSize) | |
169 » » » t.table[r.mapping[t.prefix[0]]] = prefixNode | |
170 » » » t.table[r.mapping[key[0]]] = keyNode | |
171 » » » t.prefix = "" | |
172 » » » t.next = nil | |
173 » » » keyNode.add(key[1:], val, priority, r) | |
174 » » } else { | |
175 » » » // Insert new node after the common section of the prefi x. | |
176 » » » next := &trieNode{ | |
177 » » » » prefix: t.prefix[n:], | |
178 » » » » next: t.next, | |
179 » » » } | |
180 » » » t.prefix = t.prefix[:n] | |
181 » » » t.next = next | |
182 » » » next.add(key[n:], val, priority, r) | |
183 » » } | |
184 » } else if t.table != nil { | |
185 » » // Insert into existing table. | |
186 » » m := r.mapping[key[0]] | |
187 » » if t.table[m] == nil { | |
188 » » » t.table[m] = new(trieNode) | |
189 » » } | |
190 » » t.table[m].add(key[1:], val, priority, r) | |
191 » } else { | |
192 » » t.prefix = key | |
193 » » t.next = new(trieNode) | |
194 » » t.next.add("", val, priority, r) | |
195 » } | |
196 } | |
197 | |
198 func (r *genericReplacer) lookup(s string, ignoreRoot bool) (val string, keylen int, found bool) { | |
107 // Iterate down the trie to the end, and grab the value and keylen with | 199 // Iterate down the trie to the end, and grab the value and keylen with |
108 // the highest priority. | 200 // the highest priority. |
109 bestPriority := 0 | 201 bestPriority := 0 |
110 » node := t | 202 » node := &r.root |
111 n := 0 | 203 n := 0 |
112 for node != nil { | 204 for node != nil { |
113 » » if node.priority > bestPriority { | 205 » » if node.priority > bestPriority && !(ignoreRoot && node == &r.ro ot) { |
114 bestPriority = node.priority | 206 bestPriority = node.priority |
115 val = node.value | 207 val = node.value |
116 keylen = n | 208 keylen = n |
117 found = true | 209 found = true |
118 } | 210 } |
119 | 211 |
120 » » if len(s) == 0 { | 212 » » if s == "" { |
121 break | 213 break |
122 } | 214 } |
123 » » node = node.next[s[0]] | 215 » » if node.table != nil { |
124 » » s = s[1:] | 216 » » » index := r.mapping[s[0]] |
125 » » n++ | 217 » » » if int(index) == r.tableSize { |
218 » » » » break | |
219 » » » } | |
220 » » » node = node.table[index] | |
221 » » » s = s[1:] | |
222 » » » n++ | |
223 » » } else if node.prefix != "" && HasPrefix(s, node.prefix) { | |
224 » » » n += len(node.prefix) | |
225 » » » s = s[len(node.prefix):] | |
226 » » » node = node.next | |
227 » » } else { | |
228 » » » break | |
229 » » } | |
126 } | 230 } |
127 return | 231 return |
128 } | 232 } |
129 | 233 |
130 // genericReplacer is the fully generic algorithm. | 234 // genericReplacer is the fully generic algorithm. |
131 // It's used as a fallback when nothing faster can be used. | 235 // It's used as a fallback when nothing faster can be used. |
132 type genericReplacer struct { | 236 type genericReplacer struct { |
133 » trie *trie | 237 » root trieNode |
134 » // handle empty match separately | 238 » // tableSize is the size of a trie node's lookup table. It is the number |
135 » emptyMatch string | 239 » // of unique key bytes. |
136 } | 240 » tableSize int |
137 | 241 » // mapping maps from key bytes to a dense index for trieNode.table. |
138 func buildGenReplacer(oldnew []string) *genericReplacer { | 242 » mapping [256]byte |
139 » t := new(trie) | 243 } |
140 » r := &genericReplacer{trie: t} | 244 |
245 func makeGenericReplacer(oldnew []string) *genericReplacer { | |
246 » r := new(genericReplacer) | |
247 » // Find each byte used, then assign them each an index. | |
141 for i := 0; i < len(oldnew); i += 2 { | 248 for i := 0; i < len(oldnew); i += 2 { |
142 » » key, val := oldnew[i], oldnew[i+1] | 249 » » key := oldnew[i] |
143 » » if len(key) == 0 { | 250 » » for j := 0; j < len(key); j++ { |
nigeltao
2012/09/04 04:29:59
if key == "" {
is more idiomatic, and should be ju
Eric Roshan Eisner
2012/09/04 06:27:52
Done.
| |
144 » » » r.emptyMatch = val | 251 » » » r.mapping[key[j]] = 1 |
nigeltao
2012/09/04 04:29:59
A TestReplacer test case with more than one empty
Eric Roshan Eisner
2012/09/04 06:27:52
Some of the other implementations currently overwr
| |
145 » » } else { | 252 » » } |
146 » » » t.add(key, val, len(oldnew)-i) | 253 » } |
147 » » } | 254 |
255 » for _, b := range r.mapping { | |
256 » » r.tableSize += int(b) | |
257 » } | |
258 | |
259 » var index byte | |
260 » for i, b := range r.mapping { | |
261 » » if b == 0 { | |
262 » » » r.mapping[i] = byte(r.tableSize) | |
263 » » } else { | |
264 » » » r.mapping[i] = index | |
265 » » » index++ | |
266 » » } | |
267 » } | |
268 » // Ensure root node uses a lookup table (for performance). | |
269 » r.root.table = make([]*trieNode, r.tableSize) | |
270 | |
271 » for i := 0; i < len(oldnew); i += 2 { | |
272 » » r.root.add(oldnew[i], oldnew[i+1], len(oldnew)-i, r) | |
148 } | 273 } |
149 return r | 274 return r |
150 } | 275 } |
151 | 276 |
277 type appendSliceWriter []byte | |
278 | |
279 // Write writes to the buffer to satisfy io.Writer. | |
280 func (w *appendSliceWriter) Write(p []byte) (int, error) { | |
281 *w = append(*w, p...) | |
282 return len(p), nil | |
283 } | |
284 | |
285 // WriteString writes to the buffer without string->[]byte->string allocations. | |
286 func (w *appendSliceWriter) WriteString(s string) (int, error) { | |
287 *w = append(*w, s...) | |
288 return len(s), nil | |
289 } | |
290 | |
291 type stringWriter struct { | |
292 w io.Writer | |
293 } | |
294 | |
295 func (w stringWriter) WriteString(s string) (int, error) { | |
296 return w.w.Write([]byte(s)) | |
297 } | |
298 | |
152 func (r *genericReplacer) Replace(s string) string { | 299 func (r *genericReplacer) Replace(s string) string { |
153 » var buf []byte | 300 » buf := make(appendSliceWriter, 0, len(s)) |
154 » last := 0 | 301 » r.WriteString(&buf, s) |
155 » for i := 0; i < len(s); i++ { | 302 » return string(buf) |
156 » » val, keylen, match := r.trie.lookup(s[i:]) | 303 } |
304 | |
305 func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error) { | |
306 » sw, ok := w.(interface { | |
307 » » WriteString(string) (int, error) | |
308 » }) | |
309 » if !ok { | |
310 » » sw = stringWriter{w} | |
311 » } | |
312 | |
313 » var last, wn int | |
314 » var prevMatchEmpty bool | |
315 » for i := 0; i <= len(s); { | |
316 » » // Ignore the empty match iff the previous loop found the empty match. | |
317 » » val, keylen, match := r.lookup(s[i:], prevMatchEmpty) | |
318 » » prevMatchEmpty = match && keylen == 0 | |
157 if match { | 319 if match { |
158 » » » if len(r.emptyMatch) == 0 { | 320 » » » wn, err = sw.WriteString(s[last:i]) |
159 » » » » // can only aggregate when there's no empty matc h | |
160 » » » » buf = append(buf, s[last:i]...) | |
161 » » » } else { | |
162 » » » » buf = append(buf, r.emptyMatch...) | |
163 » » » } | |
164 » » » buf = append(buf, val...) | |
165 » » » last = i + keylen | |
166 » » » i += keylen - 1 // looping adds another 1 | |
nigeltao
2012/09/04 04:29:59
The artificial -1 looks awkward. It might read bet
Eric Roshan Eisner
2012/09/04 06:27:52
Done.
| |
167 » » } else if len(r.emptyMatch) != 0 { | |
168 » » » buf = append(buf, s[i]) | |
nigeltao
2012/09/04 04:29:59
Should the
buf = append(buf, r.emptyMatch...)
a fe
Eric Roshan Eisner
2012/09/04 06:27:52
Done.
| |
169 » » } | |
170 » } | |
171 » if len(r.emptyMatch) == 0 { | |
172 » » if buf == nil { | |
173 » » » // If nothing got replaced, avoid any allocation. | |
174 » » » return s | |
175 » » } | |
176 » » buf = append(buf, s[last:]...) | |
177 » } else { | |
178 » » buf = append(buf, r.emptyMatch...) | |
179 » } | |
180 » return string(buf) | |
181 } | |
182 | |
183 // Same logic as Replace, so if you want to avoid potentially a lot of small | |
nigeltao
2012/09/04 04:29:59
Go doc comments should be complete sentences (i.e.
Eric Roshan Eisner
2012/09/04 06:27:52
Done.
| |
184 // writes, write to bufio.Writer | |
185 func (r *genericReplacer) WriteString(w io.Writer, s string) (n int, err error) { | |
186 » var last, wn int | |
187 » for i := 0; i < len(s); i++ { | |
188 » » val, keylen, match := r.trie.lookup(s[i:]) | |
189 » » if match { | |
190 » » » if len(r.emptyMatch) == 0 { | |
191 » » » » // can only aggregate when there's no empty matc h | |
192 » » » » wn, err = io.WriteString(w, s[last:i]) | |
193 » » » } else { | |
194 » » » » wn, err = io.WriteString(w, r.emptyMatch) | |
195 » » » } | |
196 n += wn | 321 n += wn |
197 if err != nil { | 322 if err != nil { |
198 return | 323 return |
199 } | 324 } |
200 | 325 » » » wn, err = sw.WriteString(val) |
201 » » » wn, err = io.WriteString(w, val) | |
202 n += wn | 326 n += wn |
203 if err != nil { | 327 if err != nil { |
204 return | 328 return |
205 } | 329 } |
206 » » » last = i + keylen | 330 » » » i += keylen |
207 » » » i += keylen - 1 // looping adds another 1 | 331 » » » last = i |
208 » » } else if len(r.emptyMatch) != 0 { | 332 » » » continue |
209 » » » wn, err = io.WriteString(w, s[i:i+1]) | 333 » » } |
210 » » » n += wn | 334 » » i++ |
211 » » » if err != nil { | 335 » } |
212 » » » » return | 336 » if last != len(s) { |
213 » » » } | 337 » » wn, err = sw.WriteString(s[last:]) |
214 » » } | |
215 » } | |
216 » if len(r.emptyMatch) == 0 { | |
217 » » wn, err = io.WriteString(w, s[last:]) | |
218 » » n += wn | |
219 » } else { | |
220 » » wn, err = io.WriteString(w, r.emptyMatch) | |
221 n += wn | 338 n += wn |
222 } | 339 } |
223 return | 340 return |
224 } | 341 } |
225 | 342 |
226 // byteReplacer is the implementation that's used when all the "old" | 343 // byteReplacer is the implementation that's used when all the "old" |
227 // and "new" values are single ASCII bytes. | 344 // and "new" values are single ASCII bytes. |
228 type byteReplacer struct { | 345 type byteReplacer struct { |
229 // old has a bit set for each old byte that should be replaced. | 346 // old has a bit set for each old byte that should be replaced. |
230 old byteBitmap | 347 old byteBitmap |
(...skipping 125 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
356 } | 473 } |
357 if len(bi) > 0 { | 474 if len(bi) > 0 { |
358 nw, err := w.Write(bi) | 475 nw, err := w.Write(bi) |
359 n += nw | 476 n += nw |
360 if err != nil { | 477 if err != nil { |
361 return n, err | 478 return n, err |
362 } | 479 } |
363 } | 480 } |
364 return n, nil | 481 return n, nil |
365 } | 482 } |
366 | |
367 // strings is too low-level to import io/ioutil | |
368 var discard io.Writer = devNull(0) | |
369 | |
370 type devNull int | |
371 | |
372 func (devNull) Write(p []byte) (int, error) { | |
373 return len(p), nil | |
374 } | |
LEFT | RIGHT |