anda_db_tfs 0.11.0

/// Represents different types of boolean queries that can be parsed from a query string.
/// Supports Term, Or, And, and Not operations for building complex search expressions.
/// Operator precedence: OR < AND < NOT.
///
/// # Grammar (informal)
///
/// ```text
/// expr    := or_expr
/// or_expr := and_expr ( " OR " and_expr )*
/// and_expr := not_expr ( " AND " not_expr )*
/// not_expr := "NOT " term | term
/// term    := "(" or_expr ")" | word ( whitespace word )*
/// ```
///
/// Whitespace-separated words at the `term` level default to an implicit `OR`
/// between them, matching the behaviour of [`BM25Index::search`].
///
/// The parser is intentionally lenient: unbalanced parentheses are treated as
/// part of the surrounding text so that user input never causes a parse error.
///
/// # Examples
///
/// ```
/// use anda_db_tfs::QueryType;
///
/// let query = QueryType::parse("(hello AND world) OR (rust AND NOT java)");
/// ```
///
/// [`BM25Index::search`]: crate::BM25Index::search
#[derive(Debug, Clone, PartialEq)]
pub enum QueryType {
    /// A simple term query that matches a single word or phrase
    Term(String),

    /// A logical OR query that requires at least one subquery to match
    Or(Vec<Box<QueryType>>),

    /// A logical AND query that requires all subqueries to match
    And(Vec<Box<QueryType>>),

    /// A logical NOT query that negates the result of its subquery
    Not(Box<QueryType>),
}

const MAX_LOGICAL_QUERY_LEN: usize = 8 * 1024;
const MAX_LOGICAL_QUERY_DEPTH: usize = 64;
const MAX_LOGICAL_QUERY_NODES: usize = 1_024;
const MAX_LOGICAL_QUERY_BRANCHES: usize = 512;

impl QueryType {
    /// Parses a query string into a QueryType structure.
    ///
    /// This is the main entry point for converting a string query into a structured
    /// representation that can be used for searching.
    ///
    /// Parsing is total and stack-safe: parenthesis nesting deeper than the
    /// internal budget (64 levels) degrades leniently to plain terms instead
    /// of recursing further. Use [`QueryType::try_parse`] to reject oversized
    /// or overly complex input instead of degrading.
    ///
    /// # Arguments
    ///
    /// * `query` - A string slice containing the query to parse
    ///
    /// # Returns
    ///
    /// A QueryType representing the parsed query
    ///
    /// # Examples
    ///
    /// ```
    /// use anda_db_tfs::QueryType;
    ///
    /// let query = QueryType::parse("(hello AND world) OR (rust AND NOT java)");
    /// ```
    pub fn parse(query: &str) -> Self {
        let query = query.trim();
        if query.is_empty() {
            return QueryType::Or(vec![]);
        }

        Self::parse_or_expression(query, 0)
    }

    /// Parses a query string after applying resource-exhaustion guards.
    pub fn try_parse(query: &str) -> Result<Self, String> {
        validate_query_input(query)?;
        let query = Self::parse(query);
        query.validate_complexity()?;
        Ok(query)
    }

    /// Returns true when executing this AST may materialize a NOT complement.
    pub fn may_materialize_not_complement(&self) -> bool {
        may_materialize_not_complement(self, false)
    }

    fn validate_complexity(&self) -> Result<(), String> {
        let mut stats = QueryStats::default();
        validate_ast(self, 0, &mut stats)
    }

    /// Parses an OR expression, which has the lowest precedence in the query grammar.
    ///
    /// # Arguments
    ///
    /// * `query` - A string slice containing the query to parse
    ///
    /// # Returns
    ///
    /// A QueryType representing the parsed OR expression
    fn parse_or_expression(query: &str, depth: usize) -> Self {
        let parts: Vec<&str> = Self::split_top_level(query, " OR ");

        if parts.len() == 1 {
            return Self::parse_and_expression(parts[0], depth);
        }

        let subqueries: Vec<Box<QueryType>> = parts
            .into_iter()
            .map(|p| Box::new(Self::parse_and_expression(p, depth)))
            .collect();

        QueryType::Or(subqueries)
    }

