src/cmd/compile/internal/liveness/intervals_test.go

// Copyright 2024 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package liveness

import (
	"flag"
	"fmt"
	"math/rand"
	"os"
	"sort"
	"testing"
)

func TestMain(m *testing.M) {
	flag.Parse()
	os.Exit(m.Run())
}

func TestMakeAndPrint(t *testing.T) {
	testcases := []struct {
		inp []int
		exp string
		err bool
	}{
		{
			inp: []int{0, 1, 2, 3},
			exp: "[0,1) [2,3)",
		},
		{ // degenerate but legal
			inp: []int{0, 1, 1, 2},
			exp: "[0,1) [1,2)",
		},
		{ // odd number of elems
			inp: []int{0},
			err: true,
			exp: "odd number of elems 1",
		},
		{
			// bad range element
			inp: []int{0, 0},
			err: true,
			exp: "bad range elem 0:0, en<=st",
		},
		{
			// overlap w/ previous
			inp: []int{0, 9, 3, 12},
			err: true,
			exp: "bad range elem 3:12 overlaps prev 0:9",
		},
		{
			// range starts not ordered
			inp: []int{10, 11, 3, 4},
			err: true,
			exp: "range start not ordered 3:4 less than prev 10:11",
		},
	}

	for k, tc := range testcases {
		is, err := makeIntervals(tc.inp...)
		want := tc.exp
		if err != nil {
			if !tc.err {
				t.Fatalf("unexpected error on tc:%d %+v -> %v", k, tc.inp, err)
			} else {
				got := fmt.Sprintf("%v", err)
				if got != want {
					t.Fatalf("bad error on tc:%d %+v got %q want %q", k, tc.inp, got, want)
				}
			}
			continue
		} else if tc.err {
			t.Fatalf("missing error on tc:%d %+v return was %q", k, tc.inp, is.String())
		}
		got := is.String()
		if got != want {
			t.Fatalf("exp mismatch on tc:%d %+v got %q want %q", k, tc.inp, got, want)
		}
	}
}

func TestIntervalOverlap(t *testing.T) {
	testcases := []struct {
		i1, i2 Interval
		exp    bool
	}{
		{
			i1:  Interval{st: 0, en: 1},
			i2:  Interval{st: 0, en: 1},
			exp: true,
		},
		{
			i1:  Interval{st: 0, en: 1},
			i2:  Interval{st: 1, en: 2},
			exp: false,
		},
		{
			i1:  Interval{st: 9, en: 10},
			i2:  Interval{st: 1, en: 2},
			exp: false,
		},
		{
			i1:  Interval{st: 0, en: 10},
			i2:  Interval{st: 5, en: 6},
			exp: true,
		},
	}

	for _, tc := range testcases {
		want := tc.exp
		got := tc.i1.Overlaps(tc.i2)
		if want != got {
			t.Fatalf("Overlaps([%d,%d), [%d,%d)): got %v want %v",
				tc.i1.st, tc.i1.en, tc.i2.st, tc.i2.en, got, want)
		}
	}
}

func TestIntervalAdjacent(t *testing.T) {
	testcases := []struct {
		i1, i2 Interval
		exp    bool
	}{
		{
			i1:  Interval{st: 0, en: 1},
			i2:  Interval{st: 0, en: 1},
			exp: false,
		},
		{
			i1:  Interval{st: 0, en: 1},
			i2:  Interval{st: 1, en: 2},
			exp: true,
		},
		{
			i1:  Interval{st: 1, en: 2},
			i2:  Interval{st: 0, en: 1},
			exp: true,
		},
		{
			i1:  Interval{st: 0, en: 10},
			i2:  Interval{st: 0, en: 3},
			exp: false,
		},
	}

	for k, tc := range testcases {
		want := tc.exp
		got := tc.i1.adjacent(tc.i2)
		if want != got {
			t.Fatalf("tc=%d adjacent([%d,%d), [%d,%d)): got %v want %v",
				k, tc.i1.st, tc.i1.en, tc.i2.st, tc.i2.en, got, want)
		}
	}
}

