aboutsummaryrefslogtreecommitdiffstats
path: root/actionpack/lib/action_dispatch/journey/nfa/transition_table.rb
blob: 543a670da0a67f8a5cb5f5254437577c7740d596 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
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