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