use std::fmt::{Display, Formatter};
use smallvec::SmallVec;
use crate::core::store::{ByteArrayDataOutput, DataOutput, IndexOutput};
use crate::core::util::accountable::Accountable;
use crate::core::util::array_util::ArrayUtil;
use crate::core::util::close::Closeable;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::fst_impl::dummy::dummy_bytes_reader::DummyBytesReader;
use crate::core::util::fst_impl::fst::{
ARCS_FOR_BINARY_SEARCH, ARCS_FOR_CONTINUOUS, ARCS_FOR_DIRECT_ADDRESSING,
BIT_ARC_HAS_FINAL_OUTPUT, BIT_ARC_HAS_OUTPUT, BIT_FINAL_ARC, BIT_LAST_ARC, BIT_STOP_NODE,
BIT_TARGET_NEXT, BytesReaderEnum2, FINAL_END_NODE, FST, FSTMetadata, InputType,
NON_FINAL_END_NODE, VERSION_90, VERSION_CONTINUOUS_ARCS, VERSION_CURRENT, get_num_presence_bytes,
};
use crate::core::util::fst_impl::fst_reader::FstReader;
use crate::core::util::fst_impl::growable_byte_array_data_output::GrowableByteArrayDataOutput;
use crate::core::util::fst_impl::node_hash::NodeHash;
use crate::core::util::fst_impl::outputs::{Outputs, OutputsBound};
use crate::core::util::fst_impl::read_write_data_output::ReadWriteDataOutput;
use crate::core::util::fst_impl::reverse_bytes_reader::ReverseBytesReader;
use crate::core::util::ints_ref::IntsRef;
use crate::core::util::ints_ref_builder::IntsRefBuilder;
use crate::core::util::{SliceCopyOps, TryIntoInt};
pub struct FSTCompiler<O, DO>
where
O: Outputs,
DO: IndexOutput,
{
pub(crate) dedup_hash: Option<NodeHash<O::V>>,
pub(crate) fst: FST<O, NullFSTReader>,
pub(crate) last_input: IntsRefBuilder<Vec<i32>>,
pub(crate) padding_byte_pending: bool,
pub(crate) last_frozen_node: i64,
pub(crate) arc_sizes: Vec<[i32; 2]>,
pub(crate) fixed_length_arcs_buffer: FixedLengthArcsBuffer,
pub(crate) arc_count: i64,
pub(crate) node_count: i64,
pub(crate) binary_search_node_count: i64,
pub(crate) direct_addressing_node_count: i64,
pub(crate) continuous_node_count: i64,
pub(crate) allow_fixed_length_arcs: bool,
pub(crate) direct_addressing_max_oversizing_factor: f32,
pub(crate) version: i32,
pub(crate) direct_addressing_expansion_credit: i64,
pub(crate) data_output: DataOutputEnum<DO>,
pub(crate) scratch_bytes: GrowableByteArrayDataOutput,
pub(crate) num_bytes_written: i64,
pub(crate) frontier: Vec<UnCompiledNode<O::V>>,
}
impl<O, DO> FSTCompiler<O, DO>
where
O: Outputs,
DO: IndexOutput,
{
fn new(
input_type: InputType,
suffix_ram_limit_mb: f64,
outputs: O,
allow_fixed_length_arcs: bool,
data_output: DataOutputEnum<DO>,
direct_addressing_max_oversizing_factor: f32,
version: i32,
) -> Result<Self> {
let dedup_hash = if suffix_ram_limit_mb < 0.0 {
return Err(LuceneError::illegal_argument(format!(
"ramLimitMB must be >= 0; got: {suffix_ram_limit_mb}"
)));
} else if suffix_ram_limit_mb > 0f64 {
Some(NodeHash::new(suffix_ram_limit_mb)?)
} else {
None
};
let num_bytes_written = 1; let padding_byte_pending = true;
let fst_meta = FSTMetadata::new(input_type, outputs, None, -1, version, 0);
let fst = FST::new(fst_meta, NullFSTReader);
let mut frontier = Vec::with_capacity(16);
frontier.push(UnCompiledNode::new(0));
Ok(Self {
dedup_hash,
fst,
last_input: IntsRefBuilder::default(),
padding_byte_pending,
last_frozen_node: 0,
arc_sizes: vec![],
fixed_length_arcs_buffer: FixedLengthArcsBuffer::new(),
arc_count: 0,
node_count: 0,
binary_search_node_count: 0,
direct_addressing_node_count: 0,
continuous_node_count: 0,
allow_fixed_length_arcs,
direct_addressing_max_oversizing_factor,
version,
direct_addressing_expansion_credit: 0,
data_output,
scratch_bytes: GrowableByteArrayDataOutput::new(),
num_bytes_written,
frontier,
})
}
fn compile_node(&mut self, node_in_idx: usize) -> Result<CompiledNode> {
let num_arcs = self.frontier[node_in_idx].num_arcs;
let bytes_pos_start = self.num_bytes_written;
let node = match self.dedup_hash.is_some() {
true => {
if num_arcs == 0 {
let node = self.add_node(node_in_idx)?;
self.last_frozen_node = node;
node
} else {
NodeHash::add(node_in_idx, self)?
}
},
false => self.add_node(node_in_idx)?,
};
debug_assert!(node != -2);
let bytes_pos_end = self.num_bytes_written;
if bytes_pos_end != bytes_pos_start {
debug_assert!(bytes_pos_end > bytes_pos_start);
self.last_frozen_node = node;
}
Ok(CompiledNode { node })
}
fn freeze_tail(&mut self, prefix_len_plus1: usize) -> Result<()> {
let (len, down_to) = { (self.last_input.length(), prefix_len_plus1.max(1)) };
let mut idx = len;
while idx >= down_to {
let (label, next_final_output, is_final, prev_idx) = {
let node = &mut self.frontier[idx];
let prev_idx = idx - 1;
let next_final_output = if self.dedup_hash.is_none() {
node.output.take()
} else {
None
};
let is_final = node.is_final || node.num_arcs == 0;
let label = self.last_input.int_at(prev_idx);
(label, next_final_output, is_final, prev_idx)
};
let compiled = self.compile_node(idx)?;
let node = &mut self.frontier[idx];
let next_final_output = next_final_output.or_else(|| node.output.take());
node.clear();
let parent = &mut self.frontier[prev_idx];
parent.replace_last(
label,
NodeEnum::CompiledNode(compiled),
next_final_output,
is_final,
);
idx -= 1;
}
Ok(())
}
pub fn add(&mut self, input: &IntsRef<Vec<i32>>, mut output: Option<O::V>) -> Result<()> {
let ints = &input.ints;
debug_assert!(
self.last_input.length() == 0 || *input >= *self.last_input.get(),
"inputs are added out of order lastInput={:?} vs input={:?}",
self.last_input.get(),
input
);
if input.length == 0 {
self.frontier[0].is_final = true;
self.set_empty_output(output)?;
return Ok(());
}
let mut pos1 = 0;
let mut pos2 = input.offset;
let pos1_stop = self.last_input.length().min(input.length);
while pos1 < pos1_stop && self.last_input.int_at(pos1) == ints[pos2] {
pos1 += 1;
pos2 += 1;
}
let prefix_len_plus1 = pos1 + 1;
if self.frontier.len() < (input.length + 1) {
let old_len = self.frontier.len();
let min_size = input.length + 1;
if self.frontier.capacity().min(ArrayUtil::MAX_ARRAY_LENGTH) < min_size {
let capacity = ArrayUtil::oversize(min_size, std::mem::size_of::<UnCompiledNode<O::V>>())?;
self.frontier.reserve_exact(capacity - old_len);
}
self
.frontier
.extend((old_len..min_size).map(UnCompiledNode::new));
}
self.freeze_tail(prefix_len_plus1)?;
let offset = input.offset;
for idx in prefix_len_plus1..=input.length {
let label = ints[offset + idx - 1];
let un_compiled = NodeEnum::UnCompiledNode;
self.frontier[idx - 1].add_arc(label, un_compiled)?;
}
let last_input_len = self.last_input.length();
let last_node = &mut self.frontier[input.length];
if last_input_len != input.length || prefix_len_plus1 != input.length + 1 {
last_node.is_final = true;
last_node.output = None;
}
let outputs = &self.fst.outputs;
for idx in 1..prefix_len_plus1 {
let (parents, nodes) = self.frontier.split_at_mut(idx);
let parent = &mut parents[idx - 1];
let node = &mut nodes[0];
let label = ints[offset + idx - 1];
let last_output = parent.get_last_output(label);
if last_output.is_some() {
let common_output_prefix = outputs.common(&output, last_output);
let word_suffix = outputs.subtract(last_output, &common_output_prefix);
let common_output_prefix = parent.set_last_output(label, common_output_prefix);
node.prepend_output(&word_suffix, outputs);
outputs.subtract_assign(&mut output, common_output_prefix);
} else {
outputs.subtract_assign(&mut output, &None);
}
}
if self.last_input.length() == input.length && prefix_len_plus1 == input.length + 1 {
let last_node = &self.frontier[input.length];
let v = self.fst.outputs.merge(&last_node.output, &output)?;
self.frontier[input.length].output = v;
} else {
let label = ints[input.offset + prefix_len_plus1 - 1];
let _ = self.frontier[prefix_len_plus1 - 1].set_last_output(label, output);
}
if self.last_input.ints().len() >= input.length {
self.last_input.ints()[pos1..input.length]
.copy_from_slice(&ints[input.offset + pos1..input.offset + input.length]);
self.last_input.set_length(input.length);
} else {
self.last_input.copy_ints_ref(input)?;
}
Ok(())
}
pub fn compile(&mut self) -> Result<Option<FSTMetadata<O>>> {
self.freeze_tail(0)?;
if self.frontier[0].num_arcs == 0 {
if self.fst.metadata.empty_output.is_none() {
return Ok(None);
} else {
self.write_padding_byte()?;
}
}
let compiled_root = self.compile_node(0)?;
self.frontier[0].clear();
self.finish(compiled_root.node)?;
let v = std::mem::take(&mut self.fst.metadata);
Ok(Some(v))
}
pub fn close_data_output(&mut self) -> Result<()> {
self.data_output.close()
}
pub(crate) fn add_node(&mut self, node_in_idx: usize) -> Result<i64> {
let node_in = &self.frontier[node_in_idx];
if node_in.num_arcs == 0 {
return Ok(if node_in.is_final {
FINAL_END_NODE
} else {
NON_FINAL_END_NODE
});
}
self.scratch_bytes.set_position(0)?;
let do_fixed_length_arcs = self.should_expand_node_with_fixed_length_arcs(node_in);
if do_fixed_length_arcs {
self.arc_sizes.clear();
ArrayUtil::grow_capacity(&mut self.arc_sizes, node_in.num_arcs)?;
}
self.arc_count += node_in.num_arcs as i64;
let last_arc = node_in.num_arcs - 1;
let mut last_arc_start = 0;
let mut max_bytes_per_arc = 0;
let mut max_bytes_per_arc_without_label = 0;
for (arc_idx, arc) in node_in.arcs.iter().enumerate().take(node_in.num_arcs) {
match &arc.target {
NodeEnum::CompiledNode(target) => {
let mut flags = 0;
if arc_idx == last_arc {
flags |= BIT_LAST_ARC;
}
if self.last_frozen_node == target.node && !do_fixed_length_arcs {
flags |= BIT_TARGET_NEXT;
}
if arc.is_final {
flags |= BIT_FINAL_ARC;
if !arc.next_final_output.is_none() {
flags |= BIT_ARC_HAS_FINAL_OUTPUT;
}
} else {
debug_assert!(arc.next_final_output.is_none());
}
let target_has_arcs = target.node > 0;
if !target_has_arcs {
flags |= BIT_STOP_NODE;
}
let arc_has_output = !arc.output.is_none();
if arc_has_output {
flags |= BIT_ARC_HAS_OUTPUT;
}
self.scratch_bytes.write_byte(flags)?;
let label_start = self.scratch_bytes.get_position();
{
debug_assert!(arc.label >= 0, "v = {}", arc.label);
match self.fst.metadata.input_type {
InputType::Byte1 => {
debug_assert!(arc.label <= 255, "v = {}", arc.label);
self.scratch_bytes.write_byte(arc.label as u8)?;
},
InputType::Byte2 => {
debug_assert!(arc.label <= 65535, "v = {}", arc.label);
self.scratch_bytes.write_short(arc.label as i16)?;
},
InputType::Byte4 => {
self.scratch_bytes.write_vint(arc.label)?;
},
}
}
let label_end = self.scratch_bytes.get_position();
let num_label_bytes = (label_end - label_start) as i32;
if arc_has_output {
self
.fst
.outputs
.write(&arc.output, &mut self.scratch_bytes)?;
}
if !arc.next_final_output.is_none() {
self
.fst
.outputs
.write_final_output(&arc.next_final_output, &mut self.scratch_bytes)?;
}
if target_has_arcs && (flags & BIT_TARGET_NEXT) == 0 {
self.scratch_bytes.write_vlong(target.node)?;
}
if do_fixed_length_arcs {
let arc_length = self.scratch_bytes.get_position() - last_arc_start;
let num_arc_bytes: i32 = arc_length.try_convert()?;
self.arc_sizes.push([num_arc_bytes, num_label_bytes]);
last_arc_start = self.scratch_bytes.get_position();
max_bytes_per_arc = max_bytes_per_arc.max(num_arc_bytes);
max_bytes_per_arc_without_label =
max_bytes_per_arc_without_label.max(num_arc_bytes - num_label_bytes);
}
},
NodeEnum::UnCompiledNode => {
return Err(LuceneError::illegal_state("should be compiled"));
},
}
}
if do_fixed_length_arcs {
debug_assert!(max_bytes_per_arc > 0);
let label_range = node_in.arcs[last_arc].label - node_in.arcs[0].label + 1;
debug_assert!(label_range > 0);
let continuous_label = label_range == node_in.num_arcs as i32;
if continuous_label && self.version >= VERSION_CONTINUOUS_ARCS {
self.write_node_for_direct_addressing_or_continuous(
node_in_idx,
max_bytes_per_arc_without_label,
label_range,
true,
)?;
self.continuous_node_count += 1;
} else if self.should_expand_node_with_direct_addressing(
node_in_idx,
max_bytes_per_arc,
max_bytes_per_arc_without_label,
label_range,
)? {
self.write_node_for_direct_addressing_or_continuous(
node_in_idx,
max_bytes_per_arc_without_label,
label_range,
false,
)?;
self.direct_addressing_node_count += 1;
} else {
self.write_node_for_binary_search(node_in_idx, max_bytes_per_arc)?;
self.binary_search_node_count += 1;
}
}
self.reverse_scratch_bytes();
if self.padding_byte_pending {
self.write_padding_byte()?;
}
self
.scratch_bytes
.write_to_data_output(&mut self.data_output)?;
self.num_bytes_written += self.scratch_bytes.get_position() as i64;
self.node_count += 1;
Ok(self.num_bytes_written - 1)
}
pub fn get_fst_reader(&mut self) -> Result<DataOutputEnum<DO>> {
let is_fst_reader = match self.data_output {
DataOutputEnum::FromDir(_) => false,
DataOutputEnum::ReadWriter(_) => true,
};
if is_fst_reader {
let v = std::mem::replace(
&mut self.data_output,
DataOutputEnum::ReadWriter(ReadWriteDataOutput::default()),
);
Ok(v)
} else {
Err(LuceneError::illegal_state(format!(
"The DataOutput must implement FSTReader, but got {}",
self.data_output
)))
}
}
pub fn get_direct_addressing_max_oversizing_factor(&self) -> f32 {
self.direct_addressing_max_oversizing_factor
}
pub fn get_node_count(&self) -> i64 {
1 + self.node_count
}
pub fn get_arc_count(&self) -> i64 {
self.arc_count
}
fn write_padding_byte(&mut self) -> Result<()> {
debug_assert!(self.padding_byte_pending);
self.data_output.write_byte(0)?;
self.padding_byte_pending = false;
Ok(())
}
#[allow(dead_code)]
fn write_label(&mut self, _v: i32) -> Result<()> {
Ok(())
}
fn should_expand_node_with_fixed_length_arcs(&self, node: &UnCompiledNode<O::V>) -> bool {
self.allow_fixed_length_arcs
&& (((node.depth as usize) <= FIXED_LENGTH_ARC_SHALLOW_DEPTH
&& node.num_arcs >= FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS)
|| node.num_arcs >= FIXED_LENGTH_ARC_DEEP_NUM_ARCS)
}
fn should_expand_node_with_direct_addressing(
&mut self,
node_in_idx: usize,
num_bytes_per_arc: i32,
max_bytes_per_arc_without_label: i32,
label_range: i32,
) -> Result<bool> {
let node_in = &self.frontier[node_in_idx];
let size_for_binary_search = num_bytes_per_arc * node_in.num_arcs as i32;
let size_for_direct_addressing = get_num_presence_bytes(label_range)
+ self.arc_sizes[0][1]
+ max_bytes_per_arc_without_label * node_in.num_arcs as i32;
let allowed_oversize =
(size_for_binary_search as f32 * self.get_direct_addressing_max_oversizing_factor()) as i32;
let expansion_cost = size_for_direct_addressing - allowed_oversize;
if expansion_cost == 0
|| (self.direct_addressing_expansion_credit >= expansion_cost as i64
&& size_for_direct_addressing
<= (allowed_oversize as f32 * DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR) as i32)
{
self.direct_addressing_expansion_credit -= expansion_cost as i64;
return Ok(true);
}
Ok(false)
}
fn write_node_for_binary_search(
&mut self,
node_in_idx: usize,
max_bytes_per_arc: i32,
) -> Result<()> {
self.fixed_length_arcs_buffer.reset_position()?;
self
.fixed_length_arcs_buffer
.write_byte(ARCS_FOR_BINARY_SEARCH)?;
let node_in = &self.frontier[node_in_idx];
self
.fixed_length_arcs_buffer
.write_vint(node_in.num_arcs as i32)?;
self
.fixed_length_arcs_buffer
.write_vint(max_bytes_per_arc)?;
let header_len = self.fixed_length_arcs_buffer.get_position();
let src_pos = self.scratch_bytes.get_position();
let dest_pos = header_len + (node_in.num_arcs as i32 * max_bytes_per_arc) as usize;
debug_assert!(dest_pos >= src_pos);
if dest_pos > src_pos {
self.scratch_bytes.set_position(dest_pos)?;
let scratch_bytes = self.scratch_bytes.get_bytes();
let arc_bytes = &self.arc_sizes;
let mut src_pos = src_pos;
let mut dest_pos = dest_pos;
let max_bytes_per_arc = max_bytes_per_arc as usize;
for arc_idx in (0..node_in.num_arcs).rev() {
dest_pos -= max_bytes_per_arc;
let arc_len = arc_bytes[arc_idx][0] as usize;
src_pos -= arc_len;
if src_pos != dest_pos {
debug_assert!(
dest_pos >= src_pos,
"dest_pos={} < src_pos={} at arc_idx={}, max_bytes_per_arc={}, arc_len={}, num_arcs={}",
dest_pos,
src_pos,
arc_idx,
max_bytes_per_arc,
arc_len,
node_in.num_arcs
);
scratch_bytes.copy_within(src_pos..src_pos + arc_len, dest_pos);
}
}
}
self
.scratch_bytes
.get_bytes()
.copy_from(&self.fixed_length_arcs_buffer.get_bytes()[..header_len], 0);
Ok(())
}
fn reverse_scratch_bytes(&mut self) {
let pos = self.scratch_bytes.get_position();
self.scratch_bytes.get_bytes()[..pos].reverse();
}
#[allow(dead_code)]
fn write_scratch_bytes(&mut self, _dest_pos: i32, _bytes: &[u8], _offset: i32, _length: i32) {
}
fn write_node_for_direct_addressing_or_continuous(
&mut self,
node_in_idx: usize,
max_bytes_per_arc_without_label: i32,
label_range: i32,
continuous: bool,
) -> Result<()> {
let header_max_len = 11;
let num_presence_bytes = if continuous {
0
} else {
get_num_presence_bytes(label_range) as usize
};
let mut src_pos = self.scratch_bytes.get_position();
let node_in = &self.frontier[node_in_idx];
let total_arc_bytes =
(self.arc_sizes[0][1] + node_in.num_arcs as i32 * max_bytes_per_arc_without_label) as usize;
let mut buffer_offset = header_max_len + num_presence_bytes + total_arc_bytes;
self
.fixed_length_arcs_buffer
.ensure_capacity(buffer_offset)?;
let buffer = self.fixed_length_arcs_buffer.get_bytes();
for arc_idx in (0..node_in.num_arcs).rev() {
buffer_offset -= max_bytes_per_arc_without_label as usize;
let src_arc_len = self.arc_sizes[arc_idx][0] as usize;
src_pos -= src_arc_len;
let label_len = self.arc_sizes[arc_idx][1] as usize;
self
.scratch_bytes
.write_to(src_pos, buffer, buffer_offset, 1);
let remaining_len = src_arc_len - 1 - label_len;
if remaining_len != 0 {
self.scratch_bytes.write_to(
src_pos + 1 + label_len,
buffer,
buffer_offset + 1,
remaining_len,
);
}
if arc_idx == 0 {
buffer_offset -= label_len;
self
.scratch_bytes
.write_to(src_pos + 1, buffer, buffer_offset, label_len);
}
}
debug_assert_eq!(
buffer_offset,
header_max_len + num_presence_bytes,
"buffer_offset mismatch"
);
self.fixed_length_arcs_buffer.reset_position()?;
self.fixed_length_arcs_buffer.write_byte(if continuous {
ARCS_FOR_CONTINUOUS
} else {
ARCS_FOR_DIRECT_ADDRESSING
})?;
self.fixed_length_arcs_buffer.write_vint(label_range)?; self
.fixed_length_arcs_buffer
.write_vint(max_bytes_per_arc_without_label)?; let header_len = self.fixed_length_arcs_buffer.get_position();
self.scratch_bytes.set_position(0)?;
self.scratch_bytes.write_bytes_range(
self.fixed_length_arcs_buffer.get_bytes(),
0,
header_len,
)?;
if !continuous {
self.write_presence_bits(node_in_idx)?;
debug_assert_eq!(
self.scratch_bytes.get_position(),
header_len + num_presence_bytes
);
}
self.scratch_bytes.write_bytes_range(
self.fixed_length_arcs_buffer.get_bytes(),
buffer_offset,
total_arc_bytes,
)?;
debug_assert_eq!(
self.scratch_bytes.get_position(),
header_len + num_presence_bytes + total_arc_bytes
);
Ok(())
}
fn write_presence_bits(&mut self, node_in_idx: usize) -> Result<()> {
let mut presence_bits: u8 = 1; let mut presence_index = 0;
let node_in = &self.frontier[node_in_idx];
let mut previous_label = node_in.arcs[0].label;
let byte_size = i8::BITS as i32;
for arc_idx in 1..node_in.num_arcs {
let label = node_in.arcs[arc_idx].label;
debug_assert!(label > previous_label);
presence_index += label - previous_label;
while presence_index >= byte_size {
self.scratch_bytes.write_byte(presence_bits)?;
presence_bits = 0;
presence_index -= byte_size;
}
presence_bits |= 1 << presence_index;
previous_label = label;
}
debug_assert!({
let last_label = node_in.arcs[node_in.num_arcs - 1].label;
let first_label = node_in.arcs[0].label;
presence_index == (last_label - first_label) % 8
});
debug_assert!(presence_bits != 0); debug_assert!((presence_bits & (1 << presence_index)) != 0);
self.scratch_bytes.write_byte(presence_bits)?;
Ok(())
}
pub(crate) fn set_empty_output(&mut self, v: Option<O::V>) -> Result<()> {
if let Some(existing) = &mut self.fst.metadata.empty_output {
self.fst.metadata.empty_output = Some(self.fst.outputs.merge(existing, &v)?);
} else {
self.fst.metadata.empty_output = Some(v);
}
Ok(())
}
pub(crate) fn finish(&mut self, mut new_start_node: i64) -> Result<()> {
debug_assert!(new_start_node <= self.num_bytes_written);
if self.fst.metadata.start_node != -1 {
return Err(LuceneError::illegal_state("already finished"));
}
if new_start_node == FINAL_END_NODE && self.fst.metadata.empty_output.is_some() {
new_start_node = 0;
}
self.fst.metadata.start_node = new_start_node;
self.fst.metadata.num_bytes = self.num_bytes_written;
match self.data_output {
DataOutputEnum::FromDir(_) => {
},
DataOutputEnum::ReadWriter(ref mut rw) => {
rw.freeze()?;
},
}
Ok(())
}
pub fn fst_ram_bytes_used(&self) -> Result<i64> {
let mut ram_bytes_used = self.scratch_bytes.ram_bytes_used()?;
ram_bytes_used += self.data_output.ram_bytes_used()?;
Ok(ram_bytes_used)
}
pub fn fst_size_in_bytes(&self) -> i64 {
self.num_bytes_written
}
}
pub(crate) struct NullFSTReader;
impl Accountable for NullFSTReader {
fn ram_bytes_used(&self) -> Result<i64> {
Ok(0)
}
}
impl FstReader for NullFSTReader {
type FstBytesReader = DummyBytesReader;
fn get_reverse_bytes_reader(&self) -> Result<Self::FstBytesReader> {
Err(LuceneError::unsupported_operation(
"FST was not constructed with getOnHeapReaderWriter()",
))
}
fn write_to<DO>(&self, _out: &mut DO) -> Result<()>
where
DO: DataOutput,
{
Err(LuceneError::unsupported_operation(
"FST was not constructed with getOnHeapReaderWriter()",
))
}
}
pub struct Builder<O, DO>
where
O: Outputs,
DO: IndexOutput,
{
input_type: InputType,
outputs: O,
suffix_ram_limit_mb: f64,
allow_fixed_length_arcs: bool,
data_output: Option<DataOutputEnum<DO>>,
direct_addressing_max_oversizing_factor: f32,
version: i32,
}
impl<O, DO> Builder<O, DO>
where
O: Outputs,
DO: IndexOutput,
{
pub fn new(input_type: InputType, outputs: O) -> Self {
Self {
input_type,
outputs,
suffix_ram_limit_mb: 32.0,
allow_fixed_length_arcs: true,
data_output: None,
direct_addressing_max_oversizing_factor: DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR,
version: VERSION_CURRENT,
}
}
pub fn suffix_ram_limit_mb(&mut self, mb: f64) -> Result<()> {
if mb < 0f64 {
return Err(LuceneError::illegal_argument(format!(
"suffix_ram_limit_mb must be >= 0; got: {mb}"
)));
}
self.suffix_ram_limit_mb = mb;
Ok(())
}
pub fn allow_fixed_length_arcs(&mut self, allow: bool) {
self.allow_fixed_length_arcs = allow;
}
pub fn data_output(&mut self, data_output: DataOutputEnum<DO>) {
self.data_output = Some(data_output);
}
pub fn with_direct_addressing_max_oversizing_factor(&mut self, factor: f32) {
self.direct_addressing_max_oversizing_factor = factor;
}
pub fn with_version(&mut self, version: i32) -> Result<()> {
if !(VERSION_90..=VERSION_CURRENT).contains(&version) {
return Err(LuceneError::illegal_argument(format!(
"Version must be in range [{} - {}]; got: {}",
VERSION_90, VERSION_CURRENT, version
)));
}
self.version = version;
Ok(())
}
pub fn build(mut self) -> Result<FSTCompiler<O, DO>> {
let data_output = match self.data_output.take() {
Some(data_output) => data_output,
None => DataOutputEnum::ReadWriter(get_on_heap_reader_writer(15)?),
};
FSTCompiler::new(
self.input_type,
self.suffix_ram_limit_mb,
self.outputs,
self.allow_fixed_length_arcs,
data_output,
self.direct_addressing_max_oversizing_factor,
self.version,
)
}
}
pub enum DataOutputEnum<O> {
FromDir(O),
ReadWriter(ReadWriteDataOutput),
}
impl<O> Display for DataOutputEnum<O>
where
O: Display,
{
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
match self {
DataOutputEnum::FromDir(data_output) => {
write!(f, "{data_output}")
},
DataOutputEnum::ReadWriter(_) => {
write!(f, "ReadWriteDataOutput")
},
}
}
}
impl<O> Accountable for DataOutputEnum<O> {
fn ram_bytes_used(&self) -> Result<i64> {
match self {
DataOutputEnum::FromDir(_) => Ok(0),
DataOutputEnum::ReadWriter(data_output) => data_output.ram_bytes_used(),
}
}
}
impl<O> Closeable for DataOutputEnum<O>
where
O: Closeable,
{
fn close(&mut self) -> Result<()> {
match self {
DataOutputEnum::FromDir(data_output) => data_output.close(),
DataOutputEnum::ReadWriter(_) => Ok(()),
}
}
}
impl<O> FstReader for DataOutputEnum<O> {
type FstBytesReader = ReverseBytesReader;
fn get_reverse_bytes_reader(&self) -> Result<Self::FstBytesReader> {
match self {
DataOutputEnum::FromDir(_) => Err(LuceneError::unsupported_operation("")),
DataOutputEnum::ReadWriter(rw) => match rw.get_reverse_bytes_reader()? {
BytesReaderEnum2::A(_) => Err(LuceneError::illegal_state(
"FSTCompiler reader must use a contiguous byte buffer",
)),
BytesReaderEnum2::B(reader) => Ok(reader),
},
}
}
fn write_to<DO>(&self, out: &mut DO) -> Result<()>
where
DO: DataOutput,
{
match self {
DataOutputEnum::FromDir(_) => Err(LuceneError::unsupported_operation("")),
DataOutputEnum::ReadWriter(rw) => rw.write_to(out),
}
}
}
impl<O> DataOutput for DataOutputEnum<O>
where
O: DataOutput,
{
fn write_byte(&mut self, b: u8) -> Result<()> {
match self {
DataOutputEnum::FromDir(data_output) => data_output.write_byte(b),
DataOutputEnum::ReadWriter(rw) => rw.write_byte(b),
}
}
fn write_bytes_range(&mut self, b: &[u8], offset: usize, length: usize) -> Result<()> {
match self {
DataOutputEnum::FromDir(data_output) => data_output.write_bytes_range(b, offset, length),
DataOutputEnum::ReadWriter(rw) => rw.write_bytes_range(b, offset, length),
}
}
}
pub(crate) struct Arc<T> {
pub label: i32, pub target: NodeEnum,
pub is_final: bool,
pub output: Option<T>,
pub next_final_output: Option<T>,
}
#[allow(dead_code)] pub(crate) trait Node {
fn is_compiled(&self) -> bool;
}
pub(crate) enum NodeEnum {
UnCompiledNode,
CompiledNode(CompiledNode),
}
impl Node for NodeEnum {
fn is_compiled(&self) -> bool {
match self {
NodeEnum::UnCompiledNode => false,
NodeEnum::CompiledNode(node) => node.is_compiled(),
}
}
}
pub(crate) struct CompiledNode {
pub(crate) node: i64,
}
impl Node for CompiledNode {
fn is_compiled(&self) -> bool {
true
}
}
pub(crate) struct UnCompiledNode<T> {
pub(crate) num_arcs: usize,
pub(crate) arcs: SmallVec<[Arc<T>; 1]>,
pub(crate) output: Option<T>,
pub(crate) is_final: bool,
pub depth: i32,
}
impl<T> UnCompiledNode<T>
where
T: OutputsBound,
{
pub(crate) fn new(depth: usize) -> Self {
Self {
num_arcs: 0,
arcs: SmallVec::new(),
output: None,
is_final: false,
depth: depth as i32,
}
}
pub(crate) fn clear(&mut self) {
self.num_arcs = 0;
self.is_final = false;
self.output = None;
}
pub(crate) fn get_last_output(&self, label_to_match: i32) -> &Option<T> {
debug_assert!(self.num_arcs > 0);
debug_assert!(self.arcs[self.num_arcs - 1].label == label_to_match);
&self.arcs[self.num_arcs - 1].output
}
pub(crate) fn add_arc(&mut self, label: i32, target: NodeEnum) -> Result<()> {
debug_assert!(label >= 0);
debug_assert!(
self.num_arcs == 0 || label > self.arcs[self.num_arcs - 1].label,
"arc[numArcs-1].label={} new label={} numArcs={}",
self.arcs[self.num_arcs - 1].label,
label,
self.num_arcs
);
if self.num_arcs == self.arcs.len() {
self.arcs.push(Arc {
label,
target,
is_final: false,
output: None,
next_final_output: None,
});
self.num_arcs += 1;
return Ok(());
}
let arc = &mut self.arcs[self.num_arcs];
self.num_arcs += 1;
arc.label = label;
arc.target = target;
arc.output = None;
arc.next_final_output = None;
arc.is_final = false;
Ok(())
}
pub(crate) fn replace_last(
&mut self,
label_to_match: i32,
target: NodeEnum,
next_final_output: Option<T>,
is_final: bool,
) {
debug_assert!(self.num_arcs > 0);
let arc = &mut self.arcs[self.num_arcs - 1];
debug_assert_eq!(
arc.label, label_to_match,
"arc.label={} vs {}",
arc.label, label_to_match
);
arc.target = target;
arc.next_final_output = next_final_output;
arc.is_final = is_final;
}
pub(crate) fn set_last_output(
&mut self,
label_to_match: i32,
new_output: Option<T>,
) -> &Option<T> {
debug_assert!(self.num_arcs > 0);
let arc = &mut self.arcs[self.num_arcs - 1];
debug_assert_eq!(arc.label, label_to_match);
arc.output = new_output;
&arc.output
}
pub(crate) fn prepend_output<O>(&mut self, output_prefix: &Option<O::V>, outputs: &O)
where
O: Outputs<V = T>,
{
for i in 0..self.num_arcs {
let current = &mut self.arcs[i].output;
match outputs.add(output_prefix, current) {
None => *current = None,
Some(std::borrow::Cow::Borrowed(next))
if current
.as_ref()
.is_some_and(|value| std::ptr::eq(next, value)) => {},
Some(std::borrow::Cow::Borrowed(next)) => *current = Some(next.clone()),
Some(std::borrow::Cow::Owned(next)) => *current = Some(next),
}
}
if self.is_final {
match outputs.add(output_prefix, &self.output) {
None => self.output = None,
Some(std::borrow::Cow::Borrowed(next))
if self
.output
.as_ref()
.is_some_and(|value| std::ptr::eq(next, value)) => {},
Some(std::borrow::Cow::Borrowed(next)) => self.output = Some(next.clone()),
Some(std::borrow::Cow::Owned(next)) => self.output = Some(next),
}
}
}
}
impl<T> Node for UnCompiledNode<T>
where
T: OutputsBound,
{
fn is_compiled(&self) -> bool {
false
}
}
pub(crate) struct FixedLengthArcsBuffer {
bado: ByteArrayDataOutput<Vec<u8>>,
}
impl FixedLengthArcsBuffer {
pub(crate) fn new() -> Self {
let bytes = Vec::new();
let bado = ByteArrayDataOutput::with_bytes(bytes);
Self { bado }
}
pub(crate) fn ensure_capacity(&mut self, capacity: usize) -> Result<()> {
if self.bado.bytes.len() < capacity {
ArrayUtil::grow_no_copy(&mut self.bado.bytes, capacity, || 0)?;
self.bado.reset()?;
}
Ok(())
}
pub(crate) fn reset_position(&mut self) -> Result<()> {
if self.bado.bytes.is_empty() {
self.ensure_capacity(11)?;
return Ok(());
}
self.bado.reset()
}
pub(crate) fn write_byte(&mut self, b: u8) -> Result<()> {
self.bado.write_byte(b)
}
pub(crate) fn write_vint(&mut self, i: i32) -> Result<()> {
self.bado.write_vint(i)
}
pub(crate) fn get_position(&self) -> usize {
self.bado.get_position()
}
pub(crate) fn get_bytes(&mut self) -> &mut [u8] {
&mut self.bado.bytes
}
}
pub(crate) const DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR: f32 = 1.0;
pub(crate) const FIXED_LENGTH_ARC_SHALLOW_DEPTH: usize = 3;
pub(crate) const FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS: usize = 5;
pub(crate) const FIXED_LENGTH_ARC_DEEP_NUM_ARCS: usize = 10;
const DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR: f32 = 1.66;
pub fn get_on_heap_reader_writer(block_bits: i32) -> Result<ReadWriteDataOutput> {
ReadWriteDataOutput::new(block_bits, true)
}