// Copyright 2017 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 (
	"cmp"
	"fmt"
	"reflect"
	"strconv"
	"strings"
	"testing"
	"unsafe"
)

var firstUniqueStringsTestCases = []struct {
	in  []string
	out []string
}{
	{
		in:  []string{"a"},
		out: []string{"a"},
	},
	{
		in:  []string{"a", "b"},
		out: []string{"a", "b"},
	},
	{
		in:  []string{"a", "a"},
		out: []string{"a"},
	},
	{
		in:  []string{"a", "b", "a"},
		out: []string{"a", "b"},
	},
	{
		in:  []string{"b", "a", "a"},
		out: []string{"b", "a"},
	},
	{
		in:  []string{"a", "a", "b"},
		out: []string{"a", "b"},
	},
	{
		in:  []string{"a", "b", "a", "b"},
		out: []string{"a", "b"},
	},
	{
		in:  []string{"liblog", "libdl", "libc++", "libdl", "libc", "libm"},
		out: []string{"liblog", "libdl", "libc++", "libc", "libm"},
	},
}

func TestFirstUniqueStrings(t *testing.T) {
	f := func(t *testing.T, imp func([]string) []string, in, want []string) {
		t.Helper()
		out := imp(in)
		if !reflect.DeepEqual(out, want) {
			t.Errorf("incorrect output:")
			t.Errorf("     input: %#v", in)
			t.Errorf("  expected: %#v", want)
			t.Errorf("       got: %#v", out)
		}
	}

	for _, testCase := range firstUniqueStringsTestCases {
		t.Run("list", func(t *testing.T) {
			f(t, firstUniqueList[string], testCase.in, testCase.out)
		})
		t.Run("map", func(t *testing.T) {
			f(t, firstUniqueMap[string], testCase.in, testCase.out)
		})
	}
}

var lastUniqueStringsTestCases = []struct {
	in  []string
	out []string
}{
	{
		in:  []string{"a"},
		out: []string{"a"},
	},
	{
		in:  []string{"a", "b"},
		out: []string{"a", "b"},
	},
	{
		in:  []string{"a", "a"},
		out: []string{"a"},
	},
	{
		in:  []string{"a", "b", "a"},
		out: []string{"b", "a"},
	},
	{
		in:  []string{"b", "a", "a"},
		out: []string{"b", "a"},
	},
	{
		in:  []string{"a", "a", "b"},
		out: []string{"a", "b"},
	},
	{
		in:  []string{"a", "b", "a", "b"},
		out: []string{"a", "b"},
	},
	{
		in:  []string{"liblog", "libdl", "libc++", "libdl", "libc", "libm"},
		out: []string{"liblog", "libc++", "libdl", "libc", "libm"},
	},
}

func TestLastUniqueStrings(t *testing.T) {
	for _, testCase := range lastUniqueStringsTestCases {
		out := LastUniqueStrings(testCase.in)
		if !reflect.DeepEqual(out, testCase.out) {
			t.Errorf("incorrect output:")
			t.Errorf("     input: %#v", testCase.in)
			t.Errorf("  expected: %#v", testCase.out)
			t.Errorf("       got: %#v", out)
		}
	}
}

func TestJoinWithPrefix(t *testing.T) {
	testcases := []struct {
		name     string
		input    []string
		expected string
	}{
		{
			name:     "zero_inputs",
			input:    []string{},
			expected: "",
		},
		{
			name:     "one_input",
			input:    []string{"a"},
			expected: "prefix:a",
		},
		{
			name:     "two_inputs",
			input:    []string{"a", "b"},
			expected: "prefix:a prefix:b",
		},
	}

	prefix := "prefix:"

	for _, testCase := range testcases {
		t.Run(testCase.name, func(t *testing.T) {
			out := JoinWithPrefix(testCase.input, prefix)
			if out != testCase.expected {
				t.Errorf("incorrect output:")
				t.Errorf("     input: %#v", testCase.input)
				t.Errorf("    prefix: %#v", prefix)
				t.Errorf("  expected: %#v", testCase.expected)
				t.Errorf("       got: %#v", out)
			}
		})
	}
}

