rumdl_lib/

workspace_index.rs

//! Workspace-wide index for cross-file analysis
//!
//! This module provides infrastructure for rules that need to validate
//! references across multiple files, such as MD051 which validates that
//! cross-file link fragments point to valid headings.
//!
//! The index is built in parallel and designed for minimal memory overhead.
//!
//! ## Cache Format
//!
//! The workspace index can be persisted to disk for faster startup on
//! repeated runs. The cache format includes a version header to detect
//! incompatible format changes:
//!
//! ```text
//! [4 bytes: magic "RWSI" - Rumdl Workspace Index]
//! [4 bytes: format version (u32 little-endian)]
//! [N bytes: postcard-serialized WorkspaceIndex]
//! ```

use regex::Regex;
use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet};
use std::path::{Path, PathBuf};
use std::sync::LazyLock;

use crate::lint_context::{LintContext, SourcePositions};
use crate::utils::range_utils::byte_to_char_count;

// =============================================================================
// URL Decoding Helper
// =============================================================================

/// Convert a hex digit character to its numeric value (0-15)
fn hex_digit_to_value(c: u8) -> Option<u8> {
    match c {
        b'0'..=b'9' => Some(c - b'0'),
        b'a'..=b'f' => Some(c - b'a' + 10),
        b'A'..=b'F' => Some(c - b'A' + 10),
        _ => None,
    }
}

/// URL-decode a string, handling percent-encoded characters.
///
/// Returns the decoded string, or the original if the decoded bytes are not
/// UTF-8. A `%` not followed by two hex digits is kept as written. Used both to
/// match URL-encoded CJK fragments against raw anchors and to turn a link's
/// path into the file name it spells.
pub(crate) fn url_decode(s: &str) -> String {
    // Fast path: no percent signs means no encoding
    if !s.contains('%') {
        return s.to_string();
    }

    let bytes = s.as_bytes();
    let mut result = Vec::with_capacity(bytes.len());
    let mut i = 0;

    while i < bytes.len() {
        if bytes[i] == b'%' && i + 2 < bytes.len() {
            // Try to parse the two hex digits following %
            let hex1 = bytes[i + 1];
            let hex2 = bytes[i + 2];
            if let (Some(d1), Some(d2)) = (hex_digit_to_value(hex1), hex_digit_to_value(hex2)) {
                result.push(d1 * 16 + d2);
                i += 3;
                continue;
            }
        }
        result.push(bytes[i]);
        i += 1;
    }

    // Convert to UTF-8, falling back to original if invalid
    String::from_utf8(result).unwrap_or_else(|_| s.to_string())
}

/// Spell a file path as a link destination, the inverse of [`link_path_part`].
///
/// Percent-encodes what would end the destination or change what it names:
/// whitespace and control characters, `(`, `)`, `<` and `>`, the `?` and `#`
/// that would start a query or fragment, a `\` that would escape the next
/// character, and `%` itself. Everything else, non-ASCII included, is kept as
/// written so the destination stays readable.
#[cfg(feature = "native")]
pub(crate) fn url_encode_path(path: &str) -> std::borrow::Cow<'_, str> {
    let needs_encoding =
        |c: char| c.is_whitespace() || c.is_control() || matches!(c, '%' | '(' | ')' | '<' | '>' | '?' | '#' | '\\');
    if !path.contains(needs_encoding) {
        return std::borrow::Cow::Borrowed(path);
    }
    let mut encoded = String::with_capacity(path.len() + 8);
    for c in path.chars() {
        if needs_encoding(c) {
            let mut bytes = [0; 4];
            for byte in c.encode_utf8(&mut bytes).bytes() {
                encoded.push_str(&format!("%{byte:02X}"));
            }
        } else {
            encoded.push(c);
        }
    }
    std::borrow::Cow::Owned(encoded)
}

// =============================================================================
// Shared cross-file link extraction utilities
//
// These regexes and helpers are the canonical implementation for extracting
// cross-file links. Both MD057 and LSP use this shared code path for correct
// position tracking.
// =============================================================================

/// Regex to match the start of a link
static LINK_START_REGEX: LazyLock<Regex> = LazyLock::new(|| Regex::new(r"!?\[[^\]]*\]").unwrap());

