magi-code 0.77.1

use super::{matcher::build_matchers, reader};
use crate::{
    cancellation::AgentCancellation,
    tools::workspace::{WorkspaceWalkOptions, WorkspaceWalker},
};
use grep_matcher::Matcher;
use std::{
    cmp::Ordering,
    collections::{BTreeMap, BinaryHeap, HashMap, HashSet},
    path::{Path, PathBuf},
    time::{Duration, Instant},
};

pub(super) const OUTPUT_MAX_BYTES: usize = 65_536;
const MAX_FILES: usize = 10_000;
const MAX_BYTES: u64 = 128 * 1024 * 1024;
const DEADLINE: Duration = Duration::from_secs(10);
const PER_FILE_RANKED: usize = 5;
const RANKED_PRIMARY_MAX_BYTES: usize = 240;
const RAW_PRIMARY_MAX_BYTES: usize = 4096;
const CONTEXT_MAX_BYTES: usize = 160;
const CANCEL_CHECK_INTERVAL: usize = 128;

#[derive(Debug, Default, Clone)]
pub(super) struct GrepScan {
    pub(super) lines: Vec<String>,
    pub(super) matches_seen: usize,
    pub(super) files_scanned: usize,
    pub(super) bytes_scanned: u64,
    pub(super) truncated: bool,
    pub(super) timed_out: bool,
    /// At least one regular file was limited to its 4 MiB prefix.
    pub(super) byte_limit_reached: bool,
    /// The invocation-wide 128 MiB scan budget stopped traversal or a file.
    pub(super) scan_byte_limit_reached: bool,
    /// The invocation-wide 10,000-file scan budget stopped traversal.
    pub(super) file_limit_reached: bool,
    /// Raw mode found the one-match lookahead used to establish pagination.
    pub(super) match_limit_reached: bool,
    pub(super) per_file_limit_reached: bool,
    pub(super) files_with_matches: usize,
    pub(super) files_returned: usize,
    pub(super) invalid_utf8_files: usize,
    pub(super) invalid_utf8_lines: usize,
    pub(super) read_errors_skipped: usize,
    pub(super) walk_errors: usize,
    pub(super) walk_entries_omitted: usize,
    pub(super) binary_files_skipped: usize,
    pub(super) scan_complete: bool,
    pub(super) output_bytes: usize,
    pub(super) output_byte_limit_reached: bool,
    pub(super) context_lines_omitted: usize,
    pub(super) next_offset: Option<usize>,
    pub(super) has_more: Option<bool>,
    pub(super) truncation_reasons: Vec<&'static str>,
    pub(super) matches_seen_exact: bool,
    pub(super) raw_lookahead_reached: bool,
    pub(super) output_lines_returned: usize,
    pub(super) matches_returned: usize,
    pub(super) patterns_adjusted: usize,
    pub(super) literal_fallbacks: usize,
}

pub(super) struct GrepRequest<'a> {
    pub(super) cwd: &'a Path,
    pub(super) walker: &'a WorkspaceWalker,
    pub(super) patterns: &'a [String],
    pub(super) root: &'a Path,
    pub(super) limit: usize,
    pub(super) offset: usize,
    pub(super) context: usize,
    pub(super) raw: bool,
    pub(super) cancellation: &'a AgentCancellation,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum HitKind {
    Import,
    Match,
    DefLike,
}

impl HitKind {
    fn score(self) -> u8 {
        match self {
            Self::Import => 0,
            Self::Match => 1,
            Self::DefLike => 2,
        }
    }

    fn label(self) -> &'static str {
        match self {
            Self::Import => "import",
            Self::Match => "match",
            Self::DefLike => "def-like",
        }
    }
}

#[derive(Debug, Clone, Copy)]
struct Candidate {
    line: usize,
    match_start: usize,
    kind: HitKind,
}

#[derive(Debug, Clone)]
struct ContextLine {
    line: usize,
    text: String,
}

#[derive(Debug, Clone)]
struct Hit {
    path: PathBuf,
    line: usize,
    kind: HitKind,
    text: String,
    context: Vec<ContextLine>,
}

#[derive(Debug, Clone, Copy)]
struct LineSpan {
    start: u32,
    end: u32,
}

impl LineSpan {
    fn text(self, bytes: &[u8]) -> &[u8] {
        &bytes[self.start as usize..self.end as usize]
    }
}

#[derive(Debug)]
struct RankedHeapHit(Hit);

