正規表現でstickyが使えないとき

JavaScript内でパーザーのようなものを実装しようとして正規表現のstickyフラグを使用していました。

stickyフラグとは開始位置から指定した正規表現が始まっていなければマッチしない、というものです。

let re = /([A-Za-z_][0-9A-Za-z_]*)/gy; // yをつけることでstickyフラグがONになる

re.lastIndex = 5;
let match = re.exec("1234 ABCDEFG");
// => match: [0: 'ABCDEFG', 1: 'ABCDEFG', length: 2, index: 5]

re.lastIndex = 5;
let match2 = re.exec("1234 5678 ABCDEFG");
// => null

しかし、stickyってIEではサポートされていないんですね...

仕方ないのでとりあえずstickyなしで、見つかった場所が開始位置でなければ見つかっていないことにしていました。

function stickyMatch(re, text, index) {
  re.lastIndex = index;
  let match = re.exec(text);
  return match && match.index === index ? match : null;
}

let re = /([A-Za-z_][0-9A-Z-a-z_]*)/g;
let match = stickyMatch(re, "1234 ABCDEFG", 5);
// => match: {0: 'ABCDEFG', 1: 'ABCDEFG', length: 2, index: 5}

let match2 = stickyMatch(re, "1234 5678 ABCDEFG", 5);
// => null

が、これだと長いテキストをパーズしているときにちょっとした性能問題にぶち当たります。

開始位置にパターンにマッチする文字列が存在しないとき、検索が文字列の最後まで走ってしまいます。パーザーで使用するつもりなのでそれが最悪で文字列の長さ分繰り返されるため、ちょっと考えるだけで$O(n^2)$以上のコストになります。

どうしたもんかと頭を抱えていたんですが、ふと思いついたのでメモ書き。

function stickyMatch(re, text, index) {
  re.lastIndex = index;
  let match = re.exec(text);
  return match && match[match.length - 1] === undefined ? match : null;
}

let re = /([A-Za-z_][0-9A-Z-a-z_]*)|()/g; // 最後の |()がミソ

let match = stickyMatch(re, "1234 ABCDEFG", 5);
// => match: {0: 'ABCDEFG', 1: 'ABCDEFG', 2: undefined, length: 3, index: 5}

let match2 = stickyMatch(re, "1234 5678 ABCDEFG", 5);
// => match2: null

正規表現の最後に|()をつけることで指定したパターンにマッチしなくても、開始位置で確実にマッチして文字列の余計な操作が実行されません。また本来マッチしてほしいパターンがあればちゃんとマッチします。

最後に指定しているので、マッチしてほしいパターンが開始位置になければ最後の()にはマッチするので''になっているはずです。逆に開始位置にパターンがあればundefinedになっています。つまりmatch[match.length - 1] === undefinedであれば、本来のパターンにマッチしたことがわかります。

いちいち|()をつけて回るのが面倒でpolyfillを書こうとしたけど、/～/yはJavaScriptのエンジン側で対応しなければ無理と気づいて断念。