tools: Add src/cts/results.List.MinimalVariantTags
MinimalVariantTags accepts a list of tag-sets (e.g GPU tags, OS tags, etc),
and returns an optimized list of variants, folding together variants that
have identical result query-to-status mappings, and removing redundant tags.
Bug: dawn:1342
Change-Id: I759c82e9a0631a9d321d376656e5a2dbbf5f5507
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/87643
Reviewed-by: Dan Sinclair <dsinclair@chromium.org>
Kokoro: Kokoro <noreply+kokoro@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
diff --git a/tools/src/container/set.go b/tools/src/container/set.go
index 689c1e3..4adde5c 100644
--- a/tools/src/container/set.go
+++ b/tools/src/container/set.go
@@ -71,7 +71,7 @@
return found
}
-// Contains returns true if the set contains all the items in o
+// ContainsAll returns true if the set contains all the items in o
func (s Set[T]) ContainsAll(o Set[T]) bool {
for item := range o {
if !s.Contains(item) {
@@ -81,6 +81,16 @@
return true
}
+// ContainsAny returns true if the set contains any of the items in o
+func (s Set[T]) ContainsAny(o Set[T]) bool {
+ for item := range o {
+ if s.Contains(item) {
+ return true
+ }
+ }
+ return false
+}
+
// Intersection returns true if the set contains all the items in o
func (s Set[T]) Intersection(o Set[T]) Set[T] {
out := NewSet[T]()
diff --git a/tools/src/container/set_test.go b/tools/src/container/set_test.go
index 2e8bf53..35ebd4f 100644
--- a/tools/src/container/set_test.go
+++ b/tools/src/container/set_test.go
@@ -123,6 +123,39 @@
expectEq(t, `s.ContainsAll("c", "a", "b")`, s.ContainsAll(S("c", "a", "b")), true)
}
+func TestSetContainsAny(t *testing.T) {
+ S := container.NewSet[string]
+
+ s := container.NewSet[string]()
+ s.Add("c")
+ expectEq(t, `s.ContainsAny("a")`, s.ContainsAny(S("a")), false)
+ expectEq(t, `s.ContainsAny("b")`, s.ContainsAny(S("b")), false)
+ expectEq(t, `s.ContainsAny("c")`, s.ContainsAny(S("c")), true)
+ expectEq(t, `s.ContainsAny("a", "b")`, s.ContainsAny(S("a", "b")), false)
+ expectEq(t, `s.ContainsAny("b", "c")`, s.ContainsAny(S("b", "c")), true)
+ expectEq(t, `s.ContainsAny("c", "a")`, s.ContainsAny(S("c", "a")), true)
+ expectEq(t, `s.ContainsAny("c", "a", "b")`, s.ContainsAny(S("c", "a", "b")), true)
+
+ s.Add("a")
+ expectEq(t, `s.ContainsAny("a")`, s.ContainsAny(S("a")), true)
+ expectEq(t, `s.ContainsAny("b")`, s.ContainsAny(S("b")), false)
+ expectEq(t, `s.ContainsAny("c")`, s.ContainsAny(S("c")), true)
+ expectEq(t, `s.ContainsAny("a", "b")`, s.ContainsAny(S("a", "b")), true)
+ expectEq(t, `s.ContainsAny("b", "c")`, s.ContainsAny(S("b", "c")), true)
+ expectEq(t, `s.ContainsAny("c", "a")`, s.ContainsAny(S("c", "a")), true)
+ expectEq(t, `s.ContainsAny("c", "a", "b")`, s.ContainsAny(S("c", "a", "b")), true)
+
+ s.Remove("c")
+ s.Add("b")
+ expectEq(t, `s.ContainsAny("a")`, s.ContainsAny(S("a")), true)
+ expectEq(t, `s.ContainsAny("b")`, s.ContainsAny(S("b")), true)
+ expectEq(t, `s.ContainsAny("c")`, s.ContainsAny(S("c")), false)
+ expectEq(t, `s.ContainsAny("a", "b")`, s.ContainsAny(S("a", "b")), true)
+ expectEq(t, `s.ContainsAny("b", "c")`, s.ContainsAny(S("b", "c")), true)
+ expectEq(t, `s.ContainsAny("c", "a")`, s.ContainsAny(S("c", "a")), true)
+ expectEq(t, `s.ContainsAny("c", "a", "b")`, s.ContainsAny(S("c", "a", "b")), true)
+}
+
func TestSetIntersection(t *testing.T) {
a := container.NewSet(1, 3, 4, 6)
b := container.NewSet(2, 3, 4, 5)
diff --git a/tools/src/cts/result/mvt.go b/tools/src/cts/result/mvt.go
new file mode 100644
index 0000000..2318821
--- /dev/null
+++ b/tools/src/cts/result/mvt.go
@@ -0,0 +1,146 @@
+// Copyright 2022 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package result
+
+import (
+ "sort"
+
+ "dawn.googlesource.com/dawn/tools/src/cts/query"
+)
+
+// MinimalVariantTags accepts a list of tag-sets (e.g GPU tags, OS tags, etc),
+// and returns an optimized list of variants, folding together variants that
+// have identical result query-to-status mappings, and removing redundant tags.
+//
+// MinimalVariantTags will attempt to remove variant tags starting with the
+// first set of tags in tagSets, then second, and so on. If a tag-set cannot
+// be removed, then the tags of the set are left alone, and the algorithm will
+// progress to the next tag-set.
+//
+// MinimalVariantTags assumes that there are no duplicate results (same query,
+// same tags) in l.
+func (l List) MinimalVariantTags(tagSets []Tags) []Variant {
+ type VariantData struct {
+ // The variant tags
+ tags Variant
+ // The query -> status for all results in l that have this variant's
+ // tags.
+ queryToStatus map[query.Query]Status
+ }
+
+ variants := []VariantData{}
+
+ // Build the initial list of variants from l.
+ // Bin result [query -> status] to the variant.
+ {
+ variantIndices := map[string]int{}
+ for _, r := range l {
+ key := TagsToString(r.Tags)
+ if idx, found := variantIndices[key]; !found {
+ variantIndices[key] = len(variants)
+ variants = append(variants, VariantData{
+ tags: Variant(r.Tags.Clone()),
+ queryToStatus: map[query.Query]Status{
+ r.Query: r.Status,
+ },
+ })
+ } else {
+ variants[idx].queryToStatus[r.Query] = r.Status
+ }
+ }
+ }
+
+ // canReduce checks that the variant would match the same results if the
+ // tags were reduced to 'tags'. Returns true if the variant's tags could
+ // be reduced, otherwise false.
+ canReduce := func(variant VariantData, tags Tags) bool {
+ for _, r := range l.FilterByTags(tags) {
+ existing, found := variant.queryToStatus[r.Query]
+ if !found {
+ // Removing the tag has expanded the set of queries.
+ return false
+ }
+ if existing != r.Status {
+ // Removing the tag has resulted in two queries with different
+ // results.
+ return false
+ }
+ }
+ return true
+ }
+
+ // tryToRemoveTags will remove all the tags in 'tags' from all variants
+ // iff doing so does not affect the set of results filtered by each variant.
+ // If it was possible to remove the tags, then variants that now have the
+ // same tags may be folded together, reducing the total number of variants.
+ tryToRemoveTags := func(tags Tags) {
+ newVariants := make([]VariantData, 0, len(variants))
+
+ for _, v := range variants {
+ // Does the variant even contain these tags?
+ if !v.tags.ContainsAny(tags) {
+ // Nope. Skip the canReduce() call, and keep the variant.
+ newVariants = append(newVariants, v)
+ continue
+ }
+
+ // Build the new set of tags with 'tags' removed.
+ newTags := v.tags.Clone()
+ newTags.RemoveAll(tags)
+
+ // Check wether removal of these tags affected the outcome.
+ if !canReduce(v, newTags) {
+ // Removing these tags resulted in differences.
+ return // Abort
+ }
+ newVariants = append(newVariants, VariantData{newTags, v.queryToStatus})
+ }
+
+ // Remove variants that are now subsets of others.
+ // Start by sorting the variants by number of tags.
+ // This ensures that the variants with fewer tags (fewer constraints)
+ // come first.
+ sort.Slice(newVariants, func(i, j int) bool {
+ return len(newVariants[i].tags) < len(newVariants[j].tags)
+ })
+
+ // Now check each variant's tags against the previous variant tags.
+ // As we've sorted, we know that supersets (fewer-tags) come before
+ // subsets (more-tags).
+ variants = []VariantData{}
+
+ nextVariant:
+ for i, v1 := range newVariants { // for variants 0..N
+ for _, v2 := range newVariants[:i] { // for variants 0..i
+ if v1.tags.ContainsAll(v2.tags) {
+ continue nextVariant // v1 is a subset of v2. Omit.
+ }
+ }
+ variants = append(variants, v1)
+ }
+ }
+
+ // Attempt to remove the tag sets from the variants, one by one.
+ for _, tags := range tagSets {
+ tryToRemoveTags(tags)
+ }
+
+ // Return the final set of unique variants
+ out := make([]Variant, len(variants))
+ for i, v := range variants {
+ out[i] = v.tags
+ }
+ return out
+}
diff --git a/tools/src/cts/result/mvt_test.go b/tools/src/cts/result/mvt_test.go
new file mode 100644
index 0000000..bfa67a7
--- /dev/null
+++ b/tools/src/cts/result/mvt_test.go
@@ -0,0 +1,117 @@
+// Copyright 2022 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package result_test
+
+import (
+ "fmt"
+ "testing"
+
+ "dawn.googlesource.com/dawn/tools/src/cts/result"
+ "dawn.googlesource.com/dawn/tools/src/utils"
+ "github.com/google/go-cmp/cmp"
+)
+
+func TestMinimalVariantTags(t *testing.T) {
+ type Test struct {
+ location string
+ results result.List
+ expect []result.Variant
+ }
+ for _, test := range []Test{
+ { //////////////////////////////////////////////////////////////////////
+ location: utils.ThisLine(),
+ results: result.List{},
+ expect: []result.Variant{},
+ }, { ///////////////////////////////////////////////////////////////////
+ // Single variant, that can be entirely optimized away
+ location: utils.ThisLine(),
+ results: result.List{
+ {Query: Q("a:b,c:d,*"), Tags: T("a0", "b1", "c2"), Status: result.Pass},
+ },
+ expect: []result.Variant{T()},
+ }, { ///////////////////////////////////////////////////////////////////
+ // Multiple variants on the same query.
+ // Can also be entirely optimized away.
+ location: utils.ThisLine(),
+ results: result.List{
+ {Query: Q("a:b,c:d,*"), Tags: T("a0", "b1", "c2"), Status: result.Pass},
+ {Query: Q("a:b,c:d,*"), Tags: T("a1", "b2", "c0"), Status: result.Pass},
+ {Query: Q("a:b,c:d,*"), Tags: T("a2", "b1", "c0"), Status: result.Pass},
+ },
+ expect: []result.Variant{T()},
+ }, { ///////////////////////////////////////////////////////////////////
+ // Two variants where the 1st and 2nd tag-sets are redundant.
+ location: utils.ThisLine(),
+ results: result.List{
+ {Query: Q("a:b,c:d,*"), Tags: T("a0", "b0", "c0"), Status: result.Pass},
+ {Query: Q("a:b,c:d,*"), Tags: T("a1", "b1", "c1"), Status: result.Failure},
+ },
+ expect: []result.Variant{T("c0"), T("c1")},
+ }, { ///////////////////////////////////////////////////////////////////
+ // Two variants where the 1st and 3rd tag-sets are redundant.
+ location: utils.ThisLine(),
+ results: result.List{
+ {Query: Q("a:b,c:d,*"), Tags: T("a0", "b0", "c0"), Status: result.Pass},
+ {Query: Q("a:b,c:d,*"), Tags: T("a1", "b1", "c1"), Status: result.Failure},
+ {Query: Q("a:b,c:d,*"), Tags: T("a0", "b0", "c1"), Status: result.Pass},
+ {Query: Q("a:b,c:d,*"), Tags: T("a1", "b1", "c0"), Status: result.Failure},
+ },
+ expect: []result.Variant{T("b0"), T("b1")},
+ }, { ///////////////////////////////////////////////////////////////////
+ // Two variants where the 2nd and 3rd tag-sets are redundant.
+ location: utils.ThisLine(),
+ results: result.List{
+ {Query: Q("a:b,c:d,*"), Tags: T("a0", "b0", "c0"), Status: result.Pass},
+ {Query: Q("a:b,c:d,*"), Tags: T("a1", "b1", "c1"), Status: result.Failure},
+ {Query: Q("a:b,c:d,*"), Tags: T("a0", "b1", "c1"), Status: result.Pass},
+ {Query: Q("a:b,c:d,*"), Tags: T("a1", "b0", "c0"), Status: result.Failure},
+ },
+ expect: []result.Variant{T("a0"), T("a1")},
+ }, { ///////////////////////////////////////////////////////////////////
+ // Check that variants aren't optimized to expand the set of results
+ // they target, even if results are uniform
+ location: utils.ThisLine(),
+ results: result.List{
+ {Query: Q("a:b,c:d0,*"), Tags: T("a0", "b0", "c0"), Status: result.Pass},
+ {Query: Q("a:b,c:d1,*"), Tags: T("a1", "b1", "c1"), Status: result.Pass},
+ },
+ expect: []result.Variant{T("c0"), T("c1")},
+ }, { ///////////////////////////////////////////////////////////////////
+ // Exercise the optimizations to skip checks on tag removals that
+ // aren't found in all variants
+ location: utils.ThisLine(),
+ results: result.List{
+ {Query: Q("a:b,c:d0,*"), Tags: T("a0"), Status: result.Pass},
+ {Query: Q("a:b,c:d1,*"), Tags: T("b0"), Status: result.Pass},
+ {Query: Q("a:b,c:d2,*"), Tags: T("c0"), Status: result.Pass},
+ },
+ expect: []result.Variant{T("a0"), T("b0"), T("c0")},
+ },
+ } {
+ preReduce := fmt.Sprint(test.results)
+ got := test.results.MinimalVariantTags([]result.Tags{
+ T("a0", "a1", "a2"),
+ T("b0", "b1", "b2"),
+ T("c0", "c1", "c2"),
+ })
+ postReduce := fmt.Sprint(test.results)
+ if diff := cmp.Diff(got, test.expect); diff != "" {
+ t.Errorf("%v MinimalVariantTags() diff:\n%v", test.location, diff)
+ }
+ if diff := cmp.Diff(preReduce, postReduce); diff != "" {
+ t.Errorf("%v MinimalVariantTags() modified original list:\n%v", test.location, diff)
+ }
+ }
+}
diff --git a/tools/src/cts/result/result.go b/tools/src/cts/result/result.go
index 99d14d2..0ec6095 100644
--- a/tools/src/cts/result/result.go
+++ b/tools/src/cts/result/result.go
@@ -97,9 +97,13 @@
// List is a list of results
type List []Result
-// Returns the list of unique tags across all results.
-func (l List) UniqueTags() []Tags {
- tags := container.NewMap[string, Tags]()
+// Variant is a collection of tags that uniquely identify a test
+// configuration (e.g the combination of OS, GPU, validation-modes, etc).
+type Variant = Tags
+
+// Variants returns the list of unique tags (variants) across all results.
+func (l List) Variants() []Variant {
+ tags := container.NewMap[string, Variant]()
for _, r := range l {
tags.Add(TagsToString(r.Tags), r.Tags)
}
diff --git a/tools/src/cts/result/result_test.go b/tools/src/cts/result/result_test.go
index bc87bc6..7eae418 100644
--- a/tools/src/cts/result/result_test.go
+++ b/tools/src/cts/result/result_test.go
@@ -91,7 +91,7 @@
}
}
-func TestUniqueTags(t *testing.T) {
+func TestVariants(t *testing.T) {
type Test struct {
results result.List
expect []result.Tags
@@ -198,7 +198,7 @@
},
},
} {
- got := test.results.UniqueTags()
+ got := test.results.Variants()
if diff := cmp.Diff(got, test.expect); diff != "" {
t.Errorf("Results:\n%v\nUniqueTags() was not as expected:\n%v", test.results, diff)
}
