semlith 0.46.0

//! `semlith pattern`: a tree-sitter structural query over the indexed files of
//! one language.
//!
//! The question this answers is the one a regex cannot: "every call whose
//! receiver is `self.index`", "every struct with a lifetime parameter". The
//! graph already parses these files with these grammars; this exposes the
//! parser to a caller who knows what shape they are looking for.
//!
//! Two things keep it honest. The grammar comes from [`crate::graph`]'s own
//! table, so a language `pattern` accepts is a language the extractor accepts
//! and there is no second list to drift. And the text comes from the store's
//! chunks rather than from disk, for the reason [`crate::Semlith::read`] does:
//! the boundary that decided what may be indexed is the boundary that decides
//! what may be read back.

use crate::filter::Filter;
use crate::store;
use anyhow::{Result, bail};
use tree_sitter::{Parser, Query, QueryCursor, StreamingIterator};

/// How many captures one pattern will return before it stops and says so.
///
/// A pattern over a large store can match tens of thousands of nodes, and the
/// answer stops being useful long before it stops growing — the same reasoning
/// `graph::MAX_NODES` records for a traversal.
pub const MAX_MATCHES: usize = 200;

/// How many files one pattern will parse.
///
/// Parsing is the cost here: the store holds the text already, so the budget
/// is on syntax trees built rather than on bytes read.
pub const MAX_FILES: usize = 2000;

/// How long one pattern or grep call may run before it stops and says it was
/// cut short, as it does at [`MAX_MATCHES`] (audit S18). A query that has to
/// walk a planted file node by node, or a grep over a store of very long
/// lines, otherwise held its caller — an agent's MCP call, a portal request —
/// for as long as it took.
pub const TIME_BUDGET: std::time::Duration = std::time::Duration::from_secs(10);

/// How many in-progress matches tree-sitter keeps for one query at once; past
/// it the oldest are dropped. Bounds the memory a pathological pattern costs.
const IN_PROGRESS: u32 = 1024;

/// One captured node.
#[derive(Debug, Clone, serde::Serialize)]
pub struct Match {
    pub path: String,
    /// The capture's own name in the pattern, without the `@`.
    pub capture: String,
    pub start_line: u32,
    pub end_line: u32,
    /// The captured text, cut to one line's worth so a pattern that captures a
    /// whole `impl` block does not return the block.
    pub text: String,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub store: Option<String>,
}

/// What one pattern run produced.
#[derive(Debug, Clone, serde::Serialize)]
pub struct Matches {
    pub language: String,
    pub matches: Vec<Match>,
    /// Files parsed, so an empty answer can be told from an answer about
    /// nothing: "no file of that language is indexed" and "none of them match"
    /// are different facts.
    pub files: usize,
    /// True when [`MAX_MATCHES`] or [`MAX_FILES`] cut the answer short.
    pub truncated: bool,
    /// Matches this run passed over to honour the caller's `offset`.
    ///
    /// Reported so a fleet can carry one offset across several stores: the
    /// second store's offset is the caller's minus what the first one already
    /// skipped, and without this number there is nothing to subtract.
    pub skipped: usize,
}