impl PartialEq for RankedHeapHit {
    fn eq(&self, other: &Self) -> bool {
        cmp_ranked(&self.0, &other.0) == Ordering::Equal
    }
}

impl Eq for RankedHeapHit {}

impl Ord for RankedHeapHit {
    fn cmp(&self, other: &Self) -> Ordering {
        cmp_ranked(&self.0, &other.0)
    }
}

impl PartialOrd for RankedHeapHit {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

#[derive(Debug)]
struct RenderRow {
    line: usize,
    text: String,
    kind: Option<HitKind>,
}

#[derive(Debug)]
struct OutputRecord {
    text: String,
    primary_file: Option<PathBuf>,
}

impl OutputRecord {
    fn primary(path: &Path, text: String) -> Self {
        Self {
            text,
            primary_file: Some(path.to_path_buf()),
        }
    }

    fn auxiliary(text: String) -> Self {
        Self {
            text,
            primary_file: None,
        }
    }
}

#[derive(Debug, Default)]
struct OutputBuilder {
    lines: Vec<String>,
    bytes: usize,
    primary_count: usize,
    primary_files: HashSet<PathBuf>,
    mandatory_remaining_bytes: usize,
    context_lines_omitted: usize,
    output_limit_reached: bool,
    stopped: bool,
}

impl OutputBuilder {
    fn with_mandatory_bytes(mandatory_remaining_bytes: usize) -> Self {
        Self {
            mandatory_remaining_bytes,
            ..Self::default()
        }
    }

    fn push(&mut self, record: OutputRecord) -> bool {
        self.push_many(std::slice::from_ref(&record))
    }

    fn push_many(&mut self, records: &[OutputRecord]) -> bool {
        self.push_many_inner(records, true)
    }

    fn push_optional(&mut self, record: OutputRecord) -> bool {
        self.push_many_inner(std::slice::from_ref(&record), false)
    }

