depends.go

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

     1  // Copyright 2021 The Kubernetes Authors.
     2  // SPDX-License-Identifier: Apache-2.0
     3  
     4  // This package provides a object sorting functionality
     5  // based on the explicit "depends-on" annotation, and
     6  // implicit object dependencies like namespaces and CRD's.
     7  package graph
     8  
     9  import (
    10  	"sort"
    11  
    12  	"k8s.io/apimachinery/pkg/apis/meta/v1/unstructured"
    13  	"k8s.io/klog/v2"
    14  	"sigs.k8s.io/cli-utils/pkg/multierror"
    15  	"sigs.k8s.io/cli-utils/pkg/object"
    16  	"sigs.k8s.io/cli-utils/pkg/object/dependson"
    17  	"sigs.k8s.io/cli-utils/pkg/object/mutation"
    18  	"sigs.k8s.io/cli-utils/pkg/object/validation"
    19  	"sigs.k8s.io/cli-utils/pkg/ordering"
    20  )
    21  
    22  // DependencyGraph returns a new graph, populated with the supplied objects as
    23  // vetices and edges built from their dependencies.
    24  func DependencyGraph(objs object.UnstructuredSet) (*Graph, error) {
    25  	g := New()
    26  	if len(objs) == 0 {
    27  		return g, nil
    28  	}
    29  	var errors []error
    30  
    31  	// Convert to IDs (same length & order as objs)
    32  	// This is simply an optimiation to avoid repeating obj -> id conversion.
    33  	ids := object.UnstructuredSetToObjMetadataSet(objs)
    34  
    35  	// Add objects as graph vertices
    36  	addVertices(g, ids)
    37  	// Add dependencies as graph edges
    38  	addCRDEdges(g, objs, ids)
    39  	addNamespaceEdges(g, objs, ids)
    40  	if err := addDependsOnEdges(g, objs, ids); err != nil {
    41  		errors = append(errors, err)
    42  	}
    43  	if err := addApplyTimeMutationEdges(g, objs, ids); err != nil {
    44  		errors = append(errors, err)
    45  	}
    46  	if len(errors) > 0 {
    47  		return g, multierror.Wrap(errors...)
    48  	}
    49  	return g, nil
    50  }
    51  
    52  // HydrateSetList takes a list of sets of ids and a set of objects and returns
    53  // a list of set of objects. The output set list will be the same order as the
    54  // input set list, but with IDs converted into Objects. Any IDs that do not
    55  // match objects in the provided object set will be skipped (filtered) in the
    56  // output.
    57  func HydrateSetList(idSetList []object.ObjMetadataSet, objs object.UnstructuredSet) []object.UnstructuredSet {
    58  	var objSetList []object.UnstructuredSet
    59  
    60  	// Build a map of id -> obj.
    61  	objToUnstructured := map[object.ObjMetadata]*unstructured.Unstructured{}
    62  	for _, obj := range objs {
    63  		objToUnstructured[object.UnstructuredToObjMetadata(obj)] = obj
    64  	}
    65  
    66  	// Map the object metadata back to the sorted sets of unstructured objects.
    67  	// Ignore any edges that aren't part of the input set (don't wait for them).
    68  	for _, objSet := range idSetList {
    69  		currentSet := object.UnstructuredSet{}
    70  		for _, id := range objSet {
    71  			var found bool
    72  			var obj *unstructured.Unstructured
    73  			if obj, found = objToUnstructured[id]; found {
    74  				currentSet = append(currentSet, obj)
    75  			}
    76  		}
    77  		if len(currentSet) > 0 {
    78  			// Sort each set in apply order
    79  			sort.Sort(ordering.SortableUnstructureds(currentSet))
    80  			objSetList = append(objSetList, currentSet)
    81  		}
    82  	}
    83  
    84  	return objSetList
    85  }
    86  
    87  // SortObjs returns a slice of the sets of objects to apply (in order).
    88  // Each of the objects in an apply set is applied together. The order of
    89  // the returned applied sets is a topological ordering of the sets to apply.
    90  // Returns an single empty apply set if there are no objects to apply.
    91  func SortObjs(objs object.UnstructuredSet) ([]object.UnstructuredSet, error) {
    92  	var errors []error
    93  	if len(objs) == 0 {
    94  		return nil, nil
    95  	}
    96  
    97  	g, err := DependencyGraph(objs)
    98  	if err != nil {
    99  		// collect and continue
   100  		errors = multierror.Unwrap(err)
   101  	}
   102  
   103  	idSetList, err := g.Sort()
   104  	if err != nil {
   105  		errors = append(errors, err)
   106  	}
   107  
   108  	objSetList := HydrateSetList(idSetList, objs)
   109  
   110  	if len(errors) > 0 {
   111  		return objSetList, multierror.Wrap(errors...)
   112  	}
   113  	return objSetList, nil
   114  }
   115  
   116  // ReverseSortObjs is the same as SortObjs but using reverse ordering.
   117  func ReverseSortObjs(objs object.UnstructuredSet) ([]object.UnstructuredSet, error) {
   118  	// Sorted objects using normal ordering.
   119  	s, err := SortObjs(objs)
   120  	if err != nil {
   121  		return s, err
   122  	}
   123  	ReverseSetList(s)
   124  	return s, nil
   125  }
   126  
   127  // ReverseSetList deep reverses of a list of object lists
   128  func ReverseSetList(setList []object.UnstructuredSet) {
   129  	// Reverse the ordering of the object sets using swaps.
   130  	for i, j := 0, len(setList)-1; i < j; i, j = i+1, j-1 {
   131  		setList[i], setList[j] = setList[j], setList[i]
   132  	}
   133  	// Reverse the ordering of the objects in each set using swaps.
   134  	for _, set := range setList {
   135  		for i, j := 0, len(set)-1; i < j; i, j = i+1, j-1 {
   136  			set[i], set[j] = set[j], set[i]
   137  		}
   138  	}
   139  }
   140  
   141  // addVertices adds all the IDs in the set as graph vertices.
   142  func addVertices(g *Graph, ids object.ObjMetadataSet) {
   143  	for _, id := range ids {
   144  		klog.V(3).Infof("adding vertex: %s", id)
   145  		g.AddVertex(id)
   146  	}
   147  }
   148  
   149  // addApplyTimeMutationEdges updates the graph with edges from objects
   150  // with an explicit "apply-time-mutation" annotation.
   151  // The objs and ids must match in order and length (optimization).
   152  func addApplyTimeMutationEdges(g *Graph, objs object.UnstructuredSet, ids object.ObjMetadataSet) error {
   153  	var errors []error
   154  	for i, obj := range objs {
   155  		if !mutation.HasAnnotation(obj) {
   156  			continue
   157  		}
   158  		id := ids[i]
   159  		subs, err := mutation.ReadAnnotation(obj)
   160  		if err != nil {
   161  			klog.V(3).Infof("failed to add edges from: %s: %v", id, err)
   162  			errors = append(errors, validation.NewError(err, id))
   163  			continue
   164  		}
   165  		seen := make(map[object.ObjMetadata]struct{})
   166  		var objErrors []error
   167  		for _, sub := range subs {
   168  			dep := sub.SourceRef.ToObjMetadata()
   169  			// Duplicate dependencies can be safely skipped.
   170  			if _, found := seen[dep]; found {
   171  				continue
   172  			}
   173  			// Mark as seen
   174  			seen[dep] = struct{}{}
   175  			// Require dependencies to be in the same resource group.
   176  			// Waiting for external dependencies isn't implemented (yet).
   177  			if !ids.Contains(dep) {
   178  				err := object.InvalidAnnotationError{
   179  					Annotation: mutation.Annotation,
   180  					Cause: ExternalDependencyError{
   181  						Edge: Edge{
   182  							From: id,
   183  							To:   dep,
   184  						},
   185  					},
   186  				}
   187  				objErrors = append(objErrors, err)
   188  				klog.V(3).Infof("failed to add edges: %v", err)
   189  				continue
   190  			}
   191  			klog.V(3).Infof("adding edge from: %s, to: %s", id, dep)
   192  			g.AddEdge(id, dep)
   193  		}
   194  		if len(objErrors) > 0 {
   195  			errors = append(errors,
   196  				validation.NewError(multierror.Wrap(objErrors...), id))
   197  		}
   198  	}
   199  	if len(errors) > 0 {
   200  		return multierror.Wrap(errors...)
   201  	}
   202  	return nil
   203  }
   204  
   205  // addDependsOnEdges updates the graph with edges from objects
   206  // with an explicit "depends-on" annotation.
   207  // The objs and ids must match in order and length (optimization).
   208  func addDependsOnEdges(g *Graph, objs object.UnstructuredSet, ids object.ObjMetadataSet) error {
   209  	var errors []error
   210  	for i, obj := range objs {
   211  		if !dependson.HasAnnotation(obj) {
   212  			continue
   213  		}
   214  		id := ids[i]
   215  		deps, err := dependson.ReadAnnotation(obj)
   216  		if err != nil {
   217  			klog.V(3).Infof("failed to add edges from: %s: %v", id, err)
   218  			errors = append(errors, validation.NewError(err, id))
   219  			continue
   220  		}
   221  		seen := make(map[object.ObjMetadata]struct{})
   222  		var objErrors []error
   223  		for _, dep := range deps {
   224  			// Duplicate dependencies in the same annotation are not allowed.
   225  			// Having duplicates won't break the graph, but skip it anyway.
   226  			if _, found := seen[dep]; found {
   227  				err := object.InvalidAnnotationError{
   228  					Annotation: dependson.Annotation,
   229  					Cause: DuplicateDependencyError{
   230  						Edge: Edge{
   231  							From: id,
   232  							To:   dep,
   233  						},
   234  					},
   235  				}
   236  				objErrors = append(objErrors, err)
   237  				klog.V(3).Infof("failed to add edges from: %s: %v", id, err)
   238  				continue
   239  			}
   240  			// Mark as seen
   241  			seen[dep] = struct{}{}
   242  			// Require dependencies to be in the same resource group.
   243  			// Waiting for external dependencies isn't implemented (yet).
   244  			if !ids.Contains(dep) {
   245  				err := object.InvalidAnnotationError{
   246  					Annotation: dependson.Annotation,
   247  					Cause: ExternalDependencyError{
   248  						Edge: Edge{
   249  							From: id,
   250  							To:   dep,
   251  						},
   252  					},
   253  				}
   254  				objErrors = append(objErrors, err)
   255  				klog.V(3).Infof("failed to add edges: %v", err)
   256  				continue
   257  			}
   258  			klog.V(3).Infof("adding edge from: %s, to: %s", id, dep)
   259  			g.AddEdge(id, dep)
   260  		}
   261  		if len(objErrors) > 0 {
   262  			errors = append(errors,
   263  				validation.NewError(multierror.Wrap(objErrors...), id))
   264  		}
   265  	}
   266  	if len(errors) > 0 {
   267  		return multierror.Wrap(errors...)
   268  	}
   269  	return nil
   270  }
   271  
   272  // addCRDEdges adds edges to the dependency graph from custom
   273  // resources to their definitions to ensure the CRD's exist
   274  // before applying the custom resources created with the definition.
   275  // The objs and ids must match in order and length (optimization).
   276  func addCRDEdges(g *Graph, objs object.UnstructuredSet, ids object.ObjMetadataSet) {
   277  	crds := map[string]object.ObjMetadata{}
   278  	// First create a map of all the CRD's.
   279  	for i, u := range objs {
   280  		if object.IsCRD(u) {
   281  			groupKind, found := object.GetCRDGroupKind(u)
   282  			if found {
   283  				crds[groupKind.String()] = ids[i]
   284  			}
   285  		}
   286  	}
   287  	// Iterate through all resources to see if we are applying any
   288  	// custom resources defined by previously recorded CRD's.
   289  	for i, u := range objs {
   290  		gvk := u.GroupVersionKind()
   291  		groupKind := gvk.GroupKind()
   292  		if to, found := crds[groupKind.String()]; found {
   293  			from := ids[i]
   294  			klog.V(3).Infof("adding edge from: custom resource %s, to CRD: %s", from, to)
   295  			g.AddEdge(from, to)
   296  		}
   297  	}
   298  }
   299  
   300  // addNamespaceEdges adds edges to the dependency graph from namespaced
   301  // objects to the namespace objects. Ensures the namespaces exist
   302  // before the resources in those namespaces are applied.
   303  // The objs and ids must match in order and length (optimization).
   304  func addNamespaceEdges(g *Graph, objs object.UnstructuredSet, ids object.ObjMetadataSet) {
   305  	namespaces := map[string]object.ObjMetadata{}
   306  	// First create a map of all the namespaces objects live in.
   307  	for i, obj := range objs {
   308  		if object.IsKindNamespace(obj) {
   309  			namespace := obj.GetName()
   310  			namespaces[namespace] = ids[i]
   311  		}
   312  	}
   313  	// Next, if the namespace of a namespaced object is being applied,
   314  	// then create an edge from the namespaced object to its namespace.
   315  	for i, obj := range objs {
   316  		if object.IsNamespaced(obj) {
   317  			objNamespace := obj.GetNamespace()
   318  			if to, found := namespaces[objNamespace]; found {
   319  				from := ids[i]
   320  				klog.V(3).Infof("adding edge from: %s to namespace: %s", from, to)
   321  				g.AddEdge(from, to)
   322  			}
   323  		}
   324  	}
   325  }
   326
View as plain text