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/Android.bp b/android/Android.bp
index 94d2c04..0ebc29b 100644
--- a/android/Android.bp
+++ b/android/Android.bp
@@ -48,7 +48,6 @@
"defaults.go",
"defs.go",
"depset_generic.go",
- "depset_paths.go",
"deptag.go",
"expand.go",
"filegroup.go",
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()
-}
diff --git a/android/depset_paths.go b/android/depset_paths.go
deleted file mode 100644
index ed561ba..0000000
--- a/android/depset_paths.go
+++ /dev/null
@@ -1,94 +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
-
-// This file implements DepSet, a thin type-safe wrapper around depSet that contains Paths.
-
-// 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 {
- depSet
-}
-
-// DepSetBuilder is used to create an immutable DepSet.
-type DepSetBuilder struct {
- depSetBuilder
-}
-
-// NewDepSet returns an immutable DepSet with the given order, direct and transitive contents.
-func NewDepSet(order DepSetOrder, direct Paths, transitive []*DepSet) *DepSet {
- return &DepSet{*newDepSet(order, direct, transitive)}
-}
-
-// NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order.
-func NewDepSetBuilder(order DepSetOrder) *DepSetBuilder {
- return &DepSetBuilder{*newDepSetBuilder(order, Paths(nil))}
-}
-
-// 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.depSetBuilder.DirectSlice(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.depSetBuilder.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 &DepSet{*b.depSetBuilder.Build()}
-}
-
-// 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 {
- if d == nil {
- return nil
- }
- return d.toList(func(paths interface{}) interface{} {
- return FirstUniquePaths(paths.(Paths))
- }).(Paths)
-}
-
-// ToSortedList returns the direct and transitive contents of a DepSet in lexically sorted order
-// with duplicates removed.
-func (d *DepSet) ToSortedList() Paths {
- if d == nil {
- return nil
- }
- paths := d.ToList()
- return SortedUniquePaths(paths)
-}
diff --git a/android/depset_test.go b/android/depset_test.go
index 955ccb0..376dffa 100644
--- a/android/depset_test.go
+++ b/android/depset_test.go
@@ -17,51 +17,40 @@
import (
"fmt"
"reflect"
- "strconv"
"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()
+ 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(d.ToList().Strings())
+ fmt.Println(Paths(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()
+ 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(d.ToList().Strings())
+ fmt.Println(Paths(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()
+ 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(d.ToList().Strings())
+ fmt.Println(Paths(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) {
@@ -74,13 +63,13 @@
tests := []struct {
name string
- depSet func(t *testing.T, order DepSetOrder) *DepSet
+ depSet func(t *testing.T, order DepSetOrder) *DepSet[Path]
postorder, preorder, topological []string
}{
{
name: "simple",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet {
- return NewDepSet(order, Paths{c, a, b}, nil)
+ 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"},
@@ -88,8 +77,8 @@
},
{
name: "simpleNoDuplicates",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet {
- return NewDepSet(order, Paths{c, a, a, a, b}, nil)
+ 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"},
@@ -97,9 +86,9 @@
},
{
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})
+ 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"},
@@ -107,14 +96,14 @@
},
{
name: "builderReuse",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet {
+ 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(order)
+ builder := NewDepSetBuilder[Path](order)
assertEquals(t, nil, builder.Build().ToList())
builder.Direct(b)
@@ -123,7 +112,7 @@
builder.Direct(d)
assertEquals(t, Paths{b, d}, builder.Build().ToList())
- child := NewDepSetBuilder(order).Direct(c, a, e).Build()
+ child := NewDepSetBuilder[Path](order).Direct(c, a, e).Build()
builder.Transitive(child)
return builder.Build()
},
@@ -133,9 +122,9 @@
},
{
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()
+ 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"},
@@ -143,9 +132,9 @@
},
{
name: "transitiveDepsHandledSeparately",
- depSet: func(t *testing.T, order DepSetOrder) *DepSet {
- subset := NewDepSetBuilder(order).Direct(c, a, e).Build()
- builder := NewDepSetBuilder(order)
+ 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)
@@ -159,9 +148,9 @@
},
{
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()
+ 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"},
@@ -169,10 +158,10 @@
},
{
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()
+ 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
},
@@ -182,11 +171,11 @@
},
{
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()
+ 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
},
@@ -196,12 +185,12 @@
},
{
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()
+ 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"},
@@ -210,13 +199,13 @@
},
{
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()
+ 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"},
@@ -225,10 +214,10 @@
},
{
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()
+ 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"},
@@ -237,12 +226,12 @@
},
{
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()
+ 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"},
@@ -255,19 +244,19 @@
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) {
+ 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 := depSet.ToList().Strings(), tt.preorder; !reflect.DeepEqual(g, w) {
+ 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 := depSet.ToList().Strings(), tt.topological; !reflect.DeepEqual(g, w) {
+ if g, w := Paths(depSet.ToList()).Strings(), tt.topological; !reflect.DeepEqual(g, w) {
t.Errorf("expected ToList() = %q, got %q", w, g)
}
})
@@ -288,7 +277,7 @@
}
}
}()
- NewDepSet(order1, nil, []*DepSet{NewDepSet(order2, nil, nil)})
+ NewDepSet(order1, nil, []*DepSet[Path]{NewDepSet[Path](order2, nil, nil)})
t.Fatal("expected panic")
}
@@ -304,87 +293,3 @@
})
}
}
-
-func Test_firstUnique(t *testing.T) {
- f := func(t *testing.T, imp func([]string) []string, in, want []string) {
- t.Helper()
- out := imp(in)
- if !reflect.DeepEqual(out, want) {
- t.Errorf("incorrect output:")
- t.Errorf(" input: %#v", in)
- t.Errorf(" expected: %#v", want)
- t.Errorf(" got: %#v", out)
- }
- }
-
- for _, testCase := range firstUniqueStringsTestCases {
- t.Run("list", func(t *testing.T) {
- f(t, func(s []string) []string {
- return firstUniqueList(s).([]string)
- }, testCase.in, testCase.out)
- })
- t.Run("map", func(t *testing.T) {
- f(t, func(s []string) []string {
- return firstUniqueMap(s).([]string)
- }, testCase.in, testCase.out)
- })
- }
-}
-
-func Benchmark_firstUnique(b *testing.B) {
- implementations := []struct {
- name string
- f func([]string) []string
- }{
- {
- name: "list",
- f: func(slice []string) []string {
- return firstUniqueList(slice).([]string)
- },
- },
- {
- name: "map",
- f: func(slice []string) []string {
- return firstUniqueMap(slice).([]string)
- },
- },
- {
- name: "optimal",
- f: func(slice []string) []string {
- return firstUnique(slice).([]string)
- },
- },
- }
- const maxSize = 1024
- uniqueStrings := make([]string, maxSize)
- for i := range uniqueStrings {
- uniqueStrings[i] = strconv.Itoa(i)
- }
- sameString := make([]string, maxSize)
- for i := range sameString {
- sameString[i] = uniqueStrings[0]
- }
-
- f := func(b *testing.B, imp func([]string) []string, s []string) {
- for i := 0; i < b.N; i++ {
- b.ReportAllocs()
- s = append([]string(nil), s...)
- imp(s)
- }
- }
-
- for n := 1; n <= maxSize; n <<= 1 {
- b.Run(strconv.Itoa(n), func(b *testing.B) {
- for _, implementation := range implementations {
- b.Run(implementation.name, func(b *testing.B) {
- b.Run("same", func(b *testing.B) {
- f(b, implementation.f, sameString[:n])
- })
- b.Run("unique", func(b *testing.B) {
- f(b, implementation.f, uniqueStrings[:n])
- })
- })
- }
- })
- }
-}
diff --git a/android/license_metadata.go b/android/license_metadata.go
index 73000a9..8933bd5 100644
--- a/android/license_metadata.go
+++ b/android/license_metadata.go
@@ -55,7 +55,7 @@
var allDepMetadataFiles Paths
var allDepMetadataArgs []string
var allDepOutputFiles Paths
- var allDepMetadataDepSets []*PathsDepSet
+ var allDepMetadataDepSets []*DepSet[Path]
ctx.VisitDirectDepsBlueprint(func(bpdep blueprint.Module) {
dep, _ := bpdep.(Module)
@@ -127,7 +127,7 @@
JoinWithPrefix(proptools.NinjaAndShellEscapeListIncludingSpaces(base.commonProperties.Effective_license_text.Strings()), "-n "))
if isContainer {
- transitiveDeps := newPathsDepSet(nil, allDepMetadataDepSets).ToList()
+ transitiveDeps := Paths(NewDepSet[Path](TOPOLOGICAL, nil, allDepMetadataDepSets).ToList())
args = append(args,
JoinWithPrefix(proptools.NinjaAndShellEscapeListIncludingSpaces(transitiveDeps.Strings()), "-d "))
orderOnlyDeps = append(orderOnlyDeps, transitiveDeps...)
@@ -170,7 +170,7 @@
ctx.SetProvider(LicenseMetadataProvider, &LicenseMetadataInfo{
LicenseMetadataPath: licenseMetadataFile,
- LicenseMetadataDepSet: newPathsDepSet(Paths{licenseMetadataFile}, allDepMetadataDepSets),
+ LicenseMetadataDepSet: NewDepSet(TOPOLOGICAL, Paths{licenseMetadataFile}, allDepMetadataDepSets),
})
}
@@ -198,7 +198,7 @@
// LicenseMetadataInfo stores the license metadata path for a module.
type LicenseMetadataInfo struct {
LicenseMetadataPath Path
- LicenseMetadataDepSet *PathsDepSet
+ LicenseMetadataDepSet *DepSet[Path]
}
// licenseAnnotationsFromTag returns the LicenseAnnotations for a tag (if any) converted into
diff --git a/android/module.go b/android/module.go
index ba32710..c1ba67a 100644
--- a/android/module.go
+++ b/android/module.go
@@ -1517,10 +1517,10 @@
noAddressSanitizer bool
installFiles InstallPaths
- installFilesDepSet *installPathsDepSet
+ installFilesDepSet *DepSet[InstallPath]
checkbuildFiles Paths
packagingSpecs []PackagingSpec
- packagingSpecsDepSet *packagingSpecsDepSet
+ packagingSpecsDepSet *DepSet[PackagingSpec]
// katiInstalls tracks the install rules that were created by Soong but are being exported
// to Make to convert to ninja rules so that Make can add additional dependencies.
katiInstalls katiInstalls
@@ -2083,9 +2083,9 @@
// computeInstallDeps finds the installed paths of all dependencies that have a dependency
// tag that is annotated as needing installation via the isInstallDepNeeded method.
-func (m *ModuleBase) computeInstallDeps(ctx ModuleContext) ([]*installPathsDepSet, []*packagingSpecsDepSet) {
- var installDeps []*installPathsDepSet
- var packagingSpecs []*packagingSpecsDepSet
+func (m *ModuleBase) computeInstallDeps(ctx ModuleContext) ([]*DepSet[InstallPath], []*DepSet[PackagingSpec]) {
+ var installDeps []*DepSet[InstallPath]
+ var packagingSpecs []*DepSet[PackagingSpec]
ctx.VisitDirectDeps(func(dep Module) {
if isInstallDepNeeded(dep, ctx.OtherModuleDependencyTag(dep)) {
// Installation is still handled by Make, so anything hidden from Make is not
@@ -2380,7 +2380,7 @@
// set m.installFilesDepSet to only the transitive dependencies to be used as the dependencies
// of installed files of this module. It will be replaced by a depset including the installed
// files of this module at the end for use by modules that depend on this one.
- m.installFilesDepSet = newInstallPathsDepSet(nil, dependencyInstallFiles)
+ m.installFilesDepSet = NewDepSet[InstallPath](TOPOLOGICAL, nil, dependencyInstallFiles)
// Temporarily continue to call blueprintCtx.GetMissingDependencies() to maintain the previous behavior of never
// reporting missing dependency errors in Blueprint when AllowMissingDependencies == true.
@@ -2487,8 +2487,8 @@
}
}
- m.installFilesDepSet = newInstallPathsDepSet(m.installFiles, dependencyInstallFiles)
- m.packagingSpecsDepSet = newPackagingSpecsDepSet(m.packagingSpecs, dependencyPackagingSpecs)
+ m.installFilesDepSet = NewDepSet[InstallPath](TOPOLOGICAL, m.installFiles, dependencyInstallFiles)
+ m.packagingSpecsDepSet = NewDepSet[PackagingSpec](TOPOLOGICAL, m.packagingSpecs, dependencyPackagingSpecs)
buildLicenseMetadata(ctx, m.licenseMetadataFile)
@@ -3369,7 +3369,7 @@
m.module.base().hooks.runInstallHooks(m, srcPath, fullInstallPath, false)
if !m.skipInstall() {
- deps = append(deps, m.module.base().installFilesDepSet.ToList().Paths()...)
+ deps = append(deps, InstallPaths(m.module.base().installFilesDepSet.ToList()).Paths()...)
var implicitDeps, orderOnlyDeps Paths
@@ -3944,26 +3944,6 @@
return blueprint.CheckBlueprintSyntax(bpctx.ModuleFactories(), filename, contents)
}
-// installPathsDepSet is a thin type-safe wrapper around the generic depSet. It always uses
-// topological order.
-type installPathsDepSet struct {
- depSet
-}
-
-// newInstallPathsDepSet returns an immutable packagingSpecsDepSet with the given direct and
-// transitive contents.
-func newInstallPathsDepSet(direct InstallPaths, transitive []*installPathsDepSet) *installPathsDepSet {
- return &installPathsDepSet{*newDepSet(TOPOLOGICAL, direct, transitive)}
-}
-
-// ToList returns the installPathsDepSet flattened to a list in topological order.
-func (d *installPathsDepSet) ToList() InstallPaths {
- if d == nil {
- return nil
- }
- return d.depSet.ToList().(InstallPaths)
-}
-
func registerSoongConfigTraceMutator(ctx RegisterMutatorsContext) {
ctx.BottomUp("soongconfigtrace", soongConfigTraceMutator).Parallel()
}
diff --git a/android/packaging.go b/android/packaging.go
index c764a6d..503bb97 100644
--- a/android/packaging.go
+++ b/android/packaging.go
@@ -282,23 +282,3 @@
builder.Build("zip_deps", fmt.Sprintf("Zipping deps for %s", ctx.ModuleName()))
return entries
}
-
-// packagingSpecsDepSet is a thin type-safe wrapper around the generic depSet. It always uses
-// topological order.
-type packagingSpecsDepSet struct {
- depSet
-}
-
-// newPackagingSpecsDepSet returns an immutable packagingSpecsDepSet with the given direct and
-// transitive contents.
-func newPackagingSpecsDepSet(direct []PackagingSpec, transitive []*packagingSpecsDepSet) *packagingSpecsDepSet {
- return &packagingSpecsDepSet{*newDepSet(TOPOLOGICAL, direct, transitive)}
-}
-
-// ToList returns the packagingSpecsDepSet flattened to a list in topological order.
-func (d *packagingSpecsDepSet) ToList() []PackagingSpec {
- if d == nil {
- return nil
- }
- return d.depSet.ToList().([]PackagingSpec)
-}
diff --git a/android/paths.go b/android/paths.go
index 0f3d972..b8a119b 100644
--- a/android/paths.go
+++ b/android/paths.go
@@ -2199,23 +2199,3 @@
}
return false
}
-
-// PathsDepSet is a thin type-safe wrapper around the generic depSet. It always uses
-// topological order.
-type PathsDepSet struct {
- depSet
-}
-
-// newPathsDepSet returns an immutable PathsDepSet with the given direct and
-// transitive contents.
-func newPathsDepSet(direct Paths, transitive []*PathsDepSet) *PathsDepSet {
- return &PathsDepSet{*newDepSet(TOPOLOGICAL, direct, transitive)}
-}
-
-// ToList returns the PathsDepSet flattened to a list in topological order.
-func (d *PathsDepSet) ToList() Paths {
- if d == nil {
- return nil
- }
- return d.depSet.ToList().(Paths)
-}
diff --git a/android/util.go b/android/util.go
index 08a3521..c4ce71a 100644
--- a/android/util.go
+++ b/android/util.go
@@ -284,38 +284,74 @@
list = CopyOf(list)
// 128 was chosen based on BenchmarkFirstUniqueStrings results.
if len(list) > 128 {
- return firstUniqueStringsMap(list)
+ return firstUnique(list)
}
- return firstUniqueStringsList(list)
+ return firstUnique(list)
}
-func firstUniqueStringsList(list []string) []string {
- k := 0
+// 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.
+func firstUnique[T comparable](slice []T) []T {
+ // 4 was chosen based on Benchmark_firstUnique results.
+ if len(slice) > 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[T any](in []T) []T {
+ writeIndex := 0
outer:
- for i := 0; i < len(list); i++ {
- for j := 0; j < k; j++ {
- if list[i] == list[j] {
+ for readIndex := 0; readIndex < len(in); readIndex++ {
+ for compareIndex := 0; compareIndex < writeIndex; compareIndex++ {
+ if interface{}(in[readIndex]) == interface{}(in[compareIndex]) {
+ // The value at readIndex already exists somewhere in the output region
+ // of the slice before writeIndex, skip it.
continue outer
}
}
- list[k] = list[i]
- k++
+ if readIndex != writeIndex {
+ in[writeIndex] = in[readIndex]
+ }
+ writeIndex++
}
- return list[:k]
+ return in[0:writeIndex]
}
-func firstUniqueStringsMap(list []string) []string {
- k := 0
- seen := make(map[string]bool, len(list))
- for i := 0; i < len(list); i++ {
- if seen[list[i]] {
+// firstUniqueMap is an implementation of firstUnique using an O(N) hash set lookup to look for
+// duplicates.
+func firstUniqueMap[T comparable](in []T) []T {
+ writeIndex := 0
+ seen := make(map[T]bool, len(in))
+ for readIndex := 0; readIndex < len(in); readIndex++ {
+ if _, exists := seen[in[readIndex]]; exists {
continue
}
- seen[list[i]] = true
- list[k] = list[i]
- k++
+ seen[in[readIndex]] = true
+ if readIndex != writeIndex {
+ in[writeIndex] = in[readIndex]
+ }
+ writeIndex++
}
- return list[:k]
+ return in[0:writeIndex]
+}
+
+// reverseSliceInPlace reverses the elements of a slice in place.
+func reverseSliceInPlace[T any](in []T) {
+ for i, j := 0, len(in)-1; i < j; i, j = i+1, j-1 {
+ in[i], in[j] = in[j], in[i]
+ }
+}
+
+// reverseSlice returns a copy of a slice in reverse order.
+func reverseSlice[T any](in []T) []T {
+ out := make([]T, len(in))
+ for i := 0; i < len(in); i++ {
+ out[i] = in[len(in)-1-i]
+ }
+ return out
}
// LastUniqueStrings returns all unique elements of a slice of strings, keeping the last copy of
diff --git a/android/util_test.go b/android/util_test.go
index a2ef589..bee31a9 100644
--- a/android/util_test.go
+++ b/android/util_test.go
@@ -74,10 +74,10 @@
for _, testCase := range firstUniqueStringsTestCases {
t.Run("list", func(t *testing.T) {
- f(t, firstUniqueStringsList, testCase.in, testCase.out)
+ f(t, firstUniqueList[string], testCase.in, testCase.out)
})
t.Run("map", func(t *testing.T) {
- f(t, firstUniqueStringsMap, testCase.in, testCase.out)
+ f(t, firstUniqueMap[string], testCase.in, testCase.out)
})
}
}
@@ -604,11 +604,11 @@
}{
{
name: "list",
- f: firstUniqueStringsList,
+ f: firstUniqueList[string],
},
{
name: "map",
- f: firstUniqueStringsMap,
+ f: firstUniqueMap[string],
},
{
name: "optimal",