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