func TestIndexList(t *testing.T) {
	input := []string{"a", "b", "c"}

	testcases := []struct {
		key      string
		expected int
	}{
		{
			key:      "a",
			expected: 0,
		},
		{
			key:      "b",
			expected: 1,
		},
		{
			key:      "c",
			expected: 2,
		},
		{
			key:      "X",
			expected: -1,
		},
	}

	for _, testCase := range testcases {
		t.Run(testCase.key, func(t *testing.T) {
			out := IndexList(testCase.key, input)
			if out != testCase.expected {
				t.Errorf("incorrect output:")
				t.Errorf("       key: %#v", testCase.key)
				t.Errorf("     input: %#v", input)
				t.Errorf("  expected: %#v", testCase.expected)
				t.Errorf("       got: %#v", out)
			}
		})
	}
}

func TestInList(t *testing.T) {
	input := []string{"a"}

	testcases := []struct {
		key      string
		expected bool
	}{
		{
			key:      "a",
			expected: true,
		},
		{
			key:      "X",
			expected: false,
		},
	}

	for _, testCase := range testcases {
		t.Run(testCase.key, func(t *testing.T) {
			out := InList(testCase.key, input)
			if out != testCase.expected {
				t.Errorf("incorrect output:")
				t.Errorf("       key: %#v", testCase.key)
				t.Errorf("     input: %#v", input)
				t.Errorf("  expected: %#v", testCase.expected)
				t.Errorf("       got: %#v", out)
			}
		})
	}
}

func TestPrefixInList(t *testing.T) {
	prefixes := []string{"a", "b"}

	testcases := []struct {
		str      string
		expected bool
	}{
		{
			str:      "a-example",
			expected: true,
		},
		{
			str:      "b-example",
			expected: true,
		},
		{
			str:      "X-example",
			expected: false,
		},
	}

	for _, testCase := range testcases {
		t.Run(testCase.str, func(t *testing.T) {
			out := HasAnyPrefix(testCase.str, prefixes)
			if out != testCase.expected {
				t.Errorf("incorrect output:")
				t.Errorf("       str: %#v", testCase.str)
				t.Errorf("  prefixes: %#v", prefixes)
				t.Errorf("  expected: %#v", testCase.expected)
				t.Errorf("       got: %#v", out)
			}
		})
	}
}

func TestFilterList(t *testing.T) {
	input := []string{"a", "b", "c", "c", "b", "d", "a"}
	filter := []string{"a", "c"}
	remainder, filtered := FilterList(input, filter)

	expected := []string{"b", "b", "d"}
	if !reflect.DeepEqual(remainder, expected) {
		t.Errorf("incorrect remainder output:")
		t.Errorf("     input: %#v", input)
		t.Errorf("    filter: %#v", filter)
		t.Errorf("  expected: %#v", expected)
		t.Errorf("       got: %#v", remainder)
	}

	expected = []string{"a", "c", "c", "a"}
	if !reflect.DeepEqual(filtered, expected) {
		t.Errorf("incorrect filtered output:")
		t.Errorf("     input: %#v", input)
		t.Errorf("    filter: %#v", filter)
		t.Errorf("  expected: %#v", expected)
		t.Errorf("       got: %#v", filtered)
	}
}

func TestFilterListPred(t *testing.T) {
	pred := func(s string) bool { return strings.HasPrefix(s, "a/") }
	AssertArrayString(t, "filter", FilterListPred([]string{"a/c", "b/a", "a/b"}, pred), []string{"a/c", "a/b"})
	AssertArrayString(t, "filter", FilterListPred([]string{"b/c", "a/a", "b/b"}, pred), []string{"a/a"})
	AssertArrayString(t, "filter", FilterListPred([]string{"c/c", "b/a", "c/b"}, pred), []string{})
	AssertArrayString(t, "filter", FilterListPred([]string{"a/c", "a/a", "a/b"}, pred), []string{"a/c", "a/a", "a/b"})
}

