tofieldset.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  	"sync"
    21  
    22  	"sigs.k8s.io/structured-merge-diff/v4/fieldpath"
    23  	"sigs.k8s.io/structured-merge-diff/v4/schema"
    24  	"sigs.k8s.io/structured-merge-diff/v4/value"
    25  )
    26  
    27  var tPool = sync.Pool{
    28  	New: func() interface{} { return &toFieldSetWalker{} },
    29  }
    30  
    31  func (tv TypedValue) toFieldSetWalker() *toFieldSetWalker {
    32  	v := tPool.Get().(*toFieldSetWalker)
    33  	v.value = tv.value
    34  	v.schema = tv.schema
    35  	v.typeRef = tv.typeRef
    36  	v.set = &fieldpath.Set{}
    37  	v.allocator = value.NewFreelistAllocator()
    38  	return v
    39  }
    40  
    41  func (v *toFieldSetWalker) finished() {
    42  	v.schema = nil
    43  	v.typeRef = schema.TypeRef{}
    44  	v.path = nil
    45  	v.set = nil
    46  	tPool.Put(v)
    47  }
    48  
    49  type toFieldSetWalker struct {
    50  	value   value.Value
    51  	schema  *schema.Schema
    52  	typeRef schema.TypeRef
    53  
    54  	set  *fieldpath.Set
    55  	path fieldpath.Path
    56  
    57  	// Allocate only as many walkers as needed for the depth by storing them here.
    58  	spareWalkers *[]*toFieldSetWalker
    59  	allocator    value.Allocator
    60  }
    61  
    62  func (v *toFieldSetWalker) prepareDescent(pe fieldpath.PathElement, tr schema.TypeRef) *toFieldSetWalker {
    63  	if v.spareWalkers == nil {
    64  		// first descent.
    65  		v.spareWalkers = &[]*toFieldSetWalker{}
    66  	}
    67  	var v2 *toFieldSetWalker
    68  	if n := len(*v.spareWalkers); n > 0 {
    69  		v2, *v.spareWalkers = (*v.spareWalkers)[n-1], (*v.spareWalkers)[:n-1]
    70  	} else {
    71  		v2 = &toFieldSetWalker{}
    72  	}
    73  	*v2 = *v
    74  	v2.typeRef = tr
    75  	v2.path = append(v2.path, pe)
    76  	return v2
    77  }
    78  
    79  func (v *toFieldSetWalker) finishDescent(v2 *toFieldSetWalker) {
    80  	// if the descent caused a realloc, ensure that we reuse the buffer
    81  	// for the next sibling.
    82  	v.path = v2.path[:len(v2.path)-1]
    83  	*v.spareWalkers = append(*v.spareWalkers, v2)
    84  }
    85  
    86  func (v *toFieldSetWalker) toFieldSet() ValidationErrors {
    87  	return resolveSchema(v.schema, v.typeRef, v.value, v)
    88  }
    89  
    90  func (v *toFieldSetWalker) doScalar(t *schema.Scalar) ValidationErrors {
    91  	v.set.Insert(v.path)
    92  
    93  	return nil
    94  }
    95  
    96  func (v *toFieldSetWalker) visitListItems(t *schema.List, list value.List) (errs ValidationErrors) {
    97  	// Keeps track of the PEs we've seen
    98  	seen := fieldpath.MakePathElementSet(list.Length())
    99  	// Keeps tracks of the PEs we've counted as duplicates
   100  	duplicates := fieldpath.MakePathElementSet(list.Length())
   101  	for i := 0; i < list.Length(); i++ {
   102  		child := list.At(i)
   103  		pe, _ := listItemToPathElement(v.allocator, v.schema, t, child)
   104  		if seen.Has(pe) {
   105  			if duplicates.Has(pe) {
   106  				// do nothing
   107  			} else {
   108  				v.set.Insert(append(v.path, pe))
   109  				duplicates.Insert(pe)
   110  			}
   111  		} else {
   112  			seen.Insert(pe)
   113  		}
   114  	}
   115  
   116  	for i := 0; i < list.Length(); i++ {
   117  		child := list.At(i)
   118  		pe, _ := listItemToPathElement(v.allocator, v.schema, t, child)
   119  		if duplicates.Has(pe) {
   120  			continue
   121  		}
   122  		v2 := v.prepareDescent(pe, t.ElementType)
   123  		v2.value = child
   124  		errs = append(errs, v2.toFieldSet()...)
   125  
   126  		v2.set.Insert(v2.path)
   127  		v.finishDescent(v2)
   128  	}
   129  	return errs
   130  }
   131  
   132  func (v *toFieldSetWalker) doList(t *schema.List) (errs ValidationErrors) {
   133  	list, _ := listValue(v.allocator, v.value)
   134  	if list != nil {
   135  		defer v.allocator.Free(list)
   136  	}
   137  	if t.ElementRelationship == schema.Atomic {
   138  		v.set.Insert(v.path)
   139  		return nil
   140  	}
   141  
   142  	if list == nil {
   143  		return nil
   144  	}
   145  
   146  	errs = v.visitListItems(t, list)
   147  
   148  	return errs
   149  }
   150  
   151  func (v *toFieldSetWalker) visitMapItems(t *schema.Map, m value.Map) (errs ValidationErrors) {
   152  	m.Iterate(func(key string, val value.Value) bool {
   153  		pe := fieldpath.PathElement{FieldName: &key}
   154  
   155  		tr := t.ElementType
   156  		if sf, ok := t.FindField(key); ok {
   157  			tr = sf.Type
   158  		}
   159  		v2 := v.prepareDescent(pe, tr)
   160  		v2.value = val
   161  		errs = append(errs, v2.toFieldSet()...)
   162  		if val.IsNull() || (val.IsMap() && val.AsMap().Length() == 0) {
   163  			v2.set.Insert(v2.path)
   164  		} else if _, ok := t.FindField(key); !ok {
   165  			v2.set.Insert(v2.path)
   166  		}
   167  		v.finishDescent(v2)
   168  		return true
   169  	})
   170  	return errs
   171  }
   172  
   173  func (v *toFieldSetWalker) doMap(t *schema.Map) (errs ValidationErrors) {
   174  	m, _ := mapValue(v.allocator, v.value)
   175  	if m != nil {
   176  		defer v.allocator.Free(m)
   177  	}
   178  	if t.ElementRelationship == schema.Atomic {
   179  		v.set.Insert(v.path)
   180  		return nil
   181  	}
   182  
   183  	if m == nil {
   184  		return nil
   185  	}
   186  
   187  	errs = v.visitMapItems(t, m)
   188  
   189  	return errs
   190  }
   191
View as plain text