use crate::core::search::field_comparator::{FieldComparator, FieldComparatorEnum};
use crate::core::search::field_value_hit_queue::TopFieldScoreDoc;
use crate::core::search::pruning::Pruning;
use crate::core::search::score_doc::ScoreDocLike;
use crate::core::search::sort::Sort;
use crate::core::search::sort_field::SortFiledBase;
use crate::core::search::top_field_docs::TopFieldDocs;
use crate::core::search::total_hits::{Relation, TotalHits};
use crate::core::util::error::lucene_error::{LuceneError, Result};
use crate::core::util::priority_queue::{Compare, PriorityQueue};
use crate::core::util::{Comparator, ToInt};
use std::borrow::Borrow;
use std::marker::PhantomData;
#[derive(Clone)]
pub struct TopDocs<S> {
pub total_hits: TotalHits,
pub score_docs: Vec<S>,
}
impl<S> TopDocs<S> {
pub fn new<I>(total_hits: TotalHits, score_docs: I) -> Self
where
I: IntoIterator<Item = S>,
{
let score_docs = score_docs.into_iter().collect::<Vec<S>>();
Self {
total_hits,
score_docs,
}
}
}
pub fn merge_top_field_docs<I>(
sort: &Sort,
top_n: usize,
shard_hits: I,
) -> Result<TopFieldDocs>
where
I: IntoIterator,
I::Item: Borrow<TopDocs<TopFieldScoreDoc>>,
{
merge_top_field_docs_with_start(sort, 0, top_n, shard_hits)
}
pub fn merge_top_field_docs_with_start<I>(
sort: &Sort,
start: usize,
top_n: usize,
shard_hits: I,
) -> Result<TopFieldDocs>
where
I: IntoIterator,
I::Item: Borrow<TopDocs<TopFieldScoreDoc>>,
{
merge_top_field_docs_with_comparator(sort, start, top_n, shard_hits, DefaultTieBreaker::default())
}
pub fn merge_top_field_docs_with_comparator<C, I>(
sort: &Sort,
start: usize,
size: usize,
shard_hits: I,
tie_breaker: C,
) -> Result<TopFieldDocs>
where
C: Comparator<TopFieldScoreDoc>,
I: IntoIterator,
I::Item: Borrow<TopDocs<TopFieldScoreDoc>>,
{
let shard_hits = shard_hits.into_iter().collect::<Vec<I::Item>>();
let len = shard_hits.len();
let cmp = MergeSortQueueCmp::new(sort, &shard_hits, tie_breaker)?;
let queue = PriorityQueue::new(len, &cmp)?;
let (total_hits, hits) = merge_aux(queue, start, size, &shard_hits)?;
Ok(TopFieldDocs::new(total_hits, hits, sort.fields.clone()))
}
pub fn merge_top_docs<S, I>(top_n: usize, shard_hits: I) -> Result<TopDocs<S>>
where
S: ScoreDocLike,
I: IntoIterator,
I::Item: Borrow<TopDocs<S>>,
{
merge_top_docs_with_start(0, top_n, shard_hits)
}
pub fn merge_top_docs_with_start<S, I>(
start: usize,
top_n: usize,
shard_hits: I,
) -> Result<TopDocs<S>>
where
S: ScoreDocLike,
I: IntoIterator,
I::Item: Borrow<TopDocs<S>>,
{
merge_top_docs_with_comparator(start, top_n, shard_hits, DefaultTieBreaker::default())
}
pub fn merge_top_docs_with_comparator<C, S, I>(
start: usize,
size: usize,
shard_hits: I,
tie_breaker: C,
) -> Result<TopDocs<S>>
where
C: Comparator<S>,
S: ScoreDocLike,
I: IntoIterator,
I::Item: Borrow<TopDocs<S>>,
{
let shard_hits = shard_hits.into_iter().collect::<Vec<I::Item>>();
let len = shard_hits.len();
debug_assert!(len <= i32::MAX as usize);
let cmp = ScoreMergeSortQueueCmp::<_, S, _>::new(&shard_hits, tie_breaker);
let queue = PriorityQueue::new(len, &cmp)?;
let (total_hits, hits) = merge_aux(queue, start, size, &shard_hits)?;
Ok(TopDocs::new(total_hits, hits))
}
#[derive(Default)]
struct ShardIndexTieBreaker;
impl<S> Comparator<S> for ShardIndexTieBreaker
where
S: ScoreDocLike,
{
const TYPE: &'static str = "ShardIndexTieBreaker";
fn compare(&self, a: &S, b: &S) -> Result<i32> {
Ok(a.shard_index().cmp(&b.shard_index()).to_int())
}
}
#[derive(Default)]
struct DocIdTieBreaker;
impl<S> Comparator<S> for DocIdTieBreaker
where
S: ScoreDocLike,
{
const TYPE: &'static str = "DocIdTieBreaker";
fn compare(&self, a: &S, b: &S) -> Result<i32> {
Ok(a.doc().cmp(&b.doc()).to_int())
}
}
#[derive(Default)]
struct DefaultTieBreaker {
shard_cmp: ShardIndexTieBreaker,
doc_cmp: DocIdTieBreaker,
}
impl<S> Comparator<S> for DefaultTieBreaker
where
S: ScoreDocLike,
{
const TYPE: &'static str = "DefaultTieBreaker";
fn compare(&self, a: &S, b: &S) -> Result<i32> {
let res = self.shard_cmp.compare(a, b)?;
if res != 0 {
Ok(res)
} else {
self.doc_cmp.compare(a, b)
}
}
}
#[derive(Debug, Clone, Default)]
pub(crate) struct ShardRef {
pub(crate) shard_index: usize,
pub(crate) hit_index: usize,
}
impl ShardRef {
pub fn new(shard_index: usize) -> Self {
ShardRef {
shard_index,
hit_index: 0,
}
}
}
impl std::fmt::Display for ShardRef {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"ShardRef(shardIndex={} hitIndex={})",
self.shard_index, self.hit_index
)
}
}
pub(crate) fn tie_break_less_than<C, S>(
first: &ShardRef,
first_doc: &S,
second: &ShardRef,
second_doc: &S,
tie_breaker: &C,
) -> Result<bool>
where
C: Comparator<S>,
S: ScoreDocLike,
{
let value = tie_breaker.compare(first_doc, second_doc)?;
if value == 0 {
debug_assert!(first.hit_index != second.hit_index);
return Ok(first.hit_index < second.hit_index);
}
Ok(value < 0)
}
fn merge_aux<C, S, B>(
mut queue: PriorityQueue<ShardRef, C>,
start: usize,
size: usize,
shard_hits: &[B],
) -> Result<(TotalHits, Vec<S>)>
where
C: Compare<ShardRef>,
S: ScoreDocLike,
B: Borrow<TopDocs<S>>,
{
let mut total_hit_count: i64 = 0;
let mut total_hits_relation = Relation::EqualTo;
let mut avail_hit_count = 0;
for (shard_idx, shard) in shard_hits.iter().enumerate() {
let shard = shard.borrow();
total_hit_count = total_hit_count.wrapping_add(shard.total_hits.value as i64);
if shard.total_hits.relation == Relation::GreaterThanOrEqualTo {
total_hits_relation = Relation::GreaterThanOrEqualTo;
}
if !shard.score_docs.is_empty() {
avail_hit_count += shard.score_docs.len();
queue.add(ShardRef::new(shard_idx))?;
}
}
let mut hits: Vec<S>;
let mut unset_shard_index = false;
if avail_hit_count <= start {
hits = Vec::new();
} else {
let len = std::cmp::min(size, avail_hit_count - start);
hits = vec![S::default(); len];
let requested_result_window = start + size;
let num_iter_on_hits = std::cmp::min(avail_hit_count, requested_result_window);
let mut hit_upto = 0;
while hit_upto < num_iter_on_hits {
debug_assert!(queue.size() > 0);
let ref_ = match queue.top_mut() {
None => return Err(LuceneError::illegal_state("queue is empty")),
Some(v) => v,
};
let shard = shard_hits[ref_.shard_index].borrow();
let hit = &shard.score_docs[ref_.hit_index];
ref_.hit_index += 1;
if hit_upto > 0 && unset_shard_index != (hit.shard_index() == -1) {
return Err(LuceneError::illegal_argument(
"Inconsistent order of shard indices",
));
}
unset_shard_index |= hit.shard_index() == -1;
if hit_upto >= start {
hits[hit_upto - start] = hit.clone();
}
hit_upto += 1;
if ref_.hit_index < shard.score_docs.len() {
queue.update_top()?;
} else {
queue.pop_unchecked()?;
}
}
}
if total_hit_count < 0 {
return Err(LuceneError::illegal_argument(format!(
"value must be >= 0, got {total_hit_count}"
)));
}
Ok((
TotalHits::new(total_hit_count as usize, total_hits_relation),
hits,
))
}
pub(crate) struct ScoreMergeSortQueueCmp<'a, C, S, B = TopDocs<S>> {
shard_hits: &'a [B],
score_doc: PhantomData<fn() -> S>,
tie_breaker_comparator: C,
}
impl<'a, C, S, B> ScoreMergeSortQueueCmp<'a, C, S, B> {
pub fn new(shard_hits: &'a [B], tie_breaker_comparator: C) -> Self {
Self {
shard_hits,
score_doc: PhantomData,
tie_breaker_comparator,
}
}
}
impl<C, S, B> Compare<ShardRef> for ScoreMergeSortQueueCmp<'_, C, S, B>
where
C: Comparator<S>,
S: ScoreDocLike,
B: Borrow<TopDocs<S>>,
{
fn less_than(&self, first: &ShardRef, second: &ShardRef) -> Result<bool> {
let first_shard_hits = self.shard_hits[first.shard_index].borrow();
let second_shard_hits = self.shard_hits[second.shard_index].borrow();
let first_scorer_doc = &first_shard_hits.score_docs[first.hit_index];
let second_scorer_doc = &second_shard_hits.score_docs[second.hit_index];
let first_scorer_doc_score = first_scorer_doc.score();
let second_scorer_doc_score = second_scorer_doc.score();
if first_scorer_doc_score < second_scorer_doc_score {
Ok(false)
} else if first_scorer_doc_score > second_scorer_doc_score {
Ok(true)
} else {
tie_break_less_than(
first,
first_scorer_doc,
second,
second_scorer_doc,
&self.tie_breaker_comparator,
)
}
}
}
pub(crate) struct MergeSortQueueCmp<'a, C, B = TopDocs<TopFieldScoreDoc>> {
shard_hits: &'a [B],
comparators: Vec<FieldComparatorEnum>,
reverse_mul: Vec<i8>,
tie_breaker: C,
}
impl<'a, C, B> MergeSortQueueCmp<'a, C, B>
where
B: Borrow<TopDocs<TopFieldScoreDoc>>,
{
pub fn new(sort: &Sort, shard_hits: &'a [B], tie_breaker: C) -> Result<Self> {
for (shard_index, shard) in shard_hits.iter().enumerate() {
let shard = shard.borrow();
for score_doc in &shard.score_docs {
if score_doc.as_field().is_none() {
return Err(LuceneError::illegal_argument(format!(
"shard {shard_index} was not sorted by the provided Sort (expected FieldDoc but got ScoreDoc)"
)));
}
}
}
let mut comparators = Vec::with_capacity(sort.fields.len());
let mut reverse_mul = Vec::with_capacity(sort.fields.len());
for sf in &sort.fields {
comparators.push(sf.get_comparator(1, Pruning::None)?);
reverse_mul.push(if sf.get_reverse() { -1 } else { 1 });
}
Ok(Self {
shard_hits,
comparators,
reverse_mul,
tie_breaker,
})
}
}
impl<C, B> Compare<ShardRef> for MergeSortQueueCmp<'_, C, B>
where
C: Comparator<TopFieldScoreDoc>,
B: Borrow<TopDocs<TopFieldScoreDoc>>,
{
fn less_than(&self, first: &ShardRef, second: &ShardRef) -> Result<bool> {
let first_fd = &self.shard_hits[first.shard_index].borrow().score_docs[first.hit_index];
let second_fd = &self.shard_hits[second.shard_index].borrow().score_docs[second.hit_index];
let first_fields = first_fd.fields()?;
let second_fields = second_fd.fields()?;
for (i, comp) in self.comparators.iter().enumerate() {
let cmp = i32::from(self.reverse_mul[i])
* comp.compare_values(Some(&first_fields[i]), Some(&second_fields[i]))?;
if cmp != 0 {
return Ok(cmp < 0);
}
}
tie_break_less_than(first, first_fd, second, second_fd, &self.tie_breaker)
}
}
impl<S> TopDocsLike for TopDocs<S>
where
S: ScoreDocLike,
{
fn total_hits(&self) -> &TotalHits {
&self.total_hits
}
type ScoreDocLike = S;
fn score_docs(&self) -> &[Self::ScoreDocLike] {
&self.score_docs
}
fn score_docs_mut(&mut self) -> &mut [Self::ScoreDocLike] {
&mut self.score_docs
}
fn take_score_docs(&mut self) -> Vec<Self::ScoreDocLike> {
std::mem::take(&mut self.score_docs)
}
}
pub trait TopDocsLike {
fn total_hits(&self) -> &TotalHits;
type ScoreDocLike: ScoreDocLike;
fn score_docs(&self) -> &[Self::ScoreDocLike];
fn score_docs_mut(&mut self) -> &mut [Self::ScoreDocLike];
fn take_score_docs(&mut self) -> Vec<Self::ScoreDocLike>;
}