vessel/graph_test.go at main · xraph/vessel · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
package vessel

import (
	"testing"

	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func TestDependencyGraph_TopologicalSort_Simple(t *testing.T) {
	g := NewDependencyGraph()
	g.AddNode("a", nil)
	g.AddNode("b", []string{"a"})
	g.AddNode("c", []string{"b"})

	result, err := g.TopologicalSort()
	require.NoError(t, err)

	// Should be in dependency order: a, b, c
	assert.Equal(t, []string{"a", "b", "c"}, result)
}

func TestDependencyGraph_TopologicalSort_Complex(t *testing.T) {
	g := NewDependencyGraph()
	g.AddNode("a", nil)
	g.AddNode("b", []string{"a"})
	g.AddNode("c", []string{"a"})
	g.AddNode("d", []string{"b", "c"})

	result, err := g.TopologicalSort()
	require.NoError(t, err)

	// "a" must come before "b" and "c"
	// "b" and "c" must come before "d"
	aIdx := indexOf(result, "a")
	bIdx := indexOf(result, "b")
	cIdx := indexOf(result, "c")
	dIdx := indexOf(result, "d")

	assert.Less(t, aIdx, bIdx)
	assert.Less(t, aIdx, cIdx)
	assert.Less(t, bIdx, dIdx)
	assert.Less(t, cIdx, dIdx)
}

func TestDependencyGraph_TopologicalSort_CircularDependency(t *testing.T) {
	g := NewDependencyGraph()
	g.AddNode("a", []string{"b"})
	g.AddNode("b", []string{"a"})

	_, err := g.TopologicalSort()
	assert.ErrorIs(t, err, ErrCircularDependencySentinel)
}

func TestDependencyGraph_TopologicalSort_SelfReference(t *testing.T) {
	g := NewDependencyGraph()
	g.AddNode("a", []string{"a"})

	_, err := g.TopologicalSort()
	assert.ErrorIs(t, err, ErrCircularDependencySentinel)
}

func TestDependencyGraph_TopologicalSort_MissingDependency(t *testing.T) {
	g := NewDependencyGraph()
	g.AddNode("a", []string{"nonexistent"})

	// Should not error - missing dependencies are skipped
	result, err := g.TopologicalSort()
	require.NoError(t, err)
	assert.Equal(t, []string{"a"}, result)
}

func TestDependencyGraph_TopologicalSort_Empty(t *testing.T) {
	g := NewDependencyGraph()

	result, err := g.TopologicalSort()
	require.NoError(t, err)
	assert.Empty(t, result)
}

func TestDependencyGraph_TopologicalSort_PreservesRegistrationOrder(t *testing.T) {
	// Test that nodes without dependencies maintain registration order (FIFO)
	g := NewDependencyGraph()

	// Add nodes in specific order without dependencies
	g.AddNode("first", nil)
	g.AddNode("second", nil)
	g.AddNode("third", nil)
	g.AddNode("fourth", nil)

	result, err := g.TopologicalSort()
	require.NoError(t, err)

	// Should maintain registration order (FIFO) for nodes without dependencies
	assert.Equal(t, []string{"first", "second", "third", "fourth"}, result)
}

func TestDependencyGraph_TopologicalSort_MixedDependenciesAndOrder(t *testing.T) {
	// Test that dependency constraints are respected while preserving registration order for independent nodes
	g := NewDependencyGraph()

	// Add nodes with mixed dependencies
	g.AddNode("independent1", nil)           // No deps - position 0
	g.AddNode("dependent", []string{"base"}) // Depends on base
	g.AddNode("base", nil)                   // No deps - position 2
	g.AddNode("independent2", nil)           // No deps - position 3

	result, err := g.TopologicalSort()
	require.NoError(t, err)

	// Verify constraints:
	// 1. "base" must come before "dependent"
	baseIdx := indexOf(result, "base")
	dependentIdx := indexOf(result, "dependent")
	assert.Less(t, baseIdx, dependentIdx, "base must come before dependent")

	// 2. Independent nodes without shared dependencies should maintain relative registration order
	ind1Idx := indexOf(result, "independent1")
	ind2Idx := indexOf(result, "independent2")
	assert.Less(t, ind1Idx, ind2Idx, "independent1 registered before independent2, should maintain order")
}

func TestDependencyGraph_Visit_AlreadyVisited(t *testing.T) {
	g := NewDependencyGraph()
	g.AddNode("a", nil)

	visited := map[string]bool{"a": true}
	visiting := make(map[string]bool)
	result := []string{}

	err := g.visit("a", visited, visiting, &result)
	assert.NoError(t, err)
	assert.Empty(t, result) // Should not add again
}

// Helper function.
func indexOf(slice []string, value string) int {
	for i, v := range slice {
		if v == value {
			return i
		}
	}

	return -1
}