From 56fee39c392788314c44a575b3fd66e16a50c8b5 Mon Sep 17 00:00:00 2001
From: Andrew White <andyw@pixeltrix.co.uk>
Date: Wed, 19 Dec 2012 20:54:47 +0000
Subject: 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.
---
 .../journey/nfa/transition_table.rb                | 166 +++++++++++++++++++++
 1 file changed, 166 insertions(+)
 create mode 100644 actionpack/lib/action_dispatch/journey/nfa/transition_table.rb

(limited to 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb')

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
-- 
cgit v1.2.3