use bit_set::BitSet;
use num_traits::ToPrimitive;
use std::fmt;
use std::fmt::{Display, Formatter};
use crate::core::util::accountable::Accountable;
use crate::core::util::array_util::ArrayUtil;
use crate::core::util::automation::transition::Transition;
use crate::core::util::automation::transition_accessor::TransitionAccessor;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::in_place_merge_sorter::InPlaceMergeSorter;
use crate::core::util::ram_usage_estimator::size_of_vec;
use crate::core::util::{BitSetExt, Sorter, TryIntoInt};
#[derive(Debug, Clone)]
pub struct Automaton {
next_state: usize,
next_transition: usize,
cur_state: Option<usize>,
states: Vec<i32>,
is_accept: BitSet,
transitions: Vec<i32>,
deterministic: bool,
}
impl Display for Automaton {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(f, "{}", std::any::type_name::<Self>())
}
}
impl Default for Automaton {
fn default() -> Self {
Self::new()
}
}
impl Automaton {
pub fn new() -> Self {
Self::with_capacity(2, 2)
}
pub fn with_capacity(num_states: usize, num_transitions: usize) -> Self {
Automaton {
next_state: 0,
next_transition: 0,
cur_state: None,
states: vec![0; num_states * 2],
is_accept: BitSet::with_capacity(num_states),
transitions: Vec::with_capacity(num_transitions * 3),
deterministic: true,
}
}
pub fn create_state(&mut self) -> Result<i32> {
self.grow_states()?;
let state = (self.next_state / 2) as i32;
self.states[self.next_state] = -1;
self.next_state += 2;
Ok(state)
}
pub fn set_accept(&mut self, state: i32, accept: bool) {
let state_index = state as usize;
debug_assert!(
(0..self.get_num_states() as usize).contains(&state_index),
"state {state} out of bounds"
);
if accept {
self.is_accept.insert(state_index);
} else {
self.is_accept.remove(state_index);
}
}
pub fn get_sorted_transitions(&self) -> Vec<Vec<Transition>> {
let num_states = self.get_num_states();
let mut result = Vec::with_capacity(num_states as usize);
for s in 0..num_states {
let cnt = self.get_num_transitions_with_state(s);
let mut row = Vec::with_capacity(cnt as usize);
for i in 0..cnt {
let mut t = Transition::default();
self.get_transition(s, i, &mut t);
row.push(t);
}
result.push(row);
}
result
}
pub(crate) fn get_accept_states(&self) -> &BitSet {
&self.is_accept
}
pub fn is_accept(&self, state: i32) -> bool {
self.is_accept.contains(state as usize)
}
pub fn add_transition_label(&mut self, source: i32, dest: i32, label: i32) -> Result<()> {
self.add_transition(source, dest, label, label)
}
pub fn add_transition(&mut self, source: i32, dest: i32, min: i32, max: i32) -> Result<()> {
debug_assert!(self.next_transition.is_multiple_of(3));
let bounds = (self.next_state / 2) as i32;
debug_assert!((0..bounds).contains(&source));
debug_assert!((0..bounds).contains(&dest));
self.grow_transitions()?;
let source = source as usize;
if self.cur_state != Some(source) {
if let Some(state) = self.cur_state {
self.finish_current_state(state)?;
}
self.cur_state = Some(source);
if self.states[2 * source] != -1 {
return Err(LuceneError::illegal_state(format!(
"from state ({source}) already had transitions added"
)));
}
debug_assert!(self.states[2 * source + 1] == 0);
self.states[2 * source] = self.next_transition as i32;
}
self.transitions.extend_from_slice(&[dest, min, max]);
self.next_transition += 3;
self.states[2 * source + 1] += 1;
Ok(())
}
pub fn add_epsilon(&mut self, source: i32, dest: i32) -> Result<()> {
let mut t = Transition::default();
let count = self.init_transition(dest, &mut t);
for _ in 0..count {
self.get_next_transition(&mut t)?;
self.add_transition(source, t.dest, t.min, t.max)?;
}
if self.is_accept(dest) {
self.set_accept(source, true);
}
Ok(())
}
pub fn copy(&mut self, other: &Automaton) -> Result<()> {
let state_offset = self.get_num_states();
let total_states = self.next_state + other.next_state;
ArrayUtil::grow_with(&mut self.states, total_states, || 0)?;
self.states[self.next_state..total_states].copy_from_slice(&other.states[..other.next_state]);
let next_state = self.next_state;
for i in (0..other.next_state).step_by(2) {
if self.states[next_state + i] != -1 {
self.states[next_state + i] += self.next_transition as i32;
}
}
self.next_state += other.next_state;
let other_num_states = other.get_num_states();
let other_accept_states = other.get_accept_states();
let mut state = 0;
while state < other_num_states {
state = other_accept_states.next_set_bit(state as usize);
if state == -1 {
break;
}
self.set_accept(state_offset + state, true);
state += 1;
}
let len = self.next_transition + other.next_transition;
ArrayUtil::grow_capacity(&mut self.transitions, len)?;
self
.transitions
.extend_from_slice(&other.transitions[..other.next_transition]);
let next_transition = self.next_transition;
for i in (0..other.next_transition).step_by(3) {
self.transitions[next_transition + i] += state_offset;
}
self.next_transition += other.next_transition;
if !other.deterministic {
self.deterministic = false;
}
Ok(())
}
fn finish_current_state(&mut self, state: usize) -> Result<()> {
let num_transitions = self.states[2 * state + 1];
debug_assert!(num_transitions > 0, "no transitions to finish");
let offset = self.states[2 * state];
let start = offset / 3;
let sub = DestMinMaxSorter {
transitions: &mut self.transitions,
};
let mut sort = InPlaceMergeSorter::new(sub);
let start_index: usize = start.try_convert()?;
sort.sort(start_index, (start + num_transitions).try_convert()?)?;
let mut upto = 0;
let mut min = -1;
let mut max = -1;
let mut dest = -1;
let offset = offset as usize;
for i in 0..num_transitions as usize {
let base = offset + 3 * i;
let t_dest = self.transitions[base];
let t_min = self.transitions[base + 1];
let t_max = self.transitions[base + 2];
if dest == t_dest {
if t_min <= max + 1 {
if t_max > max {
max = t_max;
}
} else {
if dest != -1 {
self.transitions[offset + 3 * upto] = dest;
self.transitions[offset + 3 * upto + 1] = min;
self.transitions[offset + 3 * upto + 2] = max;
upto += 1;
}
min = t_min;
max = t_max;
}
} else {
if dest != -1 {
self.transitions[offset + 3 * upto] = dest;
self.transitions[offset + 3 * upto + 1] = min;
self.transitions[offset + 3 * upto + 2] = max;
upto += 1;
}
dest = t_dest;
min = t_min;
max = t_max;
}
}
if dest != -1 {
self.transitions[offset + 3 * upto] = dest;
self.transitions[offset + 3 * upto + 1] = min;
self.transitions[offset + 3 * upto + 2] = max;
upto += 1;
}
debug_assert!(upto.to_i32().is_some());
self.next_transition -= (num_transitions - upto as i32) as usize * 3;
self.transitions.truncate(self.next_transition);
self.states[2 * state + 1] = upto as i32;
let sub = MinMaxDestSorter {
transitions: &mut self.transitions,
};
let mut sort = InPlaceMergeSorter::new(sub);
sort.sort(start_index, start_index + upto)?;
if self.deterministic && upto > 1 {
let mut last_max = self.transitions[offset + 2];
for i in 1..upto {
let next_min = self.transitions[offset + 3 * i + 1];
if next_min <= last_max {
self.deterministic = false;
break;
}
last_max = self.transitions[offset + 3 * i + 2];
}
}
Ok(())
}
pub fn is_deterministic(&self) -> bool {
self.deterministic
}
pub fn finish_state(&mut self) -> Result<()> {
if let Some(state) = self.cur_state {
self.finish_current_state(state)?;
self.cur_state = None;
}
Ok(())
}
pub fn get_num_states(&self) -> i32 {
(self.next_state / 2) as i32
}
pub fn get_num_transitions(&self) -> i32 {
(self.next_transition / 3) as i32
}
fn grow_states(&mut self) -> Result<()> {
let len = self.next_state + 2;
if len > self.states.len() {
ArrayUtil::grow_with(&mut self.states, len, || 0)?;
}
Ok(())
}
fn grow_transitions(&mut self) -> Result<()> {
let len = self.next_transition + 3;
if len > self.transitions.capacity() {
ArrayUtil::grow_capacity(&mut self.transitions, len)?;
}
Ok(())
}
fn transition_sorted(&self, t: &Transition) -> Result<bool> {
let upto = t
.transition_upto
.ok_or_else(|| LuceneError::illegal_state("transition cursor is not initialized"))?;
if upto as i32 == self.states[2 * t.source as usize] {
return Ok(true);
}
let next_dest = self.transitions[upto];
let next_min = self.transitions[upto + 1];
let next_max = self.transitions[upto + 2];
Ok(if next_min > t.min {
true
} else if next_min < t.min {
false
} else if next_max > t.max {
true
} else if next_max < t.max {
false
} else if next_dest > t.dest {
true
} else {
false
})
}
pub fn get_start_points(&self) -> Vec<i32> {
let mut byte_points = [0_u64; 5];
byte_points[0] = 1;
let mut points = None;
for s in (0..self.next_state).step_by(2) {
let mut trans = self.states[s] as usize;
let limit = trans + 3 * self.states[s + 1] as usize;
while trans < limit {
let min = self.transitions[trans + 1];
let max = self.transitions[trans + 2];
if points.is_none() && (0..=255).contains(&min) && (0..=255).contains(&max) {
byte_points[min as usize / 64] |= 1 << (min % 64);
let end = max as usize + 1;
byte_points[end / 64] |= 1 << (end % 64);
} else {
let points = points.get_or_insert_with(|| {
let mut points = Vec::with_capacity(1 + 2 * (self.next_transition / 3));
for (word, &bits) in byte_points.iter().enumerate() {
let mut bits = bits;
while bits != 0 {
points.push((word * 64 + bits.trailing_zeros() as usize) as i32);
bits &= bits - 1;
}
}
points
});
points.push(min);
if max < char::MAX as i32 {
points.push(max + 1);
}
}
trans += 3;
}
}
if let Some(mut points) = points {
points.sort_unstable();
points.dedup();
points.shrink_to_fit();
points
} else {
let count = byte_points
.iter()
.map(|bits| bits.count_ones() as usize)
.sum();
let mut points = Vec::with_capacity(count);
for (word, &bits) in byte_points.iter().enumerate() {
let mut bits = bits;
while bits != 0 {
points.push((word * 64 + bits.trailing_zeros() as usize) as i32);
bits &= bits - 1;
}
}
points
}
}
pub fn step(&self, state: i32, label: i32) -> i32 {
self.next_impl(state, 0, label, None)
}
pub fn next(&self, transition: &mut Transition, label: i32) -> i32 {
self.next_impl(
transition.source,
transition.transition_upto.map_or(-1, |upto| upto as i32),
label,
Some(transition),
)
}
fn next_impl(
&self,
state: i32,
from_transition_idx: i32,
label: i32,
transition: Option<&mut Transition>,
) -> i32 {
debug_assert!(label >= 0);
let state_index = 2 * state as usize;
let first_transition = self.states[state_index];
let num_transitions = self.states[state_index + 1];
let mut low = from_transition_idx.max(0);
let mut high = num_transitions - 1;
while low <= high {
let mid = ((low + high) as u32 >> 1) as i32;
let transition_index = (first_transition + 3 * mid) as usize;
let min_label = self.transitions[transition_index + 1];
if min_label > label {
high = mid - 1;
} else {
let max_label = self.transitions[transition_index + 2];
if max_label < label {
low = mid + 1;
} else {
let dest = self.transitions[transition_index];
if let Some(tr) = transition {
tr.dest = dest;
tr.min = min_label;
tr.max = max_label;
tr.transition_upto = Some(mid as usize);
}
return dest;
}
}
}
let dest_state = -1;
if let Some(tr) = transition {
tr.dest = dest_state;
tr.transition_upto = Some(low as usize);
}
dest_state
}
pub fn append_char_string(c: i32, f: &mut fmt::Formatter<'_>) -> fmt::Result {
if (0x21..=0x7e).contains(&c) && c != '\\' as i32 && c != '"' as i32 {
write!(f, "{}", char::from_u32(c as u32).unwrap_or('?'))
} else {
write!(f, "\\\\U{c:08X}")
}
}
}
impl TransitionAccessor for Automaton {
fn init_transition(&self, state: i32, t: &mut Transition) -> i32 {
debug_assert!(
state < (self.next_state / 2) as i32,
"state {} next_state {}",
state,
self.next_state
);
t.source = state;
let transition_upto = self.states[2 * state as usize];
t.transition_upto = (transition_upto != -1).then_some(transition_upto as usize);
self.get_num_transitions_with_state(state)
}
fn get_next_transition(&self, t: &mut Transition) -> Result<()> {
let base = t
.transition_upto
.ok_or_else(|| LuceneError::illegal_state("transition cursor is not initialized"))?;
debug_assert!(
(base as i32 + 3 - self.states[2 * t.source as usize])
<= 3 * self.states[2 * t.source as usize + 1]
);
debug_assert!(self.transition_sorted(t)?);
t.dest = self.transitions[base];
t.min = self.transitions[base + 1];
t.max = self.transitions[base + 2];
t.transition_upto = Some(base + 3);
Ok(())
}
fn get_num_transitions_with_state(&self, state: i32) -> i32 {
debug_assert!(state >= 0);
debug_assert!(state < self.get_num_states());
let count = self.states[2 * state as usize + 1];
if count == -1 { 0 } else { count }
}
fn get_transition(&self, state: i32, index: i32, t: &mut Transition) {
let base = self.states[2 * state as usize] as usize;
let offset = base + 3 * index as usize;
t.source = state;
t.dest = self.transitions[offset];
t.min = self.transitions[offset + 1];
t.max = self.transitions[offset + 2];
}
}
impl Accountable for Automaton {
fn ram_bytes_used(&self) -> Result<i64> {
Ok(
size_of_vec(&self.states)
.saturating_add(size_of_vec(&self.transitions))
.saturating_add((self.is_accept.capacity() / 8) as i64),
)
}
}
#[derive(Clone)]
pub struct Builder {
next_state: i32,
is_accept: BitSet,
transitions: Vec<i32>,
next_transition: usize,
}
impl Accountable for Builder {
fn ram_bytes_used(&self) -> Result<i64> {
Ok(size_of_vec(&self.transitions).saturating_add((self.is_accept.capacity() / 8) as i64))
}
}
impl Default for Builder {
fn default() -> Self {
Self::new()
}
}
impl Builder {
pub fn new() -> Self {
Self::with_capacity(16, 16)
}
pub fn with_capacity(num_states: usize, num_transitions: usize) -> Self {
let is_accept = BitSet::with_capacity(num_states);
let transitions = Vec::with_capacity(num_transitions * 4);
Builder {
next_state: 0,
is_accept,
transitions,
next_transition: 0,
}
}
pub fn add_transition_label(&mut self, source: i32, dest: i32, label: i32) -> Result<()> {
self.add_transition(source, dest, label, label)
}
pub fn add_transition(&mut self, source: i32, dest: i32, min: i32, max: i32) -> Result<()> {
let new_len = self.next_transition + 4;
if self.transitions.capacity() < new_len {
ArrayUtil::grow_capacity(&mut self.transitions, new_len)?;
}
self
.transitions
.extend_from_slice(&[source, dest, min, max]);
self.next_transition = new_len;
Ok(())
}
pub fn add_epsilon(&mut self, source: i32, dest: i32) -> Result<()> {
let mut upto = 0;
while upto < self.next_transition {
if self.transitions[upto] == dest {
self.add_transition(
source,
self.transitions[upto + 1],
self.transitions[upto + 2],
self.transitions[upto + 3],
)?;
}
upto += 4;
}
if self.is_accept(dest) {
self.set_accept(source, true);
}
Ok(())
}
pub fn finish(&mut self) -> Result<Automaton> {
let num_states = self.next_state;
let num_transitions = self.next_transition / 4;
let mut a = Automaton::with_capacity(num_states as usize, num_transitions);
for state in 0..num_states {
a.create_state()?;
a.set_accept(state, self.is_accept(state));
}
let sub = InPlaceMergeSorterImpl {
transitions: &mut self.transitions,
};
let mut sort = InPlaceMergeSorter::new(sub);
debug_assert!(num_transitions.to_i32().is_some());
sort.sort(0, num_transitions)?;
let mut upto = 0;
while upto < self.next_transition {
a.add_transition(
self.transitions[upto],
self.transitions[upto + 1],
self.transitions[upto + 2],
self.transitions[upto + 3],
)?;
upto += 4;
}
a.finish_state()?;
Ok(a)
}
pub fn create_state(&mut self) -> i32 {
let s = self.next_state;
self.next_state += 1;
s
}
pub fn set_accept(&mut self, state: i32, accept: bool) {
debug_assert!(
(0..self.next_state).contains(&state),
"state {state} out of bounds"
);
if accept {
self.is_accept.insert(state as usize);
} else {
self.is_accept.remove(state as usize);
}
}
pub fn is_accept(&self, state: i32) -> bool {
self.is_accept.contains(state as usize)
}
pub fn get_num_states(&self) -> i32 {
self.next_state
}
pub fn copy(&mut self, other: &Automaton) -> Result<()> {
let offset = self.get_num_states();
let other_num_states = other.get_num_states();
self.copy_states(other);
let mut t = Transition::default();
for s in 0..other_num_states {
let count = other.init_transition(s, &mut t);
for _ in 0..count {
other.get_next_transition(&mut t)?;
self.add_transition(offset + s, offset + t.dest, t.min, t.max)?;
}
}
Ok(())
}
pub fn copy_states(&mut self, other: &Automaton) {
let other_num_states = other.get_num_states();
for s in 0..other_num_states {
let new_state = self.create_state();
let is_accept = other.is_accept(s);
self.set_accept(new_state, is_accept);
}
}
}
pub struct InPlaceMergeSorterImpl<'a> {
transitions: &'a mut [i32],
}
impl<'a> InPlaceMergeSorterImpl<'a> {
fn swap_one(&mut self, i: usize, j: usize) {
self.transitions.swap(i, j);
}
}
impl Sorter for InPlaceMergeSorterImpl<'_> {
fn compare(&mut self, i: usize, j: usize) -> Result<i32> {
let i_start = i * 4;
let i_transition = &self.transitions[i_start..i_start + 4];
let j_start = j * 4;
let j_transition = &self.transitions[j_start..j_start + 4];
let i_src = i_transition[0];
let j_src = j_transition[0];
if i_src < j_src {
return Ok(-1);
}
if i_src > j_src {
return Ok(1);
}
let i_min = i_transition[2];
let j_min = j_transition[2];
if i_min < j_min {
return Ok(-1);
}
if i_min > j_min {
return Ok(1);
}
let i_max = i_transition[3];
let j_max = j_transition[3];
if i_max < j_max {
return Ok(-1);
}
if i_max > j_max {
return Ok(1);
}
let i_dest = i_transition[1];
let j_dest = j_transition[1];
if i_dest < j_dest {
Ok(-1)
} else if i_dest > j_dest {
Ok(1)
} else {
Ok(0)
}
}
fn swap(&mut self, i: usize, j: usize) -> Result<()> {
let i_start = i * 4;
let j_start = j * 4;
self.swap_one(i_start, j_start);
self.swap_one(i_start + 1, j_start + 1);
self.swap_one(i_start + 2, j_start + 2);
self.swap_one(i_start + 3, j_start + 3);
Ok(())
}
}
pub struct MinMaxDestSorter<'a> {
transitions: &'a mut [i32],
}
impl<'a> MinMaxDestSorter<'a> {
fn swap_one(&mut self, i: usize, j: usize) {
self.transitions.swap(i, j)
}
}
impl Sorter for MinMaxDestSorter<'_> {
fn compare(&mut self, i: usize, j: usize) -> Result<i32> {
let i_start = 3 * i;
let i_transition = &self.transitions[i_start..i_start + 3];
let j_start = 3 * j;
let j_transition = &self.transitions[j_start..j_start + 3];
let i_min = i_transition[1];
let j_min = j_transition[1];
if i_min < j_min {
return Ok(-1);
} else if i_min > j_min {
return Ok(1);
}
let i_max = i_transition[2];
let j_max = j_transition[2];
if i_max < j_max {
return Ok(-1);
} else if i_max > j_max {
return Ok(1);
}
let i_dest = i_transition[0];
let j_dest = j_transition[0];
if i_dest < j_dest {
Ok(-1)
} else if i_dest > j_dest {
Ok(1)
} else {
Ok(0)
}
}
fn swap(&mut self, i: usize, j: usize) -> Result<()> {
let i_start = 3 * i;
let j_start = 3 * j;
self.swap_one(i_start, j_start);
self.swap_one(i_start + 1, j_start + 1);
self.swap_one(i_start + 2, j_start + 2);
Ok(())
}
}
pub struct DestMinMaxSorter<'a> {
transitions: &'a mut [i32],
}
impl<'a> DestMinMaxSorter<'a> {
fn swap_one(&mut self, i: usize, j: usize) {
self.transitions.swap(i, j)
}
}
impl Sorter for DestMinMaxSorter<'_> {
fn compare(&mut self, i: usize, j: usize) -> Result<i32> {
let i_start = 3 * i;
let i_transition = &self.transitions[i_start..i_start + 3];
let j_start = 3 * j;
let j_transition = &self.transitions[j_start..j_start + 3];
let i_dest = i_transition[0];
let j_dest = j_transition[0];
if i_dest < j_dest {
return Ok(-1);
} else if i_dest > j_dest {
return Ok(1);
}
let i_min = i_transition[1];
let j_min = j_transition[1];
if i_min < j_min {
return Ok(-1);
} else if i_min > j_min {
return Ok(1);
}
let i_max = i_transition[2];
let j_max = j_transition[2];
if i_max < j_max {
return Ok(-1);
} else if i_max > j_max {
return Ok(1);
}
Ok(0)
}
fn swap(&mut self, i: usize, j: usize) -> Result<()> {
let i_start = 3 * i;
let j_start = 3 * j;
self.swap_one(i_start, j_start);
self.swap_one(i_start + 1, j_start + 1);
self.swap_one(i_start + 2, j_start + 2);
Ok(())
}
}