Text-Creolize を Javascript に移植

ブラウザ側で Wiki フォーマッタとテキスト差分を動かす Wiki でも作ってみようかと Perl で記述した Text-Creolize を javascript-1.6 に移植しだしたところ、標準の正規表現で非欲張りマッチが使えないことを初め、いろいろと苦しむハメになって土日を潰してしまいました。なんとか、Creole1.0Test を処理できるコードまでたどり着いたので、リファクタリングしていない炊きたてホカホカものを記念に GIST に上げておきます。

https://gist.github.com/1496276/d55fb471c47d3190c366c933fa493b820f97e5a9

以下、自分のためのメモです。

  1. markup() と emit_block() は Perl から直訳したものがそのまま動作しました。ここは楽でした。あまりに楽だったので、この調子でブロックとインラインもできるだろうと甘くみたのが敗因だったようで……。
  2. ブロックでは正規表現を使わず、String.indexOf() と String.substr() 比較で非欲張りマッチの正規表現エンジンと等価な動作をするコードにハンドコンパイルしました。30年前にスキャナを書いていたときは、この手を使ったものです。何もかも懐かしい。
  3. インラインでは、欲張りマッチを使って非欲張りマッチ動作をする正規表現を作っています。こちらは、一つ作ってしまえばワンパターンで記述できるので、ブロックよりは楽でした。
  4. インラインの正規表現を何通りも作る気にはならなかったので、Perl では別枠で処理していた定義リストとテーブル行の処理をインライン部に統合しました。予想していたよりも、可読性が落ちなかったので、Perl 版にバックポートしてもいいかもしれません。

インライン部は大枠では同じなので、ブロック部のメモを。

Perl 版のブロック・スキャナは、非欲張りマッチに依存する典型的な /\G(.*?)(?:PATTERN)/gcmsx ループになっています。

    while ($s =~ m{
        \G(.*?)^
        (?: \{\{\{\n (.*?) \n\}\}\}\n
        |   [ ]*
            (?: () \n
            |   () ----+ [ ]*\n
            |   (=+) [ ]* (.*?) [ ]* (?:(?<!~)=+[ ]*)? \n
            |   # ...
            )
        )
    }gcmsx) {
        # ... マッチした結果を使うところ
    }

これを、文字列サーチと比較を使う低レベル処理にハンドコンパイルするには、2重ループにします。外側のループは Perl の while ループの役割をし、内側のループで /\G(.*?)^(?:PATTERN1|..)/ の非欲張りマッチ範囲を後続パターンに一致するまで伸ばしていきます。内側のループ内で行頭に文字ポインタを進めて、それから、各パターンと一致するかどうかを調べます。一致したら、内側のループを break で抜け出します。どれにも一致しないときは、文字ポインタを進めて、次の行頭からパターンが一致するかどうかを繰り返しチェックします。

    var pos = 0, epos = s.length;
    while (pos < epos) {
      capture[1].start = capture[1].end = pos;
      while (pos < epos) {
        if (pos > 0 && s.charAt(pos - 1) != '\n') /* (?m:\G(.*?)^) */
          pos = s.indexOf('\n', pos) + 1;
        assert(pos == 0 || s.charAt(pos - 1) == '\n'); /* 行頭に一致(?m:^) */
        capture[1].end = pos;
        if (/* PATTERN1 の可能性あり */) {
          /* PATTERN1 全体への一致を判別 */
          if (/* PATTERN1 全体に一致した */)
            break;
          else
            continue; /* continue しなくても構わないが、pos が進んでいるので最適化 */
        }
        // 他の選択肢への一致をチェック
        // すべてダメだったときは、\G(.*?) の非欲張りマッチの範囲を伸ばす。
        pos = s.indexOf('\n', pos) + 1; /* ++pos でもいいけど、最適化 */
      }
      // ... マッチした結果を使うところ
    }

非欲張りマッチは、簡単に言えば、後続パターンに一致する一番近い文字列位置を求めることで実現できます。後続パターンが文字列リテラルだと、indexOf() で探すだけです。上の場合では、行末記号を探しています。最初の verbatim との一致判定も後続パターンは文字列リテラルなので簡単です。下の記述は最初に書いた直訳で、GIST にあるのは不要な変数を除去した後のものです。

      if (s.substr(pos, 4) == '{{{\n') {
        var start = pos + 4;
        var end = s.indexOf('\n}}}\n', pos + 2);
        if (end == -1) {
          pos = capture[1].end + 4;
          continue;
        }
        capture[2].start = start;
        capture[2].end = end;
        pos = end + 5;
        break;
      }

ヘッディングのパターンでは、末尾のイコール記号列に一致するかどうか調べる部分があります。素直に直訳すると、pos を 1 つずつ増やしつつ、後続イコール列パターンに一致するかどうか調べるように記述しますが、ここは最適化して、行末記号を探してから前に後戻りしながら、一致するかどうかをチェックするようにしました。これも直訳版から。

        if (s.charAt(pos) == '=') {
          capture[5].start = pos;       /* ^[ ]*(=+)[ ]* */
          while (s.charAt(pos) == '=')
            ++pos;
          capture[5].end = pos;
          while (s.charAt(pos) == ' ')
            ++pos;
          capture[6].start = pos;       /* (.*?) [ ]* (?:(?<!~)=+[ ]*)? \n */
          var eol = s.indexOf('\n', pos);
          pos = eol - 1;
          while (pos >= capture[6].start && s.charAt(pos) == ' ')
            --pos;
          capture[6].end = pos + 1;
          while (pos >= capture[6].start && s.charAt(pos) == '=')
            --pos;
          if (pos < capture[6].start || s.charAt(pos) != '~') {
            while (pos >= capture[6].start && s.charAt(pos) == ' ')
              --pos;
            capture[6].end = pos + 1;
          }
          pos = eol + 1;
          break;
        }

他も似たようなものなので略します。Perl 版の条件付きで正規表現を切り替えていた部分は、Javascript 版では条件判定に組み込み、条件付きマッチングにしています。せっかく正規表現エンジンを文字列検査ループに展開したこともあり、Perl 版に対して、ブロッククォートを取り込むロジックの最適化を進めることができました。定義リストもすっきりしました。ブロッククォートのロジックを Perl 版にバックポートするのは厳しそうですけど、定義リストは可能でしょう。