Visualizing routes as a DFA state table

routes_as_dfa.markdown

Visualizing routes as a DFA state table

Given a routing table in rails, it is possible to generate a state table for recognizing URI paths. We'll use journey to parse routes, and a proof of concept library compiler to generate the state table.

Routes

We'll work assuming a routes file that looks like this:

AppTemplate::Application.routes.draw do
  resources :articles
end

Generating a Parse tree

A resource in Rails will create four unique patterns for matching the path:

/articles(.:format)
/articles/new(.:format)
/articles/:id/edit(.:format)
/articles/:id(.:format)

We can use journey obtain a parse tree for each route and generate a graph:

require 'compiler'

parser = Journey::Definition::Parser.new
ast    = parser.parse '/articles(.:format)'
puts ast.to_dot

If we graph the generated parse tree, it looks like this:

Converting to an NFA

We can walk the parse tree for a route and convert an NFA table for that route. After obtaining this table, we can output a dot file:

require 'compiler'

parser   = Journey::Definition::Parser.new
ast      = parser.parse '/articles(.:format)'
to_nfa   = Journey::ToNFA.new
nfa_tree = to_nfa.accept ast

puts nfa_tree.to_dot

Feed the dot file through Graphviz and we get this:

The circled node indicates an "accepting" state. If our state machine ends on that state, we know we have a match.

Converting NFA to DFA

We can convert our NFA table to a DFA table, reducing states and eliminating nil transitions. Finally, output our DFA table as a dot file:

require 'compiler'

parser   = Journey::Definition::Parser.new
ast      = parser.parse '/articles(.:format)'
to_nfa   = Journey::ToNFA.new
nfa_tree = to_nfa.accept ast

nfa = Compiler::NFA.new nfa_tree
dfa_tree = nfa.dfa_tree

puts dfa_tree.to_dot

Feed this dot file through Graphviz:

We now have vastly fewer states, and our table is deterministic. Again, the double circled states are states where we know we have a match.

Combining our routes

We create parse trees for all routes generated by the resources line and combine them using an OR node. We'll output dot files for the combined NFA and DFA state tables:

require 'compiler'

routes = [
  '/articles(.:format)',
  '/articles/new(.:format)',
  '/articles/:id/edit(.:format)',
  '/articles/:id(.:format)',
]

parser = Journey::Definition::Parser.new

# Parse all routes
asts = routes.map { |r| parser.parse r }

# Combine routes under an OR node
ast = Journey::Definition::Node.new(:OR, asts)

to_nfa   = Journey::ToNFA.new
nfa_tree = to_nfa.accept ast

File.open('nfa.dot', 'wb') { |f| f.write nfa_tree.to_dot }

nfa = Compiler::NFA.new nfa_tree
dfa_tree = nfa.dfa_tree

File.open('dfa.dot', 'wb') { |f| f.write dfa_tree.to_dot }

The resulting NFA table looks like this:

Finally we can view the resulting DFA table:

What next?

Possible next steps could be:

• Output state tables that Racc can use for simulation
• Write our own simulator for this state table
• Generate a regular expression from the DFA

Improvements:

• Make journey directly output the NFA from the grammar

A big use of this data would be able to ensure your functional tests cover 100% of your website. In addition this defines the entire surface of your application exposed over HTTP, which is good for security audits.

So cool. Seems writing the routing engine is always a fun game. I suspect that is what this is for? Perhaps to speed it up?

Thanks for this! I'm trying to get this working with the new version of Journey is difficult (without really understanding Journey enough). I've updated the gist and complier, but it looks like Node was moved to Journey::Nodes::Node which has an initializer taking only the :left argument. So I can't figure out how to combine the routes under the OR node because population of the enumerable is not apparent. Ideas.

# Combine routes under an OR node
ast = Journey::Definition::Node.new(:OR, asts) # <- asts cannot be an argument in the initializer.