    fn push_many_inner(&mut self, records: &[OutputRecord], stop_on_failure: bool) -> bool {
        if self.stopped || records.is_empty() {
            return false;
        }
        let separators = if self.lines.is_empty() {
            records.len().saturating_sub(1)
        } else {
            records.len()
        };
        let record_bytes = records
            .iter()
            .map(|record| record.text.len())
            .sum::<usize>();
        let additional = record_bytes.saturating_add(separators);
        let reserved = if stop_on_failure {
            0
        } else {
            self.mandatory_remaining_bytes
        };
        if self
            .bytes
            .saturating_add(additional)
            .saturating_add(reserved)
            > OUTPUT_MAX_BYTES
        {
            self.output_limit_reached = true;
            if stop_on_failure {
                self.stopped = true;
            } else {
                self.context_lines_omitted =
                    self.context_lines_omitted.saturating_add(records.len());
            }
            return false;
        }
        self.bytes = self.bytes.saturating_add(additional);
        if stop_on_failure {
            self.mandatory_remaining_bytes =
                self.mandatory_remaining_bytes.saturating_sub(additional);
        }
        self.primary_count += records
            .iter()
            .filter(|record| record.primary_file.is_some())
            .count();
        for path in records
            .iter()
            .filter_map(|record| record.primary_file.as_ref())
        {
            self.primary_files.insert(path.clone());
        }
        self.lines
            .extend(records.iter().map(|record| record.text.clone()));
        true
    }
}

pub(super) fn run(r: GrepRequest<'_>) -> anyhow::Result<GrepScan> {
    let matcher_result = build_matchers(r.patterns)?;
    let start = Instant::now();
    let mut scan = GrepScan {
        patterns_adjusted: matcher_result.patterns_adjusted,
        literal_fallbacks: matcher_result.literal_fallbacks,
        ..GrepScan::default()
    };
    let target = r.offset.saturating_add(r.limit).saturating_add(1);
    let mut stopped = false;
    let mut raw_hits = Vec::with_capacity(r.limit.saturating_add(1));
    let mut ranked_hits = BinaryHeap::<RankedHeapHit>::new();
    let mut ranked_candidate_count = 0usize;

    let mut visit = |path: PathBuf| -> anyhow::Result<bool> {
        if stopped {
            return Ok(false);
        }
        r.cancellation.check()?;
        if start.elapsed() >= DEADLINE {
            scan.timed_out = true;
            stopped = true;
            return Ok(false);
        }
        if scan.files_scanned >= MAX_FILES {
            scan.file_limit_reached = true;
            stopped = true;
            return Ok(false);
        }
        if scan.bytes_scanned >= MAX_BYTES {
            scan.scan_byte_limit_reached = true;
            stopped = true;
            return Ok(false);
        }

        let remaining_bytes = MAX_BYTES.saturating_sub(scan.bytes_scanned);
        let outcome = match reader::read_file_bytes(&path, remaining_bytes) {
            Ok(outcome) => outcome,
            Err(error)
                if matches!(
                    error.kind(),
                    std::io::ErrorKind::NotFound | std::io::ErrorKind::PermissionDenied
                ) =>
            {
                scan.read_errors_skipped += 1;
                return Ok(true);
            }
            Err(error) => return Err(error.into()),
        };

        let reader::ReadOutcome::Bytes {
            bytes,
            bytes_scanned,
            truncated,
            scan_byte_limit_reached,
            ..
        } = outcome
        else {
            match outcome {
                reader::ReadOutcome::ReadErrorSkipped => scan.read_errors_skipped += 1,
                reader::ReadOutcome::ScanByteLimitReached => {
                    scan.scan_byte_limit_reached = true;
                    stopped = true;
                }
                reader::ReadOutcome::Skipped => {}
                reader::ReadOutcome::Bytes { .. } => unreachable!(),
            }
            return Ok(!stopped);
        };

        scan.files_scanned += 1;
        scan.bytes_scanned = scan.bytes_scanned.saturating_add(bytes_scanned);
        scan.byte_limit_reached |= truncated;
        scan.scan_byte_limit_reached |= scan_byte_limit_reached;

        if bytes.contains(&0) {
            scan.binary_files_skipped += 1;
            if scan_byte_limit_reached {
                stopped = true;
            }
            return Ok(!stopped);
        }

        let spans = line_spans(&bytes);
        let incomplete_trailing_line =
            (truncated || scan_byte_limit_reached) && !bytes.ends_with(b"\n");
        let malformed_lines = count_invalid_utf8_lines(&bytes, &spans, incomplete_trailing_line);
        if malformed_lines > 0 {
            scan.invalid_utf8_files += 1;
            scan.invalid_utf8_lines += malformed_lines;
        }

        let mut file_candidates = Vec::with_capacity(PER_FILE_RANKED);
        let mut file_matches = 0usize;
        for (index, span) in spans.iter().copied().enumerate() {
            if index % CANCEL_CHECK_INTERVAL == 0 {
                r.cancellation.check()?;
                if start.elapsed() >= DEADLINE {
                    scan.timed_out = true;
                    stopped = true;
                    break;
                }
            }
            let line = span.text(&bytes);
            let Some(match_start) = first_match_start(&matcher_result.matchers, line)? else {
                continue;
            };
            file_matches += 1;
            scan.matches_seen = scan.matches_seen.saturating_add(1);
            let candidate = Candidate {
                line: index + 1,
                match_start,
                kind: classify_hit(&path, line),
            };
            if r.raw {
                if scan.matches_seen > r.offset && raw_hits.len() < r.limit.saturating_add(1) {
                    file_candidates.push(candidate);
                }
                if scan.matches_seen >= target {
                    scan.match_limit_reached = true;
                    scan.raw_lookahead_reached = true;
                    stopped = true;
                    break;
                }
            } else {
                retain_best_per_file(&mut file_candidates, candidate);
            }
        }

        if file_matches > 0 {
            scan.files_with_matches += 1;
        }
        if !r.raw && file_matches > file_candidates.len() {
            scan.per_file_limit_reached = true;
        }
        if r.raw {
            for candidate in file_candidates {
                raw_hits.push(make_hit(
                    &path,
                    &bytes,
                    &spans,
                    candidate,
                    RAW_PRIMARY_MAX_BYTES,
                    r.context,
                ));
            }
        } else {
            file_candidates.sort_by(cmp_candidate_same_file);
            ranked_candidate_count = ranked_candidate_count.saturating_add(file_candidates.len());
            for candidate in file_candidates {
                let hit = make_hit(
                    &path,
                    &bytes,
                    &spans,
                    candidate,
                    RANKED_PRIMARY_MAX_BYTES,
                    r.context,
                );
                retain_ranked(&mut ranked_hits, hit, target);
            }
        }
        if scan_byte_limit_reached {
            stopped = true;
        }
        Ok(!stopped)
    };

    let traversal_completed = if r.root.symlink_metadata()?.file_type().is_file() {
        visit(r.root.to_path_buf())?
    } else {
        let status = r.walker.visit_sorted_files_with_diagnostics(
            WorkspaceWalkOptions {
                root: r.root,
                skip_dirs: &[".git", "target"],
                cancel_interval: 32,
            },
            Some(r.cancellation),
            &mut visit,
        )?;
        scan.walk_errors = status.walk_errors;
        scan.walk_entries_omitted = status.entries_omitted;
        status.completed
    };

    let intentional_raw_stop = scan.raw_lookahead_reached;
    scan.scan_complete = !scan.timed_out
        && !scan.byte_limit_reached
        && !scan.scan_byte_limit_reached
        && !scan.file_limit_reached
        && scan.read_errors_skipped == 0
        && scan.walk_errors == 0
        && scan.walk_entries_omitted == 0
        && (traversal_completed || intentional_raw_stop);
    scan.matches_seen_exact = scan.scan_complete && !intentional_raw_stop;

    if scan.timed_out {
        add_reason(&mut scan.truncation_reasons, "deadline");
    }
    if scan.scan_byte_limit_reached {
        add_reason(&mut scan.truncation_reasons, "scan_bytes");
    }
    if scan.file_limit_reached {
        add_reason(&mut scan.truncation_reasons, "file_limit");
    }
    if scan.byte_limit_reached {
        add_reason(&mut scan.truncation_reasons, "file_bytes");
    }
    if scan.read_errors_skipped > 0 {
        add_reason(&mut scan.truncation_reasons, "read_errors");
    }
    if scan.walk_errors > 0 || scan.walk_entries_omitted > 0 {
        add_reason(&mut scan.truncation_reasons, "walk_errors");
    }
    if scan.per_file_limit_reached {
        add_reason(&mut scan.truncation_reasons, "per_file");
    }
    if scan.match_limit_reached {
        add_reason(&mut scan.truncation_reasons, "matches");
    }
    scan.truncated = !scan.scan_complete || !scan.truncation_reasons.is_empty();

    let mut ranked_hits = ranked_hits.into_iter().map(|hit| hit.0).collect::<Vec<_>>();
    ranked_hits.sort_by(cmp_ranked);
    raw_hits.sort_by(cmp_raw);

    let (page_hits, available_matches) = if r.raw {
        let page_len = raw_hits.len().min(r.limit);
        (&raw_hits[..page_len], raw_hits.len())
    } else {
        let start_index = r.offset.min(ranked_hits.len());
        let end_index = start_index.saturating_add(r.limit).min(ranked_hits.len());
        (&ranked_hits[start_index..end_index], ranked_candidate_count)
    };
    if r.raw {
        render_raw(page_hits, r.cwd, &mut scan);
    } else {
        render_grouped(page_hits, r.cwd, &mut scan);
    }

    let rendered_page_matches = scan.matches_returned;
    let page_had_unemitted_matches = rendered_page_matches < page_hits.len();
    let logical_more = if scan.scan_complete {
        if r.raw {
            available_matches > page_hits.len()
        } else {
            available_matches > r.offset.saturating_add(page_hits.len())
        }
    } else {
        false
    };
    let has_more = scan.scan_complete && (logical_more || page_had_unemitted_matches);
    scan.has_more = scan.scan_complete.then_some(has_more);
    scan.next_offset = scan
        .has_more
        .filter(|has_more| *has_more)
        .map(|_| r.offset.saturating_add(rendered_page_matches));
    if scan.output_byte_limit_reached {
        scan.truncated = true;
        add_reason(&mut scan.truncation_reasons, "output_bytes");
    }

    Ok(scan)
}

fn retain_best_per_file(candidates: &mut Vec<Candidate>, candidate: Candidate) {
    if candidates.len() < PER_FILE_RANKED {
        candidates.push(candidate);
        return;
    }
    let Some((worst_index, worst)) = candidates
        .iter()
        .enumerate()
        .max_by(|(_, a), (_, b)| cmp_candidate_same_file(a, b))
    else {
        return;
    };
    if cmp_candidate_same_file(&candidate, worst).is_lt() {
        candidates[worst_index] = candidate;
    }
}

fn retain_ranked(heap: &mut BinaryHeap<RankedHeapHit>, hit: Hit, capacity: usize) {
    if capacity == 0 {
        return;
    }
    if heap.len() < capacity {
        heap.push(RankedHeapHit(hit));
        return;
    }
    let replace = heap
        .peek()
        .is_some_and(|worst| cmp_ranked(&hit, &worst.0).is_lt());
    if replace {
        heap.pop();
        heap.push(RankedHeapHit(hit));
    }
}

fn make_hit(
    path: &Path,
    bytes: &[u8],
    spans: &[LineSpan],
    candidate: Candidate,
    primary_max_bytes: usize,
    context: usize,
) -> Hit {
    let index = candidate
        .line
        .saturating_sub(1)
        .min(spans.len().saturating_sub(1));
    let span = spans[index];
    let context = context.min(20);
    let mut context_lines = Vec::with_capacity(context.saturating_mul(2));
    let first = index.saturating_sub(context);
    let last = index
        .saturating_add(context)
        .saturating_add(1)
        .min(spans.len());
    for (other_index, other_span) in spans[first..last].iter().copied().enumerate() {
        let other_index = first + other_index;
        if other_index != index {
            context_lines.push(ContextLine {
                line: other_index + 1,
                text: excerpt(other_span.text(bytes), CONTEXT_MAX_BYTES, None),
            });
        }
    }
    Hit {
        path: path.to_path_buf(),
        line: candidate.line,
        kind: candidate.kind,
        text: excerpt(
            span.text(bytes),
            primary_max_bytes,
            Some(candidate.match_start),
        ),
        context: context_lines,
    }
}

fn mandatory_line_reserve<I>(lengths: I) -> usize
where
    I: Iterator<Item = usize>,
{
    lengths.fold(0, |total, length| {
        total.saturating_add(length).saturating_add(1)
    })
}

fn raw_row_text(display_path: &str, row: &RenderRow) -> String {
    let primary = row.kind.is_some();
    let separator = if primary { ':' } else { '-' };
    format!(
        "{display_path}{separator}{}{separator}{}",
        row.line, row.text
    )
}

fn render_raw(hits: &[Hit], cwd: &Path, scan: &mut GrepScan) {
    let mut files = BTreeMap::<PathBuf, BTreeMap<usize, RenderRow>>::new();
    for hit in hits {
        let rows = files.entry(hit.path.clone()).or_default();
        rows.insert(
            hit.line,
            RenderRow {
                line: hit.line,
                text: hit.text.clone(),
                kind: Some(hit.kind),
            },
        );
        for context in &hit.context {
            rows.entry(context.line).or_insert_with(|| RenderRow {
                line: context.line,
                text: context.text.clone(),
                kind: None,
            });
        }
    }

    let mandatory_bytes = mandatory_line_reserve(files.iter().flat_map(|(path, rows)| {
        let display_path = display_path(cwd, path);
        rows.values()
            .filter(|row| row.kind.is_some())
            .map(move |row| raw_row_text(&display_path, row).len())
    }));
    let mut output = OutputBuilder::with_mandatory_bytes(mandatory_bytes);
    'files: for (path, rows) in files {
        let display_path = display_path(cwd, &path);
        for (_, row) in rows {
            let primary = row.kind.is_some();
            let text = raw_row_text(&display_path, &row);
            let record = if primary {
                OutputRecord::primary(&path, text)
            } else {
                OutputRecord::auxiliary(text)
            };
            if primary {
                if !output.push(record) {
                    break 'files;
                }
            } else {
                output.push_optional(record);
            }
        }
    }
    finish_output(output, scan);
}

