Railsのルーティングを支える技術 - Journeyについて

Journeyは、Railsのルーティング処理を担当するライブラリです。Rails3で導入され、大規模なアプリケーションでの処理が高速化しました。

今回は、Journeyがどのようにしてルーティング処理を行っているかを紹介します。

TL;DR

• Railsのルーターは、ウェブから受け取ったURL(入力URL)を認識し、ルート定義と見比べマッチする処理が見つかればそれを呼び出す
• 入力URLに対応する処理を高速に探すためのライブラリがJourneyである
• Journeyはルート定義を非決定性有限オートマトン(NFA)に変換し、マッチングを行う
• Journeyは以下ステップを踏み、ルート定義をNFAに変換している
  1. ルート定義URLを字句解析し、トークンに分解する
  2. トークンから抽象構文木(AST)を構築する
  3. ASTからNFAに変換する
• Journeyは以下ステップを踏み、入力URLに対するマッチング処理を行っている
  1. 入力として与えられたURLを字句解析し、NFA入力形式に分解する
  2. 入力をもとにNFAのシミュレーションをする
  3. NFAが受理状態となった場合、対応する処理を呼び出す
• NFAでのマッチングを行うことで、高速なルーティングを実現している

Journeyを理解するために必要な基本知識

Journeyの内部実装を説明するまえに、まずは理解が必要な項目の解説を行います。

• Railsのルート定義について
• 有限オートマトンとはなにか

Railsのルート定義

Railsでは、以下文法でルーティングの定義を行います。

get "/articles(.:format)",          to: "articles#index"
get "/articles/new(.:format)",      to: "articles#new"
get "/articles/:id/edit(.:format)", to: "articles#edit"
get "/articles/:id(.:format)",      to: "articles#show"

これは例えばGETリクエストで /articles/12 が入力URLとして与えられた場合、処理articles#showを呼び出します。

:(コロン)で始まる項目はパラメーターで、URLで利用できる英数字記号ならなんでもよいです。
()で始まる部分は任意の項目です。例えば、/articles/12.json は id=12、 format=json と認識され、articles#show にマッチします。

入力URLが複数定義にマッチした場合は、先に定義した処理が呼び出されます。
例えば、入力URL/articles/new は articles#new と articles#show にマッチしますが、先に定義をしているnewが呼び出されます。

有限オートマトン

Journeyのルートマッチング処理を理解するためには、オートマトンについて理解をしておく必要があります。

オートマトンは、計算理論で使われるモデルのことです。
今回は有限オートマトンと呼ばれる領域に絞って説明します。有限オートマトンと聞くとなんだか複雑そうですが、いたってシンプルなモデルです。

有限オートマトンは現在の状態と、入力が与えられた時にどの状態へ遷移するかの規則をもっています。
初期状態から入力値に従って状態遷移し、次の状態に進みます。
すべての入力が終わり、最終的な状態が受理状態であったら、受理したという結果を返します。

以下は、シンプルなオートマトンを図にしたものです。

この有限オートマトンは、入力値は0,1いずれかを取ります。q0は初期状態で、q0,q1,q2は各種状態を表しています。二重丸q2は、受理状態を表しています。

このオートマトンに入力1を与えると、状態はq0からq1に遷移します。さらに入力1を与えると、状態はq1からq2に遷移します。その後入力がなければ、受理された状態となります。二重丸q2まで遷移しなかったものは、受理されず拒否状態となります。

上記オートマトンに以下の入力を与えた場合、受理状態となります。

11
011
000000011
110
111

以下入力では拒否となります。

000
001
0010
00100

有限オートマトンには、決定性と非決定性のものがあります。
上記のオートマトンは、入力に対して遷移先が一意に決まるため、決定性有限オートマトン(DFA; Deterministic Finite Automaton) と呼びます。

DFAに対し、入力に対して遷移先が一意に決まらないものは、非決定性有限オートマトン(NFA; Nondeterministic Finite Automaton) と呼びます。
例えば、以下はNFAの例です。

