libgo/go/strings/replace_test.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package strings_test
   6
   7 import (
   8         "bytes"
   9         "fmt"
  10         . "strings"
  11         "testing"
  12 )
  13
  14 var htmlEscaper = NewReplacer(
  15         "&", "&amp;",
  16         "<", "&lt;",
  17         ">", "&gt;",
  18         `"`, "&quot;",
  19         "'", "&apos;",
  20 )
  21
  22 var htmlUnescaper = NewReplacer(
  23         "&amp;", "&",
  24         "&lt;", "<",
  25         "&gt;", ">",
  26         "&quot;", `"`,
  27         "&apos;", "'",
  28 )
  29
  30 // The http package's old HTML escaping function.
  31 func oldHTMLEscape(s string) string {
  32         s = Replace(s, "&", "&amp;", -1)
  33         s = Replace(s, "<", "&lt;", -1)
  34         s = Replace(s, ">", "&gt;", -1)
  35         s = Replace(s, `"`, "&quot;", -1)
  36         s = Replace(s, "'", "&apos;", -1)
  37         return s
  38 }
  39
  40 var capitalLetters = NewReplacer("a", "A", "b", "B")
  41
  42 // TestReplacer tests the replacer implementations.
  43 func TestReplacer(t *testing.T) {
  44         type testCase struct {
  45                 r       *Replacer
  46                 in, out string
  47         }
  48         var testCases []testCase
  49
  50         // str converts 0xff to "\xff". This isn't just string(b) since that converts to UTF-8.
  51         str := func(b byte) string {
  52                 return string([]byte{b})
  53         }
  54         var s []string
  55
  56         // inc maps "\x00"->"\x01", ..., "a"->"b", "b"->"c", ..., "\xff"->"\x00".
  57         s = nil
  58         for i := 0; i < 256; i++ {
  59                 s = append(s, str(byte(i)), str(byte(i+1)))
  60         }
  61         inc := NewReplacer(s...)
  62
  63         // Test cases with 1-byte old strings, 1-byte new strings.
  64         testCases = append(testCases,
  65                 testCase{capitalLetters, "brad", "BrAd"},
  66                 testCase{capitalLetters, Repeat("a", (32<<10)+123), Repeat("A", (32<<10)+123)},
  67                 testCase{capitalLetters, "", ""},
  68
  69                 testCase{inc, "brad", "csbe"},
  70                 testCase{inc, "\x00\xff", "\x01\x00"},
  71                 testCase{inc, "", ""},
  72
  73                 testCase{NewReplacer("a", "1", "a", "2"), "brad", "br1d"},
  74         )
  75
  76         // repeat maps "a"->"a", "b"->"bb", "c"->"ccc", ...
  77         s = nil
  78         for i := 0; i < 256; i++ {
  79                 n := i + 1 - 'a'
  80                 if n < 1 {
  81                         n = 1
  82                 }
  83                 s = append(s, str(byte(i)), Repeat(str(byte(i)), n))
  84         }
  85         repeat := NewReplacer(s...)
  86
  87         // Test cases with 1-byte old strings, variable length new strings.
  88         testCases = append(testCases,
  89                 testCase{htmlEscaper, "No changes", "No changes"},
  90                 testCase{htmlEscaper, "I <3 escaping & stuff", "I &lt;3 escaping &amp; stuff"},
  91                 testCase{htmlEscaper, "&&&", "&amp;&amp;&amp;"},
  92                 testCase{htmlEscaper, "", ""},
  93
  94                 testCase{repeat, "brad", "bbrrrrrrrrrrrrrrrrrradddd"},
  95                 testCase{repeat, "abba", "abbbba"},
  96                 testCase{repeat, "", ""},
  97
  98                 testCase{NewReplacer("a", "11", "a", "22"), "brad", "br11d"},
  99         )
 100
 101         // The remaining test cases have variable length old strings.
 102
 103         testCases = append(testCases,
 104                 testCase{htmlUnescaper, "&amp;amp;", "&amp;"},
 105                 testCase{htmlUnescaper, "&lt;b&gt;HTML&apos;s neat&lt;/b&gt;", "<b>HTML's neat</b>"},
 106                 testCase{htmlUnescaper, "", ""},
 107
 108                 testCase{NewReplacer("a", "1", "a", "2", "xxx", "xxx"), "brad", "br1d"},
 109
 110                 testCase{NewReplacer("a", "1", "aa", "2", "aaa", "3"), "aaaa", "1111"},
 111
 112                 testCase{NewReplacer("aaa", "3", "aa", "2", "a", "1"), "aaaa", "31"},
 113         )
 114
 115         // gen1 has multiple old strings of variable length. There is no
 116         // overall non-empty common prefix, but some pairwise common prefixes.
 117         gen1 := NewReplacer(
 118                 "aaa", "3[aaa]",
 119                 "aa", "2[aa]",
 120                 "a", "1[a]",
 121                 "i", "i",
 122                 "longerst", "most long",
 123                 "longer", "medium",
 124                 "long", "short",
 125                 "xx", "xx",
 126                 "x", "X",
 127                 "X", "Y",
 128                 "Y", "Z",
 129         )
 130         testCases = append(testCases,
 131                 testCase{gen1, "fooaaabar", "foo3[aaa]b1[a]r"},
 132                 testCase{gen1, "long, longerst, longer", "short, most long, medium"},
 133                 testCase{gen1, "xxxxx", "xxxxX"},
 134                 testCase{gen1, "XiX", "YiY"},
 135                 testCase{gen1, "", ""},
 136         )
 137
 138         // gen2 has multiple old strings with no pairwise common prefix.
 139         gen2 := NewReplacer(
 140                 "roses", "red",
 141                 "violets", "blue",
 142                 "sugar", "sweet",
 143         )
 144         testCases = append(testCases,
 145                 testCase{gen2, "roses are red, violets are blue...", "red are red, blue are blue..."},
 146                 testCase{gen2, "", ""},
 147         )
 148
 149         // gen3 has multiple old strings with an overall common prefix.
 150         gen3 := NewReplacer(
 151                 "abracadabra", "poof",
 152                 "abracadabrakazam", "splat",
 153                 "abraham", "lincoln",
 154                 "abrasion", "scrape",
 155                 "abraham", "isaac",
 156         )
 157         testCases = append(testCases,
 158                 testCase{gen3, "abracadabrakazam abraham", "poofkazam lincoln"},
 159                 testCase{gen3, "abrasion abracad", "scrape abracad"},
 160                 testCase{gen3, "abba abram abrasive", "abba abram abrasive"},
 161                 testCase{gen3, "", ""},
 162         )
 163
 164         // foo{1,2,3,4} have multiple old strings with an overall common prefix
 165         // and 1- or 2- byte extensions from the common prefix.
 166         foo1 := NewReplacer(
 167                 "foo1", "A",
 168                 "foo2", "B",
 169                 "foo3", "C",
 170         )
 171         foo2 := NewReplacer(
 172                 "foo1", "A",
 173                 "foo2", "B",
 174                 "foo31", "C",
 175                 "foo32", "D",
 176         )
 177         foo3 := NewReplacer(
 178                 "foo11", "A",
 179                 "foo12", "B",
 180                 "foo31", "C",
 181                 "foo32", "D",
 182         )
 183         foo4 := NewReplacer(
 184                 "foo12", "B",
 185                 "foo32", "D",
 186         )
 187         testCases = append(testCases,
 188                 testCase{foo1, "fofoofoo12foo32oo", "fofooA2C2oo"},
 189                 testCase{foo1, "", ""},
 190
 191                 testCase{foo2, "fofoofoo12foo32oo", "fofooA2Doo"},
 192                 testCase{foo2, "", ""},
 193
 194                 testCase{foo3, "fofoofoo12foo32oo", "fofooBDoo"},
 195                 testCase{foo3, "", ""},
 196
 197                 testCase{foo4, "fofoofoo12foo32oo", "fofooBDoo"},
 198                 testCase{foo4, "", ""},
 199         )
 200
 201         // genAll maps "\x00\x01\x02...\xfe\xff" to "[all]", amongst other things.
 202         allBytes := make([]byte, 256)
 203         for i := range allBytes {
 204                 allBytes[i] = byte(i)
 205         }
 206         allString := string(allBytes)
 207         genAll := NewReplacer(
 208                 allString, "[all]",
 209                 "\xff", "[ff]",
 210                 "\x00", "[00]",
 211         )
 212         testCases = append(testCases,
 213                 testCase{genAll, allString, "[all]"},
 214                 testCase{genAll, "a\xff" + allString + "\x00", "a[ff][all][00]"},
 215                 testCase{genAll, "", ""},
 216         )
 217
 218         // Test cases with empty old strings.
 219
 220         blankToX1 := NewReplacer("", "X")
 221         blankToX2 := NewReplacer("", "X", "", "")
 222         blankHighPriority := NewReplacer("", "X", "o", "O")
 223         blankLowPriority := NewReplacer("o", "O", "", "X")
 224         blankNoOp1 := NewReplacer("", "")
 225         blankNoOp2 := NewReplacer("", "", "", "A")
 226         blankFoo := NewReplacer("", "X", "foobar", "R", "foobaz", "Z")
 227         testCases = append(testCases,
 228                 testCase{blankToX1, "foo", "XfXoXoX"},
 229                 testCase{blankToX1, "", "X"},
 230
 231                 testCase{blankToX2, "foo", "XfXoXoX"},
 232                 testCase{blankToX2, "", "X"},
 233
 234                 testCase{blankHighPriority, "oo", "XOXOX"},
 235                 testCase{blankHighPriority, "ii", "XiXiX"},
 236                 testCase{blankHighPriority, "oiio", "XOXiXiXOX"},
 237                 testCase{blankHighPriority, "iooi", "XiXOXOXiX"},
 238                 testCase{blankHighPriority, "", "X"},
 239
 240                 testCase{blankLowPriority, "oo", "OOX"},
 241                 testCase{blankLowPriority, "ii", "XiXiX"},
 242                 testCase{blankLowPriority, "oiio", "OXiXiOX"},
 243                 testCase{blankLowPriority, "iooi", "XiOOXiX"},
 244                 testCase{blankLowPriority, "", "X"},
 245
 246                 testCase{blankNoOp1, "foo", "foo"},
 247                 testCase{blankNoOp1, "", ""},
 248
 249                 testCase{blankNoOp2, "foo", "foo"},
 250                 testCase{blankNoOp2, "", ""},
 251
 252                 testCase{blankFoo, "foobarfoobaz", "XRXZX"},
 253                 testCase{blankFoo, "foobar-foobaz", "XRX-XZX"},
 254                 testCase{blankFoo, "", "X"},
 255         )
 256
 257         // single string replacer
 258
 259         abcMatcher := NewReplacer("abc", "[match]")
 260
 261         testCases = append(testCases,
 262                 testCase{abcMatcher, "", ""},
 263                 testCase{abcMatcher, "ab", "ab"},
 264                 testCase{abcMatcher, "abc", "[match]"},
 265                 testCase{abcMatcher, "abcd", "[match]d"},
 266                 testCase{abcMatcher, "cabcabcdabca", "c[match][match]d[match]a"},
 267         )
 268
 269         // Issue 6659 cases (more single string replacer)
 270
 271         noHello := NewReplacer("Hello", "")
 272         testCases = append(testCases,
 273                 testCase{noHello, "Hello", ""},
 274                 testCase{noHello, "Hellox", "x"},
 275                 testCase{noHello, "xHello", "x"},
 276                 testCase{noHello, "xHellox", "xx"},
 277         )
 278
 279         // No-arg test cases.
 280
 281         nop := NewReplacer()
 282         testCases = append(testCases,
 283                 testCase{nop, "abc", "abc"},
 284                 testCase{nop, "", ""},
 285         )
 286
 287         // Run the test cases.
 288
 289         for i, tc := range testCases {
 290                 if s := tc.r.Replace(tc.in); s != tc.out {
 291                         t.Errorf("%d. Replace(%q) = %q, want %q", i, tc.in, s, tc.out)
 292                 }
 293                 var buf bytes.Buffer
 294                 n, err := tc.r.WriteString(&buf, tc.in)
 295                 if err != nil {
 296                         t.Errorf("%d. WriteString: %v", i, err)
 297                         continue
 298                 }
 299                 got := buf.String()
 300                 if got != tc.out {
 301                         t.Errorf("%d. WriteString(%q) wrote %q, want %q", i, tc.in, got, tc.out)
 302                         continue
 303                 }
 304                 if n != len(tc.out) {
 305                         t.Errorf("%d. WriteString(%q) wrote correct string but reported %d bytes; want %d (%q)",
 306                                 i, tc.in, n, len(tc.out), tc.out)
 307                 }
 308         }
 309 }
 310
 311 var algorithmTestCases = []struct {
 312         r    *Replacer
 313         want string
 314 }{
 315         {capitalLetters, "*strings.byteReplacer"},
 316         {htmlEscaper, "*strings.byteStringReplacer"},
 317         {NewReplacer("12", "123"), "*strings.singleStringReplacer"},
 318         {NewReplacer("1", "12"), "*strings.byteStringReplacer"},
 319         {NewReplacer("", "X"), "*strings.genericReplacer"},
 320         {NewReplacer("a", "1", "b", "12", "cde", "123"), "*strings.genericReplacer"},
 321 }
 322
 323 // TestPickAlgorithm tests that NewReplacer picks the correct algorithm.
 324 func TestPickAlgorithm(t *testing.T) {
 325         for i, tc := range algorithmTestCases {
 326                 got := fmt.Sprintf("%T", tc.r.Replacer())
 327                 if got != tc.want {
 328                         t.Errorf("%d. algorithm = %s, want %s", i, got, tc.want)
 329                 }
 330         }
 331 }
 332
 333 type errWriter struct{}
 334
 335 func (errWriter) Write(p []byte) (n int, err error) {
 336         return 0, fmt.Errorf("unwritable")
 337 }
 338
 339 // TestWriteStringError tests that WriteString returns an error
 340 // received from the underlying io.Writer.
 341 func TestWriteStringError(t *testing.T) {
 342         for i, tc := range algorithmTestCases {
 343                 n, err := tc.r.WriteString(errWriter{}, "abc")
 344                 if n != 0 || err == nil || err.Error() != "unwritable" {
 345                         t.Errorf("%d. WriteStringError = %d, %v, want 0, unwritable", i, n, err)
 346                 }
 347         }
 348 }
 349
 350 // TestGenericTrieBuilding verifies the structure of the generated trie. There
 351 // is one node per line, and the key ending with the current line is in the
 352 // trie if it ends with a "+".
 353 func TestGenericTrieBuilding(t *testing.T) {
 354         testCases := []struct{ in, out string }{
 355                 {"abc;abdef;abdefgh;xx;xy;z", `-
 356                         a-
 357                         .b-
 358                         ..c+
 359                         ..d-
 360                         ...ef+
 361                         .....gh+
 362                         x-
 363                         .x+
 364                         .y+
 365                         z+
 366                         `},
 367                 {"abracadabra;abracadabrakazam;abraham;abrasion", `-
 368                         a-
 369                         .bra-
 370                         ....c-
 371                         .....adabra+
 372                         ...........kazam+
 373                         ....h-
 374                         .....am+
 375                         ....s-
 376                         .....ion+
 377                         `},
 378                 {"aaa;aa;a;i;longerst;longer;long;xx;x;X;Y", `-
 379                         X+
 380                         Y+
 381                         a+
 382                         .a+
 383                         ..a+
 384                         i+
 385                         l-
 386                         .ong+
 387                         ....er+
 388                         ......st+
 389                         x+
 390                         .x+
 391                         `},
 392                 {"foo;;foo;foo1", `+
 393                         f-
 394                         .oo+
 395                         ...1+
 396                         `},
 397         }
 398
 399         for _, tc := range testCases {
 400                 keys := Split(tc.in, ";")
 401                 args := make([]string, len(keys)*2)
 402                 for i, key := range keys {
 403                         args[i*2] = key
 404                 }
 405
 406                 got := NewReplacer(args...).PrintTrie()
 407                 // Remove tabs from tc.out
 408                 wantbuf := make([]byte, 0, len(tc.out))
 409                 for i := 0; i < len(tc.out); i++ {
 410                         if tc.out[i] != '\t' {
 411                                 wantbuf = append(wantbuf, tc.out[i])
 412                         }
 413                 }
 414                 want := string(wantbuf)
 415
 416                 if got != want {
 417                         t.Errorf("PrintTrie(%q)\ngot\n%swant\n%s", tc.in, got, want)
 418                 }
 419         }
 420 }
 421
 422 func BenchmarkGenericNoMatch(b *testing.B) {
 423         str := Repeat("A", 100) + Repeat("B", 100)
 424         generic := NewReplacer("a", "A", "b", "B", "12", "123") // varying lengths forces generic
 425         for i := 0; i < b.N; i++ {
 426                 generic.Replace(str)
 427         }
 428 }
 429
 430 func BenchmarkGenericMatch1(b *testing.B) {
 431         str := Repeat("a", 100) + Repeat("b", 100)
 432         generic := NewReplacer("a", "A", "b", "B", "12", "123")
 433         for i := 0; i < b.N; i++ {
 434                 generic.Replace(str)
 435         }
 436 }
 437
 438 func BenchmarkGenericMatch2(b *testing.B) {
 439         str := Repeat("It&apos;s &lt;b&gt;HTML&lt;/b&gt;!", 100)
 440         for i := 0; i < b.N; i++ {
 441                 htmlUnescaper.Replace(str)
 442         }
 443 }
 444
 445 func benchmarkSingleString(b *testing.B, pattern, text string) {
 446         r := NewReplacer(pattern, "[match]")
 447         b.SetBytes(int64(len(text)))
 448         b.ResetTimer()
 449         for i := 0; i < b.N; i++ {
 450                 r.Replace(text)
 451         }
 452 }
 453
 454 func BenchmarkSingleMaxSkipping(b *testing.B) {
 455         benchmarkSingleString(b, Repeat("b", 25), Repeat("a", 10000))
 456 }
 457
 458 func BenchmarkSingleLongSuffixFail(b *testing.B) {
 459         benchmarkSingleString(b, "b"+Repeat("a", 500), Repeat("a", 1002))
 460 }
 461
 462 func BenchmarkSingleMatch(b *testing.B) {
 463         benchmarkSingleString(b, "abcdef", Repeat("abcdefghijklmno", 1000))
 464 }
 465
 466 func BenchmarkByteByteNoMatch(b *testing.B) {
 467         str := Repeat("A", 100) + Repeat("B", 100)
 468         for i := 0; i < b.N; i++ {
 469                 capitalLetters.Replace(str)
 470         }
 471 }
 472
 473 func BenchmarkByteByteMatch(b *testing.B) {
 474         str := Repeat("a", 100) + Repeat("b", 100)
 475         for i := 0; i < b.N; i++ {
 476                 capitalLetters.Replace(str)
 477         }
 478 }
 479
 480 func BenchmarkByteStringMatch(b *testing.B) {
 481         str := "<" + Repeat("a", 99) + Repeat("b", 99) + ">"
 482         for i := 0; i < b.N; i++ {
 483                 htmlEscaper.Replace(str)
 484         }
 485 }
 486
 487 func BenchmarkHTMLEscapeNew(b *testing.B) {
 488         str := "I <3 to escape HTML & other text too."
 489         for i := 0; i < b.N; i++ {
 490                 htmlEscaper.Replace(str)
 491         }
 492 }
 493
 494 func BenchmarkHTMLEscapeOld(b *testing.B) {
 495         str := "I <3 to escape HTML & other text too."
 496         for i := 0; i < b.N; i++ {
 497                 oldHTMLEscape(str)
 498         }
 499 }
 500
 501 func BenchmarkByteStringReplacerWriteString(b *testing.B) {
 502         str := Repeat("I <3 to escape HTML & other text too.", 100)
 503         buf := new(bytes.Buffer)
 504         for i := 0; i < b.N; i++ {
 505                 htmlEscaper.WriteString(buf, str)
 506                 buf.Reset()
 507         }
 508 }
 509
 510 func BenchmarkByteReplacerWriteString(b *testing.B) {
 511         str := Repeat("abcdefghijklmnopqrstuvwxyz", 100)
 512         buf := new(bytes.Buffer)
 513         for i := 0; i < b.N; i++ {
 514                 capitalLetters.WriteString(buf, str)
 515                 buf.Reset()
 516         }
 517 }
 518
 519 // BenchmarkByteByteReplaces compares byteByteImpl against multiple Replaces.
 520 func BenchmarkByteByteReplaces(b *testing.B) {
 521         str := Repeat("a", 100) + Repeat("b", 100)
 522         for i := 0; i < b.N; i++ {
 523                 Replace(Replace(str, "a", "A", -1), "b", "B", -1)
 524         }
 525 }
 526
 527 // BenchmarkByteByteMap compares byteByteImpl against Map.
 528 func BenchmarkByteByteMap(b *testing.B) {
 529         str := Repeat("a", 100) + Repeat("b", 100)
 530         fn := func(r rune) rune {
 531                 switch r {
 532                 case 'a':
 533                         return 'A'
 534                 case 'b':
 535                         return 'B'
 536                 }
 537                 return r
 538         }
 539         for i := 0; i < b.N; i++ {
 540                 Map(fn, str)
 541         }
 542 }
 543
 544 var mapdata = []struct{ name, data string }{
 545         {"ASCII", "a b c d e f g h i j k l m n o p q r s t u v w x y z"},
 546         {"Greek", "α β γ δ ε ζ η θ ι κ λ μ ν ξ ο π ρ ς σ τ υ φ χ ψ ω"},
 547 }
 548
 549 func BenchmarkMap(b *testing.B) {
 550         mapidentity := func(r rune) rune {
 551                 return r
 552         }
 553
 554         b.Run("identity", func(b *testing.B) {
 555                 for _, md := range mapdata {
 556                         b.Run(md.name, func(b *testing.B) {
 557                                 for i := 0; i < b.N; i++ {
 558                                         Map(mapidentity, md.data)
 559                                 }
 560                         })
 561                 }
 562         })
 563
 564         mapchange := func(r rune) rune {
 565                 if 'a' <= r && r <= 'z' {
 566                         return r + 'A' - 'a'
 567                 }
 568                 if 'α' <= r && r <= 'ω' {
 569                         return r + 'Α' - 'α'
 570                 }
 571                 return r
 572         }
 573
 574         b.Run("change", func(b *testing.B) {
 575                 for _, md := range mapdata {
 576                         b.Run(md.name, func(b *testing.B) {
 577                                 for i := 0; i < b.N; i++ {
 578                                         Map(mapchange, md.data)
 579                                 }
 580                         })
 581                 }
 582         })
 583 }