You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
643 lines
15 KiB
643 lines
15 KiB
// 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 (
|
|
"fmt"
|
|
"reflect"
|
|
"strconv"
|
|
"strings"
|
|
"testing"
|
|
)
|
|
|
|
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, firstUniqueStringsList, testCase.in, testCase.out)
|
|
})
|
|
t.Run("map", func(t *testing.T) {
|
|
f(t, firstUniqueStringsMap, 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 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: firstUniqueStringsList,
|
|
},
|
|
{
|
|
name: "map",
|
|
f: firstUniqueStringsMap,
|
|
},
|
|
{
|
|
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])
|
|
})
|
|
})
|
|
}
|
|
})
|
|
}
|
|
}
|