func TestRemoveListFromList(t *testing.T) {
	input := []string{"a", "b", "c", "d", "a", "c", "d"}
	filter := []string{"a", "c"}
	expected := []string{"b", "d", "d"}
	out := RemoveListFromList(input, filter)
	if !reflect.DeepEqual(out, expected) {
		t.Errorf("incorrect output:")
		t.Errorf("     input: %#v", input)
		t.Errorf("    filter: %#v", filter)
		t.Errorf("  expected: %#v", expected)
		t.Errorf("       got: %#v", out)
	}
}

func TestRemoveFromList(t *testing.T) {
	testcases := []struct {
		name          string
		key           string
		input         []string
		expectedFound bool
		expectedOut   []string
	}{
		{
			name:          "remove_one_match",
			key:           "a",
			input:         []string{"a", "b", "c"},
			expectedFound: true,
			expectedOut:   []string{"b", "c"},
		},
		{
			name:          "remove_three_matches",
			key:           "a",
			input:         []string{"a", "b", "a", "c", "a"},
			expectedFound: true,
			expectedOut:   []string{"b", "c"},
		},
		{
			name:          "remove_zero_matches",
			key:           "X",
			input:         []string{"a", "b", "a", "c", "a"},
			expectedFound: false,
			expectedOut:   []string{"a", "b", "a", "c", "a"},
		},
		{
			name:          "remove_all_matches",
			key:           "a",
			input:         []string{"a", "a", "a", "a"},
			expectedFound: true,
			expectedOut:   []string{},
		},
	}

	for _, testCase := range testcases {
		t.Run(testCase.name, func(t *testing.T) {
			found, out := RemoveFromList(testCase.key, testCase.input)
			if found != testCase.expectedFound {
				t.Errorf("incorrect output:")
				t.Errorf("       key: %#v", testCase.key)
				t.Errorf("     input: %#v", testCase.input)
				t.Errorf("  expected: %#v", testCase.expectedFound)
				t.Errorf("       got: %#v", found)
			}
			if !reflect.DeepEqual(out, testCase.expectedOut) {
				t.Errorf("incorrect output:")
				t.Errorf("       key: %#v", testCase.key)
				t.Errorf("     input: %#v", testCase.input)
				t.Errorf("  expected: %#v", testCase.expectedOut)
				t.Errorf("       got: %#v", out)
			}
		})
	}
}

func TestCopyOfEmptyAndNil(t *testing.T) {
	emptyList := []string{}
	copyOfEmptyList := CopyOf(emptyList)
	AssertBoolEquals(t, "Copy of an empty list should be an empty list and not nil", true, copyOfEmptyList != nil)
	copyOfNilList := CopyOf([]string(nil))
	AssertBoolEquals(t, "Copy of a nil list should be a nil list and not an empty list", true, copyOfNilList == nil)
}

func ExampleCopyOf() {
	a := []string{"1", "2", "3"}
	b := CopyOf(a)
	a[0] = "-1"
	fmt.Printf("a = %q\n", a)
	fmt.Printf("b = %q\n", b)

	// Output:
	// a = ["-1" "2" "3"]
	// b = ["1" "2" "3"]
}

func ExampleCopyOf_append() {
	a := make([]string, 1, 2)
	a[0] = "foo"

	fmt.Println("Without CopyOf:")
	b := append(a, "bar")
	c := append(a, "baz")
	fmt.Printf("a = %q\n", a)
	fmt.Printf("b = %q\n", b)
	fmt.Printf("c = %q\n", c)

	a = make([]string, 1, 2)
	a[0] = "foo"

	fmt.Println("With CopyOf:")
	b = append(CopyOf(a), "bar")
	c = append(CopyOf(a), "baz")
	fmt.Printf("a = %q\n", a)
	fmt.Printf("b = %q\n", b)
	fmt.Printf("c = %q\n", c)

	// Output:
	// Without CopyOf:
	// a = ["foo"]
	// b = ["foo" "baz"]
	// c = ["foo" "baz"]
	// With CopyOf:
	// a = ["foo"]
	// b = ["foo" "bar"]
	// c = ["foo" "baz"]
}

