depset_test.go 11 KB

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