android/depset_test.go

// 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[Path](POSTORDER).Direct(PathForTesting("a")).Build()
	b := NewDepSetBuilder[Path](POSTORDER).Direct(PathForTesting("b")).Transitive(a).Build()
	c := NewDepSetBuilder[Path](POSTORDER).Direct(PathForTesting("c")).Transitive(a).Build()
	d := NewDepSetBuilder[Path](POSTORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()

	fmt.Println(Paths(d.ToList()).Strings())
	// Output: [a b c d]
}

func ExampleDepSet_ToList_preordered() {
	a := NewDepSetBuilder[Path](PREORDER).Direct(PathForTesting("a")).Build()
	b := NewDepSetBuilder[Path](PREORDER).Direct(PathForTesting("b")).Transitive(a).Build()
	c := NewDepSetBuilder[Path](PREORDER).Direct(PathForTesting("c")).Transitive(a).Build()
	d := NewDepSetBuilder[Path](PREORDER).Direct(PathForTesting("d")).Transitive(b, c).Build()

	fmt.Println(Paths(d.ToList()).Strings())
	// Output: [d b a c]
}

func ExampleDepSet_ToList_topological() {
	a := NewDepSetBuilder[Path](TOPOLOGICAL).Direct(PathForTesting("a")).Build()
	b := NewDepSetBuilder[Path](TOPOLOGICAL).Direct(PathForTesting("b")).Transitive(a).Build()
	c := NewDepSetBuilder[Path](TOPOLOGICAL).Direct(PathForTesting("c")).Transitive(a).Build()
	d := NewDepSetBuilder[Path](TOPOLOGICAL).Direct(PathForTesting("d")).Transitive(b, c).Build()

	fmt.Println(Paths(d.ToList()).Strings())
	// Output: [d b c a]
}

// 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[Path]
		postorder, preorder, topological []string
	}{
		{
			name: "simple",
			depSet: func(t *testing.T, order DepSetOrder) *DepSet[Path] {
				return NewDepSet[Path](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[Path] {
				return NewDepSet[Path](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[Path] {
				subset := NewDepSet[Path](order, Paths{c, a, e}, nil)
				return NewDepSet[Path](order, Paths{b, d}, []*DepSet[Path]{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[Path] {
				assertEquals := func(t *testing.T, w, g Paths) {
					t.Helper()
					if !reflect.DeepEqual(w, g) {
						t.Errorf("want %q, got %q", w, g)
					}
				}
				builder := NewDepSetBuilder[Path](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[Path](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[Path] {
				return NewDepSetBuilder[Path](order).Direct(b).Direct(d).
					Transitive(NewDepSetBuilder[Path](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[Path] {
				subset := NewDepSetBuilder[Path](order).Direct(c, a, e).Build()
				builder := NewDepSetBuilder[Path](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[Path] {
				subset := NewDepSetBuilder[Path](order).Direct(c, a, e).Build()
				return NewDepSetBuilder[Path](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[Path] {
				c := NewDepSetBuilder[Path](order).Direct(c).Build()
				b := NewDepSetBuilder[Path](order).Direct(b).Transitive(c).Build()
				a := NewDepSetBuilder[Path](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[Path] {
				d := NewDepSetBuilder[Path](order).Direct(d).Build()
				c := NewDepSetBuilder[Path](order).Direct(c).Transitive(d).Build()
				b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Build()
				a := NewDepSetBuilder[Path](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[Path] {
				d := NewDepSetBuilder[Path](order).Direct(d).Build()
				e := NewDepSetBuilder[Path](order).Direct(e).Build()
				b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Transitive(e).Build()
				c := NewDepSetBuilder[Path](order).Direct(c).Transitive(e).Transitive(d).Build()
				a := NewDepSetBuilder[Path](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[Path] {
				d := NewDepSetBuilder[Path](order).Direct(d).Build()
				e := NewDepSetBuilder[Path](order).Direct(e).Build()
				b := NewDepSetBuilder[Path](order).Direct(b).Transitive(d).Transitive(e).Build()
				c2 := NewDepSetBuilder[Path](order).Direct(c2).Transitive(e).Transitive(d).Build()
				c := NewDepSetBuilder[Path](order).Direct(c).Transitive(c2).Build()
				a := NewDepSetBuilder[Path](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[Path] {
				child1 := NewDepSetBuilder[Path](order).Direct(a, b).Build()
				child2 := NewDepSetBuilder[Path](order).Direct(b, a).Build()
				parent := NewDepSetBuilder[Path](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[Path] {
				a := NewDepSetBuilder[Path](order).Direct(a).Build()
				b := NewDepSetBuilder[Path](order).Direct(b).Build()
				child1 := NewDepSetBuilder[Path](order).Transitive(a).Transitive(b).Build()
				child2 := NewDepSetBuilder[Path](order).Transitive(b).Transitive(a).Build()
				parent := NewDepSetBuilder[Path](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 := Paths(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 := Paths(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 := Paths(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[Path]{NewDepSet[Path](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)
					}
				})
			}
		})
	}
}