Rails Rails 路由 Journey 与有限状态自动机

zhuoerri · 2021年03月04日 · 最后由 liuminhan 回复于 2022年01月25日 · 1277 次阅读

本帖已被管理员设置为精华贴

前言

本人水平有限，如有错误，欢迎指正与补充。

Rails 路由的作用是根据 config/routes.rb 的规则，生成有限状态自动机来匹配 http 请求的路径，找到对应的 controller 与 action。然后将 rack 的请求转给 controller 的 action

本文主要介绍有限状态自动机的部分，Mapper 以及 RouteSet 只会一笔带过，论坛里早已有过分析 Mapper 和 RouteSet 等源码的帖子，感兴趣的同学可阅读下面的链接。

https://ruby-china.org/topics/22726

https://ruby-china.org/topics/30916

https://ruby-china.org/topics/34110

https://ruby-china.org/topics/30929

Mapper

config/routes.rb 里各种方法的源码主要在 actionpack/lib/action_dispatch/routing/mapper.rb 里，例如最常用的 resources 方法就定义在 mapper.rb 里。

Racc 与抽象语法树

Mapper 里识别了路径后，再用 Racc 根据 actionpack/lib/action_dispatch/journey/parser.y 自动生成的 actionpack/lib/action_dispatch/journey/parser.rb。来生成以 Journey::Nodes::Node 为节点的抽象语法树。例如如下代码

ActionDispatch::Journey::Parser.new.parse("/users/new")

#<ActionDispatch::Journey::Nodes::Cat:0x0055a9bd16a0a0
 @left=#<ActionDispatch::Journey::Nodes::Slash:0x0055a9bd16a4d8 @left="/", @memo=nil>,
 @memo=nil,
 @right=
  #<ActionDispatch::Journey::Nodes::Cat:0x0055a9bd16a0f0
   @left=#<ActionDispatch::Journey::Nodes::Literal:0x0055a9bd16a3c0 @left="users", @memo=nil>,
   @memo=nil,
   @right=
    #<ActionDispatch::Journey::Nodes::Cat:0x0055a9bd16a140
     @left=#<ActionDispatch::Journey::Nodes::Slash:0x0055a9bd16a2f8 @left="/", @memo=nil>,
     @memo=nil,
     @right=#<ActionDispatch::Journey::Nodes::Literal:0x0055a9bd16a1e0 @left="new", @memo=nil>>>>

整理一下返回结果，画成图如下

Journey

语法树

Journey 把每个路由规则的小语法树，拼成一个大语法树，以 Node::Or 作为 root 节点，例如如图。

有限状态自动机

以上图为例，当 http 请求的路径是/users/2 时。Journey 依次读到了的是 /, users, /, 2。当读到/, users 的这两个前缀时，从大语法树的 root 节点出发，每个子语法树 /users/new, /users, /users/:id 都匹配，这时就不知道该应该走哪个子节点来匹配。

这种处于某个节点状态，根据输入的数据能转移到多个子节点，不确定应该转到哪个节点才能匹配的图，就是不确定的有限状态自动机 nfa.

nfa 转 dfa

不确定有限状态自动机是可以转为确定的有限状态自动机 dfa(每个输入能确定跳转到唯一的目标节点)，原理就是把多个不确定有限状态自动机的节点，组成一个集和，作为一个新状态。这个新状态作为确定的有限状态自动机里的节点状态。例如下图

左边是不确定的有限状态自动机，右边是对应的确定的优先状态自动机。黄色节点为接受状态节点。左右都可以识别 12，13，124，134 这四个字符串。但左边的 a 节点读取到 1 时，不能确定跳转到 b，还是 c。而右边节点的 A，读取到 1 时，直接确定跳转到 B。所以右边的 B 对应左边的 [b, c]。右边其他节点同理。

Journey::GTG::TransitionTable

rails 里把整个 Nodes::Node 的 nfa 转为 TransitionTable 的 dfa，源码在 Journey::GTG::Builder.transition_table , 省略精简后，主要逻辑如下

def transition_table
  # dtrans 用来存储最终的 dfa
  dtrans   = TransitionTable.new

  # 给新生成的dfa节点赋值一个id
  state_id = Hash.new { |h, k| h[k] = h.length }.compare_by_identity

  # root 是 nfa的根节点，dstates里存储了从根节点出发，能转移到的所有节点组成的出发节点数组
  dstates  = [firstpos(root)]

  until dstates.empty?
    s = dstates.shift

    s.group_by { |state| symbol(state) }.each do |sym, ps|
      # u是一个数组，对应原nfa中所有可能跳转到的目标节点数组
      u = ps.flat_map { |l| @followpos[l] }.uniq
      next if u.empty?

      # from是新建的dfa里的出发节点，对应原nfa里s出发节点数组
      from = state_id[s]

      # 如果所有nfa中的目标节点数组中节点都是接受节点
      if u.all? { |pos| pos == DUMMY_END_NODE }
        # 创建一个新 dfa 节点
        to = state_id[Object.new]
        # 写入dfa中，从from节点，读取到sym后，进入to节点
        dtrans[from, to] = sym
        # 把to节点标记为接受节点
        dtrans.add_accepting(to)

      else
        # 根据nfa的u节点数组，读取或新建对应的dfa节点to
        to = state_id[u]
        # 写入dfa中，从from节点，读取到sym后，进入to节点
        dtrans[from, to] = sym

        if u.include?(DUMMY_END_NODE)
          # 如果u节点数组中有接受节点，把to节点标记为接受节点
          dtrans.add_accepting(to)
        end
      end

      # 把u节点数组作为出发节点，继续循环
      dstates << u
    end

处理 rack 请求

router 收到 rack 请求后，会尝试用上面的 TransitionTable 来匹配 req.path_info。匹配的源码主要在 Journey::GTG::Simulator#memos

def memos(string)
    # input 是要匹配的路径，例如 /users/new
    input = StringScanner.new(string)

    # INITIAL_STATE = [ [0, nil] ].
    # dfa 的初始节点状态，即0 
    state = INITIAL_STATE

    start_index = 0

    while sym = input.scan(%r([/.?]|[^/.?]+))
      end_index = start_index + sym.length

     # tt是TransitionTable
     # 从state节点出发，读取到 string[start_index, end_index] 后，跳转的目标节点又赋值给state
      state = tt.move(state, string, start_index, end_index)

      start_index = end_index
    end

    # 如果最终有可接受节点，返回节点信息。否则 yield
    acceptance_states = state.each_with_object([]) do |s_d, memos|
      s, idx = s_d
      memos.concat(tt.memo(s)) if idx.nil? && tt.accepting?(s)
    end

    acceptance_states.empty? ? yield : acceptance_states
  end