use crate::core::codecs::CodecUtil;
use crate::core::store::data_input_ext::DataInputExt;
use crate::core::store::output_stream_data_output::OutputStreamDataOutput;
use crate::core::store::{ByteBuffersDataOutput, DataInput, DataOutput};
use crate::core::util::IOUtils;
use crate::core::util::close::Closeable;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::fst_impl::bit_table_util::BitTableUtil;
use crate::core::util::fst_impl::fst_reader::FstReader;
use crate::core::util::fst_impl::on_heap_fst_store::OnHeapFSTStore;
use crate::core::util::fst_impl::outputs::{Outputs, OutputsBound};
use core::fmt;
use std::cell::RefCell;
use std::fmt::{Display, Formatter};
use std::fs::File;
use std::path::Path;
use std::rc::Rc;
pub struct FST<O, F>
where
O: Outputs,
{
pub metadata: FSTMetadata<O>,
pub outputs: O,
pub fst_reader: F,
}
impl<O> FST<O, OnHeapFSTStore>
where
O: Outputs,
{
pub fn from_on_heap_store<DI>(metadata: FSTMetadata<O>, input: &mut DI) -> Result<Self>
where
DI: DataInput,
{
let store = OnHeapFSTStore::new(DEFAULT_MAX_BLOCK_BITS, input, metadata.num_bytes)?;
Ok(Self::new(metadata, store))
}
}
impl<O, F> FST<O, F>
where
O: Outputs,
{
pub fn new(metadata: FSTMetadata<O>, fst_reader: F) -> Self {
Self {
outputs: metadata.outputs.clone(),
metadata,
fst_reader,
}
}
pub fn from_fst_reader(metadata: FSTMetadata<O>, fst_reader: F) -> Option<Self> {
Some(Self::new(metadata, fst_reader))
}
pub fn num_bytes(&self) -> i64 {
self.metadata.num_bytes
}
pub fn get_empty_output(&self) -> Option<&Option<O::V>> {
self.metadata.empty_output.as_ref()
}
pub fn metadata(&self) -> &FSTMetadata<O> {
&self.metadata
}
}
impl<O, F> FST<O, F>
where
O: Outputs,
F: FstReader,
{
pub fn save<DO, DO2>(&mut self, meta_out: &mut DO, out: &mut DO2) -> Result<()>
where
DO: DataOutput,
DO2: DataOutput,
{
self.metadata.save(meta_out)?;
self.fst_reader.write_to(out)
}
pub fn save_with_same_data_out<DO>(&self, out: &mut DO) -> Result<()>
where
DO: DataOutput,
{
self.metadata.save(out)?;
self.fst_reader.write_to(out)
}
pub fn save_to_path<P>(&mut self, path: P) -> Result<()>
where
P: AsRef<Path>,
{
let file = File::create(path)?;
let mut out = OutputStreamDataOutput::new(file);
let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
self.save_with_same_data_out(&mut out)
}));
let close_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| out.close()));
IOUtils::use_or_suppress_caught_result(result, close_result)
}
pub fn read_from_path(_path: &Path, _outputs: Rc<RefCell<O>>) -> Result<Self> {
todo!()
}
pub fn read_label<DI>(&self, input: &mut DI) -> Result<i32>
where
DI: DataInput,
{
let input_type = self.metadata.input_type;
let version = self.metadata.version;
let v = match input_type {
InputType::Byte1 => input.read_byte()? as i32,
InputType::Byte2 => {
let raw = input.read_short()?;
if version < VERSION_LITTLE_ENDIAN {
i32::from(raw.swap_bytes() as u16)
} else {
raw as u16 as i32
}
},
InputType::Byte4 => input.read_vint()?,
};
Ok(v)
}
fn read_presence_bytes<T>(&self, arc: &mut Arc<O::V>, reader: &mut T) -> Result<()>
where
T: BytesReader,
{
debug_assert!(arc.bytes_per_arc > 0);
debug_assert_eq!(arc.node_flags, ARCS_FOR_DIRECT_ADDRESSING);
arc.bit_table_start = reader.get_position();
let skip_bytes = get_num_presence_bytes(arc.num_arcs);
reader.skip_bytes(skip_bytes as i64)?;
Ok(())
}
pub fn get_first_arc(&self, arc: &mut Arc<O::V>) {
let (flags, final_output) = self.first_arc_state();
arc.flags = flags;
match (arc.next_final_output.as_mut(), final_output) {
(Some(current), Some(output)) => current.assign_from(output),
(_, None) => arc.next_final_output = None,
(None, Some(output)) => arc.next_final_output = Some(output.clone()),
}
arc.output = None;
arc.target = self.metadata.start_node;
}
pub fn get_first_arc_owned(&self) -> Arc<O::V> {
let (flags, final_output) = self.first_arc_state();
Arc {
label: 0,
output: None,
target: self.metadata.start_node,
flags,
next_final_output: final_output.cloned(),
next_arc: 0,
node_flags: 0,
bytes_per_arc: 0,
pos_arcs_start: 0,
arc_idx: 0,
num_arcs: 0,
bit_table_start: 0,
first_label: 0,
presence_index: 0,
}
}
fn first_arc_state(&self) -> (u8, Option<&O::V>) {
match self.metadata.empty_output.as_ref() {
Some(empty_output) => {
let mut flags = BIT_FINAL_ARC | BIT_LAST_ARC;
if empty_output.is_some() {
flags |= BIT_ARC_HAS_FINAL_OUTPUT;
}
(flags, empty_output.as_ref())
},
None => (BIT_LAST_ARC, None),
}
}
pub(crate) fn read_last_target_arc<'a, T>(
&self,
follow: &Arc<O::V>,
arc: &'a mut Arc<O::V>,
input: &mut T,
) -> Result<&'a mut Arc<O::V>>
where
T: BytesReader,
{
if !target_has_arcs(follow) {
debug_assert!(follow.is_final());
arc.label = END_LABEL;
arc.target = FINAL_END_NODE;
arc.output.assign_from(&follow.next_final_output);
arc.flags = BIT_LAST_ARC;
arc.node_flags = arc.flags;
return Ok(arc);
}
input.set_position(follow.target());
let flags = input.read_byte()?;
arc.node_flags = flags;
if flags == ARCS_FOR_BINARY_SEARCH
|| flags == ARCS_FOR_DIRECT_ADDRESSING
|| flags == ARCS_FOR_CONTINUOUS
{
arc.num_arcs = input.read_vint()?;
arc.bytes_per_arc = input.read_vint()?;
if flags == ARCS_FOR_DIRECT_ADDRESSING {
read_presence_bytes(arc, input)?;
arc.first_label = self.read_label(input)?;
arc.pos_arcs_start = input.get_position();
self.read_last_arc_by_direct_addressing(arc, input)?;
} else if flags == ARCS_FOR_BINARY_SEARCH {
arc.arc_idx = arc.num_arcs - 2;
arc.pos_arcs_start = input.get_position();
self.read_next_real_arc(arc, input)?;
} else {
arc.first_label = self.read_label(input)?;
arc.pos_arcs_start = input.get_position();
self.read_last_arc_by_continuous(arc, input)?;
}
} else {
arc.flags = flags;
arc.bytes_per_arc = 0;
while !arc.is_last() {
self.read_label(input)?;
if arc.flag(BIT_ARC_HAS_OUTPUT) {
self.outputs.skip_output(input)?;
}
if arc.flag(BIT_ARC_HAS_FINAL_OUTPUT) {
self.outputs.skip_final_output(input)?;
}
if arc.flag(BIT_STOP_NODE) || arc.flag(BIT_TARGET_NEXT) {
} else {
self.read_unpacked_node_target(input)?;
}
arc.flags = input.read_byte()?;
}
input.skip_bytes(-1)?;
arc.next_arc = input.get_position();
self.read_next_real_arc(arc, input)?;
}
debug_assert!(arc.is_last());
Ok(arc)
}
fn read_unpacked_node_target<T>(&self, reader: &mut T) -> Result<i64>
where
T: BytesReader,
{
reader.read_vlong()
}
pub(crate) fn find_target_arc_impl<'a, T, AF>(
&self,
label_to_match: i32,
follow: AF,
arc: &mut Arc<O::V>,
input: &mut T,
) -> Result<Option<()>>
where
T: BytesReader,
O::V: 'a,
AF: Into<Option<&'a Arc<O::V>>>,
{
let follow = follow.into();
let follow_target = follow.unwrap_or(arc).target();
if label_to_match == END_LABEL {
return if follow.unwrap_or(arc).is_final() {
if follow_target <= 0 {
arc.flags = BIT_LAST_ARC;
} else {
arc.flags = 0;
arc.next_arc = follow_target;
}
arc.output = follow.unwrap_or(arc).next_final_output();
arc.label = END_LABEL;
arc.node_flags = arc.flags;
Ok(Some(()))
} else {
Ok(None)
};
}
if follow_target <= 0 {
return Ok(None);
}
input.set_position(follow_target);
let flags = input.read_byte()?;
arc.node_flags = flags;
if flags == ARCS_FOR_DIRECT_ADDRESSING {
arc.num_arcs = input.read_vint()?;
arc.bytes_per_arc = input.read_vint()?;
self.read_presence_bytes(arc, input)?;
arc.first_label = self.read_label(input)?;
arc.pos_arcs_start = input.get_position();
let arc_index = label_to_match - arc.first_label;
if arc_index < 0 || arc_index >= arc.num_arcs {
return Ok(None); } else if !BitTable::is_bit_set(arc_index, arc, input)? {
return Ok(None); }
return self
.read_arc_by_direct_addressing(arc, input, arc_index)
.map(Some);
} else if flags == ARCS_FOR_BINARY_SEARCH {
arc.num_arcs = input.read_vint()?;
arc.bytes_per_arc = input.read_vint()?;
arc.pos_arcs_start = input.get_position();
let mut low = 0;
let mut high = arc.num_arcs - 1;
while low <= high {
let mid = (low + high) >> 1;
input.set_position(arc.pos_arcs_start - (arc.bytes_per_arc * mid + 1) as i64);
let mid_label = self.read_label(input)?;
match mid_label.cmp(&label_to_match) {
std::cmp::Ordering::Less => low = mid + 1,
std::cmp::Ordering::Greater => high = mid - 1,
std::cmp::Ordering::Equal => {
arc.arc_idx = mid - 1;
return self.read_next_real_arc(arc, input).map(Some);
},
}
}
return Ok(None);
} else if flags == ARCS_FOR_CONTINUOUS {
arc.num_arcs = input.read_vint()?;
arc.bytes_per_arc = input.read_vint()?;
arc.first_label = self.read_label(input)?;
arc.pos_arcs_start = input.get_position();
let arc_index = label_to_match - arc.first_label;
if arc_index < 0 || arc_index >= arc.num_arcs {
return Ok(None); }
arc.arc_idx = arc_index - 1;
return self.read_next_real_arc(arc, input).map(Some);
}
self.read_first_arc_info(follow_target, arc, input)?;
input.set_position(arc.next_arc);
loop {
debug_assert_eq!(arc.bytes_per_arc, 0);
arc.flags = input.read_byte()?;
let pos = input.get_position();
let label = self.read_label(input)?;
if label == label_to_match {
input.set_position(pos);
return self.read_arc(arc, input).map(Some);
} else if label > label_to_match || arc.is_last() {
return Ok(None);
} else {
let flag = arc.flags;
if flag_mod(flag, BIT_ARC_HAS_OUTPUT) {
self.outputs.skip_output(input)?;
}
if flag_mod(flag, BIT_ARC_HAS_FINAL_OUTPUT) {
self.outputs.skip_final_output(input)?;
}
if !flag_mod(flag, BIT_STOP_NODE) && !flag_mod(flag, BIT_TARGET_NEXT) {
self.read_unpacked_node_target(input)?;
}
}
}
}
pub fn read_first_target_arc<T>(
&self,
follow: &Arc<O::V>,
arc: &mut Arc<O::V>,
input: &mut T,
) -> Result<()>
where
T: BytesReader,
{
self.read_first_target_arc_impl(Some(follow), arc, input)
}
pub(crate) fn read_first_target_arc_impl<'a, T, AF>(
&self,
follow: AF,
arc: &mut Arc<O::V>,
input: &mut T,
) -> Result<()>
where
T: BytesReader,
O::V: 'a,
AF: Into<Option<&'a Arc<O::V>>>,
{
let follow = follow.into();
let follow_target = follow.unwrap_or(arc).target;
if follow.unwrap_or(arc).is_final() {
arc.label = END_LABEL;
let final_output = match follow {
Some(follow) => &follow.next_final_output,
None => &arc.next_final_output,
};
arc.output.assign_from(final_output);
arc.flags = BIT_FINAL_ARC;
if follow_target <= 0 {
arc.flags |= BIT_LAST_ARC;
} else {
arc.next_arc = follow_target;
}
arc.target = FINAL_END_NODE;
arc.node_flags = arc.flags;
Ok(())
} else {
self.read_first_real_target_arc(follow_target, arc, input)
}
}
fn read_first_arc_info<T>(
&self,
node_address: i64,
arc: &mut Arc<O::V>,
reader: &mut T,
) -> Result<()>
where
T: BytesReader,
{
reader.set_position(node_address);
let flags = reader.read_byte()?;
arc.node_flags = flags;
if flags == ARCS_FOR_BINARY_SEARCH
|| flags == ARCS_FOR_DIRECT_ADDRESSING
|| flags == ARCS_FOR_CONTINUOUS
{
arc.num_arcs = reader.read_vint()?;
arc.bytes_per_arc = reader.read_vint()?;
arc.arc_idx = -1;
if flags == ARCS_FOR_DIRECT_ADDRESSING {
self.read_presence_bytes(arc, reader)?;
arc.first_label = self.read_label(reader)?;
arc.presence_index = -1;
} else if flags == ARCS_FOR_CONTINUOUS {
arc.first_label = self.read_label(reader)?;
}
arc.pos_arcs_start = reader.get_position();
} else {
arc.next_arc = node_address;
arc.bytes_per_arc = 0;
}
Ok(())
}
pub fn read_first_real_target_arc<T>(
&self,
node_address: i64,
arc: &mut Arc<O::V>,
reader: &mut T,
) -> Result<()>
where
T: BytesReader,
{
self.read_first_arc_info(node_address, arc, reader)?;
self.read_next_real_arc(arc, reader)
}
pub fn is_expanded_target<T>(&self, follow: &Arc<O::V>, reader: &mut T) -> Result<bool>
where
T: BytesReader,
{
if !target_has_arcs(follow) {
Ok(false)
} else {
reader.set_position(follow.target);
let flags = reader.read_byte()?;
Ok(
flags == ARCS_FOR_BINARY_SEARCH
|| flags == ARCS_FOR_DIRECT_ADDRESSING
|| flags == ARCS_FOR_CONTINUOUS,
)
}
}
pub fn read_next_arc<T>(&self, arc: &mut Arc<O::V>, input: &mut T) -> Result<()>
where
T: BytesReader,
{
if arc.label() == END_LABEL {
if arc.next_arc() <= 0 {
return Err(LuceneError::illegal_argument(
"cannot read_next_arc when arc.is_last()=true",
));
}
self.read_first_real_target_arc(arc.next_arc(), arc, input)
} else {
self.read_next_real_arc(arc, input)
}
}
pub(crate) fn read_next_arc_label<T>(&self, arc: &Arc<O::V>, input: &mut T) -> Result<i32>
where
T: BytesReader,
{
debug_assert!(!arc.is_last());
if arc.label() == END_LABEL {
input.set_position(arc.next_arc());
let flags = input.read_byte()?;
if flags == ARCS_FOR_BINARY_SEARCH
|| flags == ARCS_FOR_DIRECT_ADDRESSING
|| flags == ARCS_FOR_CONTINUOUS
{
let num_arcs = input.read_vint()?;
input.read_vint()?; if flags == ARCS_FOR_BINARY_SEARCH {
input.read_byte()?; } else if flags == ARCS_FOR_DIRECT_ADDRESSING {
input.skip_bytes(get_num_presence_bytes(num_arcs) as i64)?;
} }
} else {
match arc.node_flags() {
ARCS_FOR_BINARY_SEARCH => {
let pos =
arc.pos_arcs_start() - (1 + arc.arc_idx()) as i64 * arc.bytes_per_arc() as i64 - 1;
input.set_position(pos);
},
ARCS_FOR_DIRECT_ADDRESSING => {
debug_assert!(BitTable::assert_is_valid(arc, input)?);
debug_assert!(BitTable::is_bit_set(arc.arc_idx(), arc, input)?);
let next_index = BitTable::next_bit_set(arc.arc_idx(), arc, input)?;
debug_assert!(next_index != -1);
return Ok(arc.first_label() + next_index);
},
ARCS_FOR_CONTINUOUS => {
return Ok(arc.first_label() + arc.arc_idx() + 1);
},
_ => {
debug_assert_eq!(arc.bytes_per_arc(), 0);
input.set_position(arc.next_arc() - 1);
},
}
}
self.read_label(input)
}
pub fn read_arc_by_index<T>(&self, arc: &mut Arc<O::V>, input: &mut T, idx: i32) -> Result<()>
where
T: BytesReader,
{
debug_assert!(arc.bytes_per_arc() > 0);
debug_assert_eq!(arc.node_flags(), ARCS_FOR_BINARY_SEARCH);
debug_assert!(idx >= 0 && idx < arc.num_arcs());
input.set_position(arc.pos_arcs_start() - idx as i64 * arc.bytes_per_arc() as i64);
arc.arc_idx = idx;
arc.flags = input.read_byte()?;
self.read_arc(arc, input)
}
pub fn read_arc_by_continuous<T>(
&self,
arc: &mut Arc<O::V>,
reader: &mut T,
range_index: i32,
) -> Result<()>
where
T: BytesReader,
{
debug_assert!(range_index >= 0 && range_index < arc.num_arcs);
let pos = arc.pos_arcs_start - (range_index as i64 * arc.bytes_per_arc as i64);
reader.set_position(pos);
arc.arc_idx = range_index;
arc.flags = reader.read_byte()?;
self.read_arc(arc, reader)
}
pub fn read_arc_by_direct_addressing<T>(
&self,
arc: &mut Arc<O::V>,
reader: &mut T,
range_index: i32,
) -> Result<()>
where
T: BytesReader,
{
debug_assert!(BitTable::assert_is_valid(arc, reader)?);
debug_assert!(
range_index >= 0 && range_index < arc.num_arcs,
"range_index {} out of bounds (0..{})",
range_index,
arc.num_arcs
);
debug_assert!(
BitTable::is_bit_set(range_index, arc, reader)?,
"bit not set at index {range_index}"
);
let presence_index = BitTable::count_bits_upto(range_index, arc, reader)?;
self.read_arc_by_direct_addressing_with_presence_index(arc, reader, range_index, presence_index)
}
pub fn read_arc_by_direct_addressing_with_presence_index<T>(
&self,
arc: &mut Arc<O::V>,
reader: &mut T,
range_index: i32,
presence_index: i32,
) -> Result<()>
where
T: BytesReader,
{
let pos = arc.pos_arcs_start - (presence_index as i64 * arc.bytes_per_arc as i64);
reader.set_position(pos);
arc.arc_idx = range_index;
arc.presence_index = presence_index;
arc.flags = reader.read_byte()?;
self.read_arc(arc, reader)
}
pub fn read_last_arc_by_direct_addressing<T>(
&self,
arc: &mut Arc<O::V>,
reader: &mut T,
) -> Result<()>
where
T: BytesReader,
{
debug_assert!(BitTable::assert_is_valid(arc, reader)?);
let presence_index = BitTable::count_bits(arc, reader)? - 1;
self.read_arc_by_direct_addressing_with_presence_index(
arc,
reader,
arc.num_arcs - 1,
presence_index,
)
}
pub fn read_last_arc_by_continuous<T>(&self, arc: &mut Arc<O::V>, reader: &mut T) -> Result<()>
where
T: BytesReader,
{
self.read_arc_by_continuous(arc, reader, arc.num_arcs - 1)
}
pub fn read_next_real_arc<T>(&self, arc: &mut Arc<O::V>, reader: &mut T) -> Result<()>
where
T: BytesReader,
{
match arc.node_flags {
ARCS_FOR_BINARY_SEARCH | ARCS_FOR_CONTINUOUS => {
debug_assert!(arc.bytes_per_arc > 0);
arc.arc_idx += 1;
debug_assert!(arc.arc_idx >= 0 && arc.arc_idx < arc.num_arcs);
let pos = arc.pos_arcs_start - (arc.arc_idx as i64 * arc.bytes_per_arc as i64);
reader.set_position(pos);
arc.flags = reader.read_byte()?;
},
ARCS_FOR_DIRECT_ADDRESSING => {
debug_assert!(BitTable::assert_is_valid(arc, reader)?);
debug_assert!(
arc.arc_idx == -1 || BitTable::is_bit_set(arc.arc_idx, arc, reader)?,
"arcIdx {} must be valid or unset",
arc.arc_idx
);
let next_index = BitTable::next_bit_set(arc.arc_idx, arc, reader)?;
return self.read_arc_by_direct_addressing_with_presence_index(
arc,
reader,
next_index,
arc.presence_index + 1,
);
},
_ => {
debug_assert_eq!(arc.bytes_per_arc, 0);
reader.set_position(arc.next_arc);
arc.flags = reader.read_byte()?;
},
}
self.read_arc(arc, reader)
}
pub fn read_arc<T>(&self, arc: &mut Arc<O::V>, reader: &mut T) -> Result<()>
where
T: BytesReader,
{
if arc.node_flags == ARCS_FOR_DIRECT_ADDRESSING || arc.node_flags == ARCS_FOR_CONTINUOUS {
arc.label = arc.first_label() + arc.arc_idx();
} else {
arc.label = self.read_label(reader)?;
}
if arc.flag(BIT_ARC_HAS_OUTPUT) {
arc.output = self.outputs.read(reader)?;
} else {
arc.output = None;
}
if arc.flag(BIT_ARC_HAS_FINAL_OUTPUT) {
arc.next_final_output = self.outputs.read_final_output(reader)?;
} else {
arc.next_final_output = None;
}
if arc.flag(BIT_STOP_NODE) {
arc.target = if arc.flag(BIT_FINAL_ARC) {
FINAL_END_NODE
} else {
NON_FINAL_END_NODE
};
arc.next_arc = reader.get_position();
} else if arc.flag(BIT_TARGET_NEXT) {
arc.next_arc = reader.get_position();
if !arc.flag(BIT_LAST_ARC) {
if arc.bytes_per_arc() == 0 {
self.seek_to_next_node(reader)?;
} else {
let num_arcs = if arc.node_flags == ARCS_FOR_DIRECT_ADDRESSING {
BitTable::count_bits(arc, reader)?
} else {
arc.num_arcs()
};
let pos = arc.pos_arcs_start - (arc.bytes_per_arc as i64 * num_arcs as i64);
reader.set_position(pos);
}
}
arc.target = reader.get_position();
} else {
arc.target = self.read_unpacked_node_target(reader)?;
arc.next_arc = reader.get_position();
}
Ok(())
}
pub fn find_target_arc<T>(
&self,
label_to_match: i32,
follow: &Arc<O::V>,
arc: &mut Arc<O::V>,
input: &mut T,
) -> Result<Option<()>>
where
T: BytesReader,
{
self.find_target_arc_impl(label_to_match, follow, arc, input)
}
pub fn seek_to_next_node<T>(&self, reader: &mut T) -> Result<()>
where
T: BytesReader,
{
loop {
let flags = reader.read_byte()?;
self.read_label(reader)?;
if flags & BIT_ARC_HAS_OUTPUT != 0 {
self.outputs.skip_output(reader)?;
}
if flags & BIT_ARC_HAS_FINAL_OUTPUT != 0 {
self.outputs.skip_final_output(reader)?;
}
if !flag_mod(flags, BIT_STOP_NODE) && !flag_mod(flags, BIT_TARGET_NEXT) {
self.read_unpacked_node_target(reader)?;
}
if flags & BIT_LAST_ARC != 0 {
return Ok(());
}
}
}
pub fn get_bytes_reader(&self) -> Result<F::FstBytesReader> {
self.fst_reader.get_reverse_bytes_reader()
}
}
impl<O, F> Display for FST<O, F>
where
O: Outputs,
{
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(
f,
"{}(input={:?}, output={})",
std::any::type_name::<Self>(),
self.metadata.input_type,
self.outputs
)
}
}
#[derive(Default, Clone, Debug)]
pub struct Arc<T> {
pub(crate) label: i32,
pub(crate) output: Option<T>,
target: i64,
flags: u8,
pub(crate) next_final_output: Option<T>,
next_arc: i64,
node_flags: u8,
bytes_per_arc: i32,
pos_arcs_start: i64,
arc_idx: i32,
num_arcs: i32,
bit_table_start: i64,
first_label: i32,
presence_index: i32,
}
impl<T> Arc<T> {
pub(crate) fn with_outputs(output: Option<T>, next_final_output: Option<T>) -> Self {
Self {
label: 0,
output,
target: 0,
flags: 0,
next_final_output,
next_arc: 0,
node_flags: 0,
bytes_per_arc: 0,
pos_arcs_start: 0,
arc_idx: 0,
num_arcs: 0,
bit_table_start: 0,
first_label: 0,
presence_index: 0,
}
}
pub(crate) fn flag(&self, flag: u8) -> bool {
flag_mod(self.flags, flag)
}
pub fn is_last(&self) -> bool {
self.flag(BIT_LAST_ARC)
}
pub fn is_final(&self) -> bool {
self.flag(BIT_FINAL_ARC)
}
pub fn label(&self) -> i32 {
self.label
}
pub fn target(&self) -> i64 {
self.target
}
pub fn flags(&self) -> u8 {
self.flags
}
pub fn next_arc(&self) -> i64 {
self.next_arc
}
pub fn arc_idx(&self) -> i32 {
self.arc_idx
}
pub fn node_flags(&self) -> u8 {
self.node_flags
}
pub fn pos_arcs_start(&self) -> i64 {
self.pos_arcs_start
}
pub fn bytes_per_arc(&self) -> i32 {
self.bytes_per_arc
}
pub fn num_arcs(&self) -> i32 {
self.num_arcs
}
pub fn first_label(&self) -> i32 {
self.first_label
}
}
impl<T: Clone> Arc<T> {
pub fn copy_from(&mut self, other: &Arc<T>) {
self.label = other.label();
self.target = other.target();
self.flags = other.flags();
self.output = other.output();
self.next_final_output = other.next_final_output();
self.next_arc = other.next_arc();
self.node_flags = other.node_flags();
self.bytes_per_arc = other.bytes_per_arc();
self.pos_arcs_start = other.pos_arcs_start();
self.arc_idx = other.arc_idx();
self.num_arcs = other.num_arcs();
self.bit_table_start = other.bit_table_start;
self.first_label = other.first_label();
self.presence_index = other.presence_index;
}
pub fn output(&self) -> Option<T> {
self.output.clone()
}
pub fn next_final_output(&self) -> Option<T> {
self.next_final_output.clone()
}
}
impl<T: Display> Display for Arc<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
write!(f, " target={}", self.target)?;
write!(f, " label=0x{:x}", self.label)?;
if self.flag(BIT_FINAL_ARC) {
write!(f, " final")?;
}
if self.flag(BIT_LAST_ARC) {
write!(f, " last")?;
}
if self.flag(BIT_TARGET_NEXT) {
write!(f, " targetNext")?;
}
if self.flag(BIT_STOP_NODE) {
write!(f, " stop")?;
}
if self.flag(BIT_ARC_HAS_OUTPUT)
&& let Some(output) = &self.output
{
write!(f, " output={output}")?;
}
if self.flag(BIT_ARC_HAS_FINAL_OUTPUT)
&& let Some(output) = &self.next_final_output
{
write!(f, " nextFinalOutput={output}")?;
}
if self.bytes_per_arc() != 0 {
let node_flag_str = match self.node_flags {
ARCS_FOR_DIRECT_ADDRESSING => "da",
ARCS_FOR_CONTINUOUS => "cs",
_ => "bs",
};
write!(
f,
" arcArray(idx={} of {})({})",
self.arc_idx, self.num_arcs, node_flag_str
)?;
}
Ok(())
}
}
pub(crate) struct BitTable;
impl BitTable {
pub(crate) fn is_bit_set<T, T2>(bit_index: i32, arc: &Arc<T>, reader: &mut T2) -> Result<bool>
where
T2: BytesReader,
{
debug_assert_eq!(arc.node_flags(), ARCS_FOR_DIRECT_ADDRESSING);
reader.set_position(arc.bit_table_start);
BitTableUtil::is_bit_set(bit_index, reader)
}
pub(crate) fn count_bits<R, T>(arc: &Arc<T>, reader: &mut R) -> Result<i32>
where
R: BytesReader,
{
debug_assert_eq!(arc.node_flags(), ARCS_FOR_DIRECT_ADDRESSING);
reader.set_position(arc.bit_table_start);
let num_presence_bytes = get_num_presence_bytes(arc.num_arcs());
BitTableUtil::count_bits(num_presence_bytes, reader)
}
pub(crate) fn count_bits_upto<T, T2>(bit_index: i32, arc: &Arc<T>, reader: &mut T2) -> Result<i32>
where
T2: BytesReader,
{
debug_assert_eq!(arc.node_flags(), ARCS_FOR_DIRECT_ADDRESSING);
reader.set_position(arc.bit_table_start);
BitTableUtil::count_bits_upto(bit_index, reader)
}
pub(crate) fn next_bit_set<T, T2>(bit_index: i32, arc: &Arc<T>, reader: &mut T2) -> Result<i32>
where
T2: BytesReader,
{
debug_assert_eq!(arc.node_flags(), ARCS_FOR_DIRECT_ADDRESSING);
reader.set_position(arc.bit_table_start);
let num_bytes = get_num_presence_bytes(arc.num_arcs());
BitTableUtil::next_bit_set(bit_index, num_bytes, reader)
}
pub(crate) fn previous_bit_set<T, T2>(
bit_index: i32,
arc: &Arc<T>,
reader: &mut T2,
) -> Result<i32>
where
T2: BytesReader,
{
debug_assert_eq!(arc.node_flags(), ARCS_FOR_DIRECT_ADDRESSING);
reader.set_position(arc.bit_table_start);
BitTableUtil::previous_bit_set(bit_index, reader)
}
pub(crate) fn assert_is_valid<T, T2>(arc: &Arc<T>, reader: &mut T2) -> Result<bool>
where
T2: BytesReader,
{
debug_assert!(arc.bytes_per_arc() > 0);
debug_assert_eq!(arc.node_flags(), ARCS_FOR_DIRECT_ADDRESSING);
debug_assert!(Self::is_bit_set(0, arc, reader)?);
debug_assert!(Self::is_bit_set(arc.num_arcs() - 1, arc, reader)?);
debug_assert_eq!(Self::next_bit_set(arc.num_arcs() - 1, arc, reader)?, -1);
Ok(true)
}
}
#[derive(Default)]
pub struct FSTMetadata<O>
where
O: Outputs,
{
pub input_type: InputType,
pub outputs: O,
pub version: i32,
pub empty_output: Option<Option<O::V>>,
pub start_node: i64,
pub num_bytes: i64,
}
impl<O: Outputs> FSTMetadata<O> {
pub fn new(
input_type: InputType,
outputs: O,
empty_output: Option<Option<O::V>>,
start_node: i64,
version: i32,
num_bytes: i64,
) -> Self {
Self {
input_type,
outputs,
version,
empty_output,
start_node,
num_bytes,
}
}
pub fn version(&self) -> i32 {
self.version
}
pub fn empty_output(&self) -> Option<&Option<O::V>> {
self.empty_output.as_ref()
}
pub fn num_bytes(&self) -> i64 {
self.num_bytes
}
pub fn save<DO>(&self, meta_out: &mut DO) -> Result<()>
where
DO: DataOutput,
{
CodecUtil::write_header(meta_out, FILE_FORMAT_NAME, VERSION_CURRENT)?;
if let Some(ref empty_output) = self.empty_output {
meta_out.write_byte(1)?;
let mut ros = ByteBuffersDataOutput::new();
self.outputs.write_final_output(empty_output, &mut ros)?;
let mut empty_output_bytes = ros.into_array();
let empty_len = empty_output_bytes.len();
let stop_at = empty_len / 2;
for i in 0..stop_at {
empty_output_bytes.swap(i, empty_len - i - 1);
}
meta_out.write_vint(empty_len as i32)?;
debug_assert!(empty_output_bytes.len() <= i32::MAX as usize);
meta_out.write_bytes_range(&empty_output_bytes, 0, empty_len)?;
} else {
meta_out.write_byte(0)?;
}
let t = match self.input_type {
InputType::Byte1 => 0u8,
InputType::Byte2 => 1u8,
InputType::Byte4 => 2u8,
};
meta_out.write_byte(t)?;
meta_out.write_vlong(self.start_node)?;
meta_out.write_vlong(self.num_bytes)?;
Ok(())
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum InputType {
#[default]
Byte1,
Byte2,
Byte4,
}
pub trait BytesReader: DataInput {
fn get_position(&self) -> i64;
fn set_position(&mut self, pos: i64);
}
pub enum BytesReaderEnum2<A, B> {
A(A),
B(B),
}
impl<A, B> crate::core::util::close::Closeable for BytesReaderEnum2<A, B> {}
impl<A, B> DataInput for BytesReaderEnum2<A, B>
where
A: BytesReader,
B: BytesReader,
{
fn read_byte(&mut self) -> Result<u8> {
match self {
BytesReaderEnum2::A(reader) => reader.read_byte(),
BytesReaderEnum2::B(reader) => reader.read_byte(),
}
}
fn get_bytes<'a>(&'a mut self, len: usize) -> Result<std::borrow::Cow<'a, [u8]>> {
match self {
BytesReaderEnum2::A(reader) => DataInput::get_bytes(reader, len),
BytesReaderEnum2::B(reader) => DataInput::get_bytes(reader, len),
}
}
fn read_bytes(&mut self, b: &mut [u8], offset: usize, len: usize) -> Result<()> {
match self {
BytesReaderEnum2::A(reader) => reader.read_bytes(b, offset, len),
BytesReaderEnum2::B(reader) => reader.read_bytes(b, offset, len),
}
}
fn read_group_vint(&mut self, dst: &mut [i32], offset: usize) -> Result<()> {
match self {
BytesReaderEnum2::A(reader) => reader.read_group_vint(dst, offset),
BytesReaderEnum2::B(reader) => reader.read_group_vint(dst, offset),
}
}
fn skip_bytes(&mut self, num_bytes: i64) -> Result<()> {
match self {
BytesReaderEnum2::A(reader) => reader.skip_bytes(num_bytes),
BytesReaderEnum2::B(reader) => reader.skip_bytes(num_bytes),
}
}
}
impl<A, B> DataInputExt for BytesReaderEnum2<A, B>
where
A: BytesReader,
B: BytesReader,
{
}
impl<A, B> Display for BytesReaderEnum2<A, B>
where
A: BytesReader,
B: BytesReader,
{
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
match self {
BytesReaderEnum2::A(reader) => {
write!(f, "BytesReaderEnum(F: {})", reader.get_position())
},
BytesReaderEnum2::B(reader) => {
write!(f, "BytesReaderEnum(S: {})", reader.get_position())
},
}
}
}
impl<A, B> BytesReader for BytesReaderEnum2<A, B>
where
A: BytesReader,
B: BytesReader,
{
fn get_position(&self) -> i64 {
match self {
BytesReaderEnum2::A(reader) => reader.get_position(),
BytesReaderEnum2::B(reader) => reader.get_position(),
}
}
fn set_position(&mut self, pos: i64) {
match self {
BytesReaderEnum2::A(reader) => reader.set_position(pos),
BytesReaderEnum2::B(reader) => reader.set_position(pos),
}
}
}
use crate::core::util::fst_impl::fst_compiler::get_on_heap_reader_writer;
pub(crate) const BIT_FINAL_ARC: u8 = 1 << 0;
pub(crate) const BIT_LAST_ARC: u8 = 1 << 1;
pub(crate) const BIT_TARGET_NEXT: u8 = 1 << 2;
pub(crate) const BIT_STOP_NODE: u8 = 1 << 3;
pub const BIT_ARC_HAS_OUTPUT: u8 = 1 << 4;
pub(crate) const BIT_ARC_HAS_FINAL_OUTPUT: u8 = 1 << 5;
pub const ARCS_FOR_BINARY_SEARCH: u8 = BIT_ARC_HAS_FINAL_OUTPUT;
pub const ARCS_FOR_DIRECT_ADDRESSING: u8 = 1 << 6;
pub const ARCS_FOR_CONTINUOUS: u8 = ARCS_FOR_DIRECT_ADDRESSING + ARCS_FOR_BINARY_SEARCH;
const FILE_FORMAT_NAME: &str = "FST";
pub const VERSION_START: i32 = 6;
const VERSION_LITTLE_ENDIAN: i32 = 8;
pub const VERSION_CONTINUOUS_ARCS: i32 = 9;
pub const VERSION_CURRENT: i32 = VERSION_CONTINUOUS_ARCS;
pub const VERSION_90: i32 = VERSION_LITTLE_ENDIAN;
pub(crate) const FINAL_END_NODE: i64 = -1;
pub(crate) const NON_FINAL_END_NODE: i64 = 0;
pub const END_LABEL: i32 = -1;
#[cfg(target_pointer_width = "64")]
pub const DEFAULT_MAX_BLOCK_BITS: i32 = 30;
#[cfg(not(target_pointer_width = "64"))]
pub const DEFAULT_MAX_BLOCK_BITS: i32 = 28;
#[inline]
pub(crate) fn flag_mod(flags: u8, bit: u8) -> bool {
(flags & bit) != 0
}
pub fn read_metadata<O, DI>(meta_in: &mut DI, outputs: O) -> Result<FSTMetadata<O>>
where
O: Outputs,
DI: DataInput,
{
let version = CodecUtil::check_header(meta_in, FILE_FORMAT_NAME, VERSION_START, VERSION_CURRENT)?;
let mut empty_output: Option<Option<O::V>> = None;
if meta_in.read_byte()? == 1 {
let mut empty_bytes = get_on_heap_reader_writer(10)?;
let num_bytes = meta_in.read_vint()?;
if num_bytes <= 0 || num_bytes > crate::core::store::data_output::COPY_BUFFER_SIZE as i32 {
empty_bytes.copy_bytes(meta_in, num_bytes as usize)?;
} else {
let bytes = match meta_in.get_bytes(num_bytes as usize)? {
std::borrow::Cow::Owned(mut bytes) if bytes.len() >= num_bytes as usize => {
bytes.truncate(num_bytes as usize);
bytes
},
bytes => bytes[..num_bytes as usize].to_vec(),
};
empty_bytes.byte_buffer = Some(Rc::new(bytes));
}
empty_bytes.freeze()?;
let mut reader = empty_bytes.get_reverse_bytes_reader()?;
if num_bytes > 0 {
reader.set_position((num_bytes - 1) as i64);
}
empty_output = Some(outputs.read_final_output(&mut reader)?);
}
let input_type = match meta_in.read_byte()? {
0 => InputType::Byte1,
1 => InputType::Byte2,
2 => InputType::Byte4,
invalid => {
return Err(LuceneError::corrupt_index(format!(
"invalid input type {invalid} (resource={meta_in})"
)));
},
};
let start_node = meta_in.read_vlong()?;
let num_bytes = meta_in.read_vlong()?;
Ok(FSTMetadata::new(
input_type,
outputs,
empty_output,
start_node,
version,
num_bytes,
))
}
pub fn target_has_arcs<T>(arc: &Arc<T>) -> bool {
arc.target() > 0
}
pub(crate) fn get_num_presence_bytes(label_range: i32) -> i32 {
debug_assert!(label_range >= 0);
(label_range + 7) >> 3
}
pub(crate) fn read_presence_bytes<T, T2>(arc: &mut Arc<T>, reader: &mut T2) -> Result<()>
where
T2: BytesReader,
{
debug_assert!(arc.bytes_per_arc() > 0);
debug_assert_eq!(arc.node_flags(), ARCS_FOR_DIRECT_ADDRESSING);
arc.bit_table_start = reader.get_position();
let skip = get_num_presence_bytes(arc.num_arcs());
reader.skip_bytes(skip as i64)
}
pub(crate) fn read_end_arc<T>(follow: &Arc<T>, arc: &mut Arc<T>) -> Option<()>
where
T: Clone,
{
if follow.is_final() {
if follow.target() <= 0 {
arc.flags = BIT_LAST_ARC;
} else {
arc.flags = 0;
arc.next_arc = follow.target();
}
arc.output = follow.next_final_output();
arc.label = END_LABEL;
Some(())
} else {
None
}
}