テキスト上の位置の計算と合成 or 累積和の一例

テキスト上の何行目・何列目の形で表される位置の計算方法と合成について書き、累積和の実用的な例になっていることをいいます。

導入

プログラミング言語処理系では、主にエラー報告などのために、しばしばソースコード上の位置を扱います。例:

print!("{}", a);

エラー: 変数 `a` は定義されていません。(1行目、14列目)

位置は通常、人間にとって分かりやすい「y 行目の x 列目」という形で表現します。本稿ではこの形式を テキスト上の位置 と呼びます。y を行番号、x を列番号と呼ぶことにします。先頭は 0 行目の 0 列目です。(0-based index)

テキスト上の位置の計算

次にテキスト上の位置を計算する方法を述べます。

行番号は、その位置より前にある改行文字の個数に等しいです。すなわち、文字列の先頭から1文字ずつみていき、改行を発見するたびにカウンタを回せば求まります。

なお改行には CRLF (\r\n) と LF (\n) の2種類の形式がありますが、\n だけ数えれば十分です。(\r と \n の間が何行目かにはきっと興味ないでしょう。)

fn calculate_line_number(s: &str, i: usize) -> usize {
    let mut y = 0; // 行番号

    for c in s[..i].chars() { // c: 文字
        if c == '\n' { // 改行文字だったら
            y += 1;
        }
    }

    y
}

列番号は改行のたびに 0 にリセットされてしまうので、最後の改行の後ろから特定の位置までの長さに等しいです。

行番号の計算でも改行の位置を見ているので、一緒に求めても複雑にはなりません。

fn calculate_position(s: &str, i: usize) -> (usize, usize) {
    let mut y = 0; // 行番号
    let mut x = 0; // 列番号

    for c in s[..i].chars() { // c: 文字
        if c == '\n' {
            y += 1;
            x = 0;
        } else {
            x += c.len_utf8(); // 文字 c の長さを加算
        }
    }

    (y, x)
}

これは　O(i) 時間です。ソースコードの長さ N に関して O(N) 時間といった方が分かりやすいかもしれません。

各文字のテキスト上の位置を割り出す

複数のエラーを報告するときや、デバッグ情報を埋め込むときなど、テキスト上の位置を多数計算することがあります。

そういうときは、ソースコード全体に対して上のループを回して、各文字のテキスト上の位置を割り出してしまうのも1つの手です。これも O(N) 時間であり、十分に高速です。(ボトルネックになるほど遅くはないだろうの意)

fn calculate_positions(s: &str) -> Vec<(usize, usize)> {
    // positions[i] : i バイト目のテキスト上の位置
    let mut positions = vec![];
    positions.resize(s.len() + 1, (0, 0));

    let mut y = 0; // 行番号
    let mut x = 0; // 列番号
    let mut i = 0; // バイトインデックス

    for c in s.chars() { // c: 文字
        if c == '\n' {
            y += 1;
            x = 0;
        } else {
            x += c.len_utf8();
        }

        i += c.len_utf8();
        positions[i] = (y, x);
    }

    positions
}

(コードはイメージです。)

これは複数行文字列や複数行コメントなどの字句解析時に、バイトインデックスと行番号・列番号の両方を正しく更新するのがめんどくさいときに役立つかもしれません。

構文木組み替え後のテキスト上の位置

たいていのプログラミング言語にはテキストエディタ上にコンパイルエラーを表示する機能があります。「IDE 機能」とか「インテリセンス」とか「LSP サーバー」とかそういうやつです。

そのようなツールはプログラマーが 何か入力するたびに構文解析をやり直す ことになります。しかし、数文字書き換えた程度で構文木が一変することはそうそうなく、解析結果の大部分は同じ になるでしょう。

実際にはソースコード上で変化があった部分、例えば1つの関数の内部とかだけ再解析して、その部分だけ構文木を組み替えれば十分なはずです。(注: まだ実装はしてない。)

そのような構文木の組み替えの後、前項の「各文字のテキスト上の位置のマップ」は作り直しになります。これでは効率化になっていません。

構文木の 各ノードに「改行の個数」と「最後の改行の後の長さ」を持たせる という方法で再び効率化できそうです。

「改行の個数」と「最後の改行の後の長さ」はどちらも内部のソースコードが変化しなかったノードでは変わらないため、更新の範囲は組み換えられた部分の外に波及しなくなります。

また、テキスト上の位置が欲しいときは、構文木の枝をたどっていく過程で「改行の個数」を加算して行番号とし、最後の改行の後にある「最後の改行の後の文字数」の和を列番号とすればよいからです。

(コードはイメージしてください。)

「テキスト上の位置」がなすモノイド

(ほぼ余談)

競技プログラミング界隈の人は気づいていると思いますが、 「各文字のテキスト上の位置を割り出す」の節で使ったループはほぼ累積和のようなものです。ここで累積和の「和」とは何でしょうか。

集合 $\mathbb{N}^2$ = { (y, x) | y: 改行の個数 (≥0), x: 最後の改行の後の長さ (≥0) } を考えます。これに「和」として次の演算 (<>) を入れるとモノイドをなします。

    (y1, x1) <> (y2, x2) =
        | (y1 + y2,      x2)    if y2 >= 1
        | (y1 + y2, x1 + x2)    if y2 == 0

ここで文字 c をモノイドの元に対応させます。

    '\n' → (1, 0)
    c    → (0, 1)    (あるいは (0, c.len_utf8()))

こうすると前述のループを累積和と呼んでも許される気がしてきます。

そういうわけで累積和の実用的に面白い例の1つでした。

お詫び: 当初は「モノイドではない半群をなす」と記述していましたが、誤りでした。申し訳ありません。