481 lines
8.8 KiB
Go
481 lines
8.8 KiB
Go
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 TestAcyclicGraph_ReverseDepthFirstWalk_WithRemoval(t *testing.T) {
|
|
var g AcyclicGraph
|
|
g.Add(1)
|
|
g.Add(2)
|
|
g.Add(3)
|
|
g.Connect(BasicEdge(3, 2))
|
|
g.Connect(BasicEdge(2, 1))
|
|
|
|
var visits []Vertex
|
|
var lock sync.Mutex
|
|
root := make(Set)
|
|
root.Add(1)
|
|
|
|
err := g.ReverseDepthFirstWalk(root, func(v Vertex, d int) error {
|
|
lock.Lock()
|
|
defer lock.Unlock()
|
|
visits = append(visits, v)
|
|
g.Remove(v)
|
|
return nil
|
|
})
|
|
if err != nil {
|
|
t.Fatalf("err: %s", err)
|
|
}
|
|
|
|
expected := []Vertex{1, 2, 3}
|
|
if !reflect.DeepEqual(visits, expected) {
|
|
t.Fatalf("expected: %#v, got: %#v", expected, visits)
|
|
}
|
|
}
|
|
|
|
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
|
|
`
|