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	"strings"
21	"testing"
22)
23
24func ExampleDepSet_ToList_postordered() {
25	a := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("a")).Build()
26	b := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build()
27	c := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build()
28	d := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
29
30	fmt.Println(d.ToList().Strings())
31	// Output: [a b c d]
32}
33
34func ExampleDepSet_ToList_preordered() {
35	a := NewDepSetBuilder(PREORDER).Direct(PathForTesting("a")).Build()
36	b := NewDepSetBuilder(PREORDER).Direct(PathForTesting("b")).Transitive(a).Build()
37	c := NewDepSetBuilder(PREORDER).Direct(PathForTesting("c")).Transitive(a).Build()
38	d := NewDepSetBuilder(PREORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
39
40	fmt.Println(d.ToList().Strings())
41	// Output: [d b a c]
42}
43
44func ExampleDepSet_ToList_topological() {
45	a := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("a")).Build()
46	b := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("b")).Transitive(a).Build()
47	c := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("c")).Transitive(a).Build()
48	d := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("d")).Transitive(b, c).Build()
49
50	fmt.Println(d.ToList().Strings())
51	// Output: [d b c a]
52}
53
54func ExampleDepSet_ToSortedList() {
55	a := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("a")).Build()
56	b := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build()
57	c := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build()
58	d := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()
59
60	fmt.Println(d.ToSortedList().Strings())
61	// Output: [a b c d]
62}
63
64// Tests based on Bazel's ExpanderTestBase.java to ensure compatibility
65// https://github.com/bazelbuild/bazel/blob/master/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java
66func TestDepSet(t *testing.T) {
67	a := PathForTesting("a")
68	b := PathForTesting("b")
69	c := PathForTesting("c")
70	c2 := PathForTesting("c2")
71	d := PathForTesting("d")
72	e := PathForTesting("e")
73
74	tests := []struct {
75		name                             string
76		depSet                           func(t *testing.T, order DepSetOrder) *DepSet
77		postorder, preorder, topological []string
78	}{
79		{
80			name: "simple",
81			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
82				return NewDepSet(order, Paths{c, a, b}, nil)
83			},
84			postorder:   []string{"c", "a", "b"},
85			preorder:    []string{"c", "a", "b"},
86			topological: []string{"c", "a", "b"},
87		},
88		{
89			name: "simpleNoDuplicates",
90			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
91				return NewDepSet(order, Paths{c, a, a, a, b}, nil)
92			},
93			postorder:   []string{"c", "a", "b"},
94			preorder:    []string{"c", "a", "b"},
95			topological: []string{"c", "a", "b"},
96		},
97		{
98			name: "nesting",
99			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
100				subset := NewDepSet(order, Paths{c, a, e}, nil)
101				return NewDepSet(order, Paths{b, d}, []*DepSet{subset})
102			},
103			postorder:   []string{"c", "a", "e", "b", "d"},
104			preorder:    []string{"b", "d", "c", "a", "e"},
105			topological: []string{"b", "d", "c", "a", "e"},
106		},
107		{
108			name: "builderReuse",
109			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
110				assertEquals := func(t *testing.T, w, g Paths) {
111					if !reflect.DeepEqual(w, g) {
112						t.Errorf("want %q, got %q", w, g)
113					}
114				}
115				builder := NewDepSetBuilder(order)
116				assertEquals(t, nil, builder.Build().ToList())
117
118				builder.Direct(b)
119				assertEquals(t, Paths{b}, builder.Build().ToList())
120
121				builder.Direct(d)
122				assertEquals(t, Paths{b, d}, builder.Build().ToList())
123
124				child := NewDepSetBuilder(order).Direct(c, a, e).Build()
125				builder.Transitive(child)
126				return builder.Build()
127			},
128			postorder:   []string{"c", "a", "e", "b", "d"},
129			preorder:    []string{"b", "d", "c", "a", "e"},
130			topological: []string{"b", "d", "c", "a", "e"},
131		},
132		{
133			name: "builderChaining",
134			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
135				return NewDepSetBuilder(order).Direct(b).Direct(d).
136					Transitive(NewDepSetBuilder(order).Direct(c, a, e).Build()).Build()
137			},
138			postorder:   []string{"c", "a", "e", "b", "d"},
139			preorder:    []string{"b", "d", "c", "a", "e"},
140			topological: []string{"b", "d", "c", "a", "e"},
141		},
142		{
143			name: "transitiveDepsHandledSeparately",
144			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
145				subset := NewDepSetBuilder(order).Direct(c, a, e).Build()
146				builder := NewDepSetBuilder(order)
147				// The fact that we add the transitive subset between the Direct(b) and Direct(d)
148				// calls should not change the result.
149				builder.Direct(b)
150				builder.Transitive(subset)
151				builder.Direct(d)
152				return builder.Build()
153			},
154			postorder:   []string{"c", "a", "e", "b", "d"},
155			preorder:    []string{"b", "d", "c", "a", "e"},
156			topological: []string{"b", "d", "c", "a", "e"},
157		},
158		{
159			name: "nestingNoDuplicates",
160			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
161				subset := NewDepSetBuilder(order).Direct(c, a, e).Build()
162				return NewDepSetBuilder(order).Direct(b, d, e).Transitive(subset).Build()
163			},
164			postorder:   []string{"c", "a", "e", "b", "d"},
165			preorder:    []string{"b", "d", "e", "c", "a"},
166			topological: []string{"b", "d", "c", "a", "e"},
167		},
168		{
169			name: "chain",
170			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
171				c := NewDepSetBuilder(order).Direct(c).Build()
172				b := NewDepSetBuilder(order).Direct(b).Transitive(c).Build()
173				a := NewDepSetBuilder(order).Direct(a).Transitive(b).Build()
174
175				return a
176			},
177			postorder:   []string{"c", "b", "a"},
178			preorder:    []string{"a", "b", "c"},
179			topological: []string{"a", "b", "c"},
180		},
181		{
182			name: "diamond",
183			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
184				d := NewDepSetBuilder(order).Direct(d).Build()
185				c := NewDepSetBuilder(order).Direct(c).Transitive(d).Build()
186				b := NewDepSetBuilder(order).Direct(b).Transitive(d).Build()
187				a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
188
189				return a
190			},
191			postorder:   []string{"d", "b", "c", "a"},
192			preorder:    []string{"a", "b", "d", "c"},
193			topological: []string{"a", "b", "c", "d"},
194		},
195		{
196			name: "extendedDiamond",
197			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
198				d := NewDepSetBuilder(order).Direct(d).Build()
199				e := NewDepSetBuilder(order).Direct(e).Build()
200				b := NewDepSetBuilder(order).Direct(b).Transitive(d).Transitive(e).Build()
201				c := NewDepSetBuilder(order).Direct(c).Transitive(e).Transitive(d).Build()
202				a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
203				return a
204			},
205			postorder:   []string{"d", "e", "b", "c", "a"},
206			preorder:    []string{"a", "b", "d", "e", "c"},
207			topological: []string{"a", "b", "c", "e", "d"},
208		},
209		{
210			name: "extendedDiamondRightArm",
211			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
212				d := NewDepSetBuilder(order).Direct(d).Build()
213				e := NewDepSetBuilder(order).Direct(e).Build()
214				b := NewDepSetBuilder(order).Direct(b).Transitive(d).Transitive(e).Build()
215				c2 := NewDepSetBuilder(order).Direct(c2).Transitive(e).Transitive(d).Build()
216				c := NewDepSetBuilder(order).Direct(c).Transitive(c2).Build()
217				a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build()
218				return a
219			},
220			postorder:   []string{"d", "e", "b", "c2", "c", "a"},
221			preorder:    []string{"a", "b", "d", "e", "c", "c2"},
222			topological: []string{"a", "b", "c", "c2", "e", "d"},
223		},
224		{
225			name: "orderConflict",
226			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
227				child1 := NewDepSetBuilder(order).Direct(a, b).Build()
228				child2 := NewDepSetBuilder(order).Direct(b, a).Build()
229				parent := NewDepSetBuilder(order).Transitive(child1).Transitive(child2).Build()
230				return parent
231			},
232			postorder:   []string{"a", "b"},
233			preorder:    []string{"a", "b"},
234			topological: []string{"b", "a"},
235		},
236		{
237			name: "orderConflictNested",
238			depSet: func(t *testing.T, order DepSetOrder) *DepSet {
239				a := NewDepSetBuilder(order).Direct(a).Build()
240				b := NewDepSetBuilder(order).Direct(b).Build()
241				child1 := NewDepSetBuilder(order).Transitive(a).Transitive(b).Build()
242				child2 := NewDepSetBuilder(order).Transitive(b).Transitive(a).Build()
243				parent := NewDepSetBuilder(order).Transitive(child1).Transitive(child2).Build()
244				return parent
245			},
246			postorder:   []string{"a", "b"},
247			preorder:    []string{"a", "b"},
248			topological: []string{"b", "a"},
249		},
250	}
251
252	for _, tt := range tests {
253		t.Run(tt.name, func(t *testing.T) {
254			t.Run("postorder", func(t *testing.T) {
255				depSet := tt.depSet(t, POSTORDER)
256				if g, w := depSet.ToList().Strings(), tt.postorder; !reflect.DeepEqual(g, w) {
257					t.Errorf("expected ToList() = %q, got %q", w, g)
258				}
259			})
260			t.Run("preorder", func(t *testing.T) {
261				depSet := tt.depSet(t, PREORDER)
262				if g, w := depSet.ToList().Strings(), tt.preorder; !reflect.DeepEqual(g, w) {
263					t.Errorf("expected ToList() = %q, got %q", w, g)
264				}
265			})
266			t.Run("topological", func(t *testing.T) {
267				depSet := tt.depSet(t, TOPOLOGICAL)
268				if g, w := depSet.ToList().Strings(), tt.topological; !reflect.DeepEqual(g, w) {
269					t.Errorf("expected ToList() = %q, got %q", w, g)
270				}
271			})
272		})
273	}
274}
275
276func TestDepSetInvalidOrder(t *testing.T) {
277	orders := []DepSetOrder{POSTORDER, PREORDER, TOPOLOGICAL}
278
279	run := func(t *testing.T, order1, order2 DepSetOrder) {
280		defer func() {
281			if r := recover(); r != nil {
282				if err, ok := r.(error); !ok {
283					t.Fatalf("expected panic error, got %v", err)
284				} else if !strings.Contains(err.Error(), "incompatible order") {
285					t.Fatalf("expected incompatible order error, got %v", err)
286				}
287			}
288		}()
289		NewDepSet(order1, nil, []*DepSet{NewDepSet(order2, nil, nil)})
290		t.Fatal("expected panic")
291	}
292
293	for _, order1 := range orders {
294		t.Run(order1.String(), func(t *testing.T) {
295			for _, order2 := range orders {
296				t.Run(order2.String(), func(t *testing.T) {
297					if order1 != order2 {
298						run(t, order1, order2)
299					}
300				})
301			}
302		})
303	}
304}
305