luci/query/

wildcard.rs

//! Wildcard query: match terms using * (any chars) and ? (single char).
//!
//! Compiles the wildcard pattern to an unanchored regex string, then to
//! a `RegexAutomaton` (DFA implementing `fst::Automaton`). Term
//! enumeration happens via `reader.automaton_search` — FST/DFA
//! intersection that prunes non-matching subtrees via `can_match`.
//! Same primitive `levenshtein_automata::DFA` uses for fuzzy and
//! `RegexpQuery` uses for general regex.
//!
//! For trailing-wildcard patterns like `tech*` the DFA's `can_match`
//! naturally prunes the FST to the literal-prefix subtree (no separate
//! fast path needed). For non-trailing patterns like `*ology` or
//! `t?ch` the DFA still drives O(matching subtrees) work — this is
//! the fix that closes the leading-wildcard performance gap.
//!
//! Uses **per-segment rewrite**: term enumeration happens inside
//! `scorer_supplier(reader)` for each segment, not globally at `bind()`.
//! Matched terms are unioned via [`ConstantScoreMultiTermSupplier`]
//! (shared `FilterScorer` + `BufferedUnionScorer`), matching Lucene's
//! `MultiTermQueryConstantScoreBlendedWrapper`. Every matching doc
//! receives a constant score of 1.0.
//!
//! See [[fix-wildcard-fuzzy-quadratic-dedup]],
//! [[optimization-multiterm-constant-score-rewrite]], and
//! [[optimization-regexp-wildcard-fst-automaton]].

use crate::core::{Result, ScoreMode};
use regex::Regex;

use crate::query::multi_term::ConstantScoreMultiTermSupplier;
use crate::query::regex_automaton::RegexAutomaton;
use crate::query::{BoundQuery, Query, ScorerSupplier};
use crate::search::searcher::Searcher;
use crate::segment::reader::SegmentReader;

/// Wildcard query: * matches any sequence, ? matches single character.
pub struct WildcardQuery {
    pub field: String,
    pub pattern: String,
}

impl WildcardQuery {
    /// Check if a term matches the wildcard pattern (for tests).
    pub fn matches(pattern: &str, term: &str) -> bool {
        let regex_pattern = wildcard_to_regex_anchored(pattern);
        Regex::new(&regex_pattern)
            .map(|re| re.is_match(term))
            .unwrap_or(false)
    }
}

/// Convert a wildcard pattern to an unanchored regex pattern (for the
/// `RegexAutomaton` path — anchoring is handled by the DFA's
/// `StartKind::Anchored` configuration).
/// `*` → `.*`, `?` → `.`, other regex meta chars are escaped.
fn wildcard_to_regex_unanchored(pattern: &str) -> String {
    let mut regex = String::with_capacity(pattern.len() * 2);
    for ch in pattern.chars() {
        match ch {
            '*' => regex.push_str(".*"),
            '?' => regex.push('.'),
            '.' | '+' | '(' | ')' | '[' | ']' | '{' | '}' | '\\' | '^' | '$' | '|' => {
                regex.push('\\');
                regex.push(ch);
            }
            _ => regex.push(ch),
        }
    }
    regex
}

/// Anchored variant for the legacy `WildcardQuery::matches` test helper.
fn wildcard_to_regex_anchored(pattern: &str) -> String {
    let mut s = String::with_capacity(pattern.len() * 2 + 2);
    s.push('^');
    s.push_str(&wildcard_to_regex_unanchored(pattern));
    s.push('$');
    s
}

impl Query for WildcardQuery {
    fn bind(&self, _searcher: &Searcher, _score_mode: ScoreMode) -> Result<Box<dyn BoundQuery>> {
        let regex_pattern = wildcard_to_regex_unanchored(&self.pattern);
        let automaton = RegexAutomaton::new(&regex_pattern)?;
        Ok(Box::new(BoundWildcardQuery {
            field: self.field.clone(),
            automaton,
        }))
    }
}

/// Bound wildcard query — defers term enumeration to per-segment
/// `scorer_supplier(reader)` calls via `automaton_search`.
struct BoundWildcardQuery {
    field: String,
    automaton: RegexAutomaton,
}