func TestSplitFileExt(t *testing.T) {
	t.Run("soname with version", func(t *testing.T) {
		root, suffix, ext := SplitFileExt("libtest.so.1.0.30")
		expected := "libtest"
		if root != expected {
			t.Errorf("root should be %q but got %q", expected, root)
		}
		expected = ".so.1.0.30"
		if suffix != expected {
			t.Errorf("suffix should be %q but got %q", expected, suffix)
		}
		expected = ".so"
		if ext != expected {
			t.Errorf("ext should be %q but got %q", expected, ext)
		}
	})

	t.Run("soname with svn version", func(t *testing.T) {
		root, suffix, ext := SplitFileExt("libtest.so.1svn")
		expected := "libtest"
		if root != expected {
			t.Errorf("root should be %q but got %q", expected, root)
		}
		expected = ".so.1svn"
		if suffix != expected {
			t.Errorf("suffix should be %q but got %q", expected, suffix)
		}
		expected = ".so"
		if ext != expected {
			t.Errorf("ext should be %q but got %q", expected, ext)
		}
	})

	t.Run("version numbers in the middle should be ignored", func(t *testing.T) {
		root, suffix, ext := SplitFileExt("libtest.1.0.30.so")
		expected := "libtest.1.0.30"
		if root != expected {
			t.Errorf("root should be %q but got %q", expected, root)
		}
		expected = ".so"
		if suffix != expected {
			t.Errorf("suffix should be %q but got %q", expected, suffix)
		}
		expected = ".so"
		if ext != expected {
			t.Errorf("ext should be %q but got %q", expected, ext)
		}
	})

	t.Run("no known file extension", func(t *testing.T) {
		root, suffix, ext := SplitFileExt("test.exe")
		expected := "test"
		if root != expected {
			t.Errorf("root should be %q but got %q", expected, root)
		}
		expected = ".exe"
		if suffix != expected {
			t.Errorf("suffix should be %q but got %q", expected, suffix)
		}
		if ext != expected {
			t.Errorf("ext should be %q but got %q", expected, ext)
		}
	})
}

func Test_Shard(t *testing.T) {
	type args struct {
		strings   []string
		shardSize int
	}
	tests := []struct {
		name string
		args args
		want [][]string
	}{
		{
			name: "empty",
			args: args{
				strings:   nil,
				shardSize: 1,
			},
			want: [][]string(nil),
		},
		{
			name: "single shard",
			args: args{
				strings:   []string{"a", "b"},
				shardSize: 2,
			},
			want: [][]string{{"a", "b"}},
		},
		{
			name: "single short shard",
			args: args{
				strings:   []string{"a", "b"},
				shardSize: 3,
			},
			want: [][]string{{"a", "b"}},
		},
		{
			name: "shard per input",
			args: args{
				strings:   []string{"a", "b", "c"},
				shardSize: 1,
			},
			want: [][]string{{"a"}, {"b"}, {"c"}},
		},
		{
			name: "balanced shards",
			args: args{
				strings:   []string{"a", "b", "c", "d"},
				shardSize: 2,
			},
			want: [][]string{{"a", "b"}, {"c", "d"}},
		},
		{
			name: "unbalanced shards",
			args: args{
				strings:   []string{"a", "b", "c"},
				shardSize: 2,
			},
			want: [][]string{{"a", "b"}, {"c"}},
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			t.Run("strings", func(t *testing.T) {
				if got := ShardStrings(tt.args.strings, tt.args.shardSize); !reflect.DeepEqual(got, tt.want) {
					t.Errorf("ShardStrings(%v, %v) = %v, want %v",
						tt.args.strings, tt.args.shardSize, got, tt.want)
				}
			})

			t.Run("paths", func(t *testing.T) {
				stringsToPaths := func(strings []string) Paths {
					if strings == nil {
						return nil
					}
					paths := make(Paths, len(strings))
					for i, s := range strings {
						paths[i] = PathForTesting(s)
					}
					return paths
				}

				paths := stringsToPaths(tt.args.strings)

				var want []Paths
				if sWant := tt.want; sWant != nil {
					want = make([]Paths, len(sWant))
					for i, w := range sWant {
						want[i] = stringsToPaths(w)
					}
				}

				if got := ShardPaths(paths, tt.args.shardSize); !reflect.DeepEqual(got, want) {
					t.Errorf("ShardPaths(%v, %v) = %v, want %v",
						paths, tt.args.shardSize, got, want)
				}
			})
		})
	}
}

