1// Copyright 2024 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 5package liveness 6 7import ( 8 "flag" 9 "fmt" 10 "math/rand" 11 "os" 12 "sort" 13 "testing" 14) 15 16func TestMain(m *testing.M) { 17 flag.Parse() 18 os.Exit(m.Run()) 19} 20 21func TestMakeAndPrint(t *testing.T) { 22 testcases := []struct { 23 inp []int 24 exp string 25 err bool 26 }{ 27 { 28 inp: []int{0, 1, 2, 3}, 29 exp: "[0,1) [2,3)", 30 }, 31 { // degenerate but legal 32 inp: []int{0, 1, 1, 2}, 33 exp: "[0,1) [1,2)", 34 }, 35 { // odd number of elems 36 inp: []int{0}, 37 err: true, 38 exp: "odd number of elems 1", 39 }, 40 { 41 // bad range element 42 inp: []int{0, 0}, 43 err: true, 44 exp: "bad range elem 0:0, en<=st", 45 }, 46 { 47 // overlap w/ previous 48 inp: []int{0, 9, 3, 12}, 49 err: true, 50 exp: "bad range elem 3:12 overlaps prev 0:9", 51 }, 52 { 53 // range starts not ordered 54 inp: []int{10, 11, 3, 4}, 55 err: true, 56 exp: "range start not ordered 3:4 less than prev 10:11", 57 }, 58 } 59 60 for k, tc := range testcases { 61 is, err := makeIntervals(tc.inp...) 62 want := tc.exp 63 if err != nil { 64 if !tc.err { 65 t.Fatalf("unexpected error on tc:%d %+v -> %v", k, tc.inp, err) 66 } else { 67 got := fmt.Sprintf("%v", err) 68 if got != want { 69 t.Fatalf("bad error on tc:%d %+v got %q want %q", k, tc.inp, got, want) 70 } 71 } 72 continue 73 } else if tc.err { 74 t.Fatalf("missing error on tc:%d %+v return was %q", k, tc.inp, is.String()) 75 } 76 got := is.String() 77 if got != want { 78 t.Fatalf("exp mismatch on tc:%d %+v got %q want %q", k, tc.inp, got, want) 79 } 80 } 81} 82 83func TestIntervalOverlap(t *testing.T) { 84 testcases := []struct { 85 i1, i2 Interval 86 exp bool 87 }{ 88 { 89 i1: Interval{st: 0, en: 1}, 90 i2: Interval{st: 0, en: 1}, 91 exp: true, 92 }, 93 { 94 i1: Interval{st: 0, en: 1}, 95 i2: Interval{st: 1, en: 2}, 96 exp: false, 97 }, 98 { 99 i1: Interval{st: 9, en: 10}, 100 i2: Interval{st: 1, en: 2}, 101 exp: false, 102 }, 103 { 104 i1: Interval{st: 0, en: 10}, 105 i2: Interval{st: 5, en: 6}, 106 exp: true, 107 }, 108 } 109 110 for _, tc := range testcases { 111 want := tc.exp 112 got := tc.i1.Overlaps(tc.i2) 113 if want != got { 114 t.Fatalf("Overlaps([%d,%d), [%d,%d)): got %v want %v", 115 tc.i1.st, tc.i1.en, tc.i2.st, tc.i2.en, got, want) 116 } 117 } 118} 119 120func TestIntervalAdjacent(t *testing.T) { 121 testcases := []struct { 122 i1, i2 Interval 123 exp bool 124 }{ 125 { 126 i1: Interval{st: 0, en: 1}, 127 i2: Interval{st: 0, en: 1}, 128 exp: false, 129 }, 130 { 131 i1: Interval{st: 0, en: 1}, 132 i2: Interval{st: 1, en: 2}, 133 exp: true, 134 }, 135 { 136 i1: Interval{st: 1, en: 2}, 137 i2: Interval{st: 0, en: 1}, 138 exp: true, 139 }, 140 { 141 i1: Interval{st: 0, en: 10}, 142 i2: Interval{st: 0, en: 3}, 143 exp: false, 144 }, 145 } 146 147 for k, tc := range testcases { 148 want := tc.exp 149 got := tc.i1.adjacent(tc.i2) 150 if want != got { 151 t.Fatalf("tc=%d adjacent([%d,%d), [%d,%d)): got %v want %v", 152 k, tc.i1.st, tc.i1.en, tc.i2.st, tc.i2.en, got, want) 153 } 154 } 155} 156 157func TestIntervalMerge(t *testing.T) { 158 testcases := []struct { 159 i1, i2 Interval 160 exp Interval 161 err bool 162 }{ 163 { 164 // error case 165 i1: Interval{st: 0, en: 1}, 166 i2: Interval{st: 2, en: 3}, 167 err: true, 168 }, 169 { 170 // same 171 i1: Interval{st: 0, en: 1}, 172 i2: Interval{st: 0, en: 1}, 173 exp: Interval{st: 0, en: 1}, 174 err: false, 175 }, 176 { 177 // adjacent 178 i1: Interval{st: 0, en: 1}, 179 i2: Interval{st: 1, en: 2}, 180 exp: Interval{st: 0, en: 2}, 181 err: false, 182 }, 183 { 184 // overlapping 1 185 i1: Interval{st: 0, en: 5}, 186 i2: Interval{st: 3, en: 10}, 187 exp: Interval{st: 0, en: 10}, 188 err: false, 189 }, 190 { 191 // overlapping 2 192 i1: Interval{st: 9, en: 15}, 193 i2: Interval{st: 3, en: 11}, 194 exp: Interval{st: 3, en: 15}, 195 err: false, 196 }, 197 } 198 199 for k, tc := range testcases { 200 var dst Interval 201 dstp := &dst 202 dst = tc.i1 203 err := dstp.MergeInto(tc.i2) 204 if (err != nil) != tc.err { 205 t.Fatalf("tc=%d MergeInto([%d,%d) <= [%d,%d)): got err=%v want err=%v", k, tc.i1.st, tc.i1.en, tc.i2.st, tc.i2.en, err, tc.err) 206 } 207 if err != nil { 208 continue 209 } 210 want := tc.exp.String() 211 got := dst.String() 212 if want != got { 213 t.Fatalf("tc=%d MergeInto([%d,%d) <= [%d,%d)): got %v want %v", 214 k, tc.i1.st, tc.i1.en, tc.i2.st, tc.i2.en, got, want) 215 } 216 } 217} 218 219func TestIntervalsOverlap(t *testing.T) { 220 testcases := []struct { 221 inp1, inp2 []int 222 exp bool 223 }{ 224 { 225 // first empty 226 inp1: []int{}, 227 inp2: []int{1, 2}, 228 exp: false, 229 }, 230 { 231 // second empty 232 inp1: []int{9, 10}, 233 inp2: []int{}, 234 exp: false, 235 }, 236 { 237 // disjoint 1 238 inp1: []int{1, 2}, 239 inp2: []int{2, 3}, 240 exp: false, 241 }, 242 { 243 // disjoint 2 244 inp1: []int{2, 3}, 245 inp2: []int{1, 2}, 246 exp: false, 247 }, 248 { 249 // interleaved 1 250 inp1: []int{1, 2, 3, 4}, 251 inp2: []int{2, 3, 5, 6}, 252 exp: false, 253 }, 254 { 255 // interleaved 2 256 inp1: []int{2, 3, 5, 6}, 257 inp2: []int{1, 2, 3, 4}, 258 exp: false, 259 }, 260 { 261 // overlap 1 262 inp1: []int{1, 3}, 263 inp2: []int{2, 9, 10, 11}, 264 exp: true, 265 }, 266 { 267 // overlap 2 268 inp1: []int{18, 29}, 269 inp2: []int{2, 9, 10, 19}, 270 exp: true, 271 }, 272 } 273 274 for k, tc := range testcases { 275 is1, err1 := makeIntervals(tc.inp1...) 276 if err1 != nil { 277 t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.inp1, err1) 278 } 279 is2, err2 := makeIntervals(tc.inp2...) 280 if err2 != nil { 281 t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.inp2, err2) 282 } 283 got := is1.Overlaps(is2) 284 want := tc.exp 285 if got != want { 286 t.Fatalf("overlaps mismatch on tc:%d %+v %+v got %v want %v", k, tc.inp1, tc.inp2, got, want) 287 } 288 } 289} 290 291var seedflag = flag.Int64("seed", 101, "Random seed") 292var trialsflag = flag.Int64("trials", 10000, "Number of trials") 293var segsflag = flag.Int64("segs", 4, "Max segments within interval") 294var limitflag = flag.Int64("limit", 20, "Limit of interval max end") 295 296// NB: consider turning this into a fuzz test if the interval data 297// structures or code get any more complicated. 298 299func TestRandomIntervalsOverlap(t *testing.T) { 300 rand.Seed(*seedflag) 301 302 // Return a pseudo-random intervals object with 0-3 segments within 303 // the range of 0 to limit 304 mk := func() Intervals { 305 vals := rand.Perm(int(*limitflag)) 306 // decide how many segments 307 segs := rand.Intn(int(*segsflag)) 308 picked := vals[:(segs * 2)] 309 sort.Ints(picked) 310 ii, err := makeIntervals(picked...) 311 if err != nil { 312 t.Fatalf("makeIntervals(%+v) returns err %v", picked, err) 313 } 314 return ii 315 } 316 317 brute := func(i1, i2 Intervals) bool { 318 for i := range i1 { 319 for j := range i2 { 320 if i1[i].Overlaps(i2[j]) { 321 return true 322 } 323 } 324 } 325 return false 326 } 327 328 for k := range *trialsflag { 329 // Create two interval ranges and test if they overlap. Then 330 // compare the overlap with a brute-force overlap calculation. 331 i1, i2 := mk(), mk() 332 got := i1.Overlaps(i2) 333 want := brute(i1, i2) 334 if got != want { 335 t.Fatalf("overlap mismatch on t:%d %v %v got %v want %v", 336 k, i1, i2, got, want) 337 } 338 } 339} 340 341func TestIntervalsMerge(t *testing.T) { 342 testcases := []struct { 343 inp1, inp2 []int 344 exp []int 345 }{ 346 { 347 // first empty 348 inp1: []int{}, 349 inp2: []int{1, 2}, 350 exp: []int{1, 2}, 351 }, 352 { 353 // second empty 354 inp1: []int{1, 2}, 355 inp2: []int{}, 356 exp: []int{1, 2}, 357 }, 358 { 359 // overlap 1 360 inp1: []int{1, 2}, 361 inp2: []int{2, 3}, 362 exp: []int{1, 3}, 363 }, 364 { 365 // overlap 2 366 inp1: []int{1, 5}, 367 inp2: []int{2, 10}, 368 exp: []int{1, 10}, 369 }, 370 { 371 // non-overlap 1 372 inp1: []int{1, 2}, 373 inp2: []int{11, 12}, 374 exp: []int{1, 2, 11, 12}, 375 }, 376 { 377 // non-overlap 2 378 inp1: []int{1, 2, 3, 4, 5, 6}, 379 inp2: []int{2, 3, 4, 5, 6, 7}, 380 exp: []int{1, 7}, 381 }, 382 } 383 384 for k, tc := range testcases { 385 is1, err1 := makeIntervals(tc.inp1...) 386 if err1 != nil { 387 t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.inp1, err1) 388 } 389 is2, err2 := makeIntervals(tc.inp2...) 390 if err2 != nil { 391 t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.inp2, err2) 392 } 393 m := is1.Merge(is2) 394 wis, werr := makeIntervals(tc.exp...) 395 if werr != nil { 396 t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.exp, werr) 397 } 398 want := wis.String() 399 got := m.String() 400 if want != got { 401 t.Fatalf("k=%d Merge(%s, %s): got %v want %v", 402 k, is1, is2, m, want) 403 } 404 } 405} 406 407func TestBuilder(t *testing.T) { 408 type posLiveKill struct { 409 pos int 410 becomesLive, isKill bool // what to pass to IntervalsBuilder 411 } 412 testcases := []struct { 413 inp []posLiveKill 414 exp []int 415 aerr, ferr bool 416 }{ 417 // error case, position non-decreasing 418 { 419 inp: []posLiveKill{ 420 posLiveKill{pos: 10, becomesLive: true}, 421 posLiveKill{pos: 18, isKill: true}, 422 }, 423 aerr: true, 424 }, 425 // error case, position negative 426 { 427 inp: []posLiveKill{ 428 posLiveKill{pos: -1, becomesLive: true}, 429 }, 430 aerr: true, 431 }, 432 // empty 433 { 434 exp: nil, 435 }, 436 // single BB 437 { 438 inp: []posLiveKill{ 439 posLiveKill{pos: 10, becomesLive: true}, 440 posLiveKill{pos: 9, isKill: true}, 441 }, 442 exp: []int{10, 11}, 443 }, 444 // couple of BBs 445 { 446 inp: []posLiveKill{ 447 posLiveKill{pos: 11, becomesLive: true}, 448 posLiveKill{pos: 10, becomesLive: true}, 449 posLiveKill{pos: 9, isKill: true}, 450 posLiveKill{pos: 4, becomesLive: true}, 451 posLiveKill{pos: 1, isKill: true}, 452 }, 453 exp: []int{2, 5, 10, 12}, 454 }, 455 // couple of BBs 456 { 457 inp: []posLiveKill{ 458 posLiveKill{pos: 20, isKill: true}, 459 posLiveKill{pos: 19, isKill: true}, 460 posLiveKill{pos: 17, becomesLive: true}, 461 posLiveKill{pos: 14, becomesLive: true}, 462 posLiveKill{pos: 10, isKill: true}, 463 posLiveKill{pos: 4, becomesLive: true}, 464 posLiveKill{pos: 0, isKill: true}, 465 }, 466 exp: []int{1, 5, 11, 18}, 467 }, 468 } 469 470 for k, tc := range testcases { 471 var c IntervalsBuilder 472 var aerr error 473 for _, event := range tc.inp { 474 if event.becomesLive { 475 if err := c.Live(event.pos); err != nil { 476 aerr = err 477 break 478 } 479 } 480 if event.isKill { 481 if err := c.Kill(event.pos); err != nil { 482 aerr = err 483 break 484 } 485 } 486 } 487 if (aerr != nil) != tc.aerr { 488 t.Fatalf("k=%d add err mismatch: tc.aerr:%v aerr!=nil:%v", 489 k, tc.aerr, (aerr != nil)) 490 } 491 if tc.aerr { 492 continue 493 } 494 ii, ferr := c.Finish() 495 if ferr != nil { 496 if tc.ferr { 497 continue 498 } 499 t.Fatalf("h=%d finish err mismatch: tc.ferr:%v ferr!=nil:%v", k, tc.ferr, ferr != nil) 500 } 501 got := ii.String() 502 wis, werr := makeIntervals(tc.exp...) 503 if werr != nil { 504 t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.exp, werr) 505 } 506 want := wis.String() 507 if want != got { 508 t.Fatalf("k=%d Ctor test: got %v want %v", k, got, want) 509 } 510 } 511} 512 513// makeIntervals constructs an Intervals object from the start/end 514// sequence in nums, expected to be of the form 515// s1,en1,st2,en2,...,stk,enk. Used only for unit testing. 516func makeIntervals(nums ...int) (Intervals, error) { 517 var r Intervals 518 if len(nums)&1 != 0 { 519 return r, fmt.Errorf("odd number of elems %d", len(nums)) 520 } 521 for i := 0; i < len(nums); i += 2 { 522 st := nums[i] 523 en := nums[i+1] 524 r = append(r, Interval{st: st, en: en}) 525 } 526 return r, check(r) 527} 528