impl BoundQuery for BoundWildcardQuery {
    fn scorer_supplier(&self, reader: &SegmentReader) -> Result<Option<Box<dyn ScorerSupplier>>> {
        let field_id = match reader
            .header()
            .fields
            .iter()
            .find(|f| f.field_name == self.field)
            .map(|f| f.field_id)
        {
            Some(id) => id,
            None => return Ok(None),
        };

        // FST/DFA intersection — prunes non-matching subtrees via the
        // automaton's can_match. Trailing wildcards (tech*) naturally
        // narrow to the literal-prefix subtree; leading and middle
        // wildcards (*ology, t?ch) still drive O(matching subtrees)
        // work instead of O(all terms in field).
        let terms: Vec<(String, u32)> = reader.automaton_search(field_id, &self.automaton);
        if terms.is_empty() {
            return Ok(None);
        }

        Ok(Some(Box::new(ConstantScoreMultiTermSupplier::new(
            reader, field_id, terms,
        ))))
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::analysis::Token;
    use crate::core::{FieldId, SegmentId};
    use crate::mapping::{FieldType, Mapping};
    use crate::segment::builder::SegmentBuilder;
    use crate::segment::reader::SegmentReader;

    #[test]
    fn wildcard_matching() {
        assert!(WildcardQuery::matches("tech*", "technology"));
        assert!(WildcardQuery::matches("tech*", "tech"));
        assert!(!WildcardQuery::matches("tech*", "tec"));
        assert!(WildcardQuery::matches("t?ch", "tech"));
        assert!(!WildcardQuery::matches("t?ch", "touch"));
        assert!(WildcardQuery::matches("*fox*", "quick fox jumps"));
        assert!(WildcardQuery::matches("*", "anything"));
        assert!(WildcardQuery::matches("?", "x"));
        assert!(!WildcardQuery::matches("?", ""));
        assert!(WildcardQuery::matches("a*b", "ab"));
        assert!(WildcardQuery::matches("a*b", "aXYZb"));
        assert!(!WildcardQuery::matches("a*b", "aXYZc"));
    }

    #[test]
    fn wildcard_query_star() {
        let schema = Mapping::builder().field("tag", FieldType::Keyword).build();
        let mut builder = SegmentBuilder::new(SegmentId::new(1), &schema);
        for tag in &["technology", "technical", "tennis", "science"] {
            builder.add_document(
                &[(FieldId::new(0), vec![Token::new(*tag, 0, tag.len(), 0)])],
                b"{}",
            );
        }
        let reader = SegmentReader::open(builder.build()).unwrap();
        let store = crate::search::segment_store::SegmentStore::new(
            vec![reader],
            crate::analysis::AnalyzerRegistry::new(),
            None,
            None,
        );
        let searcher = Searcher::new(&store);

        let results = searcher
            .search_query(
                &WildcardQuery {
                    field: "tag".into(),
                    pattern: "tech*".into(),
                },
                10,
                0,
            )
            .unwrap();
        assert_eq!(results.total_hits.value, 2); // technology, technical
    }

    #[test]
    fn wildcard_query_question_mark() {
        let schema = Mapping::builder().field("tag", FieldType::Keyword).build();
        let mut builder = SegmentBuilder::new(SegmentId::new(1), &schema);
        for tag in &["cat", "cut", "cot", "cart"] {
            builder.add_document(
                &[(FieldId::new(0), vec![Token::new(*tag, 0, tag.len(), 0)])],
                b"{}",
            );
        }
        let reader = SegmentReader::open(builder.build()).unwrap();
        let store = crate::search::segment_store::SegmentStore::new(
            vec![reader],
            crate::analysis::AnalyzerRegistry::new(),
            None,
            None,
        );
        let searcher = Searcher::new(&store);

        let results = searcher
            .search_query(
                &WildcardQuery {
                    field: "tag".into(),
                    pattern: "c?t".into(),
                },
                10,
                0,
            )
            .unwrap();
        assert_eq!(results.total_hits.value, 3); // cat, cut, cot (not cart — 4 chars)
    }

    #[test]
    fn wildcard_constant_score_all_ones() {
        // Multi-term wildcard match: every hit should score exactly 1.0,
        // matching ES's CONSTANT_SCORE_BLENDED_REWRITE behavior.
        // See [[optimization-multiterm-constant-score-rewrite]].
        let schema = Mapping::builder().field("tag", FieldType::Keyword).build();
        let mut builder = SegmentBuilder::new(SegmentId::new(1), &schema);
        for tag in &["technology", "technical", "tennis", "science"] {
            builder.add_document(
                &[(FieldId::new(0), vec![Token::new(*tag, 0, tag.len(), 0)])],
                b"{}",
            );
        }
        let reader = SegmentReader::open(builder.build()).unwrap();
        let store = crate::search::segment_store::SegmentStore::new(
            vec![reader],
            crate::analysis::AnalyzerRegistry::new(),
            None,
            None,
        );
        let searcher = Searcher::new(&store);

        let results = searcher
            .search_query(
                &WildcardQuery {
                    field: "tag".into(),
                    pattern: "tech*".into(),
                },
                10,
                0,
            )
            .unwrap();
        assert_eq!(results.total_hits.value, 2);
        for hit in &results.hits {
            assert_eq!(
                hit.score, 1.0,
                "wildcard hit should have constant score 1.0, got {}",
                hit.score
            );
        }
    }

    #[test]
    fn wildcard_high_cardinality_constant_score() {
        // Stress the multi-term BufferedUnionScorer path (>>1 sub-scorer)
        // with constant scoring. This is the unit-test analogue of the
        // UMLS wildcard benchmark — exercises window refilling and
        // sub-scorer exhaustion logic at unit-test speed.
        let schema = Mapping::builder().field("tag", FieldType::Keyword).build();
        let mut builder = SegmentBuilder::new(SegmentId::new(1), &schema);
        for i in 0..1000 {
            let tag = format!("tag_{i:04}");
            builder.add_document(
                &[(FieldId::new(0), vec![Token::new(&tag, 0, tag.len(), 0)])],
                b"{}",
            );
        }
        let reader = SegmentReader::open(builder.build()).unwrap();
        let store = crate::search::segment_store::SegmentStore::new(
            vec![reader],
            crate::analysis::AnalyzerRegistry::new(),
            None,
            None,
        );
        let searcher = Searcher::new(&store);

        let results = searcher
            .search_query(
                &WildcardQuery {
                    field: "tag".into(),
                    pattern: "tag_*".into(),
                },
                1000,
                0,
            )
            .unwrap();
        assert_eq!(results.total_hits.value, 1000);
        assert_eq!(results.hits.len(), 1000);
        for hit in &results.hits {
            assert_eq!(
                hit.score, 1.0,
                "high-cardinality wildcard hit should score 1.0, got {}",
                hit.score
            );
        }
    }

    #[test]
    fn wildcard_no_matches() {
        let schema = Mapping::builder().field("tag", FieldType::Keyword).build();
        let mut builder = SegmentBuilder::new(SegmentId::new(1), &schema);
        builder.add_document(
            &[(FieldId::new(0), vec![Token::new("hello", 0, 5, 0)])],
            b"{}",
        );
        let reader = SegmentReader::open(builder.build()).unwrap();
        let store = crate::search::segment_store::SegmentStore::new(
            vec![reader],
            crate::analysis::AnalyzerRegistry::new(),
            None,
            None,
        );
        let searcher = Searcher::new(&store);

        let results = searcher
            .search_query(
                &WildcardQuery {
                    field: "tag".into(),
                    pattern: "xyz*".into(),
                },
                10,
                0,
            )
            .unwrap();
        assert_eq!(results.total_hits.value, 0);
    }

    #[test]
    fn wildcard_leading_wildcard_correctness() {
        // Regression sentinel: leading-wildcard hit set must be
        // identical before and after the FST automaton intersection
        // change. See [[optimization-regexp-wildcard-fst-automaton]].
        let schema = Mapping::builder().field("tag", FieldType::Keyword).build();
        let mut builder = SegmentBuilder::new(SegmentId::new(1), &schema);
        for tag in &["technology", "ecology", "biology", "tennis"] {
            builder.add_document(
                &[(FieldId::new(0), vec![Token::new(*tag, 0, tag.len(), 0)])],
                b"{}",
            );
        }
        let reader = SegmentReader::open(builder.build()).unwrap();
        let store = crate::search::segment_store::SegmentStore::new(
            vec![reader],
            crate::analysis::AnalyzerRegistry::new(),
            None,
            None,
        );
        let searcher = Searcher::new(&store);

        let results = searcher
            .search_query(
                &WildcardQuery {
                    field: "tag".into(),
                    pattern: "*ology".into(),
                },
                10,
                0,
            )
            .unwrap();
        // technology, ecology, biology — all end with "ology"
        assert_eq!(results.total_hits.value, 3);
        for hit in &results.hits {
            assert_eq!(hit.score, 1.0);
        }
    }

    #[test]
    fn wildcard_middle_wildcard_correctness() {
        // Regression sentinel: middle-wildcard hit set must be
        // identical before and after the FST automaton intersection
        // change. See [[optimization-regexp-wildcard-fst-automaton]].
        let schema = Mapping::builder().field("tag", FieldType::Keyword).build();
        let mut builder = SegmentBuilder::new(SegmentId::new(1), &schema);
        for tag in &["bat1", "bet1", "bit1", "but2", "bat2"] {
            builder.add_document(
                &[(FieldId::new(0), vec![Token::new(*tag, 0, tag.len(), 0)])],
                b"{}",
            );
        }
        let reader = SegmentReader::open(builder.build()).unwrap();
        let store = crate::search::segment_store::SegmentStore::new(
            vec![reader],
            crate::analysis::AnalyzerRegistry::new(),
            None,
            None,
        );
        let searcher = Searcher::new(&store);

        let results = searcher
            .search_query(
                &WildcardQuery {
                    field: "tag".into(),
                    pattern: "b?t1".into(),
                },
                10,
                0,
            )
            .unwrap();
        // bat1, bet1, bit1 — all match b?t1; but2 and bat2 don't (end in 2)
        assert_eq!(results.total_hits.value, 3);
    }
}