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