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

Bug: 153485543
Test: depset_test.go
Change-Id: If744affdf1ed850113166ba611a79a891262040c
Merged-In: If744affdf1ed850113166ba611a79a891262040c
(cherry picked from commit 9e44e21e91cf38aa0a863bd87cffa6fe3534cc04)

3 files changed, 496 insertions, 0 deletions

diff --git a/android/Android.bp b/android/Android.bp
index d904a86c..9712c46e 100644
--- a/android/Android.bp
+++ b/android/Android.bp
@@ -18,6 +18,7 @@ bootstrap_go_package {
         "csuite_config.go",
         "defaults.go",
         "defs.go",
+        "depset.go",
         "expand.go",
         "filegroup.go",
         "hooks.go",
@@ -59,6 +60,7 @@ bootstrap_go_package {
         "arch_test.go",
         "config_test.go",
         "csuite_config_test.go",
+        "depset_test.go",
         "expand_test.go",
         "module_test.go",
         "mutator_test.go",
diff --git a/android/depset.go b/android/depset.go
new file mode 100644
index 00000000..f7070942
--- /dev/null
+++ b/android/depset.go
@@ -0,0 +1,190 @@
+// 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"
+
+// DepSet is designed to be conceptually compatible with Bazel's depsets:
+// https://docs.bazel.build/versions/master/skylark/depsets.html
+
+// A DepSet efficiently stores Paths from transitive dependencies without copying. It is stored
+// as a DAG of DepSet nodes, each of which has some direct contents and a list of dependency
+// DepSet nodes.
+//
+// A DepSet has an order that will be used to walk the DAG when ToList() is called.  The order
+// can be POSTORDER, PREORDER, or TOPOLOGICAL.  POSTORDER and PREORDER orders return a postordered
+// or preordered left to right flattened list.  TOPOLOGICAL returns a list that guarantees that
+// elements of children are listed after all of their parents (unless there are duplicate direct
+// elements in the DepSet or any of its transitive dependencies, in which case the ordering of the
+// duplicated element is not guaranteed).
+//
+// A DepSet is created by NewDepSet or NewDepSetBuilder.Build from the Paths for direct contents
+// and the *DepSets of dependencies. A DepSet is immutable once created.
+type DepSet struct {
+	preorder   bool
+	reverse    bool
+	order      DepSetOrder
+	direct     Paths
+	transitive []*DepSet
+}
+
+// DepSetBuilder is used to create an immutable DepSet.
+type DepSetBuilder struct {
+	order      DepSetOrder
+	direct     Paths
+	transitive []*DepSet
+}
+
+type DepSetOrder int
+
+const (
+	PREORDER DepSetOrder = iota
+	POSTORDER
+	TOPOLOGICAL
+)
+
+func (o DepSetOrder) String() string {
+	switch o {
+	case PREORDER:
+		return "PREORDER"
+	case POSTORDER:
+		return "POSTORDER"
+	case TOPOLOGICAL:
+		return "TOPOLOGICAL"
+	default:
+		panic(fmt.Errorf("Invalid DepSetOrder %d", o))
+	}
+}
+
+// NewDepSet returns an immutable DepSet with the given order, direct and transitive contents.
+func NewDepSet(order DepSetOrder, direct Paths, transitive []*DepSet) *DepSet {
+	var directCopy Paths
+	var transitiveCopy []*DepSet
+	if order == TOPOLOGICAL {
+		directCopy = ReversePaths(direct)
+		transitiveCopy = reverseDepSets(transitive)
+	} else {
+		// Use copy instead of append(nil, ...) to make a slice that is exactly the size of the input
+		// slice.  The DepSet is immutable, there is no need for additional capacity.
+		directCopy = make(Paths, len(direct))
+		copy(directCopy, direct)
+		transitiveCopy = make([]*DepSet, len(transitive))
+		copy(transitiveCopy, transitive)
+	}
+
+	for _, dep := range transitive {
+		if dep.order != order {
+			panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
+				order, dep.order))
+		}
+	}
+
+	return &DepSet{
+		preorder:   order == PREORDER,
+		reverse:    order == TOPOLOGICAL,
+		order:      order,
+		direct:     directCopy,
+		transitive: transitiveCopy,
+	}
+}
+
+// NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order.
+func NewDepSetBuilder(order DepSetOrder) *DepSetBuilder {
+	return &DepSetBuilder{order: order}
+}
+
+// Direct adds direct contents to the DepSet being built by a DepSetBuilder. Newly added direct
+// contents are to the right of any existing direct contents.
+func (b *DepSetBuilder) Direct(direct ...Path) *DepSetBuilder {
+	b.direct = append(b.direct, direct...)
+	return b
+}
+
+// Transitive adds transitive contents to the DepSet being built by a DepSetBuilder. Newly added
+// transitive contents are to the right of any existing transitive contents.
+func (b *DepSetBuilder) Transitive(transitive ...*DepSet) *DepSetBuilder {
+	b.transitive = append(b.transitive, transitive...)
+	return b
+}
+
+// Returns the DepSet being built by this DepSetBuilder.  The DepSetBuilder retains its contents
+// for creating more DepSets.
+func (b *DepSetBuilder) Build() *DepSet {
+	return NewDepSet(b.order, b.direct, b.transitive)
+}
+
+// walk calls the visit method in depth-first order on a DepSet, preordered if d.preorder is set,
+// otherwise postordered.
+func (d *DepSet) walk(visit func(Paths)) {
+	visited := make(map[*DepSet]bool)
+
+	var dfs func(d *DepSet)
+	dfs = func(d *DepSet) {
+		visited[d] = true
+		if d.preorder {
+			visit(d.direct)
+		}
+		for _, dep := range d.transitive {
+			if !visited[dep] {
+				dfs(dep)
+			}
+		}
+
+		if !d.preorder {
+			visit(d.direct)
+		}
+	}
+
+	dfs(d)
+}
+
+// ToList returns the DepSet flattened to a list.  The order in the list is based on the order
+// of the DepSet.  POSTORDER and PREORDER orders return a postordered or preordered left to right
+// flattened list.  TOPOLOGICAL returns a list that guarantees that elements of children are listed
+// after all of their parents (unless there are duplicate direct elements in the DepSet or any of
+// its transitive dependencies, in which case the ordering of the duplicated element is not
+// guaranteed).
+func (d *DepSet) ToList() Paths {
+	var list Paths
+	d.walk(func(paths Paths) {
+		list = append(list, paths...)
+	})
+	list = FirstUniquePaths(list)
+	if d.reverse {
+		reversePathsInPlace(list)
+	}
+	return list
+}
+
+// ToSortedList returns the direct and transitive contents of a DepSet in lexically sorted order
+// with duplicates removed.
+func (d *DepSet) ToSortedList() Paths {
+	list := d.ToList()
+	return SortedUniquePaths(list)
+}
+
+func reversePathsInPlace(list Paths) {
+	for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 {
+		list[i], list[j] = list[j], list[i]
+	}
+}
+
+func reverseDepSets(list []*DepSet) []*DepSet {
+	ret := make([]*DepSet, len(list))
+	for i := range list {
+		ret[i] = list[len(list)-1-i]
+	}
+	return ret
+}
diff --git a/android/depset_test.go b/android/depset_test.go
new file mode 100644
index 00000000..c328127b
--- /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)
+					}
+				})
+			}
+		})
+	}
+}