Move DepSet to blueprint
Bug: 375276086
Test: depset_test.go
Flag: EXEMPT refactor
Change-Id: I408df647fa1ee7854078468985a62019cbf8bbaf
diff --git a/android/Android.bp b/android/Android.bp
index 3b54326..05ce10a 100644
--- a/android/Android.bp
+++ b/android/Android.bp
@@ -50,7 +50,6 @@
"deapexer.go",
"defaults.go",
"defs.go",
- "depset_generic.go",
"deptag.go",
"dirgroup.go",
"early_module_context.go",
@@ -123,7 +122,6 @@
"configured_jars_test.go",
"csuite_config_test.go",
"defaults_test.go",
- "depset_test.go",
"deptag_test.go",
"expand_test.go",
"filegroup_test.go",
diff --git a/android/depset_generic.go b/android/depset_generic.go
deleted file mode 100644
index 6dab3b3..0000000
--- a/android/depset_generic.go
+++ /dev/null
@@ -1,265 +0,0 @@
-// 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"
- "iter"
- "slices"
-
- "github.com/google/blueprint"
-)
-
-// DepSet is designed to be conceptually compatible with Bazel's depsets:
-// https://docs.bazel.build/versions/master/skylark/depsets.html
-
-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))
- }
-}
-
-type depSettableType comparable
-
-// A DepSet efficiently stores a slice of an arbitrary type 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 slice for direct contents
-// and the *DepSets of dependencies. A DepSet is immutable once created.
-type DepSet[T depSettableType] struct {
- handle *depSet[T]
-}
-
-type depSet[T depSettableType] struct {
- preorder bool
- reverse bool
- order DepSetOrder
- direct []T
- transitive []DepSet[T]
-}
-
-func (d DepSet[T]) impl() *depSet[T] {
- return d.handle
-}
-
-func (d DepSet[T]) order() DepSetOrder {
- impl := d.impl()
- return impl.order
-}
-
-type depSetGob[T depSettableType] struct {
- Preorder bool
- Reverse bool
- Order DepSetOrder
- Direct []T
- Transitive []DepSet[T]
-}
-
-func (d *DepSet[T]) ToGob() *depSetGob[T] {
- impl := d.impl()
- return &depSetGob[T]{
- Preorder: impl.preorder,
- Reverse: impl.reverse,
- Order: impl.order,
- Direct: impl.direct,
- Transitive: impl.transitive,
- }
-}
-
-func (d *DepSet[T]) FromGob(data *depSetGob[T]) {
- d.handle = &depSet[T]{
- preorder: data.Preorder,
- reverse: data.Reverse,
- order: data.Order,
- direct: data.Direct,
- transitive: data.Transitive,
- }
-}
-
-func (d *DepSet[T]) GobEncode() ([]byte, error) {
- return blueprint.CustomGobEncode[depSetGob[T]](d)
-}
-
-func (d *DepSet[T]) GobDecode(data []byte) error {
- return blueprint.CustomGobDecode[depSetGob[T]](data, d)
-}
-
-// NewDepSet returns an immutable DepSet with the given order, direct and transitive contents.
-func NewDepSet[T depSettableType](order DepSetOrder, direct []T, transitive []DepSet[T]) DepSet[T] {
- var directCopy []T
- var transitiveCopy []DepSet[T]
- nonEmptyTransitiveCount := 0
- for _, t := range transitive {
- if t.handle != nil {
- if t.order() != order {
- panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
- order, t.order()))
- }
- nonEmptyTransitiveCount++
- }
- }
-
- if nonEmptyTransitiveCount > 0 {
- transitiveCopy = make([]DepSet[T], 0, nonEmptyTransitiveCount)
- }
- var transitiveIter iter.Seq2[int, DepSet[T]]
- if order == TOPOLOGICAL {
- // TOPOLOGICAL is implemented as a postorder traversal followed by reversing the output.
- // Pre-reverse the inputs here so their order is maintained in the output.
- directCopy = ReverseSlice(direct)
- transitiveIter = slices.Backward(transitive)
- } else {
- directCopy = slices.Clone(direct)
- transitiveIter = slices.All(transitive)
- }
- for _, t := range transitiveIter {
- if t.handle != nil {
- transitiveCopy = append(transitiveCopy, t)
- }
- }
-
- if len(directCopy) == 0 && len(transitive) == 0 {
- return DepSet[T]{nil}
- }
-
- depSet := &depSet[T]{
- preorder: order == PREORDER,
- reverse: order == TOPOLOGICAL,
- order: order,
- direct: directCopy,
- transitive: transitiveCopy,
- }
-
- return DepSet[T]{depSet}
-}
-
-// DepSetBuilder is used to create an immutable DepSet.
-type DepSetBuilder[T depSettableType] struct {
- order DepSetOrder
- direct []T
- transitive []DepSet[T]
-}
-
-// NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order and
-// type, represented by a slice of type that will be in the DepSet.
-func NewDepSetBuilder[T depSettableType](order DepSetOrder) *DepSetBuilder[T] {
- return &DepSetBuilder[T]{
- order: order,
- }
-}
-
-// DirectSlice 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[T]) DirectSlice(direct []T) *DepSetBuilder[T] {
- b.direct = append(b.direct, direct...)
- return b
-}
-
-// 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[T]) Direct(direct ...T) *DepSetBuilder[T] {
- 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[T]) Transitive(transitive ...DepSet[T]) *DepSetBuilder[T] {
- for _, t := range transitive {
- if t.handle != nil && t.order() != b.order {
- panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
- b.order, t.order()))
- }
- }
- 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[T]) Build() DepSet[T] {
- 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[T]) walk(visit func([]T)) {
- visited := make(map[DepSet[T]]bool)
-
- var dfs func(d DepSet[T])
- dfs = func(d DepSet[T]) {
- impl := d.impl()
- visited[d] = true
- if impl.preorder {
- visit(impl.direct)
- }
- for _, dep := range impl.transitive {
- if !visited[dep] {
- dfs(dep)
- }
- }
-
- if !impl.preorder {
- visit(impl.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[T]) ToList() []T {
- if d.handle == nil {
- return nil
- }
- impl := d.impl()
- var list []T
- d.walk(func(paths []T) {
- list = append(list, paths...)
- })
- list = firstUniqueInPlace(list)
- if impl.reverse {
- ReverseSliceInPlace(list)
- }
- return list
-}
diff --git a/android/depset_test.go b/android/depset_test.go
deleted file mode 100644
index 46c5b99..0000000
--- a/android/depset_test.go
+++ /dev/null
@@ -1,307 +0,0 @@
-// 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[Path](POSTORDER).Direct(PathForTesting("a")).Build()
- b := NewDepSetBuilder[Path](POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build()
- c := NewDepSetBuilder[Path](POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build()
- d := NewDepSetBuilder[Path](POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
-
- fmt.Println(Paths(d.ToList()).Strings())
- // Output: [a b c d]
-}
-
-func ExampleDepSet_ToList_preordered() {
- a := NewDepSetBuilder[Path](PREORDER).Direct(PathForTesting("a")).Build()
- b := NewDepSetBuilder[Path](PREORDER).Direct(PathForTesting("b")).Transitive(a).Build()
- c := NewDepSetBuilder[Path](PREORDER).Direct(PathForTesting("c")).Transitive(a).Build()
- d := NewDepSetBuilder[Path](PREORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
-
- fmt.Println(Paths(d.ToList()).Strings())
- // Output: [d b a c]
-}
-
-func ExampleDepSet_ToList_topological() {
- a := NewDepSetBuilder[Path](TOPOLOGICAL).Direct(PathForTesting("a")).Build()
- b := NewDepSetBuilder[Path](TOPOLOGICAL).Direct(PathForTesting("b")).Transitive(a).Build()
- c := NewDepSetBuilder[Path](TOPOLOGICAL).Direct(PathForTesting("c")).Transitive(a).Build()
- d := NewDepSetBuilder[Path](TOPOLOGICAL).Direct(PathForTesting("d")).Transitive(b, c).Build()
-
- fmt.Println(Paths(d.ToList()).Strings())
- // Output: [d b c a]
-}
-
-// 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[Path]
- postorder, preorder, topological []string
- }{
- {
- name: "simple",
- depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
- return NewDepSet[Path](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[Path] {
- return NewDepSet[Path](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[Path] {
- subset := NewDepSet[Path](order, Paths{c, a, e}, nil)
- return NewDepSet[Path](order, Paths{b, d}, []DepSet[Path]{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[Path] {
- assertEquals := func(t *testing.T, w, g Paths) {
- t.Helper()
- if !reflect.DeepEqual(w, g) {
- t.Errorf("want %q, got %q", w, g)
- }
- }
- builder := NewDepSetBuilder[Path](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[Path](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[Path] {
- return NewDepSetBuilder[Path](order).Direct(b).Direct(d).
- Transitive(NewDepSetBuilder[Path](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[Path] {
- subset := NewDepSetBuilder[Path](order).Direct(c, a, e).Build()
- builder := NewDepSetBuilder[Path](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[Path] {
- subset := NewDepSetBuilder[Path](order).Direct(c, a, e).Build()
- return NewDepSetBuilder[Path](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[Path] {
- c := NewDepSetBuilder[Path](order).Direct(c).Build()
- b := NewDepSetBuilder[Path](order).Direct(b).Transitive(c).Build()
- a := NewDepSetBuilder[Path](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[Path] {
- d := NewDepSetBuilder[Path](order).Direct(d).Build()
- c := NewDepSetBuilder[Path](order).Direct(c).Transitive(d).Build()
- b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Build()
- a := NewDepSetBuilder[Path](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[Path] {
- d := NewDepSetBuilder[Path](order).Direct(d).Build()
- e := NewDepSetBuilder[Path](order).Direct(e).Build()
- b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Transitive(e).Build()
- c := NewDepSetBuilder[Path](order).Direct(c).Transitive(e).Transitive(d).Build()
- a := NewDepSetBuilder[Path](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[Path] {
- d := NewDepSetBuilder[Path](order).Direct(d).Build()
- e := NewDepSetBuilder[Path](order).Direct(e).Build()
- b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Transitive(e).Build()
- c2 := NewDepSetBuilder[Path](order).Direct(c2).Transitive(e).Transitive(d).Build()
- c := NewDepSetBuilder[Path](order).Direct(c).Transitive(c2).Build()
- a := NewDepSetBuilder[Path](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[Path] {
- child1 := NewDepSetBuilder[Path](order).Direct(a, b).Build()
- child2 := NewDepSetBuilder[Path](order).Direct(b, a).Build()
- parent := NewDepSetBuilder[Path](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[Path] {
- a := NewDepSetBuilder[Path](order).Direct(a).Build()
- b := NewDepSetBuilder[Path](order).Direct(b).Build()
- child1 := NewDepSetBuilder[Path](order).Transitive(a).Transitive(b).Build()
- child2 := NewDepSetBuilder[Path](order).Transitive(b).Transitive(a).Build()
- parent := NewDepSetBuilder[Path](order).Transitive(child1).Transitive(child2).Build()
- return parent
- },
- postorder: []string{"a", "b"},
- preorder: []string{"a", "b"},
- topological: []string{"b", "a"},
- },
- {
- name: "zeroDepSet",
- depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
- a := NewDepSetBuilder[Path](order).Build()
- var b DepSet[Path]
- c := NewDepSetBuilder[Path](order).Direct(c).Transitive(a, b).Build()
- return c
- },
- postorder: []string{"c"},
- preorder: []string{"c"},
- topological: []string{"c"},
- },
- }
-
- 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 := Paths(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 := Paths(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 := Paths(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[Path]{NewDepSet[Path](order2, Paths{PathForTesting("a")}, 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)
- }
- })
- }
- })
- }
-}