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