このオートマトンに入力1を与えると、状態はq1とq2に同時に遷移します。
NFAの場合、現在の状態を複数取ります。
さらに入力1を与えると、q1,q4へ遷移します。その後入力がなければ、q4は受理するので受理状態となります。

上記オートマトンに以下入力を与えた場合は、受理状態となります。

110      ---> q3
111      ---> q4
0101　　　---> q4
01000010 ---> q3

以下入力では拒否となります。

0000
0001

ここから先は完全に余談ですが、NFAとDFAは互いに同じモデルを表現できます(等価性)。そして任意のNFAはDFAに変換することができます。
NFAは遷移中の状態を複数持たないといけないので、遷移の処理効率が悪くなる可能性があります。
正規表現のエンジンは有限オートマトンを使ってマッチング処理をするものがありますが、それらエンジンではNFAはDFAに変換してから処理をすることがあります。
またDFAの場合、状態を最小化するアルゴリズムも存在します。
ただし、NFA/DFA変換も万能かといえばそうではなくて、DFAにすることで状態が膨大になってしまう可能性もあります。
このあたりの話は割愛します。興味がある方はぜひ調べてみてください。

Journeyのルートマッチング処理の流れ

Journeyのルートマッチング処理は非決定性オートマトン(NFA) を用いて行います。
例えば、以下ルート定義を考えます。

get "/articles/new(.:format)",      to: "articles#new"

このURLの定義を、以下6つのトークンに分解(字句解析)します。

/
articles
/
new
.
正規表現[^./?]+ (これは . または　/ または ? 以外の1文字以上の繰り返しを意味する。?-mix: はrubyの正規表現オプションなので一旦無視してください)

トークンに分解後、各種状態のノードとエッジとしNFAを作ります。図に表すと以下状態になります。
URLがマッチした場合(受理状態)は二重丸で表しています。

このNFAに対して、例えば以下入力を与えた場合は受理となります。
受理した場合は articles#newにマッチしたことになります。

/          (状態が0から1に遷移)
articles   (状態が1から2に遷移)
/          (状態が2から3に遷移)
new        (状態が3から4に遷移、入力はこれ以上ないので受理)

/          (状態が0から1に遷移)
articles   (状態が1から2に遷移)
/          (状態が2から3に遷移)
new        (状態が3から4に遷移)
.          (状態が4から5に遷移)
json       (状態が5から6に遷移、入力はこれ以上ないので受理)

もう少し複雑なルート定義を見てみます。
例えば以下のような定義があるとします。

get "/articles(.:format)",          to: "articles#index"
get "/articles/new(.:format)",      to: "articles#new"
get "/articles/:id/edit(.:format)", to: "articles#edit"
get "/articles/:id(.:format)",      to: "articles#show"

この定義をNFAで表すと以下となります。

このNFAに対し、以下入力を与えると、２つの受理状態となります。

/           (状態が0から1に遷移)
articles    (状態が1から2に遷移)
/           (状態が2から4に遷移)
new         (状態が4から6に遷移し受理 かつ 4から7に遷移し受理)

状態6で受理した場合はarticles#newを、状態7で受理した場合はarticles#show でマッチしたことを表します。
2つの受理状態となった場合は、先に定義したほうを勝ちとします。

JourneyのNFAシミュレーターが http://tenderlove.github.io/fsmjs/ にあります。
入力した文字列に対し、受理したかどうかをシミュレーションできます。このシミュレーターで色々な入力パターンを試すと理解が深まります。

Journeyの内部処理を覗く

JourneyがNFAを用いてマッチング処理を行っていることがわかりました。
次はJourneyが実際に行っている内部処理を覗いてみます。

Journeyは以下ステップを踏み、ルート定義をNFAに変換しています。

1. ルート定義URLを字句解析し、トークンに分解する
2. トークンから抽象構文木(AST)を構築する
3. ASTからNFAに変換する

また、マッチング処理をする際は、以下ステップを踏みます。

