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