use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::fs;
use std::path::{Path, PathBuf};
use anyhow::{Context, Result};
use oxc_resolver::{ResolveOptions, Resolver};
use path_clean::PathClean;
use serde::Serialize;
use crate::parser::{ImportBinding, ImportedName, MODULE_INIT, ParsedModule, parse_module};
use crate::workspace::{Package, Target};
#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd, Serialize)]
pub struct Node {
pub file: PathBuf,
pub symbol: String,
}
impl Node {
pub fn new(file: impl Into<PathBuf>, symbol: impl Into<String>) -> Self {
Self {
file: file.into(),
symbol: symbol.into(),
}
}
}
#[derive(Clone, Debug)]
pub struct TargetNode {
pub package: String,
pub node: Node,
}
#[derive(Debug)]
pub struct DependencyGraph {
pub modules: BTreeMap<PathBuf, ParsedModule>,
pub edges: BTreeMap<Node, BTreeSet<Node>>,
pub targets: Vec<TargetNode>,
resolver: Resolver,
workspace_packages: Vec<WorkspacePackage>,
}
#[derive(Debug)]
struct WorkspacePackage {
name: String,
dir: PathBuf,
entrypoint: Option<PathBuf>,
exports: BTreeMap<String, PathBuf>,
}
#[derive(Clone, Debug)]
pub struct Reachability {
pub reached: BTreeSet<Node>,
pub previous: BTreeMap<Node, Node>,
pub seed_for: BTreeMap<Node, Node>,
}
impl DependencyGraph {
pub fn build(files: &[PathBuf], targets: &[Target], packages: &[Package]) -> Result<Self> {
let mut modules = BTreeMap::new();
for path in files {
let path = normalize_path(path);
let source = fs::read_to_string(&path)
.with_context(|| format!("failed to read {}", path.display()))?;
let parsed = parse_module(&path, &source)?;
modules.insert(path, parsed);
}
let resolver = Resolver::new(ResolveOptions {
condition_names: vec![
"source".to_string(),
"import".to_string(),
"module".to_string(),
"default".to_string(),
],
extensions: vec![
".ts".to_string(),
".tsx".to_string(),
".mts".to_string(),
".cts".to_string(),
".js".to_string(),
".jsx".to_string(),
".mjs".to_string(),
".cjs".to_string(),
".json".to_string(),
],
extension_alias: vec![
(
".js".to_string(),
vec![".ts".to_string(), ".tsx".to_string(), ".js".to_string()],
),
(
".mjs".to_string(),
vec![".mts".to_string(), ".mjs".to_string()],
),
(
".cjs".to_string(),
vec![".cts".to_string(), ".cjs".to_string()],
),
],
main_fields: vec![
"source".to_string(),
"module".to_string(),
"main".to_string(),
],
..ResolveOptions::default()
});
let workspace_packages = packages
.iter()
.map(|package| WorkspacePackage {
name: package.name.clone(),
dir: normalize_path(&package.dir),
entrypoint: package.entrypoint.as_ref().map(normalize_path),
exports: package
.exports
.iter()
.map(|(name, path)| (name.clone(), normalize_path(path)))
.collect(),
})
.collect();
let mut graph = Self {
modules,
edges: BTreeMap::new(),
targets: Vec::new(),
resolver,
workspace_packages,
};
graph.link_modules();
graph.link_targets(targets);
Ok(graph)
}
pub fn affected(&self, seeds: &BTreeSet<Node>) -> Reachability {
let mut reverse: BTreeMap<Node, BTreeSet<Node>> = BTreeMap::new();
for (consumer, dependencies) in &self.edges {
for dependency in dependencies {
reverse
.entry(dependency.clone())
.or_default()
.insert(consumer.clone());
}
}
let mut reached = seeds.clone();
let mut previous = BTreeMap::new();
let mut seed_for = BTreeMap::new();
let mut queue = VecDeque::new();
for seed in seeds {
seed_for.insert(seed.clone(), seed.clone());
queue.push_back(seed.clone());
}
while let Some(node) = queue.pop_front() {
let Some(consumers) = reverse.get(&node) else {
continue;
};
for consumer in consumers {
if reached.insert(consumer.clone()) {
previous.insert(consumer.clone(), node.clone());
seed_for.insert(consumer.clone(), seed_for[&node].clone());
queue.push_back(consumer.clone());
}
}
}
Reachability {
reached,
previous,
seed_for,
}
}
pub fn path_to(&self, reachability: &Reachability, target: &Node) -> Option<Vec<Node>> {
let seed = reachability.seed_for.get(target)?;
let mut path = vec![target.clone()];
let mut current = target;
while current != seed {
current = reachability.previous.get(current)?;
path.push(current.clone());
}
path.reverse();
Some(path)
}
pub fn target_node(package: &str) -> Node {
Node::new(PathBuf::from("<target>"), package)
}
fn link_modules(&mut self) {
let paths: Vec<_> = self.modules.keys().cloned().collect();
for path in paths {
let Some(module) = self.modules.get(&path).cloned() else {
continue;
};
for (name, symbol) in &module.symbols {
let consumer = Node::new(&path, name);
for dependency in &symbol.dependencies {
self.add_edge(consumer.clone(), Node::new(&path, dependency));
}
}
for (local_name, import) in &module.imports {
self.link_import(&path, local_name, import);
}
for request in &module.module_requests {
if let Some(dependency_path) = self.resolve(&path, request) {
self.add_edge(
Node::new(&path, MODULE_INIT),
Node::new(dependency_path, MODULE_INIT),
);
}
}
}
}
fn link_import(&mut self, path: &Path, local_name: &str, import: &ImportBinding) {
let Some(dependency_path) = self.resolve(path, &import.source) else {
return;
};
let consumer = Node::new(path, local_name);
self.add_edge(consumer.clone(), Node::new(&dependency_path, MODULE_INIT));
match &import.imported {
ImportedName::Named(name) => {
let mut visited = BTreeSet::new();
for dependency in self.resolve_export(&dependency_path, name, &mut visited) {
self.add_edge(consumer.clone(), dependency);
}
}
ImportedName::Namespace => {
let mut visited = BTreeSet::new();
for dependency in self.all_exports(&dependency_path, &mut visited) {
self.add_edge(consumer.clone(), dependency);
}
}
}
}
fn link_targets(&mut self, targets: &[Target]) {
for target in targets {
let target_node = Self::target_node(&target.package);
let entrypoint = normalize_path(&target.entrypoint);
if !self.modules.contains_key(&entrypoint) {
self.targets.push(TargetNode {
package: target.package.clone(),
node: target_node,
});
continue;
}
self.add_edge(target_node.clone(), Node::new(&entrypoint, MODULE_INIT));
let mut visited = BTreeSet::new();
let exports = self.all_exports(&entrypoint, &mut visited);
if exports.is_empty() {
if let Some(module) = self.modules.get(&entrypoint) {
let symbols: Vec<_> = module
.symbols
.iter()
.filter(|(name, symbol)| name.as_str() != MODULE_INIT && symbol.runtime)
.map(|(name, _)| name.clone())
.collect();
for symbol in symbols {
self.add_edge(target_node.clone(), Node::new(&entrypoint, symbol));
}
}
} else {
for exported in exports {
self.add_edge(target_node.clone(), exported);
}
}
self.targets.push(TargetNode {
package: target.package.clone(),
node: target_node,
});
}
}
fn resolve_export(
&self,
path: &Path,
export_name: &str,
visited: &mut BTreeSet<(PathBuf, String)>,
) -> BTreeSet<Node> {
let key = (path.to_path_buf(), export_name.to_string());
if !visited.insert(key) {
return BTreeSet::new();
}
let Some(module) = self.modules.get(path) else {
return BTreeSet::new();
};
let mut resolved = BTreeSet::new();
if let Some(local_name) = module.local_exports.get(export_name)
&& module
.symbols
.get(local_name)
.is_some_and(|symbol| symbol.runtime)
{
resolved.insert(Node::new(path, local_name));
}
for re_export in module
.re_exports
.iter()
.filter(|re_export| re_export.exported == export_name)
{
let Some(dependency_path) = self.resolve(path, &re_export.source) else {
continue;
};
match &re_export.imported {
ImportedName::Named(name) => {
resolved.extend(self.resolve_export(&dependency_path, name, visited));
}
ImportedName::Namespace => {
resolved.extend(self.all_exports(&dependency_path, visited));
}
}
}
if resolved.is_empty() && export_name != "default" {
for source in &module.star_exports {
let Some(dependency_path) = self.resolve(path, source) else {
continue;
};
resolved.extend(self.resolve_export(&dependency_path, export_name, visited));
}
}
resolved
}
fn all_exports(
&self,
path: &Path,
visited: &mut BTreeSet<(PathBuf, String)>,
) -> BTreeSet<Node> {
let Some(module) = self.modules.get(path) else {
return BTreeSet::new();
};
let mut resolved = BTreeSet::new();
for export_name in module.local_exports.keys() {
resolved.extend(self.resolve_export(path, export_name, visited));
}
for re_export in &module.re_exports {
resolved.extend(self.resolve_export(path, &re_export.exported, visited));
}
for source in &module.star_exports {
let Some(dependency_path) = self.resolve(path, source) else {
continue;
};
resolved.extend(self.all_exports(&dependency_path, visited));
}
resolved
}
fn resolve(&self, importer: &Path, request: &str) -> Option<PathBuf> {
if let Some(package) = self.workspace_packages.iter().find(|package| {
request == package.name
|| request
.strip_prefix(&package.name)
.is_some_and(|suffix| suffix.starts_with('/'))
}) {
let subpath = request
.strip_prefix(&package.name)
.unwrap_or_default()
.trim_start_matches('/');
let export_name = if subpath.is_empty() {
".".to_string()
} else {
format!("./{subpath}")
};
let candidate = package.exports.get(&export_name).cloned().or_else(|| {
if subpath.is_empty() {
package.entrypoint.clone()
} else {
resolve_from_directory(&self.resolver, &package.dir, &format!("./{subpath}"))
}
});
if let Some(path) = candidate.filter(|path| self.modules.contains_key(path)) {
return Some(path);
}
}
let directory = importer.parent()?;
if request.starts_with('.') {
let requested = directory.join(request).clean();
let mut candidates = Vec::new();
match requested
.extension()
.and_then(|extension| extension.to_str())
{
Some("js") => {
candidates.push(requested.with_extension("ts"));
candidates.push(requested.with_extension("tsx"));
candidates.push(requested);
}
Some("mjs") => {
candidates.push(requested.with_extension("mts"));
candidates.push(requested);
}
Some("cjs") => {
candidates.push(requested.with_extension("cts"));
candidates.push(requested);
}
Some(_) => candidates.push(requested),
None => {
candidates.push(requested.clone());
for extension in ["ts", "tsx", "mts", "cts", "js", "jsx", "mjs", "cjs"] {
candidates.push(requested.with_extension(extension));
candidates.push(requested.join("index").with_extension(extension));
}
}
}
return candidates
.into_iter()
.find(|candidate| self.modules.contains_key(candidate));
}
if !request.starts_with('/') && !request.starts_with('#') {
return None;
}
let path = resolve_from_directory(&self.resolver, directory, request)?;
self.modules.contains_key(&path).then_some(path)
}
fn add_edge(&mut self, consumer: Node, dependency: Node) {
if consumer != dependency {
self.edges.entry(consumer).or_default().insert(dependency);
}
}
}
fn resolve_from_directory(resolver: &Resolver, directory: &Path, request: &str) -> Option<PathBuf> {
resolver
.resolve(directory, request)
.ok()
.map(|resolution| normalize_path(resolution.full_path()))
}
pub fn normalize_path(path: impl AsRef<Path>) -> PathBuf {
path.as_ref()
.canonicalize()
.unwrap_or_else(|_| path.as_ref().to_path_buf())
}
#[cfg(test)]
mod tests {
use std::fs;
use tempfile::tempdir;
use super::*;
#[test]
fn reaches_only_the_target_importing_the_changed_symbol() {
let root = tempdir().unwrap();
let shared = root.path().join("shared.ts");
let app_a = root.path().join("app-a.ts");
let app_b = root.path().join("app-b.ts");
fs::write(
&shared,
"export const used = 1; export const unrelated = 2;",
)
.unwrap();
fs::write(
&app_a,
"import { used } from './shared'; export default used;",
)
.unwrap();
fs::write(
&app_b,
"import { unrelated } from './shared'; export default unrelated;",
)
.unwrap();
let targets = vec![
Target {
package: "app-a".to_string(),
entrypoint: app_a.clone(),
},
Target {
package: "app-b".to_string(),
entrypoint: app_b.clone(),
},
];
let graph = DependencyGraph::build(&[shared.clone(), app_a, app_b], &targets, &[]).unwrap();
let seeds = BTreeSet::from([Node::new(normalize_path(shared), "used")]);
let reached = graph.affected(&seeds);
assert!(
reached
.reached
.contains(&DependencyGraph::target_node("app-a"))
);
assert!(
!reached
.reached
.contains(&DependencyGraph::target_node("app-b"))
);
}
#[test]
fn resolves_workspace_exports_without_node_modules() {
let root = tempdir().unwrap();
let shared_dir = root.path().join("packages/shared");
let app_dir = root.path().join("apps/app");
fs::create_dir_all(shared_dir.join("src")).unwrap();
fs::create_dir_all(app_dir.join("src")).unwrap();
let shared = shared_dir.join("src/index.ts");
let app = app_dir.join("src/index.ts");
fs::write(&shared, "export const value = 1;").unwrap();
fs::write(
&app,
"import { value } from '@repo/shared'; export default value;",
)
.unwrap();
let packages = vec![Package {
name: "@repo/shared".to_string(),
dir: shared_dir,
scripts: BTreeMap::new(),
entrypoint: Some(shared.clone()),
exports: BTreeMap::from([(".".to_string(), shared.clone())]),
}];
let targets = vec![Target {
package: "app".to_string(),
entrypoint: app.clone(),
}];
let graph = DependencyGraph::build(&[shared.clone(), app], &targets, &packages).unwrap();
let seeds = BTreeSet::from([Node::new(normalize_path(shared), "value")]);
let reached = graph.affected(&seeds);
assert!(
reached
.reached
.contains(&DependencyGraph::target_node("app"))
);
}
}