Text-Liq-XS/XS.c tokenize のマークアップ名認識部をダブル配列に変更

Text-Liq では XS ともども次のパターンで始まるものをマークアップとして認識し、これに出会うと、正規表現を切り替えてマークアップ内部のトークン切り出しをおこないます。

    \{%\s*
    (?: assign | break | capture | case | comment | continue | cycle
    |   else | elsif | endcapture | endcase | endfor | endif
    |   endunless | for | if | ifchanged | include | increment | raw
    |   when)\b
    \s*

この中のマークアップ名のパターンはトライで表現可能なわけですが、XS では、当初はデバッグしやすさから、トライを使わず、文字列一致を順に試すやりかたにしていました。それから、何度か手をいれて、もうバグ取りは十分だろうと判断して、トライを使うように修正しました。

トライを扱う方法は何通りもの方法があるのですが、今回は、ダブル配列を採用しました。ダブル配列によるトライの DFA 遷移は高速で簡潔に記述できるのが魅力です。ダブル配列を更新するのは面倒なのですが、静的なトライなので一度生成するだけで済みます。

今回の実装はオーソドックスにトライ木を深さ優先で探索し、枝分かれ箇所でダブル配列から利用可能な空きパターン箇所を先頭から探して、そこに置いています。ルートは 1 にしています。なお、添字をゼロからではなく 1 から始めているのは重複を避けるのに都合が良いためです。各文字列の終端記号のインデックスは 1 で、2 は英小文字 a で、以下英小文字 z まで続きます。

my @markup = qw(
    assign break capture case comment continue cycle decrement
    else elsif endcapture endcase endfor endif endifchanged
    endunless for if ifchanged include increment raw unless when
);

# double array
my @base;
my @check;

my $EOS = "\x24";
my %code = ($EOS => 1, map { $_ => (ord $_) - (ord 'a') + 2 } 'a' .. 'z');

make_array(@markup);

for my $w (@markup) {
    my $b = match_array($w);
    $base[$b] = uc "liq_$w";
}

sub any {
    my($yield, @a) = @_;
    for (@a) {
        return 1 if $yield->($_);
    }
    return;
}

sub make_array {
    my(@words) = @_;
    my @keylist = map { $_ . $EOS } sort @words;
    @base = (-1, 1);
    @check = (-1, 0);
    my @stack = (\@keylist, 0, 1);
    while (@stack) {
        my($a, $i, $parent) = splice @stack, -3;
        next if ! @{$a};
        my %h = map { (substr $_, $i, 1) => 1 } @{$a};
        my @edge = sort keys %h;
        my @edgecode = map { $code{$_} } @edge;
        my $b = 1 - $edgecode[0];
        while (any(sub{ defined $check[$b + $_] }, @edgecode)) {
            ++$b
        }
        $base[$parent] = $b;
        for my $j (@edgecode) {
            $check[$b + $j] = $parent;
        }
        my $i1 = $i + 1;
        for my $c (reverse @edge) {
            my @a1 = grep {
                $i1 < (length $_) && (substr $_, $i, 1) eq $c
            } @{$a};
            push @stack, \@a1, $i1, $b + $code{$c};
        }
    }
    return;
}

sub match_array {
    my($word) = @_;
    my $s = $word . $EOS;
    my $b = 1;
    for my $c (split //, $s) {
        my $b1 = $base[$b] + $code{$c};
        return if ! defined $check[$b1] || $check[$b1] != $b;
        $b = $b1;
    }
    return $b;
}

このスクリプトで生成したダブル配列を使ってマークアップ名の一致検査をしています。該当箇所を抜き出しました。

        case 1:
            if (c == '{') {
                LIQ_TOKENIZE_READ_AND_JUMP(2);  /* (.*?)\{_\{ */
            }
            else if (c == '%') {
                markup_b = 1;
                LIQ_TOKENIZE_READ_AND_JUMP(3);  /* (.*?)\{_% */
            }
            else {
                LIQ_TOKENIZE_READ_AND_JUMP(0);
            }
            break;
        case 3:
            LIQ_TOKENIZE_SPACE_STAR(4); /* (.*?)\{%_\s* */
            break;
        case 4:
            LIQ_TOKENIZE_PEEK_AND_JUMP(0); /* default */
            if (c >= 'a' && c <= 'z')  {
                markup_b_next = liq_markup_base[markup_b] + c - 'a' + 2;
                if (markup_b_next > 0 && markup_b_next < LIQ_TRIE_MARKUP_SIZE
                        && liq_markup_check[markup_b_next] == markup_b) {
                    markup_b = markup_b_next;
                    LIQ_TOKENIZE_READ_AND_JUMP(4);
                }
            }
            else if (! isALNUM_uni(c)) {
                markup_b_next = liq_markup_base[markup_b] + 1;
                if (markup_b_next > 0 && markup_b_next < LIQ_TRIE_MARKUP_SIZE
                        && liq_markup_check[markup_b_next] == markup_b) {
                    token_kind = liq_markup_base[markup_b_next];
                    LIQ_TOKENIZE_PEEK_AND_JUMP(5);
                }
            }
            break;
        case 5:
            LIQ_TOKENIZE_SPACE_STAR(6); /* (.*?)\{%\s*\w+_\s* */
            break;

tokenize の NFA 状態 1 で、{% を検出した段階でダブル配列の状態 markup_b を 1 に初期化し、NFA 状態 3 でスペースを読み飛ばします。NFA 状態 4 でダブル配列による遷移を繰り返します。ここで、英数字以外を先読みしたら、文字列終了インデックス 1 でダブル配列で遷移可能なのかどうかをチェックして、遷移可能なら、一致したと判定して NFA 状態を 5 に移してスペースを読み飛ばします。