#[derive(Debug)]
struct RenderGroup {
    path: PathBuf,
    primaries: Vec<RenderRow>,
    contexts: BTreeMap<usize, RenderRow>,
    primary_lines: HashSet<usize>,
}

fn render_grouped(hits: &[Hit], cwd: &Path, scan: &mut GrepScan) {
    let mut groups = Vec::<RenderGroup>::new();
    let mut group_indices = HashMap::<PathBuf, usize>::new();
    for hit in hits {
        let group_index = if let Some(index) = group_indices.get(&hit.path) {
            *index
        } else {
            let index = groups.len();
            groups.push(RenderGroup {
                path: hit.path.clone(),
                primaries: Vec::new(),
                contexts: BTreeMap::new(),
                primary_lines: HashSet::new(),
            });
            group_indices.insert(hit.path.clone(), index);
            index
        };
        let group = &mut groups[group_index];
        group.primary_lines.insert(hit.line);
        group.contexts.remove(&hit.line);
        group.primaries.push(RenderRow {
            line: hit.line,
            text: hit.text.clone(),
            kind: Some(hit.kind),
        });
        for context in &hit.context {
            if !group.primary_lines.contains(&context.line) {
                group
                    .contexts
                    .entry(context.line)
                    .or_insert_with(|| RenderRow {
                        line: context.line,
                        text: context.text.clone(),
                        kind: None,
                    });
            }
        }
    }

    // Grouped headers are structural: without a header, a primary row has no path.
    // Reserve them with the primary rows and emit each first header/primary pair atomically.

    let mandatory_bytes = mandatory_line_reserve(groups.iter().flat_map(|group| {
        let header_len = display_path(cwd, &group.path).len();
        let primary_lengths = group.primaries.iter().map(|row| {
            let kind = row.kind.expect("grouped primary row must have a kind");
            format!("[{}] {}:{}", kind.label(), row.line, row.text).len()
        });
        std::iter::once(header_len).chain(primary_lengths)
    }));
    let mut output = OutputBuilder::with_mandatory_bytes(mandatory_bytes);
    'groups: for group in groups {
        let display_path = display_path(cwd, &group.path);
        let mut first = true;
        for row in &group.primaries {
            let kind = row.kind.expect("grouped primary row must have a kind");
            let record = OutputRecord::primary(
                &group.path,
                format!("[{}] {}:{}", kind.label(), row.line, row.text),
            );
            if first {
                let header = OutputRecord::auxiliary(display_path.clone());
                if !output.push_many(&[header, record]) {
                    break 'groups;
                }
                first = false;
            } else if !output.push(record) {
                break 'groups;
            }
        }
        for row in group.contexts.into_values() {
            output.push_optional(OutputRecord::auxiliary(format!(
                "{}:{}",
                row.line, row.text
            )));
        }
    }
    finish_output(output, scan);
}

