/usr/lib/ruby/vendor_ruby/action_dispatch/journey/nfa/transition_table.rb is in ruby-actionpack 2:4.2.6-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 | 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 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).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 { |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.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
|