// 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 (
 "bufio"
 "cmp"
 "errors"
 "fmt"
 "os"
 "path/filepath"
 "reflect"
 "regexp"
 "runtime"
 "sort"
 "strings"

 "github.com/google/blueprint/proptools"
)

// 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 {
 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()
}

// SortedKeys returns the keys of the given map in the ascending order.
func SortedKeys[T cmp.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[T comparable](t T, list []T) int {
 for i, l := range list {
  if l == t {
   return i
  }
 }
 return -1
}

func InList[T comparable](t T, list []T) bool {
 return IndexList(t, 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
}

// PrettyConcat returns the formatted concatenated string suitable for displaying user-facing
// messages.
func PrettyConcat(list []string, quote bool, lastSep string) string {
 if len(list) == 0 {
  return ""
 }

 quoteStr := func(v string) string {
  if !quote {
   return v
  }
  return fmt.Sprintf("%q", v)
 }

 if len(list) == 1 {
  return quoteStr(list[0])
 }

 var sb strings.Builder
 for i, val := range list {
  if i > 0 {
   sb.WriteString(", ")
  }
  if i == len(list)-1 {
   sb.WriteString(lastSep)
   if lastSep != "" {
    sb.WriteString(" ")
   }
  }
  sb.WriteString(quoteStr(val))
 }

 return sb.String()
}

// 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 unique 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
 l1 = FirstUnique(l1)
 l2 = FirstUnique(l2)
 diff1 := []T{}
 diff2 := []T{}
 m1 := setFromList(l1)
 m2 := setFromList(l2)
 for _, t := range l1 {
  if _, ok := m2[t]; !ok {
   diff1 = append(diff1, t)
   listsDiffer = true
  }
 }
 for _, t := range l2 {
  if _, ok := m1[t]; !ok {
   diff2 = append(diff2, t)
   listsDiffer = true
  }
 }
 return listsDiffer, diff1, diff2
}

// Returns true if the two lists have common elements.
func HasIntersection[T comparable](l1, l2 []T) bool {
 m1 := setFromList(l1)
 for _, x := range l2 {
  if _, ok := m1[x]; ok {
   return true
  }
 }
 return false
}

// 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
}

// FilterListByPrefixes performs the same splitting as FilterList does, but treats the passed
// filters as prefixes
func FilterListByPrefix(list []string, filter []string) (remainder []string, filtered []string) {
 for _, l := range list {
  if HasAnyPrefix(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
}

// 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 eq(list[i], list[j]) {
    continue outer
   }
  }
  list[k] = list[i]
  k++
 }
 return list[:k]
}

// 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 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
// 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 {
 return proptools.ShardBySize(paths, shardSize)
}

// 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 {
 return proptools.ShardBySize(s, shardSize)
}

// 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
}

func AddToStringSet(set map[string]bool, items []string) {
 for _, item := range items {
  set[item] = true
 }
}

// AppendIfNotZero append the given value to the slice if it is not the zero value
// for its type.
func AppendIfNotZero[T comparable](slice []T, value T) []T {
 var zeroValue T // Get the zero value of the type T
 if value != zeroValue {
  return append(slice, value)
 }
 return slice
}

type bufferedStringWriterCloser struct {
 *bufio.Writer
 f *os.File
}

func (b bufferedStringWriterCloser) Close() error {
 flushErr := b.Writer.Flush()
 closeErr := b.f.Close()
 return errors.Join(flushErr, closeErr)
}

func openBufferedFile(path string) (*bufferedStringWriterCloser, error) {
 f, err := os.OpenFile(path, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0666)
 if err != nil {
  return nil, err
 }
 buf := bufio.NewWriterSize(f, 16*1024*1024)
 return &bufferedStringWriterCloser{
  Writer: buf,
  f:      f,
 }, nil
}