fn finish_output(output: OutputBuilder, scan: &mut GrepScan) {
    let primary_count = output.primary_count;
    let files_returned = output.primary_files.len();
    let output_limit_reached = output.output_limit_reached;
    scan.lines = output.lines;
    scan.output_bytes = output.bytes;
    scan.output_lines_returned = scan.lines.len();
    scan.matches_returned = primary_count;
    scan.files_returned = files_returned;
    scan.context_lines_omitted = output.context_lines_omitted;
    scan.output_byte_limit_reached = output_limit_reached;
    if output_limit_reached {
        scan.truncated = true;
    }
}

fn cmp_candidate_same_file(a: &Candidate, b: &Candidate) -> Ordering {
    b.kind
        .score()
        .cmp(&a.kind.score())
        .then(a.line.cmp(&b.line))
}

fn cmp_ranked(a: &Hit, b: &Hit) -> Ordering {
    b.kind
        .score()
        .cmp(&a.kind.score())
        .then(a.path.cmp(&b.path))
        .then(a.line.cmp(&b.line))
}

fn cmp_raw(a: &Hit, b: &Hit) -> Ordering {
    a.path.cmp(&b.path).then(a.line.cmp(&b.line))
}

fn classify_hit(path: &Path, line: &[u8]) -> HitKind {
    if is_def(path, line) {
        HitKind::DefLike
    } else if is_import(line) {
        HitKind::Import
    } else {
        HitKind::Match
    }
}

