やったこと

Naraku

HIRなどの仕様を考えている。

まずパース後の正規表現をpreprocessする。
preprocessでは以下のことを行う。

1. GroupNameResolver
   • 名前付きグループのグループ番号の設定
2. GroupRefResolver
   • 後方参照・条件グループ・部分式呼び出しの参照先のグループ番号の解決
   • 深さ付きの参照が使われるキャプチャの記録
3. EmptyMatchAnalyzer
   • 各ノードが空文字列にマッチするかどうかの判定
4. InfiniteCalAnalyzer
   • 部分式の呼び出しが空文字列で無限に再帰しないか (左/右再帰) のチェック
5. EmptyLoopCapsAnalyzer
   • 空ループが依存しているキャプチャのグループ番号の計算
6. CharClassExpander
   • 文字クラス ([...]) を範囲の配列に変換する
   • 文字タイプ (\w) やプロパティ (\p{...}) なども同様
7. IgnoreCaseExpander
   • ignore_case に従って文字列を展開 (unfold) する
     • /abc/ を /[aA][bB][cC]/ のようにする
     • ただし展開後が大きくなりそうならそのままを保つ
   • 文字クラスも展開 (unfold) する

次にpreprocess後の正規表現をHIRへと変換する。
HIRは次のような構造:

// HIRにloweringされた正規表現
struct HIR:
  entry: BlockId
  blocks: Map[BlockID, Block]

// ブロック
struct Block:
  insts: Array[Inst]
  term: Term

