edit-cxx11 その 4 editor_type 続き

editor_type クラスのアドレス式評価関数 evaladdr () が正規表現にマッチングする行を探すとき、 find メンバ関数を使います。 このメンバ関数は、引数に行番号 line と探す方向 way を与えます。 探索対象行には line は含まれず、way が +1 なら line + 1 から、way が -1 なら line - 1 の行番号の行から探索を始めます。 way が +1 のとき、最終行の次は先頭行に戻って line - 1 まで探索を続行します。 way が -1 のとき、番兵行 0 の次は最終行に進んで line + 1 まで戻りながら探索を続けます。

    $=1, line=0, way=+1 => {1}
    $=1, line=0, way=-1 => {1}
    $=1, line=1, way=+1 => {0}
    $=1, line=1, way=-1 => {0}

    $=8, line=0, way=+1 => {1, 2, 3, 4, 5, 6, 7, 8}
    $=8, line=0, way=-1 => {8, 7, 6, 5, 4, 3, 2, 1}
    $=8, line=1, way=+1 => {2, 3, 4, 5, 6, 7, 8, 0}
    $=8, line=1, way=-1 => {0, 8, 7, 6, 5, 4, 3, 2}
    $=8, line=4, way=+1 => {5, 6, 7, 8, 0, 1, 2, 3}
    $=8, line=4, way=-1 => {3, 2, 1, 0, 8, 7, 6, 5}
    $=8, line=8, way=+1 => {0, 1, 2, 3, 4, 5, 6, 7}
    $=8, line=8, way=-1 => {7, 6, 5, 4, 3, 2, 1, 0}

このような行番号の数列を生成する方法を考えてみます。 まず、 buffer_type では、 行番号は番兵行 0 に続いて、先頭行 1 から最終行 $ まで連続した整数値をとります。空のときに $ の値を 0 にします。 欲しい行番号の数列は循環になっており、 空のときを除くと、 0 から $ - 1 までの数列に、 line + way のオフセットを加算して、 $ + 1 を法にして剰余演算すると、 行番号の数列が求まります。way が負のときも、逆向きにオフセットを求めて $ + 1 を法とする剰余演算をおこないます。

int
editor_type::find (int line, int way, std::wstring const& pattern)
{
    regexp_type re;
    re.compile (pattern);
    int dol = buffer.dollar ();
    if (0 == dol)
        return line;
    for (int i = 0; i < dol; ++i) {
        int xline = (line + way * (i + 1)) % (dol + 1);
        if (0 == xline)
            continue;
        std::wstring::const_iterator s, e;
        buffer.get (xline, s, e);
        if (match (re, s, e))
            return xline;
    }
    return line;
}

match はコンパイル済みの正規表現が行にマッチングするかどうかを調べます。使っている regexp_type の execute は文字列の指定部分からマッチングするかどうかを調べるだけなので、match で、行の先頭から末尾までスキャンポインタを動かして、マッチングするかどうかをチェックしていきます。execute をおこなう行では行末記号を chomp_bang で取り除いています。 当初は取り除き不要だと考えていたのですけど、 行末記号の次の文字列末尾位置は正規表現にとっては空行の 2 行目になっており /^$/ にすべてのバッファの行がマッチングしてしまいます。 取り除きは必要です。

bool
editor_type::match (regexp_type& re,
    std::wstring::const_iterator s, std::wstring::const_iterator eos)
{
    std::vector<std::size_t> cap;
    std::wstring::const_iterator const bos = s;
    chomp_bang (bos, eos);
    for (; s <= eos; ++s) {
        if (re.execute (s, bos, eos, cap))
            return true;
    }
    return false;
}

s コマンド用の substitute メンバ関数は、 match を使わずに、自分のループの中から regexp_type の execute を呼んでいます。正規表現にマッチングした箇所で substhere メンバ関数で置換テンプレートを更新して doc に追加します。 置換のアルゴリズムは kernighan & Plauger Software Tools (1976) の edit コマンドのものをアレンジして使っています。 このアルゴリズムは、 ゼロ幅のマッチング時に一回だけ置換をおこなって次の文字へスキャンポインタを進めていくため、ゼロ幅マッチングと g フラグを併用しても無限ループに陥らずにすみます。

    a
    xy
    xay
    xaaaay
    .
    -2,.s/a*/A/g
    -2,.p
    AxAyA
    AxAyA
    AxAyA

ところで、 PerlRuby が使っているアルゴリズムでは、 上に相当する置換をおこなうと 2 番目と 3 番目は、AxAAyA になります。 K&P のアルゴリズムは、 直前にマッチングした範囲の終わりを記録しておき、 次回のマッチング範囲の終わりが異なるときだけ置換をして、AxAyA を得ます。 PerlRuby は記録の手間を省いているため、 まんなかで 2 回置換をおこなってしまうわけです。 当初は、PerlRuby に合わせていたのですが、 K&P のふるまいの方が自然なのでさしかえました。

void
editor_type::substitute (std::wstring const& pattern,
    std::wstring const& replacement, bool gflag, 
    std::wstring::const_iterator s, std::wstring::const_iterator eos,
    std::wstring& doc)
{
    regexp_type re;
    std::vector<std::size_t> cap;
    std::wstring::const_iterator const bos = s;
    if (! re.compile (pattern))
        return;
    int hasnewline = (bos < eos && '\n' == eos[-1]);
    if (hasnewline)
        --eos;
    /* see edit subst of Kernighan & Plauger, ``Software Tools'' (1976) */ 
    std::wstring::const_iterator lastm = bos - 1;
    for (; s <= eos; ++s) {
        std::wstring::const_iterator m = bos - 1;
        if (re.execute (s, bos, eos, cap))
            m = bos + cap[1];
        if (bos <= m && lastm != m) {
            substhere (bos, replacement, cap, doc);
            lastm = m;
            if (! gflag) {
                if (m < eos)
                    doc.append (m, eos);
                break;
            }
        }
        if (bos <= m && m != s)
            s = m - 1;
        else if (s < eos)
            doc.push_back (*s);
    }
    if (hasnewline)
        doc.push_back ('\n');
}

substhere メンバ関数は、置換テンプレートの置換変数を正規表現でキャプチャした部分文字列におきかえて文字列に追加します。置換変数は $1 から $9 までが正規表現のグループに対応し、$&$0 がマッチングした部分文字列に置き換わります。また、 バックスラッシュによるクォートで改行とタブへも置換できるので、 split 処理に近いことを s コマンドでできるようにしてあります。

void
editor_type::substhere (
    std::wstring::const_iterator const bos,
    std::wstring const& replacement,
    std::vector<std::size_t>& cap, std::wstring& doc)
{
    std::wstring::const_iterator i;
    for (i = replacement.cbegin (); i < replacement.cend (); ++i)
        if ('$' == i[0] && i + 1 < replacement.cend ()
                && ('&' == i[1] || ('0' <= i[1] && i[1] <= '9'))) {
            std::size_t n = '&' == i[1] ? 0 : i[1] - '0';
            if (n * 2 + 1 < cap.size ()
                    && cap[n * 2] != std::wstring::npos
                    && cap[n * 2 + 1] != std::wstring::npos)
                doc.append (bos + cap[n * 2], bos + cap[n * 2 + 1]);
            ++i;
        }
        else if ('\\' == *i && i + 1 < replacement.cend ()) {
            int c = *++i;
            c = 'n' == c ? '\n' : 't' == c ? '\t' : c;
            doc.push_back (c);
        }
        else
            doc.push_back (*i);
}