概要

筆者の個人的なプロジェクトとして作っているFortranで書かれた正規表現エンジン、Fortran Regular Expression - Forgexのバージョン3.4をリリースしました。

以前に『Fortranで正規表現』という記事を投稿しましたが、そこから改良を重ねてきました。最近のバージョンアップで機能の追加や内部実装の大幅な変更を行ったので、今回はそれについて書きたいと思います。なお、このライブラリの使い方の詳細についてはドキュメンテーション（日本語版）やリポジトリのREADMEを参照してください。

2024-09-02 追記 バージョン3.5をリリースしました。

Forgex バージョン3

Forgexについて

Forgexは、ほぼ完全にFortran記述された正規表現エンジンです。決定性有限オートマトン（DFA）を用いたエンジンで、正規表現マッチングの基本的な機能を提供します。このプロジェクトはMITライセンスの下で利用可能なフリーソフトウェアです。最近、バージョンを3.4に更新しました。

エンジンの実装

DFAを使用するForgexの正規表現エンジンは、バージョン1.4までは事前に非決定性有限オートマトン（NFA）から完全にコンパイルされたDFAを使用していました。その後のバージョン2.0より、遅延評価によって入力文字列に応じた遷移を動的に生成するLazy DFAを採用しています。この方法によって、状態数が非常に大きくなってしまう正規表現パターンについて、実用的な時間とメモリ消費でマッチングを行うことができるようになりました。

また、バージョン2.0までは抽象構文木（AST）とNFA、DFAのグラフをポインタを使って実装していましたが、バージョン3.0以降では、これらを派生型の配列として実装しています。Fortranでは配列の機能が豊富で高速なので、この実装方法はマッチング処理の高速化に大きく寄与していると思われます。

以下にDFAの状態ノードと遷移、オートマトンを表現するグラフの派生型の定義を例に示します。

  type, public :: dfa_transition_t
      type(segment_t)       :: c
      type(nfa_state_set_t) :: nfa_set
      integer(int32)        :: own_j = DFA_NOT_INIT ! Own index in the list of transitions
      integer(int32)        :: dst   = DFA_NOT_INIT ! The destination node index of DFA graph.
   end type dfa_transition_t


   type, public :: dfa_state_node_t
      integer(int32)                      :: own_i = DFA_NOT_INIT
      type(nfa_state_set_t)               :: nfa_set
      logical                             :: accepted = .false.
      type(dfa_transition_t), allocatable :: transition(:)
      integer(int32), private             :: tra_top = DFA_NOT_INIT_TRAENSITION_TOP
      integer(int32)                      :: alloc_count_f = ALLOC_COUNT_INITTIAL
      logical                             :: registered = .false.
      logical                             :: initialized = .false.
   contains
      procedure :: get_tra_top       => dfa_state_node__get_transition_top
      procedure :: init_tra_top      => dfa_state_node__initialize_transition_top
      procedure :: increment_tra_top => dfa_state_node__increment_transition_top
      procedure :: add_transition    => dfa_state_node__add_transition
      procedure :: realloc_f         => dfa_state_node__reallocate_transition_forward
      procedure :: is_registered_tra => dfa_state_node__is_registered_transition
      procedure :: free              => dfa_state_node__deallocate
   end type dfa_state_node_t

   type, public :: dfa_graph_t
      !! This type has the entire graph of DFA states.
      type(dfa_state_node_t), allocatable :: nodes(:)
      integer(int32) :: dfa_base  = DFA_STATE_BASE
      integer(int32) :: dfa_limit = DFA_STATE_UNIT
      integer(int32) :: dfa_top   = DFA_INVALID_INDEX
      integer(int32) :: alloc_count_node = 0
   contains
      procedure :: preprocess     => lazy_dfa__preprocess
      procedure :: registered     => lazy_dfa__registered_index
      procedure :: add_transition => lazy_dfa__add_transition
      procedure :: free           => lazy_dfa__deallocate
      procedure :: reallocate     => lazy_dfa__reallocate
   end type dfa_graph_t

この例ではDFAの各ノードと遷移の情報を含む派生型（dfa_state_node_tとdfa_transition_t）を定義し、さらにそれらを配列として保持するグラフを表現する派生型（dfa_graph_t）を定義しています。ノードとエッジを表す派生型を作り、その配列を成分として持つ派生型を作ってグラフを表現する手法は、配列で木構造などを扱う際の一つの良い方法かもしれません（ただしコードの量が多くなります）。

