...

Source file src/sigs.k8s.io/cli-utils/pkg/object/graph/graph_test.go

Documentation: sigs.k8s.io/cli-utils/pkg/object/graph

     1  // Copyright 2020 The Kubernetes Authors.
     2  // SPDX-License-Identifier: Apache-2.0
     3  
     4  // This package provides a graph data struture
     5  // and graph functionality.
     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  			// verify sort is repeatable & non-destructive
   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