Stack overflow on circular dependency

[thibault-martinez]

Problem

cargo check --release crashes with stack overflow.

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

Steps

1. git clone https://github.com/thibault-martinez/bee.git
2. cd bee/
3. git checkout cargo-stack-overflow
4. cargo check --release

Notes

cargo 1.49.0 (d00d64df9 2020-12-05)

There is a circular dependency bee-tangle->bee-snapshot->bee-ledger->bee-tangle.

[alexcrichton]

Thanks for the report! This is a bug in the implementation we have that checks for cycles from the resolver --

cargo/src/cargo/core/resolver/mod.rs

Lines 1003 to 1064 in a73e5b7

	fn check_cycles(resolve: &Resolve) -> CargoResult<()> {
	// Sort packages to produce user friendly deterministic errors.
	let mut all_packages: Vec<_> = resolve.iter().collect();
	all_packages.sort_unstable();
	let mut checked = HashSet::new();
	let mut path = Vec::new();
	let mut visited = HashSet::new();
	for pkg in all_packages {
	if !checked.contains(&pkg) {
	visit(resolve, pkg, &mut visited, &mut path, &mut checked)?
	}
	}
	return Ok(());
	fn visit(
	resolve: &Resolve,
	id: PackageId,
	visited: &mut HashSet<PackageId>,
	path: &mut Vec<PackageId>,
	checked: &mut HashSet<PackageId>,
	) -> CargoResult<()> {
	path.push(id);
	// See if we visited ourselves
	if !visited.insert(id) {
	anyhow::bail!(
	"cyclic package dependency: package `{}` depends on itself. Cycle:\n{}",
	id,
	errors::describe_path(&path.iter().rev().collect::<Vec<_>>()),
	);
	}
	// If we've already checked this node no need to recurse again as we'll
	// just conclude the same thing as last time, so we only execute the
	// recursive step if we successfully insert into `checked`.
	//
	// Note that if we hit an intransitive dependency then we clear out the
	// visitation list as we can't induce a cycle through transitive
	// dependencies.
	if checked.insert(id) {
	let mut empty_set = HashSet::new();
	let mut empty_vec = Vec::new();
	for (dep, listings) in resolve.deps_not_replaced(id) {
	let is_transitive = listings.iter().any(|d| d.is_transitive());
	let (visited, path) = if is_transitive {
	(&mut *visited, &mut *path)
	} else {
	(&mut empty_set, &mut empty_vec)
	};
	visit(resolve, dep, visited, path, checked)?;
	if let Some(id) = resolve.replacement(dep) {
	visit(resolve, id, visited, path, checked)?;
	}
	}
	}
	// Ok, we're done, no longer visiting our node any more
	path.pop();
	visited.remove(&id);
	Ok(())
	}
	}

-- and has been there for a very long time. Turns out your project is structured just right (and named just right b/c we sort things) to trigger this!

I'll take a look at how we can fix our cycle detection.