depset_paths.go 3.8 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
  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. // This file implements DepSet, a thin type-safe wrapper around depSet that contains Paths.
  16. // A DepSet efficiently stores Paths from transitive dependencies without copying. It is stored
  17. // as a DAG of DepSet nodes, each of which has some direct contents and a list of dependency
  18. // DepSet nodes.
  19. //
  20. // A DepSet has an order that will be used to walk the DAG when ToList() is called. The order
  21. // can be POSTORDER, PREORDER, or TOPOLOGICAL. POSTORDER and PREORDER orders return a postordered
  22. // or preordered left to right flattened list. TOPOLOGICAL returns a list that guarantees that
  23. // elements of children are listed after all of their parents (unless there are duplicate direct
  24. // elements in the DepSet or any of its transitive dependencies, in which case the ordering of the
  25. // duplicated element is not guaranteed).
  26. //
  27. // A DepSet is created by NewDepSet or NewDepSetBuilder.Build from the Paths for direct contents
  28. // and the *DepSets of dependencies. A DepSet is immutable once created.
  29. type DepSet struct {
  30. depSet
  31. }
  32. // DepSetBuilder is used to create an immutable DepSet.
  33. type DepSetBuilder struct {
  34. depSetBuilder
  35. }
  36. // NewDepSet returns an immutable DepSet with the given order, direct and transitive contents.
  37. func NewDepSet(order DepSetOrder, direct Paths, transitive []*DepSet) *DepSet {
  38. return &DepSet{*newDepSet(order, direct, transitive)}
  39. }
  40. // NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order.
  41. func NewDepSetBuilder(order DepSetOrder) *DepSetBuilder {
  42. return &DepSetBuilder{*newDepSetBuilder(order, Paths(nil))}
  43. }
  44. // Direct adds direct contents to the DepSet being built by a DepSetBuilder. Newly added direct
  45. // contents are to the right of any existing direct contents.
  46. func (b *DepSetBuilder) Direct(direct ...Path) *DepSetBuilder {
  47. b.depSetBuilder.DirectSlice(direct)
  48. return b
  49. }
  50. // Transitive adds transitive contents to the DepSet being built by a DepSetBuilder. Newly added
  51. // transitive contents are to the right of any existing transitive contents.
  52. func (b *DepSetBuilder) Transitive(transitive ...*DepSet) *DepSetBuilder {
  53. b.depSetBuilder.Transitive(transitive)
  54. return b
  55. }
  56. // Returns the DepSet being built by this DepSetBuilder. The DepSetBuilder retains its contents
  57. // for creating more DepSets.
  58. func (b *DepSetBuilder) Build() *DepSet {
  59. return &DepSet{*b.depSetBuilder.Build()}
  60. }
  61. // ToList returns the DepSet flattened to a list. The order in the list is based on the order
  62. // of the DepSet. POSTORDER and PREORDER orders return a postordered or preordered left to right
  63. // flattened list. TOPOLOGICAL returns a list that guarantees that elements of children are listed
  64. // after all of their parents (unless there are duplicate direct elements in the DepSet or any of
  65. // its transitive dependencies, in which case the ordering of the duplicated element is not
  66. // guaranteed).
  67. func (d *DepSet) ToList() Paths {
  68. if d == nil {
  69. return nil
  70. }
  71. return d.toList(func(paths interface{}) interface{} {
  72. return FirstUniquePaths(paths.(Paths))
  73. }).(Paths)
  74. }
  75. // ToSortedList returns the direct and transitive contents of a DepSet in lexically sorted order
  76. // with duplicates removed.
  77. func (d *DepSet) ToSortedList() Paths {
  78. if d == nil {
  79. return nil
  80. }
  81. paths := d.ToList()
  82. return SortedUniquePaths(paths)
  83. }