func BenchmarkFirstUniqueStrings(b *testing.B) {
	implementations := []struct {
		name string
		f    func([]string) []string
	}{
		{
			name: "list",
			f:    firstUniqueList[string],
		},
		{
			name: "map",
			f:    firstUniqueMap[string],
		},
		{
			name: "optimal",
			f:    FirstUniqueStrings,
		},
	}
	const maxSize = 1024
	uniqueStrings := make([]string, maxSize)
	for i := range uniqueStrings {
		uniqueStrings[i] = strconv.Itoa(i)
	}
	sameString := make([]string, maxSize)
	for i := range sameString {
		sameString[i] = uniqueStrings[0]
	}

	f := func(b *testing.B, imp func([]string) []string, s []string) {
		for i := 0; i < b.N; i++ {
			b.ReportAllocs()
			s = append([]string(nil), s...)
			imp(s)
		}
	}

	for n := 1; n <= maxSize; n <<= 1 {
		b.Run(strconv.Itoa(n), func(b *testing.B) {
			for _, implementation := range implementations {
				b.Run(implementation.name, func(b *testing.B) {
					b.Run("same", func(b *testing.B) {
						f(b, implementation.f, sameString[:n])
					})
					b.Run("unique", func(b *testing.B) {
						f(b, implementation.f, uniqueStrings[:n])
					})
				})
			}
		})
	}
}

func testSortedKeysHelper[K cmp.Ordered, V any](t *testing.T, name string, input map[K]V, expected []K) {
	t.Helper()
	t.Run(name, func(t *testing.T) {
		actual := SortedKeys(input)
		if !reflect.DeepEqual(actual, expected) {
			t.Errorf("expected %v, got %v", expected, actual)
		}
	})
}

func TestSortedKeys(t *testing.T) {
	testSortedKeysHelper(t, "simple", map[string]string{
		"b": "bar",
		"a": "foo",
	}, []string{
		"a",
		"b",
	})
	testSortedKeysHelper(t, "ints", map[int]interface{}{
		10: nil,
		5:  nil,
	}, []int{
		5,
		10,
	})

	testSortedKeysHelper(t, "nil", map[string]string(nil), nil)
	testSortedKeysHelper(t, "empty", map[string]string{}, nil)
}

func TestSortedStringValues(t *testing.T) {
	testCases := []struct {
		name     string
		in       interface{}
		expected []string
	}{
		{
			name:     "nil",
			in:       map[string]string(nil),
			expected: nil,
		},
		{
			name:     "empty",
			in:       map[string]string{},
			expected: nil,
		},
		{
			name:     "simple",
			in:       map[string]string{"foo": "a", "bar": "b"},
			expected: []string{"a", "b"},
		},
		{
			name:     "duplicates",
			in:       map[string]string{"foo": "a", "bar": "b", "baz": "b"},
			expected: []string{"a", "b", "b"},
		},
	}

	for _, tt := range testCases {
		t.Run(tt.name, func(t *testing.T) {
			got := SortedStringValues(tt.in)
			if g, w := got, tt.expected; !reflect.DeepEqual(g, w) {
				t.Errorf("wanted %q, got %q", w, g)
			}
		})
	}
}

func TestSortedUniqueStringValues(t *testing.T) {
	testCases := []struct {
		name     string
		in       interface{}
		expected []string
	}{
		{
			name:     "nil",
			in:       map[string]string(nil),
			expected: nil,
		},
		{
			name:     "empty",
			in:       map[string]string{},
			expected: nil,
		},
		{
			name:     "simple",
			in:       map[string]string{"foo": "a", "bar": "b"},
			expected: []string{"a", "b"},
		},
		{
			name:     "duplicates",
			in:       map[string]string{"foo": "a", "bar": "b", "baz": "b"},
			expected: []string{"a", "b"},
		},
	}

	for _, tt := range testCases {
		t.Run(tt.name, func(t *testing.T) {
			got := SortedUniqueStringValues(tt.in)
			if g, w := got, tt.expected; !reflect.DeepEqual(g, w) {
				t.Errorf("wanted %q, got %q", w, g)
			}
		})
	}
}

