From 70f590946be178907070a152a1daea2845f0a485 Mon Sep 17 00:00:00 2001 From: Colin Cross Date: Tue, 14 Jul 2020 15:02:16 -0700 Subject: Add DepSets Add DepSets to efficiently support tracking transitive Paths without copying, based on Bazel's depsets: https://docs.bazel.build/versions/master/skylark/depsets.html Bug: 153485543 Test: depset_test.go Change-Id: If744affdf1ed850113166ba611a79a891262040c Merged-In: If744affdf1ed850113166ba611a79a891262040c (cherry picked from commit 9e44e21e91cf38aa0a863bd87cffa6fe3534cc04) --- android/Android.bp | 2 + android/depset.go | 190 +++++++++++++++++++++++++++++++ android/depset_test.go | 304 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 496 insertions(+) create mode 100644 android/depset.go create mode 100644 android/depset_test.go diff --git a/android/Android.bp b/android/Android.bp index d904a86c..9712c46e 100644 --- a/android/Android.bp +++ b/android/Android.bp @@ -18,6 +18,7 @@ bootstrap_go_package { "csuite_config.go", "defaults.go", "defs.go", + "depset.go", "expand.go", "filegroup.go", "hooks.go", @@ -59,6 +60,7 @@ bootstrap_go_package { "arch_test.go", "config_test.go", "csuite_config_test.go", + "depset_test.go", "expand_test.go", "module_test.go", "mutator_test.go", diff --git a/android/depset.go b/android/depset.go new file mode 100644 index 00000000..f7070942 --- /dev/null +++ b/android/depset.go @@ -0,0 +1,190 @@ +// Copyright 2020 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package android + +import "fmt" + +// DepSet is designed to be conceptually compatible with Bazel's depsets: +// https://docs.bazel.build/versions/master/skylark/depsets.html + +// A DepSet efficiently stores Paths from transitive dependencies without copying. It is stored +// as a DAG of DepSet nodes, each of which has some direct contents and a list of dependency +// DepSet nodes. +// +// A DepSet has an order that will be used to walk the DAG when ToList() is called. The order +// can be POSTORDER, PREORDER, or TOPOLOGICAL. POSTORDER and PREORDER orders return a postordered +// or preordered left to right flattened list. TOPOLOGICAL returns a list that guarantees that +// elements of children are listed after all of their parents (unless there are duplicate direct +// elements in the DepSet or any of its transitive dependencies, in which case the ordering of the +// duplicated element is not guaranteed). +// +// A DepSet is created by NewDepSet or NewDepSetBuilder.Build from the Paths for direct contents +// and the *DepSets of dependencies. A DepSet is immutable once created. +type DepSet struct { + preorder bool + reverse bool + order DepSetOrder + direct Paths + transitive []*DepSet +} + +// DepSetBuilder is used to create an immutable DepSet. +type DepSetBuilder struct { + order DepSetOrder + direct Paths + transitive []*DepSet +} + +type DepSetOrder int + +const ( + PREORDER DepSetOrder = iota + POSTORDER + TOPOLOGICAL +) + +func (o DepSetOrder) String() string { + switch o { + case PREORDER: + return "PREORDER" + case POSTORDER: + return "POSTORDER" + case TOPOLOGICAL: + return "TOPOLOGICAL" + default: + panic(fmt.Errorf("Invalid DepSetOrder %d", o)) + } +} + +// NewDepSet returns an immutable DepSet with the given order, direct and transitive contents. +func NewDepSet(order DepSetOrder, direct Paths, transitive []*DepSet) *DepSet { + var directCopy Paths + var transitiveCopy []*DepSet + if order == TOPOLOGICAL { + directCopy = ReversePaths(direct) + transitiveCopy = reverseDepSets(transitive) + } else { + // Use copy instead of append(nil, ...) to make a slice that is exactly the size of the input + // slice. The DepSet is immutable, there is no need for additional capacity. + directCopy = make(Paths, len(direct)) + copy(directCopy, direct) + transitiveCopy = make([]*DepSet, len(transitive)) + copy(transitiveCopy, transitive) + } + + for _, dep := range transitive { + if dep.order != order { + panic(fmt.Errorf("incompatible order, new DepSet is %s but transitive DepSet is %s", + order, dep.order)) + } + } + + return &DepSet{ + preorder: order == PREORDER, + reverse: order == TOPOLOGICAL, + order: order, + direct: directCopy, + transitive: transitiveCopy, + } +} + +// NewDepSetBuilder returns a DepSetBuilder to create an immutable DepSet with the given order. +func NewDepSetBuilder(order DepSetOrder) *DepSetBuilder { + return &DepSetBuilder{order: order} +} + +// Direct adds direct contents to the DepSet being built by a DepSetBuilder. Newly added direct +// contents are to the right of any existing direct contents. +func (b *DepSetBuilder) Direct(direct ...Path) *DepSetBuilder { + b.direct = append(b.direct, direct...) + return b +} + +// Transitive adds transitive contents to the DepSet being built by a DepSetBuilder. Newly added +// transitive contents are to the right of any existing transitive contents. +func (b *DepSetBuilder) Transitive(transitive ...*DepSet) *DepSetBuilder { + b.transitive = append(b.transitive, transitive...) + return b +} + +// Returns the DepSet being built by this DepSetBuilder. The DepSetBuilder retains its contents +// for creating more DepSets. +func (b *DepSetBuilder) Build() *DepSet { + return NewDepSet(b.order, b.direct, b.transitive) +} + +// walk calls the visit method in depth-first order on a DepSet, preordered if d.preorder is set, +// otherwise postordered. +func (d *DepSet) walk(visit func(Paths)) { + visited := make(map[*DepSet]bool) + + var dfs func(d *DepSet) + dfs = func(d *DepSet) { + visited[d] = true + if d.preorder { + visit(d.direct) + } + for _, dep := range d.transitive { + if !visited[dep] { + dfs(dep) + } + } + + if !d.preorder { + visit(d.direct) + } + } + + dfs(d) +} + +// ToList returns the DepSet flattened to a list. The order in the list is based on the order +// of the DepSet. POSTORDER and PREORDER orders return a postordered or preordered left to right +// flattened list. TOPOLOGICAL returns a list that guarantees that elements of children are listed +// after all of their parents (unless there are duplicate direct elements in the DepSet or any of +// its transitive dependencies, in which case the ordering of the duplicated element is not +// guaranteed). +func (d *DepSet) ToList() Paths { + var list Paths + d.walk(func(paths Paths) { + list = append(list, paths...) + }) + list = FirstUniquePaths(list) + if d.reverse { + reversePathsInPlace(list) + } + return list +} + +// ToSortedList returns the direct and transitive contents of a DepSet in lexically sorted order +// with duplicates removed. +func (d *DepSet) ToSortedList() Paths { + list := d.ToList() + return SortedUniquePaths(list) +} + +func reversePathsInPlace(list Paths) { + for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 { + list[i], list[j] = list[j], list[i] + } +} + +func reverseDepSets(list []*DepSet) []*DepSet { + ret := make([]*DepSet, len(list)) + for i := range list { + ret[i] = list[len(list)-1-i] + } + return ret +} diff --git a/android/depset_test.go b/android/depset_test.go new file mode 100644 index 00000000..c328127b --- /dev/null +++ b/android/depset_test.go @@ -0,0 +1,304 @@ +// Copyright 2020 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package android + +import ( + "fmt" + "reflect" + "strings" + "testing" +) + +func ExampleDepSet_ToList_postordered() { + a := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("a")).Build() + b := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build() + c := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build() + d := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build() + + fmt.Println(d.ToList().Strings()) + // Output: [a b c d] +} + +func ExampleDepSet_ToList_preordered() { + a := NewDepSetBuilder(PREORDER).Direct(PathForTesting("a")).Build() + b := NewDepSetBuilder(PREORDER).Direct(PathForTesting("b")).Transitive(a).Build() + c := NewDepSetBuilder(PREORDER).Direct(PathForTesting("c")).Transitive(a).Build() + d := NewDepSetBuilder(PREORDER).Direct(PathForTesting("d")).Transitive(b, c).Build() + + fmt.Println(d.ToList().Strings()) + // Output: [d b a c] +} + +func ExampleDepSet_ToList_topological() { + a := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("a")).Build() + b := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("b")).Transitive(a).Build() + c := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("c")).Transitive(a).Build() + d := NewDepSetBuilder(TOPOLOGICAL).Direct(PathForTesting("d")).Transitive(b, c).Build() + + fmt.Println(d.ToList().Strings()) + // Output: [d b c a] +} + +func ExampleDepSet_ToSortedList() { + a := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("a")).Build() + b := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build() + c := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build() + d := NewDepSetBuilder(POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build() + + fmt.Println(d.ToSortedList().Strings()) + // Output: [a b c d] +} + +// Tests based on Bazel's ExpanderTestBase.java to ensure compatibility +// https://github.com/bazelbuild/bazel/blob/master/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java +func TestDepSet(t *testing.T) { + a := PathForTesting("a") + b := PathForTesting("b") + c := PathForTesting("c") + c2 := PathForTesting("c2") + d := PathForTesting("d") + e := PathForTesting("e") + + tests := []struct { + name string + depSet func(t *testing.T, order DepSetOrder) *DepSet + postorder, preorder, topological []string + }{ + { + name: "simple", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + return NewDepSet(order, Paths{c, a, b}, nil) + }, + postorder: []string{"c", "a", "b"}, + preorder: []string{"c", "a", "b"}, + topological: []string{"c", "a", "b"}, + }, + { + name: "simpleNoDuplicates", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + return NewDepSet(order, Paths{c, a, a, a, b}, nil) + }, + postorder: []string{"c", "a", "b"}, + preorder: []string{"c", "a", "b"}, + topological: []string{"c", "a", "b"}, + }, + { + name: "nesting", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + subset := NewDepSet(order, Paths{c, a, e}, nil) + return NewDepSet(order, Paths{b, d}, []*DepSet{subset}) + }, + postorder: []string{"c", "a", "e", "b", "d"}, + preorder: []string{"b", "d", "c", "a", "e"}, + topological: []string{"b", "d", "c", "a", "e"}, + }, + { + name: "builderReuse", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + assertEquals := func(t *testing.T, w, g Paths) { + if !reflect.DeepEqual(w, g) { + t.Errorf("want %q, got %q", w, g) + } + } + builder := NewDepSetBuilder(order) + assertEquals(t, nil, builder.Build().ToList()) + + builder.Direct(b) + assertEquals(t, Paths{b}, builder.Build().ToList()) + + builder.Direct(d) + assertEquals(t, Paths{b, d}, builder.Build().ToList()) + + child := NewDepSetBuilder(order).Direct(c, a, e).Build() + builder.Transitive(child) + return builder.Build() + }, + postorder: []string{"c", "a", "e", "b", "d"}, + preorder: []string{"b", "d", "c", "a", "e"}, + topological: []string{"b", "d", "c", "a", "e"}, + }, + { + name: "builderChaining", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + return NewDepSetBuilder(order).Direct(b).Direct(d). + Transitive(NewDepSetBuilder(order).Direct(c, a, e).Build()).Build() + }, + postorder: []string{"c", "a", "e", "b", "d"}, + preorder: []string{"b", "d", "c", "a", "e"}, + topological: []string{"b", "d", "c", "a", "e"}, + }, + { + name: "transitiveDepsHandledSeparately", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + subset := NewDepSetBuilder(order).Direct(c, a, e).Build() + builder := NewDepSetBuilder(order) + // The fact that we add the transitive subset between the Direct(b) and Direct(d) + // calls should not change the result. + builder.Direct(b) + builder.Transitive(subset) + builder.Direct(d) + return builder.Build() + }, + postorder: []string{"c", "a", "e", "b", "d"}, + preorder: []string{"b", "d", "c", "a", "e"}, + topological: []string{"b", "d", "c", "a", "e"}, + }, + { + name: "nestingNoDuplicates", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + subset := NewDepSetBuilder(order).Direct(c, a, e).Build() + return NewDepSetBuilder(order).Direct(b, d, e).Transitive(subset).Build() + }, + postorder: []string{"c", "a", "e", "b", "d"}, + preorder: []string{"b", "d", "e", "c", "a"}, + topological: []string{"b", "d", "c", "a", "e"}, + }, + { + name: "chain", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + c := NewDepSetBuilder(order).Direct(c).Build() + b := NewDepSetBuilder(order).Direct(b).Transitive(c).Build() + a := NewDepSetBuilder(order).Direct(a).Transitive(b).Build() + + return a + }, + postorder: []string{"c", "b", "a"}, + preorder: []string{"a", "b", "c"}, + topological: []string{"a", "b", "c"}, + }, + { + name: "diamond", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + d := NewDepSetBuilder(order).Direct(d).Build() + c := NewDepSetBuilder(order).Direct(c).Transitive(d).Build() + b := NewDepSetBuilder(order).Direct(b).Transitive(d).Build() + a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build() + + return a + }, + postorder: []string{"d", "b", "c", "a"}, + preorder: []string{"a", "b", "d", "c"}, + topological: []string{"a", "b", "c", "d"}, + }, + { + name: "extendedDiamond", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + d := NewDepSetBuilder(order).Direct(d).Build() + e := NewDepSetBuilder(order).Direct(e).Build() + b := NewDepSetBuilder(order).Direct(b).Transitive(d).Transitive(e).Build() + c := NewDepSetBuilder(order).Direct(c).Transitive(e).Transitive(d).Build() + a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build() + return a + }, + postorder: []string{"d", "e", "b", "c", "a"}, + preorder: []string{"a", "b", "d", "e", "c"}, + topological: []string{"a", "b", "c", "e", "d"}, + }, + { + name: "extendedDiamondRightArm", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + d := NewDepSetBuilder(order).Direct(d).Build() + e := NewDepSetBuilder(order).Direct(e).Build() + b := NewDepSetBuilder(order).Direct(b).Transitive(d).Transitive(e).Build() + c2 := NewDepSetBuilder(order).Direct(c2).Transitive(e).Transitive(d).Build() + c := NewDepSetBuilder(order).Direct(c).Transitive(c2).Build() + a := NewDepSetBuilder(order).Direct(a).Transitive(b).Transitive(c).Build() + return a + }, + postorder: []string{"d", "e", "b", "c2", "c", "a"}, + preorder: []string{"a", "b", "d", "e", "c", "c2"}, + topological: []string{"a", "b", "c", "c2", "e", "d"}, + }, + { + name: "orderConflict", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + child1 := NewDepSetBuilder(order).Direct(a, b).Build() + child2 := NewDepSetBuilder(order).Direct(b, a).Build() + parent := NewDepSetBuilder(order).Transitive(child1).Transitive(child2).Build() + return parent + }, + postorder: []string{"a", "b"}, + preorder: []string{"a", "b"}, + topological: []string{"b", "a"}, + }, + { + name: "orderConflictNested", + depSet: func(t *testing.T, order DepSetOrder) *DepSet { + a := NewDepSetBuilder(order).Direct(a).Build() + b := NewDepSetBuilder(order).Direct(b).Build() + child1 := NewDepSetBuilder(order).Transitive(a).Transitive(b).Build() + child2 := NewDepSetBuilder(order).Transitive(b).Transitive(a).Build() + parent := NewDepSetBuilder(order).Transitive(child1).Transitive(child2).Build() + return parent + }, + postorder: []string{"a", "b"}, + preorder: []string{"a", "b"}, + topological: []string{"b", "a"}, + }, + } + + for _, tt := range tests { + t.Run(tt.name, func(t *testing.T) { + t.Run("postorder", func(t *testing.T) { + depSet := tt.depSet(t, POSTORDER) + if g, w := depSet.ToList().Strings(), tt.postorder; !reflect.DeepEqual(g, w) { + t.Errorf("expected ToList() = %q, got %q", w, g) + } + }) + t.Run("preorder", func(t *testing.T) { + depSet := tt.depSet(t, PREORDER) + if g, w := depSet.ToList().Strings(), tt.preorder; !reflect.DeepEqual(g, w) { + t.Errorf("expected ToList() = %q, got %q", w, g) + } + }) + t.Run("topological", func(t *testing.T) { + depSet := tt.depSet(t, TOPOLOGICAL) + if g, w := depSet.ToList().Strings(), tt.topological; !reflect.DeepEqual(g, w) { + t.Errorf("expected ToList() = %q, got %q", w, g) + } + }) + }) + } +} + +func TestDepSetInvalidOrder(t *testing.T) { + orders := []DepSetOrder{POSTORDER, PREORDER, TOPOLOGICAL} + + run := func(t *testing.T, order1, order2 DepSetOrder) { + defer func() { + if r := recover(); r != nil { + if err, ok := r.(error); !ok { + t.Fatalf("expected panic error, got %v", err) + } else if !strings.Contains(err.Error(), "incompatible order") { + t.Fatalf("expected incompatible order error, got %v", err) + } + } + }() + NewDepSet(order1, nil, []*DepSet{NewDepSet(order2, nil, nil)}) + t.Fatal("expected panic") + } + + for _, order1 := range orders { + t.Run(order1.String(), func(t *testing.T) { + for _, order2 := range orders { + t.Run(order2.String(), func(t *testing.T) { + if order1 != order2 { + run(t, order1, order2) + } + }) + } + }) + } +} -- cgit v1.2.3