    /// Parses an AND expression, which has medium precedence in the query grammar.
    ///
    /// # Arguments
    ///
    /// * `query` - A string slice containing the query to parse
    ///
    /// # Returns
    ///
    /// A QueryType representing the parsed AND expression
    fn parse_and_expression(query: &str, depth: usize) -> Self {
        let parts: Vec<&str> = Self::split_top_level(query, " AND ");

        if parts.len() == 1 {
            return Self::parse_not_expression(parts[0], depth);
        }

        let subqueries: Vec<Box<QueryType>> = parts
            .into_iter()
            .map(|p| Box::new(Self::parse_not_expression(p, depth)))
            .collect();

        QueryType::And(subqueries)
    }

    /// Parses a NOT expression, which has high precedence in the query grammar.
    ///
    /// # Arguments
    ///
    /// * `query` - A string slice containing the query to parse
    ///
    /// # Returns
    ///
    /// A QueryType representing the parsed NOT expression
    fn parse_not_expression(query: &str, depth: usize) -> Self {
        let query = query.trim();

        if let Some(stripped) = query.strip_prefix("NOT ") {
            return QueryType::Not(Box::new(Self::parse_term(stripped, depth)));
        }

        Self::parse_term(query, depth)
    }

    /// Parses a term or parenthesized expression, which has the highest precedence.
    ///
    /// # Arguments
    ///
    /// * `query` - A string slice containing the query to parse
    ///
    /// # Returns
    ///
    /// A QueryType representing the parsed term or parenthesized expression
    fn parse_term(query: &str, depth: usize) -> Self {
        let query = query.trim();

        // Handle parenthesized expressions.
        //
        // The parenthesis handling below recurses back into
        // `parse_or_expression`, so an adversarial run of parentheses could
        // otherwise grow the call stack linearly with the input. The public
        // `parse` entry point has no input-size guard (only `try_parse`
        // validates), therefore recursion is bounded here: once the nesting
        // budget is exhausted the rest of the input degrades to plain terms
        // instead of overflowing the stack (an abort that cannot be caught).
        if depth < MAX_LOGICAL_QUERY_DEPTH {
            if let Some(stripped) = query.strip_prefix('(') {
                // 处理可能存在的非平衡括号
                if stripped.ends_with(')') && Self::is_balanced_parentheses(query) {
                    // 完全平衡的括号表达式
                    return Self::parse_or_expression(&stripped[..stripped.len() - 1], depth + 1);
                } else {
                    // 处理不平衡的括号
                    // 1. 如果缺少右括号，尝试解析括号内的内容
                    return Self::parse_or_expression(stripped, depth + 1);
                }
            } else if query.ends_with(')') {
                // 处理只有右括号的情况。Strip ALL contiguous trailing ')' at
                // once: stripping one per recursion needs O(n) stack (and
                // O(n²) rescans) for a `")"` flood, which overflowed the
                // stack before this guard existed.
                return Self::parse_or_expression(query.trim_end_matches(')'), depth + 1);
            }
        }

        // Handle multiple terms (default to OR relationship)
        let terms: Vec<&str> = query.split_whitespace().collect();
        if terms.len() > 1 {
            let subqueries: Vec<Box<QueryType>> = terms
                .into_iter()
                .map(|t| Box::new(QueryType::Term(t.to_lowercase())))
                .collect();
            return QueryType::Or(subqueries);
        }

        // Handle single term
        if !query.is_empty() {
            return QueryType::Term(query.to_lowercase());
        }

        // Handle empty query
        QueryType::Or(vec![])
    }

    /// Checks if parentheses in a string are balanced.
    ///
    /// # Arguments
    ///
    /// * `s` - A string slice to check for balanced parentheses
    ///
    /// # Returns
    ///
    /// A boolean indicating whether the parentheses are balanced
    fn is_balanced_parentheses(s: &str) -> bool {
        let mut count = 0;

        for c in s.chars() {
            if c == '(' {
                count += 1;
            } else if c == ')' {
                count -= 1;
                if count < 0 {
                    return false;
                }
            }
        }

        count == 0
    }

