aboutsummaryrefslogtreecommitdiffstats
path: root/actionpack/lib/action_dispatch/journey/nfa/builder.rb
blob: d22302e101a079a19d63f6b2ec236546d6f0abed (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
# 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