func TestIntervalMerge(t *testing.T) {
	testcases := []struct {
		i1, i2 Interval
		exp    Interval
		err    bool
	}{
		{
			// error case
			i1:  Interval{st: 0, en: 1},
			i2:  Interval{st: 2, en: 3},
			err: true,
		},
		{
			// same
			i1:  Interval{st: 0, en: 1},
			i2:  Interval{st: 0, en: 1},
			exp: Interval{st: 0, en: 1},
			err: false,
		},
		{
			// adjacent
			i1:  Interval{st: 0, en: 1},
			i2:  Interval{st: 1, en: 2},
			exp: Interval{st: 0, en: 2},
			err: false,
		},
		{
			// overlapping 1
			i1:  Interval{st: 0, en: 5},
			i2:  Interval{st: 3, en: 10},
			exp: Interval{st: 0, en: 10},
			err: false,
		},
		{
			// overlapping 2
			i1:  Interval{st: 9, en: 15},
			i2:  Interval{st: 3, en: 11},
			exp: Interval{st: 3, en: 15},
			err: false,
		},
	}

	for k, tc := range testcases {
		var dst Interval
		dstp := &dst
		dst = tc.i1
		err := dstp.MergeInto(tc.i2)
		if (err != nil) != tc.err {
			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)
		}
		if err != nil {
			continue
		}
		want := tc.exp.String()
		got := dst.String()
		if want != got {
			t.Fatalf("tc=%d MergeInto([%d,%d) <= [%d,%d)): got %v want %v",
				k, tc.i1.st, tc.i1.en, tc.i2.st, tc.i2.en, got, want)
		}
	}
}

func TestIntervalsOverlap(t *testing.T) {
	testcases := []struct {
		inp1, inp2 []int
		exp        bool
	}{
		{
			// first empty
			inp1: []int{},
			inp2: []int{1, 2},
			exp:  false,
		},
		{
			// second empty
			inp1: []int{9, 10},
			inp2: []int{},
			exp:  false,
		},
		{
			// disjoint 1
			inp1: []int{1, 2},
			inp2: []int{2, 3},
			exp:  false,
		},
		{
			// disjoint 2
			inp1: []int{2, 3},
			inp2: []int{1, 2},
			exp:  false,
		},
		{
			// interleaved 1
			inp1: []int{1, 2, 3, 4},
			inp2: []int{2, 3, 5, 6},
			exp:  false,
		},
		{
			// interleaved 2
			inp1: []int{2, 3, 5, 6},
			inp2: []int{1, 2, 3, 4},
			exp:  false,
		},
		{
			// overlap 1
			inp1: []int{1, 3},
			inp2: []int{2, 9, 10, 11},
			exp:  true,
		},
		{
			// overlap 2
			inp1: []int{18, 29},
			inp2: []int{2, 9, 10, 19},
			exp:  true,
		},
	}

	for k, tc := range testcases {
		is1, err1 := makeIntervals(tc.inp1...)
		if err1 != nil {
			t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.inp1, err1)
		}
		is2, err2 := makeIntervals(tc.inp2...)
		if err2 != nil {
			t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.inp2, err2)
		}
		got := is1.Overlaps(is2)
		want := tc.exp
		if got != want {
			t.Fatalf("overlaps mismatch on tc:%d %+v %+v got %v want %v", k, tc.inp1, tc.inp2, got, want)
		}
	}
}

var seedflag = flag.Int64("seed", 101, "Random seed")
var trialsflag = flag.Int64("trials", 10000, "Number of trials")
var segsflag = flag.Int64("segs", 4, "Max segments within interval")
var limitflag = flag.Int64("limit", 20, "Limit of interval max end")

// NB: consider turning this into a fuzz test if the interval data
// structures or code get any more complicated.

func TestRandomIntervalsOverlap(t *testing.T) {
	rand.Seed(*seedflag)

	// Return a pseudo-random intervals object with 0-3 segments within
	// the range of 0 to limit
	mk := func() Intervals {
		vals := rand.Perm(int(*limitflag))
		// decide how many segments
		segs := rand.Intn(int(*segsflag))
		picked := vals[:(segs * 2)]
		sort.Ints(picked)
		ii, err := makeIntervals(picked...)
		if err != nil {
			t.Fatalf("makeIntervals(%+v) returns err %v", picked, err)
		}
		return ii
	}

	brute := func(i1, i2 Intervals) bool {
		for i := range i1 {
			for j := range i2 {
				if i1[i].Overlaps(i2[j]) {
					return true
				}
			}
		}
		return false
	}

	for k := range *trialsflag {
		// Create two interval ranges and test if they overlap. Then
		// compare the overlap with a brute-force overlap calculation.
		i1, i2 := mk(), mk()
		got := i1.Overlaps(i2)
		want := brute(i1, i2)
		if got != want {
			t.Fatalf("overlap mismatch on t:%d %v %v got %v want %v",
				k, i1, i2, got, want)
		}
	}
}