以前のポインタによる実装では、ポインタ属性を持つ変数に対して必要になったらその都度、記憶領域を割付けてグラフを構築していました。この方法では、割付回数と参照が多いためかパフォーマンスが低く、さらにメモリ管理を厳密に行う必要があります。一方で、割付可能配列（allocatableな配列）を用いたグラフの実装では、配列の添字情報によって構文木のノードやオートマトンの遷移先を管理することになるので処理が軽くなります。また、割付解除もスコープを抜けたら自動的に処理系がdeallocateしてくれるのでとても使いやすいです。（この方法の欠点を挙げるならば、グラフのノード数が配列の上限を超える際に再割付けを行うと、オブジェクトのディープコピーをする必要があるので、大きなグラフの場合に遅延が発生することでしょうか。）

また、次のセクションで述べるpure属性について、APIを構成するすべての手続にこれを付与するためには、モジュール変数やポインタを自由に使えないという制約があります。これについては、派生型と型束縛手続を使うことで関数やサブルーチンを少ない引数で呼び出せるという点も効果的でした。

機能の追加

このセクションでは、バージョン2から3へ更新する際に追加された機能について述べます。

`pure elemantal` 属性

Forgexが提供する演算子.in.と.match.は、pure属性と elemental属性を持つようになりました。これらの属性は配列の取り扱いや並列処理において効果を発揮するものです。

pureな関数について簡単に述べると、副作用（仮引数がintent(inout)やintent(out)なもの、外部の変数への代入やファイル・端末への入出力など）が無く、同じ実引数なら同じ結果を返す関数です。実際的には、この属性を持つ関数はスレッドセーフが保証され、do concurrent構文内で使えるようになります。一方で、elemental属性を持つ関数は、スカラーな仮引数とスカラーな戻り値を持つ関数として定義されますが、実引数として配列を使用して呼び出すことができます。この場合には関数は配列の要素ごとに適用されて、戻り値として配列が返されます。

以下に.in.演算子の宣言部を例に示します。

interface operator(.in.)
   module procedure :: operator__in
end interface
   
pure elemental function operator__in(pattern, str) result(res)
   implicit none
   character(*), intent(in)       :: pattern, str
   logical                        :: res
...

ここではスカラーの仮引数と戻り値が定義されていて、関数宣言の先頭にpure elementalが追加されています。このelemental属性を持つ演算子は、次のようなコードで配列のためのdoループを書くことなく実行可能です。

block
   integer, parameter :: siz = 5
   character(:), allocatable :: pattern
   character(8) :: text_array(siz)
   logical :: result_array(siz)
   
   pattern = "(^a)|(.*a\s*$)"
      ! This pattern matches character a at the beginning or the trailing.

   text_array = ["alpha   ", "bravo   ", "charlie ", "delta   ", "echo    "]
   
   result_array(1:siz) = pattern .in. text_array(1:siz)
      ! Applying an operator to an array returns an array.
   
   print *, result_array    ! T F F T F
end block

つまり、elemantalな関数を使うと配列に対する演算を簡潔に記述でき、pureな関数を使うと並列処理に向いたコードを書くことができます。バージョン3.4現在、ForgexのAPI演算子.in.と.match.はpure elemental属性を持ち、サブルーチンregexと関数regex_fはpure属性を持っています。

固定文字列検索による最適化

正規表現パターンからリテラル（固定文字列）を取り出せる場合には、それを入力テキスト上で検索することで、マッチングを高速化できる可能性があります。例えばcdefghabcdeというテキストにパターンab[^x]dが含まれるかどうかを判定したいとします。このパターンはテキストの7文字目から10文字目のabcdにマッチします。以前のナイーブな実装では、1文字目からマッチを試みて失敗したら2文字目からというように繰り返すアルゴリズムでした。この方法は、先頭からマッチが成功するか全て入力を消費するまで、たとえ不要な比較でも何度も行うという点で力任せ（非効率）な方法でした。

現在の実装では、リテラル検索（固定文字列検索）最適化の手法が導入されました。この方法では、最初にパターンから接頭辞と接尾辞のリテラルを抽出します。上の例では接頭辞abと接尾辞dが抽出されます。次にこれらのリテラルを、正規表現エンジンよりも数桁高速なindex組込み関数を使って検索し、文字列の開始位置を取得します。検索された位置（この例は添字7）からエンジンを動かすことで、不要な処理をスキップして処理時間を短縮できます。添字を取得できなかった場合、そのパターンがテキストとマッチすることは無いので偽の結果をすぐに返す事ができます。

