1/* 2Copyright 2018 The Kubernetes Authors. 3 4Licensed under the Apache License, Version 2.0 (the "License"); 5you may not use this file except in compliance with the License. 6You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10Unless required by applicable law or agreed to in writing, software 11distributed under the License is distributed on an "AS IS" BASIS, 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13See the License for the specific language governing permissions and 14limitations under the License. 15*/ 16 17package typed 18 19import ( 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 27var tPool = sync.Pool{ 28 New: func() interface{} { return &toFieldSetWalker{} }, 29} 30 31func (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 41func (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 49type 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 62func (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 79func (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 86func (v *toFieldSetWalker) toFieldSet() ValidationErrors { 87 return resolveSchema(v.schema, v.typeRef, v.value, v) 88} 89 90func (v *toFieldSetWalker) doScalar(t *schema.Scalar) ValidationErrors { 91 v.set.Insert(v.path) 92 93 return nil 94} 95 96func (v *toFieldSetWalker) visitListItems(t *schema.List, list value.List) (errs ValidationErrors) { 97 for i := 0; i < list.Length(); i++ { 98 child := list.At(i) 99 pe, _ := listItemToPathElement(v.allocator, v.schema, t, i, child) 100 v2 := v.prepareDescent(pe, t.ElementType) 101 v2.value = child 102 errs = append(errs, v2.toFieldSet()...) 103 104 v2.set.Insert(v2.path) 105 v.finishDescent(v2) 106 } 107 return errs 108} 109 110func (v *toFieldSetWalker) doList(t *schema.List) (errs ValidationErrors) { 111 list, _ := listValue(v.allocator, v.value) 112 if list != nil { 113 defer v.allocator.Free(list) 114 } 115 if t.ElementRelationship == schema.Atomic { 116 v.set.Insert(v.path) 117 return nil 118 } 119 120 if list == nil { 121 return nil 122 } 123 124 errs = v.visitListItems(t, list) 125 126 return errs 127} 128 129func (v *toFieldSetWalker) visitMapItems(t *schema.Map, m value.Map) (errs ValidationErrors) { 130 m.Iterate(func(key string, val value.Value) bool { 131 pe := fieldpath.PathElement{FieldName: &key} 132 133 tr := t.ElementType 134 if sf, ok := t.FindField(key); ok { 135 tr = sf.Type 136 } 137 v2 := v.prepareDescent(pe, tr) 138 v2.value = val 139 errs = append(errs, v2.toFieldSet()...) 140 if val.IsNull() || (val.IsMap() && val.AsMap().Length() == 0) { 141 v2.set.Insert(v2.path) 142 } else if _, ok := t.FindField(key); !ok { 143 v2.set.Insert(v2.path) 144 } 145 v.finishDescent(v2) 146 return true 147 }) 148 return errs 149} 150 151func (v *toFieldSetWalker) doMap(t *schema.Map) (errs ValidationErrors) { 152 m, _ := mapValue(v.allocator, v.value) 153 if m != nil { 154 defer v.allocator.Free(m) 155 } 156 if t.ElementRelationship == schema.Atomic { 157 v.set.Insert(v.path) 158 return nil 159 } 160 161 if m == nil { 162 return nil 163 } 164 165 errs = v.visitMapItems(t, m) 166 167 return errs 168} 169