    /// Splits a string at the top level by a delimiter, ignoring delimiters inside parentheses.
    /// Handles unbalanced parentheses by treating them as part of the text.
    ///
    /// This is a key function that enables proper parsing of nested expressions.
    ///
    /// # Arguments
    ///
    /// * `s` - A string slice to split
    /// * `delimiter` - The delimiter to split by
    ///
    /// # Returns
    ///
    /// A vector of string slices resulting from the split
    fn split_top_level<'a>(s: &'a str, delimiter: &str) -> Vec<&'a str> {
        // Delimiters (" OR ", " AND ") are pure ASCII, so byte-level comparison
        // is correct and inherently avoids UTF-8 char boundary issues.
        debug_assert!(delimiter.is_ascii());

        let mut result = Vec::new();
        let mut start = 0;
        let mut paren_count: u32 = 0;
        let bytes = s.as_bytes();
        let delim_bytes = delimiter.as_bytes();
        let delim_len = delim_bytes.len();
        let mut i = 0;

        while i < bytes.len() {
            match bytes[i] {
                b'(' => {
                    paren_count += 1;
                    i += 1;
                }
                b')' => {
                    paren_count = paren_count.saturating_sub(1);
                    i += 1;
                }
                _ if paren_count == 0
                    && i + delim_len <= bytes.len()
                    && bytes[i..i + delim_len] == *delim_bytes =>
                {
                    // Safety: start and i are always at ASCII boundaries,
                    // which are valid UTF-8 char boundaries.
                    result.push(s[start..i].trim());
                    i += delim_len;
                    start = i;
                }
                _ => {
                    i += 1;
                }
            }
        }

        result.push(s[start..].trim());
        result
    }
}

fn may_materialize_not_complement(query: &QueryType, negated_not: bool) -> bool {
    match query {
        QueryType::Term(_) => false,
        QueryType::Not(subquery) => !negated_not || may_materialize_not_complement(subquery, false),
        QueryType::Or(subqueries) => subqueries
            .iter()
            .any(|query| may_materialize_not_complement(query, false)),
        QueryType::And(subqueries) => {
            if subqueries.is_empty() {
                return false;
            }
            if subqueries.len() == 1 {
                return may_materialize_not_complement(&subqueries[0], false);
            }

            let has_positive = subqueries
                .iter()
                .any(|query| !matches!(query.as_ref(), QueryType::Not(_)));
            if has_positive {
                return subqueries
                    .iter()
                    .filter(|query| !matches!(query.as_ref(), QueryType::Not(_)))
                    .any(|query| may_materialize_not_complement(query, false))
                    || subqueries
                        .iter()
                        .filter(|query| matches!(query.as_ref(), QueryType::Not(_)))
                        .any(|query| may_materialize_not_complement(query, true));
            }

            let mut negatives = subqueries.iter();
            if let Some(first) = negatives.next()
                && may_materialize_not_complement(first, false)
            {
                return true;
            }

            negatives.any(|query| may_materialize_not_complement(query, true))
        }
    }
}

#[derive(Default)]
struct QueryStats {
    nodes: usize,
    branches: usize,
}

fn validate_query_input(query: &str) -> Result<(), String> {
    if query.len() > MAX_LOGICAL_QUERY_LEN {
        return Err(format!(
            "logical query length {} exceeds maximum {MAX_LOGICAL_QUERY_LEN}",
            query.len()
        ));
    }

    // Count both directions: a flood of ')' (or other unmatched closing
    // parentheses) previously bypassed this guard entirely because only '('
    // contributed to the depth, while each unmatched ')' still costs the
    // parser a recursion step.
    let mut depth = 0usize;
    let mut max_depth = 0usize;
    let mut unmatched_close = 0usize;
    for ch in query.chars() {
        match ch {
            '(' => {
                depth = depth.saturating_add(1);
                max_depth = max_depth.max(depth);
                if max_depth > MAX_LOGICAL_QUERY_DEPTH {
                    return Err(format!(
                        "logical query parenthesis depth exceeds maximum {MAX_LOGICAL_QUERY_DEPTH}"
                    ));
                }
            }
            ')' => {
                if depth == 0 {
                    unmatched_close += 1;
                    if unmatched_close > MAX_LOGICAL_QUERY_DEPTH {
                        return Err(format!(
                            "logical query unmatched closing parenthesis count exceeds maximum {MAX_LOGICAL_QUERY_DEPTH}"
                        ));
                    }
                } else {
                    depth -= 1;
                }
            }
            _ => {}
        }
    }

    Ok(())
}

