flashsieve 0.1.3

//! Query and lookup methods for [`MmapBlockIndex`](crate::mmap_index::MmapBlockIndex).

use crate::error::{Error, Result};
use crate::filter::{ByteFilter, NgramFilter};
use crate::index::CandidateRange;
use crate::mmap_index::MmapBlockIndex;
use crate::mmap_write::{ByteHistogramRef, NgramBloomRef};

impl MmapBlockIndex<'_> {
    /// Query using byte-level filtering on serialized bytes.
    ///
    /// Returns one range per indexed block that satisfies the byte filter.
    ///
    /// # Example
    ///
    /// ```
    /// use flashsieve::{BlockIndexBuilder, ByteFilter, MmapBlockIndex};
    ///
    /// let bytes = BlockIndexBuilder::new().block_size(256).build(b"secret").unwrap().to_bytes();
    /// let mmap = MmapBlockIndex::from_slice(&bytes).unwrap();
    /// let filter = ByteFilter::from_patterns(&[b"secret".as_slice()]);
    /// let candidates = mmap.candidate_blocks_byte(&filter);
    /// assert!(!candidates.is_empty());
    /// ```
    #[must_use]
    pub fn candidate_blocks_byte(&self, filter: &ByteFilter) -> Vec<CandidateRange> {
        let block_count = self.block_metas.len();
        if block_count == 0 {
            return Vec::new();
        }
        let mut seen = vec![false; block_count];
        for index in 0..block_count {
            let h = self.block_histogram(self.block_metas[index].offset);
            if byte_filter_matches_histogram(filter, h) {
                seen[index] = true;
                continue;
            }
            if index > 0 {
                let prev_h = self.block_histogram(self.block_metas[index - 1].offset);
                if byte_filter_matches_histogram_pair(filter, prev_h, h) {
                    seen[index - 1] = true;
                    seen[index] = true;
                }
            }
        }
        for index in 1..block_count {
            if seen[index] && !seen[index - 1] {
                let prev_h = self.block_histogram(self.block_metas[index - 1].offset);
                if filter.has_any_required_byte(prev_h) {
                    seen[index - 1] = true;
                }
            }
        }

        let mut results = Vec::new();
        for (index, is_seen) in seen.into_iter().enumerate() {
            if is_seen {
                if let Some(c) = self.candidate_for_index(index) {
                    results.push(c);
                }
            }
        }
        crate::BlockIndex::merge_adjacent(&results)
    }

    /// Query using n-gram filtering on serialized bytes.
    ///
    /// Returns one range per indexed block that satisfies the n-gram filter.
    ///
    /// # Example
    ///
    /// ```
    /// use flashsieve::{BlockIndexBuilder, MmapBlockIndex, NgramFilter};
    ///
    /// let bytes = BlockIndexBuilder::new().block_size(256).build(b"secret").unwrap().to_bytes();
    /// let mmap = MmapBlockIndex::from_slice(&bytes).unwrap();
    /// let filter = NgramFilter::from_patterns(&[b"secret".as_slice()]);
    /// let candidates = mmap.candidate_blocks_ngram(&filter);
    /// assert!(!candidates.is_empty());
    /// ```
    #[must_use]
    pub fn candidate_blocks_ngram(&self, filter: &NgramFilter) -> Vec<CandidateRange> {
        let block_count = self.block_metas.len();
        if block_count == 0 {
            return Vec::new();
        }

        let window_blocks = filter
            .max_pattern_bytes()
            .div_ceil(self.block_size)
            .max(1)
            .saturating_add(1)
            .min(block_count);
        let mut seen = vec![false; block_count];

        for index in 0..block_count {
            let bloom = self.block_bloom(self.block_metas[index]);
            if ngram_filter_matches_bloom(filter, bloom) {
                seen[index] = true;
                continue;
            }

            if index == 0 {
                continue;
            }

            let prev_bloom = self.block_bloom(self.block_metas[index - 1]);
            if ngram_filter_matches_bloom_pair(filter, prev_bloom, bloom) {
                seen[index - 1] = true;
                seen[index] = true;
                continue;
            }

            let earliest_start = index.saturating_sub(window_blocks - 1);
            for window_start in earliest_start..index.saturating_sub(1) {
                let end = index + 1;
                let b_refs: Vec<_> = (window_start..end)
                    .map(|i| self.block_bloom(self.block_metas[i]))
                    .collect();
                if ngram_filter_matches_bloom_multi(filter, &b_refs) {
                    for item in seen.iter_mut().take(end).skip(window_start) {
                        *item = true;
                    }
                    break;
                }
            }
        }

        let union = filter.union_ngrams();
        if !union.is_empty() {
            for index in 1..block_count {
                if seen[index] && !seen[index - 1] {
                    let prev_bloom = self.block_bloom(self.block_metas[index - 1]);
                    if prev_bloom.maybe_contains_any(union) {
                        seen[index - 1] = true;
                    }
                }
            }
        }

        let mut results = Vec::new();
        for (index, is_seen) in seen.into_iter().enumerate() {
            if is_seen {
                if let Some(c) = self.candidate_for_index(index) {
                    results.push(c);
                }
            }
        }
        crate::BlockIndex::merge_adjacent(&results)
    }
    /// Query candidate blocks directly from the serialized histograms/blooms.
    ///
    /// # Example
    ///
    /// ```
    /// use flashsieve::{BlockIndexBuilder, ByteFilter, MmapBlockIndex, NgramFilter};
    ///
    /// let bytes = BlockIndexBuilder::new().block_size(256).build(b"secret").unwrap().to_bytes();
    /// let mmap = MmapBlockIndex::from_slice(&bytes).unwrap();
    /// let bf = ByteFilter::from_patterns(&[b"secret".as_slice()]);
    /// let nf = NgramFilter::from_patterns(&[b"secret".as_slice()]);
    /// let candidates = mmap.candidate_blocks(&bf, &nf);
    /// assert!(!candidates.is_empty());
    /// ```
    #[must_use]
    pub fn candidate_blocks(
        &self,
        byte_filter: &ByteFilter,
        ngram_filter: &NgramFilter,
    ) -> Vec<CandidateRange> {
        let paired_compact = byte_filter.compact_requirements();
        let paired_ngrams = ngram_filter.pattern_ngrams();
        let is_paired = paired_compact.len() == paired_ngrams.len();
        let use_exact = self
            .block_metas
            .first()
            .is_some_and(|meta| self.block_bloom(*meta).uses_exact_pairs());

        let block_count = self.block_metas.len();
        if block_count == 0 {
            return Vec::new();
        }

        let window_blocks = ngram_filter
            .max_pattern_bytes()
            .div_ceil(self.block_size)
            .max(1)
            .saturating_add(1)
            .min(block_count);
        let mut seen = vec![false; block_count];

        for index in 0..block_count {
            let block_meta = self.block_metas[index];
            let histogram = self.block_histogram(block_meta.offset);
            let bloom = self.block_bloom(block_meta);

            let single_match = if is_paired {
                if use_exact {
                    paired_compact
                        .iter()
                        .zip(paired_ngrams)
                        .any(|(required_bytes, ngrams)| {
                            required_bytes.iter().all(|&b| histogram.count(b) > 0)
                                && ngrams.iter().all(|&(first, second)| {
                                    bloom.maybe_contains_exact(first, second)
                                })
                        })
                } else {
                    paired_compact
                        .iter()
                        .zip(paired_ngrams)
                        .any(|(required_bytes, ngrams)| {
                            required_bytes.iter().all(|&b| histogram.count(b) > 0)
                                && ngrams.iter().all(|&(first, second)| {
                                    bloom.maybe_contains_bloom(first, second)
                                })
                        })
                }
            } else {
                byte_filter_matches_histogram(byte_filter, histogram)
                    && ngram_filter_matches_bloom(ngram_filter, bloom)
            };

            if single_match {
                seen[index] = true;
                continue;
            }

            if index == 0 {
                continue;
            }

            let prev_meta = self.block_metas[index - 1];
            let prev_histogram = self.block_histogram(prev_meta.offset);
            let prev_bloom = self.block_bloom(prev_meta);

            let pair_match = if is_paired {
                if use_exact {
                    paired_compact
                        .iter()
                        .zip(paired_ngrams)
                        .any(|(required_bytes, ngrams)| {
                            required_bytes
                                .iter()
                                .all(|&b| histogram.count(b) > 0 || prev_histogram.count(b) > 0)
                                && ngrams.iter().all(|&(first, second)| {
                                    bloom.maybe_contains_exact(first, second)
                                        || prev_bloom.maybe_contains_exact(first, second)
                                })
                        })
                } else {
                    paired_compact
                        .iter()
                        .zip(paired_ngrams)
                        .any(|(required_bytes, ngrams)| {
                            required_bytes
                                .iter()
                                .all(|&b| histogram.count(b) > 0 || prev_histogram.count(b) > 0)
                                && ngrams.iter().all(|&(first, second)| {
                                    bloom.maybe_contains_bloom(first, second)
                                        || prev_bloom.maybe_contains_bloom(first, second)
                                })
                        })
                }
            } else {
                byte_filter_matches_histogram_pair(byte_filter, prev_histogram, histogram)
                    && ngram_filter_matches_bloom_pair(ngram_filter, prev_bloom, bloom)
            };

            if pair_match {
                seen[index - 1] = true;
                seen[index] = true;
                continue;
            }

            // Multi-block window fallback for patterns spanning 3+ blocks
            let earliest_start = index.saturating_sub(window_blocks - 1);
            for window_start in earliest_start..index.saturating_sub(1) {
                let end = index + 1;
                let h_refs: Vec<_> = (window_start..end)
                    .map(|i| self.block_histogram(self.block_metas[i].offset))
                    .collect();
                let b_refs: Vec<_> = (window_start..end)
                    .map(|i| self.block_bloom(self.block_metas[i]))
                    .collect();

                let multi_match =
                    if is_paired {
                        if use_exact {
                            paired_compact.iter().zip(paired_ngrams).any(
                                |(required_bytes, ngrams)| {
                                    required_bytes
                                        .iter()
                                        .all(|&b| h_refs.iter().any(|h| h.count(b) > 0))
                                        && ngrams.iter().all(|&(first, second)| {
                                            b_refs.iter().any(|bloom| {
                                                bloom.maybe_contains_exact(first, second)
                                            })
                                        })
                                },
                            )
                        } else {
                            paired_compact.iter().zip(paired_ngrams).any(
                                |(required_bytes, ngrams)| {
                                    required_bytes
                                        .iter()
                                        .all(|&b| h_refs.iter().any(|h| h.count(b) > 0))
                                        && ngrams.iter().all(|&(first, second)| {
                                            b_refs.iter().any(|bloom| {
                                                bloom.maybe_contains_bloom(first, second)
                                            })
                                        })
                                },
                            )
                        }
                    } else {
                        byte_filter_matches_histogram_multi(byte_filter, &h_refs)
                            && ngram_filter_matches_bloom_multi(ngram_filter, &b_refs)
                    };

                if multi_match {
                    for item in seen.iter_mut().take(end).skip(window_start) {
                        *item = true;
                    }
                    break;
                }
            }
        }

        // Boundary safety: if block i matches and block i-1 contains any pattern
        // elements, a pattern might span the boundary.
        for index in 1..block_count {
            if seen[index] && !seen[index - 1] {
                let prev_meta = self.block_metas[index - 1];
                let prev_histogram = self.block_histogram(prev_meta.offset);
                let prev_bloom = self.block_bloom(prev_meta);
                let has_any =
                    if is_paired {
                        if use_exact {
                            paired_compact.iter().zip(paired_ngrams).any(
                                |(required_bytes, ngrams)| {
                                    required_bytes.iter().any(|&b| prev_histogram.count(b) > 0)
                                        || ngrams.iter().any(|&(first, second)| {
                                            prev_bloom.maybe_contains_exact(first, second)
                                        })
                                },
                            )
                        } else {
                            paired_compact.iter().zip(paired_ngrams).any(
                                |(required_bytes, ngrams)| {
                                    required_bytes.iter().any(|&b| prev_histogram.count(b) > 0)
                                        || ngrams.iter().any(|&(first, second)| {
                                            prev_bloom.maybe_contains_bloom(first, second)
                                        })
                                },
                            )
                        }
                    } else {
                        byte_filter
                            .compact_requirements()
                            .iter()
                            .any(|required_bytes| {
                                required_bytes.iter().any(|&b| prev_histogram.count(b) > 0)
                            })
                            || (!ngram_filter.union_ngrams().is_empty()
                                && prev_bloom.maybe_contains_any(ngram_filter.union_ngrams()))
                    };
                if has_any {
                    seen[index - 1] = true;
                }
            }
        }

        let mut results = Vec::new();
        for (index, is_seen) in seen.into_iter().enumerate() {
            if is_seen {
                if let Some(c) = self.candidate_for_index(index) {
                    results.push(c);
                }
            }
        }
        crate::BlockIndex::merge_adjacent(&results)
    }

    /// Get the byte histogram for a block. Deprecated; use `try_histogram` to avoid errors on out of bounds.
    ///
    /// # Panics
    ///
    /// Panics if `block_id` is out of range. Prefer [`Self::try_histogram`] for a
    /// fallible variant that returns [`Error::InvalidBlockId`] instead.
    #[must_use]
    #[deprecated(since = "0.2.0", note = "use `try_histogram` instead to avoid panics")]
    #[allow(clippy::panic)] // intentional fail-closed for deprecated infallible API; use try_histogram
    pub fn histogram(&self, block_id: usize) -> ByteHistogramRef<'_> {
        // Fail closed on an out-of-range block_id instead of returning a dummy
        // all-zero histogram (Law 10): a silent zero histogram reads downstream
        // as "this block contains no bytes", masking the bug and losing recall.
        // The deprecation note already advertises that this method panics; the
        // fallible `try_histogram` is the non-panicking variant.
        self.try_histogram(block_id).unwrap_or_else(|e| {
            panic!("MmapBlockIndex::histogram({block_id}): {e}; use try_histogram for a fallible variant")
        })
    }

    /// Access one block histogram without deserializing the whole index.
    ///
    /// # Errors
    ///
    /// Returns `Error::InvalidBlockId` if `block_id` is out of range.
    ///
    /// # Example
    ///
    /// ```
    /// use flashsieve::{BlockIndexBuilder, MmapBlockIndex};
    ///
    /// let bytes = BlockIndexBuilder::new().block_size(256).build(b"hello").unwrap().to_bytes();
    /// let mmap = MmapBlockIndex::from_slice(&bytes).unwrap();
    /// let hist = mmap.try_histogram(0).unwrap();
    /// assert_eq!(hist.count(b'h'), 1);
    /// ```
    pub fn try_histogram(&self, block_id: usize) -> Result<ByteHistogramRef<'_>> {
        let offset = self
            .block_offsets
            .get(block_id)
            .copied()
            .ok_or(Error::InvalidBlockId {
                block_id,
                block_count: self.block_count,
            })?;
        Ok(self.block_histogram(offset))
    }

    /// Get the bloom filter for a block. Deprecated; use `try_bloom` to avoid errors on out of bounds.
    ///
    /// # Panics
    ///
    /// Panics if `block_id` is out of range. Prefer [`Self::try_bloom`] for a
    /// fallible variant that returns [`Error::InvalidBlockId`] instead.
    #[must_use]
    #[deprecated(since = "0.2.0", note = "use `try_bloom` instead to avoid panics")]
    #[allow(clippy::panic)] // intentional fail-closed for deprecated infallible API; use try_bloom
    pub fn bloom(&self, block_id: usize) -> NgramBloomRef<'_> {
        // Fail closed on an out-of-range block_id instead of returning a dummy
        // empty bloom (Law 10): an empty bloom answers "contains nothing" to
        // every membership query, silently dropping recall for the block. The
        // deprecation note advertises that this method panics; `try_bloom` is the
        // fallible variant.
        self.try_bloom(block_id).unwrap_or_else(|e| {
            panic!("MmapBlockIndex::bloom({block_id}): {e}; use try_bloom for a fallible variant")
        })
    }

    /// Access one block bloom filter without deserializing the whole index.
    ///
    /// # Errors
    ///
    /// Returns `Error::InvalidBlockId` if `block_id` is out of range.
    ///
    /// # Example
    ///
    /// ```
    /// use flashsieve::{BlockIndexBuilder, MmapBlockIndex};
    ///
    /// let bytes = BlockIndexBuilder::new().block_size(256).build(b"ab").unwrap().to_bytes();
    /// let mmap = MmapBlockIndex::from_slice(&bytes).unwrap();
    /// let bloom = mmap.try_bloom(0).unwrap();
    /// assert!(bloom.maybe_contains_bloom(b'a', b'b'));
    /// ```
    pub fn try_bloom(&self, block_id: usize) -> Result<NgramBloomRef<'_>> {
        let block_meta = *self
            .block_metas
            .get(block_id)
            .ok_or(Error::InvalidBlockId {
                block_id,
                block_count: self.block_count,
            })?;
        Ok(self.block_bloom(block_meta))
    }
}