/// Run `source` as a tree-sitter query over every indexed file of `language`.
///
/// The pattern is compiled once, before any file is read, so a syntax error in
/// it costs nothing and is reported as the parser's own message rather than as
/// an empty result — an agent that mistyped a pattern and was handed "no
/// matches" would conclude the code does not contain the shape.
/// `offset` continues a listing the cap cut short. The order is total — files
/// are sorted and the matches within a file are tree-sitter's — so the same
/// call with the same offset returns the same matches, which is what makes
/// paging through a cap meaningful rather than a second sample.
pub fn run(
    db: &rusqlite::Connection,
    language: &str,
    source: &str,
    filter: &Filter,
    offset: usize,
) -> Result<Matches> {
    let language = language.trim().to_ascii_lowercase();
    let Some(grammar) = crate::graph::language_grammar(&language) else {
        bail!(
            "no grammar for {language:?}; the languages with one are {}",
            crate::graph::languages().join(", ")
        );
    };
    let query = Query::new(&grammar, source)
        .map_err(|e| anyhow::anyhow!("that is not a valid tree-sitter pattern: {e:?}"))?;
    let names = query.capture_names().to_vec();

    // The language filter and whatever the caller asked for, intersected the
    // way every other surface intersects them — one id set, one predicate.
    let scoped = filter.and_language(&language)?;
    let files = store::file_rows(db, scoped.groups(), store::FileSort::Path, false, i64::MAX)?;

    let mut out = Vec::new();
    let mut parsed = 0usize;
    let mut truncated = false;
    let mut skipped = 0usize;
    let deadline = std::time::Instant::now() + TIME_BUDGET;
    for file in files.iter().take(MAX_FILES) {
        if out.len() >= MAX_MATCHES || std::time::Instant::now() >= deadline {
            truncated = true;
            break;
        }
        let Some(text) = file_text(db, &file.path)? else {
            continue;
        };
        // In the parse worker, as indexing parses: a grammar's C code that
        // aborts or reads out of bounds on a file costs one worker there, and
        // here it was the daemon (cargo-fuzz chunk_markdown, 0.41.0). A file
        // the worker could not finish is passed over, as an unparseable one
        // always was.
        let Ok(Ok(found)) = crate::worker::pattern(&language, source, &text) else {
            continue;
        };
        parsed += 1;
        for capture in found {
            if out.len() >= MAX_MATCHES {
                truncated = true;
                break;
            }
            // Skipped after the match is found, not before the file is read:
            // the offset is into the match sequence, and a file holding forty
            // matches contributes forty to it whether or not this call
            // renders them.
            if skipped < offset {
                skipped += 1;
                continue;
            }
            out.push(Match {
                path: file.path.clone(),
                capture: names
                    .get(capture.index as usize)
                    .map(|n| n.to_string())
                    .unwrap_or_default(),
                start_line: capture.start_row + 1,
                end_line: capture.end_row + 1,
                text: first_line(text.get(capture.start..capture.end).unwrap_or("")),
                store: None,
            });
        }
    }
    if files.len() > MAX_FILES {
        truncated = true;
    }

    Ok(Matches {
        language,
        matches: out,
        files: parsed,
        truncated,
        skipped,
    })
}

/// One captured node of a pattern, as the parse worker reports it.
#[derive(Debug, serde::Serialize, serde::Deserialize)]
pub struct Capture {
    pub index: u32,
    pub start_row: u32,
    pub end_row: u32,
    pub start: usize,
    pub end: usize,
}

/// How many captures one file contributes at most.
const PER_FILE: usize = 10_000;

/// A pattern's captures in one file's text, in tree-sitter's order: what the
/// parse worker runs for [`run`]. The parse and the query each stop at
/// [`TIME_BUDGET`].
pub(crate) fn captures(language: &str, source: &str, text: &str) -> Result<Vec<Capture>> {
    let Some(grammar) = crate::graph::language_grammar(language) else {
        bail!("no grammar for {language:?}");
    };
    // Past the nesting a block grammar survives, the file has no graph
    // either, and the parse would abort.
    if crate::graph::too_nested(language, text) {
        return Ok(Vec::new());
    }
    let query = Query::new(&grammar, source)
        .map_err(|e| anyhow::anyhow!("that is not a valid tree-sitter pattern: {e:?}"))?;
    let mut parser = Parser::new();
    parser.set_language(&grammar)?;
    let deadline = std::time::Instant::now() + TIME_BUDGET;
    let mut expired = |_: &tree_sitter::ParseState| {
        if std::time::Instant::now() >= deadline {
            std::ops::ControlFlow::Break(())
        } else {
            std::ops::ControlFlow::Continue(())
        }
    };
    let options = tree_sitter::ParseOptions::default().progress_callback(&mut expired);
    let parse = crate::graph::ctype_safe(language, text);
    let Some(tree) =
        parser.parse_with_options(&mut |at, _| &parse.as_bytes()[at..], None, Some(options))
    else {
        return Ok(Vec::new());
    };
    let mut cursor = QueryCursor::new();
    cursor.set_match_limit(IN_PROGRESS);
    let mut stop = |_: &tree_sitter::QueryCursorState| {
        if std::time::Instant::now() >= deadline {
            std::ops::ControlFlow::Break(())
        } else {
            std::ops::ControlFlow::Continue(())
        }
    };
    let options = tree_sitter::QueryCursorOptions::new().progress_callback(&mut stop);
    let mut hits = cursor.matches_with_options(&query, tree.root_node(), text.as_bytes(), options);
    let mut out = Vec::new();
    while let Some(m) = hits.next() {
        for capture in m.captures() {
            if out.len() >= PER_FILE {
                return Ok(out);
            }
            let node = capture.node;
            out.push(Capture {
                index: capture.index,
                start_row: node.start_position().row as u32,
                end_row: node.end_position().row as u32,
                start: node.start_byte(),
                end: node.end_byte(),
            });
        }
    }
    Ok(out)
}

