depset_generic.go 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
  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. )
  18. // DepSet is designed to be conceptually compatible with Bazel's depsets:
  19. // https://docs.bazel.build/versions/master/skylark/depsets.html
  20. type DepSetOrder int
  21. const (
  22. PREORDER DepSetOrder = iota
  23. POSTORDER
  24. TOPOLOGICAL
  25. )
  26. func (o DepSetOrder) String() string {
  27. switch o {
  28. case PREORDER:
  29. return "PREORDER"
  30. case POSTORDER:
  31. return "POSTORDER"
  32. case TOPOLOGICAL:
  33. return "TOPOLOGICAL"
  34. default:
  35. panic(fmt.Errorf("Invalid DepSetOrder %d", o))
  36. }
  37. }
  38. type depSettableType comparable
  39. // A DepSet efficiently stores a slice of an arbitrary type from transitive dependencies without
  40. // copying. It is stored as a DAG of DepSet nodes, each of which has some direct contents and a list
  41. // of dependency DepSet nodes.
  42. //
  43. // A DepSet has an order that will be used to walk the DAG when ToList() is called. The order
  44. // can be POSTORDER, PREORDER, or TOPOLOGICAL. POSTORDER and PREORDER orders return a postordered
  45. // or preordered left to right flattened list. TOPOLOGICAL returns a list that guarantees that
  46. // elements of children are listed after all of their parents (unless there are duplicate direct
  47. // elements in the DepSet or any of its transitive dependencies, in which case the ordering of the
  48. // duplicated element is not guaranteed).
  49. //
  50. // A DepSet is created by NewDepSet or NewDepSetBuilder.Build from the slice for direct contents
  51. // and the *DepSets of dependencies. A DepSet is immutable once created.
  52. type DepSet[T depSettableType] struct {
  53. preorder bool
  54. reverse bool
  55. order DepSetOrder
  56. direct []T
  57. transitive []*DepSet[T]
  58. }
  59. // NewDepSet returns an immutable DepSet with the given order, direct and transitive contents.
  60. func NewDepSet[T depSettableType](order DepSetOrder, direct []T, transitive []*DepSet[T]) *DepSet[T] {
  61. var directCopy []T
  62. var transitiveCopy []*DepSet[T]
  63. for _, t := range transitive {
  64. if t.order != order {
  65. panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
  66. order, t.order))
  67. }
  68. }
  69. if order == TOPOLOGICAL {
  70. // TOPOLOGICAL is implemented as a postorder traversal followed by reversing the output.
  71. // Pre-reverse the inputs here so their order is maintained in the output.
  72. directCopy = reverseSlice(direct)
  73. transitiveCopy = reverseSlice(transitive)
  74. } else {
  75. directCopy = append([]T(nil), direct...)
  76. transitiveCopy = append([]*DepSet[T](nil), transitive...)
  77. }
  78. return &DepSet[T]{
  79. preorder: order == PREORDER,
  80. reverse: order == TOPOLOGICAL,
  81. order: order,
  82. direct: directCopy,
  83. transitive: transitiveCopy,
  84. }
  85. }
  86. // DepSetBuilder is used to create an immutable DepSet.
  87. type DepSetBuilder[T depSettableType] struct {
  88. order DepSetOrder
  89. direct []T
  90. transitive []*DepSet[T]
  91. }
  92. // NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order and
  93. // type, represented by a slice of type that will be in the DepSet.
  94. func NewDepSetBuilder[T depSettableType](order DepSetOrder) *DepSetBuilder[T] {
  95. return &DepSetBuilder[T]{
  96. order: order,
  97. }
  98. }
  99. // DirectSlice adds direct contents to the DepSet being built by a DepSetBuilder. Newly added direct
  100. // contents are to the right of any existing direct contents.
  101. func (b *DepSetBuilder[T]) DirectSlice(direct []T) *DepSetBuilder[T] {
  102. b.direct = append(b.direct, direct...)
  103. return b
  104. }
  105. // Direct adds direct contents to the DepSet being built by a DepSetBuilder. Newly added direct
  106. // contents are to the right of any existing direct contents.
  107. func (b *DepSetBuilder[T]) Direct(direct ...T) *DepSetBuilder[T] {
  108. b.direct = append(b.direct, direct...)
  109. return b
  110. }
  111. // Transitive adds transitive contents to the DepSet being built by a DepSetBuilder. Newly added
  112. // transitive contents are to the right of any existing transitive contents.
  113. func (b *DepSetBuilder[T]) Transitive(transitive ...*DepSet[T]) *DepSetBuilder[T] {
  114. for _, t := range transitive {
  115. if t.order != b.order {
  116. panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s",
  117. b.order, t.order))
  118. }
  119. }
  120. b.transitive = append(b.transitive, transitive...)
  121. return b
  122. }
  123. // Returns the DepSet being built by this DepSetBuilder. The DepSetBuilder retains its contents
  124. // for creating more depSets.
  125. func (b *DepSetBuilder[T]) Build() *DepSet[T] {
  126. return NewDepSet(b.order, b.direct, b.transitive)
  127. }
  128. // walk calls the visit method in depth-first order on a DepSet, preordered if d.preorder is set,
  129. // otherwise postordered.
  130. func (d *DepSet[T]) walk(visit func([]T)) {
  131. visited := make(map[*DepSet[T]]bool)
  132. var dfs func(d *DepSet[T])
  133. dfs = func(d *DepSet[T]) {
  134. visited[d] = true
  135. if d.preorder {
  136. visit(d.direct)
  137. }
  138. for _, dep := range d.transitive {
  139. if !visited[dep] {
  140. dfs(dep)
  141. }
  142. }
  143. if !d.preorder {
  144. visit(d.direct)
  145. }
  146. }
  147. dfs(d)
  148. }
  149. // ToList returns the DepSet flattened to a list. The order in the list is based on the order
  150. // of the DepSet. POSTORDER and PREORDER orders return a postordered or preordered left to right
  151. // flattened list. TOPOLOGICAL returns a list that guarantees that elements of children are listed
  152. // after all of their parents (unless there are duplicate direct elements in the DepSet or any of
  153. // its transitive dependencies, in which case the ordering of the duplicated element is not
  154. // guaranteed).
  155. func (d *DepSet[T]) ToList() []T {
  156. return d.toList(firstUnique[T])
  157. }
  158. // toList returns the DepSet flattened to a list. The order in the list is based on the order
  159. // of the DepSet. POSTORDER and PREORDER orders return a postordered or preordered left to right
  160. // flattened list. TOPOLOGICAL returns a list that guarantees that elements of children are listed
  161. // after all of their parents (unless there are duplicate direct elements in the DepSet or any of
  162. // its transitive dependencies, in which case the ordering of the duplicated element is not
  163. // guaranteed). The firstUniqueFunc is used to remove duplicates from the list.
  164. func (d *DepSet[T]) toList(firstUniqueFunc func([]T) []T) []T {
  165. if d == nil {
  166. return nil
  167. }
  168. var list []T
  169. d.walk(func(paths []T) {
  170. list = append(list, paths...)
  171. })
  172. list = firstUniqueFunc(list)
  173. if d.reverse {
  174. reverseSliceInPlace(list)
  175. }
  176. return list
  177. }