Class: Fa::Automaton

Inherits:
FFI::AutoPointer
  • Object
show all
Defined in:
lib/fa.rb

Overview

The class representing a finite automaton. It contains a pointer to a struct fa from libfa and provides Ruby wrappers for the various libfa operations.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(faptr) ⇒ Automaton

Returns a new instance of Automaton.



19
20
21
 
# File 'lib/fa.rb', line 19

def initialize(faptr)
  @faptr = faptr
end

Instance Attribute Details

#faptr ⇒ Object (readonly)

Returns the value of attribute faptr.



17
18
19
 
# File 'lib/fa.rb', line 17

def faptr
  @faptr
end

Class Method Details

.release(faptr) ⇒ Object 



205
206
207
 
# File 'lib/fa.rb', line 205

def self.release(faptr)
  FFI::free(faptr)
end

Instance Method Details

#<=(other) ⇒ Boolean

Returns whether other matches all the strings that self matches. other may match more strings than that.

Parameters:

Returns:

  • (Boolean) 


160
 
# File 'lib/fa.rb', line 160

def <=(other); other.contains(self); end

#==(other) ⇒ Boolean

Returns whether self and other match the same set of strings

Parameters:

Returns:

  • (Boolean) 


140
 
# File 'lib/fa.rb', line 140

def ==(other); equals(other); end

#complement ⇒ Fa::Automaton

Produces the complement of self. self will not be modified. The resulting automaton will match all strings that do not match self.

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



122
123
124
 
# File 'lib/fa.rb', line 122

def complement
  from_ptr( FFI::complement(faptr) )
end

#concat(other) ⇒ Fa::Automaton

Concatenates self with other, corresponding to SO. Neither self nor other will be modified.

Parameters:

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



41
42
43
 
# File 'lib/fa.rb', line 41

def concat(other)
  from_ptr( FFI::concat(faptr, other.faptr) )
end

#contains(other) ⇒ Boolean

Returns whether self matches all the strings that other matches. self may match more strings than that.

Parameters:

Returns:

  • (Boolean)

Raises:



147
148
149
150
151
152
153
 
# File 'lib/fa.rb', line 147

def contains(other)
  # The C function works like fa1 <= fa2, and not how the
  # Ruby nomenclature would suggest it, so swap the arguments
  r = FFI::contains(other.faptr, faptr)
  raise Error if r < 0
  return r == 1
end

#empty? ⇒ Boolean

Returns whether self is the empty automaton, i.e., matches no words at all

Returns:

  • (Boolean) 


178
 
# File 'lib/fa.rb', line 178

def empty?; is_basic(:empty); end

#epsilon? ⇒ Boolean

Returns whether self is the epsilon automaton, i.e., matches only the empty string

Returns:

  • (Boolean) 


183
 
# File 'lib/fa.rb', line 183

def epsilon?; is_basic(:epsilon); end

#equals(other) ⇒ Boolean

Returns whether self and other match the same set of strings

Parameters:

Returns:

  • (Boolean)

Raises:



130
131
132
133
134
 
# File 'lib/fa.rb', line 130

def equals(other)
  r = FFI::equals(faptr, other.faptr)
  raise Error if r < 0
  return r == 1
end

#from_ptr(ptr) ⇒ Object

Raises:



210
211
212
213
 
# File 'lib/fa.rb', line 210

def from_ptr(ptr)
  raise OutOfMemoryError if ptr.null?
  Automaton.new(ptr)
end

#intersect(other) ⇒ Fa::Automaton

Produces the intersection of self and other. Neither self nor other will be modified. The resulting automaton will match all strings that simultaneously match self and other,

Parameters:

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



101
102
103
 
# File 'lib/fa.rb', line 101

def intersect(other)
  from_ptr( FFI::intersect(faptr, other.faptr) )
end

#is_basic(kind) ⇒ Boolean

Returns whether self is the empty, epsilon or total automaton

Parameters:

  • kind (:empty, :epsilon, :total)

Returns:

  • (Boolean) 


166
167
168
169
170
171
172
173
 
# File 'lib/fa.rb', line 166

def is_basic(kind)
  # FFI::is_basic checks if the automaton is structurally the same as
  # +basic+; we just want to check here if they accept the same
  # language. If is_basic fails, we therefore check for equality
  r = FFI::is_basic(faptr, kind)
  return true if r == 1
  return equals(Fa::make_basic(kind))
end

#iter(min, max) ⇒ Fa::Automaton

Produces an iteration of self, corresponding to S{min,max}. self will not be modified.

Parameters:

  • min (Int) —

    the minimum number of matches

  • max (Int) —

    the maximum number of matches, use -1 for an unlimited number of matches

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



63
64
65
 
# File 'lib/fa.rb', line 63

def iter(min, max)
  from_ptr( FFI::iter(faptr, min, max) )
end

#maybe ⇒ Fa::Automaton

Produces an iteration of zero or one self, corresponding to S?. self will not be modified.

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



90
91
92
 
# File 'lib/fa.rb', line 90

def maybe
  iter(0, 1)
end

#minimize ⇒ Fa::Automaton

Minimizes this automaton in place. Uses either Hopcroft’s or Brzozowski’s algorithm. Due to a stupid design mistake in libfa, the algorithm is selected through a global variable. It defaults to Hopcroft’s algorithm though.

Returns:

Raises:



29
30
31
32
33
 
# File 'lib/fa.rb', line 29

def minimize
  r = FFI::minimize(faptr)
  raise Error if r < 0
  self
end

#minus(other) ⇒ Fa::Automaton

Produces the difference of self and other. Neither self nor other will be modified. The resulting automaton will match all strings that match self but not other,

Parameters:

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



112
113
114
 
# File 'lib/fa.rb', line 112

def minus(other)
  from_ptr( FFI::minus(faptr, other.faptr) )
end

#plus ⇒ Fa::Automaton

Produces an iteration of at least one self, corresponding to S+. self will not be modified.

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



81
82
83
 
# File 'lib/fa.rb', line 81

def plus
  iter(1, -1)
end

#star ⇒ Fa::Automaton

Produces an iteration of any number of self, corresponding to S*. self will not be modified.

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



72
73
74
 
# File 'lib/fa.rb', line 72

def star
  iter(0, -1)
end

#to_s ⇒ String

Return the representation of self as a regular expression. Note that that regular expression can look pretty complicated, even for seemingly simple automata. Sometimes, minimizing the automaton before turning it into a string helps; sometimes it doesn’t.

Returns:

  • (String) —

    the regular expression for self

Raises:



196
197
198
199
200
201
202
203
 
# File 'lib/fa.rb', line 196

def to_s
  rx = ::FFI::MemoryPointer.new :string
  rx_len = ::FFI::MemoryPointer.new :size_t
  r = FFI::as_regexp(faptr, rx, rx_len)
  raise OutOfMemoryError if r < 0
  str_ptr = rx.read_pointer()
  return str_ptr.null? ? nil : str_ptr.read_string()
end

#total? ⇒ Boolean

Returns whether self is the total automaton, i.e., matches all possible words.

Returns:

  • (Boolean) 


188
 
# File 'lib/fa.rb', line 188

def total?; is_basic(:total); end

#union(other) ⇒ Fa::Automaton

Produces the union of self with other, corresponding to S|O. Neither self nor other will be modified.

Parameters:

Returns:

Raises:

  • OutOfMemoryError if libfa fails to allocate memory



51
52
53
 
# File 'lib/fa.rb', line 51

def union(other)
  from_ptr( FFI::union(faptr, other.faptr) )
end