1. 入力として与えられたURLを字句解析し、NFA入力形式に分解する
2. 入力をもとにNFAのシミュレーションをする
3. NFAが受理状態となった場合、対応する処理を呼び出す

ルート定義URLを字句解析し、トークンに分解する

ルート定義 /articles/new(.:format) は、以下6つのトークンに分解(字句解析)します。

/
articles
/
new
.
正規表現[^./?]+ (これは . または　/ または ? 以外の1文字以上の繰り返しを意味する)

入力をトークンに分解するのは、スキャナが担当しています。
Journeyの場合、Scannerの定義は https://github.com/rails/rails/blob/v6.0.2/actionpack/lib/action_dispatch/journey/scanner.rb にあります。

これは単純で、入力に対して以下のようなトークンに分解します。

pry(main)> scanner = ActionDispatch::Journey::Scanner.new
=> #<ActionDispatch::Journey::Scanner:0x00007ff1ce901498 @ss=nil>

pry(main)> scanner.scan_setup("/articles/:id(.:format)")
=> #<StringScanner 0/23 @ "/arti...">

pry(main)> scanner.next_token
=> [:SLASH, "/"]

pry(main)> scanner.next_token
=> [:LITERAL, "articles"]

pry(main)> scanner.next_token
=> [:SLASH, "/"]

pry(main)> scanner.next_token
=> [:SYMBOL, ":id"]

pry(main)> scanner.next_token
=> [:LPAREN, "("]

pry(main)> scanner.next_token
=> [:DOT, "."]

pry(main)> scanner.next_token
=> [:SYMBOL, ":format"]

pry(main)> scanner.next_token
=> [:RPAREN, ")"]

pry(main)> scanner.next_token
nil

定義 /articles/:id(.:format) は、以下トークンとなりました。

[:SLASH, "/"]
[:LITERAL, "articles"]
[:SLASH, "/"]
[:SYMBOL, ":id"]
[:LPAREN, "("]
[:DOT, "."]
[:SYMBOL, ":format"]
[:RPAREN, ")"]

トークンから抽象構文木(AST)を構築する

NFAって、よく見ると木構造みたいなものですよね。
次はNFAに変換する前処理として、トークンを一度木構造に変換します。
この処理はパーサーが担当します。

パーサーの定義は https://github.com/rails/rails/blob/v6.0.2/actionpack/lib/action_dispatch/journey/parser.y にあります。
このパーサーは、与えられたルート定義をスキャナーを使いトークンに分解後、ASTを組み立てます。
このパーサーはRacc(yaccのruby版)を使って作られています。

Racc(yaccの定義)について、簡単に説明します。
例えば以下定義があるとします。

expressions : expression expressions  | expression;
expression  : terminal;
terminal    : symbol | dot;
symbol      : SYMBOL;
dot         : DOT;

Raccは:で区切った右辺と左辺でみます。例えば、expressionsは expression expressions または expression で構成されるという定義です。
expressionは、さらにterminal であると定義されます。
terminalは symbol または dot でできていて、symbolはSYMBOL、dotはDOTであると定義されます。大文字で表した定義が終端となります。

Raccはさらに、処理にマッチしたときのアクションを定義できます。右辺の一番右にブロックを書くことでアクションを定義できます。
例えば、以下定義でDOTという定義をすると、DOTにマッチしたらDotのインスタンスにする(マッチした定義はvalで取れる)ということが可能です。

dot         : DOT       { Dot.new(val[0]) }

JourneyのRacc定義を見てみましょう。以下のようになっています。

  expressions
    : expression expressions  { Cat.new(val.first, val.last) }
    | expression              { val.first }
    | or
    ;
  expression
    : terminal
    | group
    | star
    ;
  group
    : LPAREN expressions RPAREN { Group.new(val[1]) }
    ;
  or
    : expression OR expression { Or.new([val.first, val.last]) }
    | expression OR or { Or.new([val.first, val.last]) }
    ;
  star
    : STAR       { Star.new(Symbol.new(val.last)) }
    ;
  terminal
    : symbol
    | literal
    | slash
    | dot
    ;
  slash
    : SLASH              { Slash.new(val.first) }
    ;
  symbol
    : SYMBOL             { Symbol.new(val.first) }
    ;
  literal
    : LITERAL            { Literal.new(val.first) }
    ;
  dot
    : DOT                { Dot.new(val.first) }
    ;

