1// Copyright 2020 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
25func ExampleDepSet_ToList_postordered() {
26	a := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("a")).Build()
27	b := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build()
28	c := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build()
29	d := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
30
31	fmt.Println(d.ToList().Strings())
32	// Output: [a b c d]
33}
34
35func ExampleDepSet_ToList_preordered() {
36	a := NewDepSetBuilder(PREORDER).Direct(PathForTesting("a")).Build()
37	b := NewDepSetBuilder(PREORDER).Direct(PathForTesting("b")).Transitive(a).Build()
38	c := NewDepSetBuilder(PREORDER).Direct(PathForTesting("c")).Transitive(a).Build()
39	d := NewDepSetBuilder(PREORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
40
41	fmt.Println(d.ToList().Strings())
42	// Output: [d b a c]
43}
44
45func ExampleDepSet_ToList_topological() {
46	a := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("a")).Build()
47	b := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("b")).Transitive(a).Build()
48	c := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("c")).Transitive(a).Build()
49	d := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("d")).Transitive(b, c).Build()
50
51	fmt.Println(d.ToList().Strings())
52	// Output: [d b c a]
53}
54
55func ExampleDepSet_ToSortedList() {
56	a := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("a")).Build()
57	b := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build()
58	c := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build()
59	d := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
60
61	fmt.Println(d.ToSortedList().Strings())
62	// Output: [a b c d]
63}
64
65// Tests based on Bazel's ExpanderTestBase.java to ensure compatibility
66// https://github.com/bazelbuild/bazel/blob/master/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java
67func TestDepSet(t *testing.T) {
68	a := PathForTesting("a")
69	b := PathForTesting("b")
70	c := PathForTesting("c")
71	c2 := PathForTesting("c2")
72	d := PathForTesting("d")
73	e := PathForTesting("e")
74
75	tests := []struct {
76		name                             string
77		depSet                           func(t *testing.T, order DepSetOrder) *DepSet
78		postorder, preorder, topological []string
79	}{
80		{
81			name: "simple",
82			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
83				return NewDepSet(order, Paths{c, a, b}, nil)
84			},
85			postorder:   []string{"c", "a", "b"},
86			preorder:    []string{"c", "a", "b"},
87			topological: []string{"c", "a", "b"},
88		},
89		{
90			name: "simpleNoDuplicates",
91			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
92				return NewDepSet(order, Paths{c, a, a, a, b}, nil)
93			},
94			postorder:   []string{"c", "a", "b"},
95			preorder:    []string{"c", "a", "b"},
96			topological: []string{"c", "a", "b"},
97		},
98		{
99			name: "nesting",
100			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
101				subset := NewDepSet(order, Paths{c, a, e}, nil)
102				return NewDepSet(order, Paths{b, d}, []*DepSet{subset})
103			},
104			postorder:   []string{"c", "a", "e", "b", "d"},
105			preorder:    []string{"b", "d", "c", "a", "e"},
106			topological: []string{"b", "d", "c", "a", "e"},
107		},
108		{
109			name: "builderReuse",
110			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
111				assertEquals := func(t *testing.T, w, g Paths) {
112					t.Helper()
113					if !reflect.DeepEqual(w, g) {
114						t.Errorf("want %q, got %q", w, g)
115					}
116				}
117				builder := NewDepSetBuilder(order)
118				assertEquals(t, nil, builder.Build().ToList())
119
120				builder.Direct(b)
121				assertEquals(t, Paths{b}, builder.Build().ToList())
122
123				builder.Direct(d)
124				assertEquals(t, Paths{b, d}, builder.Build().ToList())
125
126				child := NewDepSetBuilder(order).Direct(c, a, e).Build()
127				builder.Transitive(child)
128				return builder.Build()
129			},
130			postorder:   []string{"c", "a", "e", "b", "d"},
131			preorder:    []string{"b", "d", "c", "a", "e"},
132			topological: []string{"b", "d", "c", "a", "e"},
133		},
134		{
135			name: "builderChaining",
136			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
137				return NewDepSetBuilder(order).Direct(b).Direct(d).
138					Transitive(NewDepSetBuilder(order).Direct(c, a, e).Build()).Build()
139			},
140			postorder:   []string{"c", "a", "e", "b", "d"},
141			preorder:    []string{"b", "d", "c", "a", "e"},
142			topological: []string{"b", "d", "c", "a", "e"},
143		},
144		{
145			name: "transitiveDepsHandledSeparately",
146			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
147				subset := NewDepSetBuilder(order).Direct(c, a, e).Build()
148				builder := NewDepSetBuilder(order)
149				// The fact that we add the transitive subset between the Direct(b) and Direct(d)
150				// calls should not change the result.
151				builder.Direct(b)
152				builder.Transitive(subset)
153				builder.Direct(d)
154				return builder.Build()
155			},
156			postorder:   []string{"c", "a", "e", "b", "d"},
157			preorder:    []string{"b", "d", "c", "a", "e"},
158			topological: []string{"b", "d", "c", "a", "e"},
159		},
160		{
161			name: "nestingNoDuplicates",
162			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
163				subset := NewDepSetBuilder(order).Direct(c, a, e).Build()
164				return NewDepSetBuilder(order).Direct(b, d, e).Transitive(subset).Build()
165			},
166			postorder:   []string{"c", "a", "e", "b", "d"},
167			preorder:    []string{"b", "d", "e", "c", "a"},
168			topological: []string{"b", "d", "c", "a", "e"},
169		},
170		{
171			name: "chain",
172			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
173				c := NewDepSetBuilder(order).Direct(c).Build()
174				b := NewDepSetBuilder(order).Direct(b).Transitive(c).Build()
175				a := NewDepSetBuilder(order).Direct(a).Transitive(b).Build()
176
177				return a
178			},
179			postorder:   []string{"c", "b", "a"},
180			preorder:    []string{"a", "b", "c"},
181			topological: []string{"a", "b", "c"},
182		},
183		{
184			name: "diamond",
185			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
186				d := NewDepSetBuilder(order).Direct(d).Build()
187				c := NewDepSetBuilder(order).Direct(c).Transitive(d).Build()
188				b := NewDepSetBuilder(order).Direct(b).Transitive(d).Build()
189				a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
190
191				return a
192			},
193			postorder:   []string{"d", "b", "c", "a"},
194			preorder:    []string{"a", "b", "d", "c"},
195			topological: []string{"a", "b", "c", "d"},
196		},
197		{
198			name: "extendedDiamond",
199			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
200				d := NewDepSetBuilder(order).Direct(d).Build()
201				e := NewDepSetBuilder(order).Direct(e).Build()
202				b := NewDepSetBuilder(order).Direct(b).Transitive(d).Transitive(e).Build()
203				c := NewDepSetBuilder(order).Direct(c).Transitive(e).Transitive(d).Build()
204				a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
205				return a
206			},
207			postorder:   []string{"d", "e", "b", "c", "a"},
208			preorder:    []string{"a", "b", "d", "e", "c"},
209			topological: []string{"a", "b", "c", "e", "d"},
210		},
211		{
212			name: "extendedDiamondRightArm",
213			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
214				d := NewDepSetBuilder(order).Direct(d).Build()
215				e := NewDepSetBuilder(order).Direct(e).Build()
216				b := NewDepSetBuilder(order).Direct(b).Transitive(d).Transitive(e).Build()
217				c2 := NewDepSetBuilder(order).Direct(c2).Transitive(e).Transitive(d).Build()
218				c := NewDepSetBuilder(order).Direct(c).Transitive(c2).Build()
219				a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
220				return a
221			},
222			postorder:   []string{"d", "e", "b", "c2", "c", "a"},
223			preorder:    []string{"a", "b", "d", "e", "c", "c2"},
224			topological: []string{"a", "b", "c", "c2", "e", "d"},
225		},
226		{
227			name: "orderConflict",
228			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
229				child1 := NewDepSetBuilder(order).Direct(a, b).Build()
230				child2 := NewDepSetBuilder(order).Direct(b, a).Build()
231				parent := NewDepSetBuilder(order).Transitive(child1).Transitive(child2).Build()
232				return parent
233			},
234			postorder:   []string{"a", "b"},
235			preorder:    []string{"a", "b"},
236			topological: []string{"b", "a"},
237		},
238		{
239			name: "orderConflictNested",
240			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
241				a := NewDepSetBuilder(order).Direct(a).Build()
242				b := NewDepSetBuilder(order).Direct(b).Build()
243				child1 := NewDepSetBuilder(order).Transitive(a).Transitive(b).Build()
244				child2 := NewDepSetBuilder(order).Transitive(b).Transitive(a).Build()
245				parent := NewDepSetBuilder(order).Transitive(child1).Transitive(child2).Build()
246				return parent
247			},
248			postorder:   []string{"a", "b"},
249			preorder:    []string{"a", "b"},
250			topological: []string{"b", "a"},
251		},
252	}
253
254	for _, tt := range tests {
255		t.Run(tt.name, func(t *testing.T) {
256			t.Run("postorder", func(t *testing.T) {
257				depSet := tt.depSet(t, POSTORDER)
258				if g, w := depSet.ToList().Strings(), tt.postorder; !reflect.DeepEqual(g, w) {
259					t.Errorf("expected ToList() = %q, got %q", w, g)
260				}
261			})
262			t.Run("preorder", func(t *testing.T) {
263				depSet := tt.depSet(t, PREORDER)
264				if g, w := depSet.ToList().Strings(), tt.preorder; !reflect.DeepEqual(g, w) {
265					t.Errorf("expected ToList() = %q, got %q", w, g)
266				}
267			})
268			t.Run("topological", func(t *testing.T) {
269				depSet := tt.depSet(t, TOPOLOGICAL)
270				if g, w := depSet.ToList().Strings(), tt.topological; !reflect.DeepEqual(g, w) {
271					t.Errorf("expected ToList() = %q, got %q", w, g)
272				}
273			})
274		})
275	}
276}
277
278func TestDepSetInvalidOrder(t *testing.T) {
279	orders := []DepSetOrder{POSTORDER, PREORDER, TOPOLOGICAL}
280
281	run := func(t *testing.T, order1, order2 DepSetOrder) {
282		defer func() {
283			if r := recover(); r != nil {
284				if err, ok := r.(error); !ok {
285					t.Fatalf("expected panic error, got %v", err)
286				} else if !strings.Contains(err.Error(), "incompatible order") {
287					t.Fatalf("expected incompatible order error, got %v", err)
288				}
289			}
290		}()
291		NewDepSet(order1, nil, []*DepSet{NewDepSet(order2, nil, nil)})
292		t.Fatal("expected panic")
293	}
294
295	for _, order1 := range orders {
296		t.Run(order1.String(), func(t *testing.T) {
297			for _, order2 := range orders {
298				t.Run(order2.String(), func(t *testing.T) {
299					if order1 != order2 {
300						run(t, order1, order2)
301					}
302				})
303			}
304		})
305	}
306}
307
308func Test_firstUnique(t *testing.T) {
309	f := func(t *testing.T, imp func([]string) []string, in, want []string) {
310		t.Helper()
311		out := imp(in)
312		if !reflect.DeepEqual(out, want) {
313			t.Errorf("incorrect output:")
314			t.Errorf("     input: %#v", in)
315			t.Errorf("  expected: %#v", want)
316			t.Errorf("       got: %#v", out)
317		}
318	}
319
320	for _, testCase := range firstUniqueStringsTestCases {
321		t.Run("list", func(t *testing.T) {
322			f(t, func(s []string) []string {
323				return firstUniqueList(s).([]string)
324			}, testCase.in, testCase.out)
325		})
326		t.Run("map", func(t *testing.T) {
327			f(t, func(s []string) []string {
328				return firstUniqueMap(s).([]string)
329			}, testCase.in, testCase.out)
330		})
331	}
332}
333
334func Benchmark_firstUnique(b *testing.B) {
335	implementations := []struct {
336		name string
337		f    func([]string) []string
338	}{
339		{
340			name: "list",
341			f: func(slice []string) []string {
342				return firstUniqueList(slice).([]string)
343			},
344		},
345		{
346			name: "map",
347			f: func(slice []string) []string {
348				return firstUniqueMap(slice).([]string)
349			},
350		},
351		{
352			name: "optimal",
353			f: func(slice []string) []string {
354				return firstUnique(slice).([]string)
355			},
356		},
357	}
358	const maxSize = 1024
359	uniqueStrings := make([]string, maxSize)
360	for i := range uniqueStrings {
361		uniqueStrings[i] = strconv.Itoa(i)
362	}
363	sameString := make([]string, maxSize)
364	for i := range sameString {
365		sameString[i] = uniqueStrings[0]
366	}
367
368	f := func(b *testing.B, imp func([]string) []string, s []string) {
369		for i := 0; i < b.N; i++ {
370			b.ReportAllocs()
371			s = append([]string(nil), s...)
372			imp(s)
373		}
374	}
375
376	for n := 1; n <= maxSize; n <<= 1 {
377		b.Run(strconv.Itoa(n), func(b *testing.B) {
378			for _, implementation := range implementations {
379				b.Run(implementation.name, func(b *testing.B) {
380					b.Run("same", func(b *testing.B) {
381						f(b, implementation.f, sameString[:n])
382					})
383					b.Run("unique", func(b *testing.B) {
384						f(b, implementation.f, uniqueStrings[:n])
385					})
386				})
387			}
388		})
389	}
390}
391