この手法は、接頭辞または接尾辞リテラルが存在して入力テキストが長い場合に効果的です。今のバージョンでは、中間リテラル（パターンの先頭や末尾でない場所にあるリテラル、例えばパターン.*abc.*のabcなど）による最適化は実装されていません。ASTから中間リテラルを抽出するアルゴリズムの構築が難しく、現在試行錯誤しているところです。

コマンドラインツール

バージョン3の開発で必要となったので、forgex-cliというコマンドラインツールを作成し、導入しました。このアプリケーションは、ForgexのAPIや内部モジュールを使用して、正規表現マッチングのテストとパフォーマンスの計測を行うことができます。

2024-09-02 追記 バージョン3.5以降、forgex-cliは新しい別のリポジトリShinobuAmasaki/forgex-cliで提供されるようになりました。以下のコマンドを実行するにはこのリポジトリのコードをビルドしてインストールする必要があります。

次のようなコマンドでマッチングを行い、結果を標準出力に得ることができます。

forgex-cli find match lazy-dfa '([a-z]*g+)n?' .match. 'assign'

fpm runから実行する場合には、次のようにします。

fpm run --profile release -- find match lazy-dfa '([a-z]*g+)n?' .match. 'assign'

得られる結果は次のようなものです。

             pattern: ([a-z]*g+)n?
                text: 'assign'
          parse time:        31.0μs
extract literal time:         9.0μs
         runs engine:         T
    compile nfa time:        33.0μs
 dfa initialize time:         8.0μs
         search time:       343.0μs
     matching result:         T
  memory (estimated):     10324

========== Thompson NFA ===========
state    1: (?, 5)
state    2: <Accepted>
state    3: (n, 2)(?, 2)
state    4: (g, 7)
state    5: (["a"-"f"], 6)(g, 6)(["h"-"m"], 6)(n, 6)(["o"-"z"], 6)(?, 4)
state    6: (?, 5)
state    7: (?, 8)
state    8: (g, 9)(?, 3)
state    9: (?, 8)
=============== DFA ===============
   1 : ["a"-"f"]=>2
   2 : ["o"-"z"]=>2 ["h"-"m"]=>2 g=>3
   3A: n=>4
   4A:
state    1  = ( 1 4 5 )
state    2  = ( 4 5 6 )
state    3A = ( 2 3 4 5 6 7 8 )
state    4A = ( 2 4 5 6 )
===================================

出力にはパターンと入力テキスト、実行時間などの情報を示す表と、パターンから構築されたNFAとDFAの遷移テーブルが含まれます。このコマンドではLazy DFAの他に、完全に事前コンパイルされたDFA（dense DFA）の結果も出力することが可能です。このコマンドの使い方の詳細についてはドキュメンテーションを参照してください。

なお、Windows環境でUnicode文字を端末に正しく出力させる場合には、PowerShellの文字エンコーディングをUTF-8にするか、システムのロケールをUTF-8にする必要があります。

今後やりたいこと

将来的には以下の機能を実装したいと考えています。

Unicodeプロパティへの対応
UTF-8において有効でない文字の処理
中間リテラル検索による最適化

おわりに

このプロジェクトは、筆者の夏のホームワークとしてバージョンアップされました。リテラル検索最適化を実装して一息ついたので、本稿を執筆することにしました。

Fortranで使える正規表現ライブラリをシンプルなAPIで提供したいと思い開発を進めてきましたが、途中では高速化のために内部処理を並列化することも検討しました。しかし結果として、ユーザーが並列処理を書くときに扱いやすいツールを提供したいと考え、pure属性を持つAPIを実装することに決めました。その成果が現在のバージョン3.4としてリリースされています。

ところでバージョン2をリリースしたときは全てのコードを合わせて3000行程度だったのですが、現在では9000行ほどまでになり、今後ドキュメントのためのコメントを追加すると1万行を超えそうです（本当はもっとシェイプアップして機能を実現したかったのですが）。Fortranの個人開発でこの規模のソフトウェアを書いたことはなかったので、良い経験だったかもしれません。

最後まで読んでいただきありがとうございました。

謝辞

forgex-cliのコマンドラインインターフェイスのデザインは、Rust言語のregex-cliを参考にしています。

参照

"Modern Fortran Explained—Incorporating Fortran 2018", M. Metcalf, J. Reid, M. Cohen, Oxford University Press, 2018, pp.126-129
"正規表現技術入門—最新エンジン実装と理論的背景", 新屋良磨, 鈴木勇介, 高田謙, 技術評論社, 2015, pp.218-226
rust-lang/regex/regex-cli