括弧のネスト構造を正しく判定するマッチングアルゴリズム

背景

「カーソル位置のデリミタ（括弧・引用符）間のテキストを1キーで選択・コピーする」VSCodeマクロを作る際、単純な「次に出てくる終了デリミタを探す」実装では、ネストした括弧で誤動作することが分かりました。

1. 単純な実装が失敗するケース

function(a, (b, c), d)
        ↑ここにカーソル

functionの直後の(から、右方向に最初に見つかった)を探すと、b, c)の閉じ括弧にマッチしてしまい、function(a, (b, cが選択される、という誤動作が起きます。単純なindexOfでは、この入れ子構造を扱えません。

2. ネストレベルをカウントする解決策

function findMatchingEndDelimiter(
    lineText: string,
    startPos: number,
    startDelimiter: string,
    endDelimiter: string
): number {
    if (startDelimiter === endDelimiter) {
        return lineText.indexOf(endDelimiter, startPos + 1);
    }

    let nestLevel = 1;
    for (let i = startPos + 1; i < lineText.length; i++) {
        const char = lineText[i];
        if (char === startDelimiter) {
            nestLevel++;
        } else if (char === endDelimiter) {
            nestLevel--;
            if (nestLevel === 0) {
                return i;
            }
        }
    }
    return -1;
}

開始デリミタが見つかった時点でnestLevel = 1からスタートし、同じ開始デリミタが再度出現するたびに+1、終了デリミタが出現するたびに-1します。nestLevelが0に戻った位置こそが、最初の開始デリミタに対応する終了デリミタです。

トレース例（function(a, (b, c), d)）：

function( → nestLevel = 1
(b        → nestLevel = 2（ネストが深くなる）
c)        → nestLevel = 1（ネストから抜ける）
d)        → nestLevel = 0 ✅ ここが対応する閉じ括弧

3. 開始文字=終了文字の場合は別ロジックに分岐

if (startDelimiter === endDelimiter) {
    return lineText.indexOf(endDelimiter, startPos + 1);
}

"や'のように開始・終了が同じ文字のデリミタは、ネストという概念自体が成立しません（"a"b"c"の場合、2番目の"が閉じ括弧として扱われるのが自然な挙動）。そのため、この場合だけ従来通りの単純なindexOf検索にフォールバックしています。

4. 逆方向（終了→開始）も同じロジックを反転して実装

function findMatchingStartDelimiter(
    lineText: string, endPos: number,
    startDelimiter: string, endDelimiter: string
): number {
    let nestLevel = 1;
    for (let i = endPos - 1; i >= 0; i--) {
        const char = lineText[i];
        if (char === endDelimiter) {
            nestLevel++;
        } else if (char === startDelimiter) {
            nestLevel--;
            if (nestLevel === 0) {
                return i;
            }
        }
    }
    return -1;
}

選択方向によって「右に開始デリミタから終了デリミタを探す」処理と「左に終了デリミタから開始デリミタを探す」処理の両方が必要になるため、走査方向とカウントの増減を反転させた対の関数を用意しています。

まとめ

Ctrl+Shift+\（VSCode標準の対応括弧ジャンプ）と同じ考え方の、ネストレベルをカウントするマッチングアルゴリズムでした。開始=終了文字のケースだけ別ロジックに分岐させる、という条件分岐が実装のポイントです。18種類のデリミタ対応や選択方向による動作切り替えを含む全コードは元記事にまとめています。

→ デリミタ間テキスト選択コピーを実現するTypeScriptマクロ（ブログ）