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