私は如何にしてPadrino::Routing及びhttp_routerのバグを直したか

タイトルは大げさですみません。

Padrino Contributorの先輩である@tyabeさんから解説の要請をいただいたので、うろ覚えですが解説していきます。

ちなみに問題のissueはbroken parameter assignment in routing (11.2)になります。

まずは挙動確認

nesquenaさんやsshawさんがこれもおかしいよ情報を書き込んでいてくれたので、そのテストコードを参考におかしくなる挙動を見つけていきます。

その結果、以下のことがわかります。

:withオプションに限らず、キャプチャに正規表現を使った際の挙動がおかしい。
レスポンスのステータスコードが405になっている(許可されていないメソッド)。

この二つを軸にして、実際のコードを読んでいきます。

padrino-core/application/routing.rb

基本的にPadrinoでは、routeメソッドでrouteを追加したりオプションやキャプチャをごにょごにょしているので、まずはそこを見ていきます。

この辺はプリントデバッグをした記憶がありますがあまり覚えてないです、すみません。

キャプチャ用のオプションなどはrouteメソッド内の以下の部分が肝のようでした。

          options.delete_if do |option, args|
            if route.significant_variable_names.include?(option)
              route.add_match_with(option => Array(args).first)
              true
            end
          end

ここでrouteに対してadd_match_withでオプションを渡しているようです。

routeはHttp::Routeのインスタンスなので、routing.rbはこのくらいにして次に進みます。

そしてhttp_routerへ…

まずはroute.add_match_withの動作を追います。

http_router.rbを探してもadd_match_withなんでメソッドはないので得意のヘルパーだろうなと思い、route_helper.rbを探すと案の定ありました。

    def add_match_with(matchers)
      @match_with ||= {}
      @match_with.merge!(matchers)
    end

このコード自体には何の問題も無く、やっぱりマッチングがおかしいんだよね〜ということで、match_withをコード内から探していくとmatches_withというメソッドがroute.rbで見つかります。

今度はmatches_withを検索すると明らかにそれっぽくて読み難いコードがroot.rbで見つかります(add_route, add_normal_partの辺りです)。

ここからはしばらく、渡されたキャプチャがどういう順序を辿って行くのか調べていました(プリントデバッグなので省略します)。

結果、node.add_spanning_match(route.matches_with(name))に渡っていることがわかります。

add_spanning_matchは/lib/http_router/node.rbにあるようで、以下のコードになります。

    def add_spanning_match(regexp, matching_indicies = [0], splitting_indicies = nil)
      add(SpanningRegex.new(@router, self, regexp, matching_indicies, splitting_indicies))
    end

ついに黒幕が正体を現しました。SpanningRegex、こいつです。

lib/http_router/node/spanning_regex.rbへ

ここまで辿り着けば簡単な気もしますが(params_countのコードが明らかにおかしいので)、おかしい部分には全く気づかずにちらっと見て諦めました。

読むことができないので、http_routerが内部で生成してくれたありがたいソースコードをprintしてどのように遷移していくのか見て行くことにしました。

以下のようなコードをpadrino-core/application/routing.rbに書きます(実はデバッグ時のコードは消しちゃって残ってないので再現になります…)。

  class Node::Root
    def compile(routes)
      routes.each {|route| add_route(route)}
      root.extend(root.methods_module)
      _code = to_code
      puts _code
      instance_eval "def call(request, &callback)\n#{_code}\nnil\nend"
      @compiled = true
    end
  end

余談ですが、http_routerではrouteを追加するごとに、to_codeで生成されるコードが増えていきます。地獄です。

to_codeで生成されるコードを読む

適当に作ったpadrino-appのapp/app.rbを以下のようにして、padrino sでデバッグ開始です(mock_appとか使ってテストした方が早かったと今になって思う)。

module Sandbox
  class App < Padrino::Application
    register Padrino::Rendering
    register Padrino::Helpers

    post :index, :with => [:foo, :bar], :bar => /.+/ do
      params.to_s
    end

    get :index, :map => '/mystuff/:a_id/boing/:boing_id' do
      params.to_s
    end
  end
end

適当に/などにアクセスすると以下のような出力が得られます(実際の出力は見難かったので少し整形しています)。

# HttpRouter::Node::Variable
unless request.path_finished?
  request.params << request.path.shift
  # HttpRouter::Node::SpanningRegex
  whole_path1 = request.joined_path
  if match = /.+/.match(whole_path1) and match.begin(0).zero?
    _whole_path1 = request.path.dup
    request.params << match[0]

    remaining_path = whole_path1[match[0].size + (whole_path1[match[0].size] == ?/ ? 1 : 0), whole_path1.size]
    request.path = remaining_path.split('/')
    # HttpRouter::Node::RequestMethod
    if "POST" === request.rack_request.request_method
      if "POST" === request.rack_request.request_method
        # HttpRouter::Node::Path
        if request.path_finished?
          catch(:pass) do
            if callback
              request.called = true
              callback.call(Response.new(request, @ivar_2))
            else
              env = request.rack_request.dup.env
              env['router.request'] = request
              env['router.params'] ||= {}
              env['router.params'].merge!(Hash[[:foo, :bar].zip(request.params)])
              @router.rewrite_path_info(env, request)
              response = @router.process_destination_path(@ivar_2, env)
              return response unless router.pass_on_response(response)
            end
          end
        end
      end
    end
    request.acceptable_methods.merge(["POST"])

    request.path = _whole_path1
    request.params.slice!(-8, 1)
  end

  request.path.unshift request.params.pop
