1package toml
2
3// Struct field handling is adapted from code in encoding/json:
4//
5// Copyright 2010 The Go Authors.  All rights reserved.
6// Use of this source code is governed by a BSD-style
7// license that can be found in the Go distribution.
8
9import (
10	"reflect"
11	"sort"
12	"sync"
13)
14
15// A field represents a single field found in a struct.
16type field struct {
17	name  string       // the name of the field (`toml` tag included)
18	tag   bool         // whether field has a `toml` tag
19	index []int        // represents the depth of an anonymous field
20	typ   reflect.Type // the type of the field
21}
22
23// byName sorts field by name, breaking ties with depth,
24// then breaking ties with "name came from toml tag", then
25// breaking ties with index sequence.
26type byName []field
27
28func (x byName) Len() int { return len(x) }
29
30func (x byName) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
31
32func (x byName) Less(i, j int) bool {
33	if x[i].name != x[j].name {
34		return x[i].name < x[j].name
35	}
36	if len(x[i].index) != len(x[j].index) {
37		return len(x[i].index) < len(x[j].index)
38	}
39	if x[i].tag != x[j].tag {
40		return x[i].tag
41	}
42	return byIndex(x).Less(i, j)
43}
44
45// byIndex sorts field by index sequence.
46type byIndex []field
47
48func (x byIndex) Len() int { return len(x) }
49
50func (x byIndex) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
51
52func (x byIndex) Less(i, j int) bool {
53	for k, xik := range x[i].index {
54		if k >= len(x[j].index) {
55			return false
56		}
57		if xik != x[j].index[k] {
58			return xik < x[j].index[k]
59		}
60	}
61	return len(x[i].index) < len(x[j].index)
62}
63
64// typeFields returns a list of fields that TOML should recognize for the given
65// type. The algorithm is breadth-first search over the set of structs to
66// include - the top struct and then any reachable anonymous structs.
67func typeFields(t reflect.Type) []field {
68	// Anonymous fields to explore at the current level and the next.
69	current := []field{}
70	next := []field{{typ: t}}
71
72	// Count of queued names for current level and the next.
73	count := map[reflect.Type]int{}
74	nextCount := map[reflect.Type]int{}
75
76	// Types already visited at an earlier level.
77	visited := map[reflect.Type]bool{}
78
79	// Fields found.
80	var fields []field
81
82	for len(next) > 0 {
83		current, next = next, current[:0]
84		count, nextCount = nextCount, map[reflect.Type]int{}
85
86		for _, f := range current {
87			if visited[f.typ] {
88				continue
89			}
90			visited[f.typ] = true
91
92			// Scan f.typ for fields to include.
93			for i := 0; i < f.typ.NumField(); i++ {
94				sf := f.typ.Field(i)
95				if sf.PkgPath != "" && !sf.Anonymous { // unexported
96					continue
97				}
98				opts := getOptions(sf.Tag)
99				if opts.skip {
100					continue
101				}
102				index := make([]int, len(f.index)+1)
103				copy(index, f.index)
104				index[len(f.index)] = i
105
106				ft := sf.Type
107				if ft.Name() == "" && ft.Kind() == reflect.Ptr {
108					// Follow pointer.
109					ft = ft.Elem()
110				}
111
112				// Record found field and index sequence.
113				if opts.name != "" || !sf.Anonymous || ft.Kind() != reflect.Struct {
114					tagged := opts.name != ""
115					name := opts.name
116					if name == "" {
117						name = sf.Name
118					}
119					fields = append(fields, field{name, tagged, index, ft})
120					if count[f.typ] > 1 {
121						// If there were multiple instances, add a second,
122						// so that the annihilation code will see a duplicate.
123						// It only cares about the distinction between 1 or 2,
124						// so don't bother generating any more copies.
125						fields = append(fields, fields[len(fields)-1])
126					}
127					continue
128				}
129
130				// Record new anonymous struct to explore in next round.
131				nextCount[ft]++
132				if nextCount[ft] == 1 {
133					f := field{name: ft.Name(), index: index, typ: ft}
134					next = append(next, f)
135				}
136			}
137		}
138	}
139
140	sort.Sort(byName(fields))
141
142	// Delete all fields that are hidden by the Go rules for embedded fields,
143	// except that fields with TOML tags are promoted.
144
145	// The fields are sorted in primary order of name, secondary order
146	// of field index length. Loop over names; for each name, delete
147	// hidden fields by choosing the one dominant field that survives.
148	out := fields[:0]
149	for advance, i := 0, 0; i < len(fields); i += advance {
150		// One iteration per name.
151		// Find the sequence of fields with the name of this first field.
152		fi := fields[i]
153		name := fi.name
154		for advance = 1; i+advance < len(fields); advance++ {
155			fj := fields[i+advance]
156			if fj.name != name {
157				break
158			}
159		}
160		if advance == 1 { // Only one field with this name
161			out = append(out, fi)
162			continue
163		}
164		dominant, ok := dominantField(fields[i : i+advance])
165		if ok {
166			out = append(out, dominant)
167		}
168	}
169
170	fields = out
171	sort.Sort(byIndex(fields))
172
173	return fields
174}
175
176// dominantField looks through the fields, all of which are known to
177// have the same name, to find the single field that dominates the
178// others using Go's embedding rules, modified by the presence of
179// TOML tags. If there are multiple top-level fields, the boolean
180// will be false: This condition is an error in Go and we skip all
181// the fields.
182func dominantField(fields []field) (field, bool) {
183	// The fields are sorted in increasing index-length order. The winner
184	// must therefore be one with the shortest index length. Drop all
185	// longer entries, which is easy: just truncate the slice.
186	length := len(fields[0].index)
187	tagged := -1 // Index of first tagged field.
188	for i, f := range fields {
189		if len(f.index) > length {
190			fields = fields[:i]
191			break
192		}
193		if f.tag {
194			if tagged >= 0 {
195				// Multiple tagged fields at the same level: conflict.
196				// Return no field.
197				return field{}, false
198			}
199			tagged = i
200		}
201	}
202	if tagged >= 0 {
203		return fields[tagged], true
204	}
205	// All remaining fields have the same length. If there's more than one,
206	// we have a conflict (two fields named "X" at the same level) and we
207	// return no field.
208	if len(fields) > 1 {
209		return field{}, false
210	}
211	return fields[0], true
212}
213
214var fieldCache struct {
215	sync.RWMutex
216	m map[reflect.Type][]field
217}
218
219// cachedTypeFields is like typeFields but uses a cache to avoid repeated work.
220func cachedTypeFields(t reflect.Type) []field {
221	fieldCache.RLock()
222	f := fieldCache.m[t]
223	fieldCache.RUnlock()
224	if f != nil {
225		return f
226	}
227
228	// Compute fields without lock.
229	// Might duplicate effort but won't hold other computations back.
230	f = typeFields(t)
231	if f == nil {
232		f = []field{}
233	}
234
235	fieldCache.Lock()
236	if fieldCache.m == nil {
237		fieldCache.m = map[reflect.Type][]field{}
238	}
239	fieldCache.m[t] = f
240	fieldCache.Unlock()
241	return f
242}
243