cli-utils/pkg/object/graph/graph_test.go

// Copyright 2020 The Kubernetes Authors.
// SPDX-License-Identifier: Apache-2.0

// This package provides a graph data struture
// and graph functionality.
package graph

import (
	"testing"

	"github.com/fluxcd/cli-utils/pkg/object"
	"github.com/fluxcd/cli-utils/pkg/object/validation"
	"github.com/fluxcd/cli-utils/pkg/testutil"
	"github.com/stretchr/testify/assert"
	"k8s.io/apimachinery/pkg/runtime/schema"
)

var (
	o1 = object.ObjMetadata{Name: "obj1", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
	o2 = object.ObjMetadata{Name: "obj2", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
	o3 = object.ObjMetadata{Name: "obj3", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
	o4 = object.ObjMetadata{Name: "obj4", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
	o5 = object.ObjMetadata{Name: "obj5", GroupKind: schema.GroupKind{Group: "test", Kind: "foo"}}
)

var (
	e1 = Edge{From: o1, To: o2}
	e2 = Edge{From: o2, To: o3}
	e3 = Edge{From: o1, To: o3}
	e4 = Edge{From: o3, To: o4}
	e5 = Edge{From: o2, To: o4}
	e6 = Edge{From: o2, To: o1}
	e7 = Edge{From: o3, To: o1}
	e8 = Edge{From: o4, To: o5}
)

func TestObjectGraphSort(t *testing.T) {
	testCases := map[string]struct {
		vertices      object.ObjMetadataSet
		edges         []Edge
		expected      []object.ObjMetadataSet
		expectedError error
	}{
		"one edge": {
			vertices: object.ObjMetadataSet{o1, o2},
			edges:    []Edge{e1},
			expected: []object.ObjMetadataSet{{o2}, {o1}},
		},
		"two edges": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges:    []Edge{e1, e2},
			expected: []object.ObjMetadataSet{{o3}, {o2}, {o1}},
		},
		"three edges": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges:    []Edge{e1, e3, e2},
			expected: []object.ObjMetadataSet{{o3}, {o2}, {o1}},
		},
		"four edges": {
			vertices: object.ObjMetadataSet{o1, o2, o3, o4},
			edges:    []Edge{e1, e2, e4, e5},
			expected: []object.ObjMetadataSet{{o4}, {o3}, {o2}, {o1}},
		},
		"five edges": {
			vertices: object.ObjMetadataSet{o1, o2, o3, o4},
			edges:    []Edge{e5, e1, e3, e2, e4},
			expected: []object.ObjMetadataSet{{o4}, {o3}, {o2}, {o1}},
		},
		"no edges means all in the same first set": {
			vertices: object.ObjMetadataSet{o1, o2, o3, o4},
			edges:    []Edge{},
			expected: []object.ObjMetadataSet{{o4, o3, o2, o1}},
		},
		"multiple objects in first set": {
			vertices: object.ObjMetadataSet{o1, o2, o3, o4, o5},
			edges:    []Edge{e1, e2, e5, e8},
			expected: []object.ObjMetadataSet{{o5, o3}, {o4}, {o2}, {o1}},
		},
		"simple cycle in graph is an error": {
			vertices: object.ObjMetadataSet{o1, o2},
			edges:    []Edge{e1, e6},
			expected: []object.ObjMetadataSet{},
			expectedError: validation.NewError(
				CyclicDependencyError{
					Edges: []Edge{
						{
							From: o1,
							To:   o2,
						},
						{
							From: o2,
							To:   o1,
						},
					},
				},
				o1, o2,
			),
		},
		"multi-edge cycle in graph is an error": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges:    []Edge{e1, e2, e7},
			expected: []object.ObjMetadataSet{},
			expectedError: validation.NewError(
				CyclicDependencyError{
					Edges: []Edge{
						{
							From: o1,
							To:   o2,
						},
						{
							From: o2,
							To:   o3,
						},
						{
							From: o3,
							To:   o1,
						},
					},
				},
				o1, o2, o3,
			),
		},
	}

	for tn, tc := range testCases {
		t.Run(tn, func(t *testing.T) {
			g := New()
			for _, vertex := range tc.vertices {
				g.AddVertex(vertex)
			}
			for _, edge := range tc.edges {
				g.AddEdge(edge.From, edge.To)
			}
			actual, err := g.Sort()
			if tc.expectedError != nil {
				assert.EqualError(t, tc.expectedError, err.Error())
				return
			}
			assert.NoError(t, err)
			testutil.AssertEqual(t, tc.expected, actual)

			// verify sort is repeatable & non-destructive
			actual, err = g.Sort()
			assert.NoError(t, err)
			testutil.AssertEqual(t, tc.expected, actual)
		})
	}
}

func TestGraphDependencies(t *testing.T) {
	testCases := map[string]struct {
		vertices object.ObjMetadataSet
		edges    []Edge
		from     object.ObjMetadata
		expected object.ObjMetadataSet
	}{
		"no dependencies": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges: []Edge{
				{From: o1, To: o2},
				{From: o1, To: o3},
				{From: o2, To: o3},
			},
			from:     o3,
			expected: object.ObjMetadataSet{},
		},
		"one dependency": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges: []Edge{
				{From: o1, To: o2},
				{From: o1, To: o3},
				{From: o2, To: o3},
			},
			from:     o2,
			expected: object.ObjMetadataSet{o3},
		},
		"two dependencies": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges: []Edge{
				{From: o1, To: o2},
				{From: o1, To: o3},
				{From: o2, To: o3},
			},
			from:     o1,
			expected: object.ObjMetadataSet{o2, o3},
		},
	}

	for tn, tc := range testCases {
		t.Run(tn, func(t *testing.T) {
			g := New()
			for _, vertex := range tc.vertices {
				g.AddVertex(vertex)
			}
			for _, edge := range tc.edges {
				g.AddEdge(edge.From, edge.To)
			}

			testutil.AssertEqual(t, tc.expected, g.Dependencies(tc.from))
		})
	}
}

func TestGraphDependents(t *testing.T) {
	testCases := map[string]struct {
		vertices object.ObjMetadataSet
		edges    []Edge
		to       object.ObjMetadata
		expected object.ObjMetadataSet
	}{
		"no dependents": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges: []Edge{
				{From: o1, To: o2},
				{From: o1, To: o3},
				{From: o2, To: o3},
			},
			to:       o1,
			expected: object.ObjMetadataSet{},
		},
		"one dependent": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges: []Edge{
				{From: o1, To: o2},
				{From: o1, To: o3},
				{From: o2, To: o3},
			},
			to:       o2,
			expected: object.ObjMetadataSet{o1},
		},
		"two dependents": {
			vertices: object.ObjMetadataSet{o1, o2, o3},
			edges: []Edge{
				{From: o1, To: o2},
				{From: o1, To: o3},
				{From: o2, To: o3},
			},
			to:       o3,
			expected: object.ObjMetadataSet{o1, o2},
		},
	}

	for tn, tc := range testCases {
		t.Run(tn, func(t *testing.T) {
			g := New()
			for _, vertex := range tc.vertices {
				g.AddVertex(vertex)
			}
			for _, edge := range tc.edges {
				g.AddEdge(edge.From, edge.To)
			}

			testutil.AssertEqual(t, tc.expected, g.Dependents(tc.to))
		})
	}
}