xgraph 3.0.0

//! Checks the crate's layering rule, mechanically.
//!
//! The rule is one sentence: **`core` knows nothing about the concrete graph types.**
//! Everything in `core` is written against the `GraphView` abstraction, which is what lets
//! one implementation of an algorithm serve both graphs — before this refactor each
//! algorithm existed twice, and the two copies had drifted apart.
//!
//! A rule that is only written down erodes. This test reads the source and fails if it is
//! broken, so a violation is caught when it is introduced rather than noticed a year later.
//!
//! Test code is exempt: the tests inside `core` build a concrete `Graph` to exercise the
//! abstraction, which is the natural way to test it and creates no dependency in the
//! shipped library.

use std::fs;
use std::path::{Path, PathBuf};

/// Every `.rs` file under a directory.
fn sources(root: &Path) -> Vec<PathBuf> {
    let mut found = Vec::new();
    let Ok(entries) = fs::read_dir(root) else {
        return found;
    };
    for entry in entries.flatten() {
        let path = entry.path();
        if path.is_dir() {
            found.extend(sources(&path));
        } else if path.extension().is_some_and(|extension| extension == "rs") {
            found.push(path);
        }
    }
    found.sort();
    found
}

/// Removes `#[cfg(test)]` modules, so only shipped code is examined.
///
/// Braces are matched rather than searched for, since a test module contains plenty of its
/// own — and braces inside string and character literals are skipped, since those are text.
/// A lone apostrophe is a lifetime, not a literal, which is the distinction that makes this
/// worth writing out rather than counting characters.
fn without_test_modules(source: &str) -> String {
    let mut out = String::with_capacity(source.len());
    let mut rest = source;

    while let Some(marker) = rest.find("#[cfg(test)]") {
        out.push_str(&rest[..marker]);
        let after = &rest[marker..];

        let Some(open) = after.find('{') else {
            break;
        };
        match module_end(&after[open..]) {
            Some(offset) => rest = &after[open + offset..],
            None => break,
        }
    }
    out.push_str(rest);
    out
}

/// The offset just past the brace that closes the one `source` starts with.
fn module_end(source: &str) -> Option<usize> {
    let characters: Vec<char> = source.chars().collect();
    let mut widths: Vec<usize> = characters.iter().map(|c| c.len_utf8()).collect();
    widths.insert(0, 0);
    // Running byte offset of each character, so the answer can index the original string.
    for index in 1..widths.len() {
        widths[index] += widths[index - 1];
    }

    let mut depth = 0usize;
    let mut index = 0usize;

    while index < characters.len() {
        match characters[index] {
            '"' => {
                index += 1;
                while index < characters.len() {
                    match characters[index] {
                        '\\' => index += 1,
                        '"' => break,
                        _ => {}
                    }
                    index += 1;
                }
            }
            // `'a'` and `'\n'` are literals; `'a` on its own is a lifetime.
            '\'' if is_character_literal(&characters, index) => {
                index += 1;
                while index < characters.len() {
                    match characters[index] {
                        '\\' => index += 1,
                        '\'' => break,
                        _ => {}
                    }
                    index += 1;
                }
            }
            '{' => depth += 1,
            '}' => {
                depth -= 1;
                if depth == 0 {
                    return Some(widths[index + 1]);
                }
            }
            _ => {}
        }
        index += 1;
    }
    None
}

/// Whether the apostrophe at `index` opens a character literal rather than a lifetime.
fn is_character_literal(characters: &[char], index: usize) -> bool {
    match characters.get(index + 1) {
        // An escape is always a literal: there is no such thing as an escaped lifetime.
        Some('\\') => true,
        Some(_) => characters.get(index + 2) == Some(&'\''),
        None => false,
    }
}

/// Strips line comments, so a path mentioned in prose is not mistaken for a reference.
fn without_comments(source: &str) -> String {
    source
        .lines()
        .filter(|line| {
            let trimmed = line.trim_start();
            !trimmed.starts_with("//")
        })
        .collect::<Vec<_>>()
        .join("\n")
}

#[test]
fn core_does_not_depend_on_the_concrete_graph_types() {
    let root = Path::new(env!("CARGO_MANIFEST_DIR")).join("src/core");
    let files = sources(&root);
    assert!(
        !files.is_empty(),
        "found no sources under {}",
        root.display()
    );

    let mut violations = Vec::new();
    for file in files {
        let source = fs::read_to_string(&file).unwrap();
        let shipped = without_comments(&without_test_modules(&source));

        for (number, line) in shipped.lines().enumerate() {
            if line.contains("crate::graph") || line.contains("crate::hgraph") {
                violations.push(format!(
                    "{}:{}: {}",
                    file.display(),
                    number + 1,
                    line.trim()
                ));
            }
        }
    }

    assert!(
        violations.is_empty(),
        "`core` must not reference the concrete graph types outside tests:\n{}",
        violations.join("\n")
    );
}

/// The concrete graphs are the ones that adapt to the abstraction, not the reverse.
#[test]
fn the_concrete_graphs_implement_the_abstraction() {
    let root = Path::new(env!("CARGO_MANIFEST_DIR")).join("src");
    for adapter in ["graph/view.rs", "hgraph/view.rs"] {
        let source = fs::read_to_string(root.join(adapter)).unwrap();
        assert!(
            source.contains("impl") && source.contains("GraphView for"),
            "{} should implement GraphView",
            adapter
        );
    }
}

/// The two graph modules stay independent of each other: neither is built on the other,
/// and a user who enables only one feature must still get a crate that compiles.
#[test]
fn the_two_graph_modules_do_not_depend_on_each_other() {
    let root = Path::new(env!("CARGO_MANIFEST_DIR")).join("src");
    let mut violations = Vec::new();

    for (module, forbidden) in [("graph", "crate::hgraph"), ("hgraph", "crate::graph")] {
        for file in sources(&root.join(module)) {
            let source = fs::read_to_string(&file).unwrap();
            let shipped = without_comments(&without_test_modules(&source));
            for (number, line) in shipped.lines().enumerate() {
                // `crate::graph` is a prefix of `crate::graph_conversion`-style paths only
                // within the same module, so an exact segment match is what matters.
                if line.contains(&format!("{}::", forbidden)) {
                    violations.push(format!(
                        "{}:{}: {}",
                        file.display(),
                        number + 1,
                        line.trim()
                    ));
                }
            }
        }
    }

    assert!(
        violations.is_empty(),
        "the graph modules must not reference each other:\n{}",
        violations.join("\n")
    );
}