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

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

Issue 6492076: code review 6492076: strings: implement a faster generic Replacer (Closed)
Left Patch Set: diff -r 46a4f787e8b7 https://code.google.com/p/go 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
« src/pkg/strings/replace.go ('K') | « src/pkg/strings/replace.go ('k') | no next file » | no next file with change/comment »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
LEFTRIGHT
1 // Copyright 2009 The Go Authors. All rights reserved. 1 // Copyright 2009 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_test 5 package strings_test
6 6
7 import ( 7 import (
8 "bytes" 8 "bytes"
9 "fmt" 9 "fmt"
10 . "strings" 10 . "strings"
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after
63 // Test cases with 1-byte old strings, 1-byte new strings. 63 // Test cases with 1-byte old strings, 1-byte new strings.
64 testCases = append(testCases, 64 testCases = append(testCases,
65 testCase{capitalLetters, "brad", "BrAd"}, 65 testCase{capitalLetters, "brad", "BrAd"},
66 testCase{capitalLetters, Repeat("a", (32<<10)+123), Repeat("A", (32<<10)+123)}, 66 testCase{capitalLetters, Repeat("a", (32<<10)+123), Repeat("A", (32<<10)+123)},
67 testCase{capitalLetters, "", ""}, 67 testCase{capitalLetters, "", ""},
68 68
69 testCase{inc, "brad", "csbe"}, 69 testCase{inc, "brad", "csbe"},
70 testCase{inc, "\x00\xff", "\x01\x00"}, 70 testCase{inc, "\x00\xff", "\x01\x00"},
71 testCase{inc, "", ""}, 71 testCase{inc, "", ""},
72 72
73 » » testCase{NewReplacer("a", "1", "a", "2"), "brad", "br2d"}, // TO DO: should this be "br1d"? 73 » » testCase{NewReplacer("a", "1", "a", "2"), "brad", "br1d"},
74 ) 74 )
75 75
76 // repeat maps "a"->"a", "b"->"bb", "c"->"ccc", ... 76 // repeat maps "a"->"a", "b"->"bb", "c"->"ccc", ...
77 s = nil 77 s = nil
78 for i := 0; i < 256; i++ { 78 for i := 0; i < 256; i++ {
79 n := i + 1 - 'a' 79 n := i + 1 - 'a'
80 if n < 1 { 80 if n < 1 {
81 n = 1 81 n = 1
82 } 82 }
83 s = append(s, str(byte(i)), Repeat(str(byte(i)), n)) 83 s = append(s, str(byte(i)), Repeat(str(byte(i)), n))
84 } 84 }
85 repeat := NewReplacer(s...) 85 repeat := NewReplacer(s...)
86 86
87 // Test cases with 1-byte old strings, variable length new strings. 87 // Test cases with 1-byte old strings, variable length new strings.
88 testCases = append(testCases, 88 testCases = append(testCases,
89 testCase{htmlEscaper, "No changes", "No changes"}, 89 testCase{htmlEscaper, "No changes", "No changes"},
90 testCase{htmlEscaper, "I <3 escaping & stuff", "I &lt;3 escaping &amp; stuff"}, 90 testCase{htmlEscaper, "I <3 escaping & stuff", "I &lt;3 escaping &amp; stuff"},
91 testCase{htmlEscaper, "&&&", "&amp;&amp;&amp;"}, 91 testCase{htmlEscaper, "&&&", "&amp;&amp;&amp;"},
92 testCase{htmlEscaper, "", ""}, 92 testCase{htmlEscaper, "", ""},
93 93
94 testCase{repeat, "brad", "bbrrrrrrrrrrrrrrrrrradddd"}, 94 testCase{repeat, "brad", "bbrrrrrrrrrrrrrrrrrradddd"},
95 testCase{repeat, "abba", "abbbba"}, 95 testCase{repeat, "abba", "abbbba"},
96 testCase{repeat, "", ""}, 96 testCase{repeat, "", ""},
97 97
98 » » testCase{NewReplacer("a", "11", "a", "22"), "brad", "br22d"}, // TODO: should this be "br11d"? 98 » » testCase{NewReplacer("a", "11", "a", "22"), "brad", "br11d"},
99 ) 99 )
100 100
101 // The remaining test cases have variable length old strings. 101 // The remaining test cases have variable length old strings.
102 102
103 testCases = append(testCases, 103 testCases = append(testCases,
104 testCase{htmlUnescaper, "&amp;amp;", "&amp;"}, 104 testCase{htmlUnescaper, "&amp;amp;", "&amp;"},
105 testCase{htmlUnescaper, "&lt;b&gt;HTML&apos;s neat&lt;/b&gt;", " <b>HTML's neat</b>"}, 105 testCase{htmlUnescaper, "&lt;b&gt;HTML&apos;s neat&lt;/b&gt;", " <b>HTML's neat</b>"},
106 testCase{htmlUnescaper, "", ""}, 106 testCase{htmlUnescaper, "", ""},
107 107
108 testCase{NewReplacer("a", "1", "a", "2", "xxx", "xxx"), "brad", "br1d"}, 108 testCase{NewReplacer("a", "1", "a", "2", "xxx", "xxx"), "brad", "br1d"},
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after
212 testCases = append(testCases, 212 testCases = append(testCases,
213 testCase{genAll, allString, "[all]"}, 213 testCase{genAll, allString, "[all]"},
214 testCase{genAll, "a\xff" + allString + "\x00", "a[ff][all][00]"} , 214 testCase{genAll, "a\xff" + allString + "\x00", "a[ff][all][00]"} ,
215 testCase{genAll, "", ""}, 215 testCase{genAll, "", ""},
216 ) 216 )
217 217
218 // Test cases with empty old strings. 218 // Test cases with empty old strings.
219 219
220 blankToX1 := NewReplacer("", "X") 220 blankToX1 := NewReplacer("", "X")
221 blankToX2 := NewReplacer("", "X", "", "") 221 blankToX2 := NewReplacer("", "X", "", "")
222 » blankToXOToO := NewReplacer("", "X", "o", "O") 222 » blankHighPriority := NewReplacer("", "X", "o", "O")
223 » blankLowPriority := NewReplacer("o", "O", "", "X")
223 blankNoOp1 := NewReplacer("", "") 224 blankNoOp1 := NewReplacer("", "")
224 blankNoOp2 := NewReplacer("", "", "", "A") 225 blankNoOp2 := NewReplacer("", "", "", "A")
225 blankFoo := NewReplacer("", "X", "foobar", "R", "foobaz", "Z") 226 blankFoo := NewReplacer("", "X", "foobar", "R", "foobaz", "Z")
226 testCases = append(testCases, 227 testCases = append(testCases,
227 testCase{blankToX1, "foo", "XfXoXoX"}, 228 testCase{blankToX1, "foo", "XfXoXoX"},
228 testCase{blankToX1, "", "X"}, 229 testCase{blankToX1, "", "X"},
229 230
230 testCase{blankToX2, "foo", "XfXoXoX"}, 231 testCase{blankToX2, "foo", "XfXoXoX"},
231 testCase{blankToX2, "", "X"}, 232 testCase{blankToX2, "", "X"},
232 233
233 » » testCase{blankToXOToO, "oo", "XOXOX"}, 234 » » testCase{blankHighPriority, "oo", "XOXOX"},
234 » » testCase{blankToXOToO, "ii", "XiXiX"}, 235 » » testCase{blankHighPriority, "ii", "XiXiX"},
235 » » testCase{blankToXOToO, "iooi", "XiXOXOXiX"}, 236 » » testCase{blankHighPriority, "iooi", "XiXOXOXiX"},
nigeltao 2012/09/17 01:49:24 I'd also add an "oiio" test.
236 » » testCase{blankToXOToO, "", "X"}, 237 » » testCase{blankHighPriority, "", "X"},
238
239 » » testCase{blankLowPriority, "oo", "OOX"},
240 » » testCase{blankLowPriority, "ii", "XiXiX"},
241 » » testCase{blankLowPriority, "iooi", "XiOOXiX"},
242 » » testCase{blankLowPriority, "", "X"},
237 243
238 testCase{blankNoOp1, "foo", "foo"}, 244 testCase{blankNoOp1, "foo", "foo"},
239 testCase{blankNoOp1, "", ""}, 245 testCase{blankNoOp1, "", ""},
240 246
241 testCase{blankNoOp2, "foo", "foo"}, 247 testCase{blankNoOp2, "foo", "foo"},
242 testCase{blankNoOp2, "", ""}, 248 testCase{blankNoOp2, "", ""},
243 249
244 testCase{blankFoo, "foobarfoobaz", "XRXZX"}, 250 testCase{blankFoo, "foobarfoobaz", "XRXZX"},
245 testCase{blankFoo, "foobar-foobaz", "XRX-XZX"}, 251 testCase{blankFoo, "foobar-foobaz", "XRX-XZX"},
246 testCase{blankFoo, "", "X"}, 252 testCase{blankFoo, "", "X"},
253 )
254
255 // No-arg test cases.
256
257 nop := NewReplacer()
258 testCases = append(testCases,
259 testCase{nop, "abc", "abc"},
260 testCase{nop, "", ""},
247 ) 261 )
248 262
249 // Run the test cases. 263 // Run the test cases.
250 264
251 for i, tc := range testCases { 265 for i, tc := range testCases {
252 if s := tc.r.Replace(tc.in); s != tc.out { 266 if s := tc.r.Replace(tc.in); s != tc.out {
253 t.Errorf("%d. Replace(%q) = %q, want %q", i, tc.in, s, t c.out) 267 t.Errorf("%d. Replace(%q) = %q, want %q", i, tc.in, s, t c.out)
254 } 268 }
255 var buf bytes.Buffer 269 var buf bytes.Buffer
256 n, err := tc.r.WriteString(&buf, tc.in) 270 n, err := tc.r.WriteString(&buf, tc.in)
(...skipping 13 matching lines...) Expand all
270 } 284 }
271 } 285 }
272 286
273 // TestPickAlgorithm tests that NewReplacer picks the correct algorithm. 287 // TestPickAlgorithm tests that NewReplacer picks the correct algorithm.
274 func TestPickAlgorithm(t *testing.T) { 288 func TestPickAlgorithm(t *testing.T) {
275 testCases := []struct { 289 testCases := []struct {
276 r *Replacer 290 r *Replacer
277 want string 291 want string
278 }{ 292 }{
279 {capitalLetters, "*strings.byteReplacer"}, 293 {capitalLetters, "*strings.byteReplacer"},
294 {htmlEscaper, "*strings.byteStringReplacer"},
280 {NewReplacer("12", "123"), "*strings.genericReplacer"}, 295 {NewReplacer("12", "123"), "*strings.genericReplacer"},
281 {NewReplacer("1", "12"), "*strings.byteStringReplacer"}, 296 {NewReplacer("1", "12"), "*strings.byteStringReplacer"},
282 » » {htmlEscaper, "*strings.byteStringReplacer"}, 297 » » {NewReplacer("a", "1", "b", "12", "cde", "123"), "*strings.gener icReplacer"},
283 } 298 }
284 for i, tc := range testCases { 299 for i, tc := range testCases {
285 got := fmt.Sprintf("%T", tc.r.Replacer()) 300 got := fmt.Sprintf("%T", tc.r.Replacer())
286 if got != tc.want { 301 if got != tc.want {
287 t.Errorf("%d. algorithm = %s, want %s", i, got, tc.want) 302 t.Errorf("%d. algorithm = %s, want %s", i, got, tc.want)
288 } 303 }
289 } 304 }
290 } 305 }
291 306
307 // TestGenericTrieBuilding verifies the structure of the generated trie. There
308 // is one node per line, and the key ending with the current line is in the
309 // trie if it ends with a "+".
292 func TestGenericTrieBuilding(t *testing.T) { 310 func TestGenericTrieBuilding(t *testing.T) {
293 testCases := []struct{ in, out string }{ 311 testCases := []struct{ in, out string }{
294 {"abc;abdef;abdefgh;xx;xy;z", `- 312 {"abc;abdef;abdefgh;xx;xy;z", `-
295 a- 313 a-
296 .b- 314 .b-
297 ..c+ 315 ..c+
298 ..d- 316 ..d-
299 ...ef+ 317 ...ef+
300 .....gh+ 318 .....gh+
301 x- 319 x-
(...skipping 19 matching lines...) Expand all
321 .a+ 339 .a+
322 ..a+ 340 ..a+
323 i+ 341 i+
324 l- 342 l-
325 .ong+ 343 .ong+
326 ....er+ 344 ....er+
327 ......st+ 345 ......st+
328 x+ 346 x+
329 .x+ 347 .x+
330 `}, 348 `},
331 » } 349 » » {"foo;;foo;foo1", `+
332 350 » » » f-
333 » spaceRemover := NewReplacer(" ", "", "\t", "") 351 » » » .oo+
352 » » » ...1+
353 » » » `},
354 » }
334 355
335 for _, tc := range testCases { 356 for _, tc := range testCases {
336 keys := Split(tc.in, ";") 357 keys := Split(tc.in, ";")
337 args := make([]string, len(keys)*2) 358 args := make([]string, len(keys)*2)
338 for i, key := range keys { 359 for i, key := range keys {
339 args[i*2] = key 360 args[i*2] = key
340 } 361 }
341 » » gen := NewReplacer(args...) 362
342 363 » » got := NewReplacer(args...).PrintTrie()
343 » » in := gen.PrintTrie() 364 » » // Remove tabs from tc.out
344 » » out := spaceRemover.Replace(tc.out) 365 » » wantbuf := make([]byte, 0, len(tc.out))
345 366 » » for i := 0; i < len(tc.out); i++ {
346 » » if in != out { 367 » » » if tc.out[i] != '\t' {
347 » » » t.Errorf("PrintTrie(%q) = %s, want %s", tc.in, in, out) 368 » » » » wantbuf = append(wantbuf, tc.out[i])
369 » » » }
370 » » }
371 » » want := string(wantbuf)
372
373 » » if got != want {
374 » » » t.Errorf("PrintTrie(%q)\ngot\n%swant\n%s", tc.in, got, w ant)
348 } 375 }
349 } 376 }
350 } 377 }
351 378
352 func BenchmarkGenericNoMatch(b *testing.B) { 379 func BenchmarkGenericNoMatch(b *testing.B) {
353 str := Repeat("A", 100) + Repeat("B", 100) 380 str := Repeat("A", 100) + Repeat("B", 100)
354 generic := NewReplacer("a", "A", "b", "B", "12", "123") // varying lengt hs forces generic 381 generic := NewReplacer("a", "A", "b", "B", "12", "123") // varying lengt hs forces generic
355 for i := 0; i < b.N; i++ { 382 for i := 0; i < b.N; i++ {
356 generic.Replace(str) 383 generic.Replace(str)
357 } 384 }
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after
424 return 'A' 451 return 'A'
425 case 'b': 452 case 'b':
426 return 'B' 453 return 'B'
427 } 454 }
428 return r 455 return r
429 } 456 }
430 for i := 0; i < b.N; i++ { 457 for i := 0; i < b.N; i++ {
431 Map(fn, str) 458 Map(fn, str)
432 } 459 }
433 } 460 }
LEFTRIGHT

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