fn is_import(line: &[u8]) -> bool {
    let line = line.trim_ascii_start();
    line.starts_with(b"use ") || line.starts_with(b"import ")
}

fn is_def(path: &Path, line: &[u8]) -> bool {
    matches!(
        path.extension().and_then(|extension| extension.to_str()),
        Some("rs" | "py" | "js" | "ts" | "tsx" | "go" | "java" | "c" | "cpp")
    ) && [b"fn ".as_slice(), b"def ", b"class ", b"struct "]
        .iter()
        .any(|needle| line.windows(needle.len()).any(|window| window == *needle))
}

fn first_match_start(
    matchers: &[grep_regex::RegexMatcher],
    line: &[u8],
) -> anyhow::Result<Option<usize>> {
    let mut first = None;
    for matcher in matchers {
        if let Some(found) = matcher
            .find(line)
            .map_err(|error| anyhow::anyhow!("grep matcher failed: {error}"))?
        {
            first = Some(first.map_or(found.start(), |start: usize| start.min(found.start())));
        }
    }
    Ok(first)
}

fn line_spans(bytes: &[u8]) -> Vec<LineSpan> {
    let mut spans = Vec::new();
    let mut start = 0usize;
    for (index, byte) in bytes.iter().copied().enumerate() {
        if byte == b'\n' {
            spans.push(LineSpan {
                start: start as u32,
                end: trim_carriage_return(bytes, start, index) as u32,
            });
            start = index + 1;
        }
    }
    if start < bytes.len() {
        spans.push(LineSpan {
            start: start as u32,
            end: trim_carriage_return(bytes, start, bytes.len()) as u32,
        });
    }
    spans
}

