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