sort.go

Documentation: edge-infra.dev/pkg/k8s/object

     1  package object
     2  
     3  import (
     4  	"slices"
     5  
     6  	"k8s.io/apimachinery/pkg/runtime/schema"
     7  
     8  	"sigs.k8s.io/cli-utils/pkg/object"
     9  	"sigs.k8s.io/controller-runtime/pkg/client"
    10  )
    11  
    12  type kindOrder struct {
    13  	First []string
    14  	Last  []string
    15  }
    16  
    17  // reconcileOrder holds the list of Kubernetes native kinds based on the order
    18  // they are reconciled in, for coarse dependency ordering on apply.
    19  var reconcileOrder = kindOrder{
    20  	First: []string{
    21  		"CustomResourceDefinition",
    22  		"Namespace",
    23  		"ResourceQuota",
    24  		"StorageClass",
    25  		"ServiceAccount",
    26  		"PodSecurityPolicy",
    27  		"Role",
    28  		"ClusterRole",
    29  		"RoleBinding",
    30  		"ClusterRoleBinding",
    31  		"ConfigMap",
    32  		"Secret",
    33  		"Service",
    34  		"LimitRange",
    35  		"PriorityClass",
    36  		"Deployment",
    37  		"StatefulSet",
    38  		"CronJob",
    39  		"PodDisruptionBudget",
    40  	},
    41  	Last: []string{
    42  		"MutatingWebhookConfiguration",
    43  		"ValidatingWebhookConfiguration",
    44  	},
    45  }
    46  
    47  // Sort does an in-place sort of objects.
    48  func Sort[O client.Object](objs []O) {
    49  	slices.SortFunc(objs, LessThan)
    50  }
    51  
    52  // Sort does an in-place sort of object metadata.
    53  func SortObjMeta(objMetas object.ObjMetadataSet) {
    54  	slices.SortFunc(objMetas, lessThan)
    55  }
    56  
    57  // LessThan returns true if i < j.
    58  func LessThan[O client.Object](i, j O) int {
    59  	return lessThan(
    60  		object.ObjMetadata{
    61  			GroupKind: i.GetObjectKind().GroupVersionKind().GroupKind(),
    62  			Namespace: i.GetNamespace(),
    63  			Name:      i.GetName(),
    64  		},
    65  		object.ObjMetadata{
    66  			GroupKind: j.GetObjectKind().GroupVersionKind().GroupKind(),
    67  			Namespace: j.GetNamespace(),
    68  			Name:      j.GetName(),
    69  		},
    70  	)
    71  }
    72  
    73  func lessThan(i, j object.ObjMetadata) int {
    74  	if !equals(i.GroupKind, j.GroupKind) {
    75  		cmp, resultFound := compareGroupKind(i.GroupKind, j.GroupKind)
    76  		if resultFound {
    77  			return cmp
    78  		}
    79  	}
    80  	// If we tied, compare Namespace + Name for deterministic output
    81  	if i.Namespace != j.Namespace {
    82  		if i.Namespace < j.Namespace {
    83  			return -1
    84  		}
    85  		return 1
    86  	}
    87  	if i.Name < j.Name {
    88  		return -1
    89  	}
    90  	if i.Name > j.Name {
    91  		return 1
    92  	}
    93  	return 0
    94  }
    95  
    96  func compareGroupKind(i, j schema.GroupKind) (int, bool) {
    97  	idxI, idxJ := getIndexByKind(i.Kind), getIndexByKind(j.Kind)
    98  	if idxI != idxJ {
    99  		return idxI - idxJ, true
   100  	}
   101  	if i.Group != j.Group {
   102  		if i.Group < j.Group {
   103  			return -1, true
   104  		}
   105  		return 1, true
   106  	}
   107  	if i.Kind < j.Kind {
   108  		return -1, true
   109  	}
   110  	if i.Kind > j.Kind {
   111  		return 1, true
   112  	}
   113  	return 0, false // need to do more checks to determine which is less than
   114  }
   115  
   116  func equals(i, j schema.GroupKind) bool {
   117  	return i.Group == j.Group && i.Kind == j.Kind
   118  }
   119  
   120  func computeKind2index() map[string]int {
   121  	// Based on cli-utils/pkg/ordering/sort.go
   122  	// An attempt to order things to help k8s, e.g. a Service should come before
   123  	// things that refer to it, Namespace should be first.
   124  	// In some cases order is specified to provide determinism.
   125  
   126  	kind2indexResult := make(map[string]int, len(reconcileOrder.First)+len(reconcileOrder.Last))
   127  	for i, n := range reconcileOrder.First {
   128  		kind2indexResult[n] = -len(reconcileOrder.First) + i
   129  	}
   130  	for i, n := range reconcileOrder.Last {
   131  		kind2indexResult[n] = 1 + i
   132  	}
   133  	return kind2indexResult
   134  }
   135  
   136  // getIndexByKind returns the index of the kind respecting the order
   137  func getIndexByKind(kind string) int {
   138  	return computeKind2index()[kind]
   139  }
   140
View as plain text