fn trim_carriage_return(bytes: &[u8], start: usize, mut end: usize) -> usize {
    if end > start && bytes[end - 1] == b'\r' {
        end -= 1;
    }
    end
}

fn count_invalid_utf8_lines(
    bytes: &[u8],
    spans: &[LineSpan],
    incomplete_trailing_line: bool,
) -> usize {
    spans
        .iter()
        .enumerate()
        .filter(|(index, span)| {
            let line = span.text(bytes);
            match std::str::from_utf8(line) {
                Ok(_) => false,
                Err(error) => {
                    !(incomplete_trailing_line
                        && *index + 1 == spans.len()
                        && is_truncated_utf8_error(line, error))
                }
            }
        })
        .count()
}

fn is_truncated_utf8_error(bytes: &[u8], error: std::str::Utf8Error) -> bool {
    error.error_len().is_none()
        && error.valid_up_to() < bytes.len()
        && bytes.len() - error.valid_up_to() <= 3
}

fn excerpt(bytes: &[u8], max_bytes: usize, needle: Option<usize>) -> String {
    if max_bytes == 0 || bytes.is_empty() {
        return String::new();
    }
    if bytes.len() <= max_bytes {
        return bounded_lossy(bytes, max_bytes);
    }

    const ELLIPSIS: &str = "…";
    let marker_bytes = ELLIPSIS.len();
    if max_bytes <= marker_bytes {
        return truncate_string_bytes(ELLIPSIS, max_bytes);
    }
    let inner_limit = max_bytes.saturating_sub(marker_bytes.saturating_mul(2));
    let window_len = inner_limit.min(bytes.len());
    let center = needle.unwrap_or(0).min(bytes.len());
    let mut start = center.saturating_sub(window_len / 2);
    if start.saturating_add(window_len) > bytes.len() {
        start = bytes.len() - window_len;
    }
    let mut end = start.saturating_add(window_len);
    if let Ok(text) = std::str::from_utf8(bytes) {
        while start > 0 && !text.is_char_boundary(start) {
            start -= 1;
        }
        while end > start && !text.is_char_boundary(end) {
            end -= 1;
        }
    }
    let inner = bounded_lossy(&bytes[start..end], inner_limit);
    let mut result = String::with_capacity(max_bytes);
    result.push_str(ELLIPSIS);
    result.push_str(&inner);
    result.push_str(ELLIPSIS);
    truncate_string_bytes(&result, max_bytes)
}
fn bounded_lossy(bytes: &[u8], max_bytes: usize) -> String {
    let mut output = String::new();
    let mut index = 0usize;
    while index < bytes.len() && output.len() < max_bytes {
        match std::str::from_utf8(&bytes[index..]) {
            Ok(text) => {
                append_bounded(&mut output, text, max_bytes);
                break;
            }
            Err(error) => {
                let valid = error.valid_up_to();
                if valid > 0 {
                    let valid_text = std::str::from_utf8(&bytes[index..index + valid])
                        .expect("valid prefix from Utf8Error");
                    append_bounded(&mut output, valid_text, max_bytes);
                    index += valid;
                    if output.len() >= max_bytes {
                        break;
                    }
                }
                let invalid_len = error.error_len().unwrap_or(1);
                if output.len().saturating_add('�'.len_utf8()) > max_bytes {
                    break;
                }
                output.push('�');
                index = index.saturating_add(invalid_len);
            }
        }
    }
    output
}

fn append_bounded(output: &mut String, text: &str, max_bytes: usize) {
    let remaining = max_bytes.saturating_sub(output.len());
    output.push_str(truncate_string_bytes(text, remaining).as_str());
}

fn truncate_string_bytes(text: &str, max_bytes: usize) -> String {
    if text.len() <= max_bytes {
        return text.to_owned();
    }
    let mut end = max_bytes;
    while end > 0 && !text.is_char_boundary(end) {
        end -= 1;
    }
    text[..end].to_owned()
}

fn display_path(cwd: &Path, path: &Path) -> String {
    let path = path.strip_prefix(cwd).unwrap_or(path);
    path.to_string_lossy().replace('\\', "/")
}

