Convert DepSet to a wrapper around a pointer
In preparation for converting DepSet to use unique.Handle, make DepSet
a struct that contains a pointer to an internal *depSet, and make all
the callers use DepSet instead of *DepSet.
Bug: 375276086
Test: depset_test.go
Flag: EXEMPT refactor
Change-Id: Ie498e698e03a6e470d75ede101672229e7b157cd
diff --git a/android/depset_generic.go b/android/depset_generic.go
index d04f88b..6dab3b3 100644
--- a/android/depset_generic.go
+++ b/android/depset_generic.go
@@ -16,6 +16,8 @@
import (
"fmt"
+ "iter"
+ "slices"
"github.com/google/blueprint"
)
@@ -60,11 +62,24 @@
// 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]
+ 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 {
@@ -72,25 +87,28 @@
Reverse bool
Order DepSetOrder
Direct []T
- Transitive []*DepSet[T]
+ Transitive []DepSet[T]
}
func (d *DepSet[T]) ToGob() *depSetGob[T] {
+ impl := d.impl()
return &depSetGob[T]{
- Preorder: d.preorder,
- Reverse: d.reverse,
- Order: d.order,
- Direct: d.direct,
- Transitive: d.transitive,
+ Preorder: impl.preorder,
+ Reverse: impl.reverse,
+ Order: impl.order,
+ Direct: impl.direct,
+ Transitive: impl.transitive,
}
}
func (d *DepSet[T]) FromGob(data *depSetGob[T]) {
- d.preorder = data.Preorder
- d.reverse = data.Reverse
- d.order = data.Order
- d.direct = data.Direct
- d.transitive = data.Transitive
+ 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) {
@@ -102,40 +120,59 @@
}
// 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] {
+func NewDepSet[T depSettableType](order DepSetOrder, direct []T, transitive []DepSet[T]) DepSet[T] {
var directCopy []T
- var transitiveCopy []*DepSet[T]
+ var transitiveCopy []DepSet[T]
+ nonEmptyTransitiveCount := 0
for _, t := range transitive {
- if t.order != order {
- panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
- order, t.order))
+ 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)
- transitiveCopy = ReverseSlice(transitive)
+ transitiveIter = slices.Backward(transitive)
} else {
- directCopy = append([]T(nil), direct...)
- transitiveCopy = append([]*DepSet[T](nil), transitive...)
+ directCopy = slices.Clone(direct)
+ transitiveIter = slices.All(transitive)
+ }
+ for _, t := range transitiveIter {
+ if t.handle != nil {
+ transitiveCopy = append(transitiveCopy, t)
+ }
}
- return &DepSet[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]
+ transitive []DepSet[T]
}
// NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order and
@@ -162,11 +199,11 @@
// 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] {
+func (b *DepSetBuilder[T]) Transitive(transitive ...DepSet[T]) *DepSetBuilder[T] {
for _, t := range transitive {
- if t.order != b.order {
+ 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.order, t.order()))
}
}
b.transitive = append(b.transitive, transitive...)
@@ -175,29 +212,30 @@
// Returns the DepSet being built by this DepSetBuilder. The DepSetBuilder retains its contents
// for creating more depSets.
-func (b *DepSetBuilder[T]) Build() *DepSet[T] {
+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)
+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]) {
+ var dfs func(d DepSet[T])
+ dfs = func(d DepSet[T]) {
+ impl := d.impl()
visited[d] = true
- if d.preorder {
- visit(d.direct)
+ if impl.preorder {
+ visit(impl.direct)
}
- for _, dep := range d.transitive {
+ for _, dep := range impl.transitive {
if !visited[dep] {
dfs(dep)
}
}
- if !d.preorder {
- visit(d.direct)
+ if !impl.preorder {
+ visit(impl.direct)
}
}
@@ -210,16 +248,17 @@
// 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 == nil {
+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 d.reverse {
+ if impl.reverse {
ReverseSliceInPlace(list)
}
return list
diff --git a/android/depset_test.go b/android/depset_test.go
index 376dffa..46c5b99 100644
--- a/android/depset_test.go
+++ b/android/depset_test.go
@@ -63,12 +63,12 @@
tests := []struct {
name string
- depSet func(t *testing.T, order DepSetOrder) *DepSet[Path]
+ depSet func(t *testing.T, order DepSetOrder) DepSet[Path]
postorder, preorder, topological []string
}{
{
name: "simple",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
return NewDepSet[Path](order, Paths{c, a, b}, nil)
},
postorder: []string{"c", "a", "b"},
@@ -77,7 +77,7 @@
},
{
name: "simpleNoDuplicates",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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"},
@@ -86,9 +86,9 @@
},
{
name: "nesting",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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})
+ return NewDepSet[Path](order, Paths{b, d}, []DepSet[Path]{subset})
},
postorder: []string{"c", "a", "e", "b", "d"},
preorder: []string{"b", "d", "c", "a", "e"},
@@ -96,7 +96,7 @@
},
{
name: "builderReuse",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ depSet: func(t *testing.T, order DepSetOrder) DepSet[Path] {
assertEquals := func(t *testing.T, w, g Paths) {
t.Helper()
if !reflect.DeepEqual(w, g) {
@@ -122,7 +122,7 @@
},
{
name: "builderChaining",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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()
},
@@ -132,7 +132,7 @@
},
{
name: "transitiveDepsHandledSeparately",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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)
@@ -148,7 +148,7 @@
},
{
name: "nestingNoDuplicates",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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()
},
@@ -158,7 +158,7 @@
},
{
name: "chain",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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()
@@ -171,7 +171,7 @@
},
{
name: "diamond",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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()
@@ -185,7 +185,7 @@
},
{
name: "extendedDiamond",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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()
@@ -199,7 +199,7 @@
},
{
name: "extendedDiamondRightArm",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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()
@@ -214,7 +214,7 @@
},
{
name: "orderConflict",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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()
@@ -226,7 +226,7 @@
},
{
name: "orderConflictNested",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
+ 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()
@@ -238,6 +238,18 @@
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 {
@@ -277,7 +289,7 @@
}
}
}()
- NewDepSet(order1, nil, []*DepSet[Path]{NewDepSet[Path](order2, nil, nil)})
+ NewDepSet(order1, nil, []DepSet[Path]{NewDepSet[Path](order2, Paths{PathForTesting("a")}, nil)})
t.Fatal("expected panic")
}