1// Copyright 2017 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
15package android
16
17import (
18	"fmt"
19	"reflect"
20	"strconv"
21	"strings"
22	"testing"
23)
24
25var firstUniqueStringsTestCases = []struct {
26	in  []string
27	out []string
28}{
29	{
30		in:  []string{"a"},
31		out: []string{"a"},
32	},
33	{
34		in:  []string{"a", "b"},
35		out: []string{"a", "b"},
36	},
37	{
38		in:  []string{"a", "a"},
39		out: []string{"a"},
40	},
41	{
42		in:  []string{"a", "b", "a"},
43		out: []string{"a", "b"},
44	},
45	{
46		in:  []string{"b", "a", "a"},
47		out: []string{"b", "a"},
48	},
49	{
50		in:  []string{"a", "a", "b"},
51		out: []string{"a", "b"},
52	},
53	{
54		in:  []string{"a", "b", "a", "b"},
55		out: []string{"a", "b"},
56	},
57	{
58		in:  []string{"liblog", "libdl", "libc++", "libdl", "libc", "libm"},
59		out: []string{"liblog", "libdl", "libc++", "libc", "libm"},
60	},
61}
62
63func TestFirstUniqueStrings(t *testing.T) {
64	f := func(t *testing.T, imp func([]string) []string, in, want []string) {
65		t.Helper()
66		out := imp(in)
67		if !reflect.DeepEqual(out, want) {
68			t.Errorf("incorrect output:")
69			t.Errorf("     input: %#v", in)
70			t.Errorf("  expected: %#v", want)
71			t.Errorf("       got: %#v", out)
72		}
73	}
74
75	for _, testCase := range firstUniqueStringsTestCases {
76		t.Run("list", func(t *testing.T) {
77			f(t, firstUniqueStringsList, testCase.in, testCase.out)
78		})
79		t.Run("map", func(t *testing.T) {
80			f(t, firstUniqueStringsMap, testCase.in, testCase.out)
81		})
82	}
83}
84
85var lastUniqueStringsTestCases = []struct {
86	in  []string
87	out []string
88}{
89	{
90		in:  []string{"a"},
91		out: []string{"a"},
92	},
93	{
94		in:  []string{"a", "b"},
95		out: []string{"a", "b"},
96	},
97	{
98		in:  []string{"a", "a"},
99		out: []string{"a"},
100	},
101	{
102		in:  []string{"a", "b", "a"},
103		out: []string{"b", "a"},
104	},
105	{
106		in:  []string{"b", "a", "a"},
107		out: []string{"b", "a"},
108	},
109	{
110		in:  []string{"a", "a", "b"},
111		out: []string{"a", "b"},
112	},
113	{
114		in:  []string{"a", "b", "a", "b"},
115		out: []string{"a", "b"},
116	},
117	{
118		in:  []string{"liblog", "libdl", "libc++", "libdl", "libc", "libm"},
119		out: []string{"liblog", "libc++", "libdl", "libc", "libm"},
120	},
121}
122
123func TestLastUniqueStrings(t *testing.T) {
124	for _, testCase := range lastUniqueStringsTestCases {
125		out := LastUniqueStrings(testCase.in)
126		if !reflect.DeepEqual(out, testCase.out) {
127			t.Errorf("incorrect output:")
128			t.Errorf("     input: %#v", testCase.in)
129			t.Errorf("  expected: %#v", testCase.out)
130			t.Errorf("       got: %#v", out)
131		}
132	}
133}
134
135func TestJoinWithPrefix(t *testing.T) {
136	testcases := []struct {
137		name     string
138		input    []string
139		expected string
140	}{
141		{
142			name:     "zero_inputs",
143			input:    []string{},
144			expected: "",
145		},
146		{
147			name:     "one_input",
148			input:    []string{"a"},
149			expected: "prefix:a",
150		},
151		{
152			name:     "two_inputs",
153			input:    []string{"a", "b"},
154			expected: "prefix:a prefix:b",
155		},
156	}
157
158	prefix := "prefix:"
159
160	for _, testCase := range testcases {
161		t.Run(testCase.name, func(t *testing.T) {
162			out := JoinWithPrefix(testCase.input, prefix)
163			if out != testCase.expected {
164				t.Errorf("incorrect output:")
165				t.Errorf("     input: %#v", testCase.input)
166				t.Errorf("    prefix: %#v", prefix)
167				t.Errorf("  expected: %#v", testCase.expected)
168				t.Errorf("       got: %#v", out)
169			}
170		})
171	}
172}
173
174func TestIndexList(t *testing.T) {
175	input := []string{"a", "b", "c"}
176
177	testcases := []struct {
178		key      string
179		expected int
180	}{
181		{
182			key:      "a",
183			expected: 0,
184		},
185		{
186			key:      "b",
187			expected: 1,
188		},
189		{
190			key:      "c",
191			expected: 2,
192		},
193		{
194			key:      "X",
195			expected: -1,
196		},
197	}
198
199	for _, testCase := range testcases {
200		t.Run(testCase.key, func(t *testing.T) {
201			out := IndexList(testCase.key, input)
202			if out != testCase.expected {
203				t.Errorf("incorrect output:")
204				t.Errorf("       key: %#v", testCase.key)
205				t.Errorf("     input: %#v", input)
206				t.Errorf("  expected: %#v", testCase.expected)
207				t.Errorf("       got: %#v", out)
208			}
209		})
210	}
211}
212
213func TestInList(t *testing.T) {
214	input := []string{"a"}
215
216	testcases := []struct {
217		key      string
218		expected bool
219	}{
220		{
221			key:      "a",
222			expected: true,
223		},
224		{
225			key:      "X",
226			expected: false,
227		},
228	}
229
230	for _, testCase := range testcases {
231		t.Run(testCase.key, func(t *testing.T) {
232			out := InList(testCase.key, input)
233			if out != testCase.expected {
234				t.Errorf("incorrect output:")
235				t.Errorf("       key: %#v", testCase.key)
236				t.Errorf("     input: %#v", input)
237				t.Errorf("  expected: %#v", testCase.expected)
238				t.Errorf("       got: %#v", out)
239			}
240		})
241	}
242}
243
244func TestPrefixInList(t *testing.T) {
245	prefixes := []string{"a", "b"}
246
247	testcases := []struct {
248		str      string
249		expected bool
250	}{
251		{
252			str:      "a-example",
253			expected: true,
254		},
255		{
256			str:      "b-example",
257			expected: true,
258		},
259		{
260			str:      "X-example",
261			expected: false,
262		},
263	}
264
265	for _, testCase := range testcases {
266		t.Run(testCase.str, func(t *testing.T) {
267			out := HasAnyPrefix(testCase.str, prefixes)
268			if out != testCase.expected {
269				t.Errorf("incorrect output:")
270				t.Errorf("       str: %#v", testCase.str)
271				t.Errorf("  prefixes: %#v", prefixes)
272				t.Errorf("  expected: %#v", testCase.expected)
273				t.Errorf("       got: %#v", out)
274			}
275		})
276	}
277}
278
279func TestFilterList(t *testing.T) {
280	input := []string{"a", "b", "c", "c", "b", "d", "a"}
281	filter := []string{"a", "c"}
282	remainder, filtered := FilterList(input, filter)
283
284	expected := []string{"b", "b", "d"}
285	if !reflect.DeepEqual(remainder, expected) {
286		t.Errorf("incorrect remainder output:")
287		t.Errorf("     input: %#v", input)
288		t.Errorf("    filter: %#v", filter)
289		t.Errorf("  expected: %#v", expected)
290		t.Errorf("       got: %#v", remainder)
291	}
292
293	expected = []string{"a", "c", "c", "a"}
294	if !reflect.DeepEqual(filtered, expected) {
295		t.Errorf("incorrect filtered output:")
296		t.Errorf("     input: %#v", input)
297		t.Errorf("    filter: %#v", filter)
298		t.Errorf("  expected: %#v", expected)
299		t.Errorf("       got: %#v", filtered)
300	}
301}
302
303func TestFilterListPred(t *testing.T) {
304	pred := func(s string) bool { return strings.HasPrefix(s, "a/") }
305	AssertArrayString(t, "filter", FilterListPred([]string{"a/c", "b/a", "a/b"}, pred), []string{"a/c", "a/b"})
306	AssertArrayString(t, "filter", FilterListPred([]string{"b/c", "a/a", "b/b"}, pred), []string{"a/a"})
307	AssertArrayString(t, "filter", FilterListPred([]string{"c/c", "b/a", "c/b"}, pred), []string{})
308	AssertArrayString(t, "filter", FilterListPred([]string{"a/c", "a/a", "a/b"}, pred), []string{"a/c", "a/a", "a/b"})
309}
310
311func TestRemoveListFromList(t *testing.T) {
312	input := []string{"a", "b", "c", "d", "a", "c", "d"}
313	filter := []string{"a", "c"}
314	expected := []string{"b", "d", "d"}
315	out := RemoveListFromList(input, filter)
316	if !reflect.DeepEqual(out, expected) {
317		t.Errorf("incorrect output:")
318		t.Errorf("     input: %#v", input)
319		t.Errorf("    filter: %#v", filter)
320		t.Errorf("  expected: %#v", expected)
321		t.Errorf("       got: %#v", out)
322	}
323}
324
325func TestRemoveFromList(t *testing.T) {
326	testcases := []struct {
327		name          string
328		key           string
329		input         []string
330		expectedFound bool
331		expectedOut   []string
332	}{
333		{
334			name:          "remove_one_match",
335			key:           "a",
336			input:         []string{"a", "b", "c"},
337			expectedFound: true,
338			expectedOut:   []string{"b", "c"},
339		},
340		{
341			name:          "remove_three_matches",
342			key:           "a",
343			input:         []string{"a", "b", "a", "c", "a"},
344			expectedFound: true,
345			expectedOut:   []string{"b", "c"},
346		},
347		{
348			name:          "remove_zero_matches",
349			key:           "X",
350			input:         []string{"a", "b", "a", "c", "a"},
351			expectedFound: false,
352			expectedOut:   []string{"a", "b", "a", "c", "a"},
353		},
354		{
355			name:          "remove_all_matches",
356			key:           "a",
357			input:         []string{"a", "a", "a", "a"},
358			expectedFound: true,
359			expectedOut:   []string{},
360		},
361	}
362
363	for _, testCase := range testcases {
364		t.Run(testCase.name, func(t *testing.T) {
365			found, out := RemoveFromList(testCase.key, testCase.input)
366			if found != testCase.expectedFound {
367				t.Errorf("incorrect output:")
368				t.Errorf("       key: %#v", testCase.key)
369				t.Errorf("     input: %#v", testCase.input)
370				t.Errorf("  expected: %#v", testCase.expectedFound)
371				t.Errorf("       got: %#v", found)
372			}
373			if !reflect.DeepEqual(out, testCase.expectedOut) {
374				t.Errorf("incorrect output:")
375				t.Errorf("       key: %#v", testCase.key)
376				t.Errorf("     input: %#v", testCase.input)
377				t.Errorf("  expected: %#v", testCase.expectedOut)
378				t.Errorf("       got: %#v", out)
379			}
380		})
381	}
382}
383
384func ExampleCopyOf() {
385	a := []string{"1", "2", "3"}
386	b := CopyOf(a)
387	a[0] = "-1"
388	fmt.Printf("a = %q\n", a)
389	fmt.Printf("b = %q\n", b)
390
391	// Output:
392	// a = ["-1" "2" "3"]
393	// b = ["1" "2" "3"]
394}
395
396func ExampleCopyOf_append() {
397	a := make([]string, 1, 2)
398	a[0] = "foo"
399
400	fmt.Println("Without CopyOf:")
401	b := append(a, "bar")
402	c := append(a, "baz")
403	fmt.Printf("a = %q\n", a)
404	fmt.Printf("b = %q\n", b)
405	fmt.Printf("c = %q\n", c)
406
407	a = make([]string, 1, 2)
408	a[0] = "foo"
409
410	fmt.Println("With CopyOf:")
411	b = append(CopyOf(a), "bar")
412	c = append(CopyOf(a), "baz")
413	fmt.Printf("a = %q\n", a)
414	fmt.Printf("b = %q\n", b)
415	fmt.Printf("c = %q\n", c)
416
417	// Output:
418	// Without CopyOf:
419	// a = ["foo"]
420	// b = ["foo" "baz"]
421	// c = ["foo" "baz"]
422	// With CopyOf:
423	// a = ["foo"]
424	// b = ["foo" "bar"]
425	// c = ["foo" "baz"]
426}
427
428func TestSplitFileExt(t *testing.T) {
429	t.Run("soname with version", func(t *testing.T) {
430		root, suffix, ext := SplitFileExt("libtest.so.1.0.30")
431		expected := "libtest"
432		if root != expected {
433			t.Errorf("root should be %q but got %q", expected, root)
434		}
435		expected = ".so.1.0.30"
436		if suffix != expected {
437			t.Errorf("suffix should be %q but got %q", expected, suffix)
438		}
439		expected = ".so"
440		if ext != expected {
441			t.Errorf("ext should be %q but got %q", expected, ext)
442		}
443	})
444
445	t.Run("soname with svn version", func(t *testing.T) {
446		root, suffix, ext := SplitFileExt("libtest.so.1svn")
447		expected := "libtest"
448		if root != expected {
449			t.Errorf("root should be %q but got %q", expected, root)
450		}
451		expected = ".so.1svn"
452		if suffix != expected {
453			t.Errorf("suffix should be %q but got %q", expected, suffix)
454		}
455		expected = ".so"
456		if ext != expected {
457			t.Errorf("ext should be %q but got %q", expected, ext)
458		}
459	})
460
461	t.Run("version numbers in the middle should be ignored", func(t *testing.T) {
462		root, suffix, ext := SplitFileExt("libtest.1.0.30.so")
463		expected := "libtest.1.0.30"
464		if root != expected {
465			t.Errorf("root should be %q but got %q", expected, root)
466		}
467		expected = ".so"
468		if suffix != expected {
469			t.Errorf("suffix should be %q but got %q", expected, suffix)
470		}
471		expected = ".so"
472		if ext != expected {
473			t.Errorf("ext should be %q but got %q", expected, ext)
474		}
475	})
476
477	t.Run("no known file extension", func(t *testing.T) {
478		root, suffix, ext := SplitFileExt("test.exe")
479		expected := "test"
480		if root != expected {
481			t.Errorf("root should be %q but got %q", expected, root)
482		}
483		expected = ".exe"
484		if suffix != expected {
485			t.Errorf("suffix should be %q but got %q", expected, suffix)
486		}
487		if ext != expected {
488			t.Errorf("ext should be %q but got %q", expected, ext)
489		}
490	})
491}
492
493func Test_Shard(t *testing.T) {
494	type args struct {
495		strings   []string
496		shardSize int
497	}
498	tests := []struct {
499		name string
500		args args
501		want [][]string
502	}{
503		{
504			name: "empty",
505			args: args{
506				strings:   nil,
507				shardSize: 1,
508			},
509			want: [][]string(nil),
510		},
511		{
512			name: "single shard",
513			args: args{
514				strings:   []string{"a", "b"},
515				shardSize: 2,
516			},
517			want: [][]string{{"a", "b"}},
518		},
519		{
520			name: "single short shard",
521			args: args{
522				strings:   []string{"a", "b"},
523				shardSize: 3,
524			},
525			want: [][]string{{"a", "b"}},
526		},
527		{
528			name: "shard per input",
529			args: args{
530				strings:   []string{"a", "b", "c"},
531				shardSize: 1,
532			},
533			want: [][]string{{"a"}, {"b"}, {"c"}},
534		},
535		{
536			name: "balanced shards",
537			args: args{
538				strings:   []string{"a", "b", "c", "d"},
539				shardSize: 2,
540			},
541			want: [][]string{{"a", "b"}, {"c", "d"}},
542		},
543		{
544			name: "unbalanced shards",
545			args: args{
546				strings:   []string{"a", "b", "c"},
547				shardSize: 2,
548			},
549			want: [][]string{{"a", "b"}, {"c"}},
550		},
551	}
552	for _, tt := range tests {
553		t.Run(tt.name, func(t *testing.T) {
554			t.Run("strings", func(t *testing.T) {
555				if got := ShardStrings(tt.args.strings, tt.args.shardSize); !reflect.DeepEqual(got, tt.want) {
556					t.Errorf("ShardStrings(%v, %v) = %v, want %v",
557						tt.args.strings, tt.args.shardSize, got, tt.want)
558				}
559			})
560
561			t.Run("paths", func(t *testing.T) {
562				stringsToPaths := func(strings []string) Paths {
563					if strings == nil {
564						return nil
565					}
566					paths := make(Paths, len(strings))
567					for i, s := range strings {
568						paths[i] = PathForTesting(s)
569					}
570					return paths
571				}
572
573				paths := stringsToPaths(tt.args.strings)
574
575				var want []Paths
576				if sWant := tt.want; sWant != nil {
577					want = make([]Paths, len(sWant))
578					for i, w := range sWant {
579						want[i] = stringsToPaths(w)
580					}
581				}
582
583				if got := ShardPaths(paths, tt.args.shardSize); !reflect.DeepEqual(got, want) {
584					t.Errorf("ShardPaths(%v, %v) = %v, want %v",
585						paths, tt.args.shardSize, got, want)
586				}
587			})
588		})
589	}
590}
591
592func BenchmarkFirstUniqueStrings(b *testing.B) {
593	implementations := []struct {
594		name string
595		f    func([]string) []string
596	}{
597		{
598			name: "list",
599			f:    firstUniqueStringsList,
600		},
601		{
602			name: "map",
603			f:    firstUniqueStringsMap,
604		},
605		{
606			name: "optimal",
607			f:    FirstUniqueStrings,
608		},
609	}
610	const maxSize = 1024
611	uniqueStrings := make([]string, maxSize)
612	for i := range uniqueStrings {
613		uniqueStrings[i] = strconv.Itoa(i)
614	}
615	sameString := make([]string, maxSize)
616	for i := range sameString {
617		sameString[i] = uniqueStrings[0]
618	}
619
620	f := func(b *testing.B, imp func([]string) []string, s []string) {
621		for i := 0; i < b.N; i++ {
622			b.ReportAllocs()
623			s = append([]string(nil), s...)
624			imp(s)
625		}
626	}
627
628	for n := 1; n <= maxSize; n <<= 1 {
629		b.Run(strconv.Itoa(n), func(b *testing.B) {
630			for _, implementation := range implementations {
631				b.Run(implementation.name, func(b *testing.B) {
632					b.Run("same", func(b *testing.B) {
633						f(b, implementation.f, sameString[:n])
634					})
635					b.Run("unique", func(b *testing.B) {
636						f(b, implementation.f, uniqueStrings[:n])
637					})
638				})
639			}
640		})
641	}
642}
643