end

# HttpRouter::Node::Lookup
unless request.path_finished?
  part3 = request.path.shift
  case part3
  when "mystuff"
    unless request.path_finished?
      request.params << request.path.shift
      # HttpRouter::Node::Lookup
      unless request.path_finished?
        part4 = request.path.shift
        case part4
        when "boing"
          unless request.path_finished?
            request.params << request.path.shift
            # HttpRouter::Node::RequestMethod
            if "GET" === request.rack_request.request_method
              if "GET" === request.rack_request.request_method
              # HttpRouter::Node::Path
                if request.path_finished?
                  catch(:pass) do
                    if callback
                      request.called = true
                      callback.call(Response.new(request, @ivar_5))
                    else
                      env = request.rack_request.dup.env
                      env['router.request'] = request
                      env['router.params'] ||= {}
                      env['router.params'].merge!(Hash[[:a_id, :boing_id].zip(request.params)])
                      @router.rewrite_path_info(env, request)
                      response = @router.process_destination_path(@ivar_5, env)
                      return response unless router.pass_on_response(response)
                    end
                  end
                end
              end
            end

            request.acceptable_methods.merge(["GET"])

            # HttpRouter::Node::RequestMethod
            if "HEAD" === request.rack_request.request_method
              if "HEAD" === request.rack_request.request_method
              # HttpRouter::Node::Path

                if request.path_finished?
                  catch(:pass) do
                    if callback
                      request.called = true
                      callback.call(Response.new(request, @ivar_6))
                    else
                      env = request.rack_request.dup.env
                      env['router.request'] = request
                      env['router.params'] ||= {}
                      env['router.params'].merge!(Hash[[:a_id, :boing_id].zip(request.params)])
                      @router.rewrite_path_info(env, request)
                      response = @router.process_destination_path(@ivar_6, env)
                      return response unless router.pass_on_response(response)
                    end
                  end
                end
              end
            end
            request.acceptable_methods.merge(["HEAD"])

            request.path.unshift request.params.pop
          end;
        end
        request.path.unshift part4
      end

      request.path.unshift request.params.pop
    end;
  end
  request.path.unshift part3
end

# HttpRouter::Node::Glob
request.params << (globbed_params7 = [])
until request.path.empty?
  globbed_params7 << request.path.shift
  # HttpRouter::Node::Regex
  if match = /([^\/]*?)\.png$/.match(request.path.first) and match.begin(0).zero?
    part = request.path.shift
    request.params << match[1]
    # HttpRouter::Node::RequestMethod
    if "GET" === request.rack_request.request_method
      if "GET" === request.rack_request.request_method
        # HttpRouter::Node::Path
        if request.path_finished?
          catch(:pass) do
            if callback
              request.called = true
              callback.call(Response.new(request, @ivar_8))
            else
              env = request.rack_request.dup.env
              env['router.request'] = request
              env['router.params'] ||= {}
              env['router.params'].merge!(Hash[[:__sinatra__, :image].zip(request.params)])
              @router.rewrite_path_info(env, request)
              response = @router.process_destination_path(@ivar_8, env)
              return response unless router.pass_on_response(response)
            end
          end
        end
      end
    end
    request.acceptable_methods.merge(["GET"])
    # HttpRouter::Node::RequestMethod
    if "HEAD" === request.rack_request.request_method
      if "HEAD" === request.rack_request.request_method
        # HttpRouter::Node::Path

        if request.path_finished?
          catch(:pass) do
            if callback
              request.called = true
              callback.call(Response.new(request, @ivar_9))
            else
              env = request.rack_request.dup.env
              env['router.request'] = request
              env['router.params'] ||= {}
              env['router.params'].merge!(Hash[[:__sinatra__, :image].zip(request.params)])
              @router.rewrite_path_info(env, request)
              response = @router.process_destination_path(@ivar_9, env)
              return response unless router.pass_on_response(response)
            end
          end
        end
      end
    end
    request.acceptable_methods.merge(["HEAD"])

    request.path.unshift part
    request.params.pop
  end
end
request.path[0,0] = globbed_params7

凄まじいですね！

これをcallメソッドとしてinstance_evalで定義して、リクエスト毎に毎回このコードが実行されていることになります。

このコードを読む前提として、以下のものを挙げておきます。

