magi-code 0.100.0

use std::{
    fs, io,
    path::Path,
    time::{Duration, Instant},
};

const MAX_ANCESTORS: usize = 32;
const MAX_ENTRIES: usize = 1000;
const MAX_SUGGESTIONS: usize = 3;
const DEADLINE: Duration = Duration::from_millis(100);

pub(super) fn with_suggestions(
    error: io::Error,
    candidate: &Path,
    cwd: &Path,
    allow_outside: bool,
) -> anyhow::Error {
    if error.kind() != io::ErrorKind::NotFound {
        return error.into();
    }
    let suggestions = nearby_paths(candidate, cwd, allow_outside);
    let path = candidate.strip_prefix(cwd).unwrap_or(candidate).display();
    let hint = if suggestions.is_empty() {
        String::new()
    } else {
        format!(". Did you mean: {}?", suggestions.join(", "))
    };
    anyhow::anyhow!("{error}: {path}{hint}")
}

fn nearby_paths(candidate: &Path, cwd: &Path, allow_outside: bool) -> Vec<String> {
    let deadline = Instant::now() + DEADLINE;
    let mut missing = candidate;
    let mut ancestor = None;
    for _ in 0..MAX_ANCESTORS {
        let Some(parent) = missing.parent() else {
            return Vec::new();
        };
        match parent.canonicalize() {
            Ok(path) => {
                ancestor = Some(path);
                break;
            }
            Err(error) if error.kind() == io::ErrorKind::NotFound => missing = parent,
            Err(_) => return Vec::new(),
        }
        if Instant::now() >= deadline {
            return Vec::new();
        }
    }
    let Some(ancestor) = ancestor else {
        return Vec::new();
    };
    if !allow_outside && !ancestor.starts_with(cwd) {
        return Vec::new();
    }
    // Even an outside-cwd request must not suggest symlink targets outside its search root.
    let root = if ancestor.starts_with(cwd) {
        cwd
    } else {
        &ancestor
    };
    let Some(name) = missing.file_name().and_then(|name| name.to_str()) else {
        return Vec::new();
    };
    let name = name.to_lowercase();
    let suffix = candidate.strip_prefix(missing).unwrap_or(Path::new(""));
    if suffix.components().take(MAX_ANCESTORS + 1).count() > MAX_ANCESTORS {
        return Vec::new();
    }
    let Ok(entries) = fs::read_dir(&ancestor) else {
        return Vec::new();
    };
    let mut matches = Vec::new();
    for entry in entries.take(MAX_ENTRIES) {
        if Instant::now() >= deadline {
            break;
        }
        let Ok(entry) = entry else { continue };
        let Ok(kind) = entry.file_type() else {
            continue;
        };
        if !kind.is_file() && !kind.is_dir() {
            continue;
        }
        let entry_name = entry.file_name();
        let Some(entry_name) = entry_name.to_str() else {
            continue;
        };
        let Some(distance) = edit_distance_within_two(&name, &entry_name.to_lowercase()) else {
            continue;
        };
        let path = entry.path();
        let mut full_path = path.clone();
        let mut safe_suffix = true;
        for component in suffix.components() {
            full_path.push(component);
            if !fs::symlink_metadata(&full_path)
                .is_ok_and(|metadata| !metadata.file_type().is_symlink())
            {
                safe_suffix = false;
                break;
            }
        }
        let path = if safe_suffix { full_path } else { path };
        let Ok(path) = path.canonicalize() else {
            continue;
        };
        if !path.starts_with(root) {
            continue;
        }
        let display = path
            .strip_prefix(cwd)
            .unwrap_or(&path)
            .display()
            .to_string();
        matches.push((distance, display));
    }
    matches.sort();
    matches.dedup();
    matches
        .into_iter()
        .take(MAX_SUGGESTIONS)
        .map(|(_, path)| path)
        .collect()
}

fn edit_distance_within_two(left: &str, right: &str) -> Option<usize> {
    // Filesystem component sizes are bounded; avoid expensive work on malformed input.
    if left.len() > 512 || right.len() > 512 {
        return None;
    }
    let left: Vec<_> = left.chars().collect();
    let right: Vec<_> = right.chars().collect();
    if left.len().abs_diff(right.len()) > 2 {
        return None;
    }
    let mut row: Vec<_> = (0..=right.len()).collect();
    for (i, a) in left.iter().enumerate() {
        let mut diagonal = row[0];
        row[0] = i + 1;
        for (j, b) in right.iter().enumerate() {
            let previous = row[j + 1];
            row[j + 1] = (diagonal + usize::from(a != b))
                .min(row[j] + 1)
                .min(previous + 1);
            diagonal = previous;
        }
        if row.iter().all(|distance| *distance > 2) {
            return None;
        }
    }
    let distance = row[right.len()];
    (distance <= 2).then_some(distance)
}