fn add_reason(reasons: &mut Vec<&'static str>, reason: &'static str) {
    if !reasons.contains(&reason) {
        reasons.push(reason);
    }
}

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

    #[test]
    fn output_builder_multi_append_bytes_match_joined_lines() {
        let mut output = OutputBuilder::default();
        assert!(output.push_many(&[
            OutputRecord::auxiliary("first".to_string()),
            OutputRecord::auxiliary("second".to_string()),
        ]));
        assert!(output.push(OutputRecord::auxiliary("third".to_string())));

        assert_eq!(output.bytes, output.lines.join("\n").len());
        assert_eq!(output.lines, ["first", "second", "third"]);
    }

    #[test]
    fn oversized_optional_context_does_not_stop_a_later_primary() {
        let mut output = OutputBuilder::default();
        assert!(output.push(OutputRecord::auxiliary("x".repeat(OUTPUT_MAX_BYTES - 10),)));
        assert!(!output.push_optional(OutputRecord::auxiliary(
            "context-that-does-not-fit".to_string(),
        )));
        assert!(!output.stopped);
        assert_eq!(output.context_lines_omitted, 1);
        assert!(output.output_limit_reached);
        assert!(output.push(OutputRecord::primary(
            Path::new("later.txt"),
            "123456789".to_string(),
        )));
        assert_eq!(output.primary_count, 1);
        assert_eq!(output.primary_files.len(), 1);
    }

    #[test]
    fn grouped_header_reservation_preserves_later_primary_rows() {
        let cwd = Path::new("/workspace");
        let first_path = cwd.join("first.rs");
        let later_path = cwd.join("later.rs");
        let first_header = display_path(cwd, &first_path);
        let later_header = display_path(cwd, &later_path);
        let first_primary = "[match] 1:first";
        let later_primary = "[match] 1:later";
        let first_bytes = first_header.len() + first_primary.len() + 1;
        let primary_only_reserve = later_primary.len() + 1;
        let context_text_len = OUTPUT_MAX_BYTES
            .saturating_sub(first_bytes)
            .saturating_sub(primary_only_reserve)
            .saturating_sub(1)
            .saturating_sub("2:".len());
        let hits = [
            Hit {
                path: first_path,
                line: 1,
                kind: HitKind::Match,
                text: "first".to_string(),
                context: vec![ContextLine {
                    line: 2,
                    text: "x".repeat(context_text_len),
                }],
            },
            Hit {
                path: later_path,
                line: 1,
                kind: HitKind::Match,
                text: "later".to_string(),
                context: Vec::new(),
            },
        ];
        let mut scan = GrepScan::default();
        render_grouped(&hits, cwd, &mut scan);

        assert_eq!(
            scan.lines,
            vec![
                first_header,
                first_primary.to_string(),
                later_header,
                later_primary.to_string(),
            ]
        );
        assert_eq!(scan.matches_returned, 2);
        assert_eq!(scan.context_lines_omitted, 1);
        assert!(scan.output_byte_limit_reached);
    }

    #[test]
    fn excerpt_caps_are_utf8_safe_and_keep_a_centered_match() {
        let source = format!("{}needle{}", "a".repeat(5_000), "b".repeat(5_000));
        let bytes = source.as_bytes();
        for cap in [RANKED_PRIMARY_MAX_BYTES, RAW_PRIMARY_MAX_BYTES] {
            let fragment = excerpt(bytes, cap, Some(5_000));
            assert!(fragment.len() <= cap);
            assert!(fragment.contains("needle"));
            assert!(std::str::from_utf8(fragment.as_bytes()).is_ok());
        }
        let context = excerpt(bytes, CONTEXT_MAX_BYTES, None);
        assert!(context.len() <= CONTEXT_MAX_BYTES);
        assert!(std::str::from_utf8(context.as_bytes()).is_ok());
    }

    #[test]
    fn truncated_utf8_suppresses_only_an_incomplete_suffix() {
        let incomplete = vec![b't', b'a', b'i', b'l', 0xc3];
        let incomplete_error = std::str::from_utf8(&incomplete).unwrap_err();
        assert!(is_truncated_utf8_error(&incomplete, incomplete_error));

        let malformed_before_incomplete =
            vec![b'b', b'a', b'd', 0xff, b't', b'a', b'i', b'l', 0xc3];
        let malformed_error = std::str::from_utf8(&malformed_before_incomplete).unwrap_err();
        assert!(!is_truncated_utf8_error(
            &malformed_before_incomplete,
            malformed_error,
        ));
        let spans = line_spans(&malformed_before_incomplete);
        assert_eq!(
            count_invalid_utf8_lines(&malformed_before_incomplete, &spans, true),
            1
        );
        let incomplete_spans = line_spans(&incomplete);
        assert_eq!(
            count_invalid_utf8_lines(&incomplete, &incomplete_spans, true),
            0
        );
    }
}