1//
2// Copyright (c) 2011-2019 Canonical Ltd
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
16package yaml
17
18import (
19	"encoding"
20	"encoding/base64"
21	"fmt"
22	"io"
23	"math"
24	"reflect"
25	"strconv"
26	"time"
27)
28
29// ----------------------------------------------------------------------------
30// Parser, produces a node tree out of a libyaml event stream.
31
32type parser struct {
33	parser   yaml_parser_t
34	event    yaml_event_t
35	doc      *Node
36	anchors  map[string]*Node
37	doneInit bool
38}
39
40func newParser(b []byte) *parser {
41	p := parser{}
42	if !yaml_parser_initialize(&p.parser) {
43		panic("failed to initialize YAML emitter")
44	}
45	if len(b) == 0 {
46		b = []byte{'\n'}
47	}
48	yaml_parser_set_input_string(&p.parser, b)
49	return &p
50}
51
52func newParserFromReader(r io.Reader) *parser {
53	p := parser{}
54	if !yaml_parser_initialize(&p.parser) {
55		panic("failed to initialize YAML emitter")
56	}
57	yaml_parser_set_input_reader(&p.parser, r)
58	return &p
59}
60
61func (p *parser) init() {
62	if p.doneInit {
63		return
64	}
65	p.anchors = make(map[string]*Node)
66	p.expect(yaml_STREAM_START_EVENT)
67	p.doneInit = true
68}
69
70func (p *parser) destroy() {
71	if p.event.typ != yaml_NO_EVENT {
72		yaml_event_delete(&p.event)
73	}
74	yaml_parser_delete(&p.parser)
75}
76
77// expect consumes an event from the event stream and
78// checks that it's of the expected type.
79func (p *parser) expect(e yaml_event_type_t) {
80	if p.event.typ == yaml_NO_EVENT {
81		if !yaml_parser_parse(&p.parser, &p.event) {
82			p.fail()
83		}
84	}
85	if p.event.typ == yaml_STREAM_END_EVENT {
86		failf("attempted to go past the end of stream; corrupted value?")
87	}
88	if p.event.typ != e {
89		p.parser.problem = fmt.Sprintf("expected %s event but got %s", e, p.event.typ)
90		p.fail()
91	}
92	yaml_event_delete(&p.event)
93	p.event.typ = yaml_NO_EVENT
94}
95
96// peek peeks at the next event in the event stream,
97// puts the results into p.event and returns the event type.
98func (p *parser) peek() yaml_event_type_t {
99	if p.event.typ != yaml_NO_EVENT {
100		return p.event.typ
101	}
102	if !yaml_parser_parse(&p.parser, &p.event) {
103		p.fail()
104	}
105	return p.event.typ
106}
107
108func (p *parser) fail() {
109	var where string
110	var line int
111	if p.parser.problem_mark.line != 0 {
112		line = p.parser.problem_mark.line
113		// Scanner errors don't iterate line before returning error
114		if p.parser.error == yaml_SCANNER_ERROR {
115			line++
116		}
117	} else if p.parser.context_mark.line != 0 {
118		line = p.parser.context_mark.line
119	}
120	if line != 0 {
121		where = "line " + strconv.Itoa(line) + ": "
122	}
123	var msg string
124	if len(p.parser.problem) > 0 {
125		msg = p.parser.problem
126	} else {
127		msg = "unknown problem parsing YAML content"
128	}
129	failf("%s%s", where, msg)
130}
131
132func (p *parser) anchor(n *Node, anchor []byte) {
133	if anchor != nil {
134		n.Anchor = string(anchor)
135		p.anchors[n.Anchor] = n
136	}
137}
138
139func (p *parser) parse() *Node {
140	p.init()
141	switch p.peek() {
142	case yaml_SCALAR_EVENT:
143		return p.scalar()
144	case yaml_ALIAS_EVENT:
145		return p.alias()
146	case yaml_MAPPING_START_EVENT:
147		return p.mapping()
148	case yaml_SEQUENCE_START_EVENT:
149		return p.sequence()
150	case yaml_DOCUMENT_START_EVENT:
151		return p.document()
152	case yaml_STREAM_END_EVENT:
153		// Happens when attempting to decode an empty buffer.
154		return nil
155	case yaml_TAIL_COMMENT_EVENT:
156		panic("internal error: unexpected tail comment event (please report)")
157	default:
158		panic("internal error: attempted to parse unknown event (please report): " + p.event.typ.String())
159	}
160}
161
162func (p *parser) node(kind Kind, defaultTag, tag, value string) *Node {
163	var style Style
164	if tag != "" && tag != "!" {
165		tag = shortTag(tag)
166		style = TaggedStyle
167	} else if defaultTag != "" {
168		tag = defaultTag
169	} else if kind == ScalarNode {
170		tag, _ = resolve("", value)
171	}
172	return &Node{
173		Kind:        kind,
174		Tag:         tag,
175		Value:       value,
176		Style:       style,
177		Line:        p.event.start_mark.line + 1,
178		Column:      p.event.start_mark.column + 1,
179		HeadComment: string(p.event.head_comment),
180		LineComment: string(p.event.line_comment),
181		FootComment: string(p.event.foot_comment),
182	}
183}
184
185func (p *parser) parseChild(parent *Node) *Node {
186	child := p.parse()
187	parent.Content = append(parent.Content, child)
188	return child
189}
190
191func (p *parser) document() *Node {
192	n := p.node(DocumentNode, "", "", "")
193	p.doc = n
194	p.expect(yaml_DOCUMENT_START_EVENT)
195	p.parseChild(n)
196	if p.peek() == yaml_DOCUMENT_END_EVENT {
197		n.FootComment = string(p.event.foot_comment)
198	}
199	p.expect(yaml_DOCUMENT_END_EVENT)
200	return n
201}
202
203func (p *parser) alias() *Node {
204	n := p.node(AliasNode, "", "", string(p.event.anchor))
205	n.Alias = p.anchors[n.Value]
206	if n.Alias == nil {
207		failf("unknown anchor '%s' referenced", n.Value)
208	}
209	p.expect(yaml_ALIAS_EVENT)
210	return n
211}
212
213func (p *parser) scalar() *Node {
214	var parsedStyle = p.event.scalar_style()
215	var nodeStyle Style
216	switch {
217	case parsedStyle&yaml_DOUBLE_QUOTED_SCALAR_STYLE != 0:
218		nodeStyle = DoubleQuotedStyle
219	case parsedStyle&yaml_SINGLE_QUOTED_SCALAR_STYLE != 0:
220		nodeStyle = SingleQuotedStyle
221	case parsedStyle&yaml_LITERAL_SCALAR_STYLE != 0:
222		nodeStyle = LiteralStyle
223	case parsedStyle&yaml_FOLDED_SCALAR_STYLE != 0:
224		nodeStyle = FoldedStyle
225	}
226	var nodeValue = string(p.event.value)
227	var nodeTag = string(p.event.tag)
228	var defaultTag string
229	if nodeStyle == 0 {
230		if nodeValue == "<<" {
231			defaultTag = mergeTag
232		}
233	} else {
234		defaultTag = strTag
235	}
236	n := p.node(ScalarNode, defaultTag, nodeTag, nodeValue)
237	n.Style |= nodeStyle
238	p.anchor(n, p.event.anchor)
239	p.expect(yaml_SCALAR_EVENT)
240	return n
241}
242
243func (p *parser) sequence() *Node {
244	n := p.node(SequenceNode, seqTag, string(p.event.tag), "")
245	if p.event.sequence_style()&yaml_FLOW_SEQUENCE_STYLE != 0 {
246		n.Style |= FlowStyle
247	}
248	p.anchor(n, p.event.anchor)
249	p.expect(yaml_SEQUENCE_START_EVENT)
250	for p.peek() != yaml_SEQUENCE_END_EVENT {
251		p.parseChild(n)
252	}
253	n.LineComment = string(p.event.line_comment)
254	n.FootComment = string(p.event.foot_comment)
255	p.expect(yaml_SEQUENCE_END_EVENT)
256	return n
257}
258
259func (p *parser) mapping() *Node {
260	n := p.node(MappingNode, mapTag, string(p.event.tag), "")
261	block := true
262	if p.event.mapping_style()&yaml_FLOW_MAPPING_STYLE != 0 {
263		block = false
264		n.Style |= FlowStyle
265	}
266	p.anchor(n, p.event.anchor)
267	p.expect(yaml_MAPPING_START_EVENT)
268	for p.peek() != yaml_MAPPING_END_EVENT {
269		k := p.parseChild(n)
270		if block && k.FootComment != "" {
271			// Must be a foot comment for the prior value when being dedented.
272			if len(n.Content) > 2 {
273				n.Content[len(n.Content)-3].FootComment = k.FootComment
274				k.FootComment = ""
275			}
276		}
277		v := p.parseChild(n)
278		if k.FootComment == "" && v.FootComment != "" {
279			k.FootComment = v.FootComment
280			v.FootComment = ""
281		}
282		if p.peek() == yaml_TAIL_COMMENT_EVENT {
283			if k.FootComment == "" {
284				k.FootComment = string(p.event.foot_comment)
285			}
286			p.expect(yaml_TAIL_COMMENT_EVENT)
287		}
288	}
289	n.LineComment = string(p.event.line_comment)
290	n.FootComment = string(p.event.foot_comment)
291	if n.Style&FlowStyle == 0 && n.FootComment != "" && len(n.Content) > 1 {
292		n.Content[len(n.Content)-2].FootComment = n.FootComment
293		n.FootComment = ""
294	}
295	p.expect(yaml_MAPPING_END_EVENT)
296	return n
297}
298
299// ----------------------------------------------------------------------------
300// Decoder, unmarshals a node into a provided value.
301
302type decoder struct {
303	doc     *Node
304	aliases map[*Node]bool
305	terrors []string
306
307	stringMapType  reflect.Type
308	generalMapType reflect.Type
309
310	knownFields bool
311	uniqueKeys  bool
312	decodeCount int
313	aliasCount  int
314	aliasDepth  int
315}
316
317var (
318	nodeType       = reflect.TypeOf(Node{})
319	durationType   = reflect.TypeOf(time.Duration(0))
320	stringMapType  = reflect.TypeOf(map[string]interface{}{})
321	generalMapType = reflect.TypeOf(map[interface{}]interface{}{})
322	ifaceType      = generalMapType.Elem()
323	timeType       = reflect.TypeOf(time.Time{})
324	ptrTimeType    = reflect.TypeOf(&time.Time{})
325)
326
327func newDecoder() *decoder {
328	d := &decoder{
329		stringMapType:  stringMapType,
330		generalMapType: generalMapType,
331		uniqueKeys:     true,
332	}
333	d.aliases = make(map[*Node]bool)
334	return d
335}
336
337func (d *decoder) terror(n *Node, tag string, out reflect.Value) {
338	if n.Tag != "" {
339		tag = n.Tag
340	}
341	value := n.Value
342	if tag != seqTag && tag != mapTag {
343		if len(value) > 10 {
344			value = " `" + value[:7] + "...`"
345		} else {
346			value = " `" + value + "`"
347		}
348	}
349	d.terrors = append(d.terrors, fmt.Sprintf("line %d: cannot unmarshal %s%s into %s", n.Line, shortTag(tag), value, out.Type()))
350}
351
352func (d *decoder) callUnmarshaler(n *Node, u Unmarshaler) (good bool) {
353	err := u.UnmarshalYAML(n)
354	if e, ok := err.(*TypeError); ok {
355		d.terrors = append(d.terrors, e.Errors...)
356		return false
357	}
358	if err != nil {
359		fail(err)
360	}
361	return true
362}
363
364func (d *decoder) callObsoleteUnmarshaler(n *Node, u obsoleteUnmarshaler) (good bool) {
365	terrlen := len(d.terrors)
366	err := u.UnmarshalYAML(func(v interface{}) (err error) {
367		defer handleErr(&err)
368		d.unmarshal(n, reflect.ValueOf(v))
369		if len(d.terrors) > terrlen {
370			issues := d.terrors[terrlen:]
371			d.terrors = d.terrors[:terrlen]
372			return &TypeError{issues}
373		}
374		return nil
375	})
376	if e, ok := err.(*TypeError); ok {
377		d.terrors = append(d.terrors, e.Errors...)
378		return false
379	}
380	if err != nil {
381		fail(err)
382	}
383	return true
384}
385
386// d.prepare initializes and dereferences pointers and calls UnmarshalYAML
387// if a value is found to implement it.
388// It returns the initialized and dereferenced out value, whether
389// unmarshalling was already done by UnmarshalYAML, and if so whether
390// its types unmarshalled appropriately.
391//
392// If n holds a null value, prepare returns before doing anything.
393func (d *decoder) prepare(n *Node, out reflect.Value) (newout reflect.Value, unmarshaled, good bool) {
394	if n.ShortTag() == nullTag {
395		return out, false, false
396	}
397	again := true
398	for again {
399		again = false
400		if out.Kind() == reflect.Ptr {
401			if out.IsNil() {
402				out.Set(reflect.New(out.Type().Elem()))
403			}
404			out = out.Elem()
405			again = true
406		}
407		if out.CanAddr() {
408			outi := out.Addr().Interface()
409			if u, ok := outi.(Unmarshaler); ok {
410				good = d.callUnmarshaler(n, u)
411				return out, true, good
412			}
413			if u, ok := outi.(obsoleteUnmarshaler); ok {
414				good = d.callObsoleteUnmarshaler(n, u)
415				return out, true, good
416			}
417		}
418	}
419	return out, false, false
420}
421
422func (d *decoder) fieldByIndex(n *Node, v reflect.Value, index []int) (field reflect.Value) {
423	if n.ShortTag() == nullTag {
424		return reflect.Value{}
425	}
426	for _, num := range index {
427		for {
428			if v.Kind() == reflect.Ptr {
429				if v.IsNil() {
430					v.Set(reflect.New(v.Type().Elem()))
431				}
432				v = v.Elem()
433				continue
434			}
435			break
436		}
437		v = v.Field(num)
438	}
439	return v
440}
441
442const (
443	// 400,000 decode operations is ~500kb of dense object declarations, or
444	// ~5kb of dense object declarations with 10000% alias expansion
445	alias_ratio_range_low = 400000
446
447	// 4,000,000 decode operations is ~5MB of dense object declarations, or
448	// ~4.5MB of dense object declarations with 10% alias expansion
449	alias_ratio_range_high = 4000000
450
451	// alias_ratio_range is the range over which we scale allowed alias ratios
452	alias_ratio_range = float64(alias_ratio_range_high - alias_ratio_range_low)
453)
454
455func allowedAliasRatio(decodeCount int) float64 {
456	switch {
457	case decodeCount <= alias_ratio_range_low:
458		// allow 99% to come from alias expansion for small-to-medium documents
459		return 0.99
460	case decodeCount >= alias_ratio_range_high:
461		// allow 10% to come from alias expansion for very large documents
462		return 0.10
463	default:
464		// scale smoothly from 99% down to 10% over the range.
465		// this maps to 396,000 - 400,000 allowed alias-driven decodes over the range.
466		// 400,000 decode operations is ~100MB of allocations in worst-case scenarios (single-item maps).
467		return 0.99 - 0.89*(float64(decodeCount-alias_ratio_range_low)/alias_ratio_range)
468	}
469}
470
471func (d *decoder) unmarshal(n *Node, out reflect.Value) (good bool) {
472	d.decodeCount++
473	if d.aliasDepth > 0 {
474		d.aliasCount++
475	}
476	if d.aliasCount > 100 && d.decodeCount > 1000 && float64(d.aliasCount)/float64(d.decodeCount) > allowedAliasRatio(d.decodeCount) {
477		failf("document contains excessive aliasing")
478	}
479	if out.Type() == nodeType {
480		out.Set(reflect.ValueOf(n).Elem())
481		return true
482	}
483	switch n.Kind {
484	case DocumentNode:
485		return d.document(n, out)
486	case AliasNode:
487		return d.alias(n, out)
488	}
489	out, unmarshaled, good := d.prepare(n, out)
490	if unmarshaled {
491		return good
492	}
493	switch n.Kind {
494	case ScalarNode:
495		good = d.scalar(n, out)
496	case MappingNode:
497		good = d.mapping(n, out)
498	case SequenceNode:
499		good = d.sequence(n, out)
500	default:
501		panic("internal error: unknown node kind: " + strconv.Itoa(int(n.Kind)))
502	}
503	return good
504}
505
506func (d *decoder) document(n *Node, out reflect.Value) (good bool) {
507	if len(n.Content) == 1 {
508		d.doc = n
509		d.unmarshal(n.Content[0], out)
510		return true
511	}
512	return false
513}
514
515func (d *decoder) alias(n *Node, out reflect.Value) (good bool) {
516	if d.aliases[n] {
517		// TODO this could actually be allowed in some circumstances.
518		failf("anchor '%s' value contains itself", n.Value)
519	}
520	d.aliases[n] = true
521	d.aliasDepth++
522	good = d.unmarshal(n.Alias, out)
523	d.aliasDepth--
524	delete(d.aliases, n)
525	return good
526}
527
528var zeroValue reflect.Value
529
530func resetMap(out reflect.Value) {
531	for _, k := range out.MapKeys() {
532		out.SetMapIndex(k, zeroValue)
533	}
534}
535
536func (d *decoder) scalar(n *Node, out reflect.Value) bool {
537	var tag string
538	var resolved interface{}
539	if n.indicatedString() {
540		tag = strTag
541		resolved = n.Value
542	} else {
543		tag, resolved = resolve(n.Tag, n.Value)
544		if tag == binaryTag {
545			data, err := base64.StdEncoding.DecodeString(resolved.(string))
546			if err != nil {
547				failf("!!binary value contains invalid base64 data")
548			}
549			resolved = string(data)
550		}
551	}
552	if resolved == nil {
553		if out.CanAddr() {
554			switch out.Kind() {
555			case reflect.Interface, reflect.Ptr, reflect.Map, reflect.Slice:
556				out.Set(reflect.Zero(out.Type()))
557				return true
558			}
559		}
560		return false
561	}
562	if resolvedv := reflect.ValueOf(resolved); out.Type() == resolvedv.Type() {
563		// We've resolved to exactly the type we want, so use that.
564		out.Set(resolvedv)
565		return true
566	}
567	// Perhaps we can use the value as a TextUnmarshaler to
568	// set its value.
569	if out.CanAddr() {
570		u, ok := out.Addr().Interface().(encoding.TextUnmarshaler)
571		if ok {
572			var text []byte
573			if tag == binaryTag {
574				text = []byte(resolved.(string))
575			} else {
576				// We let any value be unmarshaled into TextUnmarshaler.
577				// That might be more lax than we'd like, but the
578				// TextUnmarshaler itself should bowl out any dubious values.
579				text = []byte(n.Value)
580			}
581			err := u.UnmarshalText(text)
582			if err != nil {
583				fail(err)
584			}
585			return true
586		}
587	}
588	switch out.Kind() {
589	case reflect.String:
590		if tag == binaryTag {
591			out.SetString(resolved.(string))
592			return true
593		}
594		out.SetString(n.Value)
595		return true
596	case reflect.Interface:
597		out.Set(reflect.ValueOf(resolved))
598		return true
599	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
600		// This used to work in v2, but it's very unfriendly.
601		isDuration := out.Type() == durationType
602
603		switch resolved := resolved.(type) {
604		case int:
605			if !isDuration && !out.OverflowInt(int64(resolved)) {
606				out.SetInt(int64(resolved))
607				return true
608			}
609		case int64:
610			if !isDuration && !out.OverflowInt(resolved) {
611				out.SetInt(resolved)
612				return true
613			}
614		case uint64:
615			if !isDuration && resolved <= math.MaxInt64 && !out.OverflowInt(int64(resolved)) {
616				out.SetInt(int64(resolved))
617				return true
618			}
619		case float64:
620			if !isDuration && resolved <= math.MaxInt64 && !out.OverflowInt(int64(resolved)) {
621				out.SetInt(int64(resolved))
622				return true
623			}
624		case string:
625			if out.Type() == durationType {
626				d, err := time.ParseDuration(resolved)
627				if err == nil {
628					out.SetInt(int64(d))
629					return true
630				}
631			}
632		}
633	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
634		switch resolved := resolved.(type) {
635		case int:
636			if resolved >= 0 && !out.OverflowUint(uint64(resolved)) {
637				out.SetUint(uint64(resolved))
638				return true
639			}
640		case int64:
641			if resolved >= 0 && !out.OverflowUint(uint64(resolved)) {
642				out.SetUint(uint64(resolved))
643				return true
644			}
645		case uint64:
646			if !out.OverflowUint(uint64(resolved)) {
647				out.SetUint(uint64(resolved))
648				return true
649			}
650		case float64:
651			if resolved <= math.MaxUint64 && !out.OverflowUint(uint64(resolved)) {
652				out.SetUint(uint64(resolved))
653				return true
654			}
655		}
656	case reflect.Bool:
657		switch resolved := resolved.(type) {
658		case bool:
659			out.SetBool(resolved)
660			return true
661		case string:
662			// This offers some compatibility with the 1.1 spec (https://yaml.org/type/bool.html).
663			// It only works if explicitly attempting to unmarshal into a typed bool value.
664			switch resolved {
665			case "y", "Y", "yes", "Yes", "YES", "on", "On", "ON":
666				out.SetBool(true)
667				return true
668			case "n", "N", "no", "No", "NO", "off", "Off", "OFF":
669				out.SetBool(false)
670				return true
671			}
672		}
673	case reflect.Float32, reflect.Float64:
674		switch resolved := resolved.(type) {
675		case int:
676			out.SetFloat(float64(resolved))
677			return true
678		case int64:
679			out.SetFloat(float64(resolved))
680			return true
681		case uint64:
682			out.SetFloat(float64(resolved))
683			return true
684		case float64:
685			out.SetFloat(resolved)
686			return true
687		}
688	case reflect.Struct:
689		if resolvedv := reflect.ValueOf(resolved); out.Type() == resolvedv.Type() {
690			out.Set(resolvedv)
691			return true
692		}
693	case reflect.Ptr:
694		panic("yaml internal error: please report the issue")
695	}
696	d.terror(n, tag, out)
697	return false
698}
699
700func settableValueOf(i interface{}) reflect.Value {
701	v := reflect.ValueOf(i)
702	sv := reflect.New(v.Type()).Elem()
703	sv.Set(v)
704	return sv
705}
706
707func (d *decoder) sequence(n *Node, out reflect.Value) (good bool) {
708	l := len(n.Content)
709
710	var iface reflect.Value
711	switch out.Kind() {
712	case reflect.Slice:
713		out.Set(reflect.MakeSlice(out.Type(), l, l))
714	case reflect.Array:
715		if l != out.Len() {
716			failf("invalid array: want %d elements but got %d", out.Len(), l)
717		}
718	case reflect.Interface:
719		// No type hints. Will have to use a generic sequence.
720		iface = out
721		out = settableValueOf(make([]interface{}, l))
722	default:
723		d.terror(n, seqTag, out)
724		return false
725	}
726	et := out.Type().Elem()
727
728	j := 0
729	for i := 0; i < l; i++ {
730		e := reflect.New(et).Elem()
731		if ok := d.unmarshal(n.Content[i], e); ok {
732			out.Index(j).Set(e)
733			j++
734		}
735	}
736	if out.Kind() != reflect.Array {
737		out.Set(out.Slice(0, j))
738	}
739	if iface.IsValid() {
740		iface.Set(out)
741	}
742	return true
743}
744
745func (d *decoder) mapping(n *Node, out reflect.Value) (good bool) {
746	l := len(n.Content)
747	if d.uniqueKeys {
748		nerrs := len(d.terrors)
749		for i := 0; i < l; i += 2 {
750			ni := n.Content[i]
751			for j := i + 2; j < l; j += 2 {
752				nj := n.Content[j]
753				if ni.Kind == nj.Kind && ni.Value == nj.Value {
754					d.terrors = append(d.terrors, fmt.Sprintf("line %d: mapping key %#v already defined at line %d", nj.Line, nj.Value, ni.Line))
755				}
756			}
757		}
758		if len(d.terrors) > nerrs {
759			return false
760		}
761	}
762	switch out.Kind() {
763	case reflect.Struct:
764		return d.mappingStruct(n, out)
765	case reflect.Map:
766		// okay
767	case reflect.Interface:
768		iface := out
769		if isStringMap(n) {
770			out = reflect.MakeMap(d.stringMapType)
771		} else {
772			out = reflect.MakeMap(d.generalMapType)
773		}
774		iface.Set(out)
775	default:
776		d.terror(n, mapTag, out)
777		return false
778	}
779
780	outt := out.Type()
781	kt := outt.Key()
782	et := outt.Elem()
783
784	stringMapType := d.stringMapType
785	generalMapType := d.generalMapType
786	if outt.Elem() == ifaceType {
787		if outt.Key().Kind() == reflect.String {
788			d.stringMapType = outt
789		} else if outt.Key() == ifaceType {
790			d.generalMapType = outt
791		}
792	}
793
794	if out.IsNil() {
795		out.Set(reflect.MakeMap(outt))
796	}
797	for i := 0; i < l; i += 2 {
798		if isMerge(n.Content[i]) {
799			d.merge(n.Content[i+1], out)
800			continue
801		}
802		k := reflect.New(kt).Elem()
803		if d.unmarshal(n.Content[i], k) {
804			kkind := k.Kind()
805			if kkind == reflect.Interface {
806				kkind = k.Elem().Kind()
807			}
808			if kkind == reflect.Map || kkind == reflect.Slice {
809				failf("invalid map key: %#v", k.Interface())
810			}
811			e := reflect.New(et).Elem()
812			if d.unmarshal(n.Content[i+1], e) {
813				out.SetMapIndex(k, e)
814			}
815		}
816	}
817	d.stringMapType = stringMapType
818	d.generalMapType = generalMapType
819	return true
820}
821
822func isStringMap(n *Node) bool {
823	if n.Kind != MappingNode {
824		return false
825	}
826	l := len(n.Content)
827	for i := 0; i < l; i += 2 {
828		if n.Content[i].ShortTag() != strTag {
829			return false
830		}
831	}
832	return true
833}
834
835func (d *decoder) mappingStruct(n *Node, out reflect.Value) (good bool) {
836	sinfo, err := getStructInfo(out.Type())
837	if err != nil {
838		panic(err)
839	}
840
841	var inlineMap reflect.Value
842	var elemType reflect.Type
843	if sinfo.InlineMap != -1 {
844		inlineMap = out.Field(sinfo.InlineMap)
845		inlineMap.Set(reflect.New(inlineMap.Type()).Elem())
846		elemType = inlineMap.Type().Elem()
847	}
848
849	for _, index := range sinfo.InlineUnmarshalers {
850		field := d.fieldByIndex(n, out, index)
851		d.prepare(n, field)
852	}
853
854	var doneFields []bool
855	if d.uniqueKeys {
856		doneFields = make([]bool, len(sinfo.FieldsList))
857	}
858	name := settableValueOf("")
859	l := len(n.Content)
860	for i := 0; i < l; i += 2 {
861		ni := n.Content[i]
862		if isMerge(ni) {
863			d.merge(n.Content[i+1], out)
864			continue
865		}
866		if !d.unmarshal(ni, name) {
867			continue
868		}
869		if info, ok := sinfo.FieldsMap[name.String()]; ok {
870			if d.uniqueKeys {
871				if doneFields[info.Id] {
872					d.terrors = append(d.terrors, fmt.Sprintf("line %d: field %s already set in type %s", ni.Line, name.String(), out.Type()))
873					continue
874				}
875				doneFields[info.Id] = true
876			}
877			var field reflect.Value
878			if info.Inline == nil {
879				field = out.Field(info.Num)
880			} else {
881				field = d.fieldByIndex(n, out, info.Inline)
882			}
883			d.unmarshal(n.Content[i+1], field)
884		} else if sinfo.InlineMap != -1 {
885			if inlineMap.IsNil() {
886				inlineMap.Set(reflect.MakeMap(inlineMap.Type()))
887			}
888			value := reflect.New(elemType).Elem()
889			d.unmarshal(n.Content[i+1], value)
890			inlineMap.SetMapIndex(name, value)
891		} else if d.knownFields {
892			d.terrors = append(d.terrors, fmt.Sprintf("line %d: field %s not found in type %s", ni.Line, name.String(), out.Type()))
893		}
894	}
895	return true
896}
897
898func failWantMap() {
899	failf("map merge requires map or sequence of maps as the value")
900}
901
902func (d *decoder) merge(n *Node, out reflect.Value) {
903	switch n.Kind {
904	case MappingNode:
905		d.unmarshal(n, out)
906	case AliasNode:
907		if n.Alias != nil && n.Alias.Kind != MappingNode {
908			failWantMap()
909		}
910		d.unmarshal(n, out)
911	case SequenceNode:
912		// Step backwards as earlier nodes take precedence.
913		for i := len(n.Content) - 1; i >= 0; i-- {
914			ni := n.Content[i]
915			if ni.Kind == AliasNode {
916				if ni.Alias != nil && ni.Alias.Kind != MappingNode {
917					failWantMap()
918				}
919			} else if ni.Kind != MappingNode {
920				failWantMap()
921			}
922			d.unmarshal(ni, out)
923		}
924	default:
925		failWantMap()
926	}
927}
928
929func isMerge(n *Node) bool {
930	return n.Kind == ScalarNode && n.Value == "<<" && (n.Tag == "" || n.Tag == "!" || shortTag(n.Tag) == mergeTag)
931}
932