From 7979c8f5881b5ab183acc096f33dfcb1cab995fa Mon Sep 17 00:00:00 2001 From: Than McIntosh Date: Thu, 22 Feb 2024 14:06:28 +0000 Subject: [PATCH] cmd/compile/internal/liveness: introduce "live intervals" utility Introduce a helper type "Intervals" that contains sets of sorted disjoint ranges corresponding to live ranges within a function. Example: the Intervals set "{ [0,1), [4,10) }" would indicate that something is live starting at instruction 0, then up to but not including instruction 1, then dead from 1-3, then live again at instruction 4 up to (but not including) instruction 10. This patch provides APIs for constructing interval sets, testing to see whether two sets overlap, and unioning/merging together two intervals sets. Updates #62737. Updates #65532. Updates #65495. Change-Id: I7140a5989eba93bf3b8762d9224261f5eba0646d Reviewed-on: https://go-review.googlesource.com/c/go/+/566177 LUCI-TryBot-Result: Go LUCI Reviewed-by: Cherry Mui --- .../compile/internal/liveness/intervals.go | 387 +++++++++++++ .../internal/liveness/intervals_test.go | 527 ++++++++++++++++++ 2 files changed, 914 insertions(+) create mode 100644 src/cmd/compile/internal/liveness/intervals.go create mode 100644 src/cmd/compile/internal/liveness/intervals_test.go diff --git a/src/cmd/compile/internal/liveness/intervals.go b/src/cmd/compile/internal/liveness/intervals.go new file mode 100644 index 0000000000..4757cca3ce --- /dev/null +++ b/src/cmd/compile/internal/liveness/intervals.go @@ -0,0 +1,387 @@ +// 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 + +// This file defines an "Intervals" helper type that stores a +// sorted sequence of disjoint ranges or intervals. An Intervals +// example: { [0,5) [9-12) [100,101) }, which corresponds to the +// numbers 0-4, 9-11, and 100. Once an Intervals object is created, it +// can be tested to see if it has any overlap with another Intervals +// object, or it can be merged with another Intervals object to form a +// union of the two. +// +// The intended use case for this helper is in describing object or +// variable lifetime ranges within a linearized program representation +// where each IR instruction has a slot or index. Example: +// +// b1: +// 0 VarDef abc +// 1 memset(abc,0) +// 2 VarDef xyz +// 3 memset(xyz,0) +// 4 abc.f1 = 2 +// 5 xyz.f3 = 9 +// 6 if q goto B4 +// 7 B3: z = xyz.x +// 8 goto B5 +// 9 B4: z = abc.x +// // fallthrough +// 10 B5: z++ +// +// To describe the lifetime of the variables above we might use these +// intervals: +// +// "abc" [1,7), [9,10) +// "xyz" [3,8) +// +// Clients can construct an Intervals object from a given IR sequence +// using the "IntervalsBuilder" helper abstraction (one builder per +// candidate variable), by making a +// backwards sweep and invoking the Live/Kill methods to note the +// starts and end of a given lifetime. For the example above, we would +// expect to see this sequence of calls to Live/Kill: +// +// abc: Live(9), Kill(8), Live(6), Kill(0) +// xyz: Live(8), Kill(2) + +import ( + "fmt" + "os" + "strings" +) + +const debugtrace = false + +// Interval hols the range [st,en). +type Interval struct { + st, en int +} + +// Intervals is a sequence of sorted, disjoint intervals. +type Intervals []Interval + +func (i Interval) String() string { + return fmt.Sprintf("[%d,%d)", i.st, i.en) +} + +// TEMPORARY until bootstrap version catches up. +func imin(i, j int) int { + if i < j { + return i + } + return j +} + +// TEMPORARY until bootstrap version catches up. +func imax(i, j int) int { + if i > j { + return i + } + return j +} + +// Overlaps returns true if here is any overlap between i and i2. +func (i Interval) Overlaps(i2 Interval) bool { + return (imin(i.en, i2.en) - imax(i.st, i2.st)) > 0 +} + +// adjacent returns true if the start of one interval is equal to the +// end of another interval (e.g. they represent consecutive ranges). +func (i1 Interval) adjacent(i2 Interval) bool { + return i1.en == i2.st || i2.en == i1.st +} + +// MergeInto merges interval i2 into i1. This version happens to +// require that the two intervals either overlap or are adjacent. +func (i1 *Interval) MergeInto(i2 Interval) error { + if !i1.Overlaps(i2) && !i1.adjacent(i2) { + return fmt.Errorf("merge method invoked on non-overlapping/non-adjacent") + } + i1.st = imin(i1.st, i2.st) + i1.en = imax(i1.en, i2.en) + return nil +} + +// IntervalsBuilder is a helper for constructing intervals based on +// live dataflow sets for a series of BBs where we're making a +// backwards pass over each BB looking for uses and kills. The +// expected use case is: +// +// - invoke MakeIntervalsBuilder to create a new object "b" +// - series of calls to b.Live/b.Kill based on a backwards reverse layout +// order scan over instructions +// - invoke b.Finish() to produce final set +// +// See the Live method comment for an IR example. +type IntervalsBuilder struct { + s Intervals + // index of last instruction visited plus 1 + lidx int +} + +func (c *IntervalsBuilder) last() int { + return c.lidx - 1 +} + +func (c *IntervalsBuilder) setLast(x int) { + c.lidx = x + 1 +} + +func (c *IntervalsBuilder) Finish() (Intervals, error) { + // Reverse intervals list and check. + // FIXME: replace with slices.Reverse once the + // bootstrap version supports it. + for i, j := 0, len(c.s)-1; i < j; i, j = i+1, j-1 { + c.s[i], c.s[j] = c.s[j], c.s[i] + } + if err := check(c.s); err != nil { + return Intervals{}, err + } + r := c.s + return r, nil +} + +// Live method should be invoked on instruction at position p if instr +// contains an upwards-exposed use of a resource. See the example in +// the comment at the beginning of this file for an example. +func (c *IntervalsBuilder) Live(pos int) error { + if pos < 0 { + return fmt.Errorf("bad pos, negative") + } + if c.last() == -1 { + c.setLast(pos) + if debugtrace { + fmt.Fprintf(os.Stderr, "=-= begin lifetime at pos=%d\n", pos) + } + c.s = append(c.s, Interval{st: pos, en: pos + 1}) + return nil + } + if pos >= c.last() { + return fmt.Errorf("pos not decreasing") + } + // extend lifetime across this pos + c.s[len(c.s)-1].st = pos + c.setLast(pos) + return nil +} + +// Kill method should be invoked on instruction at position p if instr +// should be treated as as having a kill (lifetime end) for the +// resource. See the example in the comment at the beginning of this +// file for an example. Note that if we see a kill at position K for a +// resource currently live since J, this will result in a lifetime +// segment of [K+1,J+1), the assumption being that the first live +// instruction will be the one after the kill position, not the kill +// position itself. +func (c *IntervalsBuilder) Kill(pos int) error { + if pos < 0 { + return fmt.Errorf("bad pos, negative") + } + if c.last() == -1 { + return nil + } + if pos >= c.last() { + return fmt.Errorf("pos not decreasing") + } + c.s[len(c.s)-1].st = pos + 1 + // terminate lifetime + c.setLast(-1) + if debugtrace { + fmt.Fprintf(os.Stderr, "=-= term lifetime at pos=%d\n", pos) + } + return nil +} + +// check examines the intervals in "is" to try to find internal +// inconsistencies or problems. +func check(is Intervals) error { + for i := 0; i < len(is); i++ { + st := is[i].st + en := is[i].en + if en <= st { + return fmt.Errorf("bad range elem %d:%d, en<=st", st, en) + } + if i == 0 { + continue + } + // check for badly ordered starts + pst := is[i-1].st + pen := is[i-1].en + if pst >= st { + return fmt.Errorf("range start not ordered %d:%d less than prev %d:%d", st, en, + pst, pen) + } + // check end of last range against start of this range + if pen > st { + return fmt.Errorf("bad range elem %d:%d overlaps prev %d:%d", st, en, + pst, pen) + } + } + return nil +} + +func (is *Intervals) String() string { + var sb strings.Builder + for i := range *is { + if i != 0 { + sb.WriteString(" ") + } + sb.WriteString((*is)[i].String()) + } + return sb.String() +} + +// intWithIdx holds an interval i and an index pairIndex storing i's +// position (either 0 or 1) within some previously specified interval +// pair ; a pairIndex of -1 is used to signal "end of +// iteration". Used for Intervals operations, not expected to be +// exported. +type intWithIdx struct { + i Interval + pairIndex int +} + +func (iwi intWithIdx) done() bool { + return iwi.pairIndex == -1 +} + +// pairVisitor provides a way to visit (iterate through) each interval +// within a pair of Intervals in order of increasing start time. Expected +// usage model: +// +// func example(i1, i2 Intervals) { +// var pairVisitor pv +// cur := pv.init(i1, i2); +// for !cur.done() { +// fmt.Printf("interval %s from i%d", cur.i.String(), cur.pairIndex+1) +// cur = pv.nxt() +// } +// } +// +// Used internally for Intervals operations, not expected to be exported. +type pairVisitor struct { + cur intWithIdx + i1pos int + i2pos int + i1, i2 Intervals +} + +// init initializes a pairVisitor for the specified pair of intervals +// i1 and i2 and returns an intWithIdx object that points to the first +// interval by start position within i1/i2. +func (pv *pairVisitor) init(i1, i2 Intervals) intWithIdx { + pv.i1, pv.i2 = i1, i2 + pv.cur = pv.sel() + return pv.cur +} + +// nxt advances the pairVisitor to the next interval by starting +// position within the pair, returning an intWithIdx that describes +// the interval. +func (pv *pairVisitor) nxt() intWithIdx { + if pv.cur.pairIndex == 0 { + pv.i1pos++ + } else { + pv.i2pos++ + } + pv.cur = pv.sel() + return pv.cur +} + +// sel is a helper function used by 'init' and 'nxt' above; it selects +// the earlier of the two intervals at the current positions within i1 +// and i2, or a degenerate (pairIndex -1) intWithIdx if we have no +// more intervals to visit. +func (pv *pairVisitor) sel() intWithIdx { + var c1, c2 intWithIdx + if pv.i1pos >= len(pv.i1) { + c1.pairIndex = -1 + } else { + c1 = intWithIdx{i: pv.i1[pv.i1pos], pairIndex: 0} + } + if pv.i2pos >= len(pv.i2) { + c2.pairIndex = -1 + } else { + c2 = intWithIdx{i: pv.i2[pv.i2pos], pairIndex: 1} + } + if c1.pairIndex == -1 { + return c2 + } + if c2.pairIndex == -1 { + return c1 + } + if c1.i.st <= c2.i.st { + return c1 + } + return c2 +} + +// Overlaps returns whether any of the component ranges in is overlaps +// with some range in is2. +func (is Intervals) Overlaps(is2 Intervals) bool { + // check for empty intervals + if len(is) == 0 || len(is2) == 0 { + return false + } + li := len(is) + li2 := len(is2) + // check for completely disjoint ranges + if is[li-1].en <= is2[0].st || + is[0].st >= is2[li2-1].en { + return false + } + // walk the combined sets of intervals and check for piecewise + // overlap. + var pv pairVisitor + first := pv.init(is, is2) + for { + second := pv.nxt() + if second.done() { + break + } + if first.pairIndex == second.pairIndex { + first = second + continue + } + if first.i.Overlaps(second.i) { + return true + } + first = second + } + return false +} + +// Merge combines the intervals from "is" and "is2" and returns +// a new Intervals object containing all combined ranges from the +// two inputs. +func (is Intervals) Merge(is2 Intervals) Intervals { + if len(is) == 0 { + return is2 + } else if len(is2) == 0 { + return is + } + // walk the combined set of intervals and merge them together. + var ret Intervals + var pv pairVisitor + cur := pv.init(is, is2) + for { + second := pv.nxt() + if second.done() { + break + } + + // Check for overlap between cur and second. If no overlap + // then add cur to result and move on. + if !cur.i.Overlaps(second.i) && !cur.i.adjacent(second.i) { + ret = append(ret, cur.i) + cur = second + continue + } + // cur overlaps with second; merge second into cur + cur.i.MergeInto(second.i) + } + ret = append(ret, cur.i) + return ret +} diff --git a/src/cmd/compile/internal/liveness/intervals_test.go b/src/cmd/compile/internal/liveness/intervals_test.go new file mode 100644 index 0000000000..bf65a293b9 --- /dev/null +++ b/src/cmd/compile/internal/liveness/intervals_test.go @@ -0,0 +1,527 @@ +// 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) +} -- 2.50.0