diff options
Diffstat (limited to 'actionpack/lib/action_dispatch/journey')
24 files changed, 2417 insertions, 0 deletions
diff --git a/actionpack/lib/action_dispatch/journey/backwards.rb b/actionpack/lib/action_dispatch/journey/backwards.rb new file mode 100644 index 0000000000..3bd20fdf81 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/backwards.rb @@ -0,0 +1,5 @@ +module Rack # :nodoc: + Mount = ActionDispatch::Journey::Router + Mount::RouteSet = ActionDispatch::Journey::Router + Mount::RegexpWithNamedGroups = ActionDispatch::Journey::Path::Pattern +end diff --git a/actionpack/lib/action_dispatch/journey/formatter.rb b/actionpack/lib/action_dispatch/journey/formatter.rb new file mode 100644 index 0000000000..177f586c0e --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/formatter.rb @@ -0,0 +1,166 @@ +require 'action_controller/metal/exceptions' +require 'active_support/deprecation' + +module ActionDispatch + module Journey + # The Formatter class is used for formatting URLs. For example, parameters + # passed to +url_for+ in Rails will eventually call Formatter#generate. + class Formatter # :nodoc: + attr_reader :routes + + def initialize(routes) + @routes = routes + @cache = nil + end + + def generate(name, options, path_parameters, parameterize = nil) + constraints = path_parameters.merge(options) + missing_keys = [] + + match_route(name, constraints) do |route| + parameterized_parts = extract_parameterized_parts(route, options, path_parameters, parameterize) + + # Skip this route unless a name has been provided or it is a + # standard Rails route since we can't determine whether an options + # hash passed to url_for matches a Rack application or a redirect. + next unless name || route.dispatcher? + + missing_keys = missing_keys(route, parameterized_parts) + next unless missing_keys.empty? + params = options.dup.delete_if do |key, _| + parameterized_parts.key?(key) || route.defaults.key?(key) + end + + defaults = route.defaults + required_parts = route.required_parts + parameterized_parts.delete_if do |key, value| + value.to_s == defaults[key].to_s && !required_parts.include?(key) + end + + return [route.format(parameterized_parts), params] + end + + message = "No route matches #{Hash[constraints.sort].inspect}" + message << " missing required keys: #{missing_keys.sort.inspect}" unless missing_keys.empty? + + raise ActionController::UrlGenerationError, message + end + + def clear + @cache = nil + end + + private + + def extract_parameterized_parts(route, options, recall, parameterize = nil) + parameterized_parts = recall.merge(options) + + keys_to_keep = route.parts.reverse.drop_while { |part| + !options.key?(part) || (options[part] || recall[part]).nil? + } | route.required_parts + + (parameterized_parts.keys - keys_to_keep).each do |bad_key| + parameterized_parts.delete(bad_key) + end + + if parameterize + parameterized_parts.each do |k, v| + parameterized_parts[k] = parameterize.call(k, v) + end + end + + parameterized_parts.keep_if { |_, v| v } + parameterized_parts + end + + def named_routes + routes.named_routes + end + + def match_route(name, options) + if named_routes.key?(name) + yield named_routes[name] + else + # Make sure we don't show the deprecation warning more than once + warned = false + + routes = non_recursive(cache, options) + + hash = routes.group_by { |_, r| r.score(options) } + + hash.keys.sort.reverse_each do |score| + break if score < 0 + + hash[score].sort_by { |i, _| i }.each do |_, route| + if name && !warned + ActiveSupport::Deprecation.warn <<-MSG.squish + You are trying to generate the URL for a named route called + #{name.inspect} but no such route was found. In the future, + this will result in an `ActionController::UrlGenerationError` + exception. + MSG + + warned = true + end + + yield route + end + end + end + end + + def non_recursive(cache, options) + routes = [] + queue = [cache] + + while queue.any? + c = queue.shift + routes.concat(c[:___routes]) if c.key?(:___routes) + + options.each do |pair| + queue << c[pair] if c.key?(pair) + end + end + + routes + end + + # Returns an array populated with missing keys if any are present. + def missing_keys(route, parts) + missing_keys = [] + tests = route.path.requirements + route.required_parts.each { |key| + if tests.key?(key) + missing_keys << key unless /\A#{tests[key]}\Z/ === parts[key] + else + missing_keys << key unless parts[key] + end + } + missing_keys + end + + def possibles(cache, options, depth = 0) + cache.fetch(:___routes) { [] } + options.find_all { |pair| + cache.key?(pair) + }.flat_map { |pair| + possibles(cache[pair], options, depth + 1) + } + end + + def build_cache + root = { ___routes: [] } + routes.each_with_index do |route, i| + leaf = route.required_defaults.inject(root) do |h, tuple| + h[tuple] ||= {} + end + (leaf[:___routes] ||= []) << [i, route] + end + root + end + + def cache + @cache ||= build_cache + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/gtg/builder.rb b/actionpack/lib/action_dispatch/journey/gtg/builder.rb new file mode 100644 index 0000000000..450588cda6 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/builder.rb @@ -0,0 +1,162 @@ +require 'action_dispatch/journey/gtg/transition_table' + +module ActionDispatch + module Journey # :nodoc: + module GTG # :nodoc: + class Builder # :nodoc: + DUMMY = Nodes::Dummy.new + + attr_reader :root, :ast, :endpoints + + def initialize(root) + @root = root + @ast = Nodes::Cat.new root, DUMMY + @followpos = nil + end + + def transition_table + dtrans = TransitionTable.new + marked = {} + state_id = Hash.new { |h,k| h[k] = h.length } + + start = firstpos(root) + dstates = [start] + until dstates.empty? + s = dstates.shift + next if marked[s] + marked[s] = true # mark s + + s.group_by { |state| symbol(state) }.each do |sym, ps| + u = ps.flat_map { |l| followpos(l) } + next if u.empty? + + if u.uniq == [DUMMY] + from = state_id[s] + to = state_id[Object.new] + dtrans[from, to] = sym + + dtrans.add_accepting(to) + ps.each { |state| dtrans.add_memo(to, state.memo) } + else + dtrans[state_id[s], state_id[u]] = sym + + if u.include?(DUMMY) + to = state_id[u] + + accepting = ps.find_all { |l| followpos(l).include?(DUMMY) } + + accepting.each { |accepting_state| + dtrans.add_memo(to, accepting_state.memo) + } + + dtrans.add_accepting(state_id[u]) + end + end + + dstates << u + end + end + + dtrans + end + + def nullable?(node) + case node + when Nodes::Group + true + when Nodes::Star + true + when Nodes::Or + node.children.any? { |c| nullable?(c) } + when Nodes::Cat + nullable?(node.left) && nullable?(node.right) + when Nodes::Terminal + !node.left + when Nodes::Unary + nullable?(node.left) + else + raise ArgumentError, 'unknown nullable: %s' % node.class.name + end + end + + def firstpos(node) + case node + when Nodes::Star + firstpos(node.left) + when Nodes::Cat + if nullable?(node.left) + firstpos(node.left) | firstpos(node.right) + else + firstpos(node.left) + end + when Nodes::Or + node.children.flat_map { |c| firstpos(c) }.uniq + when Nodes::Unary + firstpos(node.left) + when Nodes::Terminal + nullable?(node) ? [] : [node] + else + raise ArgumentError, 'unknown firstpos: %s' % node.class.name + end + end + + def lastpos(node) + case node + when Nodes::Star + firstpos(node.left) + when Nodes::Or + node.children.flat_map { |c| lastpos(c) }.uniq + when Nodes::Cat + if nullable?(node.right) + lastpos(node.left) | lastpos(node.right) + else + lastpos(node.right) + end + when Nodes::Terminal + nullable?(node) ? [] : [node] + when Nodes::Unary + lastpos(node.left) + else + raise ArgumentError, 'unknown lastpos: %s' % node.class.name + end + end + + def followpos(node) + followpos_table[node] + end + + private + + def followpos_table + @followpos ||= build_followpos + end + + def build_followpos + table = Hash.new { |h, k| h[k] = [] } + @ast.each do |n| + case n + when Nodes::Cat + lastpos(n.left).each do |i| + table[i] += firstpos(n.right) + end + when Nodes::Star + lastpos(n).each do |i| + table[i] += firstpos(n) + end + end + end + table + end + + def symbol(edge) + case edge + when Journey::Nodes::Symbol + edge.regexp + else + edge.left + end + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/gtg/simulator.rb b/actionpack/lib/action_dispatch/journey/gtg/simulator.rb new file mode 100644 index 0000000000..94b0a24344 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/simulator.rb @@ -0,0 +1,47 @@ +require 'strscan' + +module ActionDispatch + module Journey # :nodoc: + module GTG # :nodoc: + class MatchData # :nodoc: + attr_reader :memos + + def initialize(memos) + @memos = memos + end + end + + class Simulator # :nodoc: + attr_reader :tt + + def initialize(transition_table) + @tt = transition_table + end + + def simulate(string) + ms = memos(string) { return } + MatchData.new(ms) + end + + alias :=~ :simulate + alias :match :simulate + + def memos(string) + input = StringScanner.new(string) + state = [0] + while sym = input.scan(%r([/.?]|[^/.?]+)) + state = tt.move(state, sym) + end + + acceptance_states = state.find_all { |s| + tt.accepting? s + } + + return yield if acceptance_states.empty? + + acceptance_states.flat_map { |x| tt.memo(x) }.compact + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb b/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb new file mode 100644 index 0000000000..1b914f0637 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb @@ -0,0 +1,157 @@ +require 'action_dispatch/journey/nfa/dot' + +module ActionDispatch + module Journey # :nodoc: + module GTG # :nodoc: + class TransitionTable # :nodoc: + include Journey::NFA::Dot + + attr_reader :memos + + def initialize + @regexp_states = {} + @string_states = {} + @accepting = {} + @memos = Hash.new { |h,k| h[k] = [] } + end + + def add_accepting(state) + @accepting[state] = true + end + + def accepting_states + @accepting.keys + end + + def accepting?(state) + @accepting[state] + end + + def add_memo(idx, memo) + @memos[idx] << memo + end + + def memo(idx) + @memos[idx] + end + + def eclosure(t) + Array(t) + end + + def move(t, a) + return [] if t.empty? + + regexps = [] + + t.map { |s| + if states = @regexp_states[s] + regexps.concat states.map { |re, v| re === a ? v : nil } + end + + if states = @string_states[s] + states[a] + end + }.compact.concat regexps + end + + def as_json(options = nil) + simple_regexp = Hash.new { |h,k| h[k] = {} } + + @regexp_states.each do |from, hash| + hash.each do |re, to| + simple_regexp[from][re.source] = to + end + end + + { + regexp_states: simple_regexp, + string_states: @string_states, + accepting: @accepting + } + end + + def to_svg + svg = IO.popen('dot -Tsvg', 'w+') { |f| + f.write(to_dot) + f.close_write + f.readlines + } + 3.times { svg.shift } + svg.join.sub(/width="[^"]*"/, '').sub(/height="[^"]*"/, '') + end + + def visualizer(paths, title = 'FSM') + viz_dir = File.join File.dirname(__FILE__), '..', 'visualizer' + fsm_js = File.read File.join(viz_dir, 'fsm.js') + fsm_css = File.read File.join(viz_dir, 'fsm.css') + erb = File.read File.join(viz_dir, 'index.html.erb') + states = "function tt() { return #{to_json}; }" + + fun_routes = paths.sample(3).map do |ast| + ast.map { |n| + case n + when Nodes::Symbol + case n.left + when ':id' then rand(100).to_s + when ':format' then %w{ xml json }.sample + else + 'omg' + end + when Nodes::Terminal then n.symbol + else + nil + end + }.compact.join + end + + stylesheets = [fsm_css] + svg = to_svg + javascripts = [states, fsm_js] + + # Annoying hack for 1.9 warnings + fun_routes = fun_routes + stylesheets = stylesheets + svg = svg + javascripts = javascripts + + require 'erb' + template = ERB.new erb + template.result(binding) + end + + def []=(from, to, sym) + to_mappings = states_hash_for(sym)[from] ||= {} + to_mappings[sym] = to + end + + def states + ss = @string_states.keys + @string_states.values.flat_map(&:values) + rs = @regexp_states.keys + @regexp_states.values.flat_map(&:values) + (ss + rs).uniq + end + + def transitions + @string_states.flat_map { |from, hash| + hash.map { |s, to| [from, s, to] } + } + @regexp_states.flat_map { |from, hash| + hash.map { |s, to| [from, s, to] } + } + end + + private + + def states_hash_for(sym) + case sym + when String + @string_states + when Regexp + @regexp_states + else + raise ArgumentError, 'unknown symbol: %s' % sym.class + end + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/nfa/builder.rb b/actionpack/lib/action_dispatch/journey/nfa/builder.rb new file mode 100644 index 0000000000..ee6494c3e4 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/builder.rb @@ -0,0 +1,76 @@ +require 'action_dispatch/journey/nfa/transition_table' +require 'action_dispatch/journey/gtg/transition_table' + +module ActionDispatch + module Journey # :nodoc: + module NFA # :nodoc: + class Visitor < Visitors::Visitor # :nodoc: + def initialize(tt) + @tt = tt + @i = -1 + end + + def visit_CAT(node) + left = visit(node.left) + right = visit(node.right) + + @tt.merge(left.last, right.first) + + [left.first, right.last] + end + + def visit_GROUP(node) + from = @i += 1 + left = visit(node.left) + to = @i += 1 + + @tt.accepting = to + + @tt[from, left.first] = nil + @tt[left.last, to] = nil + @tt[from, to] = nil + + [from, to] + end + + def visit_OR(node) + from = @i += 1 + children = node.children.map { |c| visit(c) } + to = @i += 1 + + children.each do |child| + @tt[from, child.first] = nil + @tt[child.last, to] = nil + end + + @tt.accepting = to + + [from, to] + end + + def terminal(node) + from_i = @i += 1 # new state + to_i = @i += 1 # new state + + @tt[from_i, to_i] = node + @tt.accepting = to_i + @tt.add_memo(to_i, node.memo) + + [from_i, to_i] + end + end + + class Builder # :nodoc: + def initialize(ast) + @ast = ast + end + + def transition_table + tt = TransitionTable.new + Visitor.new(tt).accept(@ast) + tt + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/nfa/dot.rb b/actionpack/lib/action_dispatch/journey/nfa/dot.rb new file mode 100644 index 0000000000..47bf76bdbf --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/dot.rb @@ -0,0 +1,36 @@ +# encoding: utf-8 + +module ActionDispatch + module Journey # :nodoc: + module NFA # :nodoc: + module Dot # :nodoc: + def to_dot + edges = transitions.map { |from, sym, to| + " #{from} -> #{to} [label=\"#{sym || 'ε'}\"];" + } + + #memo_nodes = memos.values.flatten.map { |n| + # label = n + # if Journey::Route === n + # label = "#{n.verb.source} #{n.path.spec}" + # end + # " #{n.object_id} [label=\"#{label}\", shape=box];" + #} + #memo_edges = memos.flat_map { |k, memos| + # (memos || []).map { |v| " #{k} -> #{v.object_id};" } + #}.uniq + + <<-eodot +digraph nfa { + rankdir=LR; + node [shape = doublecircle]; + #{accepting_states.join ' '}; + node [shape = circle]; +#{edges.join "\n"} +} + eodot + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/nfa/simulator.rb b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb new file mode 100644 index 0000000000..b23270db3c --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb @@ -0,0 +1,47 @@ +require 'strscan' + +module ActionDispatch + module Journey # :nodoc: + module NFA # :nodoc: + class MatchData # :nodoc: + attr_reader :memos + + def initialize(memos) + @memos = memos + end + end + + class Simulator # :nodoc: + attr_reader :tt + + def initialize(transition_table) + @tt = transition_table + end + + def simulate(string) + input = StringScanner.new(string) + state = tt.eclosure(0) + until input.eos? + sym = input.scan(%r([/.?]|[^/.?]+)) + + # FIXME: tt.eclosure is not needed for the GTG + state = tt.eclosure(tt.move(state, sym)) + end + + acceptance_states = state.find_all { |s| + tt.accepting?(tt.eclosure(s).sort.last) + } + + return if acceptance_states.empty? + + memos = acceptance_states.flat_map { |x| tt.memo(x) }.compact + + MatchData.new(memos) + end + + alias :=~ :simulate + alias :match :simulate + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb new file mode 100644 index 0000000000..e65f7238ab --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb @@ -0,0 +1,163 @@ +require 'action_dispatch/journey/nfa/dot' + +module ActionDispatch + module Journey # :nodoc: + module NFA # :nodoc: + class TransitionTable # :nodoc: + include Journey::NFA::Dot + + attr_accessor :accepting + attr_reader :memos + + def initialize + @table = Hash.new { |h,f| h[f] = {} } + @memos = {} + @accepting = nil + @inverted = nil + end + + def accepting?(state) + accepting == state + end + + def accepting_states + [accepting] + end + + def add_memo(idx, memo) + @memos[idx] = memo + end + + def memo(idx) + @memos[idx] + end + + def []=(i, f, s) + @table[f][i] = s + end + + def merge(left, right) + @memos[right] = @memos.delete(left) + @table[right] = @table.delete(left) + end + + def states + (@table.keys + @table.values.flat_map(&:keys)).uniq + end + + # Returns a generalized transition graph with reduced states. The states + # are reduced like a DFA, but the table must be simulated like an NFA. + # + # Edges of the GTG are regular expressions. + def generalized_table + gt = GTG::TransitionTable.new + marked = {} + state_id = Hash.new { |h,k| h[k] = h.length } + alphabet = self.alphabet + + stack = [eclosure(0)] + + until stack.empty? + state = stack.pop + next if marked[state] || state.empty? + + marked[state] = true + + alphabet.each do |alpha| + next_state = eclosure(following_states(state, alpha)) + next if next_state.empty? + + gt[state_id[state], state_id[next_state]] = alpha + stack << next_state + end + end + + final_groups = state_id.keys.find_all { |s| + s.sort.last == accepting + } + + final_groups.each do |states| + id = state_id[states] + + gt.add_accepting(id) + save = states.find { |s| + @memos.key?(s) && eclosure(s).sort.last == accepting + } + + gt.add_memo(id, memo(save)) + end + + gt + end + + # Returns set of NFA states to which there is a transition on ast symbol + # +a+ from some state +s+ in +t+. + def following_states(t, a) + Array(t).flat_map { |s| inverted[s][a] }.uniq + end + + # Returns set of NFA states to which there is a transition on ast symbol + # +a+ from some state +s+ in +t+. + def move(t, a) + Array(t).map { |s| + inverted[s].keys.compact.find_all { |sym| + sym === a + }.map { |sym| inverted[s][sym] } + }.flatten.uniq + end + + def alphabet + inverted.values.flat_map(&:keys).compact.uniq.sort_by(&:to_s) + end + + # Returns a set of NFA states reachable from some NFA state +s+ in set + # +t+ on nil-transitions alone. + def eclosure(t) + stack = Array(t) + seen = {} + children = [] + + until stack.empty? + s = stack.pop + next if seen[s] + + seen[s] = true + children << s + + stack.concat(inverted[s][nil]) + end + + children.uniq + end + + def transitions + @table.flat_map { |to, hash| + hash.map { |from, sym| [from, sym, to] } + } + end + + private + + def inverted + return @inverted if @inverted + + @inverted = Hash.new { |h, from| + h[from] = Hash.new { |j, s| j[s] = [] } + } + + @table.each { |to, hash| + hash.each { |from, sym| + if sym + sym = Nodes::Symbol === sym ? sym.regexp : sym.left + end + + @inverted[from][sym] << to + } + } + + @inverted + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/nodes/node.rb b/actionpack/lib/action_dispatch/journey/nodes/node.rb new file mode 100644 index 0000000000..bb01c087bc --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nodes/node.rb @@ -0,0 +1,128 @@ +require 'action_dispatch/journey/visitors' + +module ActionDispatch + module Journey # :nodoc: + module Nodes # :nodoc: + class Node # :nodoc: + include Enumerable + + attr_accessor :left, :memo + + def initialize(left) + @left = left + @memo = nil + end + + def each(&block) + Visitors::Each.new(block).accept(self) + end + + def to_s + Visitors::String.new.accept(self) + end + + def to_dot + Visitors::Dot.new.accept(self) + end + + def to_sym + name.to_sym + end + + def name + left.tr '*:', '' + end + + def type + raise NotImplementedError + end + + def symbol?; false; end + def literal?; false; end + end + + class Terminal < Node # :nodoc: + alias :symbol :left + end + + class Literal < Terminal # :nodoc: + def literal?; true; end + def type; :LITERAL; end + end + + class Dummy < Literal # :nodoc: + def initialize(x = Object.new) + super + end + + def literal?; false; end + end + + %w{ Symbol Slash Dot }.each do |t| + class_eval <<-eoruby, __FILE__, __LINE__ + 1 + class #{t} < Terminal; + def type; :#{t.upcase}; end + end + eoruby + end + + class Symbol < Terminal # :nodoc: + attr_accessor :regexp + alias :symbol :regexp + + DEFAULT_EXP = /[^\.\/\?]+/ + def initialize(left) + super + @regexp = DEFAULT_EXP + end + + def default_regexp? + regexp == DEFAULT_EXP + end + + def symbol?; true; end + end + + class Unary < Node # :nodoc: + def children; [left] end + end + + class Group < Unary # :nodoc: + def type; :GROUP; end + end + + class Star < Unary # :nodoc: + def type; :STAR; end + + def name + left.name.tr '*:', '' + end + end + + class Binary < Node # :nodoc: + attr_accessor :right + + def initialize(left, right) + super(left) + @right = right + end + + def children; [left, right] end + end + + class Cat < Binary # :nodoc: + def type; :CAT; end + end + + class Or < Node # :nodoc: + attr_reader :children + + def initialize(children) + @children = children + end + + def type; :OR; end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/parser.rb b/actionpack/lib/action_dispatch/journey/parser.rb new file mode 100644 index 0000000000..9012297400 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/parser.rb @@ -0,0 +1,198 @@ +# +# DO NOT MODIFY!!!! +# This file is automatically generated by Racc 1.4.11 +# from Racc grammer file "". +# + +require 'racc/parser.rb' + + +require 'action_dispatch/journey/parser_extras' +module ActionDispatch + module Journey + class Parser < Racc::Parser +##### State transition tables begin ### + +racc_action_table = [ + 13, 15, 14, 7, 21, 16, 8, 19, 13, 15, + 14, 7, 17, 16, 8, 13, 15, 14, 7, 24, + 16, 8, 13, 15, 14, 7, 19, 16, 8 ] + +racc_action_check = [ + 2, 2, 2, 2, 17, 2, 2, 2, 0, 0, + 0, 0, 1, 0, 0, 19, 19, 19, 19, 20, + 19, 19, 7, 7, 7, 7, 22, 7, 7 ] + +racc_action_pointer = [ + 6, 12, -2, nil, nil, nil, nil, 20, nil, nil, + nil, nil, nil, nil, nil, nil, nil, 4, nil, 13, + 13, nil, 17, nil, nil ] + +racc_action_default = [ + -19, -19, -2, -3, -4, -5, -6, -19, -10, -11, + -12, -13, -14, -15, -16, -17, -18, -19, -1, -19, + -19, 25, -8, -9, -7 ] + +racc_goto_table = [ + 1, 22, 18, 23, nil, nil, nil, 20 ] + +racc_goto_check = [ + 1, 2, 1, 3, nil, nil, nil, 1 ] + +racc_goto_pointer = [ + nil, 0, -18, -16, nil, nil, nil, nil, nil, nil, + nil ] + +racc_goto_default = [ + nil, nil, 2, 3, 4, 5, 6, 9, 10, 11, + 12 ] + +racc_reduce_table = [ + 0, 0, :racc_error, + 2, 11, :_reduce_1, + 1, 11, :_reduce_2, + 1, 11, :_reduce_none, + 1, 12, :_reduce_none, + 1, 12, :_reduce_none, + 1, 12, :_reduce_none, + 3, 15, :_reduce_7, + 3, 13, :_reduce_8, + 3, 13, :_reduce_9, + 1, 16, :_reduce_10, + 1, 14, :_reduce_none, + 1, 14, :_reduce_none, + 1, 14, :_reduce_none, + 1, 14, :_reduce_none, + 1, 19, :_reduce_15, + 1, 17, :_reduce_16, + 1, 18, :_reduce_17, + 1, 20, :_reduce_18 ] + +racc_reduce_n = 19 + +racc_shift_n = 25 + +racc_token_table = { + false => 0, + :error => 1, + :SLASH => 2, + :LITERAL => 3, + :SYMBOL => 4, + :LPAREN => 5, + :RPAREN => 6, + :DOT => 7, + :STAR => 8, + :OR => 9 } + +racc_nt_base = 10 + +racc_use_result_var = false + +Racc_arg = [ + racc_action_table, + racc_action_check, + racc_action_default, + racc_action_pointer, + racc_goto_table, + racc_goto_check, + racc_goto_default, + racc_goto_pointer, + racc_nt_base, + racc_reduce_table, + racc_token_table, + racc_shift_n, + racc_reduce_n, + racc_use_result_var ] + +Racc_token_to_s_table = [ + "$end", + "error", + "SLASH", + "LITERAL", + "SYMBOL", + "LPAREN", + "RPAREN", + "DOT", + "STAR", + "OR", + "$start", + "expressions", + "expression", + "or", + "terminal", + "group", + "star", + "symbol", + "literal", + "slash", + "dot" ] + +Racc_debug_parser = false + +##### State transition tables end ##### + +# reduce 0 omitted + +def _reduce_1(val, _values) + Cat.new(val.first, val.last) +end + +def _reduce_2(val, _values) + val.first +end + +# reduce 3 omitted + +# reduce 4 omitted + +# reduce 5 omitted + +# reduce 6 omitted + +def _reduce_7(val, _values) + Group.new(val[1]) +end + +def _reduce_8(val, _values) + Or.new([val.first, val.last]) +end + +def _reduce_9(val, _values) + Or.new([val.first, val.last]) +end + +def _reduce_10(val, _values) + Star.new(Symbol.new(val.last)) +end + +# reduce 11 omitted + +# reduce 12 omitted + +# reduce 13 omitted + +# reduce 14 omitted + +def _reduce_15(val, _values) + Slash.new('/') +end + +def _reduce_16(val, _values) + Symbol.new(val.first) +end + +def _reduce_17(val, _values) + Literal.new(val.first) +end + +def _reduce_18(val, _values) + Dot.new(val.first) +end + +def _reduce_none(val, _values) + val[0] +end + + end # class Parser + end # module Journey + end # module ActionDispatch diff --git a/actionpack/lib/action_dispatch/journey/parser.y b/actionpack/lib/action_dispatch/journey/parser.y new file mode 100644 index 0000000000..d3f7c4d765 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/parser.y @@ -0,0 +1,49 @@ +class ActionDispatch::Journey::Parser + options no_result_var +token SLASH LITERAL SYMBOL LPAREN RPAREN DOT STAR OR + +rule + 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('/') } + ; + symbol + : SYMBOL { Symbol.new(val.first) } + ; + literal + : LITERAL { Literal.new(val.first) } + ; + dot + : DOT { Dot.new(val.first) } + ; + +end + +---- header + +require 'action_dispatch/journey/parser_extras' diff --git a/actionpack/lib/action_dispatch/journey/parser_extras.rb b/actionpack/lib/action_dispatch/journey/parser_extras.rb new file mode 100644 index 0000000000..14892f4321 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/parser_extras.rb @@ -0,0 +1,23 @@ +require 'action_dispatch/journey/scanner' +require 'action_dispatch/journey/nodes/node' + +module ActionDispatch + module Journey # :nodoc: + class Parser < Racc::Parser # :nodoc: + include Journey::Nodes + + def initialize + @scanner = Scanner.new + end + + def parse(string) + @scanner.scan_setup(string) + do_parse + end + + def next_token + @scanner.next_token + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/path/pattern.rb b/actionpack/lib/action_dispatch/journey/path/pattern.rb new file mode 100644 index 0000000000..64b48ca45f --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/path/pattern.rb @@ -0,0 +1,198 @@ +require 'action_dispatch/journey/router/strexp' + +module ActionDispatch + module Journey # :nodoc: + module Path # :nodoc: + class Pattern # :nodoc: + attr_reader :spec, :requirements, :anchored + + def self.from_string string + new Journey::Router::Strexp.build(string, {}, ["/.?"], true) + end + + def initialize(strexp) + @spec = strexp.ast + @requirements = strexp.requirements + @separators = strexp.separators.join + @anchored = strexp.anchor + + @names = nil + @optional_names = nil + @required_names = nil + @re = nil + @offsets = nil + end + + def build_formatter + Visitors::FormatBuilder.new.accept(spec) + end + + def ast + @spec.grep(Nodes::Symbol).each do |node| + re = @requirements[node.to_sym] + node.regexp = re if re + end + + @spec.grep(Nodes::Star).each do |node| + node = node.left + node.regexp = @requirements[node.to_sym] || /(.+)/ + end + + @spec + end + + def names + @names ||= spec.grep(Nodes::Symbol).map(&:name) + end + + def required_names + @required_names ||= names - optional_names + end + + def optional_names + @optional_names ||= spec.grep(Nodes::Group).flat_map { |group| + group.grep(Nodes::Symbol) + }.map(&:name).uniq + end + + class RegexpOffsets < Journey::Visitors::Visitor # :nodoc: + attr_reader :offsets + + def initialize(matchers) + @matchers = matchers + @capture_count = [0] + end + + def visit(node) + super + @capture_count + end + + def visit_SYMBOL(node) + node = node.to_sym + + if @matchers.key?(node) + re = /#{@matchers[node]}|/ + @capture_count.push((re.match('').length - 1) + (@capture_count.last || 0)) + else + @capture_count << (@capture_count.last || 0) + end + end + end + + class AnchoredRegexp < Journey::Visitors::Visitor # :nodoc: + def initialize(separator, matchers) + @separator = separator + @matchers = matchers + @separator_re = "([^#{separator}]+)" + super() + end + + def accept(node) + %r{\A#{visit node}\Z} + end + + def visit_CAT(node) + [visit(node.left), visit(node.right)].join + end + + def visit_SYMBOL(node) + node = node.to_sym + + return @separator_re unless @matchers.key?(node) + + re = @matchers[node] + "(#{re})" + end + + def visit_GROUP(node) + "(?:#{visit node.left})?" + end + + def visit_LITERAL(node) + Regexp.escape(node.left) + end + alias :visit_DOT :visit_LITERAL + + def visit_SLASH(node) + node.left + end + + def visit_STAR(node) + re = @matchers[node.left.to_sym] || '.+' + "(#{re})" + end + + def visit_OR(node) + children = node.children.map { |n| visit n } + "(?:#{children.join(?|)})" + end + end + + class UnanchoredRegexp < AnchoredRegexp # :nodoc: + def accept(node) + %r{\A#{visit node}} + end + end + + class MatchData # :nodoc: + attr_reader :names + + def initialize(names, offsets, match) + @names = names + @offsets = offsets + @match = match + end + + def captures + (length - 1).times.map { |i| self[i + 1] } + end + + def [](x) + idx = @offsets[x - 1] + x + @match[idx] + end + + def length + @offsets.length + end + + def post_match + @match.post_match + end + + def to_s + @match.to_s + end + end + + def match(other) + return unless match = to_regexp.match(other) + MatchData.new(names, offsets, match) + end + alias :=~ :match + + def source + to_regexp.source + end + + def to_regexp + @re ||= regexp_visitor.new(@separators, @requirements).accept spec + end + + private + + def regexp_visitor + @anchored ? AnchoredRegexp : UnanchoredRegexp + end + + def offsets + return @offsets if @offsets + + viz = RegexpOffsets.new(@requirements) + @offsets = viz.accept(spec) + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/route.rb b/actionpack/lib/action_dispatch/journey/route.rb new file mode 100644 index 0000000000..3b609a184d --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/route.rb @@ -0,0 +1,125 @@ +module ActionDispatch + module Journey # :nodoc: + class Route # :nodoc: + attr_reader :app, :path, :defaults, :name + + attr_reader :constraints + alias :conditions :constraints + + attr_accessor :precedence + + ## + # +path+ is a path constraint. + # +constraints+ is a hash of constraints to be applied to this route. + def initialize(name, app, path, constraints, defaults = {}) + @name = name + @app = app + @path = path + + @constraints = constraints + @defaults = defaults + @required_defaults = nil + @required_parts = nil + @parts = nil + @decorated_ast = nil + @precedence = 0 + @path_formatter = @path.build_formatter + end + + def ast + @decorated_ast ||= begin + decorated_ast = path.ast + decorated_ast.grep(Nodes::Terminal).each { |n| n.memo = self } + decorated_ast + end + end + + def requirements # :nodoc: + # needed for rails `rake routes` + path.requirements.merge(@defaults).delete_if { |_,v| + /.+?/ == v + } + end + + def segments + path.names + end + + def required_keys + required_parts + required_defaults.keys + end + + def score(constraints) + required_keys = path.required_names + supplied_keys = constraints.map { |k,v| v && k.to_s }.compact + + return -1 unless (required_keys - supplied_keys).empty? + + score = (supplied_keys & path.names).length + score + (required_defaults.length * 2) + end + + def parts + @parts ||= segments.map(&:to_sym) + end + alias :segment_keys :parts + + def format(path_options) + @path_formatter.evaluate path_options + end + + def optional_parts + path.optional_names.map(&:to_sym) + end + + def required_parts + @required_parts ||= path.required_names.map(&:to_sym) + end + + def required_default?(key) + (constraints[:required_defaults] || []).include?(key) + end + + def required_defaults + @required_defaults ||= @defaults.dup.delete_if do |k,_| + parts.include?(k) || !required_default?(k) + end + end + + def glob? + !path.spec.grep(Nodes::Star).empty? + end + + def dispatcher? + @app.dispatcher? + end + + def matches?(request) + constraints.all? do |method, value| + next true unless request.respond_to?(method) + + case value + when Regexp, String + value === request.send(method).to_s + when Array + value.include?(request.send(method)) + when TrueClass + request.send(method).present? + when FalseClass + request.send(method).blank? + else + value === request.send(method) + end + end + end + + def ip + constraints[:ip] || // + end + + def verb + constraints[:request_method] || // + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/router.rb b/actionpack/lib/action_dispatch/journey/router.rb new file mode 100644 index 0000000000..2b036796ab --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/router.rb @@ -0,0 +1,143 @@ +require 'action_dispatch/journey/router/utils' +require 'action_dispatch/journey/router/strexp' +require 'action_dispatch/journey/routes' +require 'action_dispatch/journey/formatter' + +before = $-w +$-w = false +require 'action_dispatch/journey/parser' +$-w = before + +require 'action_dispatch/journey/route' +require 'action_dispatch/journey/path/pattern' + +module ActionDispatch + module Journey # :nodoc: + class Router # :nodoc: + class RoutingError < ::StandardError # :nodoc: + end + + # :nodoc: + VERSION = '2.0.0' + + attr_accessor :routes + + def initialize(routes) + @routes = routes + end + + def serve(req) + find_routes(req).each do |match, parameters, route| + set_params = req.path_parameters + path_info = req.path_info + script_name = req.script_name + + unless route.path.anchored + req.script_name = (script_name.to_s + match.to_s).chomp('/') + req.path_info = match.post_match + req.path_info = "/" + req.path_info unless req.path_info.start_with? "/" + end + + req.path_parameters = set_params.merge parameters + + status, headers, body = route.app.serve(req) + + if 'pass' == headers['X-Cascade'] + req.script_name = script_name + req.path_info = path_info + req.path_parameters = set_params + next + end + + return [status, headers, body] + end + + return [404, {'X-Cascade' => 'pass'}, ['Not Found']] + end + + def recognize(rails_req) + find_routes(rails_req).each do |match, parameters, route| + unless route.path.anchored + rails_req.script_name = match.to_s + rails_req.path_info = match.post_match.sub(/^([^\/])/, '/\1') + end + + yield(route, parameters) + end + end + + def visualizer + tt = GTG::Builder.new(ast).transition_table + groups = partitioned_routes.first.map(&:ast).group_by(&:to_s) + asts = groups.values.map(&:first) + tt.visualizer(asts) + end + + private + + def partitioned_routes + routes.partitioned_routes + end + + def ast + routes.ast + end + + def simulator + routes.simulator + end + + def custom_routes + partitioned_routes.last + end + + def filter_routes(path) + return [] unless ast + simulator.memos(path) { [] } + end + + def find_routes req + routes = filter_routes(req.path_info).concat custom_routes.find_all { |r| + r.path.match(req.path_info) + } + + routes = + if req.request_method == "HEAD" + match_head_routes(routes, req) + else + match_routes(routes, req) + end + + routes.sort_by!(&:precedence) + + routes.map! { |r| + match_data = r.path.match(req.path_info) + path_parameters = r.defaults.dup + match_data.names.zip(match_data.captures) { |name,val| + path_parameters[name.to_sym] = Utils.unescape_uri(val) if val + } + [match_data, path_parameters, r] + } + end + + def match_head_routes(routes, req) + head_routes = match_routes(routes, req) + + if head_routes.empty? + begin + req.request_method = "GET" + match_routes(routes, req) + ensure + req.request_method = "HEAD" + end + else + head_routes + end + end + + def match_routes(routes, req) + routes.select { |r| r.matches?(req) } + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/router/strexp.rb b/actionpack/lib/action_dispatch/journey/router/strexp.rb new file mode 100644 index 0000000000..4b7738f335 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/router/strexp.rb @@ -0,0 +1,27 @@ +module ActionDispatch + module Journey # :nodoc: + class Router # :nodoc: + class Strexp # :nodoc: + class << self + alias :compile :new + end + + attr_reader :path, :requirements, :separators, :anchor, :ast + + def self.build(path, requirements, separators, anchor = true) + parser = Journey::Parser.new + ast = parser.parse path + new ast, path, requirements, separators, anchor + end + + def initialize(ast, path, requirements, separators, anchor = true) + @ast = ast + @path = path + @requirements = requirements + @separators = separators + @anchor = anchor + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/router/utils.rb b/actionpack/lib/action_dispatch/journey/router/utils.rb new file mode 100644 index 0000000000..2b0a6575d4 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/router/utils.rb @@ -0,0 +1,93 @@ +module ActionDispatch + module Journey # :nodoc: + class Router # :nodoc: + class Utils # :nodoc: + # Normalizes URI path. + # + # Strips off trailing slash and ensures there is a leading slash. + # Also converts downcase url encoded string to uppercase. + # + # normalize_path("/foo") # => "/foo" + # normalize_path("/foo/") # => "/foo" + # normalize_path("foo") # => "/foo" + # normalize_path("") # => "/" + # normalize_path("/%ab") # => "/%AB" + def self.normalize_path(path) + path = "/#{path}" + path.squeeze!('/') + path.sub!(%r{/+\Z}, '') + path.gsub!(/(%[a-f0-9]{2})/) { $1.upcase } + path = '/' if path == '' + path + end + + # URI path and fragment escaping + # http://tools.ietf.org/html/rfc3986 + class UriEncoder # :nodoc: + ENCODE = "%%%02X".freeze + US_ASCII = Encoding::US_ASCII + UTF_8 = Encoding::UTF_8 + EMPTY = "".force_encoding(US_ASCII).freeze + DEC2HEX = (0..255).to_a.map{ |i| ENCODE % i }.map{ |s| s.force_encoding(US_ASCII) } + + ALPHA = "a-zA-Z".freeze + DIGIT = "0-9".freeze + UNRESERVED = "#{ALPHA}#{DIGIT}\\-\\._~".freeze + SUB_DELIMS = "!\\$&'\\(\\)\\*\\+,;=".freeze + + ESCAPED = /%[a-zA-Z0-9]{2}/.freeze + + FRAGMENT = /[^#{UNRESERVED}#{SUB_DELIMS}:@\/\?]/.freeze + SEGMENT = /[^#{UNRESERVED}#{SUB_DELIMS}:@]/.freeze + PATH = /[^#{UNRESERVED}#{SUB_DELIMS}:@\/]/.freeze + + def escape_fragment(fragment) + escape(fragment, FRAGMENT) + end + + def escape_path(path) + escape(path, PATH) + end + + def escape_segment(segment) + escape(segment, SEGMENT) + end + + def unescape_uri(uri) + encoding = uri.encoding == US_ASCII ? UTF_8 : uri.encoding + uri.gsub(ESCAPED) { [$&[1, 2].hex].pack('C') }.force_encoding(encoding) + end + + protected + def escape(component, pattern) + component.gsub(pattern){ |unsafe| percent_encode(unsafe) }.force_encoding(US_ASCII) + end + + def percent_encode(unsafe) + safe = EMPTY.dup + unsafe.each_byte { |b| safe << DEC2HEX[b] } + safe + end + end + + ENCODER = UriEncoder.new + + def self.escape_path(path) + ENCODER.escape_path(path.to_s) + end + + def self.escape_segment(segment) + ENCODER.escape_segment(segment.to_s) + end + + def self.escape_fragment(fragment) + ENCODER.escape_fragment(fragment.to_s) + end + + def self.unescape_uri(uri) + ENCODER.unescape_uri(uri) + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/routes.rb b/actionpack/lib/action_dispatch/journey/routes.rb new file mode 100644 index 0000000000..80e3818ccd --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/routes.rb @@ -0,0 +1,76 @@ +module ActionDispatch + module Journey # :nodoc: + # The Routing table. Contains all routes for a system. Routes can be + # added to the table by calling Routes#add_route. + class Routes # :nodoc: + include Enumerable + + attr_reader :routes, :named_routes + + def initialize + @routes = [] + @named_routes = {} + @ast = nil + @partitioned_routes = nil + @simulator = nil + end + + def length + routes.length + end + alias :size :length + + def last + routes.last + end + + def each(&block) + routes.each(&block) + end + + def clear + routes.clear + named_routes.clear + end + + def partitioned_routes + @partitioned_routes ||= routes.partition do |r| + r.path.anchored && r.ast.grep(Nodes::Symbol).all?(&:default_regexp?) + end + end + + def ast + @ast ||= begin + asts = partitioned_routes.first.map(&:ast) + Nodes::Or.new(asts) unless asts.empty? + end + end + + def simulator + @simulator ||= begin + gtg = GTG::Builder.new(ast).transition_table + GTG::Simulator.new(gtg) + end + end + + # Add a route to the routing table. + def add_route(app, path, conditions, defaults, name = nil) + route = Route.new(name, app, path, conditions, defaults) + + route.precedence = routes.length + routes << route + named_routes[name] = route if name && !named_routes[name] + clear_cache! + route + end + + private + + def clear_cache! + @ast = nil + @partitioned_routes = nil + @simulator = nil + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/scanner.rb b/actionpack/lib/action_dispatch/journey/scanner.rb new file mode 100644 index 0000000000..19e0bc03d6 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/scanner.rb @@ -0,0 +1,61 @@ +require 'strscan' + +module ActionDispatch + module Journey # :nodoc: + class Scanner # :nodoc: + def initialize + @ss = nil + end + + def scan_setup(str) + @ss = StringScanner.new(str) + end + + def eos? + @ss.eos? + end + + def pos + @ss.pos + end + + def pre_match + @ss.pre_match + end + + def next_token + return if @ss.eos? + + until token = scan || @ss.eos?; end + token + end + + private + + def scan + case + # / + when text = @ss.scan(/\//) + [:SLASH, text] + when text = @ss.scan(/\*\w+/) + [:STAR, text] + when text = @ss.scan(/(?<!\\)\(/) + [:LPAREN, text] + when text = @ss.scan(/(?<!\\)\)/) + [:RPAREN, text] + when text = @ss.scan(/\|/) + [:OR, text] + when text = @ss.scan(/\./) + [:DOT, text] + when text = @ss.scan(/(?<!\\):\w+/) + [:SYMBOL, text] + when text = @ss.scan(/(?:[\w%\-~!$&'*+,;=@]|\\:|\\\(|\\\))+/) + [:LITERAL, text.tr('\\', '')] + # any char + when text = @ss.scan(/./) + [:LITERAL, text] + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/visitors.rb b/actionpack/lib/action_dispatch/journey/visitors.rb new file mode 100644 index 0000000000..52b4c8b489 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/visitors.rb @@ -0,0 +1,221 @@ +# encoding: utf-8 + +module ActionDispatch + module Journey # :nodoc: + class Format + ESCAPE_PATH = ->(value) { Router::Utils.escape_path(value) } + ESCAPE_SEGMENT = ->(value) { Router::Utils.escape_segment(value) } + + class Parameter < Struct.new(:name, :escaper) + def escape(value); escaper.call value; end + end + + def self.required_path(symbol) + Parameter.new symbol, ESCAPE_PATH + end + + def self.required_segment(symbol) + Parameter.new symbol, ESCAPE_SEGMENT + end + + def initialize(parts) + @parts = parts + @children = [] + @parameters = [] + + parts.each_with_index do |object,i| + case object + when Journey::Format + @children << i + when Parameter + @parameters << i + end + end + end + + def evaluate(hash) + parts = @parts.dup + + @parameters.each do |index| + param = parts[index] + value = hash[param.name] + return ''.freeze unless value + parts[index] = param.escape value + end + + @children.each { |index| parts[index] = parts[index].evaluate(hash) } + + parts.join + end + end + + module Visitors # :nodoc: + class Visitor # :nodoc: + DISPATCH_CACHE = {} + + def accept(node) + visit(node) + end + + private + + def visit node + send(DISPATCH_CACHE[node.type], node) + end + + def binary(node) + visit(node.left) + visit(node.right) + end + def visit_CAT(n); binary(n); end + + def nary(node) + node.children.each { |c| visit(c) } + end + def visit_OR(n); nary(n); end + + def unary(node) + visit(node.left) + end + def visit_GROUP(n); unary(n); end + def visit_STAR(n); unary(n); end + + def terminal(node); end + def visit_LITERAL(n); terminal(n); end + def visit_SYMBOL(n); terminal(n); end + def visit_SLASH(n); terminal(n); end + def visit_DOT(n); terminal(n); end + + private_instance_methods(false).each do |pim| + next unless pim =~ /^visit_(.*)$/ + DISPATCH_CACHE[$1.to_sym] = pim + end + end + + class FormatBuilder < Visitor # :nodoc: + def accept(node); Journey::Format.new(super); end + def terminal(node); [node.left]; end + + def binary(node) + visit(node.left) + visit(node.right) + end + + def visit_GROUP(n); [Journey::Format.new(unary(n))]; end + + def visit_STAR(n) + [Journey::Format.required_path(n.left.to_sym)] + end + + def visit_SYMBOL(n) + symbol = n.to_sym + if symbol == :controller + [Journey::Format.required_path(symbol)] + else + [Journey::Format.required_segment(symbol)] + end + end + end + + # Loop through the requirements AST + class Each < Visitor # :nodoc: + attr_reader :block + + def initialize(block) + @block = block + end + + def visit(node) + block.call(node) + super + end + end + + class String < Visitor # :nodoc: + private + + def binary(node) + [visit(node.left), visit(node.right)].join + end + + def nary(node) + node.children.map { |c| visit(c) }.join '|' + end + + def terminal(node) + node.left + end + + def visit_GROUP(node) + "(#{visit(node.left)})" + end + end + + class Dot < Visitor # :nodoc: + def initialize + @nodes = [] + @edges = [] + end + + def accept(node) + super + <<-eodot + digraph parse_tree { + size="8,5" + node [shape = none]; + edge [dir = none]; + #{@nodes.join "\n"} + #{@edges.join("\n")} + } + eodot + end + + private + + def binary(node) + node.children.each do |c| + @edges << "#{node.object_id} -> #{c.object_id};" + end + super + end + + def nary(node) + node.children.each do |c| + @edges << "#{node.object_id} -> #{c.object_id};" + end + super + end + + def unary(node) + @edges << "#{node.object_id} -> #{node.left.object_id};" + super + end + + def visit_GROUP(node) + @nodes << "#{node.object_id} [label=\"()\"];" + super + end + + def visit_CAT(node) + @nodes << "#{node.object_id} [label=\"○\"];" + super + end + + def visit_STAR(node) + @nodes << "#{node.object_id} [label=\"*\"];" + super + end + + def visit_OR(node) + @nodes << "#{node.object_id} [label=\"|\"];" + super + end + + def terminal(node) + value = node.left + + @nodes << "#{node.object_id} [label=\"#{value}\"];" + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/visualizer/fsm.css b/actionpack/lib/action_dispatch/journey/visualizer/fsm.css new file mode 100644 index 0000000000..403e16a7bb --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/visualizer/fsm.css @@ -0,0 +1,30 @@ +body { + font-family: "Helvetica Neue", Helvetica, Arial, Sans-Serif; + margin: 0; +} + +h1 { + font-size: 2.0em; font-weight: bold; text-align: center; + color: white; background-color: black; + padding: 5px 0; + margin: 0 0 20px; +} + +h2 { + text-align: center; + display: none; + font-size: 0.5em; +} + +.clearfix {display: inline-block; } +.input { overflow: show;} +.instruction { color: #666; padding: 0 30px 20px; font-size: 0.9em} +.instruction p { padding: 0 0 5px; } +.instruction li { padding: 0 10px 5px; } + +.form { background: #EEE; padding: 20px 30px; border-radius: 5px; margin-left: auto; margin-right: auto; width: 500px; margin-bottom: 20px} +.form p, .form form { text-align: center } +.form form {padding: 0 10px 5px; } +.form .fun_routes { font-size: 0.9em;} +.form .fun_routes a { margin: 0 5px 0 0; } + diff --git a/actionpack/lib/action_dispatch/journey/visualizer/fsm.js b/actionpack/lib/action_dispatch/journey/visualizer/fsm.js new file mode 100644 index 0000000000..d9bcaef928 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/visualizer/fsm.js @@ -0,0 +1,134 @@ +function tokenize(input, callback) { + while(input.length > 0) { + callback(input.match(/^[\/\.\?]|[^\/\.\?]+/)[0]); + input = input.replace(/^[\/\.\?]|[^\/\.\?]+/, ''); + } +} + +var graph = d3.select("#chart-2 svg"); +var svg_edges = {}; +var svg_nodes = {}; + +graph.selectAll("g.edge").each(function() { + var node = d3.select(this); + var index = node.select("title").text().split("->"); + var left = parseInt(index[0]); + var right = parseInt(index[1]); + + if(!svg_edges[left]) { svg_edges[left] = {} } + svg_edges[left][right] = node; +}); + +graph.selectAll("g.node").each(function() { + var node = d3.select(this); + var index = parseInt(node.select("title").text()); + svg_nodes[index] = node; +}); + +function reset_graph() { + for(var key in svg_edges) { + for(var mkey in svg_edges[key]) { + var node = svg_edges[key][mkey]; + var path = node.select("path"); + var arrow = node.select("polygon"); + path.style("stroke", "black"); + arrow.style("stroke", "black").style("fill", "black"); + } + } + + for(var key in svg_nodes) { + var node = svg_nodes[key]; + node.select('ellipse').style("fill", "white"); + node.select('polygon').style("fill", "white"); + } + return false; +} + +function highlight_edge(from, to) { + var node = svg_edges[from][to]; + var path = node.select("path"); + var arrow = node.select("polygon"); + + path + .transition().duration(500) + .style("stroke", "green"); + + arrow + .transition().duration(500) + .style("stroke", "green").style("fill", "green"); +} + +function highlight_state(index, color) { + if(!color) { color = "green"; } + + svg_nodes[index].select('ellipse') + .style("fill", "white") + .transition().duration(500) + .style("fill", color); +} + +function highlight_finish(index) { + svg_nodes[index].select('polygon') + .style("fill", "while") + .transition().duration(500) + .style("fill", "blue"); +} + +function match(input) { + reset_graph(); + var table = tt(); + var states = [0]; + var regexp_states = table['regexp_states']; + var string_states = table['string_states']; + var accepting = table['accepting']; + + highlight_state(0); + + tokenize(input, function(token) { + var new_states = []; + for(var key in states) { + var state = states[key]; + + if(string_states[state] && string_states[state][token]) { + var new_state = string_states[state][token]; + highlight_edge(state, new_state); + highlight_state(new_state); + new_states.push(new_state); + } + + if(regexp_states[state]) { + for(var key in regexp_states[state]) { + var re = new RegExp("^" + key + "$"); + if(re.test(token)) { + var new_state = regexp_states[state][key]; + highlight_edge(state, new_state); + highlight_state(new_state); + new_states.push(new_state); + } + } + } + } + + if(new_states.length == 0) { + return; + } + states = new_states; + }); + + for(var key in states) { + var state = states[key]; + if(accepting[state]) { + for(var mkey in svg_edges[state]) { + if(!regexp_states[mkey] && !string_states[mkey]) { + highlight_edge(state, mkey); + highlight_finish(mkey); + } + } + } else { + highlight_state(state, "red"); + } + } + + return false; +} + diff --git a/actionpack/lib/action_dispatch/journey/visualizer/index.html.erb b/actionpack/lib/action_dispatch/journey/visualizer/index.html.erb new file mode 100644 index 0000000000..9b28a65200 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/visualizer/index.html.erb @@ -0,0 +1,52 @@ +<!DOCTYPE html> +<html> + <head> + <title><%= title %></title> + <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/meyer-reset/2.0/reset.css" type="text/css"> + <style> + <% stylesheets.each do |style| %> + <%= style %> + <% end %> + </style> + <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.8/d3.min.js" type="text/javascript"></script> + </head> + <body> + <div id="wrapper"> + <h1>Routes FSM with NFA simulation</h1> + <div class="instruction form"> + <p> + Type a route in to the box and click "simulate". + </p> + <form onsubmit="return match(this.route.value);"> + <input type="text" size="30" name="route" value="/articles/new" /> + <button>simulate</button> + <input type="reset" value="reset" onclick="return reset_graph();"/> + </form> + <p class="fun_routes"> + Some fun routes to try: + <% fun_routes.each do |path| %> + <a href="#" onclick="document.forms[0].elements[0].value=this.text.replace(/^\s+|\s+$/g,''); return match(this.text.replace(/^\s+|\s+$/g,''));"> + <%= path %> + </a> + <% end %> + </p> + </div> + <div class='chart' id='chart-2'> + <%= svg %> + </div> + <div class="instruction"> + <p> + This is a FSM for a system that has the following routes: + </p> + <ul> + <% paths.each do |route| %> + <li><%= route %></li> + <% end %> + </ul> + </div> + </div> + <% javascripts.each do |js| %> + <script><%= js %></script> + <% end %> + </body> +</html> |