Add DepSets
Add DepSets to efficiently support tracking transitive Paths without
copying, based on Bazel's depsets:
https://docs.bazel.build/versions/master/skylark/depsets.html
Test: depset_test.go
Change-Id: If744affdf1ed850113166ba611a79a891262040c
diff --git a/android/depset_test.go b/android/depset_test.go
new file mode 100644
index 0000000..c328127
--- /dev/null
+++ b/android/depset_test.go
@@ -0,0 +1,304 @@
+// Copyright 2020 Google Inc. All rights reserved.
+//
+// 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 android
+
+import (
+ "fmt"
+ "reflect"
+ "strings"
+ "testing"
+)
+
+func ExampleDepSet_ToList_postordered() {
+ a := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("a")).Build()
+ b := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build()
+ c := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build()
+ d := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
+
+ fmt.Println(d.ToList().Strings())
+ // Output: [a b c d]
+}
+
+func ExampleDepSet_ToList_preordered() {
+ a := NewDepSetBuilder(PREORDER).Direct(PathForTesting("a")).Build()
+ b := NewDepSetBuilder(PREORDER).Direct(PathForTesting("b")).Transitive(a).Build()
+ c := NewDepSetBuilder(PREORDER).Direct(PathForTesting("c")).Transitive(a).Build()
+ d := NewDepSetBuilder(PREORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
+
+ fmt.Println(d.ToList().Strings())
+ // Output: [d b a c]
+}
+
+func ExampleDepSet_ToList_topological() {
+ a := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("a")).Build()
+ b := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("b")).Transitive(a).Build()
+ c := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("c")).Transitive(a).Build()
+ d := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("d")).Transitive(b, c).Build()
+
+ fmt.Println(d.ToList().Strings())
+ // Output: [d b c a]
+}
+
+func ExampleDepSet_ToSortedList() {
+ a := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("a")).Build()
+ b := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build()
+ c := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build()
+ d := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
+
+ fmt.Println(d.ToSortedList().Strings())
+ // Output: [a b c d]
+}
+
+// Tests based on Bazel's ExpanderTestBase.java to ensure compatibility
+// https://github.com/bazelbuild/bazel/blob/master/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java
+func TestDepSet(t *testing.T) {
+ a := PathForTesting("a")
+ b := PathForTesting("b")
+ c := PathForTesting("c")
+ c2 := PathForTesting("c2")
+ d := PathForTesting("d")
+ e := PathForTesting("e")
+
+ tests := []struct {
+ name string
+ depSet func(t *testing.T, order DepSetOrder) *DepSet
+ postorder, preorder, topological []string
+ }{
+ {
+ name: "simple",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ return NewDepSet(order, Paths{c, a, b}, nil)
+ },
+ postorder: []string{"c", "a", "b"},
+ preorder: []string{"c", "a", "b"},
+ topological: []string{"c", "a", "b"},
+ },
+ {
+ name: "simpleNoDuplicates",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ return NewDepSet(order, Paths{c, a, a, a, b}, nil)
+ },
+ postorder: []string{"c", "a", "b"},
+ preorder: []string{"c", "a", "b"},
+ topological: []string{"c", "a", "b"},
+ },
+ {
+ name: "nesting",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ subset := NewDepSet(order, Paths{c, a, e}, nil)
+ return NewDepSet(order, Paths{b, d}, []*DepSet{subset})
+ },
+ postorder: []string{"c", "a", "e", "b", "d"},
+ preorder: []string{"b", "d", "c", "a", "e"},
+ topological: []string{"b", "d", "c", "a", "e"},
+ },
+ {
+ name: "builderReuse",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ assertEquals := func(t *testing.T, w, g Paths) {
+ if !reflect.DeepEqual(w, g) {
+ t.Errorf("want %q, got %q", w, g)
+ }
+ }
+ builder := NewDepSetBuilder(order)
+ assertEquals(t, nil, builder.Build().ToList())
+
+ builder.Direct(b)
+ assertEquals(t, Paths{b}, builder.Build().ToList())
+
+ builder.Direct(d)
+ assertEquals(t, Paths{b, d}, builder.Build().ToList())
+
+ child := NewDepSetBuilder(order).Direct(c, a, e).Build()
+ builder.Transitive(child)
+ return builder.Build()
+ },
+ postorder: []string{"c", "a", "e", "b", "d"},
+ preorder: []string{"b", "d", "c", "a", "e"},
+ topological: []string{"b", "d", "c", "a", "e"},
+ },
+ {
+ name: "builderChaining",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ return NewDepSetBuilder(order).Direct(b).Direct(d).
+ Transitive(NewDepSetBuilder(order).Direct(c, a, e).Build()).Build()
+ },
+ postorder: []string{"c", "a", "e", "b", "d"},
+ preorder: []string{"b", "d", "c", "a", "e"},
+ topological: []string{"b", "d", "c", "a", "e"},
+ },
+ {
+ name: "transitiveDepsHandledSeparately",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ subset := NewDepSetBuilder(order).Direct(c, a, e).Build()
+ builder := NewDepSetBuilder(order)
+ // The fact that we add the transitive subset between the Direct(b) and Direct(d)
+ // calls should not change the result.
+ builder.Direct(b)
+ builder.Transitive(subset)
+ builder.Direct(d)
+ return builder.Build()
+ },
+ postorder: []string{"c", "a", "e", "b", "d"},
+ preorder: []string{"b", "d", "c", "a", "e"},
+ topological: []string{"b", "d", "c", "a", "e"},
+ },
+ {
+ name: "nestingNoDuplicates",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ subset := NewDepSetBuilder(order).Direct(c, a, e).Build()
+ return NewDepSetBuilder(order).Direct(b, d, e).Transitive(subset).Build()
+ },
+ postorder: []string{"c", "a", "e", "b", "d"},
+ preorder: []string{"b", "d", "e", "c", "a"},
+ topological: []string{"b", "d", "c", "a", "e"},
+ },
+ {
+ name: "chain",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ c := NewDepSetBuilder(order).Direct(c).Build()
+ b := NewDepSetBuilder(order).Direct(b).Transitive(c).Build()
+ a := NewDepSetBuilder(order).Direct(a).Transitive(b).Build()
+
+ return a
+ },
+ postorder: []string{"c", "b", "a"},
+ preorder: []string{"a", "b", "c"},
+ topological: []string{"a", "b", "c"},
+ },
+ {
+ name: "diamond",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ d := NewDepSetBuilder(order).Direct(d).Build()
+ c := NewDepSetBuilder(order).Direct(c).Transitive(d).Build()
+ b := NewDepSetBuilder(order).Direct(b).Transitive(d).Build()
+ a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
+
+ return a
+ },
+ postorder: []string{"d", "b", "c", "a"},
+ preorder: []string{"a", "b", "d", "c"},
+ topological: []string{"a", "b", "c", "d"},
+ },
+ {
+ name: "extendedDiamond",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ d := NewDepSetBuilder(order).Direct(d).Build()
+ e := NewDepSetBuilder(order).Direct(e).Build()
+ b := NewDepSetBuilder(order).Direct(b).Transitive(d).Transitive(e).Build()
+ c := NewDepSetBuilder(order).Direct(c).Transitive(e).Transitive(d).Build()
+ a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
+ return a
+ },
+ postorder: []string{"d", "e", "b", "c", "a"},
+ preorder: []string{"a", "b", "d", "e", "c"},
+ topological: []string{"a", "b", "c", "e", "d"},
+ },
+ {
+ name: "extendedDiamondRightArm",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ d := NewDepSetBuilder(order).Direct(d).Build()
+ e := NewDepSetBuilder(order).Direct(e).Build()
+ b := NewDepSetBuilder(order).Direct(b).Transitive(d).Transitive(e).Build()
+ c2 := NewDepSetBuilder(order).Direct(c2).Transitive(e).Transitive(d).Build()
+ c := NewDepSetBuilder(order).Direct(c).Transitive(c2).Build()
+ a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
+ return a
+ },
+ postorder: []string{"d", "e", "b", "c2", "c", "a"},
+ preorder: []string{"a", "b", "d", "e", "c", "c2"},
+ topological: []string{"a", "b", "c", "c2", "e", "d"},
+ },
+ {
+ name: "orderConflict",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ child1 := NewDepSetBuilder(order).Direct(a, b).Build()
+ child2 := NewDepSetBuilder(order).Direct(b, a).Build()
+ parent := NewDepSetBuilder(order).Transitive(child1).Transitive(child2).Build()
+ return parent
+ },
+ postorder: []string{"a", "b"},
+ preorder: []string{"a", "b"},
+ topological: []string{"b", "a"},
+ },
+ {
+ name: "orderConflictNested",
+ depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ a := NewDepSetBuilder(order).Direct(a).Build()
+ b := NewDepSetBuilder(order).Direct(b).Build()
+ child1 := NewDepSetBuilder(order).Transitive(a).Transitive(b).Build()
+ child2 := NewDepSetBuilder(order).Transitive(b).Transitive(a).Build()
+ parent := NewDepSetBuilder(order).Transitive(child1).Transitive(child2).Build()
+ return parent
+ },
+ postorder: []string{"a", "b"},
+ preorder: []string{"a", "b"},
+ topological: []string{"b", "a"},
+ },
+ }
+
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ t.Run("postorder", func(t *testing.T) {
+ depSet := tt.depSet(t, POSTORDER)
+ if g, w := depSet.ToList().Strings(), tt.postorder; !reflect.DeepEqual(g, w) {
+ t.Errorf("expected ToList() = %q, got %q", w, g)
+ }
+ })
+ t.Run("preorder", func(t *testing.T) {
+ depSet := tt.depSet(t, PREORDER)
+ if g, w := depSet.ToList().Strings(), tt.preorder; !reflect.DeepEqual(g, w) {
+ t.Errorf("expected ToList() = %q, got %q", w, g)
+ }
+ })
+ t.Run("topological", func(t *testing.T) {
+ depSet := tt.depSet(t, TOPOLOGICAL)
+ if g, w := depSet.ToList().Strings(), tt.topological; !reflect.DeepEqual(g, w) {
+ t.Errorf("expected ToList() = %q, got %q", w, g)
+ }
+ })
+ })
+ }
+}
+
+func TestDepSetInvalidOrder(t *testing.T) {
+ orders := []DepSetOrder{POSTORDER, PREORDER, TOPOLOGICAL}
+
+ run := func(t *testing.T, order1, order2 DepSetOrder) {
+ defer func() {
+ if r := recover(); r != nil {
+ if err, ok := r.(error); !ok {
+ t.Fatalf("expected panic error, got %v", err)
+ } else if !strings.Contains(err.Error(), "incompatible order") {
+ t.Fatalf("expected incompatible order error, got %v", err)
+ }
+ }
+ }()
+ NewDepSet(order1, nil, []*DepSet{NewDepSet(order2, nil, nil)})
+ t.Fatal("expected panic")
+ }
+
+ for _, order1 := range orders {
+ t.Run(order1.String(), func(t *testing.T) {
+ for _, order2 := range orders {
+ t.Run(order2.String(), func(t *testing.T) {
+ if order1 != order2 {
+ run(t, order1, order2)
+ }
+ })
+ }
+ })
+ }
+}