reconcile_schema.go

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

     1  /*
     2  Copyright 2018 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package typed
    18  
    19  import (
    20  	"fmt"
    21  	"sync"
    22  
    23  	"sigs.k8s.io/structured-merge-diff/v4/fieldpath"
    24  	"sigs.k8s.io/structured-merge-diff/v4/schema"
    25  )
    26  
    27  var fmPool = sync.Pool{
    28  	New: func() interface{} { return &reconcileWithSchemaWalker{} },
    29  }
    30  
    31  func (v *reconcileWithSchemaWalker) finished() {
    32  	v.fieldSet = nil
    33  	v.schema = nil
    34  	v.value = nil
    35  	v.typeRef = schema.TypeRef{}
    36  	v.path = nil
    37  	v.toRemove = nil
    38  	v.toAdd = nil
    39  	fmPool.Put(v)
    40  }
    41  
    42  type reconcileWithSchemaWalker struct {
    43  	value  *TypedValue    // root of the live object
    44  	schema *schema.Schema // root of the live schema
    45  
    46  	// state of node being visited by walker
    47  	fieldSet *fieldpath.Set
    48  	typeRef  schema.TypeRef
    49  	path     fieldpath.Path
    50  	isAtomic bool
    51  
    52  	// the accumulated diff to perform to apply reconciliation
    53  	toRemove *fieldpath.Set // paths to remove recursively
    54  	toAdd    *fieldpath.Set // paths to add after any removals
    55  
    56  	// Allocate only as many walkers as needed for the depth by storing them here.
    57  	spareWalkers *[]*reconcileWithSchemaWalker
    58  }
    59  
    60  func (v *reconcileWithSchemaWalker) prepareDescent(pe fieldpath.PathElement, tr schema.TypeRef) *reconcileWithSchemaWalker {
    61  	if v.spareWalkers == nil {
    62  		// first descent.
    63  		v.spareWalkers = &[]*reconcileWithSchemaWalker{}
    64  	}
    65  	var v2 *reconcileWithSchemaWalker
    66  	if n := len(*v.spareWalkers); n > 0 {
    67  		v2, *v.spareWalkers = (*v.spareWalkers)[n-1], (*v.spareWalkers)[:n-1]
    68  	} else {
    69  		v2 = &reconcileWithSchemaWalker{}
    70  	}
    71  	*v2 = *v
    72  	v2.typeRef = tr
    73  	v2.path = append(v.path, pe)
    74  	v2.value = v.value
    75  	return v2
    76  }
    77  
    78  func (v *reconcileWithSchemaWalker) finishDescent(v2 *reconcileWithSchemaWalker) {
    79  	v2.fieldSet = nil
    80  	v2.schema = nil
    81  	v2.value = nil
    82  	v2.typeRef = schema.TypeRef{}
    83  	if cap(v2.path) < 20 { // recycle slices that do not have unexpectedly high capacity
    84  		v2.path = v2.path[:0]
    85  	} else {
    86  		v2.path = nil
    87  	}
    88  
    89  	// merge any accumulated changes into parent walker
    90  	if v2.toRemove != nil {
    91  		if v.toRemove == nil {
    92  			v.toRemove = v2.toRemove
    93  		} else {
    94  			v.toRemove = v.toRemove.Union(v2.toRemove)
    95  		}
    96  	}
    97  	if v2.toAdd != nil {
    98  		if v.toAdd == nil {
    99  			v.toAdd = v2.toAdd
   100  		} else {
   101  			v.toAdd = v.toAdd.Union(v2.toAdd)
   102  		}
   103  	}
   104  	v2.toRemove = nil
   105  	v2.toAdd = nil
   106  
   107  	// if the descent caused a realloc, ensure that we reuse the buffer
   108  	// for the next sibling.
   109  	*v.spareWalkers = append(*v.spareWalkers, v2)
   110  }
   111  
   112  // ReconcileFieldSetWithSchema reconciles the a field set with any changes to the
   113  // object's schema since the field set was written. Returns the reconciled field set, or nil of
   114  // no changes were made to the field set.
   115  //
   116  // Supports:
   117  // - changing types from atomic to granular
   118  // - changing types from granular to atomic
   119  func ReconcileFieldSetWithSchema(fieldset *fieldpath.Set, tv *TypedValue) (*fieldpath.Set, error) {
   120  	v := fmPool.Get().(*reconcileWithSchemaWalker)
   121  	v.fieldSet = fieldset
   122  	v.value = tv
   123  
   124  	v.schema = tv.schema
   125  	v.typeRef = tv.typeRef
   126  
   127  	defer v.finished()
   128  	errs := v.reconcile()
   129  
   130  	if len(errs) > 0 {
   131  		return nil, fmt.Errorf("errors reconciling field set with schema: %s", errs.Error())
   132  	}
   133  
   134  	// If there are any accumulated changes, apply them
   135  	if v.toAdd != nil || v.toRemove != nil {
   136  		out := v.fieldSet
   137  		if v.toRemove != nil {
   138  			out = out.RecursiveDifference(v.toRemove)
   139  		}
   140  		if v.toAdd != nil {
   141  			out = out.Union(v.toAdd)
   142  		}
   143  		return out, nil
   144  	}
   145  	return nil, nil
   146  }
   147  
   148  func (v *reconcileWithSchemaWalker) reconcile() (errs ValidationErrors) {
   149  	a, ok := v.schema.Resolve(v.typeRef)
   150  	if !ok {
   151  		errs = append(errs, errorf("could not resolve %v", v.typeRef)...)
   152  		return
   153  	}
   154  	return handleAtom(a, v.typeRef, v)
   155  }
   156  
   157  func (v *reconcileWithSchemaWalker) doScalar(_ *schema.Scalar) (errs ValidationErrors) {
   158  	return errs
   159  }
   160  
   161  func (v *reconcileWithSchemaWalker) visitListItems(t *schema.List, element *fieldpath.Set) (errs ValidationErrors) {
   162  	handleElement := func(pe fieldpath.PathElement, isMember bool) {
   163  		var hasChildren bool
   164  		v2 := v.prepareDescent(pe, t.ElementType)
   165  		v2.fieldSet, hasChildren = element.Children.Get(pe)
   166  		v2.isAtomic = isMember && !hasChildren
   167  		errs = append(errs, v2.reconcile()...)
   168  		v.finishDescent(v2)
   169  	}
   170  	element.Children.Iterate(func(pe fieldpath.PathElement) {
   171  		if element.Members.Has(pe) {
   172  			return
   173  		}
   174  		handleElement(pe, false)
   175  	})
   176  	element.Members.Iterate(func(pe fieldpath.PathElement) {
   177  		handleElement(pe, true)
   178  	})
   179  	return errs
   180  }
   181  
   182  func (v *reconcileWithSchemaWalker) doList(t *schema.List) (errs ValidationErrors) {
   183  	// reconcile lists changed from granular to atomic.
   184  	// Note that migrations from atomic to granular are not recommended and will
   185  	// be treated as if they were always granular.
   186  	//
   187  	// In this case, the manager that owned the previously atomic field (and all subfields),
   188  	// will now own just the top-level field and none of the subfields.
   189  	if !v.isAtomic && t.ElementRelationship == schema.Atomic {
   190  		v.toRemove = fieldpath.NewSet(v.path) // remove all root and all children fields
   191  		v.toAdd = fieldpath.NewSet(v.path)    // add the root of the atomic
   192  		return errs
   193  	}
   194  	if v.fieldSet != nil {
   195  		errs = v.visitListItems(t, v.fieldSet)
   196  	}
   197  	return errs
   198  }
   199  
   200  func (v *reconcileWithSchemaWalker) visitMapItems(t *schema.Map, element *fieldpath.Set) (errs ValidationErrors) {
   201  	handleElement := func(pe fieldpath.PathElement, isMember bool) {
   202  		var hasChildren bool
   203  		if tr, ok := typeRefAtPath(t, pe); ok { // ignore fields not in the schema
   204  			v2 := v.prepareDescent(pe, tr)
   205  			v2.fieldSet, hasChildren = element.Children.Get(pe)
   206  			v2.isAtomic = isMember && !hasChildren
   207  			errs = append(errs, v2.reconcile()...)
   208  			v.finishDescent(v2)
   209  		}
   210  	}
   211  	element.Children.Iterate(func(pe fieldpath.PathElement) {
   212  		if element.Members.Has(pe) {
   213  			return
   214  		}
   215  		handleElement(pe, false)
   216  	})
   217  	element.Members.Iterate(func(pe fieldpath.PathElement) {
   218  		handleElement(pe, true)
   219  	})
   220  
   221  	return errs
   222  }
   223  
   224  func (v *reconcileWithSchemaWalker) doMap(t *schema.Map) (errs ValidationErrors) {
   225  	// We don't currently reconcile deduced types (unstructured CRDs) or maps that contain only unknown
   226  	// fields since deduced types do not yet support atomic or granular tags.
   227  	if isUntypedDeducedMap(t) {
   228  		return errs
   229  	}
   230  
   231  	// reconcile maps and structs changed from granular to atomic.
   232  	// Note that migrations from atomic to granular are not recommended and will
   233  	// be treated as if they were always granular.
   234  	//
   235  	// In this case the manager that owned the previously atomic field (and all subfields),
   236  	// will now own just the top-level field and none of the subfields.
   237  	if !v.isAtomic && t.ElementRelationship == schema.Atomic {
   238  		if v.fieldSet != nil && v.fieldSet.Size() > 0 {
   239  			v.toRemove = fieldpath.NewSet(v.path) // remove all root and all children fields
   240  			v.toAdd = fieldpath.NewSet(v.path)    // add the root of the atomic
   241  		}
   242  		return errs
   243  	}
   244  	if v.fieldSet != nil {
   245  		errs = v.visitMapItems(t, v.fieldSet)
   246  	}
   247  	return errs
   248  }
   249  
   250  func fieldSetAtPath(node *fieldpath.Set, path fieldpath.Path) (*fieldpath.Set, bool) {
   251  	ok := true
   252  	for _, pe := range path {
   253  		if node, ok = node.Children.Get(pe); !ok {
   254  			break
   255  		}
   256  	}
   257  	return node, ok
   258  }
   259  
   260  func descendToPath(node *fieldpath.Set, path fieldpath.Path) *fieldpath.Set {
   261  	for _, pe := range path {
   262  		node = node.Children.Descend(pe)
   263  	}
   264  	return node
   265  }
   266  
   267  func typeRefAtPath(t *schema.Map, pe fieldpath.PathElement) (schema.TypeRef, bool) {
   268  	tr := t.ElementType
   269  	if pe.FieldName != nil {
   270  		if sf, ok := t.FindField(*pe.FieldName); ok {
   271  			tr = sf.Type
   272  		}
   273  	}
   274  	return tr, tr != schema.TypeRef{}
   275  }
   276  
   277  // isUntypedDeducedMap returns true if m has no fields defined, but allows untyped elements.
   278  // This is equivalent to a openAPI object that has x-kubernetes-preserve-unknown-fields=true
   279  // but does not have any properties defined on the object.
   280  func isUntypedDeducedMap(m *schema.Map) bool {
   281  	return isUntypedDeducedRef(m.ElementType) && m.Fields == nil
   282  }
   283  
   284  func isUntypedDeducedRef(t schema.TypeRef) bool {
   285  	if t.NamedType != nil {
   286  		return *t.NamedType == "__untyped_deduced_"
   287  	}
   288  	atom := t.Inlined
   289  	return atom.Scalar != nil && *atom.Scalar == "untyped"
   290  }
   291
View as plain text