rakudo-and-nqp-internals-courseに挑戦した話 その３

こんにちは、21日目の投稿になります。

# Introduction

みなさんは[rakudo-and-nqp-internals-course](https://github.com/edumentab/rakudo-and-nqp-internals-course)を知っていますか?
rakudo-and-nqp-internalsはMoarVMの開発者である[Jonathan Worthington氏](http://www.jnthn.net)の作ったnqpとrakudoの内部構造に関するチュートリアルです。

スライドだけじゃなくて、エクササイズ問題も用意されています。
http://edumentab.github.io/rakudo-and-nqp-internals-course/

というわけで、詳しい話はスライドを見てもらうとして、今回のアドベントカレンダーでは私がエクササイズ問題に挑戦していきたいと思います。

21日目はExercise 3に挑戦します。

# Exercise 3

## 3.1

3.1は問題というよりはちょっとコードを触ってみるだけの内容です。

[SlowDBの実装](https://github.com/edumentab/rakudo-and-nqp-internals-course/blob/master/examples/slowdb.nqp)をコピーして手元に持ってきましょう:

```
$ wget https://raw.githubusercontent.com/edumentab/rakudo-and-nqp-internals-course/master/examples/slowdb.nqp
```

中を見てみましょう:

```
grammar QueryParser {
    token TOP { ^ <query> $ }
    
    proto token query {*}
    token query:sym<insert> {
        'INSERT' \s <pairlist>
    }
    token query:sym<select> {
        'SELECT' \s <keylist>
        [ 'WHERE' \s <pairlist> ]?
    }
    
    rule pairlist { <pair>+ % [ ',' ] }
    rule pair     { <key> '=' <value>  }
    rule keylist  { <key>+ % [ ',' ] }
    token key     { \w+ }
    
    proto token value {*}
    token value:sym<integer> { \d+ }
    token value:sym<string>  { \' <( <-[']>+ )> \' }
}

class QueryActions {
    method TOP($/) {
        make $<query>.ast;
    }
    
    method query:sym<insert>($/) {
        my %to_insert := $<pairlist>.ast;
        make -> @db {
            nqp::push(@db, %to_insert);
            [nqp::hash('result', 'Inserted 1 row' )]
        };
    }
    
    method query:sym<select>($/) {
        my @fields  := $<keylist>.ast;
        my %filters := $<pairlist> ?? $<pairlist>.ast !! {};
        make -> @db {
            my @results;
            for @db -> %row {
                my $match := 1;
                for %filters {
                    if %row{$_.key} ne $_.value {
                        $match := 0;
                        last;
                    }
                }
                if $match {
                    my %selected;
                    for @fields {
                        %selected{$_} := %row{$_};
                    }
                    nqp::push(@results, %selected);
                }
            }
            @results
        }
    }
    
    method pairlist($/) {
        my %pairs;
        for $<pair> -> $p {
            %pairs{$p<key>} := $p<value>.ast;
        }
        make %pairs;
    }

    method keylist($/) {
        my @keys;
        for $<key> -> $k {
            nqp::push(@keys, ~$k)
        }
        make @keys;
    }
    
    method value:sym<integer>($/) { make ~$/ }
    method value:sym<string>($/)  { make ~$/ }
}

class SlowDB {
    has @!data;
    
    method execute($query) {
        if QueryParser.parse($query, :actions(QueryActions)) -> $parsed {
            my $evaluator := $parsed.ast;
            if $evaluator(@!data) -> @results {
                for @results -> %data {
                    say("[");
                    say("    {$_.key}: {$_.value}") for %data;
                    say("]");
                }
            } else {
                say("Nothing found");
            }
        } else {
            say('Syntax error in query');
        }
    }
}

# Uncomment to enable tracing.
# QueryParser.HOW.trace-on(QueryParser);

my $db := SlowDB.new();
while (my $query := stdin().get) ne 'quit' {
    $db.execute($query);
}
```

SELECTとINSERTを実行してみましょう:

```
$ nqp slowdb.nqp
INSERT name = 'larry', age = 63
[
    result: Inserted 1 row
]
SELECT name WHERE age = 63
[
    name: larry
]
```

## 3.2

+ DELETE 操作を追加してみましょうという問題です。

具体的には、下記のようなクエリを実行できるようにします:

```
DELETE WHERE name = ’jnthn’
DELETE WHERE name = ’jnthn’, is_action = 1
```

では、QueryParser, QueryActionsの順に説明していきます。

### QueryParser

ソースコード:

```
grammar QueryParser {
    token TOP { ^ <query> $ }
    
    proto token query {*}
    token query:sym<insert> {
        'INSERT' \s <pairlist>
    }
    token query:sym<select> {
        'SELECT' \s <keylist>
        [ 'WHERE' \s <pairlist> ]?
    }
    token query:sym<delete> { # (#1)
        'DELETE' \s 'WHERE' \s <pairlist>
    }
    
    rule pairlist { <pair>+ % [ ',' ] }
    rule pair     { <key> '=' <value>  }
    rule keylist  { <key>+ % [ ',' ] }
    token key     { \w+ }
    
    proto token value {*}
    token value:sym<integer> { \d+ }
    token value:sym<string>  { \' <( <-[']>+ )> \' }
}
```

+ deleteトークンを作ります。このとき、`name = ’jnthn’, is_action = 1`のような入力を受け付けるようにするために、pairlistトークンを流用します (#1)

### QueryActions

ソースコード(deleteのみ抜粋):

```
    method query:sym<delete>($/) {
        my %filters := $<pairlist> ?? $<pairlist>.ast !! {};
        make -> @db {
            my @remnant; # (#1)
            my @results; # (#2)
            while (nqp::elems(@db)) {
                my %row := nqp::shift(@db); # (#3)
                my $match := 1;
                for %filters {
                    if %row{$_.key} ne $_.value {
                        $match := 0;
                        last;
                    }
                }
                if $match {
                    nqp::push(@results, nqp::hash('result', 'Deleted 1 row'));
                } else {
                    nqp::push(@remnant, %row);
                }
            }
            for @remnant {
                nqp::push(@db, $_); # (#4)
            }
            @results;
        }
    }

```

+ ベースはSELECT操作です。これに修正を加えていきます。
+ `@remnant`は`@db`に残したい内容を一時保存するための配列です (#1)
+ `@results`はコンソールに表示したい処理結果を保存するための配列です (#2)
+ `shift` (#3) で`@db`の中身を空にした後、`push` (#4)で`@db`に必要な要素(i.e. WHERE句の条件にマッチしなかったもの)だけ入れなおすことでDELETE操作を実装していきます。`@db`に対して`@remnant`を束縛してはいけません。(※多分変数の[lexpadエントリ](https://docs.perl6.org/language/containers)関係の話[要出典]だと思いますが詳しいことは知りません)

## 3.3

+ UPDATE 操作を追加してみましょうという問題です。

具体的には、下記のようなクエリを実行できるようにします:

```
UPDATE WHERE type = ’stout’ SET tasty = 1
UPDATE WHERE type = ’stout’ SET tasty = 1, dark = 1
UPDATE WHERE type = ’stotu’ SET type = ’stout’
```

では、QueryParser, QueryActionsの順に説明していきます。

### QueryParser

ソースコード:

```
grammar QueryParser {
    token TOP { ^ <query> $ }
    
    proto token query {*}
    token query:sym<insert> {
        'INSERT' \s <pairlist>
    }
    token query:sym<select> {
        'SELECT' \s <keylist>
        [ 'WHERE' \s <pairlist> ]?
    }
    token query:sym<delete> {
        'DELETE' \s 'WHERE' \s <pairlist>
    }
    token query:sym<update> { # (#1)
        'UPDATE' \s 'WHERE' \s <pairlist>
        'SET' \s <pairlist>
    }
    
    rule pairlist { <pair>+ % [ ',' ] }
    rule pair     { <key> '=' <value>  }
    rule keylist  { <key>+ % [ ',' ] }
    token key     { \w+ }
    
    proto token value {*}
    token value:sym<integer> { \d+ }
    token value:sym<string>  { \' <( <-[']>+ )> \' }
}
```

+ SET句もWHERE句もpairlistトークンを使うとうまく表現できます。 (#1)

### QueryActions

ソースコード(updateのみ抜粋):

```
    method query:sym<update>($/) {
        my %filters := $<pairlist>[0] ?? $<pairlist>[0].ast !! {}; # (#1)
        my %settings := $<pairlist>[1] ?? $<pairlist>[1].ast !! {}; # (#2)
        make -> @db {
            my @results;
            my @updated; # (#3)
            while (nqp::elems(@db)) {
                my %row := nqp::shift(@db); # (#4)
                my $match := 1;
                for %filters {
                    if %row{$_.key} ne $_.value {
                        $match := 0;
                        last;
                    }
                }
                if $match == 1 {
                    for %settings {
                        %row{$_.key} := $_.value;
                    }
                    nqp::push(@results, %row);
                }
                nqp::push(@updated, %row);
            }
            for @updated {
                nqp::push(@db, $_); # (#5)
            }
            @results;
        }
    }

```

+ これもベースはSELECT操作です。これに修正を加えていきます。
+ WHERE句側の内容は`%filters`に(#1)、SET句側の内容は`%settings`に(#2)代入します。
+ `@db`に残したい内容を一時保存するための配列`@updated`を用意します (#3)
+ `shift` (#4) で`@db`の中身を空にした後、`push` (#5)で`@db`に必要な要素(i.e. WHERE句の条件にマッチした場合に、SET句で指定された内容を上書きしたもの)だけ入れなおすことでUPDATE操作を実装していきます。

## 3.4

+ WHERE句を表現するシーケンスが何度も生起していたと思います。この重複してしまった部分をトークンで表現してみようという問題です。

whereトークンを作りましょう:

```
    token query:sym<select> {
        'SELECT' \s <keylist>
        <where>?
    }
    token query:sym<delete> {
        'DELETE' \s <where>
    }
    token query:sym<update> {
        'UPDATE' \s <where>
        'SET' \s <pairlist>
    }
    token where {
        'WHERE' \s <pairlist>
    }
```

3.5は解いてないです :)

以上、21日目の投稿でした。

# ライセンス
rakudo-and-nqp-internals-course is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.