DOTノードがでてきたらDotインスタンスにする、SymbolインスタンスがでてきたらSymbolにする。
expressionsにヒットしたらCatノードにして、ヒットしたexpression(すなわちval[0])とexpressions(すなわちval[1])をCatノードの初期値として渡すといった意味になります。

このあたりのRaccの使い方について、詳しくは http://i.loveruby.net/ja/projects/racc/doc/usage.html を参照ください。

/articles/:id(.:format) という定義をパーサーに通してみます。パーサーは内部的にトークンに変換後、以下ASTを構築します。

pry(main)> parser = ActionDispatch::Journey::Parser.new
=> #<ActionDispatch::Journey::Parser:0x00007ff1c7f32698 @scanner=#<ActionDispatch::Journey::Scanner:0x00007ff1c7f32670 @ss=nil>>

pry(main)> parser.parse("/articles/:id(.:format)")

=> #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f0bbb0
 @left=#<ActionDispatch::Journey::Nodes::Slash:0x00007ff1c7f101d8 @left="/", @memo=nil>,
 @memo=nil,
 @right=
  #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f0bc00
   @left=#<ActionDispatch::Journey::Nodes::Literal:0x00007ff1c7f10138 @left="articles", @memo=nil>,
   @memo=nil,
   @right=
    #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f0bc50
     @left=#<ActionDispatch::Journey::Nodes::Slash:0x00007ff1c7f100c0 @left="/", @memo=nil>,
     @memo=nil,
     @right=
      #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f0bca0
       @left=#<ActionDispatch::Journey::Nodes::Symbol:0x00007ff1c7f10020 @left=":id", @memo=nil, @name="id", @regexp=/[^\.\/\?]+/>,
       @memo=nil,
       @right=
        #<ActionDispatch::Journey::Nodes::Group:0x00007ff1c7f0bd40
         @left=#<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f0bd90 @left=#<ActionDispatch::Journey::Nodes::Dot:0x00007ff1c7f0bef8 @left=".", @memo=nil>, @memo=nil, @right=#<ActionDispatch::Journey::Nodes::Symbol:0x00007ff1c7f0be58 @left=":format", @memo=nil, @name="format", @regexp=/[^\.\/\?]+/>>,
         @memo=nil>>>>>

これを図に表すと、以下となります。

ASTからNFAに変換する

