diff options
Diffstat (limited to 'actionpack/lib/action_dispatch/journey')
22 files changed, 2547 insertions, 0 deletions
diff --git a/actionpack/lib/action_dispatch/journey/formatter.rb b/actionpack/lib/action_dispatch/journey/formatter.rb new file mode 100644 index 0000000000..52396ec901 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/formatter.rb @@ -0,0 +1,189 @@ +# frozen_string_literal: true + +require "action_controller/metal/exceptions" + +module ActionDispatch + # :stopdoc: + 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(name, options, path_parameters, parameterize = nil) + constraints = path_parameters.merge(options) + missing_keys = nil + + 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 if missing_keys && !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 + + route.parts.reverse_each do |key| + break if defaults[key].nil? && parameterized_parts[key].present? + next if parameterized_parts[key].to_s != defaults[key].to_s + break if required_parts.include?(key) + + parameterized_parts.delete(key) + end + + return [route.format(parameterized_parts), params] + end + + unmatched_keys = (missing_keys || []) & constraints.keys + missing_keys = (missing_keys || []) - unmatched_keys + + message = +"No route matches #{Hash[constraints.sort_by { |k, v| k.to_s }].inspect}" + message << ", missing required keys: #{missing_keys.sort.inspect}" if missing_keys && !missing_keys.empty? + message << ", possible unmatched constraints: #{unmatched_keys.sort.inspect}" if unmatched_keys && !unmatched_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_each.drop_while { |part| + !options.key?(part) || (options[part] || recall[part]).nil? + } | route.required_parts + + parameterized_parts.delete_if do |bad_key, _| + !keys_to_keep.include?(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 + routes = non_recursive(cache, options) + + supplied_keys = options.each_with_object({}) do |(k, v), h| + h[k.to_s] = true if v + end + + hash = routes.group_by { |_, r| r.score(supplied_keys) } + + hash.keys.sort.reverse_each do |score| + break if score < 0 + + hash[score].sort_by { |i, _| i }.each do |_, route| + 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 + + module RegexCaseComparator + DEFAULT_INPUT = /[-_.a-zA-Z0-9]+\/[-_.a-zA-Z0-9]+/ + DEFAULT_REGEX = /\A#{DEFAULT_INPUT}\Z/ + + def self.===(regex) + DEFAULT_INPUT == regex + end + end + + # Returns an array populated with missing keys if any are present. + def missing_keys(route, parts) + missing_keys = nil + tests = route.path.requirements + route.required_parts.each { |key| + case tests[key] + when nil + unless parts[key] + missing_keys ||= [] + missing_keys << key + end + when RegexCaseComparator + unless RegexCaseComparator::DEFAULT_REGEX === parts[key] + missing_keys ||= [] + missing_keys << key + end + else + unless /\A#{tests[key]}\Z/ === parts[key] + missing_keys ||= [] + missing_keys << key + end + 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.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 + # :startdoc: +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..44c31053cb --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/builder.rb @@ -0,0 +1,164 @@ +# frozen_string_literal: true + +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..2ee4f5c30c --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/simulator.rb @@ -0,0 +1,41 @@ +# frozen_string_literal: true + +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 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..ea647e051a --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb @@ -0,0 +1,158 @@ +# frozen_string_literal: true + +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 __dir__, "..", "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] + + 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..d22302e101 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/builder.rb @@ -0,0 +1,78 @@ +# frozen_string_literal: true + +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..56e9e3c83d --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/dot.rb @@ -0,0 +1,36 @@ +# frozen_string_literal: true + +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..002f6feb97 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/simulator.rb @@ -0,0 +1,47 @@ +# frozen_string_literal: true + +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([/.?]|[^/.?]+)) + 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..fe55861507 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb @@ -0,0 +1,120 @@ +# frozen_string_literal: true + +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 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..086d6a3e07 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/nodes/node.rb @@ -0,0 +1,141 @@ +# frozen_string_literal: true + +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::INSTANCE.accept(self, block) + end + + def to_s + Visitors::String::INSTANCE.accept(self, "") + end + + def to_dot + Visitors::Dot::INSTANCE.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 + def terminal?; false; end + def star?; false; end + def cat?; false; end + def group?; false; end + end + + class Terminal < Node # :nodoc: + alias :symbol :left + def terminal?; true; end + 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 + + class Slash < Terminal # :nodoc: + def type; :SLASH; end + end + + class Dot < Terminal # :nodoc: + def type; :DOT; end + end + + class Symbol < Terminal # :nodoc: + attr_accessor :regexp + alias :symbol :regexp + attr_reader :name + + DEFAULT_EXP = /[^\.\/\?]+/ + def initialize(left) + super + @regexp = DEFAULT_EXP + @name = -left.tr("*:", "") + end + + def default_regexp? + regexp == DEFAULT_EXP + end + + def type; :SYMBOL; end + def symbol?; true; end + end + + class Unary < Node # :nodoc: + def children; [left] end + end + + class Group < Unary # :nodoc: + def type; :GROUP; end + def group?; true; end + end + + class Star < Unary # :nodoc: + def star?; true; end + 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 cat?; true; end + 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..e002755bcf --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/parser.rb @@ -0,0 +1,199 @@ +# +# DO NOT MODIFY!!!! +# This file is automatically generated by Racc 1.4.14 +# from Racc grammar file "". +# + +require 'racc/parser.rb' + +# :stopdoc: + +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, 19, 16, 8, 19, 13, 15, + 14, 7, 17, 16, 8, 13, 15, 14, 7, 21, + 16, 8, 13, 15, 14, 7, 24, 16, 8 ] + +racc_action_check = [ + 2, 2, 2, 2, 22, 2, 2, 2, 19, 19, + 19, 19, 1, 19, 19, 7, 7, 7, 7, 17, + 7, 7, 0, 0, 0, 0, 20, 0, 0 ] + +racc_action_pointer = [ + 20, 12, -2, nil, nil, nil, nil, 13, nil, nil, + nil, nil, nil, nil, nil, nil, nil, 19, nil, 6, + 20, nil, -5, 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(val.first) +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..f9b1a7a958 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/parser.y @@ -0,0 +1,50 @@ +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(val.first) } + ; + symbol + : SYMBOL { Symbol.new(val.first) } + ; + literal + : LITERAL { Literal.new(val.first) } + ; + dot + : DOT { Dot.new(val.first) } + ; + +end + +---- header +# :stopdoc: + +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..18ec6c9b9b --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/parser_extras.rb @@ -0,0 +1,31 @@ +# frozen_string_literal: true + +require "action_dispatch/journey/scanner" +require "action_dispatch/journey/nodes/node" + +module ActionDispatch + # :stopdoc: + module Journey + class Parser < Racc::Parser + include Journey::Nodes + + def self.parse(string) + new.parse string + end + + 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 + # :startdoc: +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..537f479ee5 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/path/pattern.rb @@ -0,0 +1,198 @@ +# frozen_string_literal: true + +module ActionDispatch + module Journey # :nodoc: + module Path # :nodoc: + class Pattern # :nodoc: + attr_reader :spec, :requirements, :anchored + + def self.from_string(string) + build(string, {}, "/.?", true) + end + + def self.build(path, requirements, separators, anchored) + parser = Journey::Parser.new + ast = parser.parse path + new ast, requirements, separators, anchored + end + + def initialize(ast, requirements, separators, anchored) + @spec = ast + @requirements = requirements + @separators = separators + @anchored = anchored + + @names = nil + @optional_names = nil + @required_names = nil + @re = nil + @offsets = nil + end + + def build_formatter + Visitors::FormatBuilder.new.accept(spec) + end + + def eager_load! + required_names + offsets + to_regexp + nil + end + + def ast + @spec.find_all(&:symbol?).each do |node| + re = @requirements[node.to_sym] + node.regexp = re if re + end + + @spec.find_all(&:star?).each do |node| + node = node.left + node.regexp = @requirements[node.to_sym] || /(.+)/ + end + + @spec + end + + def names + @names ||= spec.find_all(&:symbol?).map(&:name) + end + + def required_names + @required_names ||= names - optional_names + end + + def optional_names + @optional_names ||= spec.find_all(&:group?).flat_map { |group| + group.find_all(&:symbol?) + }.map(&:name).uniq + 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] + "(#{Regexp.union(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 + Array.new(length - 1) { |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 + + @offsets = [0] + + spec.find_all(&:symbol?).each do |node| + node = node.to_sym + + if @requirements.key?(node) + re = /#{Regexp.union(@requirements[node])}|/ + @offsets.push((re.match("").length - 1) + @offsets.last) + else + @offsets << @offsets.last + end + end + + @offsets + 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..8165709a3d --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/route.rb @@ -0,0 +1,203 @@ +# frozen_string_literal: true + +module ActionDispatch + # :stopdoc: + module Journey + class Route + attr_reader :app, :path, :defaults, :name, :precedence + + attr_reader :constraints, :internal + alias :conditions :constraints + + module VerbMatchers + VERBS = %w{ DELETE GET HEAD OPTIONS LINK PATCH POST PUT TRACE UNLINK } + VERBS.each do |v| + class_eval <<-eoc, __FILE__, __LINE__ + 1 + class #{v} + def self.verb; name.split("::").last; end + def self.call(req); req.#{v.downcase}?; end + end + eoc + end + + class Unknown + attr_reader :verb + + def initialize(verb) + @verb = verb + end + + def call(request); @verb === request.request_method; end + end + + class All + def self.call(_); true; end + def self.verb; ""; end + end + + VERB_TO_CLASS = VERBS.each_with_object(all: All) do |verb, hash| + klass = const_get verb + hash[verb] = klass + hash[verb.downcase] = klass + hash[verb.downcase.to_sym] = klass + end + end + + def self.verb_matcher(verb) + VerbMatchers::VERB_TO_CLASS.fetch(verb) do + VerbMatchers::Unknown.new verb.to_s.dasherize.upcase + end + end + + def self.build(name, app, path, constraints, required_defaults, defaults) + request_method_match = verb_matcher(constraints.delete(:request_method)) + new name, app, path, constraints, required_defaults, defaults, request_method_match, 0 + end + + ## + # +path+ is a path constraint. + # +constraints+ is a hash of constraints to be applied to this route. + def initialize(name, app, path, constraints, required_defaults, defaults, request_method_match, precedence, internal = false) + @name = name + @app = app + @path = path + + @request_method_match = request_method_match + @constraints = constraints + @defaults = defaults + @required_defaults = nil + @_required_defaults = required_defaults + @required_parts = nil + @parts = nil + @decorated_ast = nil + @precedence = precedence + @path_formatter = @path.build_formatter + @internal = internal + end + + def eager_load! + path.eager_load! + ast + parts + required_defaults + nil + end + + def ast + @decorated_ast ||= begin + decorated_ast = path.ast + decorated_ast.find_all(&:terminal?).each { |n| n.memo = self } + decorated_ast + end + end + + # Needed for `rails routes`. Picks up succinctly defined requirements + # for a route, for example route + # + # get 'photo/:id', :controller => 'photos', :action => 'show', + # :id => /[A-Z]\d{5}/ + # + # will have {:controller=>"photos", :action=>"show", :id=>/[A-Z]\d{5}/} + # as requirements. + def requirements + @defaults.merge(path.requirements).delete_if { |_, v| + /.+?/ == v + } + end + + def segments + path.names + end + + def required_keys + required_parts + required_defaults.keys + end + + def score(supplied_keys) + required_keys = path.required_names + + required_keys.each do |k| + return -1 unless supplied_keys.include?(k) + end + + score = 0 + path.names.each do |k| + score += 1 if supplied_keys.include?(k) + end + + 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 required_parts + @required_parts ||= path.required_names.map(&:to_sym) + end + + def required_default?(key) + @_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) + match_verb(request) && + constraints.all? { |method, value| + 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 + + def ip + constraints[:ip] || // + end + + def requires_matching_verb? + !@request_method_match.all? { |x| x == VerbMatchers::All } + end + + def verb + verbs.join("|") + end + + private + def verbs + @request_method_match.map(&:verb) + end + + def match_verb(request) + @request_method_match.any? { |m| m.call request } + end + end + end + # :startdoc: +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..89a164f968 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/router.rb @@ -0,0 +1,153 @@ +# frozen_string_literal: true + +require "action_dispatch/journey/router/utils" +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: + attr_accessor :routes + + def initialize(routes) + @routes = routes + end + + def eager_load! + # Eagerly trigger the simulator's initialization so + # it doesn't happen during a request cycle. + simulator + nil + 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 + + parameters = route.defaults.merge parameters.transform_values { |val| + val.dup.force_encoding(::Encoding::UTF_8) + } + + 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 + + [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 + + parameters = route.defaults.merge parameters + 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.partition { |r| + r.path.anchored && r.ast.grep(Nodes::Symbol).all? { |n| n.default_regexp? } + } + end + + def ast + routes.ast + end + + def simulator + routes.simulator + end + + def custom_routes + routes.custom_routes + 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.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 = {} + 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) + verb_specific_routes = routes.select(&:requires_matching_verb?) + head_routes = match_routes(verb_specific_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/utils.rb b/actionpack/lib/action_dispatch/journey/router/utils.rb new file mode 100644 index 0000000000..3c8b9a6eaa --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/router/utils.rb @@ -0,0 +1,102 @@ +# frozen_string_literal: true + +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 ||= "" + encoding = path.encoding + path = +"/#{path}" + path.squeeze!("/") + path.sub!(%r{/+\Z}, "") + path.gsub!(/(%[a-f0-9]{2})/) { $1.upcase } + path = +"/" if path == "" + path.force_encoding(encoding) + path + end + + # URI path and fragment escaping + # https://tools.ietf.org/html/rfc3986 + class UriEncoder # :nodoc: + ENCODE = "%%%02X" + 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" + DIGIT = "0-9" + UNRESERVED = "#{ALPHA}#{DIGIT}\\-\\._~" + SUB_DELIMS = "!\\$&'\\(\\)\\*\\+,;=" + + 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) { |match| [match[1, 2].hex].pack("C") }.force_encoding(encoding) + end + + private + 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 + + # Replaces any escaped sequences with their unescaped representations. + # + # uri = "/topics?title=Ruby%20on%20Rails" + # unescape_uri(uri) #=> "/topics?title=Ruby on Rails" + 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..c0377459d5 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/routes.rb @@ -0,0 +1,82 @@ +# frozen_string_literal: true + +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, :custom_routes, :anchored_routes + + def initialize + @routes = [] + @ast = nil + @anchored_routes = [] + @custom_routes = [] + @simulator = nil + end + + def empty? + routes.empty? + 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 + anchored_routes.clear + custom_routes.clear + end + + def partition_route(route) + if route.path.anchored && route.ast.grep(Nodes::Symbol).all?(&:default_regexp?) + anchored_routes << route + else + custom_routes << route + end + end + + def ast + @ast ||= begin + asts = anchored_routes.map(&:ast) + Nodes::Or.new(asts) + end + end + + def simulator + return if ast.nil? + @simulator ||= begin + gtg = GTG::Builder.new(ast).transition_table + GTG::Simulator.new(gtg) + end + end + + def add_route(name, mapping) + route = mapping.make_route name, routes.length + routes << route + partition_route(route) + clear_cache! + route + end + + private + + def clear_cache! + @ast = 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..2a075862e9 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/scanner.rb @@ -0,0 +1,71 @@ +# frozen_string_literal: true + +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 + + # takes advantage of String @- deduping capabilities in Ruby 2.5 upwards + # see: https://bugs.ruby-lang.org/issues/13077 + def dedup_scan(regex) + r = @ss.scan(regex) + r ? -r : nil + end + + def scan + case + # / + when @ss.skip(/\//) + [:SLASH, "/"] + when @ss.skip(/\(/) + [:LPAREN, "("] + when @ss.skip(/\)/) + [:RPAREN, ")"] + when @ss.skip(/\|/) + [:OR, "|"] + when @ss.skip(/\./) + [:DOT, "."] + when text = dedup_scan(/:\w+/) + [:SYMBOL, text] + when text = dedup_scan(/\*\w+/) + [:STAR, text] + when text = @ss.scan(/(?:[\w%\-~!$&'*+,;=@]|\\[:()])+/) + text.tr! "\\", "" + [:LITERAL, -text] + # any char + when text = dedup_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..d2619cbf3a --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/visitors.rb @@ -0,0 +1,268 @@ +# frozen_string_literal: true + +module ActionDispatch + # :stopdoc: + module Journey + class Format + ESCAPE_PATH = ->(value) { Router::Utils.escape_path(value) } + ESCAPE_SEGMENT = ->(value) { Router::Utils.escape_segment(value) } + + Parameter = Struct.new(:name, :escaper) do + 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 "" 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 FunctionalVisitor # :nodoc: + DISPATCH_CACHE = {} + + def accept(node, seed) + visit(node, seed) + end + + def visit(node, seed) + send(DISPATCH_CACHE[node.type], node, seed) + end + + def binary(node, seed) + visit(node.right, visit(node.left, seed)) + end + def visit_CAT(n, seed); binary(n, seed); end + + def nary(node, seed) + node.children.inject(seed) { |s, c| visit(c, s) } + end + def visit_OR(n, seed); nary(n, seed); end + + def unary(node, seed) + visit(node.left, seed) + end + def visit_GROUP(n, seed); unary(n, seed); end + def visit_STAR(n, seed); unary(n, seed); end + + def terminal(node, seed); seed; end + def visit_LITERAL(n, seed); terminal(n, seed); end + def visit_SYMBOL(n, seed); terminal(n, seed); end + def visit_SLASH(n, seed); terminal(n, seed); end + def visit_DOT(n, seed); terminal(n, seed); end + + 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 < FunctionalVisitor # :nodoc: + def visit(node, block) + block.call(node) + super + end + + INSTANCE = new + end + + class String < FunctionalVisitor # :nodoc: + private + + def binary(node, seed) + visit(node.right, visit(node.left, seed)) + end + + def nary(node, seed) + last_child = node.children.last + node.children.inject(seed) { |s, c| + string = visit(c, s) + string << "|" unless last_child == c + string + } + end + + def terminal(node, seed) + seed + node.left + end + + def visit_GROUP(node, seed) + visit(node.left, seed.dup << "(") << ")" + end + + INSTANCE = new + end + + class Dot < FunctionalVisitor # :nodoc: + def initialize + @nodes = [] + @edges = [] + end + + def accept(node, seed = [[], []]) + super + nodes, edges = seed + <<-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, seed) + seed.last.concat node.children.map { |c| + "#{node.object_id} -> #{c.object_id};" + } + super + end + + def nary(node, seed) + seed.last.concat node.children.map { |c| + "#{node.object_id} -> #{c.object_id};" + } + super + end + + def unary(node, seed) + seed.last << "#{node.object_id} -> #{node.left.object_id};" + super + end + + def visit_GROUP(node, seed) + seed.first << "#{node.object_id} [label=\"()\"];" + super + end + + def visit_CAT(node, seed) + seed.first << "#{node.object_id} [label=\"○\"];" + super + end + + def visit_STAR(node, seed) + seed.first << "#{node.object_id} [label=\"*\"];" + super + end + + def visit_OR(node, seed) + seed.first << "#{node.object_id} [label=\"|\"];" + super + end + + def terminal(node, seed) + value = node.left + + seed.first << "#{node.object_id} [label=\"#{value}\"];" + seed + end + INSTANCE = new + end + end + end + # :startdoc: +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> |