Use generics for DepSets
Use Go's generics for DepSets so they don't require a type-specific
wrapper and reflection.
Test: depsets_test.go
Change-Id: I22ba0b7d680d37d2cd05230b0f560d166c4dd20b
diff --git a/android/depset_generic.go b/android/depset_generic.go
index f00e462..ae14d32 100644
--- a/android/depset_generic.go
+++ b/android/depset_generic.go
@@ -16,10 +16,9 @@
import (
"fmt"
- "reflect"
)
-// depSet is designed to be conceptually compatible with Bazel's depsets:
+// DepSet is designed to be conceptually compatible with Bazel's depsets:
// https://docs.bazel.build/versions/master/skylark/depsets.html
type DepSetOrder int
@@ -43,142 +42,114 @@
}
}
-// 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.
+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
+// 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
+// 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.
-//
-// This object uses reflection to remain agnostic to the type it contains. It should be replaced
-// with generics once those exist in Go. Callers should generally use a thin wrapper around depSet
-// that provides type-safe methods like DepSet for Paths.
-type depSet struct {
+// 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 {
preorder bool
reverse bool
order DepSetOrder
- direct interface{}
- transitive []*depSet
+ direct []T
+ transitive []*DepSet[T]
}
-type depSetInterface interface {
- embeddedDepSet() *depSet
-}
-
-func (d *depSet) embeddedDepSet() *depSet {
- return d
-}
-
-var _ depSetInterface = (*depSet)(nil)
-
-// newDepSet returns an immutable depSet with the given order, direct and transitive contents.
-// direct must be a slice, but is not type-safe due to the lack of generics in Go. It can be a
-// nil slice, but not a nil interface{}, i.e. []string(nil) but not nil.
-func newDepSet(order DepSetOrder, direct interface{}, transitive interface{}) *depSet {
- var directCopy interface{}
- transitiveDepSet := sliceToDepSets(transitive, order)
-
- if order == TOPOLOGICAL {
- directCopy = reverseSlice(direct)
- reverseSliceInPlace(transitiveDepSet)
- } else {
- directCopy = copySlice(direct)
+// 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]
+ 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))
+ }
}
- return &depSet{
+ 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)
+ } else {
+ directCopy = append([]T(nil), direct...)
+ transitiveCopy = append([]*DepSet[T](nil), transitive...)
+ }
+
+ return &DepSet[T]{
preorder: order == PREORDER,
reverse: order == TOPOLOGICAL,
order: order,
direct: directCopy,
- transitive: transitiveDepSet,
+ transitive: transitiveCopy,
}
}
-// depSetBuilder is used to create an immutable depSet.
-type depSetBuilder struct {
+// DepSetBuilder is used to create an immutable DepSet.
+type DepSetBuilder[T depSettableType] struct {
order DepSetOrder
- direct reflect.Value
- transitive []*depSet
+ 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(order DepSetOrder, typ interface{}) *depSetBuilder {
- empty := reflect.Zero(reflect.TypeOf(typ))
- return &depSetBuilder{
- order: order,
- direct: empty,
+// 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,
}
}
-// sliceToDepSets converts a slice of any type that implements depSetInterface (by having a depSet
-// embedded in it) into a []*depSet.
-func sliceToDepSets(in interface{}, order DepSetOrder) []*depSet {
- slice := reflect.ValueOf(in)
- length := slice.Len()
- out := make([]*depSet, length)
- for i := 0; i < length; i++ {
- vi := slice.Index(i)
- depSetIntf, ok := vi.Interface().(depSetInterface)
- if !ok {
- panic(fmt.Errorf("element %d is a %s, not a depSetInterface", i, vi.Type()))
- }
- depSet := depSetIntf.embeddedDepSet()
- if depSet.order != order {
- panic(fmt.Errorf("incompatible order, new depSet is %s but transitive depSet is %s",
- order, depSet.order))
- }
- out[i] = depSet
- }
- return out
-}
-
-// 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. The argument must be a slice, but
-// is not type-safe due to the lack of generics in Go.
-func (b *depSetBuilder) DirectSlice(direct interface{}) *depSetBuilder {
- b.direct = reflect.AppendSlice(b.direct, reflect.ValueOf(direct))
+// 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. The argument must be the same type
-// as the element of the slice passed to newDepSetBuilder, but is not type-safe due to the lack of
-// generics in Go.
-func (b *depSetBuilder) Direct(direct interface{}) *depSetBuilder {
- b.direct = reflect.Append(b.direct, reflect.ValueOf(direct))
+// 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. The argument can
-// be any slice of type that has depSet embedded in it.
-func (b *depSetBuilder) Transitive(transitive interface{}) *depSetBuilder {
- depSets := sliceToDepSets(transitive, b.order)
- b.transitive = append(b.transitive, depSets...)
+// 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.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
+// 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.Interface(), b.transitive)
+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) walk(visit func(interface{})) {
- visited := make(map[*depSet]bool)
+func (d *DepSet[T]) walk(visit func([]T)) {
+ visited := make(map[*DepSet[T]]bool)
- var dfs func(d *depSet)
- dfs = func(d *depSet) {
+ var dfs func(d *DepSet[T])
+ dfs = func(d *DepSet[T]) {
visited[d] = true
if d.preorder {
visit(d.direct)
@@ -197,155 +168,33 @@
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
+// 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).
-//
-// This method uses a reflection-based implementation to find the unique elements in slice, which
-// is around 3x slower than a concrete implementation. Type-safe wrappers around depSet can
-// provide their own implementation of ToList that calls depSet.toList with a method that
-// uses a concrete implementation.
-func (d *depSet) ToList() interface{} {
- return d.toList(firstUnique)
+func (d *DepSet[T]) ToList() []T {
+ return d.toList(firstUnique[T])
}
-// 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
+// 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). The firstUniqueFunc is used to remove duplicates from the list.
-func (d *depSet) toList(firstUniqueFunc func(interface{}) interface{}) interface{} {
+func (d *DepSet[T]) toList(firstUniqueFunc func([]T) []T) []T {
if d == nil {
return nil
}
- slice := reflect.Zero(reflect.TypeOf(d.direct))
- d.walk(func(paths interface{}) {
- slice = reflect.AppendSlice(slice, reflect.ValueOf(paths))
+ var list []T
+ d.walk(func(paths []T) {
+ list = append(list, paths...)
})
- list := slice.Interface()
list = firstUniqueFunc(list)
if d.reverse {
reverseSliceInPlace(list)
}
return list
}
-
-// firstUnique returns all unique elements of a slice, keeping the first copy of each. It
-// modifies the slice contents in place, and returns a subslice of the original slice. The
-// argument must be a slice, but is not type-safe due to the lack of reflection in Go.
-//
-// Performance of the reflection-based firstUnique is up to 3x slower than a concrete type
-// version such as FirstUniqueStrings.
-func firstUnique(slice interface{}) interface{} {
- // 4 was chosen based on Benchmark_firstUnique results.
- if reflect.ValueOf(slice).Len() > 4 {
- return firstUniqueMap(slice)
- }
- return firstUniqueList(slice)
-}
-
-// firstUniqueList is an implementation of firstUnique using an O(N^2) list comparison to look for
-// duplicates.
-func firstUniqueList(in interface{}) interface{} {
- writeIndex := 0
- slice := reflect.ValueOf(in)
- length := slice.Len()
-outer:
- for readIndex := 0; readIndex < length; readIndex++ {
- readValue := slice.Index(readIndex)
- for compareIndex := 0; compareIndex < writeIndex; compareIndex++ {
- compareValue := slice.Index(compareIndex)
- // These two Interface() calls seem to cause an allocation and significantly
- // slow down this list-based implementation. The map implementation below doesn't
- // have this issue because reflect.Value.MapIndex takes a Value and appears to be
- // able to do the map lookup without an allocation.
- if readValue.Interface() == compareValue.Interface() {
- // The value at readIndex already exists somewhere in the output region
- // of the slice before writeIndex, skip it.
- continue outer
- }
- }
- if readIndex != writeIndex {
- writeValue := slice.Index(writeIndex)
- writeValue.Set(readValue)
- }
- writeIndex++
- }
- return slice.Slice(0, writeIndex).Interface()
-}
-
-var trueValue = reflect.ValueOf(true)
-
-// firstUniqueList is an implementation of firstUnique using an O(N) hash set lookup to look for
-// duplicates.
-func firstUniqueMap(in interface{}) interface{} {
- writeIndex := 0
- slice := reflect.ValueOf(in)
- length := slice.Len()
- seen := reflect.MakeMapWithSize(reflect.MapOf(slice.Type().Elem(), trueValue.Type()), slice.Len())
- for readIndex := 0; readIndex < length; readIndex++ {
- readValue := slice.Index(readIndex)
- if seen.MapIndex(readValue).IsValid() {
- continue
- }
- seen.SetMapIndex(readValue, trueValue)
- if readIndex != writeIndex {
- writeValue := slice.Index(writeIndex)
- writeValue.Set(readValue)
- }
- writeIndex++
- }
- return slice.Slice(0, writeIndex).Interface()
-}
-
-// reverseSliceInPlace reverses the elements of a slice in place. The argument must be a slice, but
-// is not type-safe due to the lack of reflection in Go.
-func reverseSliceInPlace(in interface{}) {
- swapper := reflect.Swapper(in)
- slice := reflect.ValueOf(in)
- length := slice.Len()
- for i, j := 0, length-1; i < j; i, j = i+1, j-1 {
- swapper(i, j)
- }
-}
-
-// reverseSlice returns a copy of a slice in reverse order. The argument must be a slice, but is
-// not type-safe due to the lack of reflection in Go.
-func reverseSlice(in interface{}) interface{} {
- slice := reflect.ValueOf(in)
- if !slice.IsValid() || slice.IsNil() {
- return in
- }
- if slice.Kind() != reflect.Slice {
- panic(fmt.Errorf("%t is not a slice", in))
- }
- length := slice.Len()
- if length == 0 {
- return in
- }
- out := reflect.MakeSlice(slice.Type(), length, length)
- for i := 0; i < length; i++ {
- out.Index(i).Set(slice.Index(length - 1 - i))
- }
- return out.Interface()
-}
-
-// copySlice returns a copy of a slice. The argument must be a slice, but is not type-safe due to
-// the lack of reflection in Go.
-func copySlice(in interface{}) interface{} {
- slice := reflect.ValueOf(in)
- if !slice.IsValid() || slice.IsNil() {
- return in
- }
- length := slice.Len()
- if length == 0 {
- return in
- }
- out := reflect.MakeSlice(slice.Type(), length, length)
- reflect.Copy(out, slice)
- return out.Interface()
-}