Class: ActionDispatch::Journey::NFA::TransitionTable

Inherits:
Object
  • Object
show all
Includes:
Dot
Defined in:
actionpack/lib/action_dispatch/journey/nfa/transition_table.rb

Overview

:nodoc:

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Dot

#to_dot

Constructor Details

#initializeTransitionTable

Returns a new instance of TransitionTable.


12
13
14
15
16
17
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 12

def initialize
  @table     = Hash.new { |h,f| h[f] = {} }
  @memos     = {}
  @accepting = nil
  @inverted  = nil
end

Instance Attribute Details

#acceptingObject

Returns the value of attribute accepting


9
10
11
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 9

def accepting
  @accepting
end

#memosObject (readonly)

Returns the value of attribute memos


10
11
12
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 10

def memos
  @memos
end

Instance Method Details

#[]=(i, f, s) ⇒ Object


35
36
37
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 35

def []=(i, f, s)
  @table[f][i] = s
end

#accepting?(state) ⇒ Boolean

Returns:

  • (Boolean)

19
20
21
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 19

def accepting?(state)
  accepting == state
end

#accepting_statesObject


23
24
25
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 23

def accepting_states
  [accepting]
end

#add_memo(idx, memo) ⇒ Object


27
28
29
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 27

def add_memo(idx, memo)
  @memos[idx] = memo
end

#alphabetObject


64
65
66
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 64

def alphabet
  inverted.values.flat_map(&:keys).compact.uniq.sort_by(&:to_s)
end

#eclosure(t) ⇒ Object

Returns a set of NFA states reachable from some NFA state s in set t on nil-transitions alone.


70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 70

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

#following_states(t, a) ⇒ Object

Returns set of NFA states to which there is a transition on ast symbol a from some state s in t.


50
51
52
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 50

def following_states(t, a)
  Array(t).flat_map { |s| inverted[s][a] }.uniq
end

#memo(idx) ⇒ Object


31
32
33
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 31

def memo(idx)
  @memos[idx]
end

#merge(left, right) ⇒ Object


39
40
41
42
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 39

def merge(left, right)
  @memos[right] = @memos.delete(left)
  @table[right] = @table.delete(left)
end

#move(t, a) ⇒ Object

Returns set of NFA states to which there is a transition on ast symbol a from some state s in t.


56
57
58
59
60
61
62
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 56

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

#statesObject


44
45
46
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 44

def states
  (@table.keys + @table.values.flat_map(&:keys)).uniq
end

#transitionsObject


88
89
90
91
92
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 88

def transitions
  @table.flat_map { |to, hash|
    hash.map { |from, sym| [from, sym, to] }
  }
end