requestはHttpRouter::Request。Rack::Requestをごにょごにょするクラスです。
request.pathは原則的に、パスを/でsplitした配列を返します。
request.joined_pathはrequest.pathを/でjoinした結果である文字列を返します。
request.paramsは後に、ブロック内で参照できるparamsの元となるものです。詳しくは上のコードとあわせてpadrino-core/application/routing.rbにあるprocess_destination_pathメソッド付近を読むとわかります。
request.rack_request.request_methodは動作に問題なく、/mystuff/5/boing/2にGETでリクエストを飛ばすとGETが格納されています。
生成されるコードでは、条件に入る前にrequest.paramsを追加し、条件に当てはまらなかった場合にはrequest.pathやrequest.paramsの値を操作して、帳尻を合わせています。
match = /.+/.match(whole_path1)の部分は不適切だと思われますが、今回の問題の本質ではないので飛ばします(新たなバグの原因なのでそのうち時間があれば直そうと思っています)。

今回問題なのは、/mystuff/5/boing/2にリクエストを飛ばしたときに405を返すというところで、本来であれば46行目のcase part3から始まる部分にマッチすべきリクエストのはずです。

part3の中身がおかしいことは明らかなので、以下のモンキーパッチをrouting.rbに書いて、中身を調べます。

  class Node::Lookup
    def to_code
      part_name = "part#{root.next_counter}"
      "unless request.path_finished?
        #{part_name} = request.path.shift
        p '#{part_name} is ' + #{part_name} # この部分を追加
        case #{part_name}
        #{@map.map{|k, v| "when #{k.inspect}; #{v.map(&:to_code) * "\n"};"} * "\n"}
        end
        request.path.unshift #{part_name}
      end"
    end
  end

すると中身が判明し、"part3 is 5/boing/2"と出ます(本当は中身がおかしいにしても5が出力されるべきなんですが、前述した不適切だと思われる部分のせいでこうなっています)。

ここまで来ると、前提として挙げた帳尻合わせが上手くいっていないことがわかるので、その部分を重点的に見ていきます。

もう気づいている人も多いかと思いますが、生成されたコードの37行目にrequest.params.slice!(-8, 1)とあります。

ここで本来削除されるべきparamを削除できていないんだろうと思い、実際にこの部分を生成しているSpanningRegexを再度調べます。

以下のコードです。

class HttpRouter
  class Node
    class SpanningRegex < Regex
      def to_code
        params_count = @ordered_indicies.size
        whole_path_var = "whole_path#{root.next_counter}"
        "#{whole_path_var} = request.joined_path
        if match = #{@matcher.inspect}.match(#{whole_path_var}) and match.begin(0).zero?
          _#{whole_path_var} = request.path.dup
          " << param_capturing_code << "
          remaining_path = #{whole_path_var}[match[0].size + (#{whole_path_var}[match[0].size] == ?/ ? 1 : 0), #{whole_path_var}.size]
          request.path = remaining_path.split('/')
          #{node_to_code}
          request.path = _#{whole_path_var}
          request.params.slice!(#{-params_count.size}, #{params_count})
       end
       "
      end
    end
  end
end

params_count.sizeは明らかにおかしい(Fixnum#sizeをこの場面で使うことはないだろうと思った)ので、.size部分を消したものをモンキーパッチとして、routing.rbに追加してやるとしっかり帳尻が合い、

issueで取り上げられていたテストも無事動きました。

後は、今回の変更で以前まで動いていたコードが動かなくなっていないかをテストして、pull reqを飛ばしました。

以上が、今回の大まかな顛末となります。

実際にはこれに辿り着いた後も、明らかにおかしい部分(前述)もまとめて上手く直す方法ないかな〜と模索していましたが途中で嫌になったのでやめてしまいました。

総括

priorityを直したときにhttp_routerのコードをある程度読んでいたのでそれが良かったと思います。
priorityを直したときと違って、明らかに今回は開発者の人が動かそうとしているのがわかったので、少ない変更で解決できて安心しています。
コード生成部分、ヤバいと思うと同時にすごいなーとも思いました。かなり勉強になりました。
そもそも、SpanningRegexに辿り着いた時点で気づくべきミス(少なくとも違和感を感じるべき)だったのでまだまだ実力が足りないなと実感しました。

最後になりますが、Padrinoは現在http_routerに依存していますが、今後のアップデートで(多分1.0かな？)http_routerを削除して、新たにroutingを書き換える予定になっています。

http_routerは確かにアレですが、Padrinoのことは嫌いにならずに使っていきましょう！

自分も少しでもPadrinoに協力できるようにがんばります！

追記

http_routerがPadrinoの高速なルーティングを実現しているという事実を認めたとしても、やはり保守性に問題がありすぎるので、自分でルーターを開発してみました。

namusyaka/pendragon

Padrino1.0からはこのルーターが組み込まれる予定です。

Mustermannというライブラリを使用しているため、ルーターのコード自体は然程多くはありません。

現時点で既にhttp_routerと同等以上のパフォーマンスを発揮していますし、まだ高速化の余地があるのでなかなか楽しみなやつです。

法華経

よろしくどうぞ