cached_count_paths recurses once per node:
successors(&start)
.into_iter()
.map(|successor| cached_count_paths(successor, successors, success, cache))
.sum()so the recursion depth is the length of the longest path, and a graph only has to be deep to bring the process down:
const N: usize = 200_000;
count_paths(0usize, |&n| (n + 1 < N).then_some(n + 1), |&n| n == N - 1);
// thread has overflowed its stack
That graph is a single chain. It has exactly one path and no loop in it anywhere.
The documentation says:
There must be no loops in the graph, or the function will overflow its stack.
which reads as a promise that a loop-free graph is safe. It is not — depth is enough on its own, and 200 000 is not a large number of nodes. This is a stack overflow rather than a panic, so it aborts the process and cannot be caught.
This is the same shape of problem as #795, which was fixed for strongly_connected_components and topological_sort in b6e418f and f907410.
I have a change and can open a PR: walk an explicit stack instead of recursing, so depth is bounded by memory.
One decision I would rather agree with you here than bury in a diff. Once the recursion is gone, the documented behaviour on a looped graph has to change, because there is no stack left to overflow — a loop would instead grow the working set until memory ran out, which is a worse failure than the one documented today. I would rather detect it: holding the nodes in an FxIndexMap<T, Option<usize>> and having the stack refer to them by index costs nothing extra (the lookup already happens, and it also avoids requiring T: Clone), and a node re-entered while its own count is still unknown is exactly a loop. That turns the current crash into a panic with a message saying the graph has a loop.
That would mean a # Panics section on count_paths and a documented behaviour change from "overflows the stack" to "panics". If you would rather it stayed a crash, or would rather it returned a Result, say so and I will do that instead.
cached_count_pathsrecurses once per node:so the recursion depth is the length of the longest path, and a graph only has to be deep to bring the process down:
That graph is a single chain. It has exactly one path and no loop in it anywhere.
The documentation says:
which reads as a promise that a loop-free graph is safe. It is not — depth is enough on its own, and 200 000 is not a large number of nodes. This is a stack overflow rather than a panic, so it aborts the process and cannot be caught.
This is the same shape of problem as #795, which was fixed for
strongly_connected_componentsandtopological_sortin b6e418f and f907410.I have a change and can open a PR: walk an explicit stack instead of recursing, so depth is bounded by memory.
One decision I would rather agree with you here than bury in a diff. Once the recursion is gone, the documented behaviour on a looped graph has to change, because there is no stack left to overflow — a loop would instead grow the working set until memory ran out, which is a worse failure than the one documented today. I would rather detect it: holding the nodes in an
FxIndexMap<T, Option<usize>>and having the stack refer to them by index costs nothing extra (the lookup already happens, and it also avoids requiringT: Clone), and a node re-entered while its own count is still unknown is exactly a loop. That turns the current crash into a panic with a message saying the graph has a loop.That would mean a
# Panicssection oncount_pathsand a documented behaviour change from "overflows the stack" to "panics". If you would rather it stayed a crash, or would rather it returned aResult, say so and I will do that instead.