var reverseTestCases = []struct {
	name     string
	in       []string
	expected []string
}{
	{
		name:     "nil",
		in:       nil,
		expected: nil,
	},
	{
		name:     "empty",
		in:       []string{},
		expected: []string{},
	},
	{
		name:     "one",
		in:       []string{"one"},
		expected: []string{"one"},
	},
	{
		name:     "even",
		in:       []string{"one", "two"},
		expected: []string{"two", "one"},
	},
	{
		name:     "odd",
		in:       []string{"one", "two", "three"},
		expected: []string{"three", "two", "one"},
	},
}

func TestReverseSliceInPlace(t *testing.T) {
	for _, testCase := range reverseTestCases {
		t.Run(testCase.name, func(t *testing.T) {
			slice := CopyOf(testCase.in)
			slice2 := slice
			ReverseSliceInPlace(slice)
			if !reflect.DeepEqual(slice, testCase.expected) {
				t.Errorf("expected %#v, got %#v", testCase.expected, slice)
			}
			if unsafe.SliceData(slice) != unsafe.SliceData(slice2) {
				t.Errorf("expected slices to share backing array")
			}
		})
	}
}

func TestReverseSlice(t *testing.T) {
	for _, testCase := range reverseTestCases {
		t.Run(testCase.name, func(t *testing.T) {
			slice := ReverseSlice(testCase.in)
			if !reflect.DeepEqual(slice, testCase.expected) {
				t.Errorf("expected %#v, got %#v", testCase.expected, slice)
			}
			if cap(slice) > 0 && unsafe.SliceData(testCase.in) == unsafe.SliceData(slice) {
				t.Errorf("expected slices to have different backing arrays")
			}
		})
	}
}

var hasIntersectionTestCases = []struct {
	name     string
	l1       []string
	l2       []string
	expected bool
}{
	{
		name:     "empty",
		l1:       []string{"a", "b", "c"},
		l2:       []string{},
		expected: false,
	},
	{
		name:     "both empty",
		l1:       []string{},
		l2:       []string{},
		expected: false,
	},
	{
		name:     "identical",
		l1:       []string{"a", "b", "c"},
		l2:       []string{"a", "b", "c"},
		expected: true,
	},
	{
		name:     "duplicates",
		l1:       []string{"a", "a", "a"},
		l2:       []string{"a", "b", "c"},
		expected: true,
	},
	{
		name:     "duplicates with no intersection",
		l1:       []string{"d", "d", "d", "d"},
		l2:       []string{"a", "b", "c"},
		expected: false,
	},
}

func TestHasIntersection(t *testing.T) {
	for _, testCase := range hasIntersectionTestCases {
		t.Run(testCase.name, func(t *testing.T) {
			hasIntersection := HasIntersection(testCase.l1, testCase.l2)
			if !reflect.DeepEqual(hasIntersection, testCase.expected) {
				t.Errorf("expected %#v, got %#v", testCase.expected, hasIntersection)
			}
		})
	}
}

var prettyConcatTestCases = []struct {
	name          string
	list          []string
	quote         bool
	lastSeparator string
	expected      string
}{
	{
		name:          "empty",
		list:          []string{},
		quote:         false,
		lastSeparator: "and",
		expected:      ``,
	},
	{
		name:          "single",
		list:          []string{"a"},
		quote:         true,
		lastSeparator: "and",
		expected:      `"a"`,
	},
	{
		name:          "with separator",
		list:          []string{"a", "b", "c"},
		quote:         true,
		lastSeparator: "or",
		expected:      `"a", "b", or "c"`,
	},
	{
		name:          "without separator",
		list:          []string{"a", "b", "c"},
		quote:         false,
		lastSeparator: "",
		expected:      `a, b, c`,
	},
}

func TestPrettyConcat(t *testing.T) {
	for _, testCase := range prettyConcatTestCases {
		t.Run(testCase.name, func(t *testing.T) {
			concatString := PrettyConcat(testCase.list, testCase.quote, testCase.lastSeparator)
			if !reflect.DeepEqual(concatString, testCase.expected) {
				t.Errorf("expected %#v, got %#v", testCase.expected, concatString)
			}
		})
	}
}