Writing A Compiler In Go を読んでいく Chapter 6　Hash編

こんちにわ、んだです。

Writing A Compiler In Go (English Edition)

作者:Ball, Thorsten

Amazon

前回は、Arrayのcompilerとvmについて見ていきました。

nda-desu.hatenablog.com

今回は、Hashです。興奮してきましたね。

Hashって？

まずは、Hashのデータ構造について確認しましょう。

{1: 2 + 3, 4: 5 * 6}
{1: 2, 3: 4, 5: 6}

keyとvalueで構成されています。

今回は、このHashのデータ構造を扱っていきます。

Compiler

では、まずはCompilerから見ていきましょう。

// compiler/compiler.go

func (c *Compiler) Compile(node ast.Node) error {
    switch node := node.(type) {

        // 中略
    case *ast.HashLiteral:
        keys := []ast.Expression{}
        for k := range node.Pairs {
            keys = append(keys, k)
        }
        sort.Slice(keys, func(i, j int) bool {
            return keys[i].String() < keys[j].String()
        })

        for _, k := range keys {
            err := c.Compile(k)
            if err != nil {
                return err
            }

            err = c.Compile(node.Pairs[k])
            if err != nil {
                return err
            }
        }

        c.emit(code.OpHash, len(node.Pairs)*2)

keysを昇順でソート

まずは、keysを昇順でソートしています。

for k := range node.Pairs {
    keys = append(keys, k)
}
sort.Slice(keys, func(i, j int) bool {
    return keys[i].String() < keys[j].String()
})

この処理は、コンパイラの実装上必要なのではなく、テストの成功を常に保証するためです。もしソートを行わない場合には、ハッシュのランダム性が起因して、テストもランダムで落ちてしまいます。

そのため、ここで昇順で一旦ソートしておるわけです。

If we didn’t do that, the emitted instructions would be in random order.

p.137

key→Valueの順番でCompile

最後に、まずはkeyをコンパイルして、続いてnode.Pairs[k]をコンパイルして完了です。

for _, k := range keys {
    err := c.Compile(k)
    if err != nil {
        return err
    }

    err = c.Compile(node.Pairs[k])
    if err != nil {
        return err
    }
}

VM

では、続いてVMの処理を見ていきましょう。

Run()は、Op.Arrayでやっていることと同じですね。違いは、buildHashにありそうです。

func (vm *VM) Run() error {
    for ip := 0; ip < len(vm.instructions); ip++ {
        op := code.Opcode(vm.instructions[ip])

        switch op {
                 // 中略
　　　　        case code.OpHash:
            numElements := int(code.ReadUnit16(vm.instructions[ip+1:]))
            ip += 2

            hash, err := vm.buildHash(vm.sp-numElements, vm.sp)
            if err != nil {
                return err
            }
            vm.sp = vm.sp - numElements

            err = vm.push(hash)
            if err != nil {
                return err
            }

buildHash

buildHashの中身です。

func (vm *VM) buildHash(startIndex, endIndex int) (object.Object, error) {
    hashedPairs := make(map[object.HashKey]object.HashPair)

    for i := startIndex; i < endIndex; i += 2 {
        key := vm.stack[i]
        value := vm.stack[i+1]

        pair := object.HashPair{Key: key, Value: value}
        hashKey, ok := key.(object.Hashable)

        if !ok {
            return nil, fmt.Errorf("unusable as hash key: %s", key.Type())
        }

        hashedPairs[hashKey.HashKey()] = pair
    }

    return &object.Hash{Pairs: hashedPairs}, nil
}

やっていることはシンプルですね。

key := vm.stack[i]
value := vm.stack[i+1]

まずは、keyとvalueを順番にstackから参照して、それをHashオブジェクトの値にして返しています。

vm.sp = vm.sp - numElements
err = vm.push(hash)

で、最後はArrayと同じようにスタックポインタをハッシュの要素分、減らしてPushです。

まとめ

今回はHashについて見てまいりました。ほとんどArrayとやっていることは同じでしたね。

次回は、Indexについてコードの詳細を追ってみます！楽しみですね。

僕から以上。あったくして寝ろよ。

全体のコードはこちら

github.com

んだ日記

ndaDayoの技術日記です