util.go 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569
  1. // Copyright 2015 Google Inc. All rights reserved.
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain a copy of the License at
  6. //
  7. // http://www.apache.org/licenses/LICENSE-2.0
  8. //
  9. // Unless required by applicable law or agreed to in writing, software
  10. // distributed under the License is distributed on an "AS IS" BASIS,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. package android
  15. import (
  16. "fmt"
  17. "path/filepath"
  18. "reflect"
  19. "regexp"
  20. "runtime"
  21. "sort"
  22. "strings"
  23. )
  24. // CopyOf returns a new slice that has the same contents as s.
  25. func CopyOf[T any](s []T) []T {
  26. // If the input is nil, return nil and not an empty list
  27. if s == nil {
  28. return s
  29. }
  30. return append([]T{}, s...)
  31. }
  32. // Concat returns a new slice concatenated from the two input slices. It does not change the input
  33. // slices.
  34. func Concat[T any](s1, s2 []T) []T {
  35. res := make([]T, 0, len(s1)+len(s2))
  36. res = append(res, s1...)
  37. res = append(res, s2...)
  38. return res
  39. }
  40. // JoinPathsWithPrefix converts the paths to strings, prefixes them
  41. // with prefix and then joins them separated by " ".
  42. func JoinPathsWithPrefix(paths []Path, prefix string) string {
  43. strs := make([]string, len(paths))
  44. for i := range paths {
  45. strs[i] = paths[i].String()
  46. }
  47. return JoinWithPrefixAndSeparator(strs, prefix, " ")
  48. }
  49. // JoinWithPrefix prepends the prefix to each string in the list and
  50. // returns them joined together with " " as separator.
  51. func JoinWithPrefix(strs []string, prefix string) string {
  52. return JoinWithPrefixAndSeparator(strs, prefix, " ")
  53. }
  54. // JoinWithPrefixAndSeparator prepends the prefix to each string in the list and
  55. // returns them joined together with the given separator.
  56. func JoinWithPrefixAndSeparator(strs []string, prefix string, sep string) string {
  57. if len(strs) == 0 {
  58. return ""
  59. }
  60. var buf strings.Builder
  61. buf.WriteString(prefix)
  62. buf.WriteString(strs[0])
  63. for i := 1; i < len(strs); i++ {
  64. buf.WriteString(sep)
  65. buf.WriteString(prefix)
  66. buf.WriteString(strs[i])
  67. }
  68. return buf.String()
  69. }
  70. // SortedStringKeys returns the keys of the given map in the ascending order.
  71. //
  72. // Deprecated: Use SortedKeys instead.
  73. func SortedStringKeys[V any](m map[string]V) []string {
  74. return SortedKeys(m)
  75. }
  76. type Ordered interface {
  77. ~string |
  78. ~float32 | ~float64 |
  79. ~int | ~int8 | ~int16 | ~int32 | ~int64 |
  80. ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
  81. }
  82. // SortedKeys returns the keys of the given map in the ascending order.
  83. func SortedKeys[T Ordered, V any](m map[T]V) []T {
  84. if len(m) == 0 {
  85. return nil
  86. }
  87. ret := make([]T, 0, len(m))
  88. for k := range m {
  89. ret = append(ret, k)
  90. }
  91. sort.Slice(ret, func(i, j int) bool {
  92. return ret[i] < ret[j]
  93. })
  94. return ret
  95. }
  96. // stringValues returns the values of the given string-valued map in randomized map order.
  97. func stringValues(m interface{}) []string {
  98. v := reflect.ValueOf(m)
  99. if v.Kind() != reflect.Map {
  100. panic(fmt.Sprintf("%#v is not a map", m))
  101. }
  102. if v.Len() == 0 {
  103. return nil
  104. }
  105. iter := v.MapRange()
  106. s := make([]string, 0, v.Len())
  107. for iter.Next() {
  108. s = append(s, iter.Value().String())
  109. }
  110. return s
  111. }
  112. // SortedStringValues returns the values of the given string-valued map in the ascending order.
  113. func SortedStringValues(m interface{}) []string {
  114. s := stringValues(m)
  115. sort.Strings(s)
  116. return s
  117. }
  118. // SortedUniqueStringValues returns the values of the given string-valued map in the ascending order
  119. // with duplicates removed.
  120. func SortedUniqueStringValues(m interface{}) []string {
  121. s := stringValues(m)
  122. return SortedUniqueStrings(s)
  123. }
  124. // IndexList returns the index of the first occurrence of the given string in the list or -1
  125. func IndexList(s string, list []string) int {
  126. for i, l := range list {
  127. if l == s {
  128. return i
  129. }
  130. }
  131. return -1
  132. }
  133. // InList checks if the string belongs to the list
  134. func InList(s string, list []string) bool {
  135. return IndexList(s, list) != -1
  136. }
  137. func setFromList[T comparable](l []T) map[T]bool {
  138. m := make(map[T]bool, len(l))
  139. for _, t := range l {
  140. m[t] = true
  141. }
  142. return m
  143. }
  144. // ListSetDifference checks if the two lists contain the same elements. It returns
  145. // a boolean which is true if there is a difference, and then returns lists of elements
  146. // that are in l1 but not l2, and l2 but not l1.
  147. func ListSetDifference[T comparable](l1, l2 []T) (bool, []T, []T) {
  148. listsDiffer := false
  149. diff1 := []T{}
  150. diff2 := []T{}
  151. m1 := setFromList(l1)
  152. m2 := setFromList(l2)
  153. for t := range m1 {
  154. if _, ok := m2[t]; !ok {
  155. diff1 = append(diff1, t)
  156. listsDiffer = true
  157. }
  158. }
  159. for t := range m2 {
  160. if _, ok := m1[t]; !ok {
  161. diff2 = append(diff2, t)
  162. listsDiffer = true
  163. }
  164. }
  165. return listsDiffer, diff1, diff2
  166. }
  167. // Returns true if the given string s is prefixed with any string in the given prefix list.
  168. func HasAnyPrefix(s string, prefixList []string) bool {
  169. for _, prefix := range prefixList {
  170. if strings.HasPrefix(s, prefix) {
  171. return true
  172. }
  173. }
  174. return false
  175. }
  176. // Returns true if any string in the given list has the given substring.
  177. func SubstringInList(list []string, substr string) bool {
  178. for _, s := range list {
  179. if strings.Contains(s, substr) {
  180. return true
  181. }
  182. }
  183. return false
  184. }
  185. // Returns true if any string in the given list has the given prefix.
  186. func PrefixInList(list []string, prefix string) bool {
  187. for _, s := range list {
  188. if strings.HasPrefix(s, prefix) {
  189. return true
  190. }
  191. }
  192. return false
  193. }
  194. // Returns true if any string in the given list has the given suffix.
  195. func SuffixInList(list []string, suffix string) bool {
  196. for _, s := range list {
  197. if strings.HasSuffix(s, suffix) {
  198. return true
  199. }
  200. }
  201. return false
  202. }
  203. // IndexListPred returns the index of the element which in the given `list` satisfying the predicate, or -1 if there is no such element.
  204. func IndexListPred(pred func(s string) bool, list []string) int {
  205. for i, l := range list {
  206. if pred(l) {
  207. return i
  208. }
  209. }
  210. return -1
  211. }
  212. // FilterList divides the string list into two lists: one with the strings belonging
  213. // to the given filter list, and the other with the remaining ones
  214. func FilterList(list []string, filter []string) (remainder []string, filtered []string) {
  215. // InList is O(n). May be worth using more efficient lookup for longer lists.
  216. for _, l := range list {
  217. if InList(l, filter) {
  218. filtered = append(filtered, l)
  219. } else {
  220. remainder = append(remainder, l)
  221. }
  222. }
  223. return
  224. }
  225. // FilterListPred returns the elements of the given list for which the predicate
  226. // returns true. Order is kept.
  227. func FilterListPred(list []string, pred func(s string) bool) (filtered []string) {
  228. for _, l := range list {
  229. if pred(l) {
  230. filtered = append(filtered, l)
  231. }
  232. }
  233. return
  234. }
  235. // RemoveListFromList removes the strings belonging to the filter list from the
  236. // given list and returns the result
  237. func RemoveListFromList(list []string, filter_out []string) (result []string) {
  238. result = make([]string, 0, len(list))
  239. for _, l := range list {
  240. if !InList(l, filter_out) {
  241. result = append(result, l)
  242. }
  243. }
  244. return
  245. }
  246. // RemoveFromList removes given string from the string list.
  247. func RemoveFromList(s string, list []string) (bool, []string) {
  248. result := make([]string, 0, len(list))
  249. var removed bool
  250. for _, item := range list {
  251. if item != s {
  252. result = append(result, item)
  253. } else {
  254. removed = true
  255. }
  256. }
  257. return removed, result
  258. }
  259. // FirstUniqueStrings returns all unique elements of a slice of strings, keeping the first copy of
  260. // each. It does not modify the input slice.
  261. func FirstUniqueStrings(list []string) []string {
  262. return firstUnique(list)
  263. }
  264. // firstUnique returns all unique elements of a slice, keeping the first copy of each. It
  265. // does not modify the input slice.
  266. func firstUnique[T comparable](slice []T) []T {
  267. // Do not modify the input in-place, operate on a copy instead.
  268. slice = CopyOf(slice)
  269. return firstUniqueInPlace(slice)
  270. }
  271. // firstUniqueInPlace returns all unique elements of a slice, keeping the first copy of
  272. // each. It modifies the slice contents in place, and returns a subslice of the original
  273. // slice.
  274. func firstUniqueInPlace[T comparable](slice []T) []T {
  275. // 128 was chosen based on BenchmarkFirstUniqueStrings results.
  276. if len(slice) > 128 {
  277. return firstUniqueMap(slice)
  278. }
  279. return firstUniqueList(slice)
  280. }
  281. // firstUniqueList is an implementation of firstUnique using an O(N^2) list comparison to look for
  282. // duplicates.
  283. func firstUniqueList[T any](in []T) []T {
  284. writeIndex := 0
  285. outer:
  286. for readIndex := 0; readIndex < len(in); readIndex++ {
  287. for compareIndex := 0; compareIndex < writeIndex; compareIndex++ {
  288. if interface{}(in[readIndex]) == interface{}(in[compareIndex]) {
  289. // The value at readIndex already exists somewhere in the output region
  290. // of the slice before writeIndex, skip it.
  291. continue outer
  292. }
  293. }
  294. if readIndex != writeIndex {
  295. in[writeIndex] = in[readIndex]
  296. }
  297. writeIndex++
  298. }
  299. return in[0:writeIndex]
  300. }
  301. // firstUniqueMap is an implementation of firstUnique using an O(N) hash set lookup to look for
  302. // duplicates.
  303. func firstUniqueMap[T comparable](in []T) []T {
  304. writeIndex := 0
  305. seen := make(map[T]bool, len(in))
  306. for readIndex := 0; readIndex < len(in); readIndex++ {
  307. if _, exists := seen[in[readIndex]]; exists {
  308. continue
  309. }
  310. seen[in[readIndex]] = true
  311. if readIndex != writeIndex {
  312. in[writeIndex] = in[readIndex]
  313. }
  314. writeIndex++
  315. }
  316. return in[0:writeIndex]
  317. }
  318. // reverseSliceInPlace reverses the elements of a slice in place.
  319. func reverseSliceInPlace[T any](in []T) {
  320. for i, j := 0, len(in)-1; i < j; i, j = i+1, j-1 {
  321. in[i], in[j] = in[j], in[i]
  322. }
  323. }
  324. // reverseSlice returns a copy of a slice in reverse order.
  325. func reverseSlice[T any](in []T) []T {
  326. out := make([]T, len(in))
  327. for i := 0; i < len(in); i++ {
  328. out[i] = in[len(in)-1-i]
  329. }
  330. return out
  331. }
  332. // LastUniqueStrings returns all unique elements of a slice of strings, keeping the last copy of
  333. // each. It modifies the slice contents in place, and returns a subslice of the original slice.
  334. func LastUniqueStrings(list []string) []string {
  335. totalSkip := 0
  336. for i := len(list) - 1; i >= totalSkip; i-- {
  337. skip := 0
  338. for j := i - 1; j >= totalSkip; j-- {
  339. if list[i] == list[j] {
  340. skip++
  341. } else {
  342. list[j+skip] = list[j]
  343. }
  344. }
  345. totalSkip += skip
  346. }
  347. return list[totalSkip:]
  348. }
  349. // SortedUniqueStrings returns what the name says
  350. func SortedUniqueStrings(list []string) []string {
  351. // FirstUniqueStrings creates a copy of `list`, so the input remains untouched.
  352. unique := FirstUniqueStrings(list)
  353. sort.Strings(unique)
  354. return unique
  355. }
  356. // checkCalledFromInit panics if a Go package's init function is not on the
  357. // call stack.
  358. func checkCalledFromInit() {
  359. for skip := 3; ; skip++ {
  360. _, funcName, ok := callerName(skip)
  361. if !ok {
  362. panic("not called from an init func")
  363. }
  364. if funcName == "init" || strings.HasPrefix(funcName, "init·") ||
  365. strings.HasPrefix(funcName, "init.") {
  366. return
  367. }
  368. }
  369. }
  370. // A regex to find a package path within a function name. It finds the shortest string that is
  371. // followed by '.' and doesn't have any '/'s left.
  372. var pkgPathRe = regexp.MustCompile(`^(.*?)\.([^/]+)$`)
  373. // callerName returns the package path and function name of the calling
  374. // function. The skip argument has the same meaning as the skip argument of
  375. // runtime.Callers.
  376. func callerName(skip int) (pkgPath, funcName string, ok bool) {
  377. var pc [1]uintptr
  378. n := runtime.Callers(skip+1, pc[:])
  379. if n != 1 {
  380. return "", "", false
  381. }
  382. f := runtime.FuncForPC(pc[0]).Name()
  383. s := pkgPathRe.FindStringSubmatch(f)
  384. if len(s) < 3 {
  385. panic(fmt.Errorf("failed to extract package path and function name from %q", f))
  386. }
  387. return s[1], s[2], true
  388. }
  389. // GetNumericSdkVersion removes the first occurrence of system_ in a string,
  390. // which is assumed to be something like "system_1.2.3"
  391. func GetNumericSdkVersion(v string) string {
  392. return strings.Replace(v, "system_", "", 1)
  393. }
  394. // copied from build/kati/strutil.go
  395. func substPattern(pat, repl, str string) string {
  396. ps := strings.SplitN(pat, "%", 2)
  397. if len(ps) != 2 {
  398. if str == pat {
  399. return repl
  400. }
  401. return str
  402. }
  403. in := str
  404. trimmed := str
  405. if ps[0] != "" {
  406. trimmed = strings.TrimPrefix(in, ps[0])
  407. if trimmed == in {
  408. return str
  409. }
  410. }
  411. in = trimmed
  412. if ps[1] != "" {
  413. trimmed = strings.TrimSuffix(in, ps[1])
  414. if trimmed == in {
  415. return str
  416. }
  417. }
  418. rs := strings.SplitN(repl, "%", 2)
  419. if len(rs) != 2 {
  420. return repl
  421. }
  422. return rs[0] + trimmed + rs[1]
  423. }
  424. // copied from build/kati/strutil.go
  425. func matchPattern(pat, str string) bool {
  426. i := strings.IndexByte(pat, '%')
  427. if i < 0 {
  428. return pat == str
  429. }
  430. return strings.HasPrefix(str, pat[:i]) && strings.HasSuffix(str, pat[i+1:])
  431. }
  432. var shlibVersionPattern = regexp.MustCompile("(?:\\.\\d+(?:svn)?)+")
  433. // splitFileExt splits a file name into root, suffix and ext. root stands for the file name without
  434. // the file extension and the version number (e.g. "libexample"). suffix stands for the
  435. // concatenation of the file extension and the version number (e.g. ".so.1.0"). ext stands for the
  436. // file extension after the version numbers are trimmed (e.g. ".so").
  437. func SplitFileExt(name string) (string, string, string) {
  438. // Extract and trim the shared lib version number if the file name ends with dot digits.
  439. suffix := ""
  440. matches := shlibVersionPattern.FindAllStringIndex(name, -1)
  441. if len(matches) > 0 {
  442. lastMatch := matches[len(matches)-1]
  443. if lastMatch[1] == len(name) {
  444. suffix = name[lastMatch[0]:lastMatch[1]]
  445. name = name[0:lastMatch[0]]
  446. }
  447. }
  448. // Extract the file name root and the file extension.
  449. ext := filepath.Ext(name)
  450. root := strings.TrimSuffix(name, ext)
  451. suffix = ext + suffix
  452. return root, suffix, ext
  453. }
  454. // ShardPaths takes a Paths, and returns a slice of Paths where each one has at most shardSize paths.
  455. func ShardPaths(paths Paths, shardSize int) []Paths {
  456. if len(paths) == 0 {
  457. return nil
  458. }
  459. ret := make([]Paths, 0, (len(paths)+shardSize-1)/shardSize)
  460. for len(paths) > shardSize {
  461. ret = append(ret, paths[0:shardSize])
  462. paths = paths[shardSize:]
  463. }
  464. if len(paths) > 0 {
  465. ret = append(ret, paths)
  466. }
  467. return ret
  468. }
  469. // ShardString takes a string and returns a slice of strings where the length of each one is
  470. // at most shardSize.
  471. func ShardString(s string, shardSize int) []string {
  472. if len(s) == 0 {
  473. return nil
  474. }
  475. ret := make([]string, 0, (len(s)+shardSize-1)/shardSize)
  476. for len(s) > shardSize {
  477. ret = append(ret, s[0:shardSize])
  478. s = s[shardSize:]
  479. }
  480. if len(s) > 0 {
  481. ret = append(ret, s)
  482. }
  483. return ret
  484. }
  485. // ShardStrings takes a slice of strings, and returns a slice of slices of strings where each one has at most shardSize
  486. // elements.
  487. func ShardStrings(s []string, shardSize int) [][]string {
  488. if len(s) == 0 {
  489. return nil
  490. }
  491. ret := make([][]string, 0, (len(s)+shardSize-1)/shardSize)
  492. for len(s) > shardSize {
  493. ret = append(ret, s[0:shardSize])
  494. s = s[shardSize:]
  495. }
  496. if len(s) > 0 {
  497. ret = append(ret, s)
  498. }
  499. return ret
  500. }
  501. // CheckDuplicate checks if there are duplicates in given string list.
  502. // If there are, it returns first such duplicate and true.
  503. func CheckDuplicate(values []string) (duplicate string, found bool) {
  504. seen := make(map[string]string)
  505. for _, v := range values {
  506. if duplicate, found = seen[v]; found {
  507. return duplicate, true
  508. }
  509. seen[v] = v
  510. }
  511. return "", false
  512. }