/// Every indexed line matching `source`, as `grep -E` would find it.
///
/// The sweep an agent reached for grep to make: every marker comment, every struct
/// literal, every use of a string. Answered from the store's text, the boundary
/// [`run`] reads through, so a refused file stays unread. Each line carries
/// the definition it sits in, which is the next thing a grep user runs `awk`
/// to find. A query that is not a valid regular expression is taken as
/// literal text, because `Row {` is what someone typing a literal means.
///
/// `files` counts files searched and `truncated` means [`MAX_MATCHES`] or [`TIME_BUDGET`] cut the
/// listing, as for a pattern; `offset` pages through it the same way.
pub fn grep(
    db: &rusqlite::Connection,
    source: &str,
    filter: &Filter,
    offset: usize,
) -> Result<Matches> {
    let regex = regex::Regex::new(source)
        .or_else(|_| regex::Regex::new(&regex::escape(source)))
        .map_err(|e| anyhow::anyhow!("that query cannot be searched for: {e}"))?;
    let files = store::file_rows(db, filter.groups(), store::FileSort::Path, false, i64::MAX)?;
    let mut out = Vec::new();
    let mut searched = 0usize;
    let mut truncated = false;
    let mut skipped = 0usize;
    let deadline = std::time::Instant::now() + TIME_BUDGET;
    'files: for file in &files {
        if std::time::Instant::now() >= deadline {
            truncated = true;
            break;
        }
        let Some(text) = file_text(db, &file.path)? else {
            continue;
        };
        searched += 1;
        let mut symbols = None;
        for (i, line) in text.lines().enumerate() {
            if i % 4096 == 0 && std::time::Instant::now() >= deadline {
                truncated = true;
                break 'files;
            }
            if !regex.is_match(line) {
                continue;
            }
            if out.len() >= MAX_MATCHES {
                truncated = true;
                break 'files;
            }
            if skipped < offset {
                skipped += 1;
                continue;
            }
            // Read once per file with a match, not per file searched.
            if symbols.is_none() {
                symbols = Some(
                    store::symbols_in_files(db, std::slice::from_ref(&file.path))?
                        .remove(&file.path)
                        .unwrap_or_default(),
                );
            }
            let defs = symbols.as_deref().unwrap_or_default();
            let at = i as u32 + 1;
            out.push(Match {
                path: file.path.clone(),
                capture: crate::enclosing_definition(defs, at, at)
                    .map(|(_, name, _)| name)
                    .unwrap_or_default(),
                start_line: at,
                end_line: at,
                text: first_line(line),
                store: None,
            });
        }
    }
    Ok(Matches {
        language: String::new(),
        matches: out,
        files: searched,
        truncated,
        skipped,
    })
}

/// One file's text, stitched from the chunks the store holds.
///
/// Chunks overlap by two lines, so they are joined by line number rather than
/// concatenated — the seam would otherwise appear twice and every line after
/// it would be numbered wrongly, which for a tool whose whole output is line
/// numbers is the only thing that matters.
fn file_text(db: &rusqlite::Connection, path: &str) -> Result<Option<String>> {
    let chunks = store::chunks_overlapping(db, path, 1, u32::MAX)?;
    if chunks.is_empty() {
        return Ok(None);
    }
    // Keyed by line number: a scan of the lines so far for each new one was
    // quadratic in the file, which a grep over every file in the store pays.
    let mut lines: std::collections::BTreeMap<u32, String> = Default::default();
    for chunk in &chunks {
        for (offset, line) in chunk.text.lines().enumerate() {
            lines
                .entry(chunk.start_line + offset as u32)
                .or_insert_with(|| line.to_string());
        }
    }

    // A line no chunk holds -- a blank first line, a gap -- is kept as an empty
    // line, so every row the parser and the grep report is the file's own line
    // number. Dropping such a file instead hid twelve Markdown files on the
    // benchmark corpus from every exact search, and joining around a gap would
    // have shifted every line after it.
    let Some(&last) = lines.keys().next_back() else {
        return Ok(None);
    };
    let text = (1..=last)
        .map(|n| lines.get(&n).map_or("", String::as_str))
        .collect::<Vec<_>>()
        .join("\n");
    Ok(Some(text))
}

