intervals_test.go

Documentation: cmd/compile/internal/liveness

     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  
     5  package liveness
     6  
     7  import (
     8  	"flag"
     9  	"fmt"
    10  	"math/rand"
    11  	"os"
    12  	"sort"
    13  	"testing"
    14  )
    15  
    16  func TestMain(m *testing.M) {
    17  	flag.Parse()
    18  	os.Exit(m.Run())
    19  }
    20  
    21  func 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  
    83  func 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  
   120  func 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  
   157  func 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  
   219  func 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  
   291  var seedflag = flag.Int64("seed", 101, "Random seed")
   292  var trialsflag = flag.Int64("trials", 10000, "Number of trials")
   293  var segsflag = flag.Int64("segs", 4, "Max segments within interval")
   294  var 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  
   299  func 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  
   341  func 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  
   407  func 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.
   516  func 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
View as plain text