use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::fst_impl::fst::{
ARCS_FOR_BINARY_SEARCH, ARCS_FOR_CONTINUOUS, ARCS_FOR_DIRECT_ADDRESSING, Arc, BitTable,
END_LABEL, FST,
};
use crate::core::util::fst_impl::fst_reader::FstReader;
use crate::core::util::fst_impl::outputs::{Outputs, OutputsBound};
use crate::core::util::fst_impl::util::Util;
pub struct FSTEnum<O, F>
where
O: Outputs,
F: FstReader,
{
pub fst: FST<O, F>,
pub(crate) arcs: Vec<Arc<O::V>>,
pub(crate) output: Vec<Option<O::V>>,
pub(crate) fst_reader: F::FstBytesReader,
pub(crate) upto: usize,
pub(crate) target_length: usize,
}
impl<O, F> FSTEnum<O, F>
where
O: Outputs,
F: FstReader,
{
pub(crate) fn new(fst: FST<O, F>) -> Result<Self> {
let fst_reader = fst.get_bytes_reader()?;
let mut arcs = Vec::with_capacity(10);
let mut output = Vec::with_capacity(10);
let root = fst.get_first_arc_owned();
arcs.push(root);
output.push(None);
Ok(Self {
fst,
arcs,
output,
fst_reader,
upto: 0,
target_length: 0,
})
}
fn set_output(
outputs: &O,
slots: &mut Vec<Option<O::V>>,
upto: usize,
arc_output: &Option<O::V>,
) {
if upto < slots.len() {
let (prefix, current) = slots.split_at_mut(upto);
match outputs.add(&prefix[upto - 1], arc_output) {
None => current[0] = None,
Some(std::borrow::Cow::Borrowed(output)) => {
if let Some(current) = &mut current[0] {
current.assign_from(output);
} else {
current[0] = Some(output.clone());
}
},
Some(std::borrow::Cow::Owned(output)) => current[0] = Some(output),
}
} else {
let output = outputs
.add(&slots[upto - 1], arc_output)
.map(std::borrow::Cow::into_owned);
slots.push(output);
}
}
fn rewind_prefix<FB>(&mut self, sub: &mut FB, target: &FB::V) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
if self.upto == 0 {
self.upto = 1;
self.grow_slots();
let (left, right) = self.arcs.split_at_mut(1);
let arc0 = &left[0];
let arc1 = &mut right[0];
self
.fst
.read_first_target_arc(arc0, arc1, &mut self.fst_reader)?;
return Ok(());
}
let current_limit = self.upto;
self.upto = 1;
{
while self.upto < current_limit && self.upto <= self.target_length + 1 {
let cmp = sub.get_current_label(self)? - sub.get_target_label(self, target)?;
if cmp < 0 {
break;
} else if cmp > 0 {
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc_prev = &left[self.upto - 1];
let arc = &mut right[0];
self
.fst
.read_first_target_arc(arc_prev, arc, &mut self.fst_reader)?;
break;
}
self.upto += 1;
}
}
Ok(())
}
pub(crate) fn do_next<FB>(&mut self, sub: &mut FB) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
if self.upto == 0 {
self.upto = 1;
self.grow_slots();
let (left, right) = self.arcs.split_at_mut(1);
let arc0 = &left[0];
let arc1 = &mut right[0];
self
.fst
.read_first_target_arc(arc0, arc1, &mut self.fst_reader)?;
} else {
while self.arcs[self.upto].is_last() {
self.upto -= 1;
if self.upto == 0 {
return Ok(());
}
}
let arc = &mut self.arcs[self.upto];
self.fst.read_next_arc(arc, &mut self.fst_reader)?;
}
self.push_first(sub)?;
Ok(())
}
pub(crate) fn do_seek_ceil<FB>(&mut self, sub: &mut FB, target: &FB::V) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
self.rewind_prefix(sub, target)?;
let mut upto = self.upto;
let mut fst_reader = None;
loop {
let target_label = sub.get_target_label(self, target)?;
let arc = &mut self.arcs[upto];
if arc.bytes_per_arc() != 0 && arc.label() != END_LABEL {
let node_flags = arc.node_flags();
let fst_reader = match &mut fst_reader {
Some(reader) => reader,
slot @ None => slot.insert(self.fst.get_bytes_reader()?),
};
let result = match node_flags {
ARCS_FOR_DIRECT_ADDRESSING => {
match self.do_seek_ceil_array_direct_addressing(upto, target_label, fst_reader, sub)? {
Some(index) => {
upto = index;
Some(())
},
None => None,
}
},
ARCS_FOR_BINARY_SEARCH => {
match self.do_seek_ceil_array_packed(upto, target_label, fst_reader, sub)? {
Some(index) => {
upto = index;
Some(())
},
None => None,
}
},
ARCS_FOR_CONTINUOUS => {
match self.do_seek_ceil_array_continuous(upto, target_label, fst_reader, sub)? {
Some(index) => {
upto = index;
Some(())
},
None => None,
}
},
_ => Some(()),
};
match result {
Some(_) => continue,
None => break,
}
} else {
let result = self.do_seek_ceil_list(upto, target_label, sub)?;
match result {
Some(index) => {
upto = index;
},
None => break,
}
}
}
Ok(())
}
fn do_seek_ceil_array_continuous<FB>(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
sub: &mut FB,
) -> Result<Option<usize>>
where
FB: FSTEnumBase<O, F>,
{
let arc = &mut self.arcs[arc_index];
let target_index = target_label - arc.first_label();
if target_index >= arc.num_arcs() {
self.rollback_to_last_fork_then_push(sub)?;
return Ok(None);
}
if target_index < 0 {
self.fst.read_arc_by_continuous(arc, reader, 0)?;
debug_assert!(arc.label() > target_label);
self.push_first(sub)?;
Ok(None)
} else {
{
self.fst.read_arc_by_continuous(arc, reader, target_index)?;
debug_assert_eq!(arc.label(), target_label);
Self::set_output(&self.fst.outputs, &mut self.output, self.upto, &arc.output);
if target_label == END_LABEL {
return Ok(None);
}
sub.set_current_label(arc.label(), self)?;
self.incr(sub)?;
}
debug_assert!(self.upto > arc_index);
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[arc_index];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
Ok(Some(self.upto))
}
}
fn do_seek_ceil_array_direct_addressing<FB>(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
sub: &mut FB,
) -> Result<Option<usize>>
where
FB: FSTEnumBase<O, F>,
{
let arc = &mut self.arcs[arc_index];
let mut target_index = target_label - arc.first_label();
if target_index >= arc.num_arcs() {
self.rollback_to_last_fork_then_push(sub)?;
return Ok(None);
}
if target_index < 0 {
target_index = -1;
} else if BitTable::is_bit_set(target_index, arc, reader)? {
{
self
.fst
.read_arc_by_direct_addressing(arc, reader, target_index)?;
debug_assert_eq!(arc.label(), target_label);
Self::set_output(&self.fst.outputs, &mut self.output, self.upto, &arc.output);
if target_label == END_LABEL {
return Ok(None);
}
sub.set_current_label(arc.label(), self)?;
self.incr(sub)?;
}
debug_assert!(self.upto > arc_index);
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[arc_index];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
return Ok(Some(self.upto));
}
let ceil_index = BitTable::next_bit_set(target_index, arc, reader)?;
debug_assert_ne!(ceil_index, -1);
self
.fst
.read_arc_by_direct_addressing(arc, reader, ceil_index)?;
debug_assert!(arc.label() > target_label);
self.push_first(sub)?;
Ok(None)
}
fn do_seek_ceil_array_packed<FB>(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
sub: &mut FB,
) -> Result<Option<usize>>
where
FB: FSTEnumBase<O, F>,
{
let arc = &mut self.arcs[arc_index];
let mut idx = Util::binary_search(&self.fst, arc, target_label)?;
if idx >= 0 {
self.fst.read_arc_by_index(arc, reader, idx)?;
debug_assert_eq!(arc.arc_idx(), idx);
debug_assert_eq!(arc.label(), target_label);
Self::set_output(&self.fst.outputs, &mut self.output, self.upto, &arc.output);
if target_label == END_LABEL {
return Ok(None);
}
sub.set_current_label(arc.label(), self)?;
self.incr(sub)?;
debug_assert!(self.upto > arc_index);
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[arc_index];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
return Ok(Some(self.upto));
}
idx = -1 - idx;
if idx == arc.num_arcs() {
self.fst.read_arc_by_index(arc, reader, idx - 1)?;
debug_assert!(arc.is_last());
if self.upto == 0 {
return Ok(None);
}
if self.upto == 0 {
return Err(LuceneError::illegal_state("upto should be greater than 0"));
}
self.upto -= 1;
while self.upto > 0 {
let prev_arc = &mut self.arcs[self.upto];
if !prev_arc.is_last() {
self.fst.read_next_arc(prev_arc, &mut self.fst_reader)?;
self.push_first(sub)?;
return Ok(None);
}
self.upto -= 1;
}
Ok(None)
} else {
self.fst.read_arc_by_index(arc, reader, idx)?;
debug_assert!(arc.label() > target_label);
self.push_first(sub)?;
Ok(None)
}
}
fn do_seek_ceil_list<FB>(
&mut self,
arc_index: usize,
target_label: i32,
sub: &mut FB,
) -> Result<Option<usize>>
where
FB: FSTEnumBase<O, F>,
{
let upto = arc_index;
let arc = &mut self.arcs[upto];
if arc.label() == target_label {
Self::set_output(&self.fst.outputs, &mut self.output, self.upto, &arc.output);
if target_label == END_LABEL {
return Ok(None);
}
sub.set_current_label(arc.label(), self)?;
self.incr(sub)?;
debug_assert!(self.upto > arc_index);
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[arc_index];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
Ok(Some(self.upto))
} else if arc.label() > target_label {
self.push_first(sub)?;
Ok(None)
} else if arc.is_last() {
if self.upto == 0 {
return Err(LuceneError::illegal_state("upto should be greater than 0"));
}
self.upto -= 1;
while self.upto > 0 {
let prev_arc = &mut self.arcs[self.upto];
if !prev_arc.is_last() {
self.fst.read_next_arc(prev_arc, &mut self.fst_reader)?;
self.push_first(sub)?;
return Ok(None);
}
self.upto -= 1;
}
Ok(None)
} else {
self.fst.read_next_arc(arc, &mut self.fst_reader)?;
Ok(Some(upto))
}
}
pub(crate) fn do_seek_floor<FB>(&mut self, sub: &mut FB, target: &FB::V) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
self.rewind_prefix(sub, target)?;
let mut upto = self.upto;
let mut fst_reader = None;
loop {
let target_label = sub.get_target_label(self, target)?;
let arc = &mut self.arcs[upto];
if arc.bytes_per_arc() != 0 && arc.label() != END_LABEL {
let node_flags = arc.node_flags();
let fst_reader = match &mut fst_reader {
Some(reader) => reader,
slot @ None => slot.insert(self.fst.get_bytes_reader()?),
};
let result = match node_flags {
ARCS_FOR_DIRECT_ADDRESSING => {
match self.do_seek_floor_array_direct_addressing(
upto,
target_label,
fst_reader,
sub,
target,
)? {
Some(index) => {
upto = index;
Some(())
},
None => None,
}
},
ARCS_FOR_BINARY_SEARCH => {
match self.do_seek_floor_array_packed(upto, target_label, fst_reader, sub, target)? {
Some(index) => {
upto = index;
Some(())
},
None => None,
}
},
ARCS_FOR_CONTINUOUS => {
match self.do_seek_floor_continuous(upto, target_label, fst_reader, sub, target)? {
Some(index) => {
upto = index;
Some(())
},
None => None,
}
},
_ => Some(()),
};
match result {
Some(_) => {
continue;
},
None => break,
}
} else {
let result = self.do_seek_floor_list(upto, target_label, sub, target)?;
match result {
Some(index) => {
upto = index;
},
None => break,
}
}
}
Ok(())
}
fn do_seek_floor_continuous<FB>(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
sub: &mut FB,
target: &FB::V,
) -> Result<Option<usize>>
where
FB: FSTEnumBase<O, F>,
{
let upto = arc_index;
let arc = &mut self.arcs[upto];
let target_index = target_label - arc.first_label();
if target_index < 0 {
let result = self.backtrack_to_floor_arc(arc_index, target_label, reader, sub, target)?;
debug_assert!(result.is_none());
Ok(None)
} else if target_index >= arc.num_arcs() {
self.fst.read_last_arc_by_continuous(arc, reader)?;
debug_assert!(arc.label() < target_label);
debug_assert!(arc.is_last());
self.push_last(sub)?;
Ok(None)
} else {
self.fst.read_arc_by_continuous(arc, reader, target_index)?;
debug_assert_eq!(arc.label(), target_label);
Self::set_output(&self.fst.outputs, &mut self.output, self.upto, &arc.output);
if target_label == END_LABEL {
return Ok(None);
}
sub.set_current_label(arc.label(), self)?;
self.incr(sub)?;
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[arc_index];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
Ok(Some(self.upto))
}
}
fn do_seek_floor_array_direct_addressing<FB>(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
sub: &mut FB,
target: &FB::V,
) -> Result<Option<usize>>
where
FB: FSTEnumBase<O, F>,
{
let upto = arc_index;
let arc = &mut self.arcs[upto];
let target_index = target_label - arc.first_label();
if target_index < 0 {
let result = self.backtrack_to_floor_arc(upto, target_label, reader, sub, target)?;
debug_assert!(result.is_none());
Ok(None)
} else if target_index >= arc.num_arcs() {
self.fst.read_last_arc_by_direct_addressing(arc, reader)?;
debug_assert!(arc.label() < target_label);
debug_assert!(arc.is_last());
self.push_last(sub)?;
Ok(None)
} else {
if BitTable::is_bit_set(target_index, arc, reader)? {
self
.fst
.read_arc_by_direct_addressing(arc, reader, target_index)?;
debug_assert_eq!(arc.label(), target_label);
Self::set_output(&self.fst.outputs, &mut self.output, self.upto, &arc.output);
if target_label == END_LABEL {
return Ok(None);
}
sub.set_current_label(arc.label(), self)?;
self.incr(sub)?;
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[arc_index];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
return Ok(Some(self.upto));
}
let floor_index = BitTable::previous_bit_set(target_index, arc, reader)?;
debug_assert_ne!(floor_index, -1);
self
.fst
.read_arc_by_direct_addressing(arc, reader, floor_index)?;
debug_assert!(arc.label() < target_label);
debug_assert!(arc.is_last() || self.fst.read_next_arc_label(arc, reader)? > target_label);
self.push_last(sub)?;
Ok(None)
}
}
fn rollback_to_last_fork_then_push<FB>(&mut self, sub: &mut FB) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
if self.upto == 0 {
return Err(LuceneError::illegal_state("upto should be greater than 0"));
}
self.upto -= 1;
while self.upto > 0 {
let upto = self.upto;
let prev_arc = &mut self.arcs[upto];
if !prev_arc.is_last() {
self.fst.read_next_arc(prev_arc, &mut self.fst_reader)?;
self.push_first(sub)?;
return Ok(());
}
self.upto -= 1;
}
Ok(())
}
fn backtrack_to_floor_arc<FB>(
&mut self,
arc_index: usize,
mut target_label: i32,
reader: &mut F::FstBytesReader,
sub: &mut FB,
target: &FB::V,
) -> Result<Option<Arc<O::V>>>
where
FB: FSTEnumBase<O, F>,
{
let mut upto = arc_index;
loop {
let (label, is_last, bytes_per_arc, node_flags) = {
let (left, right) = self.arcs.split_at_mut(upto);
let prev_arc = &left[self.upto - 1];
let arc = &mut right[0];
self
.fst
.read_first_target_arc(prev_arc, arc, &mut self.fst_reader)?;
(
arc.label(),
arc.is_last(),
arc.bytes_per_arc(),
arc.node_flags(),
)
};
if label < target_label {
if !is_last {
if bytes_per_arc != 0 && label != END_LABEL {
if node_flags == ARCS_FOR_BINARY_SEARCH {
self.find_next_floor_arc_binary_search(upto, target_label, reader)?;
} else if node_flags == ARCS_FOR_DIRECT_ADDRESSING {
self.find_next_floor_arc_direct_addressing(upto, target_label, reader)?;
} else if node_flags == ARCS_FOR_CONTINUOUS {
self.find_next_floor_arc_continuous(upto, target_label, reader)?;
} else {
return Err(LuceneError::corrupt_index(format!(
"invalid FST node flags: {node_flags}"
)));
}
} else {
let arc = &mut self.arcs[upto];
while !is_last && self.fst.read_next_arc_label(arc, reader)? < target_label {
self.fst.read_next_arc(arc, &mut self.fst_reader)?;
}
}
}
let arc = &mut self.arcs[upto];
debug_assert!(arc.label() < target_label);
debug_assert!(arc.is_last() || self.fst.read_next_arc_label(arc, reader)? >= target_label);
self.push_last(sub)?;
return Ok(None);
}
self.upto -= 1;
if self.upto == 0 {
return Ok(None);
}
target_label = sub.get_target_label(self, target)?;
upto = self.upto;
}
}
fn find_next_floor_arc_direct_addressing(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
) -> Result<()> {
let arc = &mut self.arcs[arc_index];
debug_assert_eq!(arc.node_flags(), ARCS_FOR_DIRECT_ADDRESSING);
debug_assert_ne!(arc.label(), END_LABEL);
debug_assert_eq!(arc.label(), arc.first_label());
if arc.num_arcs() > 1 {
let target_index = target_label - arc.first_label();
debug_assert!(target_index >= 0);
if target_index >= arc.num_arcs() {
self.fst.read_last_arc_by_direct_addressing(arc, reader)?;
} else {
let floor_index = BitTable::previous_bit_set(target_index, arc, reader)?;
if floor_index > 0 {
self
.fst
.read_arc_by_direct_addressing(arc, reader, floor_index)?;
}
}
}
Ok(())
}
fn find_next_floor_arc_continuous(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
) -> Result<()> {
let arc = &mut self.arcs[arc_index];
debug_assert_eq!(arc.node_flags(), ARCS_FOR_CONTINUOUS);
debug_assert_ne!(arc.label(), END_LABEL);
debug_assert_eq!(arc.label(), arc.first_label());
if arc.num_arcs() > 1 {
let target_index = target_label - arc.first_label();
debug_assert!(target_index >= 0);
if target_index >= arc.num_arcs() {
self.fst.read_last_arc_by_continuous(arc, reader)?;
} else {
self
.fst
.read_arc_by_continuous(arc, reader, target_index - 1)?;
}
}
Ok(())
}
fn find_next_floor_arc_binary_search(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
) -> Result<()> {
let arc = &mut self.arcs[arc_index];
debug_assert_eq!(arc.node_flags(), ARCS_FOR_BINARY_SEARCH);
debug_assert_ne!(arc.label(), END_LABEL);
debug_assert_eq!(arc.arc_idx(), 0);
if arc.num_arcs() > 1 {
let idx = Util::binary_search(&self.fst, arc, target_label)?;
debug_assert_ne!(idx, -1);
if idx > 1 {
self.fst.read_arc_by_index(arc, reader, idx - 1)?;
} else if idx < -2 {
self.fst.read_arc_by_index(arc, reader, -2 - idx)?;
}
}
Ok(())
}
fn do_seek_floor_array_packed<FB>(
&mut self,
arc_index: usize,
target_label: i32,
reader: &mut F::FstBytesReader,
sub: &mut FB,
target: &FB::V,
) -> Result<Option<usize>>
where
FB: FSTEnumBase<O, F>,
{
let upto = arc_index;
let arc = &mut self.arcs[upto];
let idx = Util::binary_search(&self.fst, arc, target_label)?;
if idx >= 0 {
self.fst.read_arc_by_index(arc, reader, idx)?;
debug_assert_eq!(arc.arc_idx(), idx);
debug_assert_eq!(
arc.label(),
target_label,
"arc.label()={} vs target_label={} mid={}",
arc.label(),
target_label,
idx
);
Self::set_output(&self.fst.outputs, &mut self.output, self.upto, &arc.output);
if target_label == END_LABEL {
return Ok(None);
}
sub.set_current_label(arc.label(), self)?;
self.incr(sub)?;
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[arc_index];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
Ok(Some(self.upto))
} else if idx == -1 {
let result = self.backtrack_to_floor_arc(upto, target_label, reader, sub, target)?;
debug_assert!(result.is_none());
Ok(None)
} else {
let floor_idx = -2 - idx;
self.fst.read_arc_by_index(arc, reader, floor_idx)?;
debug_assert!(arc.is_last() || self.fst.read_next_arc_label(arc, reader)? > target_label);
debug_assert!(
arc.label() < target_label,
"arc.label()={} vs target_label={}",
arc.label(),
target_label
);
self.push_last(sub)?;
Ok(None)
}
}
fn do_seek_floor_list<FB>(
&mut self,
arc_index: usize,
mut target_label: i32,
sub: &mut FB,
target: &FB::V,
) -> Result<Option<usize>>
where
FB: FSTEnumBase<O, F>,
{
let upto = arc_index;
let arc = &mut self.arcs[upto];
if arc.label() == target_label {
Self::set_output(&self.fst.outputs, &mut self.output, self.upto, &arc.output);
if target_label == END_LABEL {
return Ok(None);
}
sub.set_current_label(arc.label(), self)?;
self.incr(sub)?;
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[arc_index];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
Ok(Some(self.upto))
} else if arc.label() > target_label {
let mut upto = upto;
loop {
let (left, right) = self.arcs.split_at_mut(upto);
let prev_arc = &left[self.upto - 1];
let arc = &mut right[0];
self
.fst
.read_first_target_arc(prev_arc, arc, &mut self.fst_reader)?;
if arc.label() < target_label {
while !arc.is_last()
&& self.fst.read_next_arc_label(arc, &mut self.fst_reader)? < target_label
{
self.fst.read_next_arc(arc, &mut self.fst_reader)?;
}
self.push_last(sub)?;
return Ok(None);
}
self.upto -= 1;
if self.upto == 0 {
return Ok(None);
}
target_label = sub.get_target_label(self, target)?;
upto = self.upto;
}
} else if !arc.is_last() {
let next_label = self.fst.read_next_arc_label(arc, &mut self.fst_reader)?;
if next_label > target_label {
self.push_last(sub)?;
Ok(None)
} else {
self.fst.read_next_arc(arc, &mut self.fst_reader)?;
Ok(Some(upto))
}
} else {
self.push_last(sub)?;
Ok(None)
}
}
pub(crate) fn do_seek_exact<FB>(&mut self, sub: &mut FB, target: &FB::V) -> Result<bool>
where
FB: FSTEnumBase<O, F>,
{
self.rewind_prefix(sub, target)?;
let mut upto = self.upto - 1;
let mut target_label = sub.get_target_label(self, target)?;
let mut fst_reader = self.fst.get_bytes_reader()?;
loop {
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[upto];
let next_arc = &mut right[0];
let found = self
.fst
.find_target_arc(target_label, arc, next_arc, &mut fst_reader)?;
if found.is_none() {
self
.fst
.read_first_target_arc(arc, next_arc, &mut fst_reader)?;
return Ok(false);
}
Self::set_output(
&self.fst.outputs,
&mut self.output,
self.upto,
&next_arc.output,
);
if target_label == END_LABEL {
return Ok(true);
}
sub.set_current_label(target_label, self)?;
upto = self.upto;
self.incr(sub)?;
target_label = sub.get_target_label(self, target)?;
}
}
fn incr<FB>(&mut self, sub: &mut FB) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
if self.upto + 1 < self.arcs.len() {
self.upto += 1;
Ok(())
} else {
self.incr_and_grow(sub)
}
}
fn incr_and_grow<FB>(&mut self, sub: &mut FB) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
self.upto += 1;
sub.grow(self)?;
debug_assert!(self.upto <= i32::MAX as usize);
self.grow_slots();
Ok(())
}
fn grow_slots(&mut self) {
if self.arcs.len() <= self.upto {
self.arcs.push(Arc::with_outputs(None, None));
}
}
fn push_first<FB>(&mut self, sub: &mut FB) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
let mut upto = self.upto;
let mut label = self.arcs[upto].label();
loop {
if self.output.len() == self.upto {
let output = self
.fst
.outputs
.add(&self.output[self.upto - 1], &self.arcs[self.upto].output)
.map(std::borrow::Cow::into_owned);
self.output.push(output);
} else {
let (prefix, current) = self.output.split_at_mut(self.upto);
match self
.fst
.outputs
.add(&prefix[self.upto - 1], &self.arcs[self.upto].output)
{
None => current[0] = None,
Some(std::borrow::Cow::Borrowed(output)) => {
if let Some(value) = current[0].as_mut() {
value.assign_from(output);
} else {
current[0] = Some(output.clone());
}
},
Some(std::borrow::Cow::Owned(output)) => current[0] = Some(output),
}
}
if label == END_LABEL {
break;
}
sub.set_current_label(label, self)?;
upto = self.upto;
self.incr(sub)?;
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[upto];
let next_arc = &mut right[0];
self
.fst
.read_first_target_arc(arc, next_arc, &mut self.fst_reader)?;
label = next_arc.label();
}
Ok(())
}
fn push_last<FB>(&mut self, sub: &mut FB) -> Result<()>
where
FB: FSTEnumBase<O, F>,
{
let mut upto = self.upto;
let mut label = self.arcs[upto].label();
loop {
sub.set_current_label(label, self)?;
if self.output.len() == self.upto {
let output = self
.fst
.outputs
.add(&self.output[self.upto - 1], &self.arcs[self.upto].output)
.map(std::borrow::Cow::into_owned);
self.output.push(output);
} else {
let (prefix, current) = self.output.split_at_mut(self.upto);
match self
.fst
.outputs
.add(&prefix[self.upto - 1], &self.arcs[self.upto].output)
{
None => current[0] = None,
Some(std::borrow::Cow::Borrowed(output)) => {
if let Some(value) = current[0].as_mut() {
value.assign_from(output);
} else {
current[0] = Some(output.clone());
}
},
Some(std::borrow::Cow::Owned(output)) => current[0] = Some(output),
}
}
if label == END_LABEL {
break;
}
upto = self.upto;
self.incr(sub)?;
let (left, right) = self.arcs.split_at_mut(self.upto);
let arc = &left[upto];
let next_arc = &mut right[0];
self
.fst
.read_last_target_arc(arc, next_arc, &mut self.fst_reader)?;
label = next_arc.label();
}
Ok(())
}
}
pub(crate) trait FSTEnumBase<O, F>
where
O: Outputs,
F: FstReader,
{
type V;
fn get_target_label(&self, base: &FSTEnum<O, F>, target: &Self::V) -> Result<i32>;
fn get_current_label(&self, base: &FSTEnum<O, F>) -> Result<i32>;
fn set_current_label(&mut self, label: i32, base: &FSTEnum<O, F>) -> Result<()>;
fn grow(&mut self, base: &FSTEnum<O, F>) -> Result<()>;
}
#[derive(Clone)]
pub struct InputOutput<T, I> {
pub input: I,
pub output: Option<T>,
}