123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569 |
- // Copyright 2015 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"
- "path/filepath"
- "reflect"
- "regexp"
- "runtime"
- "sort"
- "strings"
- )
- // CopyOf returns a new slice that has the same contents as s.
- 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([]T{}, s...)
- }
- // Concat returns a new slice concatenated from the two input slices. It does not change the input
- // slices.
- func Concat[T any](s1, s2 []T) []T {
- res := make([]T, 0, len(s1)+len(s2))
- res = append(res, s1...)
- res = append(res, s2...)
- 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 {
- return JoinWithPrefixAndSeparator(strs, prefix, " ")
- }
- // 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 {
- if len(strs) == 0 {
- return ""
- }
- var buf strings.Builder
- buf.WriteString(prefix)
- buf.WriteString(strs[0])
- for i := 1; i < len(strs); i++ {
- buf.WriteString(sep)
- buf.WriteString(prefix)
- buf.WriteString(strs[i])
- }
- return buf.String()
- }
- // SortedStringKeys returns the keys of the given map in the ascending order.
- //
- // Deprecated: Use SortedKeys instead.
- 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 {
- if len(m) == 0 {
- return nil
- }
- ret := make([]T, 0, len(m))
- for k := range m {
- ret = append(ret, k)
- }
- sort.Slice(ret, func(i, j int) bool {
- return ret[i] < ret[j]
- })
- return ret
- }
- // stringValues returns the values of the given string-valued map in randomized map order.
- func stringValues(m interface{}) []string {
- v := reflect.ValueOf(m)
- if v.Kind() != reflect.Map {
- panic(fmt.Sprintf("%#v is not a map", m))
- }
- if v.Len() == 0 {
- return nil
- }
- iter := v.MapRange()
- s := make([]string, 0, v.Len())
- for iter.Next() {
- s = append(s, iter.Value().String())
- }
- return s
- }
- // SortedStringValues returns the values of the given string-valued map in the ascending order.
- func SortedStringValues(m interface{}) []string {
- s := stringValues(m)
- sort.Strings(s)
- return s
- }
- // SortedUniqueStringValues returns the values of the given string-valued map in the ascending order
- // with duplicates removed.
- func SortedUniqueStringValues(m interface{}) []string {
- s := stringValues(m)
- return SortedUniqueStrings(s)
- }
- // IndexList returns the index of the first occurrence of the given string in the list or -1
- func IndexList(s string, list []string) int {
- for i, l := range list {
- if l == s {
- 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 setFromList[T comparable](l []T) map[T]bool {
- m := make(map[T]bool, len(l))
- for _, t := range l {
- m[t] = true
- }
- return m
- }
- // ListSetDifference checks if the two lists contain the same elements. It returns
- // a boolean which is true if there is a difference, and then returns lists of elements
- // that are in l1 but not l2, and l2 but not l1.
- func ListSetDifference[T comparable](l1, l2 []T) (bool, []T, []T) {
- listsDiffer := false
- diff1 := []T{}
- diff2 := []T{}
- m1 := setFromList(l1)
- m2 := setFromList(l2)
- for t := range m1 {
- if _, ok := m2[t]; !ok {
- diff1 = append(diff1, t)
- listsDiffer = true
- }
- }
- for t := range m2 {
- if _, ok := m1[t]; !ok {
- diff2 = append(diff2, t)
- listsDiffer = true
- }
- }
- return listsDiffer, diff1, diff2
- }
- // 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 {
- if strings.HasPrefix(s, prefix) {
- return true
- }
- }
- return false
- }
- // Returns true if any string in the given list has the given substring.
- func SubstringInList(list []string, substr string) bool {
- for _, s := range list {
- if strings.Contains(s, substr) {
- return true
- }
- }
- return false
- }
- // Returns true if any string in the given list has the given prefix.
- func PrefixInList(list []string, prefix string) bool {
- for _, s := range list {
- if strings.HasPrefix(s, prefix) {
- return true
- }
- }
- return false
- }
- // Returns true if any string in the given list has the given suffix.
- func SuffixInList(list []string, suffix string) bool {
- for _, s := range list {
- if strings.HasSuffix(s, suffix) {
- return true
- }
- }
- return false
- }
- // IndexListPred returns the index of the element which in the given `list` satisfying the predicate, or -1 if there is no such element.
- func IndexListPred(pred func(s string) bool, list []string) int {
- for i, l := range list {
- if pred(l) {
- return i
- }
- }
- return -1
- }
- // FilterList divides the string list into two lists: one with the strings belonging
- // to the given filter list, and the other with the remaining ones
- func FilterList(list []string, filter []string) (remainder []string, filtered []string) {
- // InList is O(n). May be worth using more efficient lookup for longer lists.
- for _, l := range list {
- if InList(l, filter) {
- filtered = append(filtered, l)
- } else {
- remainder = append(remainder, l)
- }
- }
- return
- }
- // FilterListPred returns the elements of the given list for which the predicate
- // returns true. Order is kept.
- func FilterListPred(list []string, pred func(s string) bool) (filtered []string) {
- for _, l := range list {
- if pred(l) {
- filtered = append(filtered, l)
- }
- }
- return
- }
- // RemoveListFromList removes the strings belonging to the filter list from the
- // given list and returns the result
- func RemoveListFromList(list []string, filter_out []string) (result []string) {
- result = make([]string, 0, len(list))
- for _, l := range list {
- if !InList(l, filter_out) {
- result = append(result, l)
- }
- }
- return
- }
- // RemoveFromList removes given string from the string list.
- func RemoveFromList(s string, list []string) (bool, []string) {
- result := make([]string, 0, len(list))
- var removed bool
- for _, item := range list {
- if item != s {
- result = append(result, item)
- } else {
- removed = true
- }
- }
- return removed, result
- }
- // 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[in[readIndex]] = true
- if readIndex != writeIndex {
- in[writeIndex] = in[readIndex]
- }
- writeIndex++
- }
- 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
- // each. It modifies the slice contents in place, and returns a subslice of the original slice.
- func LastUniqueStrings(list []string) []string {
- totalSkip := 0
- for i := len(list) - 1; i >= totalSkip; i-- {
- skip := 0
- for j := i - 1; j >= totalSkip; j-- {
- if list[i] == list[j] {
- skip++
- } else {
- list[j+skip] = list[j]
- }
- }
- totalSkip += skip
- }
- return list[totalSkip:]
- }
- // SortedUniqueStrings returns what the name says
- func SortedUniqueStrings(list []string) []string {
- // FirstUniqueStrings creates a copy of `list`, so the input remains untouched.
- unique := FirstUniqueStrings(list)
- sort.Strings(unique)
- return unique
- }
- // checkCalledFromInit panics if a Go package's init function is not on the
- // call stack.
- func checkCalledFromInit() {
- for skip := 3; ; skip++ {
- _, funcName, ok := callerName(skip)
- if !ok {
- panic("not called from an init func")
- }
- if funcName == "init" || strings.HasPrefix(funcName, "init·") ||
- strings.HasPrefix(funcName, "init.") {
- return
- }
- }
- }
- // A regex to find a package path within a function name. It finds the shortest string that is
- // followed by '.' and doesn't have any '/'s left.
- var pkgPathRe = regexp.MustCompile(`^(.*?)\.([^/]+)$`)
- // callerName returns the package path and function name of the calling
- // function. The skip argument has the same meaning as the skip argument of
- // runtime.Callers.
- func callerName(skip int) (pkgPath, funcName string, ok bool) {
- var pc [1]uintptr
- n := runtime.Callers(skip+1, pc[:])
- if n != 1 {
- return "", "", false
- }
- f := runtime.FuncForPC(pc[0]).Name()
- s := pkgPathRe.FindStringSubmatch(f)
- if len(s) < 3 {
- panic(fmt.Errorf("failed to extract package path and function name from %q", f))
- }
- return s[1], s[2], true
- }
- // GetNumericSdkVersion removes the first occurrence of system_ in a string,
- // which is assumed to be something like "system_1.2.3"
- func GetNumericSdkVersion(v string) string {
- return strings.Replace(v, "system_", "", 1)
- }
- // copied from build/kati/strutil.go
- func substPattern(pat, repl, str string) string {
- ps := strings.SplitN(pat, "%", 2)
- if len(ps) != 2 {
- if str == pat {
- return repl
- }
- return str
- }
- in := str
- trimmed := str
- if ps[0] != "" {
- trimmed = strings.TrimPrefix(in, ps[0])
- if trimmed == in {
- return str
- }
- }
- in = trimmed
- if ps[1] != "" {
- trimmed = strings.TrimSuffix(in, ps[1])
- if trimmed == in {
- return str
- }
- }
- rs := strings.SplitN(repl, "%", 2)
- if len(rs) != 2 {
- return repl
- }
- return rs[0] + trimmed + rs[1]
- }
- // copied from build/kati/strutil.go
- func matchPattern(pat, str string) bool {
- i := strings.IndexByte(pat, '%')
- if i < 0 {
- return pat == str
- }
- return strings.HasPrefix(str, pat[:i]) && strings.HasSuffix(str, pat[i+1:])
- }
- var shlibVersionPattern = regexp.MustCompile("(?:\\.\\d+(?:svn)?)+")
- // splitFileExt splits a file name into root, suffix and ext. root stands for the file name without
- // the file extension and the version number (e.g. "libexample"). suffix stands for the
- // concatenation of the file extension and the version number (e.g. ".so.1.0"). ext stands for the
- // file extension after the version numbers are trimmed (e.g. ".so").
- func SplitFileExt(name string) (string, string, string) {
- // Extract and trim the shared lib version number if the file name ends with dot digits.
- suffix := ""
- matches := shlibVersionPattern.FindAllStringIndex(name, -1)
- if len(matches) > 0 {
- lastMatch := matches[len(matches)-1]
- if lastMatch[1] == len(name) {
- suffix = name[lastMatch[0]:lastMatch[1]]
- name = name[0:lastMatch[0]]
- }
- }
- // Extract the file name root and the file extension.
- ext := filepath.Ext(name)
- root := strings.TrimSuffix(name, ext)
- suffix = ext + suffix
- return root, suffix, ext
- }
- // 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
- }
- // ShardString takes a string and returns a slice of strings where the length of each one is
- // at most shardSize.
- func ShardString(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
- }
- // 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
- }
- // CheckDuplicate checks if there are duplicates in given string list.
- // If there are, it returns first such duplicate and true.
- func CheckDuplicate(values []string) (duplicate string, found bool) {
- seen := make(map[string]string)
- for _, v := range values {
- if duplicate, found = seen[v]; found {
- return duplicate, true
- }
- seen[v] = v
- }
- return "", false
- }
|