fn byte_filter_matches_histogram(filter: &ByteFilter, histogram: ByteHistogramRef<'_>) -> bool {
    if filter.compact_requirements().is_empty() {
        return false;
    }

    filter
        .compact_requirements()
        .iter()
        .any(|required_bytes| required_bytes.iter().all(|&byte| histogram.count(byte) > 0))
}

fn byte_filter_matches_histogram_pair(
    filter: &ByteFilter,
    h1: ByteHistogramRef<'_>,
    h2: ByteHistogramRef<'_>,
) -> bool {
    let requirements = filter.compact_requirements();
    if requirements.is_empty() {
        return false;
    }
    requirements.iter().any(|required_bytes| {
        required_bytes
            .iter()
            .all(|&b| h1.count(b) > 0 || h2.count(b) > 0)
    })
}

fn byte_filter_matches_histogram_multi(
    filter: &ByteFilter,
    histograms: &[ByteHistogramRef<'_>],
) -> bool {
    let requirements = filter.compact_requirements();
    if requirements.is_empty() {
        return false;
    }
    requirements.iter().any(|required_bytes| {
        required_bytes
            .iter()
            .all(|&b| histograms.iter().any(|h| h.count(b) > 0))
    })
}

fn ngram_filter_matches_bloom_pair(
    filter: &NgramFilter,
    b1: NgramBloomRef<'_>,
    b2: NgramBloomRef<'_>,
) -> bool {
    let ngrams_list = filter.pattern_ngrams();
    if ngrams_list.is_empty() {
        return false;
    }

    if b1.uses_exact_pairs() && b2.uses_exact_pairs() {
        ngrams_list.iter().any(|ngrams| {
            ngrams.iter().all(|&(first, second)| {
                b1.maybe_contains_exact(first, second) || b2.maybe_contains_exact(first, second)
            })
        })
    } else {
        ngrams_list.iter().any(|ngrams| {
            ngrams.iter().all(|&(first, second)| {
                b1.maybe_contains_bloom(first, second) || b2.maybe_contains_bloom(first, second)
            })
        })
    }
}

fn ngram_filter_matches_bloom_multi(filter: &NgramFilter, blooms: &[NgramBloomRef<'_>]) -> bool {
    let ngrams_list = filter.pattern_ngrams();
    if ngrams_list.is_empty() {
        return false;
    }

    let use_exact = blooms.first().is_some_and(NgramBloomRef::uses_exact_pairs);
    if use_exact {
        ngrams_list.iter().any(|ngrams| {
            ngrams.iter().all(|&(first, second)| {
                blooms
                    .iter()
                    .any(|bloom| bloom.maybe_contains_exact(first, second))
            })
        })
    } else {
        ngrams_list.iter().any(|ngrams| {
            ngrams.iter().all(|&(first, second)| {
                blooms
                    .iter()
                    .any(|bloom| bloom.maybe_contains_bloom(first, second))
            })
        })
    }
}

fn ngram_filter_matches_bloom(filter: &NgramFilter, bloom: NgramBloomRef<'_>) -> bool {
    if filter.pattern_ngrams().is_empty() {
        return false;
    }

    // Fast early rejection: same rules as `NgramFilter::matches_bloom` (see filter.rs).
    let any_pattern_has_no_ngrams = filter.pattern_ngrams().iter().any(Vec::is_empty);
    let union_ngrams = filter.union_ngrams();
    if !any_pattern_has_no_ngrams
        && !union_ngrams.is_empty()
        && !bloom.maybe_contains_any(union_ngrams)
    {
        return false;
    }

    if bloom.uses_exact_pairs() {
        filter.pattern_ngrams().iter().any(|ngrams| {
            ngrams
                .iter()
                .all(|&(first, second)| bloom.maybe_contains_exact(first, second))
        })
    } else {
        filter.pattern_ngrams().iter().any(|ngrams| {
            ngrams
                .iter()
                .all(|&(first, second)| bloom.maybe_contains_bloom(first, second))
        })
    }
}