associative_sequence.go

Documentation: sigs.k8s.io/kustomize/kyaml/yaml/walk

     1  // Copyright 2019 The Kubernetes Authors.
     2  // SPDX-License-Identifier: Apache-2.0
     3  
     4  package walk
     5  
     6  import (
     7  	"strings"
     8  
     9  	"github.com/go-errors/errors"
    10  	"sigs.k8s.io/kustomize/kyaml/openapi"
    11  	"sigs.k8s.io/kustomize/kyaml/sets"
    12  	"sigs.k8s.io/kustomize/kyaml/yaml"
    13  )
    14  
    15  // appendListNode will append the nodes from src to dst and return dst.
    16  // src and dst should be both sequence node. key is used to call ElementSetter.
    17  // ElementSetter will use key-value pair to find and set the element in sequence
    18  // node.
    19  func appendListNode(dst, src *yaml.RNode, keys []string) (*yaml.RNode, error) {
    20  	var err error
    21  	for _, elem := range src.Content() {
    22  		// If key is empty, we know this is a scalar value and we can directly set the
    23  		// node
    24  		if keys[0] == "" {
    25  			_, err = dst.Pipe(yaml.ElementSetter{
    26  				Element: elem,
    27  				Keys:    []string{""},
    28  				Values:  []string{elem.Value},
    29  			})
    30  			if err != nil {
    31  				return nil, err
    32  			}
    33  			continue
    34  		}
    35  
    36  		// we need to get the value for key so that we can find the element to set
    37  		// in sequence.
    38  		v := []string{}
    39  		for _, key := range keys {
    40  			tmpNode := yaml.NewRNode(elem)
    41  			valueNode, err := tmpNode.Pipe(yaml.Get(key))
    42  			if err != nil {
    43  				return nil, err
    44  			}
    45  			if valueNode.IsNil() {
    46  				// no key found, directly append to dst
    47  				err = dst.PipeE(yaml.Append(elem))
    48  				if err != nil {
    49  					return nil, err
    50  				}
    51  				continue
    52  			}
    53  			v = append(v, valueNode.YNode().Value)
    54  		}
    55  
    56  		// When there are multiple keys, ElementSetter appends the node to dst
    57  		// even if the output is already in dst. We remove the node from dst to
    58  		// prevent duplicates.
    59  		if len(keys) > 1 {
    60  			_, err = dst.Pipe(yaml.ElementSetter{
    61  				Keys:   keys,
    62  				Values: v,
    63  			})
    64  			if err != nil {
    65  				return nil, err
    66  			}
    67  		}
    68  
    69  		// We use the key and value from elem to find the corresponding element in dst.
    70  		// Then we will use ElementSetter to replace the element with elem. If we cannot
    71  		// find the item, the element will be appended.
    72  		_, err = dst.Pipe(yaml.ElementSetter{
    73  			Element: elem,
    74  			Keys:    keys,
    75  			Values:  v,
    76  		})
    77  		if err != nil {
    78  			return nil, err
    79  		}
    80  	}
    81  	return dst, nil
    82  }
    83  
    84  // validateKeys returns a list of valid key-value pairs
    85  // if secondary merge key values are missing, use only the available merge keys
    86  func validateKeys(valuesList [][]string, values []string, keys []string) ([]string, []string) {
    87  	validKeys := make([]string, 0)
    88  	validValues := make([]string, 0)
    89  	validKeySet := sets.String{}
    90  	for _, values := range valuesList {
    91  		for i, v := range values {
    92  			if v != "" {
    93  				validKeySet.Insert(keys[i])
    94  			}
    95  		}
    96  	}
    97  	if validKeySet.Len() == 0 { // if values missing, fall back to primary keys
    98  		return keys, values
    99  	}
   100  	for _, k := range keys {
   101  		if validKeySet.Has(k) {
   102  			validKeys = append(validKeys, k)
   103  		}
   104  	}
   105  	for i, v := range values {
   106  		if v != "" || validKeySet.Has(keys[i]) {
   107  			validValues = append(validValues, v)
   108  		}
   109  	}
   110  	return validKeys, validValues
   111  }
   112  
   113  // mergeValues merges values together - e.g. if two containerPorts
   114  // have the same port and targetPort but one has an empty protocol
   115  // and the other doesn't, they are treated as the same containerPort
   116  func mergeValues(valuesList [][]string) [][]string {
   117  	for i, values1 := range valuesList {
   118  		for j, values2 := range valuesList {
   119  			if matched, values := match(values1, values2); matched {
   120  				valuesList[i] = values
   121  				valuesList[j] = values
   122  			}
   123  		}
   124  	}
   125  	return valuesList
   126  }
   127  
   128  // two values match if they have at least one common element and
   129  // corresponding elements only differ if one is an empty string
   130  func match(values1 []string, values2 []string) (bool, []string) {
   131  	if len(values1) != len(values2) {
   132  		return false, nil
   133  	}
   134  	var commonElement bool
   135  	var res []string
   136  	for i := range values1 {
   137  		if values1[i] == values2[i] {
   138  			commonElement = true
   139  			res = append(res, values1[i])
   140  			continue
   141  		}
   142  		if values1[i] != "" && values2[i] != "" {
   143  			return false, nil
   144  		}
   145  		if values1[i] != "" {
   146  			res = append(res, values1[i])
   147  		} else {
   148  			res = append(res, values2[i])
   149  		}
   150  	}
   151  	return commonElement, res
   152  }
   153  
   154  // setAssociativeSequenceElements recursively set the elements in the list
   155  func (l *Walker) setAssociativeSequenceElements(valuesList [][]string, keys []string, dest *yaml.RNode) (*yaml.RNode, error) {
   156  	// itemsToBeAdded contains the items that will be added to dest
   157  	itemsToBeAdded := yaml.NewListRNode()
   158  	var schema *openapi.ResourceSchema
   159  	if l.Schema != nil {
   160  		schema = l.Schema.Elements()
   161  	}
   162  	if len(keys) > 1 {
   163  		valuesList = mergeValues(valuesList)
   164  	}
   165  
   166  	// each element in valuesList is a list of values corresponding to the keys
   167  	// for example, for the following yaml:
   168  	//        - containerPort: 8080
   169  	//          protocol: UDP
   170  	//        - containerPort: 8080
   171  	//          protocol: TCP
   172  	// `keys` would be [containerPort, protocol]
   173  	// and `valuesList` would be [ [8080, UDP], [8080, TCP] ]
   174  	var validKeys []string
   175  	var validValues []string
   176  	for _, values := range valuesList {
   177  		if len(values) == 0 {
   178  			continue
   179  		}
   180  
   181  		validKeys, validValues = validateKeys(valuesList, values, keys)
   182  		val, err := Walker{
   183  			VisitKeysAsScalars:    l.VisitKeysAsScalars,
   184  			InferAssociativeLists: l.InferAssociativeLists,
   185  			Visitor:               l,
   186  			Schema:                schema,
   187  			Sources:               l.elementValueList(validKeys, validValues),
   188  			MergeOptions:          l.MergeOptions,
   189  		}.Walk()
   190  		if err != nil {
   191  			return nil, err
   192  		}
   193  
   194  		exit := false
   195  		for i, key := range validKeys {
   196  			// delete the node from **dest** if it's null or empty
   197  			if yaml.IsMissingOrNull(val) || yaml.IsEmptyMap(val) {
   198  				_, err = dest.Pipe(yaml.ElementSetter{
   199  					Keys:   validKeys,
   200  					Values: validValues,
   201  				})
   202  				if err != nil {
   203  					return nil, err
   204  				}
   205  				exit = true
   206  			} else if val.Field(key) == nil && validValues[i] != "" {
   207  				// make sure the key is set on the field
   208  				_, err = val.Pipe(yaml.SetField(key, yaml.NewScalarRNode(validValues[i])))
   209  				if err != nil {
   210  					return nil, err
   211  				}
   212  			}
   213  		}
   214  		if exit {
   215  			continue
   216  		}
   217  
   218  		// Add the val to the sequence. val will replace the item in the sequence if
   219  		// there is an item that matches all key-value pairs. Otherwise val will be appended
   220  		// the sequence.
   221  		_, err = itemsToBeAdded.Pipe(yaml.ElementSetter{
   222  			Element: val.YNode(),
   223  			Keys:    validKeys,
   224  			Values:  validValues,
   225  		})
   226  		if err != nil {
   227  			return nil, err
   228  		}
   229  	}
   230  
   231  	var err error
   232  	if len(valuesList) > 0 {
   233  		if l.MergeOptions.ListIncreaseDirection == yaml.MergeOptionsListPrepend {
   234  			// items from patches are needed to be prepended. so we append the
   235  			// dest to itemsToBeAdded
   236  			dest, err = appendListNode(itemsToBeAdded, dest, validKeys)
   237  		} else {
   238  			// append the items
   239  			dest, err = appendListNode(dest, itemsToBeAdded, validKeys)
   240  		}
   241  	}
   242  
   243  	if err != nil {
   244  		return nil, err
   245  	}
   246  	// sequence is empty
   247  	if yaml.IsMissingOrNull(dest) {
   248  		return nil, nil
   249  	}
   250  	return dest, nil
   251  }
   252  
   253  func (l *Walker) walkAssociativeSequence() (*yaml.RNode, error) {
   254  	// may require initializing the dest node
   255  	dest, err := l.Sources.setDestNode(l.VisitList(l.Sources, l.Schema, AssociativeList))
   256  	if dest == nil || err != nil {
   257  		return nil, err
   258  	}
   259  
   260  	// get the merge key(s) from schema
   261  	var strategy string
   262  	var keys []string
   263  	if l.Schema != nil {
   264  		strategy, keys = l.Schema.PatchStrategyAndKeyList()
   265  	}
   266  	if strategy == "" && len(keys) == 0 { // neither strategy nor keys present in the schema -- infer the key
   267  		// find the list of elements we need to recursively walk
   268  		key, err := l.elementKey()
   269  		if err != nil {
   270  			return nil, err
   271  		}
   272  		if key != "" {
   273  			keys = append(keys, key)
   274  		}
   275  	}
   276  
   277  	// non-primitive associative list -- merge the elements
   278  	values := l.elementValues(keys)
   279  	if len(values) != 0 || len(keys) > 0 {
   280  		return l.setAssociativeSequenceElements(values, keys, dest)
   281  	}
   282  
   283  	// primitive associative list -- merge the values
   284  	return l.setAssociativeSequenceElements(l.elementPrimitiveValues(), []string{""}, dest)
   285  }
   286  
   287  // elementKey returns the merge key to use for the associative list
   288  func (l Walker) elementKey() (string, error) {
   289  	var key string
   290  	for i := range l.Sources {
   291  		if l.Sources[i] != nil && len(l.Sources[i].Content()) > 0 {
   292  			newKey := l.Sources[i].GetAssociativeKey()
   293  			if key != "" && key != newKey {
   294  				return "", errors.Errorf(
   295  					"conflicting merge keys [%s,%s] for field %s",
   296  					key, newKey, strings.Join(l.Path, "."))
   297  			}
   298  			key = newKey
   299  		}
   300  	}
   301  	if key == "" {
   302  		return "", errors.Errorf("no merge key found for field %s",
   303  			strings.Join(l.Path, "."))
   304  	}
   305  	return key, nil
   306  }
   307  
   308  // elementValues returns a slice containing all values for the field across all elements
   309  // from all sources.
   310  // Return value slice is ordered using the original ordering from the elements, where
   311  // elements missing from earlier sources appear later.
   312  func (l Walker) elementValues(keys []string) [][]string {
   313  	// use slice to to keep elements in the original order
   314  	var returnValues [][]string
   315  	var seen sets.StringList
   316  
   317  	// if we are doing append, dest node should be the first.
   318  	// otherwise dest node should be the last.
   319  	beginIdx := 0
   320  	if l.MergeOptions.ListIncreaseDirection == yaml.MergeOptionsListPrepend {
   321  		beginIdx = 1
   322  	}
   323  	for i := range l.Sources {
   324  		src := l.Sources[(i+beginIdx)%len(l.Sources)]
   325  		if src == nil {
   326  			continue
   327  		}
   328  
   329  		// add the value of the field for each element
   330  		// don't check error, we know this is a list node
   331  		values, _ := src.ElementValuesList(keys)
   332  		for _, s := range values {
   333  			if len(s) == 0 || seen.Has(s) {
   334  				continue
   335  			}
   336  			returnValues = append(returnValues, s)
   337  			seen = seen.Insert(s)
   338  		}
   339  	}
   340  	return returnValues
   341  }
   342  
   343  // elementPrimitiveValues returns the primitive values in an associative list -- eg. finalizers
   344  func (l Walker) elementPrimitiveValues() [][]string {
   345  	// use slice to to keep elements in the original order
   346  	var returnValues [][]string
   347  	seen := sets.String{}
   348  	// if we are doing append, dest node should be the first.
   349  	// otherwise dest node should be the last.
   350  	beginIdx := 0
   351  	if l.MergeOptions.ListIncreaseDirection == yaml.MergeOptionsListPrepend {
   352  		beginIdx = 1
   353  	}
   354  	for i := range l.Sources {
   355  		src := l.Sources[(i+beginIdx)%len(l.Sources)]
   356  		if src == nil {
   357  			continue
   358  		}
   359  
   360  		// add the value of the field for each element
   361  		// don't check error, we know this is a list node
   362  		for _, item := range src.YNode().Content {
   363  			if seen.Has(item.Value) {
   364  				continue
   365  			}
   366  			returnValues = append(returnValues, []string{item.Value})
   367  			seen.Insert(item.Value)
   368  		}
   369  	}
   370  	return returnValues
   371  }
   372  
   373  // fieldValue returns a slice containing each source's value for fieldName
   374  func (l Walker) elementValueList(keys []string, values []string) []*yaml.RNode {
   375  	keys, values = validateKeys([][]string{values}, values, keys)
   376  	var fields []*yaml.RNode
   377  	for i := range l.Sources {
   378  		if l.Sources[i] == nil {
   379  			fields = append(fields, nil)
   380  			continue
   381  		}
   382  		fields = append(fields, l.Sources[i].ElementList(keys, values))
   383  	}
   384  	return fields
   385  }
   386
View as plain text