fn validate_ast(query: &QueryType, depth: usize, stats: &mut QueryStats) -> Result<(), String> {
    if depth > MAX_LOGICAL_QUERY_DEPTH {
        return Err(format!(
            "logical query AST depth exceeds maximum {MAX_LOGICAL_QUERY_DEPTH}"
        ));
    }

    stats.nodes = stats.nodes.saturating_add(1);
    if stats.nodes > MAX_LOGICAL_QUERY_NODES {
        return Err(format!(
            "logical query AST node count exceeds maximum {MAX_LOGICAL_QUERY_NODES}"
        ));
    }

    match query {
        QueryType::Term(_) => Ok(()),
        QueryType::Not(query) => validate_ast(query, depth + 1, stats),
        QueryType::Or(queries) | QueryType::And(queries) => {
            stats.branches = stats.branches.saturating_add(queries.len());
            if stats.branches > MAX_LOGICAL_QUERY_BRANCHES {
                return Err(format!(
                    "logical query AST branch count exceeds maximum {MAX_LOGICAL_QUERY_BRANCHES}"
                ));
            }
            for query in queries {
                validate_ast(query, depth + 1, stats)?;
            }
            Ok(())
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Tests parsing a simple term query
    #[test]
    fn test_simple_term() {
        assert_eq!(
            QueryType::parse("hello"),
            QueryType::Term("hello".to_string())
        );
    }

    /// Tests parsing an AND query
    #[test]
    fn test_and_query() {
        assert_eq!(
            QueryType::parse("hello AND world"),
            QueryType::And(vec![
                Box::new(QueryType::Term("hello".to_string())),
                Box::new(QueryType::Term("world".to_string()))
            ])
        );
    }

    /// Tests parsing an OR query
    #[test]
    fn test_or_query() {
        assert_eq!(
            QueryType::parse("hello OR world"),
            QueryType::Or(vec![
                Box::new(QueryType::Term("hello".to_string())),
                Box::new(QueryType::Term("world".to_string()))
            ])
        );
    }

    /// Tests parsing a NOT query
    #[test]
    fn test_not_query() {
        assert_eq!(
            QueryType::parse("NOT hello"),
            QueryType::Not(Box::new(QueryType::Term("hello".to_string())))
        );
    }

    /// Tests parsing a complex query with nested expressions
    #[test]
    fn test_complex_query() {
        assert_eq!(
            QueryType::parse("(hello AND world) OR (rust AND NOT java)"),
            QueryType::Or(vec![
                Box::new(QueryType::And(vec![
                    Box::new(QueryType::Term("hello".to_string())),
                    Box::new(QueryType::Term("world".to_string()))
                ])),
                Box::new(QueryType::And(vec![
                    Box::new(QueryType::Term("rust".to_string())),
                    Box::new(QueryType::Not(Box::new(QueryType::Term(
                        "java".to_string()
                    ))))
                ]))
            ])
        );
    }

    /// Tests parsing queries with unbalanced parentheses
    #[test]
    fn test_unbalanced_parentheses() {
        // 缺少右括号
        assert_eq!(
            QueryType::parse("(hello AND world"),
            QueryType::And(vec![
                Box::new(QueryType::Term("hello".to_string())),
                Box::new(QueryType::Term("world".to_string()))
            ])
        );

        // 缺少左括号
        assert_eq!(
            QueryType::parse("hello AND world)"),
            QueryType::And(vec![
                Box::new(QueryType::Term("hello".to_string())),
                Box::new(QueryType::Term("world".to_string()))
            ])
        );

        // 嵌套括号不平衡
        assert_eq!(
            QueryType::parse("(hello AND (world OR rust)"),
            QueryType::And(vec![
                Box::new(QueryType::Term("hello".to_string())),
                Box::new(QueryType::Or(vec![
                    Box::new(QueryType::Term("world".to_string())),
                    Box::new(QueryType::Term("rust".to_string()))
                ]))
            ])
        );
    }

    /// Tests that multi-byte UTF-8 characters don't cause panic in split_top_level
    #[test]
    fn test_multibyte_utf8_query() {
        // 纯中文词，不应 panic
        assert_eq!(
            QueryType::parse("巨蟹"),
            QueryType::Term("巨蟹".to_string())
        );

        // 中文词 AND 英文词
        assert_eq!(
            QueryType::parse("巨蟹 AND rust"),
            QueryType::And(vec![
                Box::new(QueryType::Term("巨蟹".to_string())),
                Box::new(QueryType::Term("rust".to_string()))
            ])
        );

        // 中文词 OR 中文词
        assert_eq!(
            QueryType::parse("巨蟹 OR 天蝎"),
            QueryType::Or(vec![
                Box::new(QueryType::Term("巨蟹".to_string())),
                Box::new(QueryType::Term("天蝎".to_string()))
            ])
        );

        // 带括号的中文表达式
        assert_eq!(
            QueryType::parse("(巨蟹 AND 座) OR 天蝎"),
            QueryType::Or(vec![
                Box::new(QueryType::And(vec![
                    Box::new(QueryType::Term("巨蟹".to_string())),
                    Box::new(QueryType::Term("座".to_string()))
                ])),
                Box::new(QueryType::Term("天蝎".to_string()))
            ])
        );

        // NOT + 中文词
        assert_eq!(
            QueryType::parse("NOT 巨蟹"),
            QueryType::Not(Box::new(QueryType::Term("巨蟹".to_string())))
        );

        // 多个中文词（默认 OR 关系）
        assert_eq!(
            QueryType::parse("巨蟹 天蝎 双鱼"),
            QueryType::Or(vec![
                Box::new(QueryType::Term("巨蟹".to_string())),
                Box::new(QueryType::Term("天蝎".to_string())),
                Box::new(QueryType::Term("双鱼".to_string()))
            ])
        );
    }

    #[test]
    fn try_parse_rejects_excessive_parenthesis_depth() {
        let query = format!("{}hello{}", "(".repeat(MAX_LOGICAL_QUERY_DEPTH + 1), ")");
        assert!(QueryType::try_parse(&query).is_err());
    }

    #[test]
    fn try_parse_rejects_close_parenthesis_flood() {
        // Regression: a ')' flood used to bypass validate_query_input (which
        // only counted '(') and overflow the stack inside parse_term.
        let query = format!("x{}", ")".repeat(MAX_LOGICAL_QUERY_DEPTH + 1));
        assert!(QueryType::try_parse(&query).is_err());

        // Within the guard budget the query still parses leniently.
        let query = format!("x{}", ")".repeat(MAX_LOGICAL_QUERY_DEPTH));
        assert_eq!(
            QueryType::try_parse(&query).unwrap(),
            QueryType::Term("x".to_string())
        );
    }

    #[test]
    fn parse_survives_parenthesis_floods_without_stack_overflow() {
        // Regression: the unguarded public `parse` used to recurse once per
        // trailing ')', so `"x" + ")"*8190` aborted with a stack overflow in
        // debug builds. Contiguous ')' runs are now stripped in one step.
        let query = format!("x{}", ")".repeat(8190));
        assert_eq!(QueryType::parse(&query), QueryType::Term("x".to_string()));

        // Far past any length guard: still O(1) recursion.
        let query = format!("x{}", ")".repeat(1_000_000));
        assert_eq!(QueryType::parse(&query), QueryType::Term("x".to_string()));

        // '(' floods recurse once per '(' but are cut off by the depth budget.
        let query = format!("{}hello", "(".repeat(1_000_000));
        let _ = QueryType::parse(&query);

        // Spaced ')' floods cannot be stripped in one pass; the depth budget
        // caps the recursion and the rest degrades to plain terms.
        let query = format!("x{}", " )".repeat(100_000));
        let _ = QueryType::parse(&query);

        // Alternating unbalanced parentheses.
        let query = ")(".repeat(500_000);
        let _ = QueryType::parse(&query);
    }

    #[test]
    fn parse_close_paren_stripping_matches_old_semantics() {
        // Trailing ')' stripping must keep the lenient-parse results.
        assert_eq!(
            QueryType::parse("hello AND world))"),
            QueryType::And(vec![
                Box::new(QueryType::Term("hello".to_string())),
                Box::new(QueryType::Term("world".to_string()))
            ])
        );
        assert_eq!(
            QueryType::parse("a) OR b)"),
            QueryType::Or(vec![
                Box::new(QueryType::Term("a".to_string())),
                Box::new(QueryType::Term("b".to_string()))
            ])
        );
        assert_eq!(
            QueryType::parse("NOT NOT a))"),
            QueryType::Not(Box::new(QueryType::Not(Box::new(QueryType::Term(
                "a".to_string()
            )))))
        );
        assert_eq!(QueryType::parse(")))"), QueryType::Or(vec![]));
    }

    #[test]
    fn not_complement_detection_distinguishes_and_not_filter() {
        let query = QueryType::try_parse("hello AND NOT world").unwrap();
        assert!(!query.may_materialize_not_complement());

        let query = QueryType::try_parse("hello OR NOT world").unwrap();
        assert!(query.may_materialize_not_complement());

        let query = QueryType::try_parse("hello AND NOT (world AND NOT rust)").unwrap();
        assert!(!query.may_materialize_not_complement());

        let query = QueryType::try_parse("hello AND NOT (world OR NOT rust)").unwrap();
        assert!(query.may_materialize_not_complement());

        let query = QueryType::try_parse("hello AND NOT (NOT world)").unwrap();
        assert!(query.may_materialize_not_complement());
    }
}