Permalink
Browse files

Integrate Journey into Action Dispatch

Move the Journey code underneath the ActionDispatch namespace so
that we don't pollute the global namespace with names that may
be used for models.

Fixes rails/journey#49.
  • Loading branch information...
1 parent c2be9b0 commit 81bcfbacc9ae44232056f71843a7e5ec0c599544 @pixeltrix pixeltrix committed Nov 30, 2012
Showing with 3,970 additions and 5 deletions.
  1. +3 −2 Gemfile
  2. +5 −0 actionpack/CHANGELOG.md
  3. +7 −1 actionpack/Rakefile
  4. +0 −1 actionpack/actionpack.gemspec
  5. +1 −0 actionpack/lib/action_dispatch.rb
  6. +5 −0 actionpack/lib/action_dispatch/journey.rb
  7. +5 −0 actionpack/lib/action_dispatch/journey/backwards.rb
  8. +11 −0 actionpack/lib/action_dispatch/journey/core-ext/hash.rb
  9. +147 −0 actionpack/lib/action_dispatch/journey/formatter.rb
  10. +161 −0 actionpack/lib/action_dispatch/journey/gtg/builder.rb
  11. +44 −0 actionpack/lib/action_dispatch/journey/gtg/simulator.rb
  12. +155 −0 actionpack/lib/action_dispatch/journey/gtg/transition_table.rb
  13. +76 −0 actionpack/lib/action_dispatch/journey/nfa/builder.rb
  14. +36 −0 actionpack/lib/action_dispatch/journey/nfa/dot.rb
  15. +47 −0 actionpack/lib/action_dispatch/journey/nfa/simulator.rb
  16. +166 −0 actionpack/lib/action_dispatch/journey/nfa/transition_table.rb
  17. +124 −0 actionpack/lib/action_dispatch/journey/nodes/node.rb
  18. +206 −0 actionpack/lib/action_dispatch/journey/parser.rb
  19. +47 −0 actionpack/lib/action_dispatch/journey/parser.y
  20. +23 −0 actionpack/lib/action_dispatch/journey/parser_extras.rb
  21. +195 −0 actionpack/lib/action_dispatch/journey/path/pattern.rb
  22. +94 −0 actionpack/lib/action_dispatch/journey/route.rb
  23. +168 −0 actionpack/lib/action_dispatch/journey/router.rb
  24. +24 −0 actionpack/lib/action_dispatch/journey/router/strexp.rb
  25. +59 −0 actionpack/lib/action_dispatch/journey/router/utils.rb
  26. +77 −0 actionpack/lib/action_dispatch/journey/routes.rb
  27. +60 −0 actionpack/lib/action_dispatch/journey/scanner.rb
  28. +188 −0 actionpack/lib/action_dispatch/journey/visitors.rb
  29. +34 −0 actionpack/lib/action_dispatch/journey/visualizer/fsm.css
  30. +134 −0 actionpack/lib/action_dispatch/journey/visualizer/fsm.js
  31. +52 −0 actionpack/lib/action_dispatch/journey/visualizer/index.html.erb
  32. +1 −1 actionpack/lib/action_dispatch/routing/route_set.rb
  33. +79 −0 actionpack/test/journey/gtg/builder_test.rb
  34. +115 −0 actionpack/test/journey/gtg/transition_table_test.rb
  35. +98 −0 actionpack/test/journey/nfa/simulator_test.rb
  36. +72 −0 actionpack/test/journey/nfa/transition_table_test.rb
  37. +17 −0 actionpack/test/journey/nodes/symbol_test.rb
  38. +284 −0 actionpack/test/journey/path/pattern_test.rb
  39. +110 −0 actionpack/test/journey/route/definition/parser_test.rb
  40. +56 −0 actionpack/test/journey/route/definition/scanner_test.rb
  41. +103 −0 actionpack/test/journey/route_test.rb
  42. +32 −0 actionpack/test/journey/router/strexp_test.rb
  43. +21 −0 actionpack/test/journey/router/utils_test.rb
  44. +575 −0 actionpack/test/journey/router_test.rb
  45. +53 −0 actionpack/test/journey/routes_test.rb
View
@@ -12,10 +12,11 @@ gem 'jquery-rails', '~> 2.1.4', github: 'rails/jquery-rails'
gem 'turbolinks'
gem 'coffee-rails', github: 'rails/coffee-rails'
-gem 'journey', github: 'rails/journey', branch: 'master'
-
gem 'activerecord-deprecated_finders', github: 'rails/activerecord-deprecated_finders', branch: 'master'
+# Needed for compiling the Journey parser
+gem 'racc', '>=1.4.6'
+
# This needs to be with require false to avoid
# it being automatically loaded by sprockets
gem 'uglifier', require: false
View
@@ -1,5 +1,10 @@
## Rails 4.0.0 (unreleased) ##
+* Integrate the Journey gem into Action Dispatch so that the global namespace
+ is not polluted with names that may be used as models.
+
+ *Andrew White*
+
* Sweepers was extracted from Action Controller as `rails-observers` gem.
*Rafael Mendonça França*
View
@@ -15,7 +15,7 @@ Rake::TestTask.new(:test_action_pack) do |t|
# make sure we include the tests in alphabetical order as on some systems
# this will not happen automatically and the tests (as a whole) will error
- t.test_files = Dir.glob('test/{abstract,controller,dispatch,template,assertions}/**/*_test.rb').sort
+ t.test_files = Dir.glob('test/{abstract,controller,dispatch,template,assertions,journey}/**/*_test.rb').sort
t.warning = true
t.verbose = true
@@ -75,3 +75,9 @@ task :lines do
puts "Total: Lines #{total_lines}, LOC #{total_codelines}"
end
+
+rule '.rb' => '.y' do |t|
+ sh "racc -l -o #{t.name} #{t.source}"
+end
+
+task :compile => 'lib/action_dispatch/journey/parser.rb'
@@ -23,7 +23,6 @@ Gem::Specification.new do |s|
s.add_dependency 'builder', '~> 3.1.0'
s.add_dependency 'rack', '~> 1.4.1'
s.add_dependency 'rack-test', '~> 0.6.1'
- s.add_dependency 'journey', '~> 2.0.0'
s.add_dependency 'erubis', '~> 2.7.0'
s.add_development_dependency 'activemodel', version
@@ -63,6 +63,7 @@ class IllegalStateError < StandardError
autoload :Static
end
+ autoload :Journey
autoload :MiddlewareStack, 'action_dispatch/middleware/stack'
autoload :Routing
@@ -0,0 +1,5 @@
+require 'action_dispatch/journey/router'
+require 'action_dispatch/journey/gtg/builder'
+require 'action_dispatch/journey/gtg/simulator'
+require 'action_dispatch/journey/nfa/builder'
+require 'action_dispatch/journey/nfa/simulator'
@@ -0,0 +1,5 @@
+module Rack
+ Mount = ActionDispatch::Journey::Router
+ Mount::RouteSet = ActionDispatch::Journey::Router
+ Mount::RegexpWithNamedGroups = ActionDispatch::Journey::Path::Pattern
+end
@@ -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:
@@ -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
@@ -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
Oops, something went wrong.

0 comments on commit 81bcfba

Please sign in to comment.