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