use std::{
collections::{BTreeMap, BTreeSet, VecDeque},
path::{Component, Path, PathBuf},
};
use anyhow::{Context, Result, bail};
use rayon::prelude::*;
use sephera_compression::{SupportedLanguage, with_parser};
use sephera_core::plugins::walk_with_declarations;
use sephera_core::progress::{NoProgress, Progress};
use sephera_ignore::IgnoreMatcher;
use sephera_scan::project_files::{ProjectFile, collect_project_files};
use sephera_core::declarations;
use super::{manifests, plugins};
use super::types::{
FileMetric, GraphEdge, GraphMetrics, GraphNode, GraphQuery, GraphReport,
ImportKind, ImportStatement, NodeMap,
};
const MAX_IMPORT_FILE_BYTES: u64 = 512 * 1024;
const MAX_UNRESOLVED_LOCAL_SAMPLES: usize = 20;
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct EdgeFilters {
pub exclude_type_aliases: bool,
}
impl EdgeFilters {
#[must_use]
pub const fn rejects(&self, statement: &ImportStatement) -> bool {
if !self.exclude_type_aliases {
return false;
}
statement.kind.is_renaming()
}
}
pub fn build_graph(
base_path: &Path,
ignore: &IgnoreMatcher,
focus_paths: &[PathBuf],
depth: Option<u32>,
query: Option<GraphQuery>,
) -> Result<GraphReport> {
build_graph_with(
base_path,
ignore,
focus_paths,
depth,
query,
EdgeFilters::default(),
)
}
pub fn build_graph_with(
base_path: &Path,
ignore: &IgnoreMatcher,
focus_paths: &[PathBuf],
depth: Option<u32>,
query: Option<GraphQuery>,
filters: EdgeFilters,
) -> Result<GraphReport> {
build_graph_with_progress(
base_path,
ignore,
focus_paths,
depth,
query,
filters,
&NoProgress,
)
}
pub fn build_graph_with_progress(
base_path: &Path,
ignore: &IgnoreMatcher,
focus_paths: &[PathBuf],
depth: Option<u32>,
query: Option<GraphQuery>,
filters: EdgeFilters,
progress: &dyn Progress,
) -> Result<GraphReport> {
let project_files = collect_project_files(base_path, ignore)?;
let focus_set = build_focus_set(base_path, focus_paths);
let query = query
.map(|query| normalize_graph_query(base_path, query))
.transpose()?;
let (mut all_file_imports, declarations) =
extract_all_imports(&project_files, progress)?;
if filters != EdgeFilters::default() {
for file in &mut all_file_imports {
file.imports.retain(|statement| !filters.rejects(statement));
}
}
let known_files: BTreeSet<String> = project_files
.iter()
.map(|f| f.normalized_relative_path.clone())
.collect();
let manifests = manifests::ManifestIndex::discover(base_path);
let project = ResolutionInputs {
base_path: base_path.to_path_buf(),
known_files,
declarations,
manifests,
};
let (edges, node_map) = build_edges_and_nodes(&all_file_imports, &project);
let selection = select_graph(&node_map, &focus_set, depth, query)?;
let filtered_node_map = filter_node_map(&node_map, &selection.node_paths);
let filtered_edges = filter_edges(&edges, &selection.node_paths);
let metrics = compute_metrics(
&project.manifests,
&filtered_node_map,
&filtered_edges,
);
let nodes = build_node_list(&filtered_node_map);
Ok(GraphReport {
base_path: base_path.to_path_buf(),
focus_paths: focus_paths
.iter()
.map(|p| p.to_string_lossy().to_string())
.collect(),
depth: selection.applied_depth,
query: selection.query,
nodes,
edges: filtered_edges,
metrics,
})
}
struct FileImportData {
file_path: String,
language: Option<&'static str>,
ts_language: SupportedLanguage,
imports: Vec<ImportStatement>,
}
fn extract_all_imports(
project_files: &[ProjectFile],
progress: &dyn Progress,
) -> Result<(Vec<FileImportData>, declarations::DeclarationIndex)> {
progress.set_total(project_files.len() as u64);
let extracted: Vec<ExtractedFile> = project_files
.par_iter()
.map(extract_one_file)
.collect::<Result<Vec<_>>>()?
.into_iter()
.flatten()
.collect();
progress.advance(project_files.len() as u64);
let mut results = Vec::with_capacity(extracted.len());
let mut declarations = declarations::DeclarationIndex::default();
for file in extracted {
if let Some((path, declared)) = file.declared {
declarations.insert(&path, declared);
}
results.push(file.data);
}
Ok((results, declarations))
}
struct ExtractedFile {
data: FileImportData,
declared: Option<(String, declarations::DeclaredNames)>,
}
fn extract_one_file(
project_file: &ProjectFile,
) -> Result<Option<ExtractedFile>> {
if project_file.size_bytes > MAX_IMPORT_FILE_BYTES {
return Ok(None);
}
let Some((_, language)) = project_file.language_match else {
return Ok(None);
};
let Some(ts_language) =
SupportedLanguage::from_language_name(language.name)
else {
return Ok(None);
};
let source =
std::fs::read(&project_file.absolute_path).with_context(|| {
format!(
"failed to read `{}` for import extraction",
project_file.absolute_path.display()
)
})?;
if std::str::from_utf8(&source).is_err() {
return Ok(Some(ExtractedFile {
data: FileImportData {
file_path: project_file.normalized_relative_path.clone(),
language: Some(language.name),
ts_language,
imports: Vec::new(),
},
declared: None,
}));
}
let Some(plugin) = plugins::builtin_import_plugin(ts_language) else {
return Ok(None);
};
let mut extracted = with_parser(ts_language, source.len(), |parser| {
walk_with_declarations(&source, parser, plugin)
})
.unwrap_or_default();
let declared = extracted
.declared
.take()
.map(|names| (project_file.normalized_relative_path.clone(), names));
Ok(Some(ExtractedFile {
data: FileImportData {
file_path: project_file.normalized_relative_path.clone(),
language: Some(language.name),
ts_language,
imports: extracted.imports,
},
declared,
}))
}
#[must_use]
pub fn build_focus_set(
base_path: &Path,
focus_paths: &[PathBuf],
) -> BTreeSet<String> {
let base = std::path::absolute(base_path)
.unwrap_or_else(|_| base_path.to_path_buf());
let mut scopes = BTreeSet::new();
for focus in focus_paths {
let resolved = if focus.is_absolute() {
focus
.strip_prefix(&base)
.unwrap_or(focus.as_path())
.to_path_buf()
} else {
strip_relative_noise(focus).unwrap_or_else(|| focus.clone())
};
let spelled = sephera_core::path_utils::forward_slashes(
&resolved.to_string_lossy(),
);
if spelled.is_empty() {
return BTreeSet::new();
}
scopes.insert(spelled);
}
scopes
}
fn strip_relative_noise(path: &Path) -> Option<PathBuf> {
let mut cleaned = PathBuf::new();
for component in path.components() {
match component {
Component::CurDir => {}
Component::Normal(part) => cleaned.push(part),
Component::ParentDir if cleaned.pop() => {}
_ => return None,
}
}
Some(cleaned)
}
#[derive(Debug)]
struct GraphSelection {
node_paths: BTreeSet<String>,
applied_depth: Option<u32>,
query: Option<GraphQuery>,
}
#[derive(Debug, Clone, Copy)]
enum TraversalDirection {
Imports,
ImportedBy,
}
fn normalize_graph_query(
base_path: &Path,
query: GraphQuery,
) -> Result<GraphQuery> {
match query {
GraphQuery::DependsOn(path) => Ok(GraphQuery::DependsOn(
normalize_query_target(base_path, &path)?,
)),
}
}
fn normalize_query_target(base_path: &Path, raw_path: &str) -> Result<String> {
let raw_path = Path::new(raw_path);
let relative_path = if raw_path.is_absolute() {
let canonical_base = base_path.canonicalize().with_context(|| {
format!("failed to resolve base path `{}`", base_path.display())
})?;
let absolute_target = raw_path
.canonicalize()
.unwrap_or_else(|_| raw_path.to_path_buf());
absolute_target
.strip_prefix(&canonical_base)
.with_context(|| {
format!(
"path `{}` must resolve inside `{}`",
raw_path.display(),
base_path.display()
)
})?
.to_path_buf()
} else {
raw_path.to_path_buf()
};
normalize_user_relative_path(&relative_path)
}
fn normalize_user_relative_path(path: &Path) -> Result<String> {
let mut parts = Vec::new();
for component in path.components() {
match component {
Component::Normal(part) => {
parts.push(part.to_string_lossy().into_owned());
}
Component::ParentDir => {
if parts.pop().is_none() {
bail!(
"path `{}` must resolve inside the base path",
path.display()
);
}
}
Component::CurDir | Component::RootDir | Component::Prefix(_) => {}
}
}
Ok(if parts.is_empty() {
".".to_owned()
} else {
parts.join("/")
})
}
fn resolve_import_with(
import_path: &str,
source_file: &str,
module_depth: u8,
kind: ImportKind,
language: SupportedLanguage,
project: &ResolutionInputs,
) -> Resolution {
let Some(plugin) = plugins::builtin_resolver_plugin(language) else {
return Resolution::External;
};
let context = plugins::ResolveContext {
source_file,
known_files: &project.known_files,
module_depth,
kind,
declarations: Some(&project.declarations),
manifests: Some(&project.manifests),
base_path: &project.base_path,
};
match plugin.resolve(import_path, context) {
Some(file) => Resolution::File(file),
None if leaves_project(plugin, import_path, context) => {
Resolution::External
}
None => Resolution::Unresolved,
}
}
fn leaves_project(
plugin: &dyn plugins::ResolverPlugin,
import_path: &str,
context: plugins::ResolveContext<'_>,
) -> bool {
const QUALIFIERS: [&str; 3] = ["crate::", "self::", "super::"];
let Some(rest) = QUALIFIERS
.iter()
.find_map(|prefix| import_path.strip_prefix(prefix))
else {
return false;
};
let name = rest.split("::").next().unwrap_or(rest);
!name.is_empty() && plugin.leaves_project(name, context)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Resolution {
File(String),
Unresolved,
External,
}
impl Resolution {
#[must_use]
pub fn file(&self) -> Option<&str> {
match self {
Self::File(file) => Some(file),
Self::Unresolved | Self::External => None,
}
}
#[must_use]
pub const fn is_resolved(&self) -> bool {
matches!(self, Self::File(_))
}
}
#[cfg(test)]
fn resolve_import_lang(
language: SupportedLanguage,
import_path: &str,
source_file: &str,
known_files: &plugins::KnownFiles,
) -> Option<String> {
resolve_plain(language, import_path, source_file, known_files)
.file()
.map(ToOwned::to_owned)
}
#[cfg(test)]
fn resolve_plain(
language: SupportedLanguage,
import_path: &str,
source_file: &str,
known_files: &plugins::KnownFiles,
) -> Resolution {
resolve_import_with(
import_path,
source_file,
0,
ImportKind::Dependency,
language,
&ResolutionInputs {
base_path: std::path::PathBuf::new(),
known_files: known_files.clone(),
declarations: declarations::DeclarationIndex::default(),
manifests: manifests::ManifestIndex::default(),
},
)
}
struct ResolutionInputs {
base_path: PathBuf,
known_files: plugins::KnownFiles,
declarations: declarations::DeclarationIndex,
manifests: manifests::ManifestIndex,
}
fn build_edges_and_nodes(
all_imports: &[FileImportData],
project: &ResolutionInputs,
) -> (Vec<GraphEdge>, NodeMap) {
let mut edges = Vec::new();
let mut node_map: NodeMap = BTreeMap::new();
for file_data in all_imports {
node_map
.entry(file_data.file_path.clone())
.or_default()
.language = file_data.language;
}
for file_data in all_imports {
for statement in &file_data.imports {
let resolved = resolve_import_with(
&statement.raw_path,
&file_data.file_path,
statement.module_depth,
statement.kind,
file_data.ts_language,
project,
);
let is_resolved = resolved.is_resolved();
let target = resolved.file().map(ToOwned::to_owned);
let local_gap = matches!(resolved, Resolution::Unresolved)
&& (looks_local(&statement.raw_path, file_data.ts_language)
|| names_a_known_module(
file_data.ts_language,
&statement.raw_path,
&file_data.file_path,
project,
))
&& (statement.kind.is_namespace()
== statement.raw_path.ends_with('*'))
&& !names_a_declared_symbol(statement, file_data, project);
if let Some(ref target) = target
&& *target != file_data.file_path
{
node_map
.entry(target.clone())
.or_default()
.imported_by
.push(file_data.file_path.clone());
let source_entry =
node_map.entry(file_data.file_path.clone()).or_default();
source_entry.imports.push(target.clone());
if statement.kind == ImportKind::ModuleDeclaration {
source_entry.declarations.insert(target.clone());
}
}
edges.push(GraphEdge {
from: file_data.file_path.clone(),
to: target,
import_path: statement.raw_path.clone(),
resolved: is_resolved,
kind: statement.kind,
cfg_gated: statement.cfg_gated,
local_gap,
});
}
}
(edges, node_map)
}
fn select_graph(
node_map: &NodeMap,
focus_set: &BTreeSet<String>,
depth: Option<u32>,
query: Option<GraphQuery>,
) -> Result<GraphSelection> {
if focus_set.is_empty() && query.is_none() {
return Ok(GraphSelection {
node_paths: node_map.keys().cloned().collect(),
applied_depth: None,
query: None,
});
}
let mut selected = BTreeSet::new();
if let Some(ref query_mode) = query {
let query_roots = roots_for_query(node_map, query_mode)?;
let mut reachable = traverse_graph(
node_map,
&query_roots,
depth,
TraversalDirection::ImportedBy,
);
if !focus_set.is_empty() {
let focus_roots = collect_focus_roots(node_map, focus_set);
reachable.retain(|path| focus_roots.contains(path));
for root in &query_roots {
reachable.insert(root.clone());
}
}
selected.extend(reachable);
} else if !focus_set.is_empty() {
let focus_roots = collect_focus_roots(node_map, focus_set);
selected.extend(traverse_graph(
node_map,
&focus_roots,
depth,
TraversalDirection::Imports,
));
}
Ok(GraphSelection {
node_paths: selected,
applied_depth: depth,
query,
})
}
fn collect_focus_roots(
node_map: &NodeMap,
focus_set: &BTreeSet<String>,
) -> BTreeSet<String> {
node_map
.keys()
.filter(|path| {
focus_set
.iter()
.any(|focus| path_matches_focus(path, focus))
})
.cloned()
.collect()
}
#[must_use]
pub fn path_matches_focus(path: &str, focus: &str) -> bool {
path == focus
|| path
.strip_prefix(focus)
.is_some_and(|rest| rest.starts_with('/'))
}
fn roots_for_query(
node_map: &NodeMap,
query: &GraphQuery,
) -> Result<BTreeSet<String>> {
match query {
GraphQuery::DependsOn(path) => {
if node_map.contains_key(path) {
Ok(BTreeSet::from([path.clone()]))
} else {
bail!(
"path `{path}` did not resolve to an analyzed graph node"
);
}
}
}
}
fn traverse_graph(
node_map: &NodeMap,
roots: &BTreeSet<String>,
depth: Option<u32>,
direction: TraversalDirection,
) -> BTreeSet<String> {
let max_distance = depth;
let mut visited = BTreeSet::new();
let mut queue: VecDeque<(String, u32)> =
roots.iter().cloned().map(|path| (path, 0)).collect();
while let Some((path, distance)) = queue.pop_front() {
if !visited.insert(path.clone()) {
continue;
}
if max_distance.is_some_and(|limit| distance >= limit) {
continue;
}
let neighbors =
node_map.get(path.as_str()).map_or(
&[][..],
|entry| match direction {
TraversalDirection::Imports => entry.imports.as_slice(),
TraversalDirection::ImportedBy => {
entry.imported_by.as_slice()
}
},
);
for neighbor in neighbors {
if !visited.contains(neighbor) {
queue.push_back((neighbor.clone(), distance + 1));
}
}
}
visited
}
fn filter_node_map(
node_map: &NodeMap,
selected_paths: &BTreeSet<String>,
) -> NodeMap {
selected_paths
.iter()
.filter_map(|path| {
node_map.get(path).map(|entry| {
(
path.clone(),
super::types::NodeEntry {
language: entry.language,
imports: entry
.imports
.iter()
.filter(|neighbor| {
selected_paths.contains(*neighbor)
})
.cloned()
.collect(),
imported_by: entry
.imported_by
.iter()
.filter(|neighbor| {
selected_paths.contains(*neighbor)
})
.cloned()
.collect(),
declarations: entry
.declarations
.iter()
.filter(|neighbor| {
selected_paths.contains(*neighbor)
})
.cloned()
.collect(),
},
)
})
})
.collect()
}
fn filter_edges(
edges: &[GraphEdge],
selected_paths: &BTreeSet<String>,
) -> Vec<GraphEdge> {
edges
.iter()
.filter(|edge| {
selected_paths.contains(&edge.from)
&& (if edge.resolved {
edge.to
.as_ref()
.is_some_and(|target| selected_paths.contains(target))
} else {
true
})
})
.cloned()
.collect()
}
fn build_node_list(node_map: &NodeMap) -> Vec<GraphNode> {
node_map
.iter()
.map(|(file_path, entry)| GraphNode {
file_path: file_path.clone(),
language: entry.language,
imports_count: u64::try_from(entry.imports.len())
.unwrap_or(u64::MAX),
imported_by_count: u64::try_from(entry.imported_by.len())
.unwrap_or(u64::MAX),
})
.collect()
}
fn compute_metrics(
index: &manifests::ManifestIndex,
node_map: &NodeMap,
edges: &[GraphEdge],
) -> GraphMetrics {
let total_files = u64::try_from(node_map.len()).unwrap_or(u64::MAX);
let self_references = u64::try_from(
edges
.iter()
.filter(|edge| edge.resolved && is_self_edge(edge))
.count(),
)
.unwrap_or(u64::MAX);
let total_internal_edges = u64::try_from(
edges
.iter()
.filter(|edge| edge.resolved && !is_self_edge(edge))
.count(),
)
.unwrap_or(u64::MAX);
let cfg_gated_edges =
u64::try_from(edges.iter().filter(|edge| edge.cfg_gated).count())
.unwrap_or(u64::MAX);
let unresolved_local: Vec<&GraphEdge> =
edges.iter().filter(|edge| edge.local_gap).collect();
let external_count = edges.iter().filter(|e| !e.resolved).count();
let total_external_edges =
u64::try_from(external_count - unresolved_local.len())
.unwrap_or(u64::MAX);
let unresolved_local_edges =
u64::try_from(unresolved_local.len()).unwrap_or(u64::MAX);
let unresolved_local_samples = unresolved_local
.iter()
.take(MAX_UNRESOLVED_LOCAL_SAMPLES)
.map(|edge| format!("{}: {}", edge.from, edge.import_path))
.collect();
let dependencies = index.summarise(edges.iter().filter_map(|edge| {
let extension = std::path::Path::new(&edge.from)
.extension()
.and_then(std::ffi::OsStr::to_str)?;
let language = SupportedLanguage::from_extension(extension)?;
(!edge.resolved).then_some((
edge.import_path.as_str(),
manifests::Ecosystem::of(language),
))
}));
let edges_of_kind = |kind: manifests::DependencyKind| {
dependencies
.iter()
.filter(|dependency| dependency.kind == kind)
.map(|dependency| dependency.edge_count)
.sum::<u64>()
};
let declared_dependency_edges =
edges_of_kind(manifests::DependencyKind::Declared);
let local_crate_edges = edges_of_kind(manifests::DependencyKind::Local);
let builtin_edges = edges_of_kind(manifests::DependencyKind::Builtin);
let mut most_importing: Vec<FileMetric> = node_map
.iter()
.map(|(path, entry)| FileMetric {
file_path: path.clone(),
count: u64::try_from(entry.imports.len()).unwrap_or(u64::MAX),
})
.filter(|m| m.count > 0)
.collect();
most_importing.sort_by_key(|m| std::cmp::Reverse(m.count));
most_importing.truncate(10);
let mut most_imported: Vec<FileMetric> = node_map
.iter()
.map(|(path, entry)| FileMetric {
file_path: path.clone(),
count: u64::try_from(entry.imported_by.len()).unwrap_or(u64::MAX),
})
.filter(|m| m.count > 0)
.collect();
most_imported.sort_by_key(|m| std::cmp::Reverse(m.count));
most_imported.truncate(10);
let cycles = detect_cycles(node_map);
let circular_dependencies = u64::try_from(cycles.len()).unwrap_or(u64::MAX);
GraphMetrics {
total_files,
total_internal_edges,
self_references,
total_external_edges,
unresolved_local_edges,
unresolved_local_samples,
cfg_gated_edges,
dependencies,
declared_dependency_edges,
local_crate_edges,
builtin_edges,
circular_dependencies,
most_importing,
most_imported,
cycles,
}
}
fn is_structural_module_edge(source: &str, target: &str) -> bool {
is_own_child_module(source, target)
|| is_own_child_module(target, source)
|| is_ancestor_module(target, source)
}
fn is_own_child_module(source: &str, target: &str) -> bool {
let children = sephera_graph_rust::module_children_dir(source);
match target.rsplit_once('/') {
Some((directory, _)) => directory == children,
None => false,
}
}
fn is_ancestor_module(ancestor: &str, descendant: &str) -> bool {
let enclosing = sephera_graph_rust::module_children_dir(ancestor);
let inner = sephera_graph_rust::module_children_dir(descendant);
inner.starts_with(&enclosing)
&& inner.len() > enclosing.len()
&& inner.as_bytes().get(enclosing.len()) == Some(&b'/')
}
fn is_self_edge(edge: &GraphEdge) -> bool {
edge.to.as_deref() == Some(edge.from.as_str())
}
fn names_a_declared_symbol(
statement: &ImportStatement,
file_data: &FileImportData,
project: &ResolutionInputs,
) -> bool {
let Some((parent, name)) = split_trailing_name(&statement.raw_path) else {
return false;
};
let Resolution::File(parent_file) = resolve_import_with(
&parent,
&file_data.file_path,
statement.module_depth,
statement.kind,
file_data.ts_language,
project,
) else {
return false;
};
project.declarations.file_reaches(&parent_file, &name)
}
fn split_trailing_name(import_path: &str) -> Option<(String, String)> {
let separator = import_path.rfind(['.', '/', ':'])?;
let name = &import_path[separator + 1..];
let parent = &import_path[..separator];
if name.is_empty() || parent.is_empty() || parent.ends_with(['.', '/', ':'])
{
return None;
}
Some((parent.to_owned(), name.to_owned()))
}
fn names_a_known_module(
language: SupportedLanguage,
import_path: &str,
source_file: &str,
project: &ResolutionInputs,
) -> bool {
let Some(plugin) = plugins::builtin_resolver_plugin(language) else {
return false;
};
let name = import_path
.split(['.', '/', ':'])
.next()
.unwrap_or_default();
plugin.names_a_known_module(
name,
plugins::ResolveContext {
source_file,
known_files: &project.known_files,
module_depth: 0,
kind: ImportKind::Dependency,
declarations: Some(&project.declarations),
manifests: Some(&project.manifests),
base_path: &project.base_path,
},
)
}
fn looks_local(import_path: &str, language: SupportedLanguage) -> bool {
if import_path.ends_with('*') {
return true;
}
match language {
SupportedLanguage::Rust => {
const QUALIFIERS: [&str; 4] = ["crate::", "self::", "super::", "."];
QUALIFIERS
.iter()
.any(|qualifier| import_path.starts_with(qualifier))
}
SupportedLanguage::Python => import_path.starts_with('.'),
SupportedLanguage::C | SupportedLanguage::Cpp => {
!import_path.starts_with('<')
}
SupportedLanguage::JavaScript | SupportedLanguage::TypeScript => {
import_path.starts_with("./") || import_path.starts_with("../")
}
SupportedLanguage::Go | SupportedLanguage::Java => false,
}
}
fn cycle_key(cycle: &[String]) -> String {
let mut ring: Vec<String> = cycle
.iter()
.take(cycle.len().saturating_sub(1))
.cloned()
.collect();
ring.sort();
ring.join("|")
}
fn structural_adjacency(node_map: &NodeMap) -> NodeMap {
let mut filtered: NodeMap = node_map.to_owned();
for (file, entry) in &mut filtered {
entry
.imports
.retain(|target| !is_structural_module_edge(file, target));
}
filtered
}
fn without_declaration_edges(node_map: &NodeMap) -> NodeMap {
let mut filtered: NodeMap = node_map.to_owned();
for entry in filtered.values_mut() {
entry
.imports
.retain(|target| !entry.declarations.contains(target));
}
filtered
}
fn detect_cycles(node_map: &NodeMap) -> Vec<Vec<String>> {
let adjacency = without_declaration_edges(&structural_adjacency(node_map));
let node_map = &adjacency;
let mut cycles: Vec<Vec<String>> = Vec::new();
let mut visited: BTreeSet<String> = BTreeSet::new();
let mut in_stack: BTreeSet<String> = BTreeSet::new();
let mut seen_cycle_keys: BTreeSet<String> = BTreeSet::new();
for start_node in node_map.keys() {
if visited.contains(start_node) {
continue;
}
let mut stack: Vec<(String, usize)> = vec![(start_node.clone(), 0)];
in_stack.insert(start_node.clone());
while let Some((node, child_idx)) = stack.last_mut() {
let children = node_map
.get(node.as_str())
.map_or(&[][..], |e| e.imports.as_slice());
if *child_idx >= children.len() {
let node = stack.pop().unwrap().0;
in_stack.remove(&node);
visited.insert(node);
continue;
}
let child = children[*child_idx].clone();
*child_idx += 1;
if in_stack.contains(&child) {
let cycle_start_idx =
stack.iter().position(|(n, _)| *n == child).unwrap_or(0);
let mut cycle: Vec<String> = stack[cycle_start_idx..]
.iter()
.map(|(n, _)| n.clone())
.collect();
cycle.push(child.clone());
if seen_cycle_keys.insert(cycle_key(&cycle)) {
cycles.push(cycle);
}
} else if !visited.contains(&child) {
in_stack.insert(child.clone());
stack.push((child, 0));
}
}
}
cycles
}
#[cfg(test)]
mod tests {
use super::*;
use crate::types::ImportKind;
use std::fs;
use tempfile::tempdir;
fn known_files(paths: &[&str]) -> BTreeSet<String> {
paths.iter().map(|path| (*path).to_owned()).collect()
}
fn statement(raw_path: &str, kind: ImportKind) -> ImportStatement {
ImportStatement {
raw_path: raw_path.to_owned(),
line: 1,
kind,
module_depth: 0,
cfg_gated: false,
}
}
#[test]
fn a_relative_focus_path_is_left_exactly_as_written() {
let focus = vec![PathBuf::from("src/main.rs")];
assert_eq!(
build_focus_set(Path::new("/anywhere"), &focus),
known_files(&["src/main.rs"])
);
assert_eq!(
build_focus_set(Path::new("."), &focus),
known_files(&["src/main.rs"]),
"a relative base must not change how a relative scope is read"
);
assert_eq!(
build_focus_set(&std::env::temp_dir().join("repo"), &focus),
known_files(&["src/main.rs"]),
"the working directory must not appear in the answer"
);
}
#[test]
fn an_absolute_focus_path_is_made_relative_to_an_absolute_base() {
let base = std::env::temp_dir().join("repo");
let focus = vec![base.join("crates").join("one")];
assert_eq!(
build_focus_set(&base, &focus),
known_files(&["crates/one"]),
"an absolute scope under the base is base-relative in the graph"
);
}
#[test]
fn an_absolute_scope_measures_the_same_from_a_relative_base() {
let base = std::env::current_dir().expect("a working directory");
let focus = vec![base.join("crates").join("one")];
assert_eq!(
build_focus_set(Path::new("."), &focus),
known_files(&["crates/one"]),
"an absolute scope under `.` must resolve as a relative one does"
);
assert_eq!(
build_focus_set(Path::new("."), &focus),
build_focus_set(&base, &focus),
"the base's own relativity must not decide whether a scope matches"
);
}
#[test]
fn an_absolute_scope_outside_the_base_is_left_alone() {
let base = std::env::temp_dir().join("repo");
let elsewhere = std::env::temp_dir().join("elsewhere");
let normalised =
build_focus_set(&base, std::slice::from_ref(&elsewhere));
assert!(
normalised.iter().any(|path| path.contains("elsewhere")),
"expected the outside path to survive, got {normalised:?}"
);
}
#[test]
fn a_scope_that_spells_the_whole_base_becomes_no_scope_at_all() {
let base = std::env::temp_dir().join("repo");
let mut spellings = vec![
PathBuf::from("."),
PathBuf::from("./"),
PathBuf::from("crates/x/../.."),
];
spellings.extend(windows_paths(&[".\\"]));
for spelling in &spellings {
assert_eq!(
build_focus_set(&base, std::slice::from_ref(spelling)),
BTreeSet::new(),
"`{}` names the whole base, so it should not restrict anything",
spelling.display()
);
}
}
#[test]
fn dot_segments_inside_a_scope_are_resolved_away() {
for (spelling, resolves_to) in [
("crates/cli/./src", "crates/cli/src"),
("./crates/cli/src", "crates/cli/src"),
("crates/cli/src/..", "crates/cli"),
("crates/cli/./src/../..", "crates"),
] {
assert_eq!(
build_focus_set(
std::env::temp_dir().join("repo").as_path(),
&[PathBuf::from(spelling)],
),
known_files(&[resolves_to]),
"`{spelling}` should resolve to {resolves_to}"
);
}
for (spelling, resolves_to) in
windows_spellings(&[(".\\crates\\cli\\src", "crates/cli/src")])
{
assert_eq!(
build_focus_set(
std::env::temp_dir().join("repo").as_path(),
&[PathBuf::from(spelling)],
),
known_files(&[resolves_to]),
"`{spelling}` should resolve to {resolves_to}"
);
}
}
fn windows_paths(raw: &[&str]) -> Vec<PathBuf> {
if cfg!(windows) {
raw.iter().map(PathBuf::from).collect()
} else {
Vec::new()
}
}
fn windows_spellings<'a>(
pairs: &[(&'a str, &'a str)],
) -> Vec<(&'a str, &'a str)> {
if cfg!(windows) {
pairs.to_vec()
} else {
Vec::new()
}
}
#[test]
fn a_backslash_is_a_separator_only_where_it_is_one() {
let spelled =
sephera_core::path_utils::forward_slashes("crates/cli\\src");
if cfg!(windows) {
assert_eq!(spelled, "crates/cli/src");
} else {
assert_eq!(
spelled, "crates/cli\\src",
"a backslash in a Unix file name is part of the name"
);
}
}
#[test]
fn one_scope_naming_the_whole_base_overrides_the_others() {
let base = std::env::temp_dir().join("repo");
let scopes = vec![PathBuf::from("."), PathBuf::from("src/core")];
assert_eq!(
build_focus_set(&base, &scopes),
BTreeSet::new(),
"a scope that is the whole base makes the whole union the whole base"
);
let reversed = vec![PathBuf::from("src/core"), PathBuf::from("./")];
assert_eq!(build_focus_set(&base, &reversed), BTreeSet::new());
}
#[test]
fn an_absolute_scope_can_still_produce_a_leading_parent() {
let base = std::env::temp_dir().join("repo");
let escaping = base.join("..").join("outside");
let scope = build_focus_set(&base, &[escaping]);
assert_eq!(
scope,
known_files(&["../outside"]),
"the base is stripped lexically, with no check for `..` in what is left"
);
}
#[test]
fn a_parent_segment_that_escapes_the_front_is_left_alone() {
let scope = build_focus_set(
std::env::temp_dir().join("repo").as_path(),
&[PathBuf::from("../outside")],
);
assert!(
scope.iter().any(|path| path.contains("..")),
"expected the escaping path to survive, got {scope:?}"
);
}
#[test]
fn depth_counts_hops_from_the_traversal_root() {
let reached = |depth: Option<u32>| {
let (node_map, roots) = chain_fixture();
traverse_graph(
&node_map,
&roots,
depth,
TraversalDirection::ImportedBy,
)
.len()
};
assert_eq!(reached(None), 4, "unbounded reaches the whole chain");
assert_eq!(reached(Some(0)), 1, "depth 0 is the root and nothing else");
assert_eq!(reached(Some(1)), 2, "depth 1 is the root plus one hop");
assert_eq!(reached(Some(2)), 3, "depth 2 adds the second hop");
assert_eq!(reached(Some(3)), 4, "depth 3 reaches the end of the chain");
assert_eq!(reached(Some(4)), 4, "already everything; no further hop");
}
fn chain_fixture() -> (NodeMap, BTreeSet<String>) {
let mut node_map: NodeMap = BTreeMap::new();
let link =
|node_map: &mut NodeMap, path: &str, imported_by: &[&str]| {
node_map.insert(
path.to_owned(),
crate::types::NodeEntry {
language: Some("Rust"),
imports: Vec::new(),
imported_by: imported_by
.iter()
.map(|s| (*s).to_owned())
.collect(),
declarations: BTreeSet::new(),
},
);
};
link(&mut node_map, "target", &["a"]);
link(&mut node_map, "a", &["b"]);
link(&mut node_map, "b", &["c"]);
link(&mut node_map, "c", &[]);
(node_map, BTreeSet::from(["target".to_owned()]))
}
#[test]
fn type_alias_imports_are_kept_by_default() {
let filters = EdgeFilters::default();
assert!(
!filters
.rejects(&statement("crate::foo::Bar", ImportKind::TypeAlias))
);
assert!(
!filters.rejects(&statement("crate::foo", ImportKind::Namespace))
);
}
#[test]
fn type_alias_imports_are_dropped_when_enabled() {
let filters = EdgeFilters {
exclude_type_aliases: true,
};
assert!(
filters
.rejects(&statement("crate::foo::Bar", ImportKind::TypeAlias))
);
assert!(
filters.rejects(&statement("crate::foo", ImportKind::Namespace))
);
}
#[test]
fn a_module_declaration_survives_the_filter() {
let filters = EdgeFilters {
exclude_type_aliases: true,
};
assert!(
!filters.rejects(&statement(
"self::types",
ImportKind::ModuleDeclaration
))
);
}
#[test]
fn ordinary_imports_survive_the_filter() {
let filters = EdgeFilters {
exclude_type_aliases: true,
};
for import in [
"crate::core::graph",
"crate::foo::Bar",
"std::collections::HashMap",
"crate::a::b::*inner",
] {
assert!(
!filters.rejects(&statement(import, ImportKind::Dependency)),
"{import} is a real dependency and must be kept"
);
}
}
#[test]
fn excluding_type_aliases_removes_only_that_edge() {
let temp_dir = tempdir().unwrap();
for (relative, contents) in [
(
"src/main.rs",
"mod util;\nuse crate::alias::Thing as Other;\nuse crate::util::u;\n",
),
("src/util.rs", "pub fn u() {}\n"),
("src/alias.rs", "pub struct Thing;\n"),
] {
let absolute = temp_dir.path().join(relative);
fs::create_dir_all(absolute.parent().unwrap()).unwrap();
fs::write(absolute, contents).unwrap();
}
let baseline = build_graph(
temp_dir.path(),
&IgnoreMatcher::empty(),
&[],
None,
None,
)
.expect("baseline graph");
let filtered = build_graph_with(
temp_dir.path(),
&IgnoreMatcher::empty(),
&[],
None,
None,
EdgeFilters {
exclude_type_aliases: true,
},
)
.expect("filtered graph");
assert_eq!(baseline.metrics.total_internal_edges, 3);
assert_eq!(filtered.metrics.total_internal_edges, 2);
let kept: Vec<&str> = filtered
.edges
.iter()
.filter(|edge| edge.resolved)
.filter_map(|edge| edge.to.as_deref())
.collect();
assert!(
kept.contains(&"src/util.rs"),
"a real import must survive: {kept:?}"
);
}
#[test]
fn an_unresolved_local_path_is_not_counted_as_external() {
let report = graph_for(&[
(
"src/main.rs",
"use std::io;\nuse crate::nowhere::Thing;\nfn main() {}\n",
),
("src/lib.rs", "pub fn f() {}\n"),
]);
assert_eq!(
report.metrics.total_external_edges, 1,
"only std::io leaves the project"
);
assert_eq!(report.metrics.unresolved_local_edges, 1);
assert_eq!(
report.metrics.unresolved_local_samples,
vec!["src/main.rs: crate::nowhere::Thing".to_owned()]
);
}
#[test]
fn a_resolvable_project_reports_no_unresolved_local_paths() {
let report = graph_for(&[("src/main.rs", "fn main() {}\n")]);
assert_eq!(report.metrics.unresolved_local_edges, 0);
assert!(
report.metrics.unresolved_local_samples.is_empty(),
"nothing should be listed when nothing is unresolved"
);
}
fn flask_package(extra_imports: &str) -> GraphReport {
graph_for(&[
(
"pkg/__init__.py",
&format!("from .app import Flask{extra_imports}"),
),
(
"pkg/app.py",
"class Flask:\n pass\n\n\ndef helper() -> int:\n return 1\n",
),
])
}
#[test]
fn a_name_the_module_declares_is_not_an_unresolved_local_path() {
let report = flask_package("");
assert_eq!(
report.metrics.unresolved_local_edges, 0,
"a class `app.py` declares is a name, not a missing module: {:?}",
report.metrics.unresolved_local_samples
);
assert_eq!(
imports_of(&report, "pkg/__init__.py"),
vec!["pkg/app.py".to_owned()],
"the dependency itself must still be there -- only the false alarm \
is removed, not the edge"
);
}
#[test]
fn a_module_level_assignment_is_a_name_the_module_declares() {
let report = graph_for(&[
("pkg/__init__.py", "from .globals import request, missing\n"),
("pkg/globals.py", "request = object()\n"),
]);
assert_eq!(
report.metrics.unresolved_local_edges, 1,
"only `missing`, which nothing declares: {:?}",
report.metrics.unresolved_local_samples
);
assert_eq!(
imports_of(&report, "pkg/__init__.py"),
vec!["pkg/globals.py".to_owned()]
);
}
#[test]
fn a_name_nothing_declares_is_still_an_unresolved_local_path() {
let report = flask_package(", Absent");
assert_eq!(
report.metrics.unresolved_local_edges, 1,
"`app.py` declares `Flask` and `helper`, and no `Absent`"
);
assert_eq!(
report.metrics.unresolved_local_samples,
vec!["pkg/__init__.py: .app.Absent".to_owned()]
);
}
#[test]
fn a_local_variable_is_not_a_name_the_module_declares() {
let report = graph_for(&[
("pkg/__init__.py", "from .app import config\n"),
(
"pkg/app.py",
"def build() -> int:\n config = 1\n return config\n",
),
]);
assert_eq!(
report.metrics.unresolved_local_edges, 1,
"`config` is assigned inside a function, so the import cannot succeed"
);
}
#[test]
fn a_decorated_definition_is_still_a_declaration() {
let report = graph_for(&[
("pkg/__init__.py", "from .app import cached\n"),
(
"pkg/app.py",
"from functools import cache\n\n\n@cache\ndef cached() -> int:\n return 1\n",
),
]);
assert_eq!(
report.metrics.unresolved_local_edges, 0,
"{:?}",
report.metrics.unresolved_local_samples
);
}
#[test]
fn a_climbing_name_the_module_declares_is_not_an_unresolved_local_path() {
let report = graph_for(&[
("pkg/sansio/app.py", "from ..helpers import split_path\n"),
(
"pkg/helpers.py",
"def split_path(name: str) -> list[str]:\n return [name]\n",
),
]);
assert_eq!(
report.metrics.unresolved_local_edges, 0,
"{:?}",
report.metrics.unresolved_local_samples
);
assert_eq!(
imports_of(&report, "pkg/sansio/app.py"),
vec!["pkg/helpers.py".to_owned()],
"climbing up two levels must still land on the module"
);
}
#[test]
fn a_name_against_the_package_itself_is_still_an_unresolved_local_path() {
let report = graph_for(&[
("pkg/__init__.py", "class Flask:\n pass\n"),
("pkg/cli.py", "from . import Flask\n"),
]);
assert_eq!(report.metrics.unresolved_local_edges, 1);
}
#[test]
fn unresolved_local_samples_are_capped() {
let files: Vec<(String, String)> = (0..MAX_UNRESOLVED_LOCAL_SAMPLES
+ 5)
.map(|index| {
(
format!("src/f{index}.rs"),
format!("use crate::absent{index}::Thing;\n"),
)
})
.collect();
let borrowed: Vec<(&str, &str)> = files
.iter()
.map(|(path, contents)| (path.as_str(), contents.as_str()))
.collect();
let report = graph_for(&borrowed);
assert_eq!(
report.metrics.unresolved_local_edges,
u64::try_from(MAX_UNRESOLVED_LOCAL_SAMPLES + 5).unwrap_or(u64::MAX),
"the count must stay exact even when the list is capped"
);
assert_eq!(
report.metrics.unresolved_local_samples.len(),
MAX_UNRESOLVED_LOCAL_SAMPLES,
"the sample list must be capped"
);
}
fn nested_module_tree() -> Vec<(&'static str, &'static str)> {
vec![
("src/main.rs", "mod util;\nfn main() {}\n"),
("src/util.rs", "mod helper;\npub fn u() {}\n"),
("src/util/helper.rs", "use super::u;\npub fn h() {}\n"),
]
}
#[test]
fn a_parent_and_child_module_are_not_reported_as_a_cycle() {
let report = graph_for(&nested_module_tree());
assert_eq!(
report.metrics.circular_dependencies, 0,
"module structure is not a dependency cycle: {:?}",
report.metrics.cycles
);
}
#[test]
fn a_real_import_cycle_is_still_reported() {
let report = graph_for(&[
("src/main.rs", "mod a;\nmod b;\nfn main() {}\n"),
("src/a.rs", "use crate::b::Thing;\npub struct A;\n"),
("src/b.rs", "use crate::a::A;\npub struct Thing;\n"),
]);
assert_eq!(
report.metrics.circular_dependencies, 1,
"a genuine import cycle must be reported: {:?}",
report.metrics.cycles
);
}
#[test]
fn a_module_declaration_is_still_reported_as_an_edge() {
let report = graph_for(&nested_module_tree());
assert!(
report
.edges
.iter()
.any(|edge| edge.kind == ImportKind::ModuleDeclaration
&& edge.to.as_deref() == Some("src/util.rs")),
"the `mod util;` edge must still be present: {:?}",
report.edges
);
}
#[test]
fn no_edge_points_at_its_own_file() {
let report = graph_for(&[
("src/main.rs", "mod missing;\nfn main() {}\n"),
("src/lib.rs", "pub fn f() {}\n"),
]);
let self_loops: Vec<&str> = report
.edges
.iter()
.filter(|edge| {
edge.from == *edge.to.as_ref().unwrap_or(&String::new())
})
.map(|edge| edge.import_path.as_str())
.collect();
assert_eq!(
self_loops,
Vec::<&str>::new(),
"a file never depends on itself"
);
}
fn graph_for(files: &[(&str, &str)]) -> GraphReport {
let temp_dir = tempdir().unwrap();
for (relative, contents) in files {
let absolute = temp_dir.path().join(relative);
fs::create_dir_all(absolute.parent().unwrap()).unwrap();
fs::write(absolute, contents).unwrap();
}
build_graph(temp_dir.path(), &IgnoreMatcher::empty(), &[], None, None)
.expect("graph build must succeed")
}
fn imports_of(report: &GraphReport, source: &str) -> Vec<String> {
report
.edges
.iter()
.filter(|edge| edge.from == source && edge.resolved)
.filter_map(|edge| edge.to.clone())
.collect()
}
#[test]
fn a_reverse_query_reaches_the_whole_transitive_closure() {
let temp_dir = tempdir().unwrap();
for (relative, contents) in [
("src/leaf.rs", "pub fn leaf() {}\n"),
("src/mid.rs", "use crate::leaf;\npub fn mid() {}\n"),
("src/top.rs", "use crate::mid;\npub fn top() {}\n"),
("src/lib.rs", "pub mod leaf;\npub mod mid;\npub mod top;\n"),
] {
let absolute = temp_dir.path().join(relative);
fs::create_dir_all(absolute.parent().unwrap()).unwrap();
fs::write(absolute, contents).unwrap();
}
let report = build_graph(
temp_dir.path(),
&IgnoreMatcher::empty(),
&[],
None,
Some(GraphQuery::DependsOn("src/leaf.rs".to_owned())),
)
.expect("graph build must succeed");
let mut paths: Vec<String> = report
.nodes
.iter()
.map(|node| node.file_path.clone())
.collect();
paths.sort();
assert_eq!(
paths,
vec![
"src/leaf.rs".to_owned(),
"src/lib.rs".to_owned(),
"src/mid.rs".to_owned(),
"src/top.rs".to_owned(),
],
"a reverse query must include transitive dependents and the \
parent that declares them, not only direct importers"
);
}
#[test]
fn a_module_declaration_does_not_close_a_cycle() {
let temp_dir = tempdir().unwrap();
for (relative, contents) in [
("src/lib.rs", "pub mod service;\n"),
("src/service.rs", "use crate::Config;\npub fn run() {}\n"),
] {
let absolute = temp_dir.path().join(relative);
fs::create_dir_all(absolute.parent().unwrap()).unwrap();
fs::write(absolute, contents).unwrap();
}
let report = build_graph(
temp_dir.path(),
&IgnoreMatcher::empty(),
&[],
None,
None,
)
.expect("graph build must succeed");
assert_eq!(
report.metrics.circular_dependencies, 0,
"a forced module relationship is not a cycle an edit can fix"
);
}
#[test]
fn mod_declarations_create_internal_edges() {
let report = graph_for(&[
("src/main.rs", "mod util;\nfn main() {}\n"),
("src/util.rs", "pub fn helper() {}\n"),
]);
let imports = imports_of(&report, "src/main.rs");
assert_eq!(
imports,
vec!["src/util.rs".to_owned()],
"a mod declaration must resolve to its file"
);
}
#[test]
fn a_file_that_is_not_utf8_is_a_node_and_contributes_nothing() {
let temp_dir = tempdir().unwrap();
for (relative, contents) in [
("src/main.rs", "mod broken;\npub struct Config;\n"),
("src/leaf.rs", "use crate::Config;\npub fn leaf() {}\n"),
] {
let absolute = temp_dir.path().join(relative);
fs::create_dir_all(absolute.parent().unwrap()).unwrap();
fs::write(absolute, contents).unwrap();
}
fs::write(
temp_dir.path().join("src/broken.rs"),
b"use crate::\xff\xfe;\n",
)
.unwrap();
let report = build_graph(
temp_dir.path(),
&IgnoreMatcher::empty(),
&[],
None,
None,
)
.expect("graph build must succeed");
assert!(
report
.nodes
.iter()
.any(|node| node.file_path == "src/broken.rs"),
"a file whose bytes cannot be decoded is still a node: {:?}",
report
.nodes
.iter()
.map(|n| &n.file_path)
.collect::<Vec<_>>()
);
assert!(
imports_of(&report, "src/broken.rs").is_empty(),
"no edge can be claimed from bytes that are not a source file: {:?}",
report
.edges
.iter()
.filter(|edge| edge.from == "src/broken.rs")
.collect::<Vec<_>>()
);
assert_eq!(
imports_of(&report, "src/leaf.rs"),
vec!["src/main.rs".to_owned()],
"one unreadable file must not cost the graph its other edges"
);
}
#[test]
fn a_mod_only_crate_is_fully_connected() {
let report = graph_for(&[
("src/main.rs", "mod a;\nmod b;\nfn main() {}\n"),
("src/a.rs", "pub fn a() {}\n"),
("src/b.rs", "pub fn b() {}\n"),
]);
assert_eq!(report.metrics.total_internal_edges, 2);
assert_eq!(report.metrics.circular_dependencies, 0);
}
#[test]
fn inline_modules_are_not_edges() {
let report = graph_for(&[(
"src/main.rs",
"mod inner {\n pub fn f() {}\n}\nfn main() {}\n",
)]);
assert_eq!(
report.metrics.total_internal_edges, 0,
"an inline module has no file to import"
);
}
#[test]
fn a_path_attribute_module_is_skipped() {
let report = graph_for(&[
(
"src/main.rs",
"#[path = \"other/renamed.rs\"]\nmod util;\nfn main() {}\n",
),
("src/other/renamed.rs", "pub fn r() {}\n"),
]);
assert_eq!(
report.metrics.total_internal_edges, 0,
"a renamed module must not resolve against the declared name"
);
}
#[test]
fn mod_and_use_together_both_resolve() {
let report = graph_for(&[
(
"src/main.rs",
"mod util;\nuse crate::helper::h;\nfn main() {}\n",
),
("src/util.rs", "pub fn u() {}\n"),
("src/helper.rs", "pub fn h() {}\n"),
]);
let mut imports = imports_of(&report, "src/main.rs");
imports.sort();
assert_eq!(
imports,
vec!["src/helper.rs".to_owned(), "src/util.rs".to_owned()]
);
}
#[test]
fn mod_resolves_through_mod_rs() {
let report = graph_for(&[
("src/lib.rs", "mod graph;\n"),
("src/graph/mod.rs", "pub mod types;\n"),
("src/graph/types.rs", "pub struct T;\n"),
]);
assert_eq!(
imports_of(&report, "src/lib.rs"),
vec!["src/graph/mod.rs".to_owned()]
);
assert_eq!(
imports_of(&report, "src/graph/mod.rs"),
vec!["src/graph/types.rs".to_owned()],
"a nested mod must also resolve"
);
}
fn write_file(base_dir: &Path, relative_path: &str, contents: &str) {
let absolute_path = base_dir.join(relative_path);
if let Some(parent) = absolute_path.parent() {
fs::create_dir_all(parent).unwrap();
}
fs::write(absolute_path, contents).unwrap();
}
fn node_map_from_edges(edges: &[(&str, &[&str])]) -> NodeMap {
let mut map: NodeMap = BTreeMap::new();
for (node, imports) in edges {
let entry = map.entry((*node).to_owned()).or_default();
for import in *imports {
entry.imports.push((*import).to_owned());
}
}
map
}
#[test]
fn cycle_key_ignores_rotation_and_direction() {
let a = vec![
"a".to_owned(),
"b".to_owned(),
"c".to_owned(),
"a".to_owned(),
];
let rotated = vec![
"b".to_owned(),
"c".to_owned(),
"a".to_owned(),
"b".to_owned(),
];
assert_eq!(cycle_key(&a), cycle_key(&rotated));
}
#[test]
fn cycle_key_distinguishes_different_node_sets() {
let a = vec!["a".to_owned(), "b".to_owned(), "a".to_owned()];
let b = vec!["a".to_owned(), "c".to_owned(), "a".to_owned()];
assert_ne!(cycle_key(&a), cycle_key(&b));
}
#[test]
fn detects_a_two_node_cycle() {
let map =
node_map_from_edges(&[("a.rs", &["b.rs"]), ("b.rs", &["a.rs"])]);
let cycles = detect_cycles(&map);
assert_eq!(cycles.len(), 1, "got {cycles:?}");
}
#[test]
fn a_ring_is_reported_once_not_once_per_member() {
let map = node_map_from_edges(&[
("a.rs", &["b.rs"]),
("b.rs", &["c.rs"]),
("c.rs", &["a.rs"]),
]);
let cycles = detect_cycles(&map);
assert_eq!(
cycles.len(),
1,
"a 3-node ring must report once: {cycles:?}"
);
}
#[test]
fn a_self_importing_file_is_one_cycle() {
let map = node_map_from_edges(&[("a.rs", &["a.rs"])]);
assert_eq!(detect_cycles(&map).len(), 1);
}
#[test]
fn distinct_rings_are_reported_separately() {
let map = node_map_from_edges(&[
("a.rs", &["b.rs"]),
("b.rs", &["a.rs"]),
("x.rs", &["y.rs"]),
("y.rs", &["x.rs"]),
]);
assert_eq!(detect_cycles(&map).len(), 2);
}
#[test]
fn acyclic_graph_reports_no_cycles() {
let map = node_map_from_edges(&[
("a.rs", &["b.rs"]),
("b.rs", &["c.rs"]),
("c.rs", &[]),
]);
assert_eq!(detect_cycles(&map), Vec::<Vec<String>>::new());
}
#[test]
fn detection_is_deterministic_across_repeated_runs() {
let map = node_map_from_edges(&[
("a.rs", &["b.rs", "c.rs"]),
("b.rs", &["c.rs", "a.rs"]),
("c.rs", &["a.rs", "b.rs"]),
]);
let first = detect_cycles(&map);
let second = detect_cycles(&map);
assert_eq!(first, second);
}
#[test]
fn resolves_rust_imports_for_crate_self_and_super_modules() {
let files = known_files(&[
"src/main.rs",
"src/core/graph.rs",
"src/core/graph/mod.rs",
"src/core/graph/parser.rs",
"src/core/graph/types.rs",
]);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Rust,
"crate::core::graph",
"src/main.rs",
&files
),
Some("src/core/graph.rs".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Rust,
"self::types",
"src/core/graph/mod.rs",
&files
),
Some("src/core/graph/types.rs".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Rust,
"super::types",
"src/core/graph/parser.rs",
&files
),
Some("src/core/graph/types.rs".to_owned())
);
}
#[test]
fn an_unqualified_rust_path_resolves_to_the_local_module() {
let files = known_files(&[
"src/main.rs",
"src/core/code_loc.rs",
"src/core/code_loc/analyzer.rs",
"src/core/code_loc/types.rs",
"src/types.rs",
]);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Rust,
"types::CodeLocReport",
"src/core/code_loc.rs",
&files,
),
Some("src/core/code_loc/types.rs".to_owned()),
"the module beside the importing file wins over the crate root"
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Rust,
"analyzer::CodeLoc",
"src/core/code_loc.rs",
&files,
),
Some("src/core/code_loc/analyzer.rs".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Rust,
"serde::Serialize",
"src/core/code_loc.rs",
&files,
),
None,
"with no local module of that name the path is an external crate"
);
}
#[test]
fn a_parent_referring_to_its_own_child_is_not_a_cycle() {
assert!(
is_own_child_module(
"src/core/runtime.rs",
"src/core/runtime/context.rs"
),
"a parent to its declared child is structural"
);
assert!(
is_own_child_module(
"src/core/code_loc.rs",
"src/core/code_loc/analyzer.rs"
),
"however the child is named"
);
assert!(
!is_own_child_module("src/core/graph.rs", "src/core/types.rs"),
"a sibling module is a real dependency"
);
assert!(
!is_own_child_module("src/core/context.rs", "src/core.rs"),
"a child naming its parent is a real reference, which is why the \\
declaration edge is the one excluded"
);
assert!(
is_own_child_module("src/core.rs", "src/core/context.rs"),
"a module file owns the directory beside it"
);
assert!(
is_own_child_module("src/core/mod.rs", "src/core/graph.rs"),
"and so does mod.rs"
);
}
#[test]
fn a_path_naming_a_reachability_resolves_to_the_declaring_file() {
let files = known_files(&[
"axum/src/lib.rs",
"axum/src/boxed.rs",
"axum/src/routing/mod.rs",
"axum-core/src/lib.rs",
"axum-core/src/body.rs",
]);
let mut index = declarations::DeclarationIndex::default();
index.insert(
"axum/src/lib.rs",
declarations::DeclaredNames::from_names(["Router"]),
);
index.insert(
"axum/src/routing/mod.rs",
declarations::DeclaredNames::from_names(["Router"]),
);
index.insert(
"axum-core/src/lib.rs",
declarations::DeclaredNames::from_names(["BoxError"]),
);
assert_eq!(
resolve_with_index(
"crate::Router",
"axum/src/boxed.rs",
&files,
&index,
),
Some("axum/src/lib.rs".to_owned()),
"a name the crate root re-exports points at the crate root"
);
assert_eq!(
resolve_with_index(
"crate::BoxError",
"axum-core/src/body.rs",
&files,
&index,
),
Some("axum-core/src/lib.rs".to_owned()),
"a name the crate root declares directly points there too"
);
}
#[test]
fn a_super_path_naming_a_name_this_file_declares_resolves_to_it() {
let files = known_files(&["src/json_lines.rs", "src/lib.rs"]);
let mut index = declarations::DeclarationIndex::default();
index.insert(
"src/json_lines.rs",
declarations::DeclaredNames::from_names(["JsonLines"]),
);
let resolved = resolve_import_with(
"super::JsonLines",
"src/json_lines.rs",
1,
ImportKind::Dependency,
SupportedLanguage::Rust,
&ResolutionInputs {
base_path: std::path::PathBuf::new(),
known_files: files,
declarations: index,
manifests: manifests::ManifestIndex::default(),
},
);
assert_eq!(
resolved.file().map(ToOwned::to_owned),
Some("src/json_lines.rs".to_owned()),
"a `super::` path naming a struct in the same file is a self-reference"
);
}
#[test]
fn a_private_use_does_not_make_a_name_reachable_from_the_crate_root() {
let files = known_files(&["src/main.rs", "src/service.rs"]);
let mut index = declarations::DeclarationIndex::default();
index.insert("src/main.rs", declarations::DeclaredNames::default());
index.insert(
"src/service.rs",
declarations::DeclaredNames::from_names(["run"]),
);
assert_eq!(
resolve_with_index("crate::service", "src/main.rs", &files, &index),
Some("src/service.rs".to_owned()),
"the module walk answers this one; no name lookup is needed"
);
}
#[test]
fn an_unqualified_path_never_resolves_through_a_name_lookup() {
let files =
known_files(&["examples/demo/src/main.rs", "src/routing/mod.rs"]);
let mut index = declarations::DeclarationIndex::default();
index.insert(
"examples/demo/src/main.rs",
declarations::DeclaredNames::from_names(["Router"]),
);
index.insert(
"src/routing/mod.rs",
declarations::DeclaredNames::from_names(["Router"]),
);
assert_eq!(
resolve_with_index(
"axum::Router",
"examples/demo/src/main.rs",
&files,
&index,
),
None,
"an unqualified path names a crate, not this file's own module"
);
}
#[test]
fn a_structural_edge_stays_in_the_graph_and_leaves_the_cycle_walk() {
let mut node_map: NodeMap = BTreeMap::new();
node_map.entry("src/lib.rs".to_owned()).or_default().imports =
vec!["src/inner.rs".to_owned(), "src/routing.rs".to_owned()];
node_map
.entry("src/inner.rs".to_owned())
.or_default()
.imports = vec!["src/lib.rs".to_owned()];
node_map
.entry("src/routing.rs".to_owned())
.or_default()
.imports = vec!["src/lib.rs".to_owned()];
node_map
.entry("src/routing.rs".to_owned())
.or_default()
.imports
.push("src/inner.rs".to_owned());
let walk = structural_adjacency(&node_map);
assert_eq!(
node_map["src/lib.rs"].imports.len(),
2,
"both dependencies are reported, so a blast-radius query can use them"
);
assert_eq!(
walk["src/lib.rs"].imports,
Vec::<String>::new(),
"a parent naming its children is structural in both directions"
);
assert_eq!(
walk["src/inner.rs"].imports,
Vec::<String>::new(),
"a child naming its ancestor is structural the other way"
);
assert_eq!(
walk["src/routing.rs"].imports,
vec!["src/inner.rs".to_owned()],
"between siblings the edge is a dependency and must survive"
);
}
fn resolve_with_index(
import_path: &str,
source_file: &str,
files: &plugins::KnownFiles,
index: &declarations::DeclarationIndex,
) -> Option<String> {
resolve_import_with(
import_path,
source_file,
0,
ImportKind::Dependency,
SupportedLanguage::Rust,
&ResolutionInputs {
base_path: std::path::PathBuf::new(),
known_files: files.clone(),
declarations: index.clone(),
manifests: manifests::ManifestIndex::default(),
},
)
.file()
.map(ToOwned::to_owned)
}
#[test]
fn resolves_python_imports_for_absolute_and_relative_modules() {
let files = known_files(&[
"pkg/local.py",
"pkg/sub/module.py",
"pkg/shared/util.py",
"pkg/shared/__init__.py",
]);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Python,
"pkg.local",
"pkg/sub/module.py",
&files
),
Some("pkg/local.py".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Python,
".local",
"pkg/module.py",
&files
),
Some("pkg/local.py".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Python,
"..shared.util",
"pkg/sub/module.py",
&files
),
Some("pkg/shared/util.py".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Python,
"requests",
"pkg/sub/module.py",
&files
),
None
);
}
#[test]
fn resolves_js_ts_imports_with_relative_paths_and_index_files() {
let files = known_files(&[
"src/main.ts",
"src/utils.ts",
"src/lib/index.ts",
"src/components/button.jsx",
]);
assert_eq!(
resolve_import_lang(
SupportedLanguage::TypeScript,
"./utils",
"src/main.ts",
&files
),
Some("src/utils.ts".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::TypeScript,
"../lib",
"src/features/item.ts",
&files
),
Some("src/lib/index.ts".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::TypeScript,
"react",
"src/main.ts",
&files
),
None
);
}
#[test]
fn resolves_go_java_and_c_family_imports() {
let go_files =
known_files(&["internal/app/main.go", "internal/pkg/service.go"]);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Go,
"github.com/demo/pkg",
"internal/app/main.go",
&go_files
),
Some("internal/pkg/service.go".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Go,
"fmt",
"internal/app/main.go",
&go_files
),
None
);
let java_files = known_files(&[
"src/com/example/utils/Helper.java",
"utils/Helper.java",
]);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Java,
"com.example.utils.Helper",
"src/com/example/Main.java",
&java_files
),
Some("src/com/example/utils/Helper.java".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::Java,
"utils.Helper",
"src/com/example/Main.java",
&java_files
),
Some("utils/Helper.java".to_owned())
);
let c_files = known_files(&["src/main.c", "include/util.h", "util.h"]);
assert_eq!(
resolve_import_lang(
SupportedLanguage::C,
"util.h",
"src/main.c",
&c_files
),
Some("util.h".to_owned())
);
assert_eq!(
resolve_import_lang(
SupportedLanguage::C,
"<stdio.h>",
"src/main.c",
&c_files
),
None
);
}
#[test]
fn builds_graph_for_rust_project() {
let temp_dir = tempdir().unwrap();
write_file(
temp_dir.path(),
"src/main.rs",
"use crate::utils;\n\nfn main() {}\n",
);
write_file(
temp_dir.path(),
"src/utils.rs",
"pub fn helper() -> bool { true }\n",
);
let ignore = IgnoreMatcher::empty();
let report =
build_graph(temp_dir.path(), &ignore, &[], None, None).unwrap();
assert!(report.nodes.len() >= 2);
assert_ne!(
report.edges,
Vec::<GraphEdge>::new(),
"expected at least one edge"
);
}
#[test]
fn detects_circular_dependency() {
let temp_dir = tempdir().unwrap();
write_file(temp_dir.path(), "a.rs", "use crate::b;\n\npub fn a() {}\n");
write_file(temp_dir.path(), "b.rs", "use crate::a;\n\npub fn b() {}\n");
let ignore = IgnoreMatcher::empty();
let report =
build_graph(temp_dir.path(), &ignore, &[], None, None).unwrap();
assert!(
report.metrics.circular_dependencies > 0,
"should detect circular dependency between a.rs and b.rs"
);
}
#[test]
fn nested_rust_super_imports_resolve_to_sibling_module() {
let temp_dir = tempdir().unwrap();
write_file(temp_dir.path(), "src/lib.rs", "mod outer;\n");
write_file(
temp_dir.path(),
"src/outer/mod.rs",
"mod parser;\nmod types;\n",
);
write_file(
temp_dir.path(),
"src/outer/parser.rs",
"use super::types::Token;\n\npub fn parse(_: Token) {}\n",
);
write_file(
temp_dir.path(),
"src/outer/types.rs",
"pub struct Token;\n",
);
let ignore = IgnoreMatcher::empty();
let report =
build_graph(temp_dir.path(), &ignore, &[], None, None).unwrap();
assert!(report.edges.iter().any(|edge| {
edge.from == "src/outer/parser.rs"
&& edge.to.as_deref() == Some("src/outer/types.rs")
&& edge.resolved
}));
}
#[test]
fn parent_relative_python_imports_resolve_across_packages() {
let temp_dir = tempdir().unwrap();
write_file(
temp_dir.path(),
"pkg/app/main.py",
"from ..shared.util import helper\n",
);
write_file(
temp_dir.path(),
"pkg/shared/util.py",
"def helper() -> None:\n pass\n",
);
let ignore = IgnoreMatcher::empty();
let report =
build_graph(temp_dir.path(), &ignore, &[], None, None).unwrap();
assert!(report.edges.iter().any(|edge| {
edge.from == "pkg/app/main.py"
&& edge.to.as_deref() == Some("pkg/shared/util.py")
&& edge.resolved
}));
}
#[test]
fn depth_zero_keeps_the_traversal_root_and_nothing_else() {
let temp_dir = tempdir().unwrap();
write_file(temp_dir.path(), "src/main.rs", "use crate::middle;\n");
write_file(temp_dir.path(), "src/middle.rs", "use crate::leaf;\n");
write_file(temp_dir.path(), "src/leaf.rs", "pub fn leaf() {}\n");
let ignore = IgnoreMatcher::empty();
let report = build_graph(
temp_dir.path(),
&ignore,
&[PathBuf::from("src/main.rs")],
Some(0),
None,
)
.unwrap();
let node_paths: BTreeSet<_> = report
.nodes
.iter()
.map(|node| node.file_path.as_str())
.collect();
assert_eq!(node_paths, BTreeSet::from(["src/main.rs"]));
assert_eq!(report.metrics.total_files, 1);
}
#[test]
fn depth_one_keeps_the_root_and_what_it_reaches_directly() {
let temp_dir = tempdir().unwrap();
write_file(temp_dir.path(), "src/main.rs", "use crate::middle;\n");
write_file(temp_dir.path(), "src/middle.rs", "use crate::leaf;\n");
write_file(temp_dir.path(), "src/leaf.rs", "pub fn leaf() {}\n");
let ignore = IgnoreMatcher::empty();
let report = build_graph(
temp_dir.path(),
&ignore,
&[PathBuf::from("src/main.rs")],
Some(1),
None,
)
.unwrap();
let node_paths: BTreeSet<_> = report
.nodes
.iter()
.map(|node| node.file_path.as_str())
.collect();
assert_eq!(
node_paths,
BTreeSet::from(["src/main.rs", "src/middle.rs"])
);
assert_eq!(report.metrics.total_files, 2);
assert_eq!(report.metrics.total_internal_edges, 1);
assert_eq!(report.metrics.most_imported[0].file_path, "src/middle.rs");
}
#[test]
fn depends_on_query_at_depth_one_returns_the_direct_importers() {
let temp_dir = tempdir().unwrap();
write_file(temp_dir.path(), "src/main.rs", "use crate::service;\n");
write_file(temp_dir.path(), "src/service.rs", "use crate::util;\n");
write_file(temp_dir.path(), "src/util.rs", "pub fn util() {}\n");
let ignore = IgnoreMatcher::empty();
let report = build_graph(
temp_dir.path(),
&ignore,
&[],
Some(1),
Some(GraphQuery::DependsOn("src/util.rs".to_owned())),
)
.unwrap();
let node_paths: BTreeSet<_> = report
.nodes
.iter()
.map(|node| node.file_path.as_str())
.collect();
assert_eq!(
node_paths,
BTreeSet::from(["src/service.rs", "src/util.rs"])
);
assert_eq!(
report.query,
Some(GraphQuery::DependsOn("src/util.rs".to_owned()))
);
assert_eq!(report.depth, Some(1));
}
#[test]
fn depends_on_query_requires_existing_node() {
let temp_dir = tempdir().unwrap();
write_file(temp_dir.path(), "src/main.rs", "fn main() {}\n");
let ignore = IgnoreMatcher::empty();
let error = build_graph(
temp_dir.path(),
&ignore,
&[],
None,
Some(GraphQuery::DependsOn("src/missing.rs".to_owned())),
)
.unwrap_err();
assert!(
error
.to_string()
.contains("did not resolve to an analyzed graph node")
);
}
#[test]
fn simplify_relative_path_works() {
assert_eq!(
plugins::paths::resolve_relative("src/core", "../utils"),
"src/utils"
);
assert_eq!(
plugins::paths::resolve_relative("src", "./helpers"),
"src/helpers"
);
assert_eq!(plugins::paths::resolve_relative("", "./foo"), "foo");
}
#[test]
fn empty_directory_produces_empty_graph() {
let temp_dir = tempdir().unwrap();
let ignore = IgnoreMatcher::empty();
let report =
build_graph(temp_dir.path(), &ignore, &[], None, None).unwrap();
assert_eq!(report.nodes, Vec::<GraphNode>::new());
assert_eq!(report.edges, Vec::<GraphEdge>::new());
}
}