// 命令
enum Inst:
  // 通常の文字列のマッチ
  case Match(lit: String, info: MetahInfo)
  // `.` のマッチ
  // `Class` でもいいけど最適化用
  case Dot(newline: Bool, dir: Dir)
  // 文字クラスとのマッチ
  // (`\w` や `\p{...}` なども `intervals` に展開されている前提)
  case Class(intervals: Array[Interval], info: MetahInfo)
  // 後方参照とのマッチ
  case Ref(cap_ids: Array[CapId], depth: Option[Int], info: MetahInfo)
  // ゼロ幅アサーション
  case Assert(assertion: Assertion)
  // キャプチャ
  case CapBegin(cap_id: CapId
  case CapEnd(
    cap_id: CapId,
    // 深さ指定での後方参照に対応するために、`call_caps` へ記録する必要があるか
    needs_depth: Boolean,
    // 空ループのチェックのために `cap_gen` に記録する必要があるか
    empty_check: Boolean
  )
  // アトミックグループ
  case AtomicBegin // `MarkAtomic`を`bt_stack`に積む
  case AtomicEnd   // `ProtectAtomic`を`bt_stack`に積む
  // カウンタによる繰り返し
  case ResetReg(reg_id: RegId)
  case IncReg(reg_id: RegId)
  // 空ループのチェック
  // `loop_gen[loop_id]` を更新し、`current_gen`をインリメントする
  case SaveCapGen(loop_id: LoopId)
  // メモ化
  // 複数のブロックから遷移してくる可能性のある分岐の前、
  // あるいはLookAroundの開始位置に追加される (メモ化可能なパターンの場合)
  case Memo(info: MemoInfo)

// 文字を読み進める命令のメタ情報
struct MatchMeta:
  // `i` フラグが有効か
  ignore_case: Bool
  // case foldingの情報 (`ignore_case` が `true` のときだけ意味がある)
  fold: FoldFlag
  // マッチの向き
  dir: Dir

// マッチの向き
enum Dir:
  // 通常、先読み中
  case Forward
  // 後読み中
  case Backward

// ゼロ幅アサーションの種類
enum Assertion:
  case WordBoundary(dir: Dir)    // `\b`
  case NonWordBoundary(dir: Dir) // `\B`
  case LineBegin                 // `^`
  case LineEnd                   // `$`
  case Begin                     // `\A`
  case End                       // `\z`
  case EndLoose                  // `\Z`
  case MatchBegin                // `\G`

// ブロック終端の命令
enum Term:
  // ブロックの遷移
  case Next(tr: Trans)

  // 部分式の呼び出し
  // `sub_stack` に `Call(pos, ret)` をpush、`bt_stack` に `PopCall` をpushしてsubに飛ぶ
  case Call(sub: BlockId, ret: BlockId)

  // 先読み・後読み
  // `sub_stack` に `LookAround(pos, positive, dir, to)` をpush、`bt_stack` に `MarkLookAround` をpushしてsubに飛ぶ
  case LookAround(positive: Bool, dir: Dir, sub: BlockId, to: BlockId)

  // 非包含オペレータ `(?~...)`
  // `sub_stack` に `Absence(pos, sub, to)` をpush、`bt_stack` に `MarkAbsence` をpushして、subに飛ぶ
  case Absence(sub: BlockId, to: BlockId)

  // 条件付きグループ `(?(ref)yes|no)`
  // refが有効ならyes、無効ならnoに分岐するが、
  // この分岐はアトミック (yesで失敗したからといってnoにバックトラックしない) なため、
  // 特別な命令が必要になる
  case Conditional(cap_nums: Array[Int], depth: Option[Int], yes: BranchId, no: BranchId)

  // パターン全体の終端
  // マッチを終了する
  case End

  // マッチの失敗 (バックトラックが起こる)
  // `bt_stack` をpopして状態を戻していく
  // 次の特別なアイテムをpopした場合止まる (`ProtectAtomic` や `ProtectLookAround` の対応の中ではスキップされる、`call_stack` の `pop` は行う)
  // - `Bt(pos, tr)`: `pos`に戻して `tr` の遷移を試みる。遷移できなければバックトラックを続ける
  // - `MarkLookAround`: `call_stack` をpopして、肯定か否定か確認。肯定ならそのままバックトラックを続ける、否定ならマッチに成功しているので`pos`に戻してから`to`に飛ぶ
  // - `MarkAbsence`: `call_stack` をpopして、`bt_stack`に `Absence(next_pos, sub, to)`をpushして、`to`に飛ぶ。`next_pos`は次の`pos`の位置
  // - `Absence(next_pos, sub, to)`: `Absence`と同等のことを `next_pos` で行う
  case Fail

  // LookAroundの終端
  // `call_stack`をpopして `pos` と `to` を得て、肯定か否定かで意味が変わる:
  // - 肯定の場合: `bt_stack` に `ProtectLookAround` をpushして、`pos` に戻してから`to`に飛ぶ
  // - 否定の場合: 対応する`MarkLookAround` (ネストを考慮して) までpopしてからバックトラック
  case EndLookAround

  // Callの終端
  // `call_stack`をpopして`ret`を得て、`bt_stack`に`PushCall(ret)`をpushして`ret`にジャンプする
  case Return

  // Absenceの終端
  // absence operatorで終端に到達する (= マッチに成功する) ということは、マッチに失敗するということ
  // `call_stack`をpopして、`bt_stack`を`AbsenceMark`が出るまでpopしてからバックトラックする
  case EndAbsence

// ブロックの遷移
// 複数に分岐する場合のためにリンクリストになっている
enum Trans:
  // バックトラックを伴う分岐の遷移
  // 条件を満たした場合 `bt_stack` に `Bt(pos, tr)` をpushして、`to` に飛ぶ
  case Fork(
    cond: Array[Cond], // 遷移の条件 (AND)、空なら無条件
    to: BlockId,
    tr: Trans
  )
  // バックトラックしない遷移
  case Jump(
    cond: Array[Cond], // 遷移の条件 (AND)、空なら無条件
    to: BlockId
  )

enum Cond:
  // カウンタによる繰り返し
  case LtReg(reg_id: RegId, n: Int)
  // 空ループのチェック
  case CheckCapGen(loop_id: LoopId, cap_ids: Array[CapId])
  // 他にも、次のバイト値が何である必要があるか、残り最低でも何バイト必要か、
  // などの条件が最適化で設定されうる

HIRの実行モデル:

struct HIRRuntime:
  // マッチ中の文字列の位置
  pos: Int
  // バックトラック用のスタック
  bt_stack: Stack[Bt]
  // 部分式の呼び出しや先読みなどのスタック
  sub_stack: Stack[Sub]
  // キャプチャ
  caps: Map[CapId, CapState]
  call_caps: Array[Map[CapId, CapState]]
  // バックトラックが有効かの
  // 空ループの判定用
  current_gen: Int
  loop_gen: Map[LoopId, Int]
  cap_gen: Map[CapId, Int]

// バックトラック用のスタック
// マッチに失敗したときなどにここからpopしていく
enum Bt:
  // posに戻して、trの遷移を試みる
  // `Fork`の際に積まれる
  case Bt(pos: Int, tr: Trans)
  // キャプチャの状態を戻す
  // `CapBegin` の際に積まれる
  case UndoCap(cap_id: CapId, cap_state: CapState)
  // `call_stack`からpopする
  // `Call`の際に積まれる
  case PopCall
  // `call_stack`に`ret`を積み直す
  // `Return`で部分式の呼び出しを抜けた際に積まれる
  case PushCall(ret: BlockId)
  // 先読み・後読み用のマーカー
  case MarkLookAround
  case ProtectLookAround
  // `Absence` 用のマーカー
  case MarkAbsence
  // アトミックグループ用のマーカー
  case MarkAtomic
  case ProtectAtomic
  // `SaveCapGen` の逆の操作
  case RestoreCapGen(loop_id: LoopId, prev_gen: Int)

// 部分式の呼び出しのスタック
// `End` に到達するとき空になっているはず
enum Sub:
  case Call(ret: BlockId)
  case LookAround(pos: Int, positive: Boolean, dir: Dir, to: BlockId)
  case Absence(pos: Int, sub: BlockId, to: BlockId)

// キャプチャの状態
enum CapState:
  case None
  case Partial(begin: Int)
  case Set(begin: Int, end: Int)

メモ化の仕様や、メモ化のためのキー (posとHIR上のカウンタを考慮した位置) をどのように決めるか考えなければいけない。