/// Regex to extract the URL from an angle-bracketed markdown link
/// Format: `](<URL>)` or `](<URL> "title")`
///
/// MD057 extracts link destinations with this same pair, applying it to a
/// parsed link's own source span rather than to the raw lines this indexer
/// reads. The regexes therefore stay shared: a destination spelling one of them
/// accepts and the other does not means a link one side sees and the other
/// misses.
pub(crate) static URL_EXTRACT_ANGLE_BRACKET_REGEX: LazyLock<Regex> =
    LazyLock::new(|| Regex::new(r#"\]\(\s*<([^>]+)>(#[^\)\s]*)?\s*(?:"[^"]*")?\s*\)"#).unwrap());

/// Regex to extract the URL from a normal markdown link (without angle brackets)
/// Format: `](URL)` or `](URL "title")`
///
/// The destination admits one level of balanced parentheses, so
/// `](file(inner).md)` yields the whole path. Stopping at the first `)` truncates
/// it to `file(inner`, which then fails the markdown-extension test and drops the
/// link from the index entirely.
pub(crate) static URL_EXTRACT_REGEX: LazyLock<Regex> =
    LazyLock::new(|| Regex::new(r#"]\(\s*((?:[^()>\s#]|\([^()]*\))+)(#[^)\s]*)?\s*(?:"[^"]*")?\s*\)"#).unwrap());

/// Regex to detect URLs with explicit schemes
pub(crate) static PROTOCOL_DOMAIN_REGEX: LazyLock<Regex> =
    LazyLock::new(|| Regex::new(r"^([a-zA-Z][a-zA-Z0-9+.-]*://|[a-zA-Z][a-zA-Z0-9+.-]*:|www\.)").unwrap());

/// Check if a link-target path has a markdown extension (case-insensitive)
#[inline]
fn is_markdown_file(path: &str) -> bool {
    crate::discovery::has_markdown_extension(std::path::Path::new(path))
}

/// Strip query parameters and fragments from a URL path
/// Returns the path portion before `?` or `#`
pub(crate) fn strip_query_and_fragment(url: &str) -> &str {
    let query_pos = url.find('?');
    let fragment_pos = url.find('#');

    match (query_pos, fragment_pos) {
        (Some(q), Some(f)) => &url[..q.min(f)],
        (Some(q), None) => &url[..q],
        (None, Some(f)) => &url[..f],
        (None, None) => url,
    }
}

/// The file path a link destination spells: the destination without its query
/// string or fragment, percent-decoded.
///
/// A destination is a URL, so `guide%20one.md` names the file `guide one.md`,
/// and a query or fragment is never part of a file name. Every question about
/// which file a link names starts from this, so the answer cannot depend on
/// which rule asked.
pub fn link_path_part(url: &str) -> String {
    url_decode(strip_query_and_fragment(url))
}

/// The file a directory-relative link names, resolved against the directory
/// holding the document that wrote it.
///
/// The index keeps a destination as the document spelled it, because that is the
/// text an edit to the link has to be measured against, and a spelling can carry
/// a query string or percent-encoding. A query is not part of a file name - no
/// file is ever called `b.md?raw=true` - so it is stripped here, and the rest is
/// decoded, since `b%20c.md` names `b c.md`. Every consumer asking which file a
/// link points at goes through this, so the index's own keys and the answers
/// navigation gives cannot disagree.
pub fn link_target_file(source_dir: &Path, target_path: &str) -> PathBuf {
    normalize_relative_path(&resolve_target_against(source_dir, target_path))
}

/// Where a destination points, relative to the directory holding the document
/// that wrote it.
///
/// A leading `/` names the project root, the way a site generator serves the
/// page, so it is resolved by walking up to that root. Joining it instead would
/// name the *filesystem* root, because `Path::join` discards the base when its
/// argument is absolute - `/docs/x.md` would become the machine's `/docs/x.md`
/// (`C:\docs\x.md` on Windows), a path no workspace file is ever indexed under.
///
/// The leading `/` is read from the destination as written, before decoding, so
/// an encoded `%2F` is part of a file name and never makes a link root-relative.
fn resolve_target_against(source_dir: &Path, target_path: &str) -> PathBuf {
    let raw = strip_query_and_fragment(target_path);
    match raw.strip_prefix('/') {
        Some(from_root) => resolve_against_project_root(source_dir, &url_decode(from_root)),
        None => source_dir.join(url_decode(raw)),
    }
}

/// The path a project-root-relative destination names, spelled the way the
/// caller spells its own paths.
///
/// That spelling is what makes the answer usable, because the index is keyed by
/// the paths the run walked. A run given an absolute path keys absolute paths,
/// and gets the resolved target as it stands. A run given a relative one keys
/// paths relative to the working directory, so the target is expressed relative
/// to that directory - which is how `/docs/x.md` still finds `x.md` when the run
/// was started from inside `docs/`, below the root the leading `/` refers to.
///
/// A target the run's own paths cannot name, because it lies outside the
/// directory they are relative to, stays absolute. Nothing in the index matches
/// it, which is the right answer for a file the run never walked.
fn resolve_against_project_root(source_dir: &Path, from_root: &str) -> PathBuf {
    let absolute = crate::utils::project_root::project_root().join(from_root);
    if source_dir.is_absolute() {
        return absolute;
    }
    match crate::utils::project_root::working_directory().and_then(|cwd| absolute.strip_prefix(cwd).ok()) {
        Some(relative) => relative.to_path_buf(),
        None => absolute,
    }
}

/// Markdown file links extracted from a document, split by how they resolve.
///
/// Linting rules only understand `relative` links (resolved against the source
/// file's directory). `root_relative` links (leading `/`) are an LSP concept
/// resolved against the configured content roots, so they are kept separate to
/// avoid changing linting behavior.
#[derive(Debug, Default)]
pub struct ExtractedCrossFileLinks {
    /// Links resolved relative to the source file's directory.
    pub relative: Vec<CrossFileLinkIndex>,
    /// Root-relative links. `target_path` has the leading `/` stripped so it can
    /// be joined directly to a content root. Parent-traversal and
    /// protocol-relative (`//host`) links are excluded.
    pub root_relative: Vec<CrossFileLinkIndex>,
}

/// Extract cross-file links from content using correct regex-based position tracking.
///
/// This is the canonical implementation used by both MD057 and LSP to ensure
/// consistent and correct column positions for diagnostic reporting.
///
/// Returns one `CrossFileLinkIndex` per markdown file link, split into directory
/// relative links and root-relative links (see `ExtractedCrossFileLinks`).
pub fn extract_cross_file_links(ctx: &LintContext) -> ExtractedCrossFileLinks {
    let content = ctx.content;

    // Early returns for performance
    if content.is_empty() || !content.contains("](") {
        return ExtractedCrossFileLinks::default();
    }

    let mut links = ExtractedCrossFileLinks::default();
    // Track which lines we've already processed to avoid duplicates
    // (ctx.links() may have multiple entries for the same line)
    let mut processed_lines = HashSet::new();
    let mut positions = SourcePositions::new(content, &ctx.lines);

    for link in ctx.links() {
        let line_idx = link.line - 1;
        if line_idx >= ctx.lines.len() {
            continue;
        }

        // YAML values can contain Markdown-looking message templates. They are
        // frontmatter data, not body links, and MD057 handles path-shaped
        // frontmatter values separately when explicitly enabled.
        if ctx.line_info(link.line).is_some_and(|info| info.in_front_matter) {
            continue;
        }

        // Skip if we've already processed this line
        if !processed_lines.insert(line_idx) {
            continue;
        }

        let line_info = &ctx.lines[line_idx];
        let line = line_info.content(content);
        if !line.contains("](") {
            continue;
        }

        let Some(mut destinations) = ctx.index_link_destinations(link.line) else {
            continue;
        };

        // Most ordinary lines have only one indexed link. Allocate character
        // checkpoints only when this line actually needs repeated columns.
        let mut first_column = true;
        let mut column_at = |offset| {
            if std::mem::replace(&mut first_column, false) {
                byte_to_char_count(line, offset - line_info.byte_offset)
            } else {
                positions.column_on_line(line_idx, offset) + 1
            }
        };

        // Find all links in this line
        for link_match in LINK_START_REGEX.find_iter(line) {
            let start_pos = link_match.start();
            let end_pos = link_match.end();

            // Calculate absolute position for code span detection
            let line_start_byte = ctx.line_start_byte(line_idx + 1).unwrap_or(0);
            let absolute_start_pos = line_start_byte + start_pos;

            // Skip if in code span
            if ctx.is_in_code_span_byte(absolute_start_pos) {
                continue;
            }

            // Extract the URL (group 1) and fragment (group 2)
            // Try angle-bracket regex first (handles URLs with parens)
            if let Some(destination) = destinations.at(end_pos - 1) {
                let file_path = content[destination.url.clone()].trim();
                let fragment = destination.fragment(content).trim_start_matches('#');

                // Root-relative links (leading `/`) resolve against content roots
                // in the LSP, not the source directory, so they are captured in a
                // separate bucket. Protocol-relative (`//host`) and parent-traversal
                // links are excluded so they cannot escape a content root.
                if let Some(rel) = file_path.strip_prefix('/') {
                    if !rel.starts_with('/')
                        && !Path::new(rel)
                            .components()
                            .any(|c| matches!(c, std::path::Component::ParentDir))
                    {
                        let stripped = strip_query_and_fragment(rel);
                        if is_markdown_file(&url_decode(stripped)) {
                            links.root_relative.push(CrossFileLinkIndex {
                                target_path: stripped.to_string(),
                                fragment: fragment.to_string(),
                                line: link.line,
                                column: column_at(destination.url.start),
                                origin: LinkOrigin::Body,
                            });
                        }
                    }
                    continue;
                }

                // Skip empty, external, template variables, framework aliases,
                // fragment-only URLs, or rustdoc intra-doc links
                if file_path.is_empty()
                    || PROTOCOL_DOMAIN_REGEX.is_match(file_path)
                    || file_path.starts_with("www.")
                    || file_path.starts_with('#')
                    || file_path.starts_with("{{")
                    || file_path.starts_with("{%")
                    || file_path.starts_with('~')
                    || file_path.starts_with('@')
                    || (file_path.starts_with('`') && file_path.ends_with('`'))
                {
                    continue;
                }

                // Strip query parameters before indexing
                let file_path = strip_query_and_fragment(file_path);

                // Only index markdown file links for cross-file validation. The
                // extension is read from the decoded name, so `guide%2Emd` is
                // the Markdown file `guide.md`.
                if is_markdown_file(&url_decode(file_path)) {
                    links.relative.push(CrossFileLinkIndex {
                        target_path: file_path.to_string(),
                        fragment: fragment.to_string(),
                        line: link.line,
                        column: column_at(destination.url.start),
                        origin: LinkOrigin::Body,
                    });
                }
            }
        }
    }

    links
}

/// Magic bytes identifying a workspace index cache file
#[cfg(feature = "postcard")]
const CACHE_MAGIC: &[u8; 4] = b"RWSI";

/// Cache format version - increment when WorkspaceIndex serialization changes
/// or when the meaning of persisted fields changes such that older caches are
/// no longer correct. Version 9 adds `CrossFileLinkIndex::origin`; postcard is
/// not self-describing, so a version 8 cache would decode the following field's
/// bytes as the new one and yield nonsense.
///
/// Version 10 changes what `cross_file_links` holds rather than how it is laid
/// out: one link is now one entry however each rule spells the destination. The
/// bytes still decode, so nothing here would notice, and a cached index is
/// reused whole when a file's content is unchanged - a version 9 cache would
/// keep reporting the duplicate this version exists to stop.
///
/// Version 11 is the same shape of change: a file's entry no longer depends on
/// its own `per-file-ignores`, so an entry written before it can be missing the
/// headings an ignored rule would have recorded. Content is what decides reuse,
/// and the content did not change, so without this the fixed build would keep
/// serving the false positive from the cache the old one left behind.
///
/// Version 12 adds the path inputs MD057 needs to validate a cached lint result.
/// An older entry cannot distinguish a document with no paths from one whose
/// path data was never recorded.
///
/// Version 13 excludes Markdown-looking YAML strings from `cross_file_links`.
/// Their content is unchanged, so older cached entries must be invalidated to
/// avoid retaining phantom body links parsed from frontmatter.
///
/// Version 14 adds `HeadingIndex::text_lines` between `line` and `is_setext`.
/// The index file sits directly in the cache directory, not under a rumdl
/// version, so a version 13 file written by an earlier release would otherwise
/// be decoded with the new layout.
///
/// Version 15 reads a link's extension from its percent-decoded path, so a
/// destination such as `guide%2Emd#part` is now a Markdown link in
/// `cross_file_links`. The content is unchanged, so an entry written before it
/// would keep omitting that link.
#[cfg(feature = "postcard")]
const CACHE_FORMAT_VERSION: u32 = 15;

/// Cache file name within the version directory
#[cfg(feature = "postcard")]
const CACHE_FILE_NAME: &str = "workspace_index.bin";

/// Monotonic counter making cache temp-file names unique per write, mirroring
/// `cache.rs`. Combined with the process id (where available) it keeps
/// concurrent writers from colliding on the temp path before the atomic rename.
#[cfg(feature = "postcard")]
static CACHE_TEMP_COUNTER: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);

/// Workspace-wide index for cross-file analysis
///
/// Contains pre-extracted information from all markdown files in the workspace,
/// enabling rules to validate cross-file references efficiently.
#[derive(Debug, Default, Clone, Serialize, Deserialize)]
pub struct WorkspaceIndex {
    /// Map from file path to its extracted data
    files: HashMap<PathBuf, FileIndex>,
    /// Reverse dependency graph: target file → files that link to it
    /// Used to efficiently re-lint dependent files when a target changes
    reverse_deps: HashMap<PathBuf, HashSet<PathBuf>>,
    /// Version counter for cache invalidation (incremented on any change)
    version: u64,
    /// The run's supplied document set, when the run lints documents that did
    /// not come from disk. Cross-file rules resolve a destination through it
    /// the way the per-file pass does, so both agree on which file a link
    /// names. Run-scoped, so never written to the cache.
    #[serde(skip)]
    link_target_policy: Option<crate::lint_context::LinkTargetPolicy>,
}

/// Index data extracted from a single file
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct FileIndex {
    /// Headings in this file with their anchors
    pub headings: Vec<HeadingIndex>,
    /// Reference links in this file (for cross-file analysis)
    pub reference_links: Vec<ReferenceLinkIndex>,
    /// Cross-file links in this file (for MD051 cross-file validation)
    pub cross_file_links: Vec<CrossFileLinkIndex>,
    /// Root-relative links (leading `/`) in this file. Resolved against the
    /// configured content roots by the LSP for go-to-definition, hover, and
    /// find-references. `target_path` has the leading `/` stripped. Linting does
    /// not use these, so they never affect diagnostics.
    #[serde(default)]
    pub root_relative_links: Vec<CrossFileLinkIndex>,
    /// Filesystem destinations MD057 may validate for this file.
    ///
    /// These inputs stay unresolved so the rule can apply the current search
    /// paths, absolute-link policy, and per-file flavor during cache lookup.
    #[serde(default)]
    pub md057_link_targets: Vec<Md057LinkTarget>,
    /// Defined reference IDs (e.g., from `[ref]: url` definitions)
    /// Used to filter out reference links that have explicit definitions
    pub defined_references: HashSet<String>,
    /// Content hash for change detection
    pub content_hash: String,
    /// O(1) anchor lookup: lowercased anchor → heading index
    /// Includes both auto-generated and custom anchors
    anchor_to_heading: HashMap<String, usize>,
    /// O(1) anchor lookup with original case preserved → heading index.
    /// Used for `ignore_case = false` (markdownlint strict parity). Skipped at
    /// query time when the lowercase map is sufficient.
    #[serde(default)]
    anchor_to_heading_exact: HashMap<String, usize>,
    /// HTML anchors defined via `<a id="...">` or `<element id="...">` tags.
    /// Stored lowercase for case-insensitive matching.
    html_anchors: HashSet<String>,
    /// HTML anchors with original case preserved.
    /// Used for `ignore_case = false` (markdownlint strict parity).
    #[serde(default)]
    html_anchors_exact: HashSet<String>,
    /// Attribute anchors defined via { #id } syntax (kramdown/MkDocs attr_list).
    /// Can appear on any element, not just headings.
    /// Stored lowercase for case-insensitive matching.
    attribute_anchors: HashSet<String>,
    /// Attribute anchors with original case preserved.
    /// Used for `ignore_case = false` (markdownlint strict parity).
    #[serde(default)]
    attribute_anchors_exact: HashSet<String>,
    /// Rules disabled for the entire file (from inline comments)
    /// Used by cross-file rules to respect inline disable directives
    pub file_disabled_rules: HashSet<String>,
    /// Persistent disable/enable state transitions, sorted by line number.
    /// Each entry: (line, disabled_rules, enabled_rules). Use binary search to query.
    pub persistent_transitions: Vec<(usize, HashSet<String>, HashSet<String>)>,
    /// Rules disabled at specific lines via disable-line / disable-next-line
    pub line_disabled_rules: HashMap<usize, HashSet<String>>,
}

/// Information about a heading for cross-file lookup
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct HeadingIndex {
    /// The heading text (e.g., "Installation Guide")
    pub text: String,
    /// Auto-generated anchor (e.g., "installation-guide")
    pub auto_anchor: String,
    /// Custom anchor if present (e.g., "install")
    pub custom_anchor: Option<String>,
    /// Line number of the last line holding the heading text (1-indexed)
    pub line: usize,
    /// How many source lines hold the heading text: 1 for an ATX heading, and
    /// the length of the paragraph a setext underline ends. The first text line
    /// is `line + 1 - text_lines`.
    pub text_lines: usize,
    /// Whether this is a Setext-style heading (underlined with = or -)
    #[serde(default)]
    pub is_setext: bool,
}

impl HeadingIndex {
    /// Line number of the first line holding the heading text (1-indexed).
    #[must_use]
    pub fn first_line(&self) -> usize {
        self.line + 1 - self.text_lines.max(1)
    }

    /// Whether the 1-indexed `line` holds part of the heading text.
    #[must_use]
    pub fn covers_line(&self, line: usize) -> bool {
        (self.first_line()..=self.line).contains(&line)
    }
}

/// Information about a reference link for cross-file analysis
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ReferenceLinkIndex {
    /// The reference ID (the part in `[text][ref]`)
    pub reference_id: String,
    /// Line number (1-indexed)
    pub line: usize,
    /// Column number (1-indexed)
    pub column: usize,
}

/// Where a cross-file link was written.
///
/// The index holds one entry per file while configuration resolves per file, so
/// it records where a link came from rather than whether some configuration
/// wanted it, and the rule reading it applies its own settings at check time.
/// That is the only arrangement that can be right when two files resolving
/// different configurations reference the same target.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub enum LinkOrigin {
    /// The document body.
    Body,
    /// A frontmatter value that reads as a path, such as `link: other.md#a`.
    /// `field` is the lowercased top-level key owning the value, or `None` where
    /// no owner is determinable. The two are kept distinct from `Body` so a
    /// value with no determinable owner is still recognizable as frontmatter.
    ///
    /// A Markdown link that happens to be written inside frontmatter
    /// (`link: [a](other.md#a)`) is `Body`: it is real Markdown link syntax, so
    /// the extraction that finds body links finds it and rename can rewrite it.
    FrontMatter { field: Option<String> },
}

/// Information about a cross-file link for validation
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct CrossFileLinkIndex {
    /// The target file path (relative, as it appears in the link)
    pub target_path: String,
    /// The fragment/anchor being linked to (without #)
    pub fragment: String,
    /// Line number (1-indexed)
    pub line: usize,
    /// Column number (1-indexed)
    pub column: usize,
    /// Where in the document the link was written.
    pub origin: LinkOrigin,
}

/// A path input whose filesystem state can affect MD057's per-file verdict.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Md057LinkTarget {
    /// The destination as MD057 passes it to its resolver.
    pub target: String,
    /// Whether the destination came from Markdown syntax or frontmatter.
    pub origin: LinkOrigin,
}

/// Every path a cross-file link target can name, in the order to try them.
///
/// The target is resolved against the directory holding the link and normalized,
/// or against the project root when it starts with `/`.
/// A target carrying no extension is then tried against each extension discovery
/// treats as Markdown, so a GitHub-style `[x](page#section)` finds `page.md`. A
/// query string is not part of a file name, so `other.md?raw=true` names
/// `other.md`, and the path is percent-decoded, so `guide%20one.md` names
/// `guide one.md`.
///
/// This is the single answer to "which file does this link mean", shared by the
/// workspace index lookup and by any caller that has to read the target itself.
pub fn link_target_candidates(source_file: &Path, target_path: &str) -> Vec<PathBuf> {
    let joined = resolve_target_against(source_file.parent().unwrap_or(Path::new("")), target_path);
    let base = normalize_relative_path(&joined);

    if base.extension().is_some() {
        return vec![base];
    }

    // The exact path first: an extension-less file can be indexed under the name
    // as written.
    let mut candidates = Vec::with_capacity(crate::discovery::MARKDOWN_EXTENSIONS.len() + 1);
    for ext in crate::discovery::MARKDOWN_EXTENSIONS {
        candidates.push(base.with_extension(ext));
    }
    candidates.insert(0, base);
    candidates
}

/// The working directory as the process reports it, in canonical form, and
/// as [`crate::discovery::canonicalize_for_matching`] spells it.
///
/// A path under any of these spellings is inside the working directory. Read
/// once, because the working directory does not change during a run. The
/// spelling the process reports comes last.
static WORKING_DIRECTORY_SPELLINGS: LazyLock<Vec<PathBuf>> = LazyLock::new(|| {
    let mut spellings = Vec::new();
    if let Ok(cwd) = std::env::current_dir() {
        let cwd = normalize_relative_path(&cwd);
        for spelling in [
            cwd.canonicalize().ok(),
            crate::discovery::canonicalize_for_matching(&cwd),
        ]
        .into_iter()
        .flatten()
        {
            if spelling != cwd && !spellings.contains(&spelling) {
                spellings.push(spelling);
            }
        }
        spellings.push(cwd);
    }
    spellings
});

/// The one key a run of supplied documents indexes a path under.
///
/// One file can be supplied as `docs/a.md`, `./docs/a.md` or
/// `/work/project/docs/a.md`; each has to land on the same entry, or a link
/// resolving to one spelling misses the document supplied under another, and
/// two spellings of one file are not recognized as a duplicate. A path inside
/// the working directory is keyed relative to it, and any other path by its
/// normalized absolute form. An absolute path that reaches the working
/// directory through a symlinked ancestor (`/var` for `/private/var`) is
/// recognized through its deepest existing ancestor, so a supplied document
/// need not exist on disk.
pub fn workspace_key(path: &Path) -> PathBuf {
    let normalized = normalize_relative_path(path);
    if normalized.is_absolute() {
        let inside_working_directory = |absolute: &Path| {
            WORKING_DIRECTORY_SPELLINGS
                .iter()
                .find_map(|cwd| absolute.strip_prefix(cwd).ok().map(Path::to_path_buf))
        };
        return inside_working_directory(&normalized)
            .or_else(|| inside_working_directory(&crate::discovery::resolve_for_matching(&normalized)))
            .unwrap_or(normalized);
    }
    if normalized.starts_with("..")
        && let Some(cwd) = WORKING_DIRECTORY_SPELLINGS.last()
    {
        return workspace_key(&cwd.join(&normalized));
    }
    normalized
}

/// Resolve parent components using filesystem traversal while retaining ordinary
/// symlink names, which configuration ignore patterns match as supplied.
pub fn absolute_selection_path(path: &Path) -> std::io::Result<PathBuf> {
    let absolute = std::path::absolute(path)?;
    let mut selected = PathBuf::new();
    for component in absolute.components() {
        if component == std::path::Component::ParentDir {
            selected = std::fs::canonicalize(&selected)?;
            selected.pop();
        } else {
            selected.push(component.as_os_str());
        }
    }
    Ok(selected)
}

/// Resolve `.` and `..` components without touching the filesystem.
///
/// This is how [`link_target_candidates`] spells the paths it returns, so a caller
/// that has to recognize one of those candidates spells its own path the same way.
///
/// A `..` cancels the name before it, and nothing else. A relative path with no
/// name left to cancel keeps saying `..`, because dropping it would rename the
/// file: `../notes.md` read from `a.md` would become `notes.md`, a different file
/// that may well exist. Above a root there is nothing to name, so `/..` is `/`,
/// which is what the filesystem itself answers.
pub fn normalize_relative_path(path: &Path) -> PathBuf {
    let mut components: Vec<std::path::Component<'_>> = Vec::new();
    for component in path.components() {
        match component {
            std::path::Component::CurDir => {}
            std::path::Component::ParentDir => match components.last() {
                Some(std::path::Component::Normal(_)) => {
                    components.pop();
                }
                Some(std::path::Component::RootDir) => {}
                _ => components.push(component),
            },
            c => components.push(c),
        }
    }
    components.iter().collect()
}

impl CrossFileLinkIndex {
    /// Whether the editor navigates by this link.
    ///
    /// Frontmatter values are excluded. They are indexed so MD051 can validate
    /// them when asked to, but they are not Markdown links: rename computes its
    /// edits by re-parsing the line as one, so it cannot rewrite a frontmatter
    /// value, and listing it as a reference would offer a location that a
    /// subsequent rename silently leaves stale.
    pub fn is_navigable(&self) -> bool {
        matches!(self.origin, LinkOrigin::Body)
    }
}

/// Information about a vulnerable anchor (heading without custom ID)
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct VulnerableAnchor {
    /// File path where the heading is located
    pub file: PathBuf,
    /// Line number of the heading
    pub line: usize,
    /// The heading text
    pub text: String,
}

impl WorkspaceIndex {
    /// Create a new empty workspace index
    pub fn new() -> Self {
        Self::default()
    }

    /// Get the current version (for cache invalidation)
    pub fn version(&self) -> u64 {
        self.version
    }

    /// Get the number of indexed files
    pub fn file_count(&self) -> usize {
        self.files.len()
    }

    /// Check if a file is in the index
    pub fn contains_file(&self, path: &Path) -> bool {
        self.files.contains_key(path)
    }

    /// Get the index data for a specific file
    pub fn get_file(&self, path: &Path) -> Option<&FileIndex> {
        self.files.get(path)
    }

    /// The index entry for a file a link resolved to, however the run spelled
    /// its keys.
    ///
    /// A resolver answers with a path built from the linking document's
    /// directory, while a run keys its files the way it came to them:
    /// canonical absolute paths for a workspace scan, paths relative to the
    /// working directory for supplied documents (see [`workspace_key`]). The
    /// target is looked up as given, then under its workspace key, then under
    /// its canonical path, so each of those runs finds the file it indexed.
    pub fn get_resolved_file(&self, target: &Path) -> Option<&FileIndex> {
        let normalized = normalize_relative_path(target);
        if let Some(index) = self.files.get(&normalized) {
            return Some(index);
        }
        if let Some(index) = self.files.get(&workspace_key(&normalized)) {
            return Some(index);
        }
        // The editor keys files by `canonicalize_for_matching`, which differs
        // from a bare canonical path on Windows (no `\\?\` prefix).
        let canonical = normalized.canonicalize().ok()?;
        let matching = crate::discovery::canonicalize_for_matching(&normalized);
        [Some(canonical), matching]
            .into_iter()
            .flatten()
            .find_map(|path| self.files.get(&path).or_else(|| self.files.get(&workspace_key(&path))))
    }

    /// The run's supplied document set, if it has one.
    pub fn link_target_policy(&self) -> Option<&crate::lint_context::LinkTargetPolicy> {
        self.link_target_policy.as_ref()
    }

    /// Resolve cross-file destinations through a supplied document set.
    pub fn set_link_target_policy(&mut self, policy: crate::lint_context::LinkTargetPolicy) {
        self.link_target_policy = Some(policy);
    }

    /// Insert or update a file's index data
    pub fn insert_file(&mut self, path: PathBuf, index: FileIndex) {
        self.files.insert(path, index);
        self.version = self.version.wrapping_add(1);
    }

    /// Remove a file from the index
    pub fn remove_file(&mut self, path: &Path) -> Option<FileIndex> {
        // Clean up reverse deps for this file
        self.clear_reverse_deps_for(path);

        let result = self.files.remove(path);
        if result.is_some() {
            self.version = self.version.wrapping_add(1);
        }
        result
    }

    /// Build a map of all "vulnerable" anchors across the workspace
    ///
    /// A vulnerable anchor is an auto-generated anchor for a heading that
    /// does NOT have a custom anchor defined. These are problematic for
    /// translated content because the anchor changes when the heading is translated.
    ///
    /// Returns: Map from lowercase anchor → Vec of VulnerableAnchor info
    /// Multiple files can have headings with the same auto-generated anchor,
    /// so we collect all occurrences.
    pub fn get_vulnerable_anchors(&self) -> HashMap<String, Vec<VulnerableAnchor>> {
        let mut vulnerable: HashMap<String, Vec<VulnerableAnchor>> = HashMap::new();

        for (file_path, file_index) in &self.files {
            for heading in &file_index.headings {
                // Only include headings WITHOUT custom anchors
                if heading.custom_anchor.is_none() && !heading.auto_anchor.is_empty() {
                    let anchor_key = heading.auto_anchor.to_lowercase();
                    vulnerable.entry(anchor_key).or_default().push(VulnerableAnchor {
                        file: file_path.clone(),
                        line: heading.line,
                        text: heading.text.clone(),
                    });
                }
            }
        }

        vulnerable
    }

    /// Get all headings across the workspace (for debugging/testing)
    pub fn all_headings(&self) -> impl Iterator<Item = (&Path, &HeadingIndex)> {
        self.files
            .iter()
            .flat_map(|(path, index)| index.headings.iter().map(move |h| (path.as_path(), h)))
    }

    /// Iterate over all files in the index
    pub fn files(&self) -> impl Iterator<Item = (&Path, &FileIndex)> {
        self.files.iter().map(|(p, i)| (p.as_path(), i))
    }

    /// All files in the index, ordered by path.
    ///
    /// `files()` iterates the backing `HashMap` in an unspecified order, so
    /// consumers that emit output (cross-file diagnostics) must use this to
    /// keep results stable across runs on identical input.
    pub fn files_sorted(&self) -> Vec<(&Path, &FileIndex)> {
        let mut entries: Vec<(&Path, &FileIndex)> = self.files.iter().map(|(p, i)| (p.as_path(), i)).collect();
        entries.sort_by_key(|(a, _)| *a);
        entries
    }

    /// Clear the entire index
    pub fn clear(&mut self) {
        self.files.clear();
        self.reverse_deps.clear();
        self.version = self.version.wrapping_add(1);
    }

    /// Update a file's index and maintain reverse dependencies
    ///
    /// This method:
    /// 1. Removes this file as a source (dependent) from all reverse deps
    /// 2. Inserts the new file index
    /// 3. Builds new reverse deps from cross_file_links
    pub fn update_file(&mut self, path: &Path, index: FileIndex) {
        // Remove this file as a source (dependent) from all target entries
        // Note: We don't remove it as a target - other files may still link to it
        self.clear_reverse_deps_as_source(path);

        // Build new reverse deps from cross_file_links
        for link in &index.cross_file_links {
            let target = self.resolve_target_path(path, &link.target_path);
            self.reverse_deps.entry(target).or_default().insert(path.to_path_buf());
        }

        self.files.insert(path.to_path_buf(), index);
        self.version = self.version.wrapping_add(1);
    }

    /// Get files that depend on (link to) the given file
    ///
    /// Returns a list of file paths that contain links targeting this file.
    /// Used to re-lint dependent files when a target file changes.
    pub fn get_dependents(&self, path: &Path) -> Vec<PathBuf> {
        self.reverse_deps
            .get(path)
            .map(|set| set.iter().cloned().collect())
            .unwrap_or_default()
    }

    /// Check if a file needs re-indexing based on its content hash
    ///
    /// Returns `true` if the file is not in the index or has a different hash.
    pub fn is_file_stale(&self, path: &Path, current_hash: &str) -> bool {
        self.files.get(path).is_none_or(|f| f.content_hash != current_hash)
    }

    /// Retain only files that exist in the given set, removing deleted files
    ///
    /// This prunes stale entries from the cache for files that no longer exist.
    /// Returns the number of files removed.
    pub fn retain_only(&mut self, current_files: &std::collections::HashSet<PathBuf>) -> usize {
        let before_count = self.files.len();

        // Collect files to remove
        let to_remove: Vec<PathBuf> = self
            .files
            .keys()
            .filter(|path| !current_files.contains(*path))
            .cloned()
            .collect();

        // Remove each file properly (clears reverse deps)
        for path in &to_remove {
            self.remove_file(path);
        }

        before_count - self.files.len()
    }

    /// Save the workspace index to a cache file
    ///
    /// Uses postcard for efficient binary serialization with:
    /// - Magic header for file type validation
    /// - Format version for compatibility detection
    /// - Atomic writes (temp file + rename) to prevent corruption
    #[cfg(feature = "postcard")]
    pub fn save_to_cache(&self, cache_dir: &Path) -> std::io::Result<()> {
        use std::fs;
        use std::io::Write;

        // Ensure cache directory exists
        fs::create_dir_all(cache_dir)?;

        // Serialize the index data using postcard
        let encoded = postcard::to_allocvec(self)
            .map_err(|e| std::io::Error::new(std::io::ErrorKind::InvalidData, e.to_string()))?;

        // Build versioned cache file: [magic][version][data]
        let mut cache_data = Vec::with_capacity(8 + encoded.len());
        cache_data.extend_from_slice(CACHE_MAGIC);
        cache_data.extend_from_slice(&CACHE_FORMAT_VERSION.to_le_bytes());
        cache_data.extend_from_slice(&encoded);

        // Write atomically: write to temp file then rename. A per-write unique
        // suffix keeps concurrent writers from clobbering each other's temp file
        // before the rename. WASI has no process id, so the counter alone carries
        // uniqueness there (matching `cache.rs`).
        let final_path = cache_dir.join(CACHE_FILE_NAME);
        let counter = CACHE_TEMP_COUNTER.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
        #[cfg(not(target_arch = "wasm32"))]
        let temp_path = cache_dir.join(format!("{CACHE_FILE_NAME}.tmp.{}.{counter}", std::process::id()));
        #[cfg(target_arch = "wasm32")]
        let temp_path = cache_dir.join(format!("{CACHE_FILE_NAME}.tmp.{counter}"));

        // Write to temp file
        {
            let mut file = fs::File::create(&temp_path)?;
            file.write_all(&cache_data)?;
            file.sync_all()?;
        }

        // Atomic rename
        fs::rename(&temp_path, &final_path)?;

        log::debug!(
            "Saved workspace index to cache: {} files, {} bytes (format v{})",
            self.files.len(),
            cache_data.len(),
            CACHE_FORMAT_VERSION
        );

        Ok(())
    }

    /// Load the workspace index from a cache file
    ///
    /// Returns `None` if:
    /// - Cache file doesn't exist
    /// - Magic header doesn't match
    /// - Format version is incompatible
    /// - Data is corrupted
    #[cfg(feature = "postcard")]
    pub fn load_from_cache(cache_dir: &Path) -> Option<Self> {
        use std::fs;

        let path = cache_dir.join(CACHE_FILE_NAME);
        let data = fs::read(&path).ok()?;

        // Validate header: need at least 8 bytes for magic + version
        if data.len() < 8 {
            log::warn!("Workspace index cache too small, discarding");
            let _ = fs::remove_file(&path);
            return None;
        }

        // Check magic header
        if &data[0..4] != CACHE_MAGIC {
            log::warn!("Workspace index cache has invalid magic header, discarding");
            let _ = fs::remove_file(&path);
            return None;
        }

        // Check format version
        let version = u32::from_le_bytes([data[4], data[5], data[6], data[7]]);
        if version != CACHE_FORMAT_VERSION {
            log::info!(
                "Workspace index cache format version mismatch (got {version}, expected {CACHE_FORMAT_VERSION}), rebuilding"
            );
            let _ = fs::remove_file(&path);
            return None;
        }

        // Deserialize the index data using postcard
        match postcard::from_bytes::<Self>(&data[8..]) {
            Ok(index) => {
                log::debug!(
                    "Loaded workspace index from cache: {} files (format v{})",
                    index.files.len(),
                    version
                );
                Some(index)
            }
            Err(e) => {
                log::warn!("Failed to deserialize workspace index cache: {e}");
                let _ = fs::remove_file(&path);
                None
            }
        }
    }

    /// Remove a file as a source from all reverse dependency entries
    ///
    /// This removes the file from being listed as a dependent in all target entries.
    /// Used when updating a file (we need to remove old outgoing links before adding new ones).
    fn clear_reverse_deps_as_source(&mut self, path: &Path) {
        // Remove `path` as a dependent only from the targets it actually links
        // to, discovered from its current index, instead of scanning every
        // entry in reverse_deps. Both callers (update_file, clear_reverse_deps_for)
        // run this before the file's entry is replaced/removed, so self.files[path]
        // still holds the links that produced these reverse-dep entries; resolving
        // them the same way reverses exactly the prior insertions.
        let targets: Vec<PathBuf> = match self.files.get(path) {
            Some(index) => index
                .cross_file_links
                .iter()
                .map(|link| self.resolve_target_path(path, &link.target_path))
                .collect(),
            None => return,
        };
        for target in targets {
            if let Some(deps) = self.reverse_deps.get_mut(&target) {
                deps.remove(path);
                if deps.is_empty() {
                    self.reverse_deps.remove(&target);
                }
            }
        }
    }

    /// Remove a file completely from reverse dependency tracking
    ///
    /// Removes the file as both a source (dependent) and as a target.
    /// Used when deleting a file from the index.
    fn clear_reverse_deps_for(&mut self, path: &Path) {
        // Remove as source (dependent)
        self.clear_reverse_deps_as_source(path);

        // Also remove as target
        self.reverse_deps.remove(path);
    }

    /// Resolve a relative path from a source file to an absolute target path
    ///
    /// This keys the reverse dependency graph, which is looked up by the path of
    /// a file that changed, so it has to answer with a file name - the same
    /// question [`link_target_file`] answers for every other consumer.
    fn resolve_target_path(&self, source_file: &Path, relative_target: &str) -> PathBuf {
        let source_dir = source_file.parent().unwrap_or(Path::new(""));
        link_target_file(source_dir, relative_target)
    }
}

impl FileIndex {
    /// Create a new empty file index
    pub fn new() -> Self {
        Self::default()
    }

    /// Create a file index with the given content hash
    pub fn with_hash(content_hash: String) -> Self {
        Self {
            content_hash,
            ..Default::default()
        }
    }

    /// Whether the data extracted from the file differs, ignoring the hash of
    /// the text it came from.
    ///
    /// This answers whether re-indexing a file can have changed a cross-file
    /// result, its own or that of a file linking to it. Every cross-file check
    /// reads the entry rather than the document, so two entries that agree on
    /// everything compared here produce the same answers however much the text
    /// between them changed. The hash is excluded precisely because it is a
    /// fingerprint of that text: it moves on every keystroke while the links
    /// and anchors a check reads stay put.
    ///
    /// Entries carry the positions their headings and links were written at, so
    /// an edit that adds or removes a line does differ even when it changes no
    /// anchor. That is the conservative direction: it costs a re-lint of the
    /// open files linking here, and never withholds one.
    pub fn extracted_data_differs(&self, other: &Self) -> bool {
        // Destructured so that adding a field to the index is a compile error
        // here rather than a silent omission, which would make a real change
        // look like no change and leave a stale diagnostic on screen.
        let Self {
            headings,
            reference_links,
            cross_file_links,
            root_relative_links,
            md057_link_targets,
            defined_references,
            content_hash: _,
            anchor_to_heading,
            anchor_to_heading_exact,
            html_anchors,
            html_anchors_exact,
            attribute_anchors,
            attribute_anchors_exact,
            file_disabled_rules,
            persistent_transitions,
            line_disabled_rules,
        } = self;

        headings != &other.headings
            || reference_links != &other.reference_links
            || cross_file_links != &other.cross_file_links
            || root_relative_links != &other.root_relative_links
            || md057_link_targets != &other.md057_link_targets
            || defined_references != &other.defined_references
            || anchor_to_heading != &other.anchor_to_heading
            || anchor_to_heading_exact != &other.anchor_to_heading_exact
            || html_anchors != &other.html_anchors
            || html_anchors_exact != &other.html_anchors_exact
            || attribute_anchors != &other.attribute_anchors
            || attribute_anchors_exact != &other.attribute_anchors_exact
            || file_disabled_rules != &other.file_disabled_rules
            || persistent_transitions != &other.persistent_transitions
            || line_disabled_rules != &other.line_disabled_rules
    }

    /// Add a heading to the index
    ///
    /// Also updates the anchor lookup maps for O(1) anchor queries. Both
    /// lowercased (for `ignore_case = true`) and case-preserving (for
    /// `ignore_case = false`) maps are populated.
    pub fn add_heading(&mut self, heading: HeadingIndex) {
        let index = self.headings.len();

        // Auto-generated anchor — slugs are already lowercase, but we still
        // populate both maps so query-time dispatch is uniform.
        self.anchor_to_heading.insert(heading.auto_anchor.to_lowercase(), index);
        self.anchor_to_heading_exact.insert(heading.auto_anchor.clone(), index);

        // Custom anchor preserves original case as written by the author.
        if let Some(ref custom) = heading.custom_anchor {
            self.anchor_to_heading.insert(custom.to_lowercase(), index);
            self.anchor_to_heading_exact.insert(custom.clone(), index);
        }

        self.headings.push(heading);
    }

    /// Add an alternative anchor that resolves to an existing heading.
    /// Used for platform-specific anchor conventions (e.g., Python-Markdown `_N` dedup).
    pub fn add_anchor_alias(&mut self, anchor: &str, heading_index: usize) {
        if heading_index < self.headings.len() {
            self.anchor_to_heading.insert(anchor.to_lowercase(), heading_index);
            self.anchor_to_heading_exact.insert(anchor.to_string(), heading_index);
        }
    }

    /// Check if an anchor exists in this file (O(1) lookup)
    ///
    /// Returns true if the anchor matches any of:
    /// - Auto-generated heading anchors
    /// - Custom heading anchors (from {#id} syntax on headings)
    /// - HTML anchors (from `<a id="...">` or `<element id="...">`)
    /// - Attribute anchors (from { #id } syntax on non-heading elements)
    ///
    /// Matching is case-insensitive. URL-encoded anchors (e.g., CJK characters
    /// like `%E6%97%A5%E6%9C%AC%E8%AA%9E` for `日本語`) are decoded before matching.
    pub fn has_anchor(&self, anchor: &str) -> bool {
        self.has_anchor_with_case(anchor, true)
    }

    /// Check if an anchor exists in this file, with explicit case sensitivity.
    ///
    /// When `ignore_case` is `true`, behaves identically to [`Self::has_anchor`]:
    /// inputs are lowercased and matched against the lowercase storage.
    /// When `false`, the input is compared as-is against parallel
    /// case-preserving storage, matching markdownlint's strict behavior for
    /// generated heading slugs, custom heading IDs, HTML anchors, and
    /// attribute anchors.
    pub fn has_anchor_with_case(&self, anchor: &str, ignore_case: bool) -> bool {
        if self.lookup_anchor(anchor, ignore_case) {
            return true;
        }

        // Slow path: if anchor contains percent-encoding, try decoded version
        if anchor.contains('%') {
            let decoded = url_decode(anchor);
            if decoded != anchor {
                return self.lookup_anchor(&decoded, ignore_case);
            }
        }

        false
    }

    /// Direct anchor lookup, dispatching to the lowercase or exact-case
    /// storage based on `ignore_case`.
    fn lookup_anchor(&self, anchor: &str, ignore_case: bool) -> bool {
        if ignore_case {
            let lower = anchor.to_lowercase();
            self.anchor_to_heading.contains_key(&lower)
                || self.html_anchors.contains(&lower)
                || self.attribute_anchors.contains(&lower)
        } else {
            self.anchor_to_heading_exact.contains_key(anchor)
                || self.html_anchors_exact.contains(anchor)
                || self.attribute_anchors_exact.contains(anchor)
        }
    }

    /// Add an HTML anchor (from `<a id="...">` or `<element id="...">` tags).
    /// Populates both lowercase (case-insensitive) and case-preserving sets.
    pub fn add_html_anchor(&mut self, anchor: &str) {
        if !anchor.is_empty() {
            self.html_anchors.insert(anchor.to_lowercase());
            self.html_anchors_exact.insert(anchor.to_string());
        }
    }

    /// Add an attribute anchor (from { #id } syntax on non-heading elements).
    /// Populates both lowercase (case-insensitive) and case-preserving sets.
    pub fn add_attribute_anchor(&mut self, anchor: &str) {
        if !anchor.is_empty() {
            self.attribute_anchors.insert(anchor.to_lowercase());
            self.attribute_anchors_exact.insert(anchor.to_string());
        }
    }

    /// Get the heading index for an anchor (O(1) lookup)
    ///
    /// Returns the index into `self.headings` if found.
    pub fn get_heading_by_anchor(&self, anchor: &str) -> Option<&HeadingIndex> {
        self.anchor_to_heading
            .get(&anchor.to_lowercase())
            .and_then(|&idx| self.headings.get(idx))
    }

    /// Add a reference link to the index
    pub fn add_reference_link(&mut self, link: ReferenceLinkIndex) {
        self.reference_links.push(link);
    }

    /// Check if a rule is disabled at a specific line
    ///
    /// Used by cross-file rules to respect inline disable directives.
    /// Checks both file-wide disables and line-specific disables.
    pub fn is_rule_disabled_at_line(&self, rule_name: &str, line: usize) -> bool {
        // Check file-wide disables (highest priority)
        if self.file_disabled_rules.contains("*") || self.file_disabled_rules.contains(rule_name) {
            return true;
        }

        // Check line-specific disables (disable-line / disable-next-line)
        if let Some(rules) = self.line_disabled_rules.get(&line)
            && (rules.contains("*") || rules.contains(rule_name))
        {
            return true;
        }

        // Check persistent disable/enable transitions via binary search
        if !self.persistent_transitions.is_empty() {
            let idx = match self.persistent_transitions.binary_search_by_key(&line, |t| t.0) {
                Ok(i) => Some(i),
                Err(i) => {
                    if i > 0 {
                        Some(i - 1)
                    } else {
                        None
                    }
                }
            };
            if let Some(i) = idx {
                let (_, ref disabled, ref enabled) = self.persistent_transitions[i];
                if disabled.contains("*") {
                    return !enabled.contains(rule_name);
                }
                return disabled.contains(rule_name);
            }
        }

        false
    }

    /// Add a cross-file link to the index, keyed on the file it names, the
    /// fragment it asks for, and the line it sits on.
    ///
    /// Several rules contribute the same link and spell it differently: MD051
    /// records the destination as written and starts at the link, MD057 records
    /// the file that destination names and starts at the URL. Neither the string
    /// nor the column can identify a link, so the file it names does - comparing
    /// the raw strings let `page.md?raw=true` in as a second entry alongside
    /// `page.md`, and MD051, which reports every entry, then reported the same
    /// broken fragment twice.
    ///
    /// One key per line is what the index has always recorded, so two links on
    /// one line asking the same file for the same fragment are one entry
    /// however each of them spells the destination.
    pub fn add_cross_file_link(&mut self, link: CrossFileLinkIndex) {
        let existing = self.cross_file_links.iter_mut().find(|existing| {
            existing.fragment == link.fragment
                && existing.line == link.line
                && strip_query_and_fragment(&existing.target_path) == strip_query_and_fragment(&link.target_path)
        });
        match existing {
            // A message quotes the destination back, so the spelling that kept the
            // query string is the one to keep, whichever rule recorded it first.
            Some(existing) => {
                if !existing.target_path.contains('?') && link.target_path.contains('?') {
                    *existing = link;
                }
            }
            None => self.cross_file_links.push(link),
        }
    }

    /// Add a root-relative link to the index (deduplicates by target_path, fragment, line)
    pub fn add_root_relative_link(&mut self, link: CrossFileLinkIndex) {
        let is_duplicate = self.root_relative_links.iter().any(|existing| {
            existing.target_path == link.target_path && existing.fragment == link.fragment && existing.line == link.line
        });
        if !is_duplicate {
            self.root_relative_links.push(link);
        }
    }

    /// Add one filesystem destination used by MD057.
    pub fn add_md057_link_target(&mut self, target: Md057LinkTarget) {
        self.md057_link_targets.push(target);
    }

    /// Add a defined reference ID (e.g., from `[ref]: url`)
    pub fn add_defined_reference(&mut self, ref_id: String) {
        self.defined_references.insert(ref_id);
    }

    /// Check if a reference ID has an explicit definition
    pub fn has_defined_reference(&self, ref_id: &str) -> bool {
        self.defined_references.contains(ref_id)
    }

    /// Check if the content hash matches
    pub fn hash_matches(&self, hash: &str) -> bool {
        self.content_hash == hash
    }

    /// Get the number of headings
    pub fn heading_count(&self) -> usize {
        self.headings.len()
    }

    /// Get the number of reference links
    pub fn reference_link_count(&self) -> usize {
        self.reference_links.len()
    }
}

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

    #[test]
    fn test_workspace_index_basic() {
        let mut index = WorkspaceIndex::new();
        assert_eq!(index.file_count(), 0);
        assert_eq!(index.version(), 0);

        let mut file_index = FileIndex::with_hash("abc123".to_string());
        file_index.add_heading(HeadingIndex {
            text: "Installation".to_string(),
            auto_anchor: "installation".to_string(),
            custom_anchor: None,
            line: 1,
            text_lines: 1,
            is_setext: false,
        });

        index.insert_file(PathBuf::from("docs/install.md"), file_index);
        assert_eq!(index.file_count(), 1);
        assert_eq!(index.version(), 1);

        assert!(index.contains_file(Path::new("docs/install.md")));
        assert!(!index.contains_file(Path::new("docs/other.md")));
    }

    #[test]
    fn test_vulnerable_anchors() {
        let mut index = WorkspaceIndex::new();

        // File 1: heading without custom anchor (vulnerable)
        let mut file1 = FileIndex::new();
        file1.add_heading(HeadingIndex {
            text: "Getting Started".to_string(),
            auto_anchor: "getting-started".to_string(),
            custom_anchor: None,
            line: 1,
            text_lines: 1,
            is_setext: false,
        });
        index.insert_file(PathBuf::from("docs/guide.md"), file1);

        // File 2: heading with custom anchor (not vulnerable)
        let mut file2 = FileIndex::new();
        file2.add_heading(HeadingIndex {
            text: "Installation".to_string(),
            auto_anchor: "installation".to_string(),
            custom_anchor: Some("install".to_string()),
            line: 1,
            text_lines: 1,
            is_setext: false,
        });
        index.insert_file(PathBuf::from("docs/install.md"), file2);

        let vulnerable = index.get_vulnerable_anchors();
        assert_eq!(vulnerable.len(), 1);
        assert!(vulnerable.contains_key("getting-started"));
        assert!(!vulnerable.contains_key("installation"));

        let anchors = vulnerable.get("getting-started").unwrap();
        assert_eq!(anchors.len(), 1);
        assert_eq!(anchors[0].file, PathBuf::from("docs/guide.md"));
        assert_eq!(anchors[0].text, "Getting Started");
    }

    #[test]
    fn test_vulnerable_anchors_multiple_files_same_anchor() {
        // Multiple files can have headings with the same auto-generated anchor
        // get_vulnerable_anchors() should collect all of them
        let mut index = WorkspaceIndex::new();

        // File 1: has "Installation" heading (vulnerable)
        let mut file1 = FileIndex::new();
        file1.add_heading(HeadingIndex {
            text: "Installation".to_string(),
            auto_anchor: "installation".to_string(),
            custom_anchor: None,
            line: 1,
            text_lines: 1,
            is_setext: false,
        });
        index.insert_file(PathBuf::from("docs/en/guide.md"), file1);

        // File 2: also has "Installation" heading with same anchor (vulnerable)
        let mut file2 = FileIndex::new();
        file2.add_heading(HeadingIndex {
            text: "Installation".to_string(),
            auto_anchor: "installation".to_string(),
            custom_anchor: None,
            line: 5,
            text_lines: 1,
            is_setext: false,
        });
        index.insert_file(PathBuf::from("docs/fr/guide.md"), file2);

        // File 3: has "Installation" but WITH custom anchor (not vulnerable)
        let mut file3 = FileIndex::new();
        file3.add_heading(HeadingIndex {
            text: "Installation".to_string(),
            auto_anchor: "installation".to_string(),
            custom_anchor: Some("install".to_string()),
            line: 10,
            text_lines: 1,
            is_setext: false,
        });
        index.insert_file(PathBuf::from("docs/de/guide.md"), file3);

        let vulnerable = index.get_vulnerable_anchors();
        assert_eq!(vulnerable.len(), 1); // One unique anchor
        assert!(vulnerable.contains_key("installation"));

        let anchors = vulnerable.get("installation").unwrap();
        // Should have 2 entries (en and fr), NOT 3 (de has custom anchor)
        assert_eq!(anchors.len(), 2, "Should collect both vulnerable anchors");

        // Verify both files are represented
        let files: std::collections::HashSet<_> = anchors.iter().map(|a| &a.file).collect();
        assert!(files.contains(&PathBuf::from("docs/en/guide.md")));
        assert!(files.contains(&PathBuf::from("docs/fr/guide.md")));
    }

    #[test]
    fn test_file_index_hash() {
        let index = FileIndex::with_hash("hash123".to_string());
        assert!(index.hash_matches("hash123"));
        assert!(!index.hash_matches("other"));
    }

    #[test]
    fn test_version_increment() {
        let mut index = WorkspaceIndex::new();
        assert_eq!(index.version(), 0);

        index.insert_file(PathBuf::from("a.md"), FileIndex::new());
        assert_eq!(index.version(), 1);

        index.insert_file(PathBuf::from("b.md"), FileIndex::new());
        assert_eq!(index.version(), 2);

        index.remove_file(Path::new("a.md"));
        assert_eq!(index.version(), 3);

        // Removing non-existent file doesn't increment
        index.remove_file(Path::new("nonexistent.md"));
        assert_eq!(index.version(), 3);
    }

    #[test]
    fn test_files_sorted_is_path_ordered() {
        let mut index = WorkspaceIndex::new();
        // Insert in a deliberately non-sorted order.
        for name in ["docs/zebra.md", "docs/apple.md", "docs/mango.md"] {
            index.update_file(Path::new(name), FileIndex::new());
        }

        let paths: Vec<&Path> = index.files_sorted().into_iter().map(|(p, _)| p).collect();
        assert_eq!(
            paths,
            vec![
                Path::new("docs/apple.md"),
                Path::new("docs/mango.md"),
                Path::new("docs/zebra.md"),
            ],
            "files_sorted() must return entries ordered by path"
        );
    }

    /// Two rules record the same link, one keeping the query string and one
    /// keeping only the file it names. That is one link, and the spelling kept
    /// is the destination as written whichever rule got there first - a message
    /// quotes it back, so the answer must not depend on rule order.
    #[test]
    fn test_add_cross_file_link_keeps_the_destination_as_written() {
        let as_written = CrossFileLinkIndex {
            target_path: "other.md?raw=true".to_string(),
            fragment: "missing".to_string(),
            line: 3,
            column: 1,
            origin: LinkOrigin::Body,
        };
        let file_named = CrossFileLinkIndex {
            target_path: "other.md".to_string(),
            fragment: "missing".to_string(),
            line: 3,
            column: 9,
            origin: LinkOrigin::Body,
        };

        for (first, second) in [
            (as_written.clone(), file_named.clone()),
            (file_named.clone(), as_written.clone()),
        ] {
            let mut index = FileIndex::new();
            index.add_cross_file_link(first);
            index.add_cross_file_link(second);

            assert_eq!(
                index.cross_file_links.len(),
                1,
                "one link is one entry, got: {:?}",
                index.cross_file_links
            );
            assert_eq!(index.cross_file_links[0].target_path, "other.md?raw=true");
        }
    }

    /// Links to two different files are two entries, so the deduplication above
    /// cannot swallow a second target.
    #[test]
    fn test_add_cross_file_link_keeps_distinct_targets() {
        let mut index = FileIndex::new();
        for target in ["one.md", "two.md"] {
            index.add_cross_file_link(CrossFileLinkIndex {
                target_path: target.to_string(),
                fragment: "missing".to_string(),
                line: 3,
                column: 1,
                origin: LinkOrigin::Body,
            });
        }
        assert_eq!(index.cross_file_links.len(), 2);
    }

    /// Two links on one line asking the same file for the same fragment are one
    /// entry, which is what the index has always recorded for two identically
    /// spelled destinations. Differing query strings do not make them two links,
    /// because a query string is not part of a file name.
    ///
    /// A different fragment, or the same link on another line, stays its own
    /// entry - so this is a boundary, not a blanket collapse to one finding.
    #[test]
    fn test_add_cross_file_link_collapses_one_line_asking_one_file_once() {
        let link = |target: &str, fragment: &str, line: usize| CrossFileLinkIndex {
            target_path: target.to_string(),
            fragment: fragment.to_string(),
            line,
            column: 1,
            origin: LinkOrigin::Body,
        };

        let mut index = FileIndex::new();
        index.add_cross_file_link(link("target.md?raw=true", "missing", 3));
        index.add_cross_file_link(link("target.md?plain=1", "missing", 3));
        assert_eq!(
            index.cross_file_links.len(),
            1,
            "one file, one fragment, one line is one entry, got: {:?}",
            index.cross_file_links
        );

        index.add_cross_file_link(link("target.md", "other", 3));
        index.add_cross_file_link(link("target.md", "missing", 4));
        assert_eq!(index.cross_file_links.len(), 3);
    }

    /// A link is a dependency on the file it names, so editing `b.md` re-lints
    /// the source whichever way that source spelled the destination. The query
    /// string is the case that gets this wrong: it is not part of a file name,
    /// nothing ever creates a file called `b.md?raw=true`, and a reverse
    /// dependency filed under that name is one no editor will ever look up.
    #[test]
    fn test_reverse_deps_ignore_a_query_string_on_the_destination() {
        let mut index = WorkspaceIndex::new();

        let mut file_a = FileIndex::new();
        file_a.add_cross_file_link(CrossFileLinkIndex {
            target_path: "b.md?raw=true".to_string(),
            fragment: "section".to_string(),
            line: 10,
            column: 5,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/a.md"), file_a);

        assert_eq!(
            index.get_dependents(Path::new("docs/b.md")),
            vec![PathBuf::from("docs/a.md")],
            "editing docs/b.md must re-lint the file linking to it"
        );

        // And the source stops depending on it once the link is gone, so the
        // stripped key is cleared by the same route it was created.
        index.update_file(Path::new("docs/a.md"), FileIndex::new());
        assert!(index.get_dependents(Path::new("docs/b.md")).is_empty());
    }

    #[test]
    fn test_reverse_deps_basic() {
        let mut index = WorkspaceIndex::new();

        // File A links to file B
        let mut file_a = FileIndex::new();
        file_a.add_cross_file_link(CrossFileLinkIndex {
            target_path: "b.md".to_string(),
            fragment: "section".to_string(),
            line: 10,
            column: 5,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/a.md"), file_a);

        // Check that B has A as a dependent
        let dependents = index.get_dependents(Path::new("docs/b.md"));
        assert_eq!(dependents.len(), 1);
        assert_eq!(dependents[0], PathBuf::from("docs/a.md"));

        // A has no dependents
        let a_dependents = index.get_dependents(Path::new("docs/a.md"));
        assert!(a_dependents.is_empty());
    }

    #[test]
    fn test_reverse_deps_multiple() {
        let mut index = WorkspaceIndex::new();

        // Files A and C both link to B
        let mut file_a = FileIndex::new();
        file_a.add_cross_file_link(CrossFileLinkIndex {
            target_path: "../b.md".to_string(),
            fragment: "".to_string(),
            line: 1,
            column: 1,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/sub/a.md"), file_a);

        let mut file_c = FileIndex::new();
        file_c.add_cross_file_link(CrossFileLinkIndex {
            target_path: "b.md".to_string(),
            fragment: "".to_string(),
            line: 1,
            column: 1,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/c.md"), file_c);

        // B should have both A and C as dependents
        let dependents = index.get_dependents(Path::new("docs/b.md"));
        assert_eq!(dependents.len(), 2);
        assert!(dependents.contains(&PathBuf::from("docs/sub/a.md")));
        assert!(dependents.contains(&PathBuf::from("docs/c.md")));
    }

    #[test]
    fn test_reverse_deps_update_clears_old() {
        let mut index = WorkspaceIndex::new();

        // File A initially links to B
        let mut file_a = FileIndex::new();
        file_a.add_cross_file_link(CrossFileLinkIndex {
            target_path: "b.md".to_string(),
            fragment: "".to_string(),
            line: 1,
            column: 1,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/a.md"), file_a);

        // Verify B has A as dependent
        assert_eq!(index.get_dependents(Path::new("docs/b.md")).len(), 1);

        // Update A to link to C instead of B
        let mut file_a_updated = FileIndex::new();
        file_a_updated.add_cross_file_link(CrossFileLinkIndex {
            target_path: "c.md".to_string(),
            fragment: "".to_string(),
            line: 1,
            column: 1,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/a.md"), file_a_updated);

        // B should no longer have A as dependent
        assert!(index.get_dependents(Path::new("docs/b.md")).is_empty());

        // C should now have A as dependent
        let c_deps = index.get_dependents(Path::new("docs/c.md"));
        assert_eq!(c_deps.len(), 1);
        assert_eq!(c_deps[0], PathBuf::from("docs/a.md"));
    }

    #[test]
    fn test_reverse_deps_remove_file() {
        let mut index = WorkspaceIndex::new();

        // File A links to B
        let mut file_a = FileIndex::new();
        file_a.add_cross_file_link(CrossFileLinkIndex {
            target_path: "b.md".to_string(),
            fragment: "".to_string(),
            line: 1,
            column: 1,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/a.md"), file_a);

        // Verify B has A as dependent
        assert_eq!(index.get_dependents(Path::new("docs/b.md")).len(), 1);

        // Remove file A
        index.remove_file(Path::new("docs/a.md"));

        // B should no longer have any dependents
        assert!(index.get_dependents(Path::new("docs/b.md")).is_empty());
    }

    #[test]
    fn test_normalize_path() {
        // Test .. handling
        let path = Path::new("docs/sub/../other.md");
        let normalized = normalize_relative_path(path);
        assert_eq!(normalized, PathBuf::from("docs/other.md"));

        // Test . handling
        let path2 = Path::new("docs/./other.md");
        let normalized2 = normalize_relative_path(path2);
        assert_eq!(normalized2, PathBuf::from("docs/other.md"));

        // Test multiple ..
        let path3 = Path::new("a/b/c/../../d.md");
        let normalized3 = normalize_relative_path(path3);
        assert_eq!(normalized3, PathBuf::from("a/d.md"));
    }

    /// A `..` with no name in front of it is the path saying it leaves the
    /// directory it started in. Dropping it renames the file - `../notes.md`
    /// would become `notes.md`, a sibling that may well exist and is not the file
    /// the link names - so it survives normalization.
    #[test]
    fn normalize_keeps_a_traversal_that_leaves_its_own_root() {
        assert_eq!(
            normalize_relative_path(Path::new("../notes.md")),
            PathBuf::from("../notes.md")
        );
        assert_eq!(
            normalize_relative_path(Path::new("docs/../../notes.md")),
            PathBuf::from("../notes.md")
        );
        assert_eq!(
            normalize_relative_path(Path::new("../../a/./b/../notes.md")),
            PathBuf::from("../../a/notes.md")
        );
    }

    /// There is nothing above a root to name, which is what the filesystem
    /// itself answers for `/..`.
    #[test]
    fn normalize_stops_a_traversal_at_a_root() {
        let root = if cfg!(windows) { "C:\\" } else { "/" };
        assert_eq!(
            normalize_relative_path(&Path::new(root).join("..").join("notes.md")),
            Path::new(root).join("notes.md")
        );
    }

    #[test]
    fn test_clear_clears_reverse_deps() {
        let mut index = WorkspaceIndex::new();

        // File A links to B
        let mut file_a = FileIndex::new();
        file_a.add_cross_file_link(CrossFileLinkIndex {
            target_path: "b.md".to_string(),
            fragment: "".to_string(),
            line: 1,
            column: 1,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/a.md"), file_a);

        // Verify B has A as dependent
        assert_eq!(index.get_dependents(Path::new("docs/b.md")).len(), 1);

        // Clear the index
        index.clear();

        // Both files and reverse deps should be cleared
        assert_eq!(index.file_count(), 0);
        assert!(index.get_dependents(Path::new("docs/b.md")).is_empty());
    }

    #[test]
    fn test_is_file_stale() {
        let mut index = WorkspaceIndex::new();

        // Non-existent file is always stale
        assert!(index.is_file_stale(Path::new("nonexistent.md"), "hash123"));

        // Add a file with known hash
        let file_index = FileIndex::with_hash("hash123".to_string());
        index.insert_file(PathBuf::from("docs/test.md"), file_index);

        // Same hash means not stale
        assert!(!index.is_file_stale(Path::new("docs/test.md"), "hash123"));

        // Different hash means stale
        assert!(index.is_file_stale(Path::new("docs/test.md"), "different_hash"));
    }

    #[cfg(feature = "native")]
    #[test]
    fn test_cache_roundtrip() {
        use std::fs;

        // Create a temp directory
        let temp_dir = std::env::temp_dir().join("rumdl_test_cache_roundtrip");
        let _ = fs::remove_dir_all(&temp_dir);
        fs::create_dir_all(&temp_dir).unwrap();

        // Create an index with some data
        let mut index = WorkspaceIndex::new();

        let mut file1 = FileIndex::with_hash("abc123".to_string());
        file1.add_heading(HeadingIndex {
            text: "Test Heading".to_string(),
            auto_anchor: "test-heading".to_string(),
            custom_anchor: Some("test".to_string()),
            line: 1,
            text_lines: 1,
            is_setext: false,
        });
        file1.add_cross_file_link(CrossFileLinkIndex {
            target_path: "./other.md".to_string(),
            fragment: "section".to_string(),
            line: 5,
            column: 3,
            origin: LinkOrigin::Body,
        });
        index.update_file(Path::new("docs/file1.md"), file1);

        let mut file2 = FileIndex::with_hash("def456".to_string());
        file2.add_heading(HeadingIndex {
            text: "Another Heading".to_string(),
            auto_anchor: "another-heading".to_string(),
            custom_anchor: None,
            line: 1,
            text_lines: 1,
            is_setext: false,
        });
        index.update_file(Path::new("docs/other.md"), file2);

        // Save to cache
        index.save_to_cache(&temp_dir).expect("Failed to save cache");

        // Verify cache file exists
        assert!(temp_dir.join("workspace_index.bin").exists());

        // Load from cache
        let loaded = WorkspaceIndex::load_from_cache(&temp_dir).expect("Failed to load cache");

        // Verify data matches
        assert_eq!(loaded.file_count(), 2);
        assert!(loaded.contains_file(Path::new("docs/file1.md")));
        assert!(loaded.contains_file(Path::new("docs/other.md")));

        // Check file1 details
        let file1_loaded = loaded.get_file(Path::new("docs/file1.md")).unwrap();
        assert_eq!(file1_loaded.content_hash, "abc123");
        assert_eq!(file1_loaded.headings.len(), 1);
        assert_eq!(file1_loaded.headings[0].text, "Test Heading");
        assert_eq!(file1_loaded.headings[0].custom_anchor, Some("test".to_string()));
        assert_eq!(file1_loaded.cross_file_links.len(), 1);
        assert_eq!(file1_loaded.cross_file_links[0].target_path, "./other.md");

        // Check reverse deps were serialized correctly
        let dependents = loaded.get_dependents(Path::new("docs/other.md"));
        assert_eq!(dependents.len(), 1);
        assert_eq!(dependents[0], PathBuf::from("docs/file1.md"));

        // Clean up
        let _ = fs::remove_dir_all(&temp_dir);
    }

    #[cfg(feature = "native")]
    #[test]
    fn test_cache_missing_file() {
        let temp_dir = std::env::temp_dir().join("rumdl_test_cache_missing");
        let _ = std::fs::remove_dir_all(&temp_dir);

        // Should return None for non-existent cache
        let result = WorkspaceIndex::load_from_cache(&temp_dir);
        assert!(result.is_none());
    }

    #[cfg(feature = "native")]
    #[test]
    fn test_cache_corrupted_file() {
        use std::fs;

        let temp_dir = std::env::temp_dir().join("rumdl_test_cache_corrupted");
        let _ = fs::remove_dir_all(&temp_dir);
        fs::create_dir_all(&temp_dir).unwrap();

        // Write corrupted data (too small for header)
        fs::write(temp_dir.join("workspace_index.bin"), b"bad").unwrap();

        // Should return None for corrupted cache (and remove the file)
        let result = WorkspaceIndex::load_from_cache(&temp_dir);
        assert!(result.is_none());

        // Corrupted file should be removed
        assert!(!temp_dir.join("workspace_index.bin").exists());

        // Clean up
        let _ = fs::remove_dir_all(&temp_dir);
    }

    #[cfg(feature = "native")]
    #[test]
    fn test_cache_invalid_magic() {
        use std::fs;

        let temp_dir = std::env::temp_dir().join("rumdl_test_cache_invalid_magic");
        let _ = fs::remove_dir_all(&temp_dir);
        fs::create_dir_all(&temp_dir).unwrap();

        // Write data with wrong magic header
        let mut data = Vec::new();
        data.extend_from_slice(b"XXXX"); // Wrong magic
        data.extend_from_slice(&1u32.to_le_bytes()); // Version 1
        data.extend_from_slice(&[0; 100]); // Some garbage data
        fs::write(temp_dir.join("workspace_index.bin"), &data).unwrap();

        // Should return None for invalid magic
        let result = WorkspaceIndex::load_from_cache(&temp_dir);
        assert!(result.is_none());

        // File should be removed
        assert!(!temp_dir.join("workspace_index.bin").exists());

        // Clean up
        let _ = fs::remove_dir_all(&temp_dir);
    }

    #[cfg(feature = "native")]
    #[test]
    fn test_cache_version_mismatch() {
        use std::fs;

        let temp_dir = std::env::temp_dir().join("rumdl_test_cache_version_mismatch");
        let _ = fs::remove_dir_all(&temp_dir);
        fs::create_dir_all(&temp_dir).unwrap();

        // Write data with correct magic but wrong version
        let mut data = Vec::new();
        data.extend_from_slice(b"RWSI"); // Correct magic
        data.extend_from_slice(&999u32.to_le_bytes()); // Future version
        data.extend_from_slice(&[0; 100]); // Some garbage data
        fs::write(temp_dir.join("workspace_index.bin"), &data).unwrap();

        // Should return None for version mismatch
        let result = WorkspaceIndex::load_from_cache(&temp_dir);
        assert!(result.is_none());

        // File should be removed to trigger rebuild
        assert!(!temp_dir.join("workspace_index.bin").exists());

        // Clean up
        let _ = fs::remove_dir_all(&temp_dir);
    }

    #[cfg(feature = "native")]
    #[test]
    fn test_cache_atomic_write() {
        use std::fs;

        // Test that atomic writes work (no temp files left behind)
        let temp_dir = std::env::temp_dir().join("rumdl_test_cache_atomic");
        let _ = fs::remove_dir_all(&temp_dir);
        fs::create_dir_all(&temp_dir).unwrap();

        let index = WorkspaceIndex::new();
        index.save_to_cache(&temp_dir).expect("Failed to save");

        // Only the final cache file should exist, no temp files
        let entries: Vec<_> = fs::read_dir(&temp_dir).unwrap().collect();
        assert_eq!(entries.len(), 1);
        assert!(temp_dir.join("workspace_index.bin").exists());

        // Clean up
        let _ = fs::remove_dir_all(&temp_dir);
    }

    #[test]
    fn test_has_anchor_auto_generated() {
        let mut file_index = FileIndex::new();
        file_index.add_heading(HeadingIndex {
            text: "Installation Guide".to_string(),
            auto_anchor: "installation-guide".to_string(),
            custom_anchor: None,
            line: 1,
            text_lines: 1,
            is_setext: false,
        });

        // Should find by auto-generated anchor
        assert!(file_index.has_anchor("installation-guide"));

        // Case-insensitive matching
        assert!(file_index.has_anchor("Installation-Guide"));
        assert!(file_index.has_anchor("INSTALLATION-GUIDE"));

        // Should not find non-existent anchor
        assert!(!file_index.has_anchor("nonexistent"));
    }

    #[test]
    fn test_has_anchor_custom() {
        let mut file_index = FileIndex::new();
        file_index.add_heading(HeadingIndex {
            text: "Installation Guide".to_string(),
            auto_anchor: "installation-guide".to_string(),
            custom_anchor: Some("install".to_string()),
            line: 1,
            text_lines: 1,
            is_setext: false,
        });

        // Should find by auto-generated anchor
        assert!(file_index.has_anchor("installation-guide"));

        // Should also find by custom anchor
        assert!(file_index.has_anchor("install"));
        assert!(file_index.has_anchor("Install")); // case-insensitive

        // Should not find non-existent anchor
        assert!(!file_index.has_anchor("nonexistent"));
    }

    #[test]
    fn test_get_heading_by_anchor() {
        let mut file_index = FileIndex::new();
        file_index.add_heading(HeadingIndex {
            text: "Installation Guide".to_string(),
            auto_anchor: "installation-guide".to_string(),
            custom_anchor: Some("install".to_string()),
            line: 10,
            text_lines: 1,
            is_setext: false,
        });
        file_index.add_heading(HeadingIndex {
            text: "Configuration".to_string(),
            auto_anchor: "configuration".to_string(),
            custom_anchor: None,
            line: 20,
            text_lines: 1,
            is_setext: false,
        });

        // Get by auto anchor
        let heading = file_index.get_heading_by_anchor("installation-guide");
        assert!(heading.is_some());
        assert_eq!(heading.unwrap().text, "Installation Guide");
        assert_eq!(heading.unwrap().line, 10);

        // Get by custom anchor
        let heading = file_index.get_heading_by_anchor("install");
        assert!(heading.is_some());
        assert_eq!(heading.unwrap().text, "Installation Guide");

        // Get second heading
        let heading = file_index.get_heading_by_anchor("configuration");
        assert!(heading.is_some());
        assert_eq!(heading.unwrap().text, "Configuration");
        assert_eq!(heading.unwrap().line, 20);

        // Non-existent
        assert!(file_index.get_heading_by_anchor("nonexistent").is_none());
    }

    #[test]
    fn test_anchor_lookup_many_headings() {
        // Test that O(1) lookup works with many headings
        let mut file_index = FileIndex::new();

        // Add 100 headings
        for i in 0..100 {
            file_index.add_heading(HeadingIndex {
                text: format!("Heading {i}"),
                auto_anchor: format!("heading-{i}"),
                custom_anchor: Some(format!("h{i}")),
                line: i + 1,
                text_lines: 1,
                is_setext: false,
            });
        }

        // Verify all can be found
        for i in 0..100 {
            assert!(file_index.has_anchor(&format!("heading-{i}")));
            assert!(file_index.has_anchor(&format!("h{i}")));

            let heading = file_index.get_heading_by_anchor(&format!("heading-{i}"));
            assert!(heading.is_some());
            assert_eq!(heading.unwrap().line, i + 1);
        }
    }

    // =============================================================================
    // Tests for extract_cross_file_links utility
    // =============================================================================

    #[test]
    fn test_extract_cross_file_links_basic() {
        use crate::config::MarkdownFlavor;

        let content = "# Test\n\nSee [link](./other.md) for info.\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        assert_eq!(links.len(), 1);
        assert_eq!(links[0].target_path, "./other.md");
        assert_eq!(links[0].fragment, "");
        assert_eq!(links[0].line, 3);
        // "See [link](" = 11 chars, so column 12 is where "./other.md" starts
        assert_eq!(links[0].column, 12);
    }

    #[test]
    fn test_extract_cross_file_links_with_fragment() {
        use crate::config::MarkdownFlavor;

        let content = "Check [guide](./guide.md#install) here.\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        assert_eq!(links.len(), 1);
        assert_eq!(links[0].target_path, "./guide.md");
        assert_eq!(links[0].fragment, "install");
        assert_eq!(links[0].line, 1);
        // "Check [guide](" = 14 chars, so column 15 is where "./guide.md" starts
        assert_eq!(links[0].column, 15);
    }

    #[test]
    fn indexed_columns_preserve_unicode_and_line_endings() {
        for newline in ["\n", "\r\n"] {
            for target in ["目标/é.md", "/目标/é.md"] {
                let unit = format!("é日本🙂 [label]({target}#part) ");
                let content = format!("{}{newline}{}", unit.repeat(80), unit.repeat(80));
                let ctx = LintContext::new(&content, crate::config::MarkdownFlavor::Standard, None);
                let extracted = extract_cross_file_links(&ctx);
                let links = if target.starts_with('/') {
                    extracted.root_relative
                } else {
                    extracted.relative
                };
                assert_eq!(links.len(), 160);
                for (link, (offset, _)) in links.iter().zip(content.match_indices(target)) {
                    assert_eq!((link.line, link.column), ctx.offset_to_line_col(offset));
                    assert_eq!(link.target_path, "目标/é.md");
                    assert_eq!(link.fragment, "part");
                }
            }
        }
        // The legacy angle-first search can report the same later destination
        // for several earlier labels. Its columns must remain unchanged too.
        let content = format!("{}[last](<目标/é.md>)", "é日本🙂 [label](one.md) ".repeat(160));
        let ctx = LintContext::new(&content, crate::config::MarkdownFlavor::Standard, None);
        let links = extract_cross_file_links(&ctx).relative;
        assert_eq!(links.len(), 161);
        let expected = ctx.offset_to_line_col(content.find("目标/é.md").unwrap());
        assert!(
            links
                .iter()
                .all(|link| (link.line, link.column) == expected && link.target_path == "目标/é.md")
        );
    }

    #[test]
    fn test_extract_cross_file_links_multiple_on_same_line() {
        use crate::config::MarkdownFlavor;

        let content = "See [a](a.md) and [b](b.md) here.\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        assert_eq!(links.len(), 2);

        assert_eq!(links[0].target_path, "a.md");
        assert_eq!(links[0].line, 1);
        // "See [a](" = 8 chars, so column 9
        assert_eq!(links[0].column, 9);

        assert_eq!(links[1].target_path, "b.md");
        assert_eq!(links[1].line, 1);
        // "See [a](a.md) and [b](" = 22 chars, so column 23
        assert_eq!(links[1].column, 23);
    }

    #[test]
    fn test_extract_cross_file_links_angle_brackets() {
        use crate::config::MarkdownFlavor;

        let content = "See [link](<path/with (parens).md>) here.\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        assert_eq!(links.len(), 1);
        assert_eq!(links[0].target_path, "path/with (parens).md");
        assert_eq!(links[0].line, 1);
        // "See [link](<" = 12 chars, so column 13
        assert_eq!(links[0].column, 13);
    }

    #[test]
    fn test_extract_cross_file_links_bare_parens_in_destination() {
        use crate::config::MarkdownFlavor;

        // Without angle brackets the destination still carries its parentheses.
        // Truncating at the first `)` yields `file(inner`, which has no markdown
        // extension and is dropped from the index instead of recorded.
        let content = "See [link](docs/file(inner).md) and [plain](docs/other.md).\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        let targets: Vec<&str> = links.iter().map(|l| l.target_path.as_str()).collect();
        assert_eq!(targets, vec!["docs/file(inner).md", "docs/other.md"]);
        // "See [link](" = 11 chars, so column 12
        assert_eq!(links[0].column, 12);
    }

    #[test]
    fn test_extract_cross_file_links_skips_external() {
        use crate::config::MarkdownFlavor;

        let content = r#"
[external](https://example.com)
[mailto](mailto:test@example.com)
[local](./local.md)
[fragment](#section)
[absolute](/docs/page.md)
"#;
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let extracted = extract_cross_file_links(&ctx);

        // Only the local markdown link is a directory-relative link.
        assert_eq!(extracted.relative.len(), 1);
        assert_eq!(extracted.relative[0].target_path, "./local.md");
        // The root-relative link is captured separately, leading `/` stripped.
        assert_eq!(extracted.root_relative.len(), 1);
        assert_eq!(extracted.root_relative[0].target_path, "docs/page.md");
    }

    #[test]
    fn test_extract_cross_file_links_root_relative() {
        use crate::config::MarkdownFlavor;

        // Root-relative markdown links land in the root_relative bucket with the
        // leading `/` stripped; parent traversal and protocol-relative links are
        // excluded so they cannot escape a content root.
        let content = "[a](/guide.md#install)\n[b](/../escape.md)\n[c](//host/x.md)\n[d](/img/pic.png)\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let extracted = extract_cross_file_links(&ctx);

        assert!(extracted.relative.is_empty(), "no directory-relative links here");
        assert_eq!(
            extracted
                .root_relative
                .iter()
                .map(|l| (l.target_path.as_str(), l.fragment.as_str()))
                .collect::<Vec<_>>(),
            vec![("guide.md", "install")],
            "only the safe root-relative markdown link is captured"
        );
    }

    #[test]
    fn test_extract_cross_file_links_skips_non_markdown() {
        use crate::config::MarkdownFlavor;

        let content = r#"
[image](./photo.png)
[doc](./readme.md)
[pdf](./document.pdf)
"#;
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        // Only markdown files are indexed for cross-file validation
        assert_eq!(links.len(), 1);
        assert_eq!(links[0].target_path, "./readme.md");
    }

    #[test]
    fn test_extract_cross_file_links_skips_code_spans() {
        use crate::config::MarkdownFlavor;

        let content = "Normal [link](./file.md) and `[code](./ignored.md)` here.\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        // Only the link outside code span should be extracted
        assert_eq!(links.len(), 1);
        assert_eq!(links[0].target_path, "./file.md");
    }

    #[test]
    fn test_extract_cross_file_links_with_query_params() {
        use crate::config::MarkdownFlavor;

        let content = "See [doc](./file.md?raw=true) here.\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        assert_eq!(links.len(), 1);
        // Query params should be stripped
        assert_eq!(links[0].target_path, "./file.md");
    }

    #[test]
    fn test_extract_cross_file_links_empty_content() {
        use crate::config::MarkdownFlavor;

        let content = "";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        assert!(links.is_empty());
    }

    #[test]
    fn test_extract_cross_file_links_no_links() {
        use crate::config::MarkdownFlavor;

        let content = "# Just a heading\n\nSome text without links.\n";
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        assert!(links.is_empty());
    }

    #[test]
    fn test_extract_cross_file_links_position_accuracy_issue_234() {
        // This test verifies the fix for GitHub issue #234
        // The LSP was reporting incorrect column positions for MD057 diagnostics
        use crate::config::MarkdownFlavor;

        let content = r#"# Test Document

Here is a [broken link](nonexistent-file.md) that should trigger MD057.

And another [link](also-missing.md) on this line.
"#;
        let ctx = LintContext::new(content, MarkdownFlavor::default(), None);
        let links = extract_cross_file_links(&ctx).relative;

        assert_eq!(links.len(), 2);

        // First link: "Here is a [broken link](" = 24 chars, column 25
        assert_eq!(links[0].target_path, "nonexistent-file.md");
        assert_eq!(links[0].line, 3);
        assert_eq!(links[0].column, 25);

        // Second link: "And another [link](" = 19 chars, column 20
        assert_eq!(links[1].target_path, "also-missing.md");
        assert_eq!(links[1].line, 5);
        assert_eq!(links[1].column, 20);
    }

    #[test]
    fn link_path_part_drops_the_query_and_fragment_and_decodes() {
        assert_eq!(link_path_part("guide%20one.md?raw=true#real"), "guide one.md");
        assert_eq!(link_path_part("guide%2Emd#real"), "guide.md");
        assert_eq!(link_path_part("#only-a-fragment"), "");
        assert_eq!(link_path_part("?only=query#x"), "");
    }

    #[cfg(feature = "native")]
    #[test]
    fn url_encode_path_is_undone_by_link_path_part() {
        for path in [
            "plain/guide.md",
            "my notes.md",
            "50%.md",
            "a(b)<c>.md",
            "what?.md",
            "c#.md",
            "back\\slash.md",
            "tab\there.md",
            "日本 語/é.md",
        ] {
            let encoded = url_encode_path(path);
            assert!(
                !encoded.contains([' ', '(', ')', '<', '>', '?', '#', '\\', '\t']),
                "{encoded}"
            );
            assert_eq!(link_path_part(&encoded), path, "{encoded}");
        }
        assert_eq!(url_encode_path("日本/guide.md"), "日本/guide.md");
        assert_eq!(url_encode_path("my notes.md"), "my%20notes.md");
    }

    #[test]
    fn workspace_key_spells_every_path_inside_the_working_directory_relatively() {
        let cwd = std::env::current_dir().unwrap();
        assert_eq!(workspace_key(Path::new("./docs/a.md")), PathBuf::from("docs/a.md"));
        assert_eq!(
            workspace_key(&cwd.join("docs/../docs/a.md")),
            PathBuf::from("docs/a.md")
        );
        assert_eq!(
            workspace_key(&cwd.canonicalize().unwrap().join("docs/a.md")),
            PathBuf::from("docs/a.md")
        );
        // A path that climbs out of the working directory, however it is
        // spelled, lands on the key its absolute form has.
        let outside = cwd.parent().unwrap().join("sibling.md");
        assert_eq!(workspace_key(Path::new("../sibling.md")), workspace_key(&outside));
        assert!(workspace_key(&outside).is_absolute());
    }

    #[cfg(unix)]
    #[test]
    fn get_resolved_file_finds_a_canonical_key_through_a_symlinked_spelling() {
        let dir = tempfile::tempdir().unwrap();
        let real = dir.path().canonicalize().unwrap().join("real");
        std::fs::create_dir(&real).unwrap();
        std::fs::write(real.join("a.md"), "# A\n").unwrap();
        let alias = dir.path().canonicalize().unwrap().join("alias");
        std::os::unix::fs::symlink(&real, &alias).unwrap();

        let mut index = WorkspaceIndex::new();
        let mut file_index = FileIndex::new();
        file_index.add_heading(HeadingIndex {
            text: "A".to_string(),
            auto_anchor: "a".to_string(),
            custom_anchor: None,
            line: 1,
            text_lines: 1,
            is_setext: false,
        });
        index.insert_file(real.join("a.md"), file_index);

        assert!(index.get_resolved_file(&alias.join("a.md")).is_some());
        assert!(index.get_resolved_file(&alias.join("./sub/../a.md")).is_some());
        assert!(index.get_resolved_file(&alias.join("b.md")).is_none());
    }
}