Regres: Keep coverage span groups stable.
Update tests.
Bug: b/152192800
Change-Id: I4e57f0d2b049f0bce7459b29f7ffc3a2ca03534a
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/43309
Kokoro-Presubmit: kokoro <noreply+kokoro@google.com>
Reviewed-by: Nicolas Capens <nicolascapens@google.com>
Tested-by: Ben Clayton <bclayton@google.com>
diff --git a/tests/regres/cov/coverage_test.go b/tests/regres/cov/coverage_test.go
index aac05b5..6bd6b73 100644
--- a/tests/regres/cov/coverage_test.go
+++ b/tests/regres/cov/coverage_test.go
@@ -88,7 +88,7 @@
// i
checkSpans(t, tree.Spans(), span0, span1, span2)
checkTests(t, tree, `{a:{b:{d:{i} e}}}`)
- checkCoverage(t, tree, fileA, `a:{[0,1] b:{[] e:{[2]}}}`)
+ checkCoverage(t, tree, fileA, `a:{[0,1] b:{e:{[2]}}}`)
t.Log("Add 'n' with the coverage [0,3]")
tree.Add(cov.Path{"a", "c", "g", "n"}, coverage(fileA, span0, span3))
@@ -132,7 +132,7 @@
// i n o
checkSpans(t, tree.Spans(), span0, span1, span2, span3)
checkTests(t, tree, `{a:{b:{d:{i} e} c:{f g:{n o}}}}`)
- checkCoverage(t, tree, fileA, `a:{[] b:{[0,1] e:{[2]}} c:{[] f:{[1]} g:{[0,3]}}}`)
+ checkCoverage(t, tree, fileA, `a:{b:{[0,1] e:{[2]}} c:{f:{[1]} g:{[0,3]}}}`)
t.Log("Add 'j' with the coverage [3]")
tree.Add(cov.Path{"a", "b", "e", "j"}, coverage(fileA, span3))
@@ -146,7 +146,7 @@
// i j n o
checkSpans(t, tree.Spans(), span0, span1, span2, span3)
checkTests(t, tree, `{a:{b:{d:{i} e:{j}} c:{f g:{n o}}}}`)
- checkCoverage(t, tree, fileA, `a:{[] b:{[] d:{[0,1]} e:{[3]}} c:{[] f:{[1]} g:{[0,3]}}}`)
+ checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1]} g:{[0,3]}}}`)
t.Log("Add 'k' with the coverage [3]")
tree.Add(cov.Path{"a", "b", "e", "k"}, coverage(fileA, span3))
@@ -160,7 +160,7 @@
// i j k n o
checkSpans(t, tree.Spans(), span0, span1, span2, span3)
checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f g:{n o}}}}`)
- checkCoverage(t, tree, fileA, `a:{[] b:{[] d:{[0,1]} e:{[3]}} c:{[] f:{[1]} g:{[0,3]}}}`)
+ checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1]} g:{[0,3]}}}`)
t.Log("Add 'v' with the coverage [1,2]")
tree.Add(cov.Path{"a", "c", "f", "l", "v"}, coverage(fileA, span1, span2))
@@ -176,7 +176,7 @@
// v
checkSpans(t, tree.Spans(), span0, span1, span2, span3)
checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f:{l:{v}} g:{n o}}}}`)
- checkCoverage(t, tree, fileA, `a:{[] b:{[] d:{[0,1]} e:{[3]}} c:{[] f:{[1,2]} g:{[0,3]}}}`)
+ checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1,2]} g:{[0,3]}}}`)
t.Log("Add 'x' with the coverage [1,2]")
tree.Add(cov.Path{"a", "c", "f", "l", "x"}, coverage(fileA, span1, span2))
@@ -192,7 +192,7 @@
// v x
checkSpans(t, tree.Spans(), span0, span1, span2, span3)
checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f:{l:{v x}} g:{n o}}}}`)
- checkCoverage(t, tree, fileA, `a:{[] b:{[] d:{[0,1]} e:{[3]}} c:{[] f:{[1,2]} g:{[0,3]}}}`)
+ checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1,2]} g:{[0,3]}}}`)
t.Log("Add 'z' with the coverage [2]")
tree.Add(cov.Path{"a", "c", "g", "n", "z"}, coverage(fileA, span2))
@@ -208,7 +208,22 @@
// v x z
checkSpans(t, tree.Spans(), span0, span1, span2, span3)
checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f:{l:{v x}} g:{n: {z} o}}}}`)
- checkCoverage(t, tree, fileA, `a:{[] b:{[] d:{[0,1]} e:{[3]}} c:{[] f:{[1,2]} g:{[] n:{[2]} o:{[0,3]}}}}`)
+ checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1,2]} g:{n:{[2]} o:{[0,3]}}}}`)
+
+ tree.Optimize()
+
+ // (a)
+ // ┏━━━━━━━━┻━━━━━━━━━━━━┓
+ // (b) (c)
+ // ┏━━━┻━━━┓ ┏━━━━┻━━━━┓
+ // <0>(d) (e)[3] <2>(f) (g)
+ // ╰─╮ ╭─┴─╮ ╭─╯ ┏━┻━┓
+ // i j k l [2](n) (o)<1>
+ // ╭┴╮ ╭╯
+ // v x z
+ checkSpans(t, tree.Spans(), span0, span1, span2, span3)
+ checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f:{l:{v x}} g:{n: {z} o}}}}`)
+ checkCoverage(t, tree, fileA, `a:{b:{d:{<0>} e:{[3]}} c:{f:{<2>} g:{n:{[2]} o:{<1>}}}}`)
}
func checkSpans(t *testing.T, got []cov.Span, expect ...cov.Span) {
diff --git a/tests/regres/cov/import.go b/tests/regres/cov/import.go
index e3c3053..100c3cb 100644
--- a/tests/regres/cov/import.go
+++ b/tests/regres/cov/import.go
@@ -37,15 +37,47 @@
return fmt.Sprintf("%v:%v", l.Line, l.Column)
}
+// Compare returns -1 if l comes before o, 1 if l comes after o, otherwise 0.
+func (l Location) Compare(o Location) int {
+ switch {
+ case l.Line < o.Line:
+ return -1
+ case l.Line > o.Line:
+ return 1
+ }
+ return 0
+}
+
+// Before returns true if l comes before o.
+func (l Location) Before(o Location) bool { return l.Compare(o) == -1 }
+
// Span describes a start and end interval in a source file.
type Span struct {
Start, End Location
}
-func (l Span) String() string {
- return fmt.Sprintf("%v-%v", l.Start, l.End)
+func (s Span) String() string {
+ return fmt.Sprintf("%v-%v", s.Start, s.End)
}
+// Compare returns -1 if l comes before o, 1 if l comes after o, otherwise 0.
+func (s Span) Compare(o Span) int {
+ switch {
+ case s.Start.Before(o.Start):
+ return -1
+ case o.Start.Before(s.Start):
+ return 1
+ case s.End.Before(o.End):
+ return -1
+ case o.End.Before(s.End):
+ return 1
+ }
+ return 0
+}
+
+// Before returns true if span s comes before o.
+func (s Span) Before(o Span) bool { return s.Compare(o) == -1 }
+
// File describes the coverage spans in a single source file.
type File struct {
Path string
diff --git a/tests/regres/cov/tree.go b/tests/regres/cov/tree.go
index d4c356b..398fd44 100644
--- a/tests/regres/cov/tree.go
+++ b/tests/regres/cov/tree.go
@@ -54,21 +54,35 @@
}
}
+// SpanList is a list of Spans
+type SpanList []Span
+
+// Compare returns -1 if l comes before o, 1 if l comes after o, otherwise 0.
+func (l SpanList) Compare(o SpanList) int {
+ switch {
+ case len(l) < len(o):
+ return -1
+ case len(l) > len(o):
+ return 1
+ }
+ for i, a := range l {
+ switch a.Compare(o[i]) {
+ case -1:
+ return -1
+ case 1:
+ return 1
+ }
+ }
+ return 0
+}
+
// Spans returns all the spans used by the tree
-func (t *Tree) Spans() []Span {
- out := make([]Span, 0, len(t.spans))
+func (t *Tree) Spans() SpanList {
+ out := make(SpanList, 0, len(t.spans))
for span := range t.spans {
out = append(out, span)
}
- sort.Slice(out, func(i, j int) bool {
- if out[i].Start.Line < out[j].Start.Line {
- return true
- }
- if out[i].Start.Line > out[j].Start.Line {
- return false
- }
- return out[i].Start.Column < out[j].Start.Column
- })
+ sort.Slice(out, func(i, j int) bool { return out[i].Before(out[j]) })
return out
}
@@ -259,7 +273,15 @@
func (tc TestCoverage) String(t *Test, s Strings) string {
sb := strings.Builder{}
- sb.WriteString(fmt.Sprintf("{%v", tc.Spans))
+ sb.WriteString("{")
+ if len(tc.Spans) > 0 {
+ sb.WriteString(tc.Spans.String())
+ }
+ if tc.Group != nil {
+ sb.WriteString(" <")
+ sb.WriteString(fmt.Sprintf("%v", *tc.Group))
+ sb.WriteString(">")
+ }
if len(tc.Children) > 0 {
sb.WriteString(" ")
sb.WriteString(tc.Children.String(t, s))
@@ -313,9 +335,32 @@
// SpanSet is a set of SpanIDs.
type SpanSet map[SpanID]struct{}
+// SpanIDList is a list of SpanIDs
+type SpanIDList []SpanID
+
+// Compare returns -1 if l comes before o, 1 if l comes after o, otherwise 0.
+func (l SpanIDList) Compare(o SpanIDList) int {
+ switch {
+ case len(l) < len(o):
+ return -1
+ case len(l) > len(o):
+ return 1
+ }
+ for i, a := range l {
+ b := o[i]
+ switch {
+ case a < b:
+ return -1
+ case a > b:
+ return 1
+ }
+ }
+ return 0
+}
+
// List returns the full list of sorted span ids.
-func (s SpanSet) List() []SpanID {
- out := make([]SpanID, 0, len(s))
+func (s SpanSet) List() SpanIDList {
+ out := make(SpanIDList, 0, len(s))
for span := range s {
out = append(out, span)
}
@@ -422,7 +467,6 @@
return
}
- // Sort by number of spans in each sets.
type spansetInfo struct {
key spansetKey
set SpanSet // fully expanded set
@@ -435,10 +479,25 @@
key: key,
set: set,
grp: SpanGroup{spans: set},
- id: SpanGroupID(len(spansets)),
})
}
- sort.Slice(spansets, func(i, j int) bool { return len(spansets[i].set) > len(spansets[j].set) })
+
+ // Sort by number of spans in each sets starting with the largest.
+ sort.Slice(spansets, func(i, j int) bool {
+ a, b := spansets[i].set, spansets[j].set
+ switch {
+ case len(a) > len(b):
+ return true
+ case len(a) < len(b):
+ return false
+ }
+ return a.List().Compare(b.List()) == -1 // Just to keep output stable
+ })
+
+ // Assign IDs now that we have stable order.
+ for i := range spansets {
+ spansets[i].id = SpanGroupID(i)
+ }
// Loop over the spanGroups starting from the largest, and try to fold them
// into the larger sets.