/// The first line of a captured node, trimmed.
///
/// A pattern that captures an `impl` block captures hundreds of lines, and a
/// caller who wanted those has `semlith read` and the span this row carries.
fn first_line(raw: &str) -> String {
    const WIDTH: usize = 120;
    let line = raw.lines().next().unwrap_or("").trim();
    if line.chars().count() <= WIDTH {
        return line.to_string();
    }
    line.chars().take(WIDTH).collect::<String>() + "…"
}

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

    /// A grep answers every matching line with the definition around it, and
    /// a query that is not a regular expression is searched as literal text.
    #[test]
    fn grep_finds_every_line_and_names_its_definition() {
        let db = rusqlite::Connection::open_in_memory().unwrap();
        db.execute_batch(store::SCHEMA).unwrap();
        db.execute_batch(
            "INSERT INTO files (id, path, hash, bytes, indexed_at) VALUES (1, '/r/a.rs', 'h', 1, 0);
             INSERT INTO chunks (id, file_id, ord, start_line, end_line, text)
               VALUES (1, 1, 0, 1, 4, 'fn one() {\n    // NOTE first\n}\nlet h = Row {');
             INSERT INTO chunks (id, file_id, ord, start_line, end_line, text)
               VALUES (2, 1, 1, 3, 6, '}\nlet h = Row {\nfn two() { // HACK second }\n');
             INSERT INTO symbols (file_id, name, qualified, kind, start_line, end_line)
               VALUES (1, 'one', 'one', 'function', 1, 3), (1, 'two', 'two', 'function', 5, 5);",
        )
        .unwrap();
        let found = grep(&db, r"\b(NOTE|HACK)\b", &Filter::default(), 0).unwrap();
        let rows: Vec<_> = found
            .matches
            .iter()
            .map(|m| (m.start_line, m.capture.as_str()))
            .collect();
        assert_eq!(rows, [(2, "one"), (5, "two")]);
        let literal = grep(&db, "Row {", &Filter::default(), 0).unwrap();
        assert_eq!(literal.matches.len(), 1, "{:?}", literal.matches);
        assert_eq!(literal.matches[0].start_line, 4);
    }

    /// A file whose stored chunks start past line 1, or leave a gap, is still
    /// searched, and every line keeps its own number. On the benchmark corpus
    /// twelve Markdown files whose first line held nothing were never searched,
    /// and a gap would have shifted every line number after it.
    #[test]
    fn grep_searches_a_file_that_does_not_start_at_line_one() {
        let db = rusqlite::Connection::open_in_memory().unwrap();
        db.execute_batch(store::SCHEMA).unwrap();
        db.execute_batch(
            "INSERT INTO files (id, path, hash, bytes, indexed_at) VALUES (1, '/r/a.md', 'h', 1, 0);
             INSERT INTO chunks (id, file_id, ord, start_line, end_line, text)
               VALUES (1, 1, 0, 3, 4, '# Title\nNEEDLE on four');
             INSERT INTO chunks (id, file_id, ord, start_line, end_line, text)
               VALUES (2, 1, 1, 7, 8, 'text\nNEEDLE on eight');",
        )
        .unwrap();
        let found = grep(&db, "NEEDLE", &Filter::default(), 0).unwrap();
        let lines: Vec<u32> = found.matches.iter().map(|m| m.start_line).collect();
        assert_eq!(lines, [4, 8], "{:?}", found.matches);
    }

    /// A pattern that does not compile is the caller's mistake and has to be
    /// reported as one. Handing back "no matches" would have the caller
    /// conclude the code does not contain the shape they asked about.
    #[test]
    fn an_invalid_pattern_is_an_error_rather_than_an_empty_answer() {
        let db = rusqlite::Connection::open_in_memory().unwrap();
        db.execute_batch(store::SCHEMA).unwrap();
        let err = run(&db, "rust", "(this is not a pattern", &Filter::default(), 0)
            .expect_err("an unbalanced pattern does not compile");
        assert!(
            err.to_string().contains("not a valid tree-sitter pattern"),
            "{err}"
        );
    }

    /// Every language the filter advertises compiles a pattern, because
    /// `pattern` and the extractor read the same grammar table.
    ///
    /// A pattern is the one surface where a missing grammar is an error a user
    /// sees rather than a silent absence of symbols, so it is asserted for all
    /// forty-six rather than assumed from the extractor's own gate.
    #[test]
    fn every_advertised_language_compiles_a_pattern() {
        let db = rusqlite::Connection::open_in_memory().unwrap();
        db.execute_batch(store::SCHEMA).unwrap();
        let mut broken: Vec<String> = Vec::new();
        for entry in crate::filter::LANGUAGES {
            if !crate::graph::has_graph(entry.name) {
                continue;
            }
            if let Err(e) = run(&db, entry.name, "(_) @node", &Filter::default(), 0) {
                broken.push(format!("{}: {e}", entry.name));
            }
        }
        assert!(broken.is_empty(), "{}", broken.join("\n"));
    }

    /// A language with no grammar is named, with the ones that have one, so a
    /// caller can correct it in one step.
    #[test]
    fn a_language_with_no_grammar_says_which_have_one() {
        let db = rusqlite::Connection::open_in_memory().unwrap();
        db.execute_batch(store::SCHEMA).unwrap();
        let err = run(&db, "cobol", "(identifier) @x", &Filter::default(), 0)
            .expect_err("cobol carries no grammar in this release");
        assert!(err.to_string().contains("rust"), "{err}");
    }
}

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

    /// A store holding one Rust file with `calls` distinct call expressions,
    /// written straight into the schema — no embedder, because a pattern run
    /// reads chunk text and never a vector.
    fn store_of(calls: usize) -> rusqlite::Connection {
        let db = rusqlite::Connection::open_in_memory().unwrap();
        db.execute_batch(store::SCHEMA).unwrap();
        let mut body = String::from("fn main() {\n");
        for i in 0..calls {
            body.push_str(&format!("    call_{i}();\n"));
        }
        body.push_str("}\n");
        let lines = body.lines().count() as u32;
        let file = store::insert_file(&db, "/work/api/src/main.rs", "hash", 1, 0).unwrap();
        store::insert_chunk(&db, file, 0, 1, lines, &body).unwrap();
        db
    }

    /// The cap is only useful if there is a way past it, and the way past it
    /// is only useful if the order is total.
    #[test]
    fn offset_continues_the_listing_and_repeats_exactly() {
        let db = store_of(MAX_MATCHES + 40);
        let pattern = "(call_expression function: (identifier) @f)";

        let first = run(&db, "rust", pattern, &Filter::default(), 0).unwrap();
        assert_eq!(first.matches.len(), MAX_MATCHES);
        assert!(first.truncated);

        let next = run(&db, "rust", pattern, &Filter::default(), MAX_MATCHES).unwrap();
        assert_eq!(next.skipped, MAX_MATCHES);
        assert_eq!(next.matches.len(), 40);
        assert_eq!(
            next.matches[0].text, "call_200",
            "the continuation starts at the match after the cap"
        );
        assert!(
            !first.matches.iter().any(|m| m.text == "call_200"),
            "the two pages must not overlap"
        );

        // Two identical calls, two identical answers. Without this the offset
        // is a second sample rather than a continuation.
        let again = run(&db, "rust", pattern, &Filter::default(), MAX_MATCHES).unwrap();
        let texts: Vec<&str> = next.matches.iter().map(|m| m.text.as_str()).collect();
        let repeat: Vec<&str> = again.matches.iter().map(|m| m.text.as_str()).collect();
        assert_eq!(texts, repeat);
    }

    /// The same glob filter every other surface takes, which is the other way
    /// past the cap.
    #[test]
    fn a_path_filter_narrows_which_files_are_parsed() {
        let db = store_of(3);
        let pattern = "(call_expression function: (identifier) @f)";

        let all = run(&db, "rust", pattern, &Filter::default(), 0).unwrap();
        assert_eq!(all.files, 1);

        let elsewhere = Filter::new(&["src/other/**".to_string()], &[], &[]).unwrap();
        let none = run(&db, "rust", pattern, &elsewhere, 0).unwrap();
        assert_eq!(none.files, 0);
        assert!(none.matches.is_empty());

        let here = Filter::new(&["**/src/**".to_string()], &[], &[]).unwrap();
        let some = run(&db, "rust", pattern, &here, 0).unwrap();
        assert_eq!(some.matches.len(), 3);
    }
}