Class: ActionDispatch::Journey::GTG::Builder

Inherits:
Object
  • Object
show all
Defined in:
lib/action_dispatch/journey/gtg/builder.rb

Overview

:nodoc:

Constant Summary collapse

DUMMY_END_NODE = 
Nodes::Dummy.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root) ⇒ Builder

Returns a new instance of Builder.



15
16
17
18
19
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 15

def initialize(root)
  @root      = root
  @ast       = Nodes::Cat.new root, DUMMY_END_NODE
  @followpos = build_followpos
end

Instance Attribute Details

#ast ⇒ Object (readonly)

Returns the value of attribute ast.



13
14
15
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 13

def ast
  @ast
end

#endpoints ⇒ Object (readonly)

Returns the value of attribute endpoints.



13
14
15
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 13

def endpoints
  @endpoints
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



13
14
15
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 13

def root
  @root
end

Instance Method Details

#firstpos(node) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 87

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) }.tap(&:uniq!)
  when Nodes::Unary
    firstpos(node.left)
  when Nodes::Terminal
    nullable?(node) ? [] : [node]
  else
    raise ArgumentError, "unknown firstpos: %s" % node.class.name
  end
end

#lastpos(node) ⇒ Object 



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 108

def lastpos(node)
  case node
  when Nodes::Star
    lastpos(node.left)
  when Nodes::Or
    node.children.flat_map { |c| lastpos(c) }.tap(&: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

#nullable?(node) ⇒ Boolean

Returns:

  • (Boolean) 


66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 66

def nullable?(node)
  case node
  when Nodes::Group
    true
  when Nodes::Star
    # the default star regex is /(.+)/ which is NOT nullable but since different
    # constraints can be provided we must actually check if this is the case or not.
    node.regexp.match?("")
  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

#transition_table ⇒ Object 



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
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 21

def transition_table
  dtrans   = TransitionTable.new
  marked   = {}.compare_by_identity
  state_id = Hash.new { |h, k| h[k] = h.length }.compare_by_identity
  dstates  = [firstpos(root)]

  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] }.uniq
      next if u.empty?

      from = state_id[s]

      if u.all? { |pos| pos == DUMMY_END_NODE }
        to = state_id[Object.new]
        dtrans[from, to] = sym
        dtrans.add_accepting(to)

        ps.each { |state| dtrans.add_memo(to, state.memo) }
      else
        to = state_id[u]
        dtrans[from, to] = sym

        if u.include?(DUMMY_END_NODE)
          ps.each do |state|
            if @followpos[state].include?(DUMMY_END_NODE)
              dtrans.add_memo(to, state.memo)
            end
          end

          dtrans.add_accepting(to)
        end
      end

      dstates << u
    end
  end

  dtrans
end