Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1038)

Delta Between Two Patch Sets: src/pkg/strings/replace.go

Issue 6492076: code review 6492076: strings: implement a faster generic Replacer (Closed)
Left Patch Set: diff -r 5c4859bc123f https://go.googlecode.com/hg Created 11 years, 6 months ago
Right Patch Set: diff -r cdee8bf43694 https://code.google.com/p/go Created 11 years, 6 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
Left: Side by side diff | Download
Right: Side by side diff | Download
LEFTRIGHT
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
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
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 }
LEFTRIGHT

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b