1 files changed, 170 insertions, 63 deletions

diff --git a/android/util.go b/android/util.go
index 08a3521a5..3c0af2f38 100644
--- a/android/util.go
+++ b/android/util.go
@@ -15,6 +15,7 @@
 package android
 
 import (
+	"cmp"
 	"fmt"
 	"path/filepath"
 	"reflect"
@@ -22,15 +23,18 @@ import (
 	"runtime"
 	"sort"
 	"strings"
+	"sync"
+
+	"github.com/google/blueprint/proptools"
 )
 
 // CopyOf returns a new slice that has the same contents as s.
-func CopyOf(s []string) []string {
+func CopyOf[T any](s []T) []T {
 	// If the input is nil, return nil and not an empty list
 	if s == nil {
 		return s
 	}
-	return append([]string{}, s...)
+	return append([]T{}, s...)
 }
 
 // Concat returns a new slice concatenated from the two input slices. It does not change the input
@@ -42,6 +46,16 @@ func Concat[T any](s1, s2 []T) []T {
 	return res
 }
 
+// JoinPathsWithPrefix converts the paths to strings, prefixes them
+// with prefix and then joins them separated by " ".
+func JoinPathsWithPrefix(paths []Path, prefix string) string {
+	strs := make([]string, len(paths))
+	for i := range paths {
+		strs[i] = paths[i].String()
+	}
+	return JoinWithPrefixAndSeparator(strs, prefix, " ")
+}
+
 // JoinWithPrefix prepends the prefix to each string in the list and
 // returns them joined together with " " as separator.
 func JoinWithPrefix(strs []string, prefix string) string {
@@ -51,17 +65,39 @@ func JoinWithPrefix(strs []string, prefix string) string {
 // JoinWithPrefixAndSeparator prepends the prefix to each string in the list and
 // returns them joined together with the given separator.
 func JoinWithPrefixAndSeparator(strs []string, prefix string, sep string) string {
+	return JoinWithPrefixSuffixAndSeparator(strs, prefix, "", sep)
+}
+
+// JoinWithSuffixAndSeparator appends the suffix to each string in the list and
+// returns them joined together with the given separator.
+func JoinWithSuffixAndSeparator(strs []string, suffix string, sep string) string {
+	return JoinWithPrefixSuffixAndSeparator(strs, "", suffix, sep)
+}
+
+// JoinWithPrefixSuffixAndSeparator appends the prefix/suffix to each string in the list and
+// returns them joined together with the given separator.
+func JoinWithPrefixSuffixAndSeparator(strs []string, prefix, suffix, sep string) string {
 	if len(strs) == 0 {
 		return ""
 	}
 
+	// Pre-calculate the length of the result
+	length := 0
+	for _, s := range strs {
+		length += len(s)
+	}
+	length += (len(prefix)+len(suffix))*len(strs) + len(sep)*(len(strs)-1)
+
 	var buf strings.Builder
+	buf.Grow(length)
 	buf.WriteString(prefix)
 	buf.WriteString(strs[0])
+	buf.WriteString(suffix)
 	for i := 1; i < len(strs); i++ {
 		buf.WriteString(sep)
 		buf.WriteString(prefix)
 		buf.WriteString(strs[i])
+		buf.WriteString(suffix)
 	}
 	return buf.String()
 }
@@ -73,15 +109,8 @@ func SortedStringKeys[V any](m map[string]V) []string {
 	return SortedKeys(m)
 }
 
-type Ordered interface {
-	~string |
-		~float32 | ~float64 |
-		~int | ~int8 | ~int16 | ~int32 | ~int64 |
-		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
-}
-
 // SortedKeys returns the keys of the given map in the ascending order.
-func SortedKeys[T Ordered, V any](m map[T]V) []T {
+func SortedKeys[T cmp.Ordered, V any](m map[T]V) []T {
 	if len(m) == 0 {
 		return nil
 	}
@@ -127,19 +156,17 @@ func SortedUniqueStringValues(m interface{}) []string {
 }
 
 // IndexList returns the index of the first occurrence of the given string in the list or -1
-func IndexList(s string, list []string) int {
+func IndexList[T comparable](t T, list []T) int {
 	for i, l := range list {
-		if l == s {
+		if l == t {
 			return i
 		}
 	}
-
 	return -1
 }
 
-// InList checks if the string belongs to the list
-func InList(s string, list []string) bool {
-	return IndexList(s, list) != -1
+func InList[T comparable](t T, list []T) bool {
+	return IndexList(t, list) != -1
 }
 
 func setFromList[T comparable](l []T) map[T]bool {
@@ -174,6 +201,12 @@ func ListSetDifference[T comparable](l1, l2 []T) (bool, []T, []T) {
 	return listsDiffer, diff1, diff2
 }
 
+// Returns true if the two lists have common elements.
+func HasIntersection[T comparable](l1, l2 []T) bool {
+	_, a, b := ListSetDifference(l1, l2)
+	return len(a)+len(b) < len(setFromList(l1))+len(setFromList(l2))
+}
+
 // Returns true if the given string s is prefixed with any string in the given prefix list.
 func HasAnyPrefix(s string, prefixList []string) bool {
 	for _, prefix := range prefixList {
@@ -277,24 +310,15 @@ func RemoveFromList(s string, list []string) (bool, []string) {
 	return removed, result
 }
 
-// FirstUniqueStrings returns all unique elements of a slice of strings, keeping the first copy of
-// each.  It modifies the slice contents in place, and returns a subslice of the original slice.
-func FirstUniqueStrings(list []string) []string {
-	// Do not moodify the input in-place, operate on a copy instead.
-	list = CopyOf(list)
-	// 128 was chosen based on BenchmarkFirstUniqueStrings results.
-	if len(list) > 128 {
-		return firstUniqueStringsMap(list)
-	}
-	return firstUniqueStringsList(list)
-}
-
-func firstUniqueStringsList(list []string) []string {
+// FirstUniqueFunc returns all unique elements of a slice, keeping the first copy of
+// each.  It does not modify the input slice. The eq function should return true
+// if two elements can be considered equal.
+func FirstUniqueFunc[SortableList ~[]Sortable, Sortable any](list SortableList, eq func(a, b Sortable) bool) SortableList {
 	k := 0
 outer:
 	for i := 0; i < len(list); i++ {
 		for j := 0; j < k; j++ {
-			if list[i] == list[j] {
+			if eq(list[i], list[j]) {
 				continue outer
 			}
 		}
@@ -304,18 +328,88 @@ outer:
 	return list[:k]
 }
 
-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]] {
+// FirstUniqueStrings returns all unique elements of a slice of strings, keeping the first copy of
+// each.  It does not modify the input slice.
+func FirstUniqueStrings(list []string) []string {
+	return firstUnique(list)
+}
+
+// firstUnique returns all unique elements of a slice, keeping the first copy of each.  It
+// does not modify the input slice.
+func firstUnique[T comparable](slice []T) []T {
+	// Do not modify the input in-place, operate on a copy instead.
+	slice = CopyOf(slice)
+	return firstUniqueInPlace(slice)
+}
+
+// firstUniqueInPlace 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 firstUniqueInPlace[T comparable](slice []T) []T {
+	// 128 was chosen based on BenchmarkFirstUniqueStrings results.
+	if len(slice) > 128 {
+		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 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
+			}
+		}
+		if readIndex != writeIndex {
+			in[writeIndex] = in[readIndex]
+		}
+		writeIndex++
+	}
+	return in[0:writeIndex]
+}
+
+// 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 and returns it.
+func ReverseSliceInPlace[T any](in []T) []T {
+	for i, j := 0, len(in)-1; i < j; i, j = i+1, j-1 {
+		in[i], in[j] = in[j], in[i]
+	}
+	return in
+}
+
+// ReverseSlice returns a copy of a slice in reverse order.
+func ReverseSlice[T any](in []T) []T {
+	if in == nil {
+		return in
+	}
+	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
@@ -458,18 +552,7 @@ func SplitFileExt(name string) (string, string, string) {
 
 // ShardPaths takes a Paths, and returns a slice of Paths where each one has at most shardSize paths.
 func ShardPaths(paths Paths, shardSize int) []Paths {
-	if len(paths) == 0 {
-		return nil
-	}
-	ret := make([]Paths, 0, (len(paths)+shardSize-1)/shardSize)
-	for len(paths) > shardSize {
-		ret = append(ret, paths[0:shardSize])
-		paths = paths[shardSize:]
-	}
-	if len(paths) > 0 {
-		ret = append(ret, paths)
-	}
-	return ret
+	return proptools.ShardBySize(paths, shardSize)
 }
 
 // ShardString takes a string and returns a slice of strings where the length of each one is
@@ -492,18 +575,7 @@ func ShardString(s string, shardSize int) []string {
 // ShardStrings takes a slice of strings, and returns a slice of slices of strings where each one has at most shardSize
 // elements.
 func ShardStrings(s []string, shardSize int) [][]string {
-	if len(s) == 0 {
-		return nil
-	}
-	ret := make([][]string, 0, (len(s)+shardSize-1)/shardSize)
-	for len(s) > shardSize {
-		ret = append(ret, s[0:shardSize])
-		s = s[shardSize:]
-	}
-	if len(s) > 0 {
-		ret = append(ret, s)
-	}
-	return ret
+	return proptools.ShardBySize(s, shardSize)
 }
 
 // CheckDuplicate checks if there are duplicates in given string list.
@@ -518,3 +590,38 @@ func CheckDuplicate(values []string) (duplicate string, found bool) {
 	}
 	return "", false
 }
+
+func AddToStringSet(set map[string]bool, items []string) {
+	for _, item := range items {
+		set[item] = true
+	}
+}
+
+// SyncMap is a wrapper around sync.Map that provides type safety via generics.
+type SyncMap[K comparable, V any] struct {
+	sync.Map
+}
+
+// Load returns the value stored in the map for a key, or the zero value if no
+// value is present.
+// The ok result indicates whether value was found in the map.
+func (m *SyncMap[K, V]) Load(key K) (value V, ok bool) {
+	v, ok := m.Map.Load(key)
+	if !ok {
+		return *new(V), false
+	}
+	return v.(V), true
+}
+
+// Store sets the value for a key.
+func (m *SyncMap[K, V]) Store(key K, value V) {
+	m.Map.Store(key, value)
+}
+
+// LoadOrStore returns the existing value for the key if present.
+// Otherwise, it stores and returns the given value.
+// The loaded result is true if the value was loaded, false if stored.
+func (m *SyncMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) {
+	v, loaded := m.Map.LoadOrStore(key, value)
+	return v.(V), loaded
+}