Module: Flexr::Automaton::Analysis

Defined in:
lib/flexr/automaton/analysis.rb

Class Method Summary collapse

Class Method Details

.accepting?(dfa, state) ⇒ Boolean

Returns:

  • (Boolean) 


74
75
76
 
# File 'lib/flexr/automaton/analysis.rb', line 74

def accepting?(dfa, state)
  state && !dfa.accepts.fetch(state).empty?
end

.dead_states(dfa) ⇒ Object 



31
32
33
34
35
 
# File 'lib/flexr/automaton/analysis.rb', line 31

def dead_states(dfa)
  dfa.transitions.each_index.select do |state|
    dfa.accepts[state].empty? && dfa.transitions[state].compact.all? { |destination| destination == state }
  end
end

.firstmatch_counterexample(first, second) ⇒ Object 



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
 
# File 'lib/flexr/automaton/analysis.rb', line 37

def firstmatch_counterexample(first, second)
  queue = [[first.start, second.start, false, +"".b]]
  visited = { [first.start, second.start, false] => true }
  bytes = joint_byte_representatives(first, second)
  cursor = 0

  while cursor < queue.length
    first_state, second_state, first_seen, input = queue.fetch(cursor)
    cursor += 1
    bytes.each do |byte|
      next_first = first_state && first.transition(first_state, byte)
      next_second = second_state && second.transition(second_state, byte)
      next unless next_second

      next_input = input + byte.chr(Encoding::BINARY)
      next_first_seen = first_seen || accepting?(first, next_first)
      return next_input if next_first_seen && accepting?(second, next_second) && !accepting?(first, next_first)

      key = [next_first, next_second, next_first_seen]
      next if visited[key]

      visited[key] = true
      queue << [next_first, next_second, next_first_seen, next_input]
    end
  end
  nil
end

.joint_byte_representatives(first, second) ⇒ Object 



65
66
67
68
69
70
71
72
 
# File 'lib/flexr/automaton/analysis.rb', line 65

def joint_byte_representatives(first, second)
  representatives = {}
  256.times do |byte|
    key = [first.ec[byte], second.ec[byte]]
    representatives[key] ||= byte
  end
  representatives.values.sort_by { |byte| [byte.between?(32, 126) ? 0 : 1, byte] }
end

.needs_backup?(dfa) ⇒ Boolean

Returns:

  • (Boolean) 


13
14
15
16
17
18
19
 
# File 'lib/flexr/automaton/analysis.rb', line 13

def needs_backup?(dfa)
  dfa.transitions.each_index.any? do |state|
    next false if dfa.accepts[state].empty?

    dfa.transitions[state].compact.any? { |destination| dfa.accepts[destination].empty? }
  end
end

.self_loop_set(dfa, state) ⇒ Object 



21
22
23
24
25
26
27
28
29
 
# File 'lib/flexr/automaton/analysis.rb', line 21

def self_loop_set(dfa, state)
  representatives = Array.new(dfa.class_count)
  dfa.ec.each_with_index { |class_id, byte| representatives[class_id] ||= byte }
  self_loops = representatives.each_index.map do |class_id|
    byte = representatives.fetch(class_id)
    byte && dfa.transition(state, byte) == state
  end
  dfa.ec.each_index.select { |byte| self_loops.fetch(dfa.ec.fetch(byte)) }
end

.unreachable_rules(compiled) ⇒ Object 



8
9
10
11
 
# File 'lib/flexr/automaton/analysis.rb', line 8

def unreachable_rules(compiled)
  present = compiled.machines.values.flat_map { |machine| machine.dfa.rule_ids }.uniq
  compiled.rules.reject { |rule| present.include?(rule.index) }
end