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

zhuoerri · 2021年03月04日 · 最后由 Vectorz 回复于 2021年03月05日 · 424 次阅读
本帖已被管理员设置为精华贴

前言

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

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

之后 router 根据节点里存的 controller 和 aciton 信息,把 rack 请求转给对应的 controller

总结

本文只讲了有限状态机,具体的判断逻辑其实更复杂,例如 /users/:id 这种 :id 参数名,dfa 匹配时需要考虑正则表达式。但本文都省略了,感兴趣的同学可以自行深入浏览源码。

最后推荐一本书的前半部分(因为我只读了前半部分)《计算的本质》,前半部分用 ruby 语言实现了简单的词法分析器与语法分析器。虽然从编译原理的角度看不够专业,但特别适小白合作为看 Rails 路由 Journey 前的预备资料。

jasl 将本帖设为了精华贴。 03月05日 21:58

计算的本质好评!这书是我当初入门 ruby 的书😆

需要 登录 后方可回复, 如果你还没有账号请 注册新账号