use std::collections::BTreeMap;
use purrdf_lex::allocation::{Memory, OrderedTable};
use purrdf_lex::walk::WorkList;
#[cfg(doc)]
use crate::budget::Budget;
use crate::error::{LoadError, LoadErrorKind, Origin, TargetProblem, TreeError};
use crate::manifest::{self, Manifest, PackageDecl};
use crate::members::members;
use crate::meter::{ItemAdmission, Meter, push_item_work};
use crate::path::{RelPath, SourceAuthorityId};
use crate::target::Package;
use crate::tree::{EntryKind, Tree};
pub(crate) struct Found {
pub(crate) package: Package,
pub(crate) declared: PackageDecl,
pub(crate) manifest: Manifest,
}
struct Walk<'a> {
tree: &'a dyn Tree,
meter: &'a Meter,
found: BTreeMap<RelPath, Found>,
names: OrderedTable<(SourceAuthorityId, String), RelPath>,
name_bytes: usize,
}
enum Step {
Dir(RelPath, usize),
Link(RelPath),
}
pub(crate) struct Discovered {
pub(crate) packages: Vec<Found>,
}
fn skipped(name: &str) -> bool {
name == "target" || name.starts_with('.')
}
impl<'a> Walk<'a> {
fn new(tree: &'a dyn Tree, meter: &'a Meter, at: &RelPath) -> Result<Self, LoadError> {
meter.items(
size_of::<OrderedTable<(SourceAuthorityId, String), RelPath>>(),
at,
None,
)?;
Ok(Self {
tree,
meter,
found: BTreeMap::new(),
names: OrderedTable::default(),
name_bytes: 0,
})
}
fn finish(self) -> Discovered {
Discovered {
packages: self.found.into_values().collect(),
}
}
fn remember_name(&mut self, name: &str, path: &RelPath) -> Result<(), LoadError> {
let mut admission = ItemAdmission::resume(self.meter, path, self.name_bytes);
let result = {
let mut memory = Memory::resume(&mut admission, self.name_bytes);
let mut owned = String::new();
let result = memory.push_str(&mut owned, name).and_then(|()| {
self.names
.insert((path.authority(), owned), path.clone(), &mut memory)
});
self.name_bytes = memory.admitted_bytes();
result
};
if result.map_err(|error| admission.error(error))?.is_some() {
return Err(LoadError::new(
path,
None,
LoadErrorKind::Internal {
what: "a source-local package name changed during insertion".to_owned(),
},
));
}
Ok(())
}
fn root(&mut self, root: &RelPath) -> Result<(), LoadError> {
let origin = Origin::Discovery;
match self
.tree
.entry(root)
.map_err(|error| LoadError::tree(root, None, &origin, error))?
{
Some(EntryKind::Dir) => self.visit(root),
Some(EntryKind::Symlink) => {
Err(LoadError::new(root, None, LoadErrorKind::DirSymlink).reached_by(&origin))
}
Some(EntryKind::File | EntryKind::Other) => Err(LoadError::tree(
root,
None,
&origin,
TreeError::NotRegular {
path: root.to_string(),
},
)),
None => Err(LoadError::tree(
root,
None,
&origin,
TreeError::NotFound {
path: root.to_string(),
},
)),
}
}
fn manifest_path(dir: &RelPath) -> Result<RelPath, LoadError> {
let origin = Origin::Discovery;
dir.join("Cargo.toml")
.map_err(|error| LoadError::tree(dir, None, &origin, error.into()))
}
fn read_manifest(&self, path: &RelPath) -> Result<Option<Manifest>, LoadError> {
let origin = Origin::Discovery;
let present = self
.tree
.entry(path)
.map_err(|error| LoadError::tree(path, None, &origin, error))?;
if present.is_none() {
return Ok(None);
}
let text = self
.tree
.read(path, self.meter.options().max_file_bytes)
.map_err(|error| LoadError::tree(path, None, &origin, error))?;
self.meter
.read(path, &text)
.map_err(|error| error.reached_by(&origin))?;
manifest::parse(&text).map(Some).map_err(|problem| {
let origin = problem
.key
.map_or(Origin::Discovery, |key| Origin::ManifestKey { key });
LoadError::new(
path,
None,
LoadErrorKind::Manifest {
message: problem.message,
source: problem.source,
},
)
.reached_by(&origin)
})
}
fn manifest(&mut self, dir: &RelPath) -> Result<bool, LoadError> {
let path = Self::manifest_path(dir)?;
let Some(parsed) = self.read_manifest(&path)? else {
return Ok(true);
};
self.retain_manifest(dir, path, parsed)
}
fn retain_manifest(
&mut self,
dir: &RelPath,
path: RelPath,
mut parsed: Manifest,
) -> Result<bool, LoadError> {
let descend = parsed.package.is_none() || parsed.has_workspace;
if let Some(package) = parsed.package.take() {
match self.names.get_by(|(authority, name)| {
(path.authority(), package.name.as_str()).cmp(&(*authority, name.as_str()))
}) {
Some(other) if *other != path => {
return Err(LoadError::new(
&path,
None,
LoadErrorKind::Target(Box::new(TargetProblem::DuplicatePackage {
name: package.name.clone(),
with: other.clone(),
})),
)
.reached_by(&Origin::ManifestKey {
key: "package.name".to_owned(),
}));
}
Some(_) => {}
None => {
self.remember_name(&package.name, &path)?;
}
}
let entry = Found {
package: Package {
name: package.name.clone(),
manifest: path.clone(),
dir: dir.clone(),
},
declared: package,
manifest: parsed,
};
self.found.insert(path, entry);
}
Ok(descend)
}
fn visit(&mut self, root: &RelPath) -> Result<(), LoadError> {
let origin = Origin::Discovery;
let mut stack = WorkList::<_, 8>::new();
push_item_work(
&mut stack,
Step::Dir(root.clone(), 0),
self.meter,
root,
None,
)?;
while let Some(step) = stack.pop() {
let (dir, depth) = match step {
Step::Dir(dir, depth) => (dir, depth),
Step::Link(path) => {
self.symlink(&path)?;
continue;
}
};
self.meter.directory(depth, &dir)?;
if !self.manifest(&dir)? {
continue;
}
let entries = self
.tree
.list(&dir)
.map_err(|error| LoadError::tree(&dir, None, &origin, error))?;
let mut steps = Vec::new();
for entry in entries {
if skipped(&entry.name) {
continue;
}
let child = dir
.join(&entry.name)
.map_err(|error| LoadError::tree(&dir, None, &origin, error.into()))?;
match entry.kind {
EntryKind::Dir => steps.push(Step::Dir(child, depth + 1)),
EntryKind::Symlink => steps.push(Step::Link(child)),
EntryKind::File | EntryKind::Other => {}
}
}
for step in steps.into_iter().rev() {
push_item_work(&mut stack, step, self.meter, &dir, None)?;
}
}
Ok(())
}
fn symlink(&self, path: &RelPath) -> Result<(), LoadError> {
let origin = Origin::Discovery;
let fail = |error| LoadError::tree(path, None, &origin, error);
match self.tree.read(path, 0) {
Ok(_) | Err(TreeError::TooLarge { .. }) => Ok(()),
Err(TreeError::NotRegular { .. }) => {
let parent = path.join("..").map_err(|error| fail(error.into()))?;
match self.tree.entry(&parent).map_err(fail)? {
Some(EntryKind::Dir) => {
Err(LoadError::new(path, None, LoadErrorKind::DirSymlink)
.reached_by(&origin))
}
Some(EntryKind::File | EntryKind::Symlink | EntryKind::Other) | None => {
Err(fail(TreeError::NotRegular {
path: path.to_string(),
}))
}
}
}
Err(error) => Err(fail(error)),
}
}
}
fn missing_selection(path: &RelPath, message: &str) -> LoadError {
LoadError::new(
path,
None,
LoadErrorKind::Manifest {
message: message.to_owned(),
source: None,
},
)
.reached_by(&Origin::Discovery)
}
pub(crate) fn workspace_members(
tree: &dyn Tree,
root: &RelPath,
meter: &Meter,
) -> Result<Discovered, LoadError> {
let root = crate::root::directory(tree, root)?;
let path = Walk::manifest_path(&root)?;
let mut walk = Walk::new(tree, meter, &path)?;
let root_manifest = walk
.read_manifest(&path)?
.filter(|manifest| manifest.has_workspace || manifest.package.is_some())
.ok_or_else(|| {
missing_selection(&path, "select a Cargo.toml with a workspace or package")
})?;
if root_manifest.has_workspace {
for member in members(tree, meter, &root, &path, &root_manifest)? {
if member == root {
continue;
}
let member = crate::root::directory(tree, &member)?;
let path = Walk::manifest_path(&member)?;
let parsed = walk
.read_manifest(&path)?
.filter(|manifest| manifest.package.is_some())
.ok_or_else(|| {
missing_selection(&path, "workspace member needs a package manifest")
})?;
walk.retain_manifest(&member, path, parsed)?;
}
}
walk.retain_manifest(&root, path, root_manifest)?;
Ok(walk.finish())
}
pub(crate) fn discover(
tree: &dyn Tree,
roots: &[RelPath],
meter: &Meter,
) -> Result<Discovered, LoadError> {
let mut walk = Walk::new(tree, meter, &RelPath::root())?;
for root in roots {
walk.root(root)?;
}
Ok(walk.finish())
}
pub(crate) fn single(
tree: &dyn Tree,
manifest: &RelPath,
meter: &Meter,
) -> Result<Discovered, LoadError> {
let dir = manifest
.parent()
.ok_or_else(|| LoadError::new(manifest, None, LoadErrorKind::NoRoots))?;
if manifest.file_name() != Some("Cargo.toml") {
return Err(LoadError::new(
manifest,
None,
LoadErrorKind::Internal {
what: "select an actual Cargo.toml manifest".into(),
},
));
}
let mut walk = Walk::new(tree, meter, manifest)?;
match tree
.entry(&dir)
.map_err(|error| LoadError::tree(&dir, None, &Origin::Discovery, error))?
{
Some(EntryKind::Dir) => {}
Some(EntryKind::Symlink) => {
return Err(LoadError::new(&dir, None, LoadErrorKind::DirSymlink)
.reached_by(&Origin::Discovery));
}
_ => return Err(LoadError::new(&dir, None, LoadErrorKind::NoRoots)),
}
walk.manifest(&dir)?;
if walk.found.len() != 1 {
return Err(LoadError::new(
manifest,
None,
LoadErrorKind::Internal {
what: "selected manifest has no package identity".into(),
},
));
}
Ok(walk.finish())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Budget, LoadOptions, MemoryTree};
fn populate_names(limit: usize) -> Result<usize, LoadError> {
let tree = MemoryTree::default();
let meter = Meter::new(&LoadOptions {
max_item_bytes: limit,
..LoadOptions::default()
});
let mut walk = Walk {
tree: &tree,
meter: &meter,
found: BTreeMap::new(),
names: OrderedTable::default(),
name_bytes: 0,
};
let path = RelPath::new("Cargo.toml")
.expect("manifest")
.in_source(SourceAuthorityId(1));
for index in 0..40 {
walk.remember_name(&format!("package-{index:02}"), &path)?;
}
let spent = meter.usage().item_bytes;
for index in 0..40 {
let name = format!("package-{index:02}");
assert_eq!(
walk.names.get_by(|(authority, stored)| {
(path.authority(), name.as_str()).cmp(&(*authority, stored.as_str()))
}),
Some(&path)
);
}
assert_eq!(meter.usage().item_bytes, spent);
Ok(spent)
}
#[test]
fn native_discovery_names_resume_retained_storage_and_refuse_the_original_grant() {
let spent = populate_names(LoadOptions::default().max_item_bytes).expect("populated");
assert_eq!(populate_names(spent).expect("exact allowance"), spent);
let error = populate_names(spent - 1).expect_err("one byte too little");
assert_eq!(error.file.authority(), SourceAuthorityId(1));
assert!(matches!(
error.kind,
LoadErrorKind::Budget {
budget: Budget::ItemBytes,
..
}
));
}
}