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