#[cfg(test)]
use crate::core::codecs::hnsw::hnsw_graph_provider::HnswGraphProvider;
#[cfg(test)]
use crate::core::index::codec_reader::CodecReader;
#[cfg(test)]
use crate::core::index::index_reader::{
IndexReader, IndexReaderContextKind, IndexReaderContextType,
};
#[cfg(test)]
use crate::core::index::index_reader_context::{IRCLeafReader, IndexReaderContext};
use crate::core::search::doc_id_set_iterator::NO_MORE_DOCS;
use crate::core::util::bit_set::BitSet;
use crate::core::util::bits::Bits;
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::fixed_bit_set::FixedBitSet;
use crate::core::util::hnsw::hnsw_graph::{HnswGraph, NodesIterator};
use smallvec::SmallVec;
pub struct HnswUtil;
impl HnswUtil {
#[cfg(test)]
pub(crate) fn is_rooted<G>(hnsw: &mut G) -> Result<bool>
where
G: HnswGraph,
{
for level in 0..hnsw.num_levels()? {
let comps = Self::components(hnsw, level, None, 0)?;
if comps.len() > 1 {
return Ok(false);
}
}
Ok(true)
}
#[cfg(test)]
pub(crate) fn component_sizes<G>(hnsw: &mut G) -> Result<Vec<usize>>
where
G: HnswGraph,
{
Self::component_sizes_on_level(hnsw, 0)
}
#[cfg(test)]
pub(crate) fn component_sizes_on_level<G>(hnsw: &mut G, level: usize) -> Result<Vec<usize>>
where
G: HnswGraph,
{
let comps = Self::components(hnsw, level, None, 0)?;
Ok(comps.into_iter().map(|c| c.size).collect())
}
fn get_total<N, G>(
nodes_iter: N,
hnsw: &mut G,
level: usize,
mut not_fully_connected: Option<&mut FixedBitSet>,
connected_nodes: &mut FixedBitSet,
max_conn: usize,
stack: &mut SmallVec<[usize; 4]>,
) -> Result<usize>
where
N: Iterator<Item = usize>,
G: HnswGraph,
{
let mut total = 0;
for entry_point in nodes_iter {
let component = Self::mark_rooted(
hnsw,
level,
connected_nodes,
not_fully_connected.as_deref_mut(),
max_conn,
entry_point,
stack,
)?;
total += component.size;
}
Ok(total)
}
pub(crate) fn components<G>(
hnsw: &mut G,
level: usize,
mut not_fully_connected: Option<&mut FixedBitSet>,
max_conn: usize,
) -> Result<Vec<Component>>
where
G: HnswGraph,
{
let mut components = Vec::new();
debug_assert!(hnsw.size() <= i32::MAX as usize);
let mut connected_nodes = FixedBitSet::new(hnsw.size());
let mut stack = SmallVec::<[usize; 4]>::new();
debug_assert_eq!(hnsw.size(), hnsw.get_nodes_on_level(0)?.size());
if level >= hnsw.num_levels()? {
return Err(LuceneError::illegal_argument(format!(
"Level {} too large for graph with {} levels",
level,
hnsw.num_levels()?
)));
}
let mut total = if level == hnsw.num_levels()? - 1 {
let entry_point = hnsw.entry_node()?;
debug_assert!(entry_point.is_some());
let iter = std::iter::once(entry_point.unwrap_or(0));
Self::get_total(
iter,
hnsw,
level,
not_fully_connected.as_deref_mut(),
&mut connected_nodes,
max_conn,
&mut stack,
)?
} else {
let iter = hnsw.get_nodes_on_level(level + 1)?;
Self::get_total(
iter,
hnsw,
level,
not_fully_connected.as_deref_mut(),
&mut connected_nodes,
max_conn,
&mut stack,
)?
};
let entry_point = if let Some(nfc) = not_fully_connected.as_ref() {
nfc.next_set_bit(0)
} else {
connected_nodes.next_set_bit(0)
};
components.push(Component {
start: entry_point,
size: total,
});
if level == 0 {
let mut next_clear = Self::next_clear_bit(&connected_nodes, 0);
while next_clear != NO_MORE_DOCS as usize {
let component = Self::mark_rooted(
hnsw,
level,
&mut connected_nodes,
not_fully_connected.as_deref_mut(),
max_conn,
next_clear,
&mut stack,
)?;
debug_assert!(component.size > 0);
components.push(component);
total += component.size;
next_clear = Self::next_clear_bit(&connected_nodes, component.start);
}
} else {
let mut nodes = hnsw.get_nodes_on_level(level)?;
for node in &mut nodes {
if connected_nodes.get(node)? {
continue;
}
let component = Self::mark_rooted(
hnsw,
level,
&mut connected_nodes,
not_fully_connected.as_deref_mut(),
max_conn,
node,
&mut stack,
)?;
debug_assert!(component.size > 0);
components.push(component);
total += component.size;
}
}
debug_assert_eq!(
total,
hnsw.get_nodes_on_level(level)?.size(),
"Mismatch total={total} vs node size on level {level}"
);
Ok(components)
}
fn mark_rooted<G>(
hnsw_graph: &mut G,
level: usize,
connected_nodes: &mut FixedBitSet,
mut not_fully_connected: Option<&mut FixedBitSet>,
max_conn: usize,
entry_point: usize,
stack: &mut SmallVec<[usize; 4]>,
) -> Result<Component>
where
G: HnswGraph,
{
stack.clear();
stack.push(entry_point);
let mut count = 0;
while let Some(node) = stack.pop() {
if connected_nodes.get(node)? {
continue;
}
count += 1;
connected_nodes.set(node)?;
hnsw_graph.seek(level, node)?;
let mut friend_count = 0;
let mut friend_ord;
while {
friend_ord = hnsw_graph.next_neighbor()?;
friend_ord != NO_MORE_DOCS as usize
} {
friend_count += 1;
stack.push(friend_ord);
}
if friend_count < max_conn
&& let Some(nfc) = not_fully_connected.as_deref_mut()
{
nfc.set(node)?;
}
}
if stack.capacity() > (64 * 1024) / size_of::<usize>() {
*stack = SmallVec::new();
}
Ok(Component {
start: entry_point,
size: count,
})
}
fn next_clear_bit(bits: &FixedBitSet, index: usize) -> usize {
let barray = bits.get_bits();
debug_assert!(
index < bits.length(),
"index={}, num_bits={}",
index,
bits.length()
);
let mut i = index >> 6;
let mut word = !barray[i].wrapping_shr(index as u32);
let mut next: usize = NO_MORE_DOCS as usize;
if word != 0 {
next = index + word.trailing_zeros() as usize;
} else {
i += 1;
while i < barray.len() {
word = !barray[i];
if word != 0 {
next = (i << 6) + word.trailing_zeros() as usize;
break;
}
i += 1;
}
}
if next >= bits.length() {
NO_MORE_DOCS as usize
} else {
next
}
}
#[cfg(test)]
pub fn graph_is_rooted<IR>(reader: IR, vector_field: &str) -> Result<bool>
where
IR: IndexReader,
IR::ContextKind: IndexReaderContextKind<IR>,
IRCLeafReader<IndexReaderContextType<IR>>: CodecReader,
<IRCLeafReader<IndexReaderContextType<IR>> as CodecReader>::KnnVectorsReader: HnswGraphProvider,
{
let context = reader.get_context()?;
for leaf in context.leaves()? {
let vector_reader = leaf
.reader()
.get_vector_reader()?
.ok_or_else(|| LuceneError::illegal_state("vector reader is missing"))?;
if !vector_reader.is_hnsw_graph_provider(vector_field) {
return Err(LuceneError::illegal_state(format!(
"vector reader for field {vector_field} does not provide an HNSW graph"
)));
}
let mut graph = vector_reader.get_graph(vector_field)?;
if !Self::is_rooted(&mut graph)? {
return Ok(false);
}
}
Ok(true)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Component {
pub start: usize,
pub size: usize,
}