diff options
Diffstat (limited to 'actionpack/lib/action_dispatch/journey')
25 files changed, 2333 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..33f6976897 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/backwards.rb @@ -0,0 +1,5 @@ +module Rack + Mount = ActionDispatch::Journey::Router + Mount::RouteSet = ActionDispatch::Journey::Router + Mount::RegexpWithNamedGroups = ActionDispatch::Journey::Path::Pattern +end diff --git a/actionpack/lib/action_dispatch/journey/core-ext/hash.rb b/actionpack/lib/action_dispatch/journey/core-ext/hash.rb new file mode 100644 index 0000000000..fad5cdaa63 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/core-ext/hash.rb @@ -0,0 +1,11 @@ +# :stopdoc: +if RUBY_VERSION < '1.9' +class Hash + def keep_if + each do |k,v| + delete(k) unless yield(k,v) + end + end +end +end +# :startdoc: diff --git a/actionpack/lib/action_dispatch/journey/formatter.rb b/actionpack/lib/action_dispatch/journey/formatter.rb new file mode 100644 index 0000000000..873a73baf0 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/formatter.rb @@ -0,0 +1,147 @@ +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 + attr_reader :routes + + def initialize routes + @routes = routes + @cache = nil + end + + def generate type, name, options, recall = {}, parameterize = nil + constraints = recall.merge options + missing_keys = [] + + match_route(name, constraints) do |route| + parameterized_parts = extract_parameterized_parts route, options, recall, parameterize + next if !name && route.requirements.empty? && route.parts.empty? + + 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 + + return [route.format(parameterized_parts), params] + end + + raise Router::RoutingError.new "missing required keys: #{missing_keys}" + end + + def clear + @cache = nil + end + + private + def extract_parameterized_parts route, options, recall, parameterize = nil + constraints = recall.merge options + data = constraints.dup + + keys_to_keep = route.parts.reverse.drop_while { |part| + !options.key?(part) || (options[part] || recall[part]).nil? + } | route.required_parts + + (data.keys - keys_to_keep).each do |bad_key| + data.delete bad_key + end + + parameterized_parts = data.dup + + 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 + #routes = possibles(@cache, options.to_a) + routes = non_recursive(cache, options.to_a) + + hash = routes.group_by { |_, r| + r.score options + } + + hash.keys.sort.reverse_each do |score| + next if score < 0 + + hash[score].sort_by { |i,_| i }.each do |_,route| + yield route + end + end + end + end + + def non_recursive cache, options + routes = [] + stack = [cache] + + while stack.any? + c = stack.shift + routes.concat c[:___routes] if c.key? :___routes + + options.each do |pair| + stack << 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 + }.map { |pair| + possibles(cache[pair], options, depth + 1) + }.flatten(1) + end + + # returns boolean, true if no missing keys are present + def verify_required_parts! route, parts + missing_keys(route, parts).empty? + 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..10b53500fc --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/builder.rb @@ -0,0 +1,161 @@ +require 'action_dispatch/journey/gtg/transition_table' + +module ActionDispatch + module Journey + module GTG + class Builder + DUMMY = Nodes::Dummy.new # :nodoc: + + 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.map { |l| followpos(l) }.flatten + 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.map { |c| firstpos(c) }.flatten.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.map { |c| lastpos(c) }.flatten.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..fda14c8680 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/simulator.rb @@ -0,0 +1,44 @@ +require 'strscan' + +module ActionDispatch + module Journey + module GTG + class MatchData + attr_reader :memos + + def initialize memos + @memos = memos + end + end + + class Simulator + attr_reader :tt + + def initialize transition_table + @tt = transition_table + end + + def simulate 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 if acceptance_states.empty? + + memos = acceptance_states.map { |x| tt.memo x }.flatten.compact + + MatchData.new memos + end + + alias :=~ :simulate + alias :match :simulate + 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..b6812b6475 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb @@ -0,0 +1,155 @@ +require 'action_dispatch/journey/nfa/dot' + +module ActionDispatch + module Journey + module GTG + class TransitionTable + include Journey::NFA::Dot + + attr_reader :memos + + def initialize + @regexp_states = Hash.new { |h,k| h[k] = {} } + @string_states = Hash.new { |h,k| h[k] = {} } + @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 + move_string(t, a).concat move_regexp(t, a) + end + + def to_json + require 'json' + + 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 + + JSON.dump({ + :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.shuffle.first(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 }.shuffle.first + 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 + case sym + when String + @string_states[from][sym] = to + when Regexp + @regexp_states[from][sym] = to + else + raise ArgumentError, 'unknown symbol: %s' % sym.class + end + end + + def states + ss = @string_states.keys + @string_states.values.map(&:values).flatten + rs = @regexp_states.keys + @regexp_states.values.map(&:values).flatten + (ss + rs).uniq + end + + def transitions + @string_states.map { |from, hash| + hash.map { |s, to| [from, s, to] } + }.flatten(1) + @regexp_states.map { |from, hash| + hash.map { |s, to| [from, s, to] } + }.flatten(1) + end + + private + def move_regexp t, a + return [] if t.empty? + + t.map { |s| + @regexp_states[s].map { |re,v| re === a ? v : nil } + }.flatten.compact.uniq + end + + def move_string t, a + return [] if t.empty? + + t.map { |s| @string_states[s][a] }.compact + 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..720820accb --- /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 + module NFA + class Visitor < Visitors::Visitor + 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 + 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..6d2f851c2c --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/dot.rb @@ -0,0 +1,36 @@ +# encoding: utf-8 + +module ActionDispatch + module Journey + module NFA + module Dot + 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.map { |k, memos| + # (memos || []).map { |v| " #{k} -> #{v.object_id};" } + #}.flatten.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..9948213146 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb @@ -0,0 +1,47 @@ +require 'strscan' + +module ActionDispatch + module Journey + module NFA + class MatchData + attr_reader :memos + + def initialize memos + @memos = memos + end + end + + class Simulator + 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.map { |x| tt.memo x }.flatten.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..053ee4351a --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb @@ -0,0 +1,166 @@ +require 'action_dispatch/journey/nfa/dot' + +module ActionDispatch + module Journey + module NFA + class TransitionTable + 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.map(&:keys).flatten).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).map { |s| inverted[s][a] }.flatten.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.map(&:keys).flatten.compact.uniq.sort_by { |x| x.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.map { |to, hash| + hash.map { |from, sym| [from, sym, to] } + }.flatten(1) + 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..16d6cb8f0e --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nodes/node.rb @@ -0,0 +1,124 @@ +require 'action_dispatch/journey/visitors' + +module ActionDispatch + module Journey + module Nodes + 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 + alias :symbol :left + end + + class Literal < Terminal + def literal?; true; end + def type; :LITERAL; end + end + + class Dummy < Literal + 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 + 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 + def children; [left] end + end + + class Group < Unary + def type; :GROUP; end + end + + class Star < Unary + def type; :STAR; end + end + + class Binary < Node + attr_accessor :right + + def initialize left, right + super(left) + @right = right + end + + def children; [left, right] end + end + + class Cat < Binary + def type; :CAT; end + end + + class Or < Node + 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..2489cd61eb --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/parser.rb @@ -0,0 +1,206 @@ +# +# DO NOT MODIFY!!!! +# This file is automatically generated by Racc 1.4.9 +# 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 = [ + 17, 21, 13, 15, 14, 7, nil, 16, 8, 19, + 13, 15, 14, 7, 23, 16, 8, 19, 13, 15, + 14, 7, nil, 16, 8, 13, 15, 14, 7, nil, + 16, 8, 13, 15, 14, 7, nil, 16, 8 ] + +racc_action_check = [ + 1, 17, 1, 1, 1, 1, nil, 1, 1, 1, + 20, 20, 20, 20, 20, 20, 20, 20, 7, 7, + 7, 7, nil, 7, 7, 19, 19, 19, 19, nil, + 19, 19, 0, 0, 0, 0, nil, 0, 0 ] + +racc_action_pointer = [ + 30, 0, nil, nil, nil, nil, nil, 16, nil, nil, + nil, nil, nil, nil, nil, nil, nil, 1, nil, 23, + 8, nil, nil, nil ] + +racc_action_default = [ + -18, -18, -2, -3, -4, -5, -6, -18, -9, -10, + -11, -12, -13, -14, -15, -16, -17, -18, -1, -18, + -18, 24, -8, -7 ] + +racc_goto_table = [ + 18, 1, nil, nil, nil, nil, nil, nil, 20, nil, + nil, nil, nil, nil, nil, nil, nil, nil, 22, 18 ] + +racc_goto_check = [ + 2, 1, nil, nil, nil, nil, nil, nil, 1, nil, + nil, nil, nil, nil, nil, nil, nil, nil, 2, 2 ] + +racc_goto_pointer = [ + nil, 1, -1, nil, 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, + 1, 16, :_reduce_9, + 1, 14, :_reduce_none, + 1, 14, :_reduce_none, + 1, 14, :_reduce_none, + 1, 14, :_reduce_none, + 1, 19, :_reduce_14, + 1, 17, :_reduce_15, + 1, 18, :_reduce_16, + 1, 20, :_reduce_17 ] + +racc_reduce_n = 18 + +racc_shift_n = 24 + +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 = true + +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, result) + result = Cat.new(val.first, val.last) + result +end + +def _reduce_2(val, _values, result) + result = val.first + result +end + +# reduce 3 omitted + +# reduce 4 omitted + +# reduce 5 omitted + +# reduce 6 omitted + +def _reduce_7(val, _values, result) + result = Group.new(val[1]) + result +end + +def _reduce_8(val, _values, result) + result = Or.new([val.first, val.last]) + result +end + +def _reduce_9(val, _values, result) + result = Star.new(Symbol.new(val.last)) + result +end + +# reduce 10 omitted + +# reduce 11 omitted + +# reduce 12 omitted + +# reduce 13 omitted + +def _reduce_14(val, _values, result) + result = Slash.new('/') + result +end + +def _reduce_15(val, _values, result) + result = Symbol.new(val.first) + result +end + +def _reduce_16(val, _values, result) + result = Literal.new(val.first) + result +end + +def _reduce_17(val, _values, result) + result = Dot.new(val.first) + result +end + +def _reduce_none(val, _values, result) + 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..a2e1afed32 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/parser.y @@ -0,0 +1,47 @@ +class ActionDispatch::Journey::Parser + +token SLASH LITERAL SYMBOL LPAREN RPAREN DOT STAR OR + +rule + expressions + : expressions expression { result = Cat.new(val.first, val.last) } + | expression { result = val.first } + | or + ; + expression + : terminal + | group + | star + ; + group + : LPAREN expressions RPAREN { result = Group.new(val[1]) } + ; + or + : expressions OR expression { result = Or.new([val.first, val.last]) } + ; + star + : STAR { result = Star.new(Symbol.new(val.last)) } + ; + terminal + : symbol + | literal + | slash + | dot + ; + slash + : SLASH { result = Slash.new('/') } + ; + symbol + : SYMBOL { result = Symbol.new(val.first) } + ; + literal + : LITERAL { result = Literal.new(val.first) } + dot + : DOT { result = 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..43f9beda12 --- /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 + class Parser < Racc::Parser + 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..e14168aeb2 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/path/pattern.rb @@ -0,0 +1,195 @@ +module ActionDispatch + module Journey + module Path + class Pattern + attr_reader :spec, :requirements, :anchored + + def initialize strexp + parser = Journey::Parser.new + + @anchored = true + + case strexp + when String + @spec = parser.parse strexp + @requirements = {} + @separators = "/.?" + when Router::Strexp + @spec = parser.parse strexp.path + @requirements = strexp.requirements + @separators = strexp.separators.join + @anchored = strexp.anchor + else + raise "wtf bro: #{strexp}" + end + + @names = nil + @optional_names = nil + @required_names = nil + @re = nil + @offsets = nil + 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 { |n| n.name } + end + + def required_names + @required_names ||= names - optional_names + end + + def optional_names + @optional_names ||= spec.grep(Nodes::Group).map { |group| + group.grep(Nodes::Symbol) + }.flatten.map { |n| n.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 + end + + class UnanchoredRegexp < AnchoredRegexp # :nodoc: + def accept node + %r{\A#{visit node}} + end + end + + class MatchData + 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..04d31cb580 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/route.rb @@ -0,0 +1,94 @@ +module ActionDispatch + module Journey + class Route + attr_reader :app, :path, :verb, :defaults, :ip, :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 = {} + constraints = constraints.dup + @name = name + @app = app + @path = path + @verb = constraints[:request_method] || // + @ip = constraints.delete(:ip) || // + + @constraints = constraints + @constraints.keep_if { |_,v| Regexp === v || String === v } + @defaults = defaults + @required_defaults = nil + @required_parts = nil + @parts = nil + @decorated_ast = nil + @precedence = 0 + end + + def ast + return @decorated_ast if @decorated_ast + + @decorated_ast = path.ast + @decorated_ast.grep(Nodes::Terminal).each { |n| n.memo = self } + @decorated_ast + 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 + path.required_names.map { |x| x.to_sym } + 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 { |n| n.to_sym } + end + alias :segment_keys :parts + + def format path_options + path_options.delete_if do |key, value| + value.to_s == defaults[key].to_s && !required_parts.include?(key) + end + + Visitors::Formatter.new(path_options).accept(path.spec) + end + + def optional_parts + path.optional_names.map { |n| n.to_sym } + end + + def required_parts + @required_parts ||= path.required_names.map { |n| n.to_sym } + end + + def required_defaults + @required_defaults ||= begin + matches = parts + @defaults.dup.delete_if { |k,_| matches.include? k } + end + 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..fcf16c1272 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/router.rb @@ -0,0 +1,168 @@ +require 'action_dispatch/journey/core-ext/hash' +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 + class Router + class RoutingError < ::StandardError + end + + VERSION = '2.0.0' + + class NullReq # :nodoc: + attr_reader :env + def initialize env + @env = env + end + + def request_method + env['REQUEST_METHOD'] + end + + def path_info + env['PATH_INFO'] + end + + def ip + env['REMOTE_ADDR'] + end + + def [](k); env[k]; end + end + + attr_reader :request_class, :formatter + attr_accessor :routes + + def initialize routes, options + @options = options + @params_key = options[:parameters_key] + @request_class = options[:request_class] || NullReq + @routes = routes + end + + def call env + env['PATH_INFO'] = Utils.normalize_path env['PATH_INFO'] + + find_routes(env).each do |match, parameters, route| + script_name, path_info, set_params = env.values_at('SCRIPT_NAME', + 'PATH_INFO', + @params_key) + + unless route.path.anchored + env['SCRIPT_NAME'] = (script_name.to_s + match.to_s).chomp('/') + env['PATH_INFO'] = match.post_match + end + + env[@params_key] = (set_params || {}).merge parameters + + status, headers, body = route.app.call(env) + + if 'pass' == headers['X-Cascade'] + env['SCRIPT_NAME'] = script_name + env['PATH_INFO'] = path_info + env[@params_key] = set_params + next + end + + return [status, headers, body] + end + + return [404, {'X-Cascade' => 'pass'}, ['Not Found']] + end + + def recognize req + find_routes(req.env).each do |match, parameters, route| + unless route.path.anchored + req.env['SCRIPT_NAME'] = match.to_s + req.env['PATH_INFO'] = match.post_match.sub(/^([^\/])/, '/\1') + end + + yield(route, nil, parameters) + end + end + + def visualizer + tt = GTG::Builder.new(ast).transition_table + groups = partitioned_routes.first.map(&:ast).group_by { |a| a.to_s } + asts = groups.values.map { |v| v.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 + data = simulator.match(path) + data ? data.memos : [] + end + + def find_routes env + req = request_class.new env + + routes = filter_routes(req.path_info).concat custom_routes.find_all { |r| + r.path.match(req.path_info) + } + routes.concat get_routes_as_head(routes) + + routes.sort_by!(&:precedence).select! { |r| + r.constraints.all? { |k,v| v === req.send(k) } && + r.verb === req.request_method + } + routes.reject! { |r| req.ip && !(r.ip === req.ip) } + + routes.map! { |r| + match_data = r.path.match(req.path_info) + match_names = match_data.names.map { |n| n.to_sym } + match_values = match_data.captures.map { |v| v && Utils.unescape_uri(v) } + info = Hash[match_names.zip(match_values).find_all { |_,y| y }] + + [match_data, r.defaults.merge(info), r] + } + end + + def get_routes_as_head(routes) + precedence = (routes.map(&:precedence).max || 0) + 1 + routes = routes.select { |r| + r.verb === "GET" && !(r.verb === "HEAD") + }.map! { |r| + Route.new(r.name, + r.app, + r.path, + r.conditions.merge(:request_method => "HEAD"), + r.defaults).tap do |route| + route.precedence = r.precedence + precedence + end + } + routes.flatten! + routes + 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..268bb4602f --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/router/strexp.rb @@ -0,0 +1,24 @@ +module ActionDispatch + module Journey + class Router + class Strexp + class << self + alias :compile :new + end + + attr_reader :path, :requirements, :separators, :anchor + + def initialize path, requirements, separators, anchor = true + @path = path + @requirements = requirements + @separators = separators + @anchor = anchor + end + + def names + @path.scan(/:\w+/).map { |s| s.tr(':', '') } + 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..a21b570013 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/router/utils.rb @@ -0,0 +1,59 @@ +require 'uri' + +module ActionDispatch + module Journey + class Router + class Utils + # Normalizes URI path. + # + # Strips off trailing slash and ensures there is a leading slash. + # + # normalize_path("/foo") # => "/foo" + # normalize_path("/foo/") # => "/foo" + # normalize_path("foo") # => "/foo" + # normalize_path("") # => "/" + def self.normalize_path(path) + path = "/#{path}" + path.squeeze!('/') + path.sub!(%r{/+\Z}, '') + path = '/' if path == '' + path + end + + # URI path and fragment escaping + # http://tools.ietf.org/html/rfc3986 + module UriEscape + # Symbol captures can generate multiple path segments, so include /. + reserved_segment = '/' + reserved_fragment = '/?' + reserved_pchar = ':@&=+$,;%' + + safe_pchar = "#{URI::REGEXP::PATTERN::UNRESERVED}#{reserved_pchar}" + safe_segment = "#{safe_pchar}#{reserved_segment}" + safe_fragment = "#{safe_pchar}#{reserved_fragment}" + if RUBY_VERSION >= '1.9' + UNSAFE_SEGMENT = Regexp.new("[^#{safe_segment}]", false).freeze + UNSAFE_FRAGMENT = Regexp.new("[^#{safe_fragment}]", false).freeze + else + UNSAFE_SEGMENT = Regexp.new("[^#{safe_segment}]", false, 'N').freeze + UNSAFE_FRAGMENT = Regexp.new("[^#{safe_fragment}]", false, 'N').freeze + end + end + + Parser = URI.const_defined?(:Parser) ? URI::Parser.new : URI + + def self.escape_path(path) + Parser.escape(path.to_s, UriEscape::UNSAFE_SEGMENT) + end + + def self.escape_fragment(fragment) + Parser.escape(fragment.to_s, UriEscape::UNSAFE_FRAGMENT) + end + + def self.unescape_uri(uri) + Parser.unescape(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..f9c4cdbd4b --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/routes.rb @@ -0,0 +1,77 @@ +module ActionDispatch + module Journey + ### + # The Routing table. Contains all routes for a system. Routes can be + # added to the table by calling Routes#add_route + class Routes + 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 + end + + def partitioned_routes + @partitioned_routes ||= routes.partition { |r| + r.path.anchored && r.ast.grep(Nodes::Symbol).all? { |n| n.default_regexp? } + } + end + + def ast + return @ast if @ast + return if partitioned_routes.first.empty? + + asts = partitioned_routes.first.map { |r| r.ast } + @ast = Nodes::Or.new(asts) + end + + def simulator + return @simulator if @simulator + + gtg = GTG::Builder.new(ast).transition_table + @simulator = GTG::Simulator.new gtg + 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..b45d72668b --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/scanner.rb @@ -0,0 +1,60 @@ +require 'strscan' + +module ActionDispatch + module Journey + class Scanner + 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] + # 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..b3f4796607 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/visitors.rb @@ -0,0 +1,188 @@ +# encoding: utf-8 +module ActionDispatch + module Journey + module Visitors + class Visitor # :nodoc: + DISPATCH_CACHE = Hash.new { |h,k| + h[k] = "visit_#{k}" + } + + 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 + %w{ LITERAL SYMBOL SLASH DOT }.each do |t| + class_eval %{ def visit_#{t}(n); terminal(n); end }, __FILE__, __LINE__ + end + end + + ## + # Loop through the requirements AST + class Each < Visitor # :nodoc: + attr_reader :block + + def initialize block + @block = block + end + + def visit node + super + block.call node + end + end + + class String < Visitor + 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 + + ### + # Used for formatting urls (url_for) + class Formatter < Visitor + attr_reader :options, :consumed + + def initialize options + @options = options + @consumed = {} + end + + private + def visit_GROUP node + if consumed == options + nil + else + route = visit node.left + route.include?("\0") ? nil : route + end + end + + def terminal node + node.left + end + + def binary node + [visit(node.left), visit(node.right)].join + end + + def nary node + node.children.map { |c| visit c }.join + end + + def visit_SYMBOL node + key = node.to_sym + + if value = options[key] + consumed[key] = value + Router::Utils.escape_path(value) + else + "\0" + end + end + end + + class Dot < Visitor + 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..50caebaa18 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/visualizer/fsm.css @@ -0,0 +1,34 @@ +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; +} + +div#chart-2 { + height: 350px; +} + +.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..6aff10956a --- /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://raw.github.com/gist/1706081/af944401f75ea20515a02ddb3fb43d23ecb8c662/reset.css" type="text/css"> + <style> + <% stylesheets.each do |style| %> + <%= style %> + <% end %> + </style> + <script src="https://raw.github.com/gist/1706081/df464722a05c3c2bec450b7b5c8240d9c31fa52d/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> |