blob: 5b273938e8fe4ba3b7dfe567cb606211d3bacdff [file] [log] [blame]
package dag
import (
"flag"
"fmt"
"os"
"reflect"
"strconv"
"strings"
"sync"
"testing"
"github.com/hashicorp/terraform/internal/tfdiags"
_ "github.com/hashicorp/terraform/internal/logging"
)
func TestMain(m *testing.M) {
flag.Parse()
os.Exit(m.Run())
}
func TestAcyclicGraphRoot(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Connect(BasicEdge(3, 2))
g.Connect(BasicEdge(3, 1))
if root, err := g.Root(); err != nil {
t.Fatalf("err: %s", err)
} else if root != 3 {
t.Fatalf("bad: %#v", root)
}
}
func TestAcyclicGraphRoot_cycle(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Connect(BasicEdge(1, 2))
g.Connect(BasicEdge(2, 3))
g.Connect(BasicEdge(3, 1))
if _, err := g.Root(); err == nil {
t.Fatal("should error")
}
}
func TestAcyclicGraphRoot_multiple(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Connect(BasicEdge(3, 2))
if _, err := g.Root(); err == nil {
t.Fatal("should error")
}
}
func TestAyclicGraphTransReduction(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Connect(BasicEdge(1, 2))
g.Connect(BasicEdge(1, 3))
g.Connect(BasicEdge(2, 3))
g.TransitiveReduction()
actual := strings.TrimSpace(g.String())
expected := strings.TrimSpace(testGraphTransReductionStr)
if actual != expected {
t.Fatalf("bad: %s", actual)
}
}
func TestAyclicGraphTransReduction_more(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Add(4)
g.Connect(BasicEdge(1, 2))
g.Connect(BasicEdge(1, 3))
g.Connect(BasicEdge(1, 4))
g.Connect(BasicEdge(2, 3))
g.Connect(BasicEdge(2, 4))
g.Connect(BasicEdge(3, 4))
g.TransitiveReduction()
actual := strings.TrimSpace(g.String())
expected := strings.TrimSpace(testGraphTransReductionMoreStr)
if actual != expected {
t.Fatalf("bad: %s", actual)
}
}
func TestAyclicGraphTransReduction_multipleRoots(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Add(4)
g.Connect(BasicEdge(1, 2))
g.Connect(BasicEdge(1, 3))
g.Connect(BasicEdge(1, 4))
g.Connect(BasicEdge(2, 3))
g.Connect(BasicEdge(2, 4))
g.Connect(BasicEdge(3, 4))
g.Add(5)
g.Add(6)
g.Add(7)
g.Add(8)
g.Connect(BasicEdge(5, 6))
g.Connect(BasicEdge(5, 7))
g.Connect(BasicEdge(5, 8))
g.Connect(BasicEdge(6, 7))
g.Connect(BasicEdge(6, 8))
g.Connect(BasicEdge(7, 8))
g.TransitiveReduction()
actual := strings.TrimSpace(g.String())
expected := strings.TrimSpace(testGraphTransReductionMultipleRootsStr)
if actual != expected {
t.Fatalf("bad: %s", actual)
}
}
// use this to simulate slow sort operations
type counter struct {
Name string
Calls int64
}
func (s *counter) String() string {
s.Calls++
return s.Name
}
// Make sure we can reduce a sizable, fully-connected graph.
func TestAyclicGraphTransReduction_fullyConnected(t *testing.T) {
var g AcyclicGraph
const nodeCount = 200
nodes := make([]*counter, nodeCount)
for i := 0; i < nodeCount; i++ {
nodes[i] = &counter{Name: strconv.Itoa(i)}
}
// Add them all to the graph
for _, n := range nodes {
g.Add(n)
}
// connect them all
for i := range nodes {
for j := range nodes {
if i == j {
continue
}
g.Connect(BasicEdge(nodes[i], nodes[j]))
}
}
g.TransitiveReduction()
vertexNameCalls := int64(0)
for _, n := range nodes {
vertexNameCalls += n.Calls
}
switch {
case vertexNameCalls > 2*nodeCount:
// Make calling it more the 2x per node fatal.
// If we were sorting this would give us roughly ln(n)(n^3) calls, or
// >59000000 calls for 200 vertices.
t.Fatalf("VertexName called %d times", vertexNameCalls)
case vertexNameCalls > 0:
// we don't expect any calls, but a change here isn't necessarily fatal
t.Logf("WARNING: VertexName called %d times", vertexNameCalls)
}
}
func TestAcyclicGraphValidate(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Connect(BasicEdge(3, 2))
g.Connect(BasicEdge(3, 1))
if err := g.Validate(); err != nil {
t.Fatalf("err: %s", err)
}
}
func TestAcyclicGraphValidate_cycle(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Connect(BasicEdge(3, 2))
g.Connect(BasicEdge(3, 1))
g.Connect(BasicEdge(1, 2))
g.Connect(BasicEdge(2, 1))
if err := g.Validate(); err == nil {
t.Fatal("should error")
}
}
func TestAcyclicGraphValidate_cycleSelf(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Connect(BasicEdge(1, 1))
if err := g.Validate(); err == nil {
t.Fatal("should error")
}
}
func TestAcyclicGraphAncestors(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Add(4)
g.Add(5)
g.Connect(BasicEdge(0, 1))
g.Connect(BasicEdge(1, 2))
g.Connect(BasicEdge(2, 3))
g.Connect(BasicEdge(3, 4))
g.Connect(BasicEdge(4, 5))
actual, err := g.Ancestors(2)
if err != nil {
t.Fatalf("err: %#v", err)
}
expected := []Vertex{3, 4, 5}
if actual.Len() != len(expected) {
t.Fatalf("bad length! expected %#v to have len %d", actual, len(expected))
}
for _, e := range expected {
if !actual.Include(e) {
t.Fatalf("expected: %#v to include: %#v", expected, actual)
}
}
}
func TestAcyclicGraphDescendents(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Add(4)
g.Add(5)
g.Connect(BasicEdge(0, 1))
g.Connect(BasicEdge(1, 2))
g.Connect(BasicEdge(2, 3))
g.Connect(BasicEdge(3, 4))
g.Connect(BasicEdge(4, 5))
actual, err := g.Descendents(2)
if err != nil {
t.Fatalf("err: %#v", err)
}
expected := []Vertex{0, 1}
if actual.Len() != len(expected) {
t.Fatalf("bad length! expected %#v to have len %d", actual, len(expected))
}
for _, e := range expected {
if !actual.Include(e) {
t.Fatalf("expected: %#v to include: %#v", expected, actual)
}
}
}
func TestAcyclicGraphWalk(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Connect(BasicEdge(3, 2))
g.Connect(BasicEdge(3, 1))
var visits []Vertex
var lock sync.Mutex
err := g.Walk(func(v Vertex) tfdiags.Diagnostics {
lock.Lock()
defer lock.Unlock()
visits = append(visits, v)
return nil
})
if err != nil {
t.Fatalf("err: %s", err)
}
expected := [][]Vertex{
{1, 2, 3},
{2, 1, 3},
}
for _, e := range expected {
if reflect.DeepEqual(visits, e) {
return
}
}
t.Fatalf("bad: %#v", visits)
}
func TestAcyclicGraphWalk_error(t *testing.T) {
var g AcyclicGraph
g.Add(1)
g.Add(2)
g.Add(3)
g.Add(4)
g.Connect(BasicEdge(4, 3))
g.Connect(BasicEdge(3, 2))
g.Connect(BasicEdge(2, 1))
var visits []Vertex
var lock sync.Mutex
err := g.Walk(func(v Vertex) tfdiags.Diagnostics {
lock.Lock()
defer lock.Unlock()
var diags tfdiags.Diagnostics
if v == 2 {
diags = diags.Append(fmt.Errorf("error"))
return diags
}
visits = append(visits, v)
return diags
})
if err == nil {
t.Fatal("should error")
}
expected := []Vertex{1}
if !reflect.DeepEqual(visits, expected) {
t.Errorf("wrong visits\ngot: %#v\nwant: %#v", visits, expected)
}
}
func BenchmarkDAG(b *testing.B) {
for i := 0; i < b.N; i++ {
count := 150
b.StopTimer()
g := &AcyclicGraph{}
// create 4 layers of fully connected nodes
// layer A
for i := 0; i < count; i++ {
g.Add(fmt.Sprintf("A%d", i))
}
// layer B
for i := 0; i < count; i++ {
B := fmt.Sprintf("B%d", i)
g.Add(B)
for j := 0; j < count; j++ {
g.Connect(BasicEdge(B, fmt.Sprintf("A%d", j)))
}
}
// layer C
for i := 0; i < count; i++ {
c := fmt.Sprintf("C%d", i)
g.Add(c)
for j := 0; j < count; j++ {
// connect them to previous layers so we have something that requires reduction
g.Connect(BasicEdge(c, fmt.Sprintf("A%d", j)))
g.Connect(BasicEdge(c, fmt.Sprintf("B%d", j)))
}
}
// layer D
for i := 0; i < count; i++ {
d := fmt.Sprintf("D%d", i)
g.Add(d)
for j := 0; j < count; j++ {
g.Connect(BasicEdge(d, fmt.Sprintf("A%d", j)))
g.Connect(BasicEdge(d, fmt.Sprintf("B%d", j)))
g.Connect(BasicEdge(d, fmt.Sprintf("C%d", j)))
}
}
b.StartTimer()
// Find dependencies for every node
for _, v := range g.Vertices() {
_, err := g.Ancestors(v)
if err != nil {
b.Fatal(err)
}
}
// reduce the final graph
g.TransitiveReduction()
}
}
func TestAcyclicGraphWalkOrder(t *testing.T) {
/* Sample dependency graph,
all edges pointing downwards.
1 2
/ \ / \
3 4 5
/ \ /
6 7
/ | \
8 9 10
\ | /
11
*/
var g AcyclicGraph
for i := 1; i <= 11; i++ {
g.Add(i)
}
g.Connect(BasicEdge(1, 3))
g.Connect(BasicEdge(1, 4))
g.Connect(BasicEdge(2, 4))
g.Connect(BasicEdge(2, 5))
g.Connect(BasicEdge(3, 6))
g.Connect(BasicEdge(4, 7))
g.Connect(BasicEdge(5, 7))
g.Connect(BasicEdge(7, 8))
g.Connect(BasicEdge(7, 9))
g.Connect(BasicEdge(7, 10))
g.Connect(BasicEdge(8, 11))
g.Connect(BasicEdge(9, 11))
g.Connect(BasicEdge(10, 11))
start := make(Set)
start.Add(2)
start.Add(1)
reverse := make(Set)
reverse.Add(11)
reverse.Add(6)
t.Run("DepthFirst", func(t *testing.T) {
var visits []vertexAtDepth
g.walk(depthFirst|downOrder, true, start, func(v Vertex, d int) error {
visits = append(visits, vertexAtDepth{v, d})
return nil
})
expect := []vertexAtDepth{
{2, 0}, {5, 1}, {7, 2}, {9, 3}, {11, 4}, {8, 3}, {10, 3}, {4, 1}, {1, 0}, {3, 1}, {6, 2},
}
if !reflect.DeepEqual(visits, expect) {
t.Errorf("expected visits:\n%v\ngot:\n%v\n", expect, visits)
}
})
t.Run("ReverseDepthFirst", func(t *testing.T) {
var visits []vertexAtDepth
g.walk(depthFirst|upOrder, true, reverse, func(v Vertex, d int) error {
visits = append(visits, vertexAtDepth{v, d})
return nil
})
expect := []vertexAtDepth{
{6, 0}, {3, 1}, {1, 2}, {11, 0}, {9, 1}, {7, 2}, {5, 3}, {2, 4}, {4, 3}, {8, 1}, {10, 1},
}
if !reflect.DeepEqual(visits, expect) {
t.Errorf("expected visits:\n%v\ngot:\n%v\n", expect, visits)
}
})
t.Run("BreadthFirst", func(t *testing.T) {
var visits []vertexAtDepth
g.walk(breadthFirst|downOrder, true, start, func(v Vertex, d int) error {
visits = append(visits, vertexAtDepth{v, d})
return nil
})
expect := []vertexAtDepth{
{1, 0}, {2, 0}, {3, 1}, {4, 1}, {5, 1}, {6, 2}, {7, 2}, {10, 3}, {8, 3}, {9, 3}, {11, 4},
}
if !reflect.DeepEqual(visits, expect) {
t.Errorf("expected visits:\n%v\ngot:\n%v\n", expect, visits)
}
})
t.Run("ReverseBreadthFirst", func(t *testing.T) {
var visits []vertexAtDepth
g.walk(breadthFirst|upOrder, true, reverse, func(v Vertex, d int) error {
visits = append(visits, vertexAtDepth{v, d})
return nil
})
expect := []vertexAtDepth{
{11, 0}, {6, 0}, {10, 1}, {8, 1}, {9, 1}, {3, 1}, {7, 2}, {1, 2}, {4, 3}, {5, 3}, {2, 4},
}
if !reflect.DeepEqual(visits, expect) {
t.Errorf("expected visits:\n%v\ngot:\n%v\n", expect, visits)
}
})
t.Run("TopologicalOrder", func(t *testing.T) {
order := g.topoOrder(downOrder)
// Validate the order by checking it against the initial graph. We only
// need to verify that each node has it's direct dependencies
// satisfied.
completed := map[Vertex]bool{}
for _, v := range order {
deps := g.DownEdges(v)
for _, dep := range deps {
if !completed[dep] {
t.Fatalf("walking node %v, but dependency %v was not yet seen", v, dep)
}
}
completed[v] = true
}
})
t.Run("ReverseTopologicalOrder", func(t *testing.T) {
order := g.topoOrder(upOrder)
// Validate the order by checking it against the initial graph. We only
// need to verify that each node has it's direct dependencies
// satisfied.
completed := map[Vertex]bool{}
for _, v := range order {
deps := g.UpEdges(v)
for _, dep := range deps {
if !completed[dep] {
t.Fatalf("walking node %v, but dependency %v was not yet seen", v, dep)
}
}
completed[v] = true
}
})
}
const testGraphTransReductionStr = `
1
2
2
3
3
`
const testGraphTransReductionMoreStr = `
1
2
2
3
3
4
4
`
const testGraphTransReductionMultipleRootsStr = `
1
2
2
3
3
4
4
5
6
6
7
7
8
8
`