update.go

Documentation: sigs.k8s.io/structured-merge-diff/v4/merge

     1  /*
     2  Copyright 2018 The Kubernetes Authors.
     3  Licensed under the Apache License, Version 2.0 (the "License");
     4  you may not use this file except in compliance with the License.
     5  You may obtain a copy of the License at
     6      http://www.apache.org/licenses/LICENSE-2.0
     7  Unless required by applicable law or agreed to in writing, software
     8  distributed under the License is distributed on an "AS IS" BASIS,
     9  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    10  See the License for the specific language governing permissions and
    11  limitations under the License.
    12  */
    13  
    14  package merge
    15  
    16  import (
    17  	"fmt"
    18  
    19  	"sigs.k8s.io/structured-merge-diff/v4/fieldpath"
    20  	"sigs.k8s.io/structured-merge-diff/v4/typed"
    21  	"sigs.k8s.io/structured-merge-diff/v4/value"
    22  )
    23  
    24  // Converter is an interface to the conversion logic. The converter
    25  // needs to be able to convert objects from one version to another.
    26  type Converter interface {
    27  	Convert(object *typed.TypedValue, version fieldpath.APIVersion) (*typed.TypedValue, error)
    28  	IsMissingVersionError(error) bool
    29  }
    30  
    31  // UpdateBuilder allows you to create a new Updater by exposing all of
    32  // the options and setting them once.
    33  type UpdaterBuilder struct {
    34  	Converter     Converter
    35  	IgnoredFields map[fieldpath.APIVersion]*fieldpath.Set
    36  
    37  	// Stop comparing the new object with old object after applying.
    38  	// This was initially used to avoid spurious etcd update, but
    39  	// since that's vastly inefficient, we've come-up with a better
    40  	// way of doing that. Create this flag to stop it.
    41  	// Comparing has become more expensive too now that we're not using
    42  	// `Compare` but `value.Equals` so this gives an option to avoid it.
    43  	ReturnInputOnNoop bool
    44  }
    45  
    46  func (u *UpdaterBuilder) BuildUpdater() *Updater {
    47  	return &Updater{
    48  		Converter:         u.Converter,
    49  		IgnoredFields:     u.IgnoredFields,
    50  		returnInputOnNoop: u.ReturnInputOnNoop,
    51  	}
    52  }
    53  
    54  // Updater is the object used to compute updated FieldSets and also
    55  // merge the object on Apply.
    56  type Updater struct {
    57  	// Deprecated: This will eventually become private.
    58  	Converter Converter
    59  
    60  	// Deprecated: This will eventually become private.
    61  	IgnoredFields map[fieldpath.APIVersion]*fieldpath.Set
    62  
    63  	returnInputOnNoop bool
    64  }
    65  
    66  func (s *Updater) update(oldObject, newObject *typed.TypedValue, version fieldpath.APIVersion, managers fieldpath.ManagedFields, workflow string, force bool) (fieldpath.ManagedFields, *typed.Comparison, error) {
    67  	conflicts := fieldpath.ManagedFields{}
    68  	removed := fieldpath.ManagedFields{}
    69  	compare, err := oldObject.Compare(newObject)
    70  	if err != nil {
    71  		return nil, nil, fmt.Errorf("failed to compare objects: %v", err)
    72  	}
    73  
    74  	versions := map[fieldpath.APIVersion]*typed.Comparison{
    75  		version: compare.ExcludeFields(s.IgnoredFields[version]),
    76  	}
    77  
    78  	for manager, managerSet := range managers {
    79  		if manager == workflow {
    80  			continue
    81  		}
    82  		compare, ok := versions[managerSet.APIVersion()]
    83  		if !ok {
    84  			var err error
    85  			versionedOldObject, err := s.Converter.Convert(oldObject, managerSet.APIVersion())
    86  			if err != nil {
    87  				if s.Converter.IsMissingVersionError(err) {
    88  					delete(managers, manager)
    89  					continue
    90  				}
    91  				return nil, nil, fmt.Errorf("failed to convert old object: %v", err)
    92  			}
    93  			versionedNewObject, err := s.Converter.Convert(newObject, managerSet.APIVersion())
    94  			if err != nil {
    95  				if s.Converter.IsMissingVersionError(err) {
    96  					delete(managers, manager)
    97  					continue
    98  				}
    99  				return nil, nil, fmt.Errorf("failed to convert new object: %v", err)
   100  			}
   101  			compare, err = versionedOldObject.Compare(versionedNewObject)
   102  			if err != nil {
   103  				return nil, nil, fmt.Errorf("failed to compare objects: %v", err)
   104  			}
   105  			versions[managerSet.APIVersion()] = compare.ExcludeFields(s.IgnoredFields[managerSet.APIVersion()])
   106  		}
   107  
   108  		conflictSet := managerSet.Set().Intersection(compare.Modified.Union(compare.Added))
   109  		if !conflictSet.Empty() {
   110  			conflicts[manager] = fieldpath.NewVersionedSet(conflictSet, managerSet.APIVersion(), false)
   111  		}
   112  
   113  		if !compare.Removed.Empty() {
   114  			removed[manager] = fieldpath.NewVersionedSet(compare.Removed, managerSet.APIVersion(), false)
   115  		}
   116  	}
   117  
   118  	if !force && len(conflicts) != 0 {
   119  		return nil, nil, ConflictsFromManagers(conflicts)
   120  	}
   121  
   122  	for manager, conflictSet := range conflicts {
   123  		managers[manager] = fieldpath.NewVersionedSet(managers[manager].Set().Difference(conflictSet.Set()), managers[manager].APIVersion(), managers[manager].Applied())
   124  	}
   125  
   126  	for manager, removedSet := range removed {
   127  		managers[manager] = fieldpath.NewVersionedSet(managers[manager].Set().Difference(removedSet.Set()), managers[manager].APIVersion(), managers[manager].Applied())
   128  	}
   129  
   130  	for manager := range managers {
   131  		if managers[manager].Set().Empty() {
   132  			delete(managers, manager)
   133  		}
   134  	}
   135  
   136  	return managers, compare, nil
   137  }
   138  
   139  // Update is the method you should call once you've merged your final
   140  // object on CREATE/UPDATE/PATCH verbs. newObject must be the object
   141  // that you intend to persist (after applying the patch if this is for a
   142  // PATCH call), and liveObject must be the original object (empty if
   143  // this is a CREATE call).
   144  func (s *Updater) Update(liveObject, newObject *typed.TypedValue, version fieldpath.APIVersion, managers fieldpath.ManagedFields, manager string) (*typed.TypedValue, fieldpath.ManagedFields, error) {
   145  	var err error
   146  	managers, err = s.reconcileManagedFieldsWithSchemaChanges(liveObject, managers)
   147  	if err != nil {
   148  		return nil, fieldpath.ManagedFields{}, err
   149  	}
   150  	managers, compare, err := s.update(liveObject, newObject, version, managers, manager, true)
   151  	if err != nil {
   152  		return nil, fieldpath.ManagedFields{}, err
   153  	}
   154  	if _, ok := managers[manager]; !ok {
   155  		managers[manager] = fieldpath.NewVersionedSet(fieldpath.NewSet(), version, false)
   156  	}
   157  
   158  	ignored := s.IgnoredFields[version]
   159  	if ignored == nil {
   160  		ignored = fieldpath.NewSet()
   161  	}
   162  	managers[manager] = fieldpath.NewVersionedSet(
   163  		managers[manager].Set().Difference(compare.Removed).Union(compare.Modified).Union(compare.Added).RecursiveDifference(ignored),
   164  		version,
   165  		false,
   166  	)
   167  	if managers[manager].Set().Empty() {
   168  		delete(managers, manager)
   169  	}
   170  	return newObject, managers, nil
   171  }
   172  
   173  // Apply should be called when Apply is run, given the current object as
   174  // well as the configuration that is applied. This will merge the object
   175  // and return it.
   176  func (s *Updater) Apply(liveObject, configObject *typed.TypedValue, version fieldpath.APIVersion, managers fieldpath.ManagedFields, manager string, force bool) (*typed.TypedValue, fieldpath.ManagedFields, error) {
   177  	var err error
   178  	managers, err = s.reconcileManagedFieldsWithSchemaChanges(liveObject, managers)
   179  	if err != nil {
   180  		return nil, fieldpath.ManagedFields{}, err
   181  	}
   182  	newObject, err := liveObject.Merge(configObject)
   183  	if err != nil {
   184  		return nil, fieldpath.ManagedFields{}, fmt.Errorf("failed to merge config: %v", err)
   185  	}
   186  	lastSet := managers[manager]
   187  	set, err := configObject.ToFieldSet()
   188  	if err != nil {
   189  		return nil, fieldpath.ManagedFields{}, fmt.Errorf("failed to get field set: %v", err)
   190  	}
   191  
   192  	ignored := s.IgnoredFields[version]
   193  	if ignored != nil {
   194  		set = set.RecursiveDifference(ignored)
   195  		// TODO: is this correct. If we don't remove from lastSet pruning might remove the fields?
   196  		if lastSet != nil {
   197  			lastSet.Set().RecursiveDifference(ignored)
   198  		}
   199  	}
   200  	managers[manager] = fieldpath.NewVersionedSet(set, version, true)
   201  	newObject, err = s.prune(newObject, managers, manager, lastSet)
   202  	if err != nil {
   203  		return nil, fieldpath.ManagedFields{}, fmt.Errorf("failed to prune fields: %v", err)
   204  	}
   205  	managers, _, err = s.update(liveObject, newObject, version, managers, manager, force)
   206  	if err != nil {
   207  		return nil, fieldpath.ManagedFields{}, err
   208  	}
   209  	if !s.returnInputOnNoop && value.EqualsUsing(value.NewFreelistAllocator(), liveObject.AsValue(), newObject.AsValue()) {
   210  		newObject = nil
   211  	}
   212  	return newObject, managers, nil
   213  }
   214  
   215  // prune will remove a field, list or map item, iff:
   216  // * applyingManager applied it last time
   217  // * applyingManager didn't apply it this time
   218  // * no other applier claims to manage it
   219  func (s *Updater) prune(merged *typed.TypedValue, managers fieldpath.ManagedFields, applyingManager string, lastSet fieldpath.VersionedSet) (*typed.TypedValue, error) {
   220  	if lastSet == nil || lastSet.Set().Empty() {
   221  		return merged, nil
   222  	}
   223  	version := lastSet.APIVersion()
   224  	convertedMerged, err := s.Converter.Convert(merged, version)
   225  	if err != nil {
   226  		if s.Converter.IsMissingVersionError(err) {
   227  			return merged, nil
   228  		}
   229  		return nil, fmt.Errorf("failed to convert merged object to last applied version: %v", err)
   230  	}
   231  
   232  	sc, tr := convertedMerged.Schema(), convertedMerged.TypeRef()
   233  	pruned := convertedMerged.RemoveItems(lastSet.Set().EnsureNamedFieldsAreMembers(sc, tr))
   234  	pruned, err = s.addBackOwnedItems(convertedMerged, pruned, version, managers, applyingManager)
   235  	if err != nil {
   236  		return nil, fmt.Errorf("failed add back owned items: %v", err)
   237  	}
   238  	pruned, err = s.addBackDanglingItems(convertedMerged, pruned, lastSet)
   239  	if err != nil {
   240  		return nil, fmt.Errorf("failed add back dangling items: %v", err)
   241  	}
   242  	return s.Converter.Convert(pruned, managers[applyingManager].APIVersion())
   243  }
   244  
   245  // addBackOwnedItems adds back any fields, list and map items that were removed by prune,
   246  // but other appliers or updaters (or the current applier's new config) claim to own.
   247  func (s *Updater) addBackOwnedItems(merged, pruned *typed.TypedValue, prunedVersion fieldpath.APIVersion, managedFields fieldpath.ManagedFields, applyingManager string) (*typed.TypedValue, error) {
   248  	var err error
   249  	managedAtVersion := map[fieldpath.APIVersion]*fieldpath.Set{}
   250  	for _, managerSet := range managedFields {
   251  		if _, ok := managedAtVersion[managerSet.APIVersion()]; !ok {
   252  			managedAtVersion[managerSet.APIVersion()] = fieldpath.NewSet()
   253  		}
   254  		managedAtVersion[managerSet.APIVersion()] = managedAtVersion[managerSet.APIVersion()].Union(managerSet.Set())
   255  	}
   256  	// Add back owned items at pruned version first to avoid conversion failure
   257  	// caused by pruned fields which are required for conversion.
   258  	if managed, ok := managedAtVersion[prunedVersion]; ok {
   259  		merged, pruned, err = s.addBackOwnedItemsForVersion(merged, pruned, prunedVersion, managed)
   260  		if err != nil {
   261  			return nil, err
   262  		}
   263  		delete(managedAtVersion, prunedVersion)
   264  	}
   265  	for version, managed := range managedAtVersion {
   266  		merged, pruned, err = s.addBackOwnedItemsForVersion(merged, pruned, version, managed)
   267  		if err != nil {
   268  			return nil, err
   269  		}
   270  	}
   271  	return pruned, nil
   272  }
   273  
   274  // addBackOwnedItemsForVersion adds back any fields, list and map items that were removed by prune with specific managed field path at a version.
   275  // It is an extracted sub-function from addBackOwnedItems for code reuse.
   276  func (s *Updater) addBackOwnedItemsForVersion(merged, pruned *typed.TypedValue, version fieldpath.APIVersion, managed *fieldpath.Set) (*typed.TypedValue, *typed.TypedValue, error) {
   277  	var err error
   278  	merged, err = s.Converter.Convert(merged, version)
   279  	if err != nil {
   280  		if s.Converter.IsMissingVersionError(err) {
   281  			return merged, pruned, nil
   282  		}
   283  		return nil, nil, fmt.Errorf("failed to convert merged object at version %v: %v", version, err)
   284  	}
   285  	pruned, err = s.Converter.Convert(pruned, version)
   286  	if err != nil {
   287  		if s.Converter.IsMissingVersionError(err) {
   288  			return merged, pruned, nil
   289  		}
   290  		return nil, nil, fmt.Errorf("failed to convert pruned object at version %v: %v", version, err)
   291  	}
   292  	mergedSet, err := merged.ToFieldSet()
   293  	if err != nil {
   294  		return nil, nil, fmt.Errorf("failed to create field set from merged object at version %v: %v", version, err)
   295  	}
   296  	prunedSet, err := pruned.ToFieldSet()
   297  	if err != nil {
   298  		return nil, nil, fmt.Errorf("failed to create field set from pruned object at version %v: %v", version, err)
   299  	}
   300  	sc, tr := merged.Schema(), merged.TypeRef()
   301  	pruned = merged.RemoveItems(mergedSet.EnsureNamedFieldsAreMembers(sc, tr).Difference(prunedSet.EnsureNamedFieldsAreMembers(sc, tr).Union(managed.EnsureNamedFieldsAreMembers(sc, tr))))
   302  	return merged, pruned, nil
   303  }
   304  
   305  // addBackDanglingItems makes sure that the fields list and map items removed by prune were
   306  // previously owned by the currently applying manager. This will add back fields list and map items
   307  // that are unowned or that are owned by Updaters and shouldn't be removed.
   308  func (s *Updater) addBackDanglingItems(merged, pruned *typed.TypedValue, lastSet fieldpath.VersionedSet) (*typed.TypedValue, error) {
   309  	convertedPruned, err := s.Converter.Convert(pruned, lastSet.APIVersion())
   310  	if err != nil {
   311  		if s.Converter.IsMissingVersionError(err) {
   312  			return merged, nil
   313  		}
   314  		return nil, fmt.Errorf("failed to convert pruned object to last applied version: %v", err)
   315  	}
   316  	prunedSet, err := convertedPruned.ToFieldSet()
   317  	if err != nil {
   318  		return nil, fmt.Errorf("failed to create field set from pruned object in last applied version: %v", err)
   319  	}
   320  	mergedSet, err := merged.ToFieldSet()
   321  	if err != nil {
   322  		return nil, fmt.Errorf("failed to create field set from merged object in last applied version: %v", err)
   323  	}
   324  	sc, tr := merged.Schema(), merged.TypeRef()
   325  	prunedSet = prunedSet.EnsureNamedFieldsAreMembers(sc, tr)
   326  	mergedSet = mergedSet.EnsureNamedFieldsAreMembers(sc, tr)
   327  	last := lastSet.Set().EnsureNamedFieldsAreMembers(sc, tr)
   328  	return merged.RemoveItems(mergedSet.Difference(prunedSet).Intersection(last)), nil
   329  }
   330  
   331  // reconcileManagedFieldsWithSchemaChanges reconciles the managed fields with any changes to the
   332  // object's schema since the managed fields were written.
   333  //
   334  // Supports:
   335  // - changing types from atomic to granular
   336  // - changing types from granular to atomic
   337  func (s *Updater) reconcileManagedFieldsWithSchemaChanges(liveObject *typed.TypedValue, managers fieldpath.ManagedFields) (fieldpath.ManagedFields, error) {
   338  	result := fieldpath.ManagedFields{}
   339  	for manager, versionedSet := range managers {
   340  		tv, err := s.Converter.Convert(liveObject, versionedSet.APIVersion())
   341  		if s.Converter.IsMissingVersionError(err) { // okay to skip, obsolete versions will be deleted automatically anyway
   342  			continue
   343  		}
   344  		if err != nil {
   345  			return nil, err
   346  		}
   347  		reconciled, err := typed.ReconcileFieldSetWithSchema(versionedSet.Set(), tv)
   348  		if err != nil {
   349  			return nil, err
   350  		}
   351  		if reconciled != nil {
   352  			result[manager] = fieldpath.NewVersionedSet(reconciled, versionedSet.APIVersion(), versionedSet.Applied())
   353  		} else {
   354  			result[manager] = versionedSet
   355  		}
   356  	}
   357  	return result, nil
   358  }
   359
View as plain text