1
2
3
4
5
6 package graph
7
8 import (
9 "testing"
10
11 "github.com/stretchr/testify/assert"
12 "k8s.io/apimachinery/pkg/runtime/schema"
13 "sigs.k8s.io/cli-utils/pkg/object"
14 "sigs.k8s.io/cli-utils/pkg/object/validation"
15 "sigs.k8s.io/cli-utils/pkg/testutil"
16 )
17
18 var (
19 o1 = object.ObjMetadata{Name: "obj1", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
20 o2 = object.ObjMetadata{Name: "obj2", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
21 o3 = object.ObjMetadata{Name: "obj3", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
22 o4 = object.ObjMetadata{Name: "obj4", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
23 o5 = object.ObjMetadata{Name: "obj5", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
24 )
25
26 var (
27 e1 = Edge{From: o1, To: o2}
28 e2 = Edge{From: o2, To: o3}
29 e3 = Edge{From: o1, To: o3}
30 e4 = Edge{From: o3, To: o4}
31 e5 = Edge{From: o2, To: o4}
32 e6 = Edge{From: o2, To: o1}
33 e7 = Edge{From: o3, To: o1}
34 e8 = Edge{From: o4, To: o5}
35 )
36
37 func TestObjectGraphSort(t *testing.T) {
38 testCases := map[string]struct {
39 vertices object.ObjMetadataSet
40 edges []Edge
41 expected []object.ObjMetadataSet
42 expectedError error
43 }{
44 "one edge": {
45 vertices: object.ObjMetadataSet{o1, o2},
46 edges: []Edge{e1},
47 expected: []object.ObjMetadataSet{{o2}, {o1}},
48 },
49 "two edges": {
50 vertices: object.ObjMetadataSet{o1, o2, o3},
51 edges: []Edge{e1, e2},
52 expected: []object.ObjMetadataSet{{o3}, {o2}, {o1}},
53 },
54 "three edges": {
55 vertices: object.ObjMetadataSet{o1, o2, o3},
56 edges: []Edge{e1, e3, e2},
57 expected: []object.ObjMetadataSet{{o3}, {o2}, {o1}},
58 },
59 "four edges": {
60 vertices: object.ObjMetadataSet{o1, o2, o3, o4},
61 edges: []Edge{e1, e2, e4, e5},
62 expected: []object.ObjMetadataSet{{o4}, {o3}, {o2}, {o1}},
63 },
64 "five edges": {
65 vertices: object.ObjMetadataSet{o1, o2, o3, o4},
66 edges: []Edge{e5, e1, e3, e2, e4},
67 expected: []object.ObjMetadataSet{{o4}, {o3}, {o2}, {o1}},
68 },
69 "no edges means all in the same first set": {
70 vertices: object.ObjMetadataSet{o1, o2, o3, o4},
71 edges: []Edge{},
72 expected: []object.ObjMetadataSet{{o4, o3, o2, o1}},
73 },
74 "multiple objects in first set": {
75 vertices: object.ObjMetadataSet{o1, o2, o3, o4, o5},
76 edges: []Edge{e1, e2, e5, e8},
77 expected: []object.ObjMetadataSet{{o5, o3}, {o4}, {o2}, {o1}},
78 },
79 "simple cycle in graph is an error": {
80 vertices: object.ObjMetadataSet{o1, o2},
81 edges: []Edge{e1, e6},
82 expected: []object.ObjMetadataSet{},
83 expectedError: validation.NewError(
84 CyclicDependencyError{
85 Edges: []Edge{
86 {
87 From: o1,
88 To: o2,
89 },
90 {
91 From: o2,
92 To: o1,
93 },
94 },
95 },
96 o1, o2,
97 ),
98 },
99 "multi-edge cycle in graph is an error": {
100 vertices: object.ObjMetadataSet{o1, o2, o3},
101 edges: []Edge{e1, e2, e7},
102 expected: []object.ObjMetadataSet{},
103 expectedError: validation.NewError(
104 CyclicDependencyError{
105 Edges: []Edge{
106 {
107 From: o1,
108 To: o2,
109 },
110 {
111 From: o2,
112 To: o3,
113 },
114 {
115 From: o3,
116 To: o1,
117 },
118 },
119 },
120 o1, o2, o3,
121 ),
122 },
123 }
124
125 for tn, tc := range testCases {
126 t.Run(tn, func(t *testing.T) {
127 g := New()
128 for _, vertex := range tc.vertices {
129 g.AddVertex(vertex)
130 }
131 for _, edge := range tc.edges {
132 g.AddEdge(edge.From, edge.To)
133 }
134 actual, err := g.Sort()
135 if tc.expectedError != nil {
136 assert.EqualError(t, tc.expectedError, err.Error())
137 return
138 }
139 assert.NoError(t, err)
140 testutil.AssertEqual(t, tc.expected, actual)
141
142
143 actual, err = g.Sort()
144 assert.NoError(t, err)
145 testutil.AssertEqual(t, tc.expected, actual)
146 })
147 }
148 }
149
150 func TestGraphDependencies(t *testing.T) {
151 testCases := map[string]struct {
152 vertices object.ObjMetadataSet
153 edges []Edge
154 from object.ObjMetadata
155 expected object.ObjMetadataSet
156 }{
157 "no dependencies": {
158 vertices: object.ObjMetadataSet{o1, o2, o3},
159 edges: []Edge{
160 {From: o1, To: o2},
161 {From: o1, To: o3},
162 {From: o2, To: o3},
163 },
164 from: o3,
165 expected: object.ObjMetadataSet{},
166 },
167 "one dependency": {
168 vertices: object.ObjMetadataSet{o1, o2, o3},
169 edges: []Edge{
170 {From: o1, To: o2},
171 {From: o1, To: o3},
172 {From: o2, To: o3},
173 },
174 from: o2,
175 expected: object.ObjMetadataSet{o3},
176 },
177 "two dependencies": {
178 vertices: object.ObjMetadataSet{o1, o2, o3},
179 edges: []Edge{
180 {From: o1, To: o2},
181 {From: o1, To: o3},
182 {From: o2, To: o3},
183 },
184 from: o1,
185 expected: object.ObjMetadataSet{o2, o3},
186 },
187 }
188
189 for tn, tc := range testCases {
190 t.Run(tn, func(t *testing.T) {
191 g := New()
192 for _, vertex := range tc.vertices {
193 g.AddVertex(vertex)
194 }
195 for _, edge := range tc.edges {
196 g.AddEdge(edge.From, edge.To)
197 }
198
199 testutil.AssertEqual(t, tc.expected, g.Dependencies(tc.from))
200 })
201 }
202 }
203
204 func TestGraphDependents(t *testing.T) {
205 testCases := map[string]struct {
206 vertices object.ObjMetadataSet
207 edges []Edge
208 to object.ObjMetadata
209 expected object.ObjMetadataSet
210 }{
211 "no dependents": {
212 vertices: object.ObjMetadataSet{o1, o2, o3},
213 edges: []Edge{
214 {From: o1, To: o2},
215 {From: o1, To: o3},
216 {From: o2, To: o3},
217 },
218 to: o1,
219 expected: object.ObjMetadataSet{},
220 },
221 "one dependent": {
222 vertices: object.ObjMetadataSet{o1, o2, o3},
223 edges: []Edge{
224 {From: o1, To: o2},
225 {From: o1, To: o3},
226 {From: o2, To: o3},
227 },
228 to: o2,
229 expected: object.ObjMetadataSet{o1},
230 },
231 "two dependents": {
232 vertices: object.ObjMetadataSet{o1, o2, o3},
233 edges: []Edge{
234 {From: o1, To: o2},
235 {From: o1, To: o3},
236 {From: o2, To: o3},
237 },
238 to: o3,
239 expected: object.ObjMetadataSet{o1, o2},
240 },
241 }
242
243 for tn, tc := range testCases {
244 t.Run(tn, func(t *testing.T) {
245 g := New()
246 for _, vertex := range tc.vertices {
247 g.AddVertex(vertex)
248 }
249 for _, edge := range tc.edges {
250 g.AddEdge(edge.From, edge.To)
251 }
252
253 testutil.AssertEqual(t, tc.expected, g.Dependents(tc.to))
254 })
255 }
256 }
257
View as plain text