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