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