diff options
Diffstat (limited to 'actionpack/lib/action_dispatch/journey/gtg')
3 files changed, 366 insertions, 0 deletions
diff --git a/actionpack/lib/action_dispatch/journey/gtg/builder.rb b/actionpack/lib/action_dispatch/journey/gtg/builder.rb new file mode 100644 index 0000000000..450588cda6 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/builder.rb @@ -0,0 +1,162 @@ +require 'action_dispatch/journey/gtg/transition_table' + +module ActionDispatch + module Journey # :nodoc: + module GTG # :nodoc: + class Builder # :nodoc: + DUMMY = Nodes::Dummy.new + + attr_reader :root, :ast, :endpoints + + def initialize(root) + @root = root + @ast = Nodes::Cat.new root, DUMMY + @followpos = nil + end + + def transition_table + dtrans = TransitionTable.new + marked = {} + state_id = Hash.new { |h,k| h[k] = h.length } + + start = firstpos(root) + dstates = [start] + until dstates.empty? + s = dstates.shift + next if marked[s] + marked[s] = true # mark s + + s.group_by { |state| symbol(state) }.each do |sym, ps| + u = ps.flat_map { |l| followpos(l) } + next if u.empty? + + if u.uniq == [DUMMY] + from = state_id[s] + to = state_id[Object.new] + dtrans[from, to] = sym + + dtrans.add_accepting(to) + ps.each { |state| dtrans.add_memo(to, state.memo) } + else + dtrans[state_id[s], state_id[u]] = sym + + if u.include?(DUMMY) + to = state_id[u] + + accepting = ps.find_all { |l| followpos(l).include?(DUMMY) } + + accepting.each { |accepting_state| + dtrans.add_memo(to, accepting_state.memo) + } + + dtrans.add_accepting(state_id[u]) + end + end + + dstates << u + end + end + + dtrans + end + + def nullable?(node) + case node + when Nodes::Group + true + when Nodes::Star + true + when Nodes::Or + node.children.any? { |c| nullable?(c) } + when Nodes::Cat + nullable?(node.left) && nullable?(node.right) + when Nodes::Terminal + !node.left + when Nodes::Unary + nullable?(node.left) + else + raise ArgumentError, 'unknown nullable: %s' % node.class.name + end + end + + def firstpos(node) + case node + when Nodes::Star + firstpos(node.left) + when Nodes::Cat + if nullable?(node.left) + firstpos(node.left) | firstpos(node.right) + else + firstpos(node.left) + end + when Nodes::Or + node.children.flat_map { |c| firstpos(c) }.uniq + when Nodes::Unary + firstpos(node.left) + when Nodes::Terminal + nullable?(node) ? [] : [node] + else + raise ArgumentError, 'unknown firstpos: %s' % node.class.name + end + end + + def lastpos(node) + case node + when Nodes::Star + firstpos(node.left) + when Nodes::Or + node.children.flat_map { |c| lastpos(c) }.uniq + when Nodes::Cat + if nullable?(node.right) + lastpos(node.left) | lastpos(node.right) + else + lastpos(node.right) + end + when Nodes::Terminal + nullable?(node) ? [] : [node] + when Nodes::Unary + lastpos(node.left) + else + raise ArgumentError, 'unknown lastpos: %s' % node.class.name + end + end + + def followpos(node) + followpos_table[node] + end + + private + + def followpos_table + @followpos ||= build_followpos + end + + def build_followpos + table = Hash.new { |h, k| h[k] = [] } + @ast.each do |n| + case n + when Nodes::Cat + lastpos(n.left).each do |i| + table[i] += firstpos(n.right) + end + when Nodes::Star + lastpos(n).each do |i| + table[i] += firstpos(n) + end + end + end + table + end + + def symbol(edge) + case edge + when Journey::Nodes::Symbol + edge.regexp + else + edge.left + end + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/gtg/simulator.rb b/actionpack/lib/action_dispatch/journey/gtg/simulator.rb new file mode 100644 index 0000000000..94b0a24344 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/simulator.rb @@ -0,0 +1,47 @@ +require 'strscan' + +module ActionDispatch + module Journey # :nodoc: + module GTG # :nodoc: + class MatchData # :nodoc: + attr_reader :memos + + def initialize(memos) + @memos = memos + end + end + + class Simulator # :nodoc: + attr_reader :tt + + def initialize(transition_table) + @tt = transition_table + end + + def simulate(string) + ms = memos(string) { return } + MatchData.new(ms) + end + + alias :=~ :simulate + alias :match :simulate + + def memos(string) + input = StringScanner.new(string) + state = [0] + while sym = input.scan(%r([/.?]|[^/.?]+)) + state = tt.move(state, sym) + end + + acceptance_states = state.find_all { |s| + tt.accepting? s + } + + return yield if acceptance_states.empty? + + acceptance_states.flat_map { |x| tt.memo(x) }.compact + end + end + end + end +end diff --git a/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb b/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb new file mode 100644 index 0000000000..1b914f0637 --- /dev/null +++ b/actionpack/lib/action_dispatch/journey/gtg/transition_table.rb @@ -0,0 +1,157 @@ +require 'action_dispatch/journey/nfa/dot' + +module ActionDispatch + module Journey # :nodoc: + module GTG # :nodoc: + class TransitionTable # :nodoc: + include Journey::NFA::Dot + + attr_reader :memos + + def initialize + @regexp_states = {} + @string_states = {} + @accepting = {} + @memos = Hash.new { |h,k| h[k] = [] } + end + + def add_accepting(state) + @accepting[state] = true + end + + def accepting_states + @accepting.keys + end + + def accepting?(state) + @accepting[state] + end + + def add_memo(idx, memo) + @memos[idx] << memo + end + + def memo(idx) + @memos[idx] + end + + def eclosure(t) + Array(t) + end + + def move(t, a) + return [] if t.empty? + + regexps = [] + + t.map { |s| + if states = @regexp_states[s] + regexps.concat states.map { |re, v| re === a ? v : nil } + end + + if states = @string_states[s] + states[a] + end + }.compact.concat regexps + end + + def as_json(options = nil) + simple_regexp = Hash.new { |h,k| h[k] = {} } + + @regexp_states.each do |from, hash| + hash.each do |re, to| + simple_regexp[from][re.source] = to + end + end + + { + regexp_states: simple_regexp, + string_states: @string_states, + accepting: @accepting + } + end + + def to_svg + svg = IO.popen('dot -Tsvg', 'w+') { |f| + f.write(to_dot) + f.close_write + f.readlines + } + 3.times { svg.shift } + svg.join.sub(/width="[^"]*"/, '').sub(/height="[^"]*"/, '') + end + + def visualizer(paths, title = 'FSM') + viz_dir = File.join File.dirname(__FILE__), '..', 'visualizer' + fsm_js = File.read File.join(viz_dir, 'fsm.js') + fsm_css = File.read File.join(viz_dir, 'fsm.css') + erb = File.read File.join(viz_dir, 'index.html.erb') + states = "function tt() { return #{to_json}; }" + + fun_routes = paths.sample(3).map do |ast| + ast.map { |n| + case n + when Nodes::Symbol + case n.left + when ':id' then rand(100).to_s + when ':format' then %w{ xml json }.sample + else + 'omg' + end + when Nodes::Terminal then n.symbol + else + nil + end + }.compact.join + end + + stylesheets = [fsm_css] + svg = to_svg + javascripts = [states, fsm_js] + + # Annoying hack for 1.9 warnings + fun_routes = fun_routes + stylesheets = stylesheets + svg = svg + javascripts = javascripts + + require 'erb' + template = ERB.new erb + template.result(binding) + end + + def []=(from, to, sym) + to_mappings = states_hash_for(sym)[from] ||= {} + to_mappings[sym] = to + end + + def states + ss = @string_states.keys + @string_states.values.flat_map(&:values) + rs = @regexp_states.keys + @regexp_states.values.flat_map(&:values) + (ss + rs).uniq + end + + def transitions + @string_states.flat_map { |from, hash| + hash.map { |s, to| [from, s, to] } + } + @regexp_states.flat_map { |from, hash| + hash.map { |s, to| [from, s, to] } + } + end + + private + + def states_hash_for(sym) + case sym + when String + @string_states + when Regexp + @regexp_states + else + raise ArgumentError, 'unknown symbol: %s' % sym.class + end + end + end + end + end +end |