func TestIntervalsMerge(t *testing.T) {
	testcases := []struct {
		inp1, inp2 []int
		exp        []int
	}{
		{
			// first empty
			inp1: []int{},
			inp2: []int{1, 2},
			exp:  []int{1, 2},
		},
		{
			// second empty
			inp1: []int{1, 2},
			inp2: []int{},
			exp:  []int{1, 2},
		},
		{
			// overlap 1
			inp1: []int{1, 2},
			inp2: []int{2, 3},
			exp:  []int{1, 3},
		},
		{
			// overlap 2
			inp1: []int{1, 5},
			inp2: []int{2, 10},
			exp:  []int{1, 10},
		},
		{
			// non-overlap 1
			inp1: []int{1, 2},
			inp2: []int{11, 12},
			exp:  []int{1, 2, 11, 12},
		},
		{
			// non-overlap 2
			inp1: []int{1, 2, 3, 4, 5, 6},
			inp2: []int{2, 3, 4, 5, 6, 7},
			exp:  []int{1, 7},
		},
	}

	for k, tc := range testcases {
		is1, err1 := makeIntervals(tc.inp1...)
		if err1 != nil {
			t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.inp1, err1)
		}
		is2, err2 := makeIntervals(tc.inp2...)
		if err2 != nil {
			t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.inp2, err2)
		}
		m := is1.Merge(is2)
		wis, werr := makeIntervals(tc.exp...)
		if werr != nil {
			t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.exp, werr)
		}
		want := wis.String()
		got := m.String()
		if want != got {
			t.Fatalf("k=%d Merge(%s, %s): got %v want %v",
				k, is1, is2, m, want)
		}
	}
}

func TestBuilder(t *testing.T) {
	type posLiveKill struct {
		pos                 int
		becomesLive, isKill bool // what to pass to IntervalsBuilder
	}
	testcases := []struct {
		inp        []posLiveKill
		exp        []int
		aerr, ferr bool
	}{
		// error case, position non-decreasing
		{
			inp: []posLiveKill{
				posLiveKill{pos: 10, becomesLive: true},
				posLiveKill{pos: 18, isKill: true},
			},
			aerr: true,
		},
		// error case, position negative
		{
			inp: []posLiveKill{
				posLiveKill{pos: -1, becomesLive: true},
			},
			aerr: true,
		},
		// empty
		{
			exp: nil,
		},
		// single BB
		{
			inp: []posLiveKill{
				posLiveKill{pos: 10, becomesLive: true},
				posLiveKill{pos: 9, isKill: true},
			},
			exp: []int{10, 11},
		},
		// couple of BBs
		{
			inp: []posLiveKill{
				posLiveKill{pos: 11, becomesLive: true},
				posLiveKill{pos: 10, becomesLive: true},
				posLiveKill{pos: 9, isKill: true},
				posLiveKill{pos: 4, becomesLive: true},
				posLiveKill{pos: 1, isKill: true},
			},
			exp: []int{2, 5, 10, 12},
		},
		// couple of BBs
		{
			inp: []posLiveKill{
				posLiveKill{pos: 20, isKill: true},
				posLiveKill{pos: 19, isKill: true},
				posLiveKill{pos: 17, becomesLive: true},
				posLiveKill{pos: 14, becomesLive: true},
				posLiveKill{pos: 10, isKill: true},
				posLiveKill{pos: 4, becomesLive: true},
				posLiveKill{pos: 0, isKill: true},
			},
			exp: []int{1, 5, 11, 18},
		},
	}

	for k, tc := range testcases {
		var c IntervalsBuilder
		var aerr error
		for _, event := range tc.inp {
			if event.becomesLive {
				if err := c.Live(event.pos); err != nil {
					aerr = err
					break
				}
			}
			if event.isKill {
				if err := c.Kill(event.pos); err != nil {
					aerr = err
					break
				}
			}
		}
		if (aerr != nil) != tc.aerr {
			t.Fatalf("k=%d add err mismatch: tc.aerr:%v aerr!=nil:%v",
				k, tc.aerr, (aerr != nil))
		}
		if tc.aerr {
			continue
		}
		ii, ferr := c.Finish()
		if ferr != nil {
			if tc.ferr {
				continue
			}
			t.Fatalf("h=%d finish err mismatch: tc.ferr:%v ferr!=nil:%v", k, tc.ferr, ferr != nil)
		}
		got := ii.String()
		wis, werr := makeIntervals(tc.exp...)
		if werr != nil {
			t.Fatalf("unexpected error on tc:%d %+v: %v", k, tc.exp, werr)
		}
		want := wis.String()
		if want != got {
			t.Fatalf("k=%d Ctor test: got %v want %v", k, got, want)
		}
	}
}

// makeIntervals constructs an Intervals object from the start/end
// sequence in nums, expected to be of the form
// s1,en1,st2,en2,...,stk,enk. Used only for unit testing.
func makeIntervals(nums ...int) (Intervals, error) {
	var r Intervals
	if len(nums)&1 != 0 {
		return r, fmt.Errorf("odd number of elems %d", len(nums))
	}
	for i := 0; i < len(nums); i += 2 {
		st := nums[i]
		en := nums[i+1]
		r = append(r, Interval{st: st, en: en})
	}
	return r, check(r)
}