normalizer.go

Documentation: edge-infra.dev/pkg/edge/gitops/fns/normalizer

     1  // Package normalizer contains the logic for the kpt fn so that it can be
     2  // leveraged in non-kpt contexts
     3  package normalizer
     4  
     5  import (
     6  	"fmt"
     7  	"sort"
     8  	"strings"
     9  	"sync"
    10  
    11  	"sigs.k8s.io/kustomize/kyaml/kio/filters"
    12  	"sigs.k8s.io/kustomize/kyaml/kio/kioutil"
    13  	"sigs.k8s.io/kustomize/kyaml/yaml"
    14  
    15  	"edge-infra.dev/pkg/edge/gitops/fn/v1alpha1"
    16  )
    17  
    18  // x is a structure that protects concurrent read/writes to the external kyaml library.
    19  //
    20  // A RWMutex (read/write mutex) is used since write locks shouldn't happen after all yaml
    21  // objects have been seen once.
    22  var x = struct {
    23  	sync.RWMutex
    24  
    25  	// ff is simply a zeroed filters.FormatFilter struct.
    26  	ff filters.FormatFilter
    27  
    28  	// For reference, some example values are provided for the whitelist objects.
    29  	//
    30  	// The Apis and Kinds whitelist values are set to nil since the library only checks the map for the key's existence.
    31  	// The Fields whitelist key is a json path to the sequence field. The Fields whitelist value is the associative key.
    32  	//
    33  	// Since the whitelists are maps, we don't need to use pointers to the objects, which is nice.
    34  	wlsApis   map[string]interface{} // yaml.WhitelistedListSortApis["kubernetes-client.io/v1"] = nil
    35  	wlsKinds  map[string]interface{} // yaml.WhitelistedListSortKinds["ExternalSecret"] = nil
    36  	wlsFields map[string]string      // yaml.WhitelistedListSortFields[".spec.data"] = "name"
    37  }{
    38  	wlsApis:   yaml.WhitelistedListSortApis,
    39  	wlsKinds:  yaml.WhitelistedListSortKinds,
    40  	wlsFields: yaml.WhitelistedListSortFields,
    41  }
    42  
    43  func init() {
    44  	x.Lock()
    45  	defer x.Unlock()
    46  	const skey = "secretKey"
    47  	for _, key := range yaml.AssociativeSequenceKeys {
    48  		if key == skey {
    49  			// key is already in yaml.AssociativeSequenceKeys
    50  			return
    51  		}
    52  	}
    53  	yaml.AssociativeSequenceKeys = append(yaml.AssociativeSequenceKeys, skey)
    54  }
    55  
    56  // setWhitelistedListSortMaps dynamically sets the following global maps from the kyaml library in a threadsafe manner:
    57  //   - yaml.WhitelistedListSortApis
    58  //   - yaml.WhitelistedListSortKinds
    59  //   - yaml.WhitelistedListSortFields
    60  func setWhitelistedListSortMaps(nodes []*yaml.RNode) error {
    61  	// Provide a detailed error when field values conflict.
    62  	const msg = "WhitelistedListSortFields contains key %q with value %q, but another yaml document contains conflicting value %q for that key."
    63  	var (
    64  		apis      = make(map[string]bool)
    65  		kinds     = make(map[string]bool)
    66  		fields    = make(map[string]string)
    67  		fieldErrs *conflictingWhitelistedListSortFieldsError
    68  
    69  		// The hasApis, hasKinds, and hasFields boolians remain true if the whitelists do not need to be modified.
    70  		hasApis   = true
    71  		hasKinds  = true
    72  		hasFields = true
    73  	)
    74  
    75  	for _, node := range nodes {
    76  		meta, err := node.GetMeta()
    77  		if err != nil {
    78  			return err
    79  		}
    80  		apis[meta.TypeMeta.APIVersion] = true
    81  		kinds[meta.TypeMeta.Kind] = true
    82  		findSequenceNodeFieldsRecursive(node.YNode(), "", fields)
    83  	}
    84  
    85  	// Read lock to see if writing is necessary.
    86  	x.RLock()
    87  	for api := range apis {
    88  		if _, found := x.wlsApis[api]; !found {
    89  			hasApis = false
    90  		}
    91  	}
    92  	for kind := range kinds {
    93  		if _, found := x.wlsKinds[kind]; !found {
    94  			hasKinds = false
    95  		}
    96  	}
    97  	for field, value := range fields {
    98  		if existing, found := x.wlsFields[field]; !found {
    99  			hasFields = false
   100  		} else if value != existing {
   101  			var info = fmt.Sprintf(msg, field, existing, value)
   102  			if fieldErrs == nil {
   103  				fieldErrs = &conflictingWhitelistedListSortFieldsError{
   104  					info: make(map[string]interface{}),
   105  				}
   106  			}
   107  			fieldErrs.info[info] = nil
   108  		}
   109  	}
   110  	x.RUnlock()
   111  
   112  	// Exit early before write locking.
   113  	if fieldErrs != nil {
   114  		return fieldErrs
   115  	} else if hasApis && hasKinds && hasFields {
   116  		return nil
   117  	}
   118  
   119  	// Whitelist the yaml information using the write lock.
   120  	//
   121  	// Compared to write locking, overwriting all the values for the three maps is negligible performance wise, so we lock once
   122  	// and overwrite everything even if only 1 value needs to be added for one of the maps.
   123  	x.Lock()
   124  	defer x.Unlock()
   125  
   126  	for api := range apis {
   127  		x.wlsApis[api] = nil
   128  	}
   129  	for kind := range kinds {
   130  		x.wlsKinds[kind] = nil
   131  	}
   132  	for field, value := range fields {
   133  		if existing, found := x.wlsFields[field]; !found {
   134  			x.wlsFields[field] = value
   135  		} else if value != existing {
   136  			// Recheck that the fields did not go bad since we unlocked before writing.
   137  			var info = fmt.Sprintf(msg, field, existing, value)
   138  			if fieldErrs == nil {
   139  				fieldErrs = &conflictingWhitelistedListSortFieldsError{
   140  					info: make(map[string]interface{}),
   141  				}
   142  			}
   143  			fieldErrs.info[info] = nil
   144  		}
   145  	}
   146  	if fieldErrs != nil {
   147  		return fieldErrs
   148  	}
   149  	return nil
   150  }
   151  
   152  // findSequenceNodeFieldsRecursive dynamically fills the provided 'fields' map with sequence node json paths and their associative keys.
   153  //
   154  // To run this function, provide an empty string for 'path' and a non-nil map for 'fields'. This function panics if you provide a nil map.
   155  func findSequenceNodeFieldsRecursive(node *yaml.Node, path string, fields map[string]string) {
   156  	switch node.Kind {
   157  	case yaml.SequenceNode:
   158  		// GetAssociativeKey checks the yaml.AssociativeSequenceKeys variable which only contains "name".
   159  		//
   160  		// In the future we may need to write to that variable. If that happens, we'll need to protect it with a RWMutex like we do with the whitelists.
   161  		if v := yaml.NewRNode(node).GetAssociativeKey(); v != "" {
   162  			fields[path] = v // ex fields[".spec.data"] = "name"
   163  		}
   164  	case yaml.MappingNode:
   165  		// MappingNode Content is strange. The node.Content object has two entries per node.
   166  		//
   167  		// The first entry contains the name of the field.
   168  		//
   169  		// The second entry contains the values of the field.
   170  		for i := range node.Content {
   171  			if i%2 != 0 {
   172  				// Skip every other node in Content.
   173  				continue
   174  			}
   175  			var fieldName = node.Content[i].Value
   176  			// Create the next json path for the mapping nodes. Only mapping nodes go in a json path.
   177  			var nextPath = fmt.Sprintf("%s.%s", path, fieldName)
   178  
   179  			findSequenceNodeFieldsRecursive(node.Content[i+1], nextPath, fields)
   180  		}
   181  	}
   182  }
   183  
   184  // Normalization modifies the yaml.RNode slice for consistent serialization. Without normalization, yaml.RNode fields are
   185  // serialized in mostly the same order they were deserialized (or constructed), and with inconsistencies in sequence nodes.
   186  //
   187  // Normalize also sorts the slice lexiographically according to the kioutil.PathAnnotation and then by the serialized yaml for
   188  // nodes with identical paths. The order of Normalize output must be kept when nodes with identical paths are joined together.
   189  //
   190  // NOTE: To use the Normalize function on nodes whose kioutil.PathAnnotation has been stripped, you must only provide 'input'
   191  // nodes with the same destination path.
   192  func Normalize(input []*yaml.RNode) error {
   193  	err := setWhitelistedListSortMaps(input)
   194  	if err != nil {
   195  		return err
   196  	}
   197  
   198  	// Normalize using the format filter.  Need to use the read lock since the format filter touches the whitelists.
   199  	x.RLock()
   200  	_, err = x.ff.Filter(input)
   201  	x.RUnlock()
   202  	if err != nil {
   203  		return err
   204  	}
   205  
   206  	// Sort the order of the nodes so that yaml with concatenated documents are serialized in the same order of documents.
   207  	sortRNodes(input)
   208  
   209  	// err = sanitizePathAnnotations(input)
   210  	// if err != nil {
   211  	// 	return err
   212  	// }
   213  
   214  	// Add quotes to cpu limits
   215  	quoteCPULimitsForNodes(input)
   216  	return nil
   217  }
   218  
   219  func quoteCPULimitsForNodes(input []*yaml.RNode) {
   220  	for i := range input {
   221  		quoteCPULimits(input[i].YNode())
   222  	}
   223  }
   224  
   225  // may be needed later, commented because the linter hates unused functions
   226  // basically both bazel and go hate colons in filenames
   227  // this didm't work by itself because the sorter is reintroducing them
   228  // if bad filenames get introduced again we may resurrevt this
   229  // func sanitizePathAnnotations(nodes []*yaml.RNode) error {
   230  // 	for _, node := range nodes {
   231  // 		pathNode, err := node.Pipe(yaml.AnnotationGetter{
   232  // 			Key: kioutil.PathAnnotation,
   233  // 		})
   234  // 		if err != nil {
   235  // 			return err
   236  // 		}
   237  // 		path := yaml.GetValue(pathNode)
   238  // 		if path == "" {
   239  // 			return nil
   240  // 		}
   241  // 		newPath := strings.ReplaceAll(path, ":", "-")
   242  // 		err = node.PipeE(yaml.AnnotationSetter{
   243  // 			Key:   kioutil.PathAnnotation,
   244  // 			Value: newPath,
   245  // 		})
   246  // 		if err != nil {
   247  // 			return err
   248  // 		}
   249  // 	}
   250  // 	return nil
   251  // }
   252  
   253  // quoteCPULimits checks if the yaml file has cpu limits recursively, and adds quotes to cpu limits if it has.
   254  func quoteCPULimits(node *yaml.Node) {
   255  	if node.Kind == yaml.ScalarNode {
   256  		return
   257  	}
   258  	for i := range node.Content {
   259  		if isKey("limits", node.Content, i) {
   260  			// node.Content[i+1] contains the value of limits field
   261  			limits := node.Content[i+1]
   262  			for j := range limits.Content {
   263  				if isKey("cpu", limits.Content, j) {
   264  					limits.Content[j+1].Style = yaml.DoubleQuotedStyle
   265  				}
   266  			}
   267  		} else {
   268  			quoteCPULimits(node.Content[i])
   269  		}
   270  	}
   271  }
   272  
   273  func isKey(key string, nodes []*yaml.Node, idx int) bool {
   274  	if idx >= len(nodes)-1 {
   275  		return false
   276  	}
   277  	if nodes[idx].Value != key {
   278  		return false
   279  	}
   280  	return true
   281  }
   282  
   283  // Run calls the Normalize function for the provided RNodes. The Run function implements the fn.Function interface.
   284  //
   285  // NOTE: Due to the kyaml filters.FormatFilter.Filter function, this function normalizes the input array.
   286  func (n *Normalizer) Run(input []*yaml.RNode) (output []*yaml.RNode, err error) {
   287  	err = Normalize(input)
   288  	if err != nil {
   289  		return
   290  	}
   291  	output = input
   292  	return
   293  }
   294  
   295  // sortRNodes sorts the provided yaml.RNode slice lexiographically by the kioutil.PathAnnotation value and then by the serialized yaml for identical paths.
   296  // The provided nodes should be normalized before they are sorted by this function. This is needed so that concatenated yaml.RNode slices always serialize
   297  // in the same order.
   298  func sortRNodes(nodes []*yaml.RNode) {
   299  	// Stable sort so that nodes that shouldn't be lexiographically sorted have their ordering preserved.
   300  	sort.Stable(&rnodeSorter{n: nodes})
   301  }
   302  
   303  // rnodeSorter implements sort.Interface to efficiently sort rnodes lexiographically.
   304  type rnodeSorter struct {
   305  	// s is a slice representing serialized nodes
   306  	s []string
   307  
   308  	// p is a slice representing `kioutil.PathAnnotation` values.
   309  	p []string
   310  
   311  	// l is a slice representing whether or not a node should be lexiographically sorted
   312  	l []bool
   313  
   314  	n []*yaml.RNode
   315  }
   316  
   317  var apiVersionPrefixFnsEdgeNcrCom = fmt.Sprintf("%s/", v1alpha1.GroupVersion.Group)
   318  
   319  // lexiographicallySortAPIVersion returns true if the provided `apiVersion` should be lexiographically sorted.
   320  func lexiographicallySortAPIVersion(apiVersion string) bool {
   321  	return !strings.HasPrefix(apiVersion, apiVersionPrefixFnsEdgeNcrCom)
   322  }
   323  
   324  // Len returns the node count, and initializes the internal `s`, `p`, and `l` slices in the rnodeSorter.
   325  func (s *rnodeSorter) Len() int {
   326  	s.s = make([]string, len(s.n)) // s gets populated in the Less function.
   327  	s.p = make([]string, len(s.n))
   328  	s.l = make([]bool, len(s.n))
   329  	for k, n := range s.n {
   330  		meta, err := n.GetMeta()
   331  		if err != nil {
   332  			s.l[k] = true // lexiographically sort nodes without metadata
   333  			continue
   334  		}
   335  		s.p[k] = meta.ObjectMeta.Annotations[kioutil.PathAnnotation]
   336  		s.l[k] = lexiographicallySortAPIVersion(meta.TypeMeta.APIVersion)
   337  	}
   338  
   339  	return len(s.n)
   340  }
   341  
   342  // Less orders lexiographically by the kioutil.PathAnnotation and then by the serialized yaml for nodes with identical paths.
   343  func (s *rnodeSorter) Less(i, j int) bool {
   344  	// If the paths are not equal, we can return the lexiographic order of the paths.
   345  	if s.p[i] != s.p[j] {
   346  		return s.p[i] < s.p[j]
   347  	}
   348  
   349  	// Check if we should lexiographically sort these nodes, or preserve their order.
   350  	if !s.l[i] && !s.l[j] {
   351  		// Returning false preserves the order when using stable sort.
   352  		return false
   353  	}
   354  
   355  	// Serialize the nodes (once) and compare them lexiographically.
   356  	if s.s[i] == "" {
   357  		s.s[i], _ = s.n[i].String()
   358  	}
   359  	if s.s[j] == "" {
   360  		s.s[j], _ = s.n[j].String()
   361  	}
   362  	return s.s[i] < s.s[j]
   363  }
   364  
   365  func (s *rnodeSorter) Swap(i, j int) {
   366  	s.s[i], s.s[j] = s.s[j], s.s[i]
   367  	s.p[i], s.p[j] = s.p[j], s.p[i]
   368  	s.l[i], s.l[j] = s.l[j], s.l[i]
   369  	s.n[i], s.n[j] = s.n[j], s.n[i]
   370  }
   371  
   372  // conflictingWhitelistedListSortFieldsError is needed in case we modify yaml.AssociativeSequenceKeys in the future.
   373  type conflictingWhitelistedListSortFieldsError struct {
   374  	// info is a map since we'll probably run into many fields with the same info.
   375  	info map[string]interface{}
   376  }
   377  
   378  func (err *conflictingWhitelistedListSortFieldsError) Error() string {
   379  	const msg = "yaml.WhitelistedListSortFields does not support conflicting values for the same field."
   380  	if len(err.info) == 0 {
   381  		return msg
   382  	}
   383  	// turn the map into a slice for printing.
   384  	var s = []interface{}{msg}
   385  	for info := range err.info {
   386  		s = append(s, info)
   387  	}
   388  	return fmt.Sprint(s...)
   389  }
   390  
   391  // IsConflictingWhitelistedListSortFieldsError returns true if the error returned during normalization was
   392  // due to the yaml.WhitelistedListSortFields map being unable to accept multiple values for the same key.
   393  //
   394  // If this error is found, a developer must be alerted and code must be changed.
   395  //
   396  // NOTE: This error should not occur unless the yaml.AssociativeSequenceKeys is dynamically populated in the
   397  // future.  That object isn't currently being populated, and it only contains one key: "name".
   398  func IsConflictingWhitelistedListSortFieldsError(err error) bool {
   399  	_, b := err.(*conflictingWhitelistedListSortFieldsError)
   400  	return b
   401  }
   402
View as plain text