blob: a0f716047b0b5fe1b99d2beaba1e117df8fb55d2 [file] [log] [blame]
Colin Crossc0b06f12015-04-08 13:03:43 -07001// 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
Colin Cross635c3b02016-05-18 15:37:25 -070015package android
Colin Crossc0b06f12015-04-08 13:03:43 -070016
Dan Willemsenb1957a52016-06-23 23:44:54 -070017import (
Colin Cross3020fee2019-03-19 15:05:17 -070018 "fmt"
Ivan Lozano022a73b2019-09-09 20:29:31 -070019 "path/filepath"
Inseob Kim1a365c62019-06-08 15:47:51 +090020 "reflect"
Colin Cross3020fee2019-03-19 15:05:17 -070021 "regexp"
Dan Willemsenb1957a52016-06-23 23:44:54 -070022 "runtime"
23 "sort"
24 "strings"
25)
Colin Cross1f8c52b2015-06-16 16:38:17 -070026
Colin Cross454c0872019-02-15 23:03:34 -080027// CopyOf returns a new slice that has the same contents as s.
28func CopyOf(s []string) []string {
29 return append([]string(nil), s...)
30}
31
Sasha Smundak1e533922020-11-19 16:48:18 -080032// JoinWithPrefix prepends the prefix to each string in the list and
33// returns them joined together with " " as separator.
Colin Crossc0b06f12015-04-08 13:03:43 -070034func JoinWithPrefix(strs []string, prefix string) string {
Yu Liu8d82ac52022-05-17 15:13:28 -070035 return JoinWithPrefixAndSeparator(strs, prefix, " ")
36}
37
38// JoinWithPrefixAndSeparator prepends the prefix to each string in the list and
39// returns them joined together with the given separator.
40func JoinWithPrefixAndSeparator(strs []string, prefix string, sep string) string {
Colin Crossc0b06f12015-04-08 13:03:43 -070041 if len(strs) == 0 {
42 return ""
43 }
44
Sasha Smundak1e533922020-11-19 16:48:18 -080045 var buf strings.Builder
46 buf.WriteString(prefix)
47 buf.WriteString(strs[0])
48 for i := 1; i < len(strs); i++ {
Yu Liu8d82ac52022-05-17 15:13:28 -070049 buf.WriteString(sep)
Sasha Smundak1e533922020-11-19 16:48:18 -080050 buf.WriteString(prefix)
51 buf.WriteString(strs[i])
Colin Crossc0b06f12015-04-08 13:03:43 -070052 }
Sasha Smundak1e533922020-11-19 16:48:18 -080053 return buf.String()
Colin Crossc0b06f12015-04-08 13:03:43 -070054}
Colin Cross9b6826f2015-04-10 15:47:33 -070055
Sasha Smundak1e533922020-11-19 16:48:18 -080056// JoinWithSuffix appends the suffix to each string in the list and
57// returns them joined together with given separator.
Inseob Kim1f086e22019-05-09 13:29:15 +090058func JoinWithSuffix(strs []string, suffix string, separator string) string {
59 if len(strs) == 0 {
60 return ""
61 }
62
Sasha Smundak1e533922020-11-19 16:48:18 -080063 var buf strings.Builder
64 buf.WriteString(strs[0])
65 buf.WriteString(suffix)
66 for i := 1; i < len(strs); i++ {
67 buf.WriteString(separator)
68 buf.WriteString(strs[i])
69 buf.WriteString(suffix)
Inseob Kim1f086e22019-05-09 13:29:15 +090070 }
Sasha Smundak1e533922020-11-19 16:48:18 -080071 return buf.String()
Inseob Kim1f086e22019-05-09 13:29:15 +090072}
73
Colin Cross9eb853b2022-02-17 11:13:37 -080074// SorterStringKeys returns the keys of the given string-keyed map in the ascending order.
Inseob Kim1a365c62019-06-08 15:47:51 +090075func SortedStringKeys(m interface{}) []string {
76 v := reflect.ValueOf(m)
77 if v.Kind() != reflect.Map {
78 panic(fmt.Sprintf("%#v is not a map", m))
79 }
Colin Cross9eb853b2022-02-17 11:13:37 -080080 if v.Len() == 0 {
81 return nil
82 }
83 iter := v.MapRange()
84 s := make([]string, 0, v.Len())
85 for iter.Next() {
86 s = append(s, iter.Key().String())
Colin Cross1f8c52b2015-06-16 16:38:17 -070087 }
88 sort.Strings(s)
89 return s
90}
Dan Willemsenb1957a52016-06-23 23:44:54 -070091
Colin Cross9eb853b2022-02-17 11:13:37 -080092// stringValues returns the values of the given string-valued map in randomized map order.
93func stringValues(m interface{}) []string {
94 v := reflect.ValueOf(m)
95 if v.Kind() != reflect.Map {
96 panic(fmt.Sprintf("%#v is not a map", m))
97 }
98 if v.Len() == 0 {
99 return nil
100 }
101 iter := v.MapRange()
102 s := make([]string, 0, v.Len())
103 for iter.Next() {
104 s = append(s, iter.Value().String())
105 }
106 return s
107}
108
109// SortedStringValues returns the values of the given string-valued map in the ascending order.
110func SortedStringValues(m interface{}) []string {
111 s := stringValues(m)
112 sort.Strings(s)
113 return s
114}
115
116// SortedUniqueStringValues returns the values of the given string-valued map in the ascending order
117// with duplicates removed.
118func SortedUniqueStringValues(m interface{}) []string {
119 s := stringValues(m)
120 return SortedUniqueStrings(s)
121}
122
Sasha Smundak1e533922020-11-19 16:48:18 -0800123// IndexList returns the index of the first occurrence of the given string in the list or -1
Colin Crossb4330e22017-12-22 15:47:09 -0800124func IndexList(s string, list []string) int {
Dan Willemsenb1957a52016-06-23 23:44:54 -0700125 for i, l := range list {
126 if l == s {
127 return i
128 }
129 }
130
131 return -1
132}
133
Sasha Smundak1e533922020-11-19 16:48:18 -0800134// InList checks if the string belongs to the list
Colin Crossb4330e22017-12-22 15:47:09 -0800135func InList(s string, list []string) bool {
136 return IndexList(s, list) != -1
Dan Willemsenb1957a52016-06-23 23:44:54 -0700137}
138
Jaewoong Jung6431ca72020-01-15 14:15:10 -0800139// Returns true if the given string s is prefixed with any string in the given prefix list.
Jaewoong Jung3aff5782020-02-11 07:54:35 -0800140func HasAnyPrefix(s string, prefixList []string) bool {
Jaewoong Jung6431ca72020-01-15 14:15:10 -0800141 for _, prefix := range prefixList {
142 if strings.HasPrefix(s, prefix) {
143 return true
144 }
145 }
146 return false
147}
148
Chih-Hung Hsieh9f94c362021-02-10 21:56:03 -0800149// Returns true if any string in the given list has the given substring.
150func SubstringInList(list []string, substr string) bool {
151 for _, s := range list {
152 if strings.Contains(s, substr) {
153 return true
154 }
155 }
156 return false
157}
158
Jaewoong Jung6431ca72020-01-15 14:15:10 -0800159// Returns true if any string in the given list has the given prefix.
Jaewoong Jung3aff5782020-02-11 07:54:35 -0800160func PrefixInList(list []string, prefix string) bool {
Jaewoong Jung6431ca72020-01-15 14:15:10 -0800161 for _, s := range list {
Ivan Lozano5f595532017-07-13 14:46:05 -0700162 if strings.HasPrefix(s, prefix) {
163 return true
164 }
165 }
166 return false
167}
168
Ivan Lozanoa0cd8f92020-04-09 09:56:02 -0400169// Returns true if any string in the given list has the given suffix.
170func SuffixInList(list []string, suffix string) bool {
171 for _, s := range list {
172 if strings.HasSuffix(s, suffix) {
173 return true
174 }
175 }
176 return false
177}
178
Jooyung Han12df5fb2019-07-11 16:18:47 +0900179// IndexListPred returns the index of the element which in the given `list` satisfying the predicate, or -1 if there is no such element.
180func IndexListPred(pred func(s string) bool, list []string) int {
181 for i, l := range list {
182 if pred(l) {
183 return i
184 }
185 }
186
187 return -1
188}
189
Sasha Smundak1e533922020-11-19 16:48:18 -0800190// FilterList divides the string list into two lists: one with the strings belonging
191// to the given filter list, and the other with the remaining ones
Colin Crossb4330e22017-12-22 15:47:09 -0800192func FilterList(list []string, filter []string) (remainder []string, filtered []string) {
Sasha Smundak1e533922020-11-19 16:48:18 -0800193 // InList is O(n). May be worth using more efficient lookup for longer lists.
Colin Crossb4330e22017-12-22 15:47:09 -0800194 for _, l := range list {
195 if InList(l, filter) {
196 filtered = append(filtered, l)
197 } else {
198 remainder = append(remainder, l)
199 }
200 }
201
202 return
203}
204
Martin Stjernholm1461c4d2021-03-27 19:04:05 +0000205// FilterListPred returns the elements of the given list for which the predicate
206// returns true. Order is kept.
207func FilterListPred(list []string, pred func(s string) bool) (filtered []string) {
208 for _, l := range list {
209 if pred(l) {
210 filtered = append(filtered, l)
211 }
212 }
213 return
214}
215
Sasha Smundak1e533922020-11-19 16:48:18 -0800216// RemoveListFromList removes the strings belonging to the filter list from the
217// given list and returns the result
Colin Crossb4330e22017-12-22 15:47:09 -0800218func RemoveListFromList(list []string, filter_out []string) (result []string) {
219 result = make([]string, 0, len(list))
220 for _, l := range list {
221 if !InList(l, filter_out) {
222 result = append(result, l)
223 }
224 }
225 return
226}
227
Sasha Smundak1e533922020-11-19 16:48:18 -0800228// RemoveFromList removes given string from the string list.
Colin Crossb4330e22017-12-22 15:47:09 -0800229func RemoveFromList(s string, list []string) (bool, []string) {
Sasha Smundak1e533922020-11-19 16:48:18 -0800230 result := make([]string, 0, len(list))
231 var removed bool
232 for _, item := range list {
233 if item != s {
234 result = append(result, item)
235 } else {
236 removed = true
Logan Chien7922ab82018-03-06 18:29:27 +0800237 }
238 }
Sasha Smundak1e533922020-11-19 16:48:18 -0800239 return removed, result
Colin Crossb4330e22017-12-22 15:47:09 -0800240}
241
Colin Crossb6715442017-10-24 11:13:31 -0700242// FirstUniqueStrings returns all unique elements of a slice of strings, keeping the first copy of
243// each. It modifies the slice contents in place, and returns a subslice of the original slice.
244func FirstUniqueStrings(list []string) []string {
Colin Cross27027c72020-02-28 15:34:17 -0800245 // 128 was chosen based on BenchmarkFirstUniqueStrings results.
246 if len(list) > 128 {
247 return firstUniqueStringsMap(list)
248 }
249 return firstUniqueStringsList(list)
250}
251
252func firstUniqueStringsList(list []string) []string {
Colin Crossb6715442017-10-24 11:13:31 -0700253 k := 0
254outer:
255 for i := 0; i < len(list); i++ {
256 for j := 0; j < k; j++ {
257 if list[i] == list[j] {
258 continue outer
259 }
260 }
261 list[k] = list[i]
262 k++
263 }
264 return list[:k]
265}
266
Colin Cross27027c72020-02-28 15:34:17 -0800267func firstUniqueStringsMap(list []string) []string {
268 k := 0
269 seen := make(map[string]bool, len(list))
270 for i := 0; i < len(list); i++ {
271 if seen[list[i]] {
272 continue
273 }
274 seen[list[i]] = true
275 list[k] = list[i]
276 k++
277 }
278 return list[:k]
279}
280
Colin Crossb6715442017-10-24 11:13:31 -0700281// LastUniqueStrings returns all unique elements of a slice of strings, keeping the last copy of
282// each. It modifies the slice contents in place, and returns a subslice of the original slice.
283func LastUniqueStrings(list []string) []string {
284 totalSkip := 0
285 for i := len(list) - 1; i >= totalSkip; i-- {
286 skip := 0
287 for j := i - 1; j >= totalSkip; j-- {
288 if list[i] == list[j] {
289 skip++
290 } else {
291 list[j+skip] = list[j]
292 }
293 }
294 totalSkip += skip
295 }
296 return list[totalSkip:]
297}
298
Jooyung Hane1633032019-08-01 17:41:43 +0900299// SortedUniqueStrings returns what the name says
300func SortedUniqueStrings(list []string) []string {
301 unique := FirstUniqueStrings(list)
302 sort.Strings(unique)
303 return unique
304}
305
Dan Willemsenb1957a52016-06-23 23:44:54 -0700306// checkCalledFromInit panics if a Go package's init function is not on the
307// call stack.
308func checkCalledFromInit() {
309 for skip := 3; ; skip++ {
310 _, funcName, ok := callerName(skip)
311 if !ok {
312 panic("not called from an init func")
313 }
314
Colin Cross3020fee2019-03-19 15:05:17 -0700315 if funcName == "init" || strings.HasPrefix(funcName, "init·") ||
316 strings.HasPrefix(funcName, "init.") {
Dan Willemsenb1957a52016-06-23 23:44:54 -0700317 return
318 }
319 }
320}
321
Colin Cross3020fee2019-03-19 15:05:17 -0700322// A regex to find a package path within a function name. It finds the shortest string that is
323// followed by '.' and doesn't have any '/'s left.
324var pkgPathRe = regexp.MustCompile(`^(.*?)\.([^/]+)$`)
325
Dan Willemsenb1957a52016-06-23 23:44:54 -0700326// callerName returns the package path and function name of the calling
327// function. The skip argument has the same meaning as the skip argument of
328// runtime.Callers.
329func callerName(skip int) (pkgPath, funcName string, ok bool) {
330 var pc [1]uintptr
331 n := runtime.Callers(skip+1, pc[:])
332 if n != 1 {
333 return "", "", false
334 }
335
Colin Cross3020fee2019-03-19 15:05:17 -0700336 f := runtime.FuncForPC(pc[0]).Name()
337 s := pkgPathRe.FindStringSubmatch(f)
338 if len(s) < 3 {
339 panic(fmt.Errorf("failed to extract package path and function name from %q", f))
Dan Willemsenb1957a52016-06-23 23:44:54 -0700340 }
341
Colin Cross3020fee2019-03-19 15:05:17 -0700342 return s[1], s[2], true
Dan Willemsenb1957a52016-06-23 23:44:54 -0700343}
Sundong Ahn0926fae2017-10-17 16:34:51 +0900344
Sasha Smundak1e533922020-11-19 16:48:18 -0800345// GetNumericSdkVersion removes the first occurrence of system_ in a string,
346// which is assumed to be something like "system_1.2.3"
Sundong Ahn0926fae2017-10-17 16:34:51 +0900347func GetNumericSdkVersion(v string) string {
Sasha Smundak1e533922020-11-19 16:48:18 -0800348 return strings.Replace(v, "system_", "", 1)
Sundong Ahn0926fae2017-10-17 16:34:51 +0900349}
Jiyong Park7f67f482019-01-05 12:57:48 +0900350
351// copied from build/kati/strutil.go
352func substPattern(pat, repl, str string) string {
353 ps := strings.SplitN(pat, "%", 2)
354 if len(ps) != 2 {
355 if str == pat {
356 return repl
357 }
358 return str
359 }
360 in := str
Sasha Smundak1e533922020-11-19 16:48:18 -0800361 trimmed := str
Jiyong Park7f67f482019-01-05 12:57:48 +0900362 if ps[0] != "" {
Sasha Smundak1e533922020-11-19 16:48:18 -0800363 trimmed = strings.TrimPrefix(in, ps[0])
364 if trimmed == in {
Jiyong Park7f67f482019-01-05 12:57:48 +0900365 return str
366 }
367 }
Sasha Smundak1e533922020-11-19 16:48:18 -0800368 in = trimmed
Jiyong Park7f67f482019-01-05 12:57:48 +0900369 if ps[1] != "" {
Sasha Smundak1e533922020-11-19 16:48:18 -0800370 trimmed = strings.TrimSuffix(in, ps[1])
371 if trimmed == in {
Jiyong Park7f67f482019-01-05 12:57:48 +0900372 return str
373 }
374 }
375
376 rs := strings.SplitN(repl, "%", 2)
377 if len(rs) != 2 {
378 return repl
379 }
Sasha Smundak1e533922020-11-19 16:48:18 -0800380 return rs[0] + trimmed + rs[1]
Jiyong Park7f67f482019-01-05 12:57:48 +0900381}
382
383// copied from build/kati/strutil.go
384func matchPattern(pat, str string) bool {
385 i := strings.IndexByte(pat, '%')
386 if i < 0 {
387 return pat == str
388 }
389 return strings.HasPrefix(str, pat[:i]) && strings.HasSuffix(str, pat[i+1:])
390}
Ivan Lozano022a73b2019-09-09 20:29:31 -0700391
392var shlibVersionPattern = regexp.MustCompile("(?:\\.\\d+(?:svn)?)+")
393
394// splitFileExt splits a file name into root, suffix and ext. root stands for the file name without
395// the file extension and the version number (e.g. "libexample"). suffix stands for the
396// concatenation of the file extension and the version number (e.g. ".so.1.0"). ext stands for the
397// file extension after the version numbers are trimmed (e.g. ".so").
398func SplitFileExt(name string) (string, string, string) {
399 // Extract and trim the shared lib version number if the file name ends with dot digits.
400 suffix := ""
401 matches := shlibVersionPattern.FindAllStringIndex(name, -1)
402 if len(matches) > 0 {
403 lastMatch := matches[len(matches)-1]
404 if lastMatch[1] == len(name) {
405 suffix = name[lastMatch[0]:lastMatch[1]]
406 name = name[0:lastMatch[0]]
407 }
408 }
409
410 // Extract the file name root and the file extension.
411 ext := filepath.Ext(name)
412 root := strings.TrimSuffix(name, ext)
413 suffix = ext + suffix
414
415 return root, suffix, ext
416}
Colin Cross0a2f7192019-09-23 14:33:09 -0700417
418// ShardPaths takes a Paths, and returns a slice of Paths where each one has at most shardSize paths.
419func ShardPaths(paths Paths, shardSize int) []Paths {
420 if len(paths) == 0 {
421 return nil
422 }
423 ret := make([]Paths, 0, (len(paths)+shardSize-1)/shardSize)
424 for len(paths) > shardSize {
425 ret = append(ret, paths[0:shardSize])
426 paths = paths[shardSize:]
427 }
428 if len(paths) > 0 {
429 ret = append(ret, paths)
430 }
431 return ret
432}
433
Hans MÃ¥nssond3f2bd72020-11-27 12:37:28 +0100434// ShardString takes a string and returns a slice of strings where the length of each one is
435// at most shardSize.
436func ShardString(s string, shardSize int) []string {
437 if len(s) == 0 {
438 return nil
439 }
440 ret := make([]string, 0, (len(s)+shardSize-1)/shardSize)
441 for len(s) > shardSize {
442 ret = append(ret, s[0:shardSize])
443 s = s[shardSize:]
444 }
445 if len(s) > 0 {
446 ret = append(ret, s)
447 }
448 return ret
449}
450
Colin Cross0a2f7192019-09-23 14:33:09 -0700451// ShardStrings takes a slice of strings, and returns a slice of slices of strings where each one has at most shardSize
452// elements.
453func ShardStrings(s []string, shardSize int) [][]string {
454 if len(s) == 0 {
455 return nil
456 }
457 ret := make([][]string, 0, (len(s)+shardSize-1)/shardSize)
458 for len(s) > shardSize {
459 ret = append(ret, s[0:shardSize])
460 s = s[shardSize:]
461 }
462 if len(s) > 0 {
463 ret = append(ret, s)
464 }
465 return ret
466}
Chih-Hung Hsieha5f22ed2019-10-24 20:47:54 -0700467
Sasha Smundak1e533922020-11-19 16:48:18 -0800468// CheckDuplicate checks if there are duplicates in given string list.
469// If there are, it returns first such duplicate and true.
Chih-Hung Hsieha5f22ed2019-10-24 20:47:54 -0700470func CheckDuplicate(values []string) (duplicate string, found bool) {
471 seen := make(map[string]string)
472 for _, v := range values {
473 if duplicate, found = seen[v]; found {
Sasha Smundak1e533922020-11-19 16:48:18 -0800474 return duplicate, true
Chih-Hung Hsieha5f22ed2019-10-24 20:47:54 -0700475 }
476 seen[v] = v
477 }
Sasha Smundak1e533922020-11-19 16:48:18 -0800478 return "", false
Chih-Hung Hsieha5f22ed2019-10-24 20:47:54 -0700479}