最後にルート定義をASTに変換したものから、NFAの状態遷移表を作成します。
これは GTG::Builder( https://github.com/rails/rails/blob/6-0-stable/actionpack/lib/action_dispatch/journey/gtg/builder.rb )が処理を担当します。

pry(main)> ast = parser.parse("/articles/:id(.:format)")

=> #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7a42fc0
 @left=#<ActionDispatch::Journey::Nodes::Slash:0x00007ff1c9974a88 @left="/", @memo=nil>,
 @memo=nil,
 @right=
  #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7a43150
   @left=#<ActionDispatch::Journey::Nodes::Literal:0x00007ff1c7a43fb0 @left="articles", @memo=nil>,
   @memo=nil,
   @right=
    #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7a432b8
     @left=#<ActionDispatch::Journey::Nodes::Slash:0x00007ff1c7a43dd0 @left="/", @memo=nil>,
     @memo=nil,
     @right=
      #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7a43308
       @left=#<ActionDispatch::Journey::Nodes::Symbol:0x00007ff1c7a43a38 @left=":id", @memo=nil, @name="id", @regexp=/[^\.\/\?]+/>,
       @memo=nil,
       @right=
        #<ActionDispatch::Journey::Nodes::Group:0x00007ff1c7a43510
         @left=#<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7a43560 @left=#<ActionDispatch::Journey::Nodes::Dot:0x00007ff1c7a438a8 @left=".", @memo=nil>, @memo=nil, @right=#<ActionDispatch::Journey::Nodes::Symbol:0x00007ff1c7a436c8 @left=":format", @memo=nil, @name="format", @regexp=/[^\.\/\?]+/>>,
         @memo=nil>>>>>


ActionDispatch::Journey::GTG::Builder.new(ast).transition_table
=> #<ActionDispatch::Journey::GTG::TransitionTable:0x00007ff1c9d07cb8 
  @accepting={4=>true, 6=>true}, 
  @memos={4=>[nil], 6=>[nil]}, 
  @regexp_states={3=>{/[^\.\/\?]+/=>4}, 5=>{/[^\.\/\?]+/=>6}}, 
  @string_states={0=>{"/"=>1}, 1=>{"articles"=>2}, 2=>{"/"=>3}, 4=>{"."=>5}}
>

acceptingは受理状態を表しています。この場合、状態4または6に到達すれば受け入れとなります。

@accepting={4=>true, 6=>true}, 

状態遷移はstring_statesとregexp_statesで表しています。
例えば、 {0=>{"/"=>1} は 状態0から入力/が来たら1に遷移せよ、ということを表しています。
memosは受理した場合の処理を入れておく変数です。とりあえず今は何も使わないのでnilのままにしておきます。

これでNFAが完成しました。図に表すと以下となります。

ルートの定義が複数ある場合はどうしたらよいでしょうか。これは、作成したASTをORノードの子とすることで表現できます。

pry(main)> ast_1 = parser.parse("/articles/:id(.:format)")
=>  省略

pry(main)> ast_2 = parser.parse("/articles/new(.:format)")
=>  省略

pry(main)> root = ActionDispatch::Journey::Nodes::Or.new([ast_1, ast_2])
=>  省略

pry(main)> ActionDispatch::Journey::GTG::Builder.new(root).transition_table
=> #<ActionDispatch::Journey::GTG::TransitionTable:0x00007ff1c8f4e4f0 

@accepting={4=>true, 5=>true, 8=>true, 9=>true}, 
@memos={4=>[nil], 5=>[nil], 8=>[nil], 9=>[nil]}, 
@regexp_states={3=>{/[^\.\/\?]+/=>4}, 6=>{/[^\.\/\?]+/=>8}, 7=>{/[^\.\/\?]+/=>9}}, 
@string_states={0=>{"/"=>1}, 1=>{"articles"=>2}, 2=>{"/"=>3}, 3=>{"new"=>5}, 4=>{"."=>6}, 5=>{"."=>7}}
>

上記NFAは図に表すと以下となります。

NFAシミュレーション - 入力URLにマッチする処理を求める

NFAが作れました。あとは入力URLをもとにNFAのシミュレーションをして、受理状態になったら対応する処理を呼び出すと、ルートのマッチング処理は完了です。

シミュレーションの処理は https://github.com/rails/rails/blob/6-0-stable/actionpack/lib/action_dispatch/journey/nfa/simulator.rb#L23 となります。
これは以下ステップを踏み、ルート定義に対応する処理を見つけます。

1. 入力として与えられたURLを字句解析し、NFA入力形式に分解する
2. 入力をもとにNFAのシミュレーションをする
3. NFAが受理状態となった場合、対応する処理を呼び出す

NFA::Simulatorは、先程作成した状態遷移表(TransitionTable)を使い、シミュレーションを行います。

pry(main)> parser = ActionDispatch::Journey::Parser.new

=> #<ActionDispatch::Journey::Parser:0x00007ff1c7fa3578 @scanner=#<ActionDispatch::Journey::Scanner:0x00007ff1c7fa3550 @ss=nil>>

pry(main)> ast_1 = parser.parse("/articles/:id(.:format)")

=> #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f78418
 @left=#<ActionDispatch::Journey::Nodes::Slash:0x00007ff1c7f78a08 @left="/", @memo=nil>,
 @memo=nil,
 @right=
  #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f78468
   @left=#<ActionDispatch::Journey::Nodes::Literal:0x00007ff1c7f78968 @left="articles", @memo=nil>,
   @memo=nil,
   @right=
    #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f784b8
     @left=#<ActionDispatch::Journey::Nodes::Slash:0x00007ff1c7f788f0 @left="/", @memo=nil>,
     @memo=nil,
     @right=
      #<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f78508
       @left=#<ActionDispatch::Journey::Nodes::Symbol:0x00007ff1c7f78850 @left=":id", @memo=nil, @name="id", @regexp=/[^\.\/\?]+/>,
       @memo=nil,
       @right=
        #<ActionDispatch::Journey::Nodes::Group:0x00007ff1c7f785a8
         @left=#<ActionDispatch::Journey::Nodes::Cat:0x00007ff1c7f785f8 @left=#<ActionDispatch::Journey::Nodes::Dot:0x00007ff1c7f78760 @left=".", @memo=nil>, @memo=nil, @right=#<ActionDispatch::Journey::Nodes::Symbol:0x00007ff1c7f786c0 @left=":format", @memo=nil, @name="format", @regexp=/[^\.\/\?]+/>>,
         @memo=nil>>>>>

pry(main)> table = ActionDispatch::Journey::GTG::Builder.new(ast_1).transition_table

=> #<ActionDispatch::Journey::GTG::TransitionTable:0x00007ff1c7f42ed0 
@accepting={4=>true, 6=>true}, 
@memos={4=>[nil], 6=>[nil]}, 
@regexp_states={3=>{/[^\.\/\?]+/=>4}, 5=>{/[^\.\/\?]+/=>6}}, 
@string_states={0=>{"/"=>1}, 1=>{"articles"=>2}, 2=>{"/"=>3}, 4=>{"."=>5}}
>

pry(main)> table.memos[4] = "State4 Match"
=> "State4 Match"
# これはstate4で受け入れた場合のロジックをいれます。

pry(main)> table.memos[6] = "State6 Match"
=> "State6 Match"
# これはstate6で受け入れた場合のロジックをいれます。

[35] pry(main)> simulator = ActionDispatch::Journey::NFA::Simulator.new(table)

=> #<ActionDispatch::Journey::NFA::Simulator:0x00007ff1c8593848 @tt=#<ActionDispatch::Journey::GTG::TransitionTable:0x00007ff1c7f42ed0 @accepting={4=>true, 6=>true}, @memos={4=>"State4 Match", 6=>"State6 Match"}, @regexp_states={3=>{/[^\.\/\?]+/=>4}, 5=>{/[^\.\/\?]+/=>6}}, @string_states={0=>{"/"=>1}, 1=>{"articles"=>2}, 2=>{"/"=>3}, 4=>{"."=>5}}>>

[36] pry(main)> simulator.simulate("/articles/3")
=> #<ActionDispatch::Journey::NFA::MatchData:0x00007ff1c8edb7e8 @memos=["State4 Match"]>

[37] pry(main)> simulator.simulate("/articles/3.json")
=> #<ActionDispatch::Journey::NFA::MatchData:0x00007ff1c8eafe68 @memos=["State6 Match"]>

[38] pry(main)> simulator.simulate("/articles/3/hello")
=> nil

/articles/:id(.:format) の定義に対し、 入力 /articles/3や/articles/3.json がマッチしていることがわかります。

おわりに

今回Journeyの内部実装を見てみました。一見難しそうに見えますが、NFAについて理解できれば何てことはないです。

私は学生時代、オートマトンの授業はあまり得意ではありませんでした。
今回Journeyの調査にあたり各種テキストを見ていたのですが、そういえばこんなこと勉強したなぁ...くらいでおぼろげな記憶しかありませんでした。
まさかRailsの内部でNFAにお目にかかるとは。CSの基礎知識は大事なんだなあと改めて感じた次第です。