GolangのYamlパッケージのバグを見つけた話

## 初めに

弊社プロダクトでは設定に関する項目をyamlで記述していてAPI起動時にUnmarshalしているのですが、その結果が期待していたものと異なることが以前発生したので原因は何だったのか、どうやって突き止めたのかをまとめてみました。
とりあえず原因だけ知りたいという方は[こちら](https://github.com/go-yaml/yaml/issues/1035)のissueを見て頂くと良いかと思います。

## 使用環境
[yamlライブラリ](https://github.com/go-yaml/yaml)
```bash
% go version
go version go1.21.1 darwin/amd64
```

## バグの詳細
yaml上に書いた一部の設定が構造体に反映されませんでした。
具体的には次のようなyamlを用意した時に、 `merger_val` の値がマッピング先に反映されていませんでした。
```config.yaml
mergee_param: &mergee
  param_key:
    keywords: []

merger_param:
  parameter:
    <<: *mergee
    param_key:
      keywords:
        - "merger_val"
```

## 原因探し
### スクリプトの用意
まずはバグを再現するための最小限のスクリプトを作ります。本番のコードは莫大すぎる上に毎度APIを再起動するのは手間なので既存のコードをベースに小規模のスクリプトを用意しました。yamlは上記のを流用して構造体もバグが再現できる最小限のものを作成しました。サンプルコードは以下になります。
```sample.go
package main

import (
	"fmt"
	"log"

	"gopkg.in/yaml.v3"
)

type (
	paramType string

	yamlMap map[string]keywords

	keywords struct {
		Param map[paramType]params `yaml:"parameter"`
	}

	params struct {
		Keywords []string `yaml:"keywords"`
	}
)

const data = `
mergee_param: &mergee
  param_key:
    keywords: []

merger_param:
  parameter:
    <<: *mergee
    param_key:
      keywords:
        - "merger_val"
`

func main() {
	var mk yamlMap
	err := yaml.Unmarshal([]byte(data), &mk)
	if err != nil {
		log.Fatalf("cannot unmarshal data: %v", err)
	}
	fmt.Printf("%+v", mk)
}

```
合わせて `<<: *mergee` という行を消すことによって結果の構造体に `merger_val` が含まれ正しく動作することが分かりました。
[公式ドキュメント](https://yaml.org/type/merge.html)によると該当の行は `マージ` という処理をしていて現在のノードに別のノードの情報を合体させるというものです。しかし、公式ドキュメントにも書いてある通り **マージが行われるキーはマージ先に存在しないキーのみ** なので今回のようにマージ元・先に同じキー( `param_key` )が存在する場合は上書きがおこらず `merger_val` がマッピングされるはずです。
### issueの確認
原因がマージ周りにあることはわかったので[issueページ](https://github.com/go-yaml/yaml/issues)にアクセスして関連する報告が上がっていないか確認します。すでに上がっている場合はわざわざコードを読まなくても良いので。しかし、ざっと見てみたところ関連するissueはあげられていませんでした。なので仕方がありませんが、実際に関数の中を見てみようと思います。
### コードリーディング(通常の流れ編)
では早速マージのバグがどこで起きているのか突き止めにいきましょう！と言いたいところですが、最初の段階ではyamlのunmarshalの実装に対する知識が0なのでまずはマージが発生しない通常の処理がどのように進んでいるかを確かめてみたいと思います。
というわけなので次のようなyamlを用意してそれがどのようにunmarshalされているか追っていきたいと思います。
```config.yaml
merger_param:
  parameter:
    param_key:
      keywords:
        - "merger_val"
```
本来コードリーディングは気になる処理を中心に読んでいくと思うのですが、現状どの辺りでマージ処理が行われているのか見当もつかない為クライアントが呼び出せるパブリックメソッドから順番に追っていこうと思います。
入り口である `Unmarshal` 関数はプライベート関数を呼んでいるだけのようです。
```yaml.go
func Unmarshal(in []byte, out interface{}) (err error) {
 return unmarshal(in, out, false)
}
```

unmarshalの処理は以下のようになっています。
```yaml.go
func unmarshal(in []byte, out interface{}, strict bool) (err error) {
	// 諸々の処理
 
	node := p.parse() // 1.渡されたyamlを Node という構造体にデコードし直す
	if node != nil {
		v := reflect.ValueOf(out) // 2.yamlをマッピングするためのデータを用意
		if v.Kind() == reflect.Ptr && !v.IsNil() {
			v = v.Elem()
		}
		d.unmarshal(node, v) // 3.作成したデータをまた別の関数に渡している
	}
	.
    .
    .
}
```

1で作成されるnodeは以下のように定義されています。yamlの各要素をそのまま表しているみたいです。
```yaml.go
type Node struct {
	// Kind defines whether the node is a document, a mapping, a sequence,
	// a scalar value, or an alias to another node. The specific data type of
	// scalar nodes may be obtained via the ShortTag and LongTag methods.
	Kind  Kind

	// Style allows customizing the apperance of the node in the tree.
	Style Style

	// Tag holds the YAML tag defining the data type for the value.
	// When decoding, this field will always be set to the resolved tag,
	// even when it wasn't explicitly provided in the YAML content.
	// When encoding, if this field is unset the value type will be
	// implied from the node properties, and if it is set, it will only
	// be serialized into the representation if TaggedStyle is used or
	// the implicit tag diverges from the provided one.
	Tag string

	// Value holds the unescaped and unquoted represenation of the value.
	Value string

	// Anchor holds the anchor name for this node, which allows aliases to point to it.
	Anchor string

	// Alias holds the node that this alias points to. Only valid when Kind is AliasNode.
	Alias *Node

	// Content holds contained nodes for documents, mappings, and sequences.
	Content []*Node

	// HeadComment holds any comments in the lines preceding the node and
	// not separated by an empty line.
	HeadComment string

	// LineComment holds any comments at the end of the line where the node is in.
	LineComment string

	// FootComment holds any comments following the node and before empty lines.
	FootComment string

	// Line and Column hold the node position in the decoded YAML text.
	// These fields are not respected when encoding the node.
	Line   int
	Column int
}
```
今回大事なのは次の三つの要素です。

1. Kind
    1. こちらはNodeの種類を表します。[公式](https://yaml.org/spec/1.2.2/#3211-nodes)によると以下の3種類があるそうです。(パッケージ内には追加でAliasNodeというものもありますが後述します)
        1. Scalar
            1. 1つ以上のユニコード文字で形成される要素
        2. Sequence
            1. 任意の数のContentを所有することができます。
        3. Mapping
            1. こちらのNodeはキーとバリューのペアをContentに持ちます。
    2. 今回使用しているyamlで言うと `param_key` はMappingNodeでキーである `keywords` はScalarNode、最後に `merger_val` を含むバリューはSequeneNodeということになります。 
2. Content
    2. yamlを見ればわかるようにそれぞれの要素の中にまた別の要素が入っています。構造体ではこの状態を `Content` というNodeの配列を使って表現しています。
3. Value
    1. 名前の示す通り各要素の値です。上のyamlでいう `keywords` `merger_val` などが当たります。


まとめると今回のyamlはざっと以下のようなNodeに変換されます。
```node.go
Node {
    Content: []*Node{
        &Node{
            Kind: MappingNode
            Content: []*Node{
                &Node{
                    Kind: ScalarNode
                    Value: "merger_param"
                }
                &Node{
                    Kind: MappingNode
                    Content: []*Node{
                        &Node{
                            Kind: ScalarNode
                            Tag: "!!str"
                            Value: "parameter"
                        }
                        &Node{
                            Kind: MappingNode
                            Content: []*Node{
                                &Node{
                                    Kind: ScalarNode
                                    Value: "param_key"
                                }
                                &Node{
                                    Kind: MappingNode
                                    Content: []*Node{
                                        &Node{
                                            Kind: ScalarNode
                                            Tag: "!!str"
                                            Value: "keywords"
                                        }
                                        &Node{
                                            Kind: SequenceNode
                                            Contentsame node  []*Node{
                                                &Node{
                                                    Kind: ScalarNode
                                                    Value: "merger_val"
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                
                }
            }
        }
    }
}
```

続いて呼び出し先の `decoder.unmarshal` について見ていきたいと思います。以下のようにこの関数はNodeの種類ごとに異なるメソッドを呼んでいる、いわばエントリーポイント的な役割だということが分かります。一つずつ見ていきたいと思います。

```decode.go
func (d *decoder) unmarshal(n *Node, out reflect.Value) (good bool) {
    // 前処理

    // nodeの種別を確認して対応するメソッドを読んでいる
	switch n.Kind {
	case ScalarNode:
		good = d.scalar(n, out)
	case MappingNode:
		good = d.mapping(n, out)
	case SequenceNode:
		good = d.sequence(n, out)
	case 0:
		if n.IsZero() {
			return d.null(out)
		}
		fallthrough
	default:
		failf("cannot decode node with unknown kind %d", n.Kind)
	}
	return good
}
```

一つ目は `scalar function` です。こちらは以下のようにnodeのvalueをセットする関数となっています。
```decode.go
func (d *decoder) scalar(n *Node, out reflect.Value) bool {
	// マッピング先の型ごとに異なるメソッドでnodeの値をセットしている
	switch out.Kind() {
	case reflect.String:
		out.SetString(n.Value)
		return true
	case reflect.Interface:
        // 値のセット
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
        // 値のセット
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
        // 値のセット
	case reflect.Bool:
        // 値のセット
	case reflect.Float32, reflect.Float64:
        // 値のセット
	case reflect.Ptr:
		panic("yaml internal error: please report the issue")
	}
	d.terror(n, tag, out)
	return false
}
```
二つ目は `sequence function` です。こちらは以下のように配列となる変数outに対して要素を一つずつセットしてく関数となっています。
```decode.go
func (d *decoder) sequence(n *Node, out reflect.Value) (good bool) {
	// do type check
 
	j := 0
	for i := 0; i < l; i++ {
		e := reflect.New(et).Elem()
		// nodeの子要素を一つずつデコードして対応するインデックスにセットしていく
		if ok := d.unmarshal(n.Content[i], e); ok {
			out.Index(j).Set(e)
			j++
		}
	}
	return true
}
```
三つ目が `mapping function` です。以下の通り変数outに対してkey・vaueを順々にセットする処理となっています。
```decode.go
func (d *decoder) mapping(n *Node, out reflect.Value) (good bool) {
	switch out.Kind() {
	case reflect.Struct:
        // 構造体へのマッピングの場合は別のメソッドを呼ぶ
		return d.mappingStruct(n, out)
	case reflect.Map:
		// okay
	case reflect.Interface:
	default:
		d.terror(n, mapTag, out)
		return false
	}
 
	outt := out.Type()
    // keyとvalueそれぞれの要素を取得している
	kt := outt.Key()
	et := outt.Elem()

	// 子要素はkey,value,key,value...の順番で並んでいるので2つずつ処理を進めてマッピングしている
	for i := 0; i < l; i += 2 {
		k := reflect.New(kt).Elem()
		// keyをunmarshal
		if d.unmarshal(n.Content[i], k) {
			kkind := k.Kind()
			if kkind == reflect.Interface {
				kkind = k.Elem().Kind()
			}
			if kkind == reflect.Map || kkind == reflect.Slice {
				failf("invalid map key: %#v", k.Interface())
			}
			e := reflect.New(et).Elem()
			// keyに対応するvalueをunmarshalしている
			if d.unmarshal(n.Content[i+1], e) || n.Content[i+1].ShortTag() == nullTag && (mapIsNew || !out.MapIndex(k).IsValid()) {
				out.SetMapIndex(k, e)
			}
		}
	}

	return true
}
````
また最初にマッピング先の型チェックをしていて構造体だった場合は `mappingStruct` が呼ばれるようになります。その処理は以下のようになっています。やっていることは `mapping` メソッドと似ていますね。
```decode.go
func (d *decoder) mappingStruct(n *Node, out reflect.Value) (good bool) {
	// 構造体のフィールドの情報を取得
	sinfo, err := getStructInfo(out.Type())

	// 諸々の処理
 
	name := settableValueOf("")
	l := len(n.Content)
    // kerとvalueのセットで処理が進むため2ずつインクリメントする
	for i := 0; i < l; i += 2 {
		ni := n.Content[i]
		if !d.unmarshal(ni, name) {
			continue
		}
		// yamlタグの名称を取得
		sname := name.String()
		// yamlタグに対応するフィールドを取得
		if info, ok := sinfo.FieldsMap[sname]; ok {
			var field reflect.Value
			if info.Inline == nil {
				field = out.Field(info.Num)
			} else {
				field = d.fieldByIndex(n, out, info.Inline)
			}
			// フィールドに対して値をマッピング
			d.unmarshal(n.Content[i+1], field)
		}
	}

	return true
}
```

以上が主要な関数となるのですが、ご覧の通り `sequence function` と `mapping function` の二つは `unmarshal function` から呼ばれたのにそれぞれの内部で再び `unmarshal function` を呼んでいます。
なぜこのようなことが起こり得るのでしょうか。これは該当のノードがScalarNode以外の可能性があるからです。
例えば　`MappingNode` に紐づく値が必ず `ScalarNode` である場合Valueを取得する際には `scalar function` を呼んで値をセットして終了します。
しかし、今回用意したyamlのように現実では `ScalarNode` 以外にも`SequenceNode` や `MappingNode` 、さらに `MappingNode` をバリューとする `MappingNode` など色々なパターンがあることが分かります。そのため内部で `unmarshal` 関数を再び呼んでノードの種類ごとに処理を行っています。

ですので、unmarshalする処理をまとめると次のようになります。

```decode.go
const data = `
merger_param:
  parameter:
    param_key:
      keywords:
        - "merger_val"
`

type (
	yamlMap map[string]keywords
 
	paramType string

	keywords struct {
		Param map[paramType]params `yaml:"parameter"`
	}

	params struct {
		Keywords []string `yaml:"keywords"`
	}
)
```

処理
```
1. yamlMap(=map[string]keywords)に対して `merger_param` をキーとしてセットし、parameterをバリューとしてセットするためにunmarshalが呼び出される
2. yamlのバリューであるkeywordsは構造体なので `mappingStruct` が呼び出され、parameterがタグ付けされているParamフィールド(=map[paramType]params)のキーに `param_key` がセットされてバリューであるparamsにkeywordsをセットしようとする
3. paramsのKeywordsフィールドの最初に値として `merger_val` がセットされる
4. params構造体が完成したので手順2のparam_keyに対応するバリューとしてセットする
5. keywords構造体が完了したので手順1のmerger_paramに紐づくバリューとしてセットする
```

### コードリーディング(マージ編)
基本的な流れはわかったのでいよいよ本丸、マージの実装を見ていこうと思います。
再掲しますが使用するyamlは以下です。
```config.yaml
mergee_param: &mergee
  param_key:
    keywords: []

merger_param:
  parameter:
    <<: *mergee
    param_key:
      keywords:
        - "merger_val"
```
まずNode構造体に変化が起こります。
```node.go
&Node{
    Kind: MappingNode
    Content: []*Node{
　　　　　　　　　　　　　　　　// 新しく加わったnode1
        &Node{
            Kind: ScalarNode
            Value "<<"
        }
        // 新しいnode2
        &Node{
            Kind: AliasNode
            Value: "mergee"
            // 元のnodeの情報を保持している
            Alias: &Node{
                    Kind: MappingNode
                    Anchor: "mergee"
                    Content: []*Node{
                        &Node{
                            Kind: ScalarNode
                            Value: "param_key"
                        }
                        &Node{
                            Kind: MappingNode
                            Content: []*Node{
                                &Node{
                                    Kind: ScalarNode
                                    Tag: "!!str"
                                    Value: "keywords"
                                }
                                &Node{
                                    Kind: SequenceNode
                                    Content: []*Node{
                                        &Node{
                                            Kind: ScalarNode
                                            Value: "mergee_val"
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
        }
        &Node{
            Kind: ScalarNode
            Value: "param_key"
        }
        &Node{
            Kind: MappingNode
            Content: []*Node{
                &Node{
                    Kind: ScalarNode
                    Value: "keywords"
                }
                &Node{
                    Kind: SequenceNode
                    Contentsame node  []*Node{
                        &Node{
                            Kind: ScalarNode
                            Value: "merger_val"
                        }
                    }
                }
            }
        }
}
```
一番外側のNodeのContent内に新しく `<<` と `mergee` というvalueを持つNodeが増えていますね。また `mergee` の方はAliasとしてmerge元のNode情報を持っていることが分かります。

続いて実際に処理がどう変わるかについて見ていきたいと思います。
まず `mapping` 関数の中で全てのキーとバリューのマッピングが終わった後に以下のようにマージに関する処理が呼ばれています。
```decode.go
func (d *decoder) mapping(n *Node, out reflect.Value) (good bool) {
	var mergeNode *Node

	for i := 0; i < l; i += 2 {
		// バリューが `<<` のnodeの場合は、次のnodeをmergeNodeとして保持しておく
		// 今回のケースの場合バリューが `mergee` のnode
		if isMerge(n.Content[i]) {
			mergeNode = n.Content[i+1]
			continue
		}
		// 通常の処理の通りキーとバリューのマッピングが行われる
	}

	// mergeされるべきnodeがあった場合は、merge処理を行う
	d.mergedFields = mergedFields
	if mergeNode != nil {
		d.merge(n, mergeNode, out)
	}

	return true
}
```
そしてmergeメソッド内ではマージ先のnodeの持つキーをマップに保存して、そのままAliasNodeをunmarshalする処理が走ります。
```decode.go
func (d *decoder) merge(parent *Node, merge *Node, out reflect.Value) {
	mergedFields := d.mergedFields
	if mergedFields == nil {
		d.mergedFields = make(map[interface{}]bool)
		// 対象のnodeの子要素の内キーに値するものをマップに保存する
		// 今回は `<<` と `param_key` をvalueに持つnode
		for i := 0; i < len(parent.Content); i += 2 {
			k := reflect.New(ifaceType).Elem()
			if d.unmarshal(parent.Content[i], k) {
				d.mergedFields[k.Interface()] = true
			}
		}
	}

	switch merge.Kind {
	case MappingNode:
	case AliasNode:
		if merge.Alias != nil && merge.Alias.Kind != MappingNode {
			failWantMap()
		}
		// 上書きするためaliasNodeに対してもunmarshalを行う
		d.unmarshal(merge, out)
	case SequenceNode:
	default:
		failWantMap()
	}

	d.mergedFields = mergedFields
}
```

`unmarshal` メソッドから `alias` メソッドが呼ばれ、そこからAliasNode.Nodeに対して再び `unmarshal` メソッドが呼ばれています。
```decode.go
func (d *decoder) unmarshal(n *Node, out reflect.Value) (good bool) {
    // 諸々の処理
    
	switch n.Kind {
	case DocumentNode:
		return d.document(n, out)
	case AliasNode:
		return d.alias(n, out)
	}
	// 前述した処理
	switch n.Kind {
	case ScalarNode:
	case MappingNode:
	case SequenceNode:
	case 0:
	default:
	}
	return good
}
```

```decode.go
func (d *decoder) alias(n *Node, out reflect.Value) (good bool) {
	// マージ元のnodeをunmarshalする
	good = d.unmarshal(n.Alias, out)
	return good
}
```
outは変わらず `map[paramType]params` なので、このままですと先にマッピングしたキー・バリューは全て上書きされてしまいます。それを防ぐために `mapping` メソッド内でマージ先(merger)に存在しているキーかを確認する処理が走ります。
```decode.go
func (d *decoder) mapping(n *Node, out reflect.Value) (good bool) {
	outt := out.Type()
	kt := outt.Key()
	et := outt.Elem()

	// キーとバリューのマッピングを進めている
	for i := 0; i < l; i += 2 {
		k := reflect.New(kt).Elem()
		if d.unmarshal(n.Content[i], k) {
			if mergedFields != nil {
				ki := k.Interface()
				// マージ先ですでに存在するキーが調べる
				// すでに存在していたら上書きを防ぐために処理をスキップ
				if mergedFields[ki] {
					continue
				}
				mergedFields[ki] = true
			}
			// キーに対応するバリューのマッピングを進める
		}
	}

	return true
}
```

だんだん見えてきましたね。つまり今回のケースのように値が上書きされているということは何らかの原因でキーが一致しなかった可能性が高そうです。では、まず `merge` メソッド内でマップに保存している処理を見てみましょう。
```decode.go
k := reflect.New(ifaceType).Elem()
if d.unmarshal(parent.Content[i], k) {
    d.mergedFields[k.Interface()] = true
}
```

`ifaceType` は以下のように定数として定義されていますが、 `interface{}` 型のようですね。
```decode.go
var (
	nodeType       = reflect.TypeOf(Node{})
	durationType   = reflect.TypeOf(time.Duration(0))
	stringMapType  = reflect.TypeOf(map[string]interface{}{})
	generalMapType = reflect.TypeOf(map[interface{}]interface{}{})
	ifaceType      = generalMapType.Elem()
	timeType       = reflect.TypeOf(time.Time{})
	ptrTimeType    = reflect.TypeOf(&time.Time{})
)
```
次に `mapping` メソッド内の処理は以下です。
```decode.go
outt := out.Type() // マッピング先の構造体
kt := outt.Key()
k := reflect.New(kt).Elem() 
d.unmarshal(n.Content[i], k)
ki := k.Interface()
```
outはマッピング先なので今回のケースは `map[paramType]params` となります。こちらの処理は `paramTyp` 型をもとに変数 `k` を定義しています。次に `Interface` メソッドを見てみます。
以下のように `interface{}` 型への代入と同義らしいですね。
```value.go
// Interface returns v's current value as an interface{}.
// It is equivalent to:
//
//	var i interface{} = (v's underlying value)
```

マップのキーとして一致しているかどうかは `==` 演算子で比較しているので、実際に以下のようなスクリプトを書いて確認してみました。が、結果は一致しませんでした。
```sample.go
package main

import "fmt"

type ParamType string

func main() {
	p := ParamType("keyword")
	var i interface{} = p

	var i2 interface{} = "keyword"
	fmt.Println(i == i2) // => false
}
```
原因はユーザー定義型を使っていることにあります。interface同士の比較の場合両者が同じ型でないとfalseになるのですがGolangではプリミティブ型とユーザー定義型は別物として扱われます。

なので代わりにプリミティブ型、つまりstring型を使ってみましょう。そうするとtrueになることが確認できます。同時に動作確認用に使っていたスクリプトでも以下のように修正しましょう。
```sample.go
type (
	// paramType string

	yamlMap map[string]keywords

	keywords struct {
		Param map[string]params `yaml:"parameter"` // paramTypeの代わりにstringを使う
	}

	params struct {
		Keywords []string `yaml:"keywords"`
	}
)
```
実行してみると以下のように `merger_val` が結果に含まれることが分かると思います。
```result.go
map[mergee_param:{Param:map[]} merger_param:{Param:map[param_key:{Keywords:[merger_val]}]}]
```

原因はユーザー定義型を使用していたことにあることが証明されましたね。

## まとめ
ここまでお読みいただきありがとうございます。

今回はyamlライブラリの予期せぬ挙動を調べた際の手順について説明しました。

長々と書いてしまいましたが、以下がライブラリのデバッグ・コーディングをする上で大切だなと思いました。
1. 動作再現用の簡易なスクリプト
2. 周辺・関連知識(今回の場合Yamlそのもの)
3. 根気よくデバッグし続ける強い心

ライブラリといえどバグは発生するものですので、この記事が今後そういった時参考になれば幸いです。