use std::{fmt, iter::FromIterator, ops, str::FromStr, sync::Arc};
use cfg::CfgOptions;
use rustc_hash::{FxHashMap, FxHashSet};
use syntax::SmolStr;
use tt::TokenExpander;
use vfs::{file_set::FileSet, FileId, VfsPath};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct SourceRootId(pub u32);
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct SourceRoot {
pub is_library: bool,
pub(crate) file_set: FileSet,
}
impl SourceRoot {
pub fn new_local(file_set: FileSet) -> SourceRoot {
SourceRoot { is_library: false, file_set }
}
pub fn new_library(file_set: FileSet) -> SourceRoot {
SourceRoot { is_library: true, file_set }
}
pub fn path_for_file(&self, file: &FileId) -> Option<&VfsPath> {
self.file_set.path_for_file(file)
}
pub fn file_for_path(&self, path: &VfsPath) -> Option<&FileId> {
self.file_set.file_for_path(path)
}
pub fn iter(&self) -> impl Iterator<Item = FileId> + '_ {
self.file_set.iter()
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct CrateGraph {
arena: FxHashMap<CrateId, CrateData>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct CrateId(pub u32);
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct CrateName(SmolStr);
impl CrateName {
pub fn new(name: &str) -> Result<CrateName, &str> {
if name.contains('-') {
Err(name)
} else {
Ok(Self(SmolStr::new(name)))
}
}
pub fn normalize_dashes(name: &str) -> CrateName {
Self(SmolStr::new(name.replace('-', "_")))
}
}
impl fmt::Display for CrateName {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}", self.0)
}
}
impl ops::Deref for CrateName {
type Target = str;
fn deref(&self) -> &str {
&*self.0
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct CrateDisplayName {
crate_name: CrateName,
canonical_name: String,
}
impl From<CrateName> for CrateDisplayName {
fn from(crate_name: CrateName) -> CrateDisplayName {
let canonical_name = crate_name.to_string();
CrateDisplayName { crate_name, canonical_name }
}
}
impl fmt::Display for CrateDisplayName {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}", self.crate_name)
}
}
impl ops::Deref for CrateDisplayName {
type Target = str;
fn deref(&self) -> &str {
&*self.crate_name
}
}
impl CrateDisplayName {
pub fn from_canonical_name(canonical_name: String) -> CrateDisplayName {
let crate_name = CrateName::normalize_dashes(&canonical_name);
CrateDisplayName { crate_name, canonical_name }
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct ProcMacroId(pub u32);
#[derive(Debug, Clone)]
pub struct ProcMacro {
pub name: SmolStr,
pub expander: Arc<dyn TokenExpander>,
}
impl Eq for ProcMacro {}
impl PartialEq for ProcMacro {
fn eq(&self, other: &ProcMacro) -> bool {
self.name == other.name && Arc::ptr_eq(&self.expander, &other.expander)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CrateData {
pub root_file_id: FileId,
pub edition: Edition,
pub display_name: Option<CrateDisplayName>,
pub cfg_options: CfgOptions,
pub env: Env,
pub dependencies: Vec<Dependency>,
pub proc_macro: Vec<ProcMacro>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Edition {
Edition2018,
Edition2015,
}
#[derive(Default, Debug, Clone, PartialEq, Eq)]
pub struct Env {
entries: FxHashMap<String, String>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Dependency {
pub crate_id: CrateId,
pub name: CrateName,
}
impl CrateGraph {
pub fn add_crate_root(
&mut self,
file_id: FileId,
edition: Edition,
display_name: Option<CrateDisplayName>,
cfg_options: CfgOptions,
env: Env,
proc_macro: Vec<(SmolStr, Arc<dyn tt::TokenExpander>)>,
) -> CrateId {
let proc_macro =
proc_macro.into_iter().map(|(name, it)| ProcMacro { name, expander: it }).collect();
let data = CrateData {
root_file_id: file_id,
edition,
display_name,
cfg_options,
env,
proc_macro,
dependencies: Vec::new(),
};
let crate_id = CrateId(self.arena.len() as u32);
let prev = self.arena.insert(crate_id, data);
assert!(prev.is_none());
crate_id
}
pub fn add_dep(
&mut self,
from: CrateId,
name: CrateName,
to: CrateId,
) -> Result<(), CyclicDependenciesError> {
if self.dfs_find(from, to, &mut FxHashSet::default()) {
return Err(CyclicDependenciesError {
from: (from, self[from].display_name.clone()),
to: (to, self[to].display_name.clone()),
});
}
self.arena.get_mut(&from).unwrap().add_dep(name, to);
Ok(())
}
pub fn is_empty(&self) -> bool {
self.arena.is_empty()
}
pub fn iter(&self) -> impl Iterator<Item = CrateId> + '_ {
self.arena.keys().copied()
}
pub fn transitive_deps(&self, of: CrateId) -> impl Iterator<Item = CrateId> + '_ {
let mut worklist = vec![of];
let mut deps = FxHashSet::default();
while let Some(krate) = worklist.pop() {
if !deps.insert(krate) {
continue;
}
worklist.extend(self[krate].dependencies.iter().map(|dep| dep.crate_id));
}
deps.remove(&of);
deps.into_iter()
}
pub fn crates_in_topological_order(&self) -> Vec<CrateId> {
let mut res = Vec::new();
let mut visited = FxHashSet::default();
for krate in self.arena.keys().copied() {
go(self, &mut visited, &mut res, krate);
}
return res;
fn go(
graph: &CrateGraph,
visited: &mut FxHashSet<CrateId>,
res: &mut Vec<CrateId>,
source: CrateId,
) {
if !visited.insert(source) {
return;
}
for dep in graph[source].dependencies.iter() {
go(graph, visited, res, dep.crate_id)
}
res.push(source)
}
}
pub fn crate_id_for_crate_root(&self, file_id: FileId) -> Option<CrateId> {
let (&crate_id, _) =
self.arena.iter().find(|(_crate_id, data)| data.root_file_id == file_id)?;
Some(crate_id)
}
pub fn extend(&mut self, other: CrateGraph) -> u32 {
let start = self.arena.len() as u32;
self.arena.extend(other.arena.into_iter().map(|(id, mut data)| {
let new_id = id.shift(start);
for dep in &mut data.dependencies {
dep.crate_id = dep.crate_id.shift(start);
}
(new_id, data)
}));
start
}
fn dfs_find(&self, target: CrateId, from: CrateId, visited: &mut FxHashSet<CrateId>) -> bool {
if !visited.insert(from) {
return false;
}
if target == from {
return true;
}
for dep in &self[from].dependencies {
let crate_id = dep.crate_id;
if self.dfs_find(target, crate_id, visited) {
return true;
}
}
false
}
pub fn patch_cfg_if(&mut self) -> bool {
let cfg_if = self.hacky_find_crate("cfg_if");
let std = self.hacky_find_crate("std");
match (cfg_if, std) {
(Some(cfg_if), Some(std)) => {
self.arena.get_mut(&cfg_if).unwrap().dependencies.clear();
self.arena
.get_mut(&std)
.unwrap()
.dependencies
.push(Dependency { crate_id: cfg_if, name: CrateName::new("cfg_if").unwrap() });
true
}
_ => false,
}
}
fn hacky_find_crate(&self, display_name: &str) -> Option<CrateId> {
self.iter().find(|it| self[*it].display_name.as_deref() == Some(display_name))
}
}
impl ops::Index<CrateId> for CrateGraph {
type Output = CrateData;
fn index(&self, crate_id: CrateId) -> &CrateData {
&self.arena[&crate_id]
}
}
impl CrateId {
pub fn shift(self, amount: u32) -> CrateId {
CrateId(self.0 + amount)
}
}
impl CrateData {
fn add_dep(&mut self, name: CrateName, crate_id: CrateId) {
self.dependencies.push(Dependency { name, crate_id })
}
}
impl FromStr for Edition {
type Err = ParseEditionError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let res = match s {
"2015" => Edition::Edition2015,
"2018" => Edition::Edition2018,
_ => return Err(ParseEditionError { invalid_input: s.to_string() }),
};
Ok(res)
}
}
impl fmt::Display for Edition {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(match self {
Edition::Edition2015 => "2015",
Edition::Edition2018 => "2018",
})
}
}
impl FromIterator<(String, String)> for Env {
fn from_iter<T: IntoIterator<Item = (String, String)>>(iter: T) -> Self {
Env { entries: FromIterator::from_iter(iter) }
}
}
impl Env {
pub fn set(&mut self, env: &str, value: String) {
self.entries.insert(env.to_owned(), value);
}
pub fn get(&self, env: &str) -> Option<String> {
self.entries.get(env).cloned()
}
}
#[derive(Debug)]
pub struct ParseEditionError {
invalid_input: String,
}
impl fmt::Display for ParseEditionError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "invalid edition: {:?}", self.invalid_input)
}
}
impl std::error::Error for ParseEditionError {}
#[derive(Debug)]
pub struct CyclicDependenciesError {
from: (CrateId, Option<CrateDisplayName>),
to: (CrateId, Option<CrateDisplayName>),
}
impl fmt::Display for CyclicDependenciesError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let render = |(id, name): &(CrateId, Option<CrateDisplayName>)| match name {
Some(it) => format!("{}({:?})", it, id),
None => format!("{:?}", id),
};
write!(f, "cyclic deps: {} -> {}", render(&self.from), render(&self.to))
}
}
#[cfg(test)]
mod tests {
use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
#[test]
fn detect_cyclic_dependency_indirect() {
let mut graph = CrateGraph::default();
let crate1 = graph.add_crate_root(
FileId(1u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
let crate2 = graph.add_crate_root(
FileId(2u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
let crate3 = graph.add_crate_root(
FileId(3u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
assert!(graph.add_dep(crate2, CrateName::new("crate3").unwrap(), crate3).is_ok());
assert!(graph.add_dep(crate3, CrateName::new("crate1").unwrap(), crate1).is_err());
}
#[test]
fn detect_cyclic_dependency_direct() {
let mut graph = CrateGraph::default();
let crate1 = graph.add_crate_root(
FileId(1u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
let crate2 = graph.add_crate_root(
FileId(2u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
assert!(graph.add_dep(crate2, CrateName::new("crate2").unwrap(), crate2).is_err());
}
#[test]
fn it_works() {
let mut graph = CrateGraph::default();
let crate1 = graph.add_crate_root(
FileId(1u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
let crate2 = graph.add_crate_root(
FileId(2u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
let crate3 = graph.add_crate_root(
FileId(3u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
assert!(graph.add_dep(crate2, CrateName::new("crate3").unwrap(), crate3).is_ok());
}
#[test]
fn dashes_are_normalized() {
let mut graph = CrateGraph::default();
let crate1 = graph.add_crate_root(
FileId(1u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
let crate2 = graph.add_crate_root(
FileId(2u32),
Edition2018,
None,
CfgOptions::default(),
Env::default(),
Default::default(),
);
assert!(graph
.add_dep(crate1, CrateName::normalize_dashes("crate-name-with-dashes"), crate2)
.is_ok());
assert_eq!(
graph[crate1].dependencies,
vec![Dependency {
crate_id: crate2,
name: CrateName::new("crate_name_with_dashes").unwrap()
}]
);
}
}