.config/coc/extensions/coc-go-data/tools/pkg/mod/github.com/google/go-cmp@v0.5.4/cmp/internal/diff/diff_test.go

   1 // Copyright 2017, 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 diff
   6
   7 import (
   8         "fmt"
   9         "math/rand"
  10         "strings"
  11         "testing"
  12         "unicode"
  13 )
  14
  15 func TestDifference(t *testing.T) {
  16         tests := []struct {
  17                 // Before passing x and y to Difference, we strip all spaces so that
  18                 // they can be used by the test author to indicate a missing symbol
  19                 // in one of the lists.
  20                 x, y string
  21                 want string // '|' separated list of possible outputs
  22         }{{
  23                 x:    "",
  24                 y:    "",
  25                 want: "",
  26         }, {
  27                 x:    "#",
  28                 y:    "#",
  29                 want: ".",
  30         }, {
  31                 x:    "##",
  32                 y:    "# ",
  33                 want: ".X|X.",
  34         }, {
  35                 x:    "a#",
  36                 y:    "A ",
  37                 want: "MX",
  38         }, {
  39                 x:    "#a",
  40                 y:    " A",
  41                 want: "XM",
  42         }, {
  43                 x:    "# ",
  44                 y:    "##",
  45                 want: ".Y|Y.",
  46         }, {
  47                 x:    " #",
  48                 y:    "@#",
  49                 want: "Y.",
  50         }, {
  51                 x:    "@#",
  52                 y:    " #",
  53                 want: "X.",
  54         }, {
  55                 x:    "##########0123456789",
  56                 y:    "          0123456789",
  57                 want: "XXXXXXXXXX..........",
  58         }, {
  59                 x:    "          0123456789",
  60                 y:    "##########0123456789",
  61                 want: "YYYYYYYYYY..........",
  62         }, {
  63                 x:    "#####0123456789#####",
  64                 y:    "     0123456789     ",
  65                 want: "XXXXX..........XXXXX",
  66         }, {
  67                 x:    "     0123456789     ",
  68                 y:    "#####0123456789#####",
  69                 want: "YYYYY..........YYYYY",
  70         }, {
  71                 x:    "01234##########56789",
  72                 y:    "01234          56789",
  73                 want: ".....XXXXXXXXXX.....",
  74         }, {
  75                 x:    "01234          56789",
  76                 y:    "01234##########56789",
  77                 want: ".....YYYYYYYYYY.....",
  78         }, {
  79                 x:    "0123456789##########",
  80                 y:    "0123456789          ",
  81                 want: "..........XXXXXXXXXX",
  82         }, {
  83                 x:    "0123456789          ",
  84                 y:    "0123456789##########",
  85                 want: "..........YYYYYYYYYY",
  86         }, {
  87                 x:    "abcdefghij0123456789",
  88                 y:    "ABCDEFGHIJ0123456789",
  89                 want: "MMMMMMMMMM..........",
  90         }, {
  91                 x:    "ABCDEFGHIJ0123456789",
  92                 y:    "abcdefghij0123456789",
  93                 want: "MMMMMMMMMM..........",
  94         }, {
  95                 x:    "01234abcdefghij56789",
  96                 y:    "01234ABCDEFGHIJ56789",
  97                 want: ".....MMMMMMMMMM.....",
  98         }, {
  99                 x:    "01234ABCDEFGHIJ56789",
 100                 y:    "01234abcdefghij56789",
 101                 want: ".....MMMMMMMMMM.....",
 102         }, {
 103                 x:    "0123456789abcdefghij",
 104                 y:    "0123456789ABCDEFGHIJ",
 105                 want: "..........MMMMMMMMMM",
 106         }, {
 107                 x:    "0123456789ABCDEFGHIJ",
 108                 y:    "0123456789abcdefghij",
 109                 want: "..........MMMMMMMMMM",
 110         }, {
 111                 x:    "ABCDEFGHIJ0123456789          ",
 112                 y:    "          0123456789abcdefghij",
 113                 want: "XXXXXXXXXX..........YYYYYYYYYY",
 114         }, {
 115                 x:    "          0123456789abcdefghij",
 116                 y:    "ABCDEFGHIJ0123456789          ",
 117                 want: "YYYYYYYYYY..........XXXXXXXXXX",
 118         }, {
 119                 x:    "ABCDE0123456789     FGHIJ",
 120                 y:    "     0123456789abcdefghij",
 121                 want: "XXXXX..........YYYYYMMMMM",
 122         }, {
 123                 x:    "     0123456789abcdefghij",
 124                 y:    "ABCDE0123456789     FGHIJ",
 125                 want: "YYYYY..........XXXXXMMMMM",
 126         }, {
 127                 x:    "ABCDE01234F G H I J 56789     ",
 128                 y:    "     01234 a b c d e56789fghij",
 129                 want: "XXXXX.....XYXYXYXYXY.....YYYYY",
 130         }, {
 131                 x:    "     01234a b c d e 56789fghij",
 132                 y:    "ABCDE01234 F G H I J56789     ",
 133                 want: "YYYYY.....XYXYXYXYXY.....XXXXX",
 134         }, {
 135                 x:    "FGHIJ01234ABCDE56789     ",
 136                 y:    "     01234abcde56789fghij",
 137                 want: "XXXXX.....MMMMM.....YYYYY",
 138         }, {
 139                 x:    "     01234abcde56789fghij",
 140                 y:    "FGHIJ01234ABCDE56789     ",
 141                 want: "YYYYY.....MMMMM.....XXXXX",
 142         }, {
 143                 x:    "ABCAB BA ",
 144                 y:    "  C BABAC",
 145                 want: "XX.X.Y..Y|XX.Y.X..Y",
 146         }, {
 147                 x:    "# ####  ###",
 148                 y:    "#y####yy###",
 149                 want: ".Y....YY...",
 150         }, {
 151                 x:    "# #### # ##x#x",
 152                 y:    "#y####y y## # ",
 153                 want: ".Y....YXY..X.X",
 154         }, {
 155                 x:    "###z#z###### x  #",
 156                 y:    "#y##Z#Z###### yy#",
 157                 want: ".Y..M.M......XYY.",
 158         }, {
 159                 x:    "0 12z3x 456789 x x 0",
 160                 y:    "0y12Z3 y456789y y y0",
 161                 want: ".Y..M.XY......YXYXY.|.Y..M.XY......XYXYY.",
 162         }, {
 163                 x:    "0 2 4 6 8 ..................abXXcdEXF.ghXi",
 164                 y:    " 1 3 5 7 9..................AB  CDE F.GH I",
 165                 want: "XYXYXYXYXY..................MMXXMM.X..MMXM",
 166         }, {
 167                 x:    "I HG.F EDC  BA..................9 7 5 3 1 ",
 168                 y:    "iXhg.FXEdcXXba.................. 8 6 4 2 0",
 169                 want: "MYMM..Y.MMYYMM..................XYXYXYXYXY",
 170         }, {
 171                 x:    "x1234",
 172                 y:    " 1234",
 173                 want: "X....",
 174         }, {
 175                 x:    "x123x4",
 176                 y:    " 123 4",
 177                 want: "X...X.",
 178         }, {
 179                 x:    "x1234x56",
 180                 y:    " 1234   ",
 181                 want: "X....XXX",
 182         }, {
 183                 x:    "x1234xxx56",
 184                 y:    " 1234   56",
 185                 want: "X....XXX..",
 186         }, {
 187                 x:    ".1234...ab",
 188                 y:    " 1234   AB",
 189                 want: "X....XXXMM",
 190         }, {
 191                 x:    "x1234xxab.",
 192                 y:    " 1234  AB ",
 193                 want: "X....XXMMX",
 194         }, {
 195                 x:    " 0123456789",
 196                 y:    "9012345678 ",
 197                 want: "Y.........X",
 198         }, {
 199                 x:    "  0123456789",
 200                 y:    "8901234567  ",
 201                 want: "YY........XX",
 202         }, {
 203                 x:    "   0123456789",
 204                 y:    "7890123456   ",
 205                 want: "YYY.......XXX",
 206         }, {
 207                 x:    "    0123456789",
 208                 y:    "6789012345    ",
 209                 want: "YYYY......XXXX",
 210         }, {
 211                 x:    "0123456789     ",
 212                 y:    "     5678901234",
 213                 want: "XXXXX.....YYYYY|YYYYY.....XXXXX",
 214         }, {
 215                 x:    "0123456789    ",
 216                 y:    "    4567890123",
 217                 want: "XXXX......YYYY",
 218         }, {
 219                 x:    "0123456789   ",
 220                 y:    "   3456789012",
 221                 want: "XXX.......YYY",
 222         }, {
 223                 x:    "0123456789  ",
 224                 y:    "  2345678901",
 225                 want: "XX........YY",
 226         }, {
 227                 x:    "0123456789 ",
 228                 y:    " 1234567890",
 229                 want: "X.........Y",
 230         }, {
 231                 x:    "0 1 2 3 45 6 7 8 9 ",
 232                 y:    " 9 8 7 6 54 3 2 1 0",
 233                 want: "XYXYXYXYX.YXYXYXYXY",
 234         }, {
 235                 x:    "0 1 2345678 9   ",
 236                 y:    " 6 72  5  819034",
 237                 want: "XYXY.XX.XX.Y.YYY",
 238         }, {
 239                 x:    "F B Q M O    I G T L       N72X90 E  4S P  651HKRJU DA 83CVZW",
 240                 y:    " 5 W H XO10R9IV K ZLCTAJ8P3N     SEQM4 7 2G6      UBD F      ",
 241                 want: "XYXYXYXY.YYYY.YXYXY.YYYYYYY.XXXXXY.YY.XYXYY.XXXXXX.Y.XYXXXXXX",
 242         }}
 243
 244         for _, tt := range tests {
 245                 t.Run("", func(t *testing.T) {
 246                         x := strings.Replace(tt.x, " ", "", -1)
 247                         y := strings.Replace(tt.y, " ", "", -1)
 248                         es := testStrings(t, x, y)
 249                         var want string
 250                         got := es.String()
 251                         for _, want = range strings.Split(tt.want, "|") {
 252                                 if got == want {
 253                                         return
 254                                 }
 255                         }
 256                         t.Errorf("Difference(%s, %s):\ngot  %s\nwant %s", x, y, got, want)
 257                 })
 258         }
 259 }
 260
 261 func TestDifferenceFuzz(t *testing.T) {
 262         tests := []struct{ px, py, pm float32 }{
 263                 {px: 0.0, py: 0.0, pm: 0.1},
 264                 {px: 0.0, py: 0.1, pm: 0.0},
 265                 {px: 0.1, py: 0.0, pm: 0.0},
 266                 {px: 0.0, py: 0.1, pm: 0.1},
 267                 {px: 0.1, py: 0.0, pm: 0.1},
 268                 {px: 0.2, py: 0.2, pm: 0.2},
 269                 {px: 0.3, py: 0.1, pm: 0.2},
 270                 {px: 0.1, py: 0.3, pm: 0.2},
 271                 {px: 0.2, py: 0.2, pm: 0.2},
 272                 {px: 0.3, py: 0.3, pm: 0.3},
 273                 {px: 0.1, py: 0.1, pm: 0.5},
 274                 {px: 0.4, py: 0.1, pm: 0.5},
 275                 {px: 0.3, py: 0.2, pm: 0.5},
 276                 {px: 0.2, py: 0.3, pm: 0.5},
 277                 {px: 0.1, py: 0.4, pm: 0.5},
 278         }
 279
 280         for i, tt := range tests {
 281                 t.Run(fmt.Sprintf("P%d", i), func(t *testing.T) {
 282                         // Sweep from 1B to 1KiB.
 283                         for n := 1; n <= 1024; n <<= 1 {
 284                                 t.Run(fmt.Sprintf("N%d", n), func(t *testing.T) {
 285                                         for j := 0; j < 10; j++ {
 286                                                 x, y := generateStrings(n, tt.px, tt.py, tt.pm, int64(j))
 287                                                 testStrings(t, x, y)
 288                                         }
 289                                 })
 290                         }
 291                 })
 292         }
 293 }
 294
 295 func BenchmarkDifference(b *testing.B) {
 296         for n := 1 << 10; n <= 1<<20; n <<= 2 {
 297                 b.Run(fmt.Sprintf("N%d", n), func(b *testing.B) {
 298                         x, y := generateStrings(n, 0.05, 0.05, 0.10, 0)
 299                         b.ReportAllocs()
 300                         b.SetBytes(int64(len(x) + len(y)))
 301                         for i := 0; i < b.N; i++ {
 302                                 Difference(len(x), len(y), func(ix, iy int) Result {
 303                                         return compareByte(x[ix], y[iy])
 304                                 })
 305                         }
 306                 })
 307         }
 308 }
 309
 310 func generateStrings(n int, px, py, pm float32, seed int64) (string, string) {
 311         if px+py+pm > 1.0 {
 312                 panic("invalid probabilities")
 313         }
 314         py += px
 315         pm += py
 316
 317         b := make([]byte, n)
 318         r := rand.New(rand.NewSource(seed))
 319         r.Read(b)
 320
 321         var x, y []byte
 322         for len(b) > 0 {
 323                 switch p := r.Float32(); {
 324                 case p < px: // UniqueX
 325                         x = append(x, b[0])
 326                 case p < py: // UniqueY
 327                         y = append(y, b[0])
 328                 case p < pm: // Modified
 329                         x = append(x, 'A'+(b[0]%26))
 330                         y = append(y, 'a'+(b[0]%26))
 331                 default: // Identity
 332                         x = append(x, b[0])
 333                         y = append(y, b[0])
 334                 }
 335                 b = b[1:]
 336         }
 337         return string(x), string(y)
 338 }
 339
 340 func testStrings(t *testing.T, x, y string) EditScript {
 341         es := Difference(len(x), len(y), func(ix, iy int) Result {
 342                 return compareByte(x[ix], y[iy])
 343         })
 344         if es.LenX() != len(x) {
 345                 t.Errorf("es.LenX = %d, want %d", es.LenX(), len(x))
 346         }
 347         if es.LenY() != len(y) {
 348                 t.Errorf("es.LenY = %d, want %d", es.LenY(), len(y))
 349         }
 350         if !validateScript(x, y, es) {
 351                 t.Errorf("invalid edit script: %v", es)
 352         }
 353         return es
 354 }
 355
 356 func validateScript(x, y string, es EditScript) bool {
 357         var bx, by []byte
 358         for _, e := range es {
 359                 switch e {
 360                 case Identity:
 361                         if !compareByte(x[len(bx)], y[len(by)]).Equal() {
 362                                 return false
 363                         }
 364                         bx = append(bx, x[len(bx)])
 365                         by = append(by, y[len(by)])
 366                 case UniqueX:
 367                         bx = append(bx, x[len(bx)])
 368                 case UniqueY:
 369                         by = append(by, y[len(by)])
 370                 case Modified:
 371                         if !compareByte(x[len(bx)], y[len(by)]).Similar() {
 372                                 return false
 373                         }
 374                         bx = append(bx, x[len(bx)])
 375                         by = append(by, y[len(by)])
 376                 }
 377         }
 378         return string(bx) == x && string(by) == y
 379 }
 380
 381 // compareByte returns a Result where the result is Equal if x == y,
 382 // similar if x and y differ only in casing, and different otherwise.
 383 func compareByte(x, y byte) (r Result) {
 384         switch {
 385         case x == y:
 386                 return equalResult // Identity
 387         case unicode.ToUpper(rune(x)) == unicode.ToUpper(rune(y)):
 388                 return similarResult // Modified
 389         default:
 390                 return differentResult // UniqueX or UniqueY
 391         }
 392 }
 393
 394 var (
 395         equalResult     = Result{NumDiff: 0}
 396         similarResult   = Result{NumDiff: 1}
 397         differentResult = Result{NumDiff: 2}
 398 )
 399
 400 func TestResult(t *testing.T) {
 401         tests := []struct {
 402                 result      Result
 403                 wantEqual   bool
 404                 wantSimilar bool
 405         }{
 406                 // equalResult is equal since NumDiff == 0, by definition of Equal method.
 407                 {equalResult, true, true},
 408                 // similarResult is similar since it is a binary result where only one
 409                 // element was compared (i.e., Either NumSame==1 or NumDiff==1).
 410                 {similarResult, false, true},
 411                 // differentResult is different since there are enough differences that
 412                 // it isn't even considered similar.
 413                 {differentResult, false, false},
 414
 415                 // Zero value is always equal.
 416                 {Result{NumSame: 0, NumDiff: 0}, true, true},
 417
 418                 // Binary comparisons (where NumSame+NumDiff == 1) are always similar.
 419                 {Result{NumSame: 1, NumDiff: 0}, true, true},
 420                 {Result{NumSame: 0, NumDiff: 1}, false, true},
 421
 422                 // More complex ratios. The exact ratio for similarity may change,
 423                 // and may require updates to these test cases.
 424                 {Result{NumSame: 1, NumDiff: 1}, false, true},
 425                 {Result{NumSame: 1, NumDiff: 2}, false, true},
 426                 {Result{NumSame: 1, NumDiff: 3}, false, false},
 427                 {Result{NumSame: 2, NumDiff: 1}, false, true},
 428                 {Result{NumSame: 2, NumDiff: 2}, false, true},
 429                 {Result{NumSame: 2, NumDiff: 3}, false, true},
 430                 {Result{NumSame: 3, NumDiff: 1}, false, true},
 431                 {Result{NumSame: 3, NumDiff: 2}, false, true},
 432                 {Result{NumSame: 3, NumDiff: 3}, false, true},
 433                 {Result{NumSame: 1000, NumDiff: 0}, true, true},
 434                 {Result{NumSame: 1000, NumDiff: 1}, false, true},
 435                 {Result{NumSame: 1000, NumDiff: 2}, false, true},
 436                 {Result{NumSame: 0, NumDiff: 1000}, false, false},
 437                 {Result{NumSame: 1, NumDiff: 1000}, false, false},
 438                 {Result{NumSame: 2, NumDiff: 1000}, false, false},
 439         }
 440
 441         for _, tt := range tests {
 442                 if got := tt.result.Equal(); got != tt.wantEqual {
 443                         t.Errorf("%#v.Equal() = %v, want %v", tt.result, got, tt.wantEqual)
 444                 }
 445                 if got := tt.result.Similar(); got != tt.wantSimilar {
 446                         t.Errorf("%#v.Similar() = %v, want %v", tt.result, got, tt.wantSimilar)
 447                 }
 448         }
 449 }