refactor: add WaitGroup for waiting for a dynamic set of tasks by katrinafyi · Pull Request #2046 · lycheeverse/lychee

katrinafyi · 2026-02-14T03:51:28Z

This is a small step towards recursion. It will enable waiting for a dynamic number of tasks which can spawn other tasks, which allows for correct and deadlock-free termination in the presence of (eventual) recursion.

I think recursion is not an astoundingly difficult feature but, because lychee is async and stream, it needs the combination of a few parts which might be tricky to get right. This is one of those parts. In fact, I had two different deadlock bugs while working on this PR before reaching the final implementation. If this was all done in one big recursion PR, then I think these bugs would be a lot harder to find and fix.

The old implementation in #1603 used Arc<AtomicUsize> to implement this requirement. This new PR uses a RAII-based guard value to represent tasks, which should make it much easier to write correct code - it's all handled by the borrow checker and Drop, so it's impossible to forget to adjust the counter.

In terms of testing, changes the check.rs command to rely on WaitGroup for termination. You can read about this in the comments. This means that every run of lychee goes through the WaitGroup code and acts as a test for WaitGroup. There is a risk that if it is buggy, the impacts would be big. However, I think the unit tests are big enough that they're a decent exercise of the WaitGroup. My second deadlock bug was found by make test.

You can also see the docs at https://waitgroup.lychee-docs-katrinafyi.pages.dev/lychee_lib/waiter/

Related work:

https://docs.rs/waitgroup/latest/waitgroup/ - seems to work
https://docs.rs/atomic-waitgroup/latest/atomic_waitgroup/index.html - doesn't support recursive.
https://docs.rs/wgp/latest/wgp/ - seems to work, but uses unsafe and has had correctness bug.
https://docs.rs/crossbeam-utils/latest/crossbeam_utils/sync/struct.WaitGroup.html, https://docs.rs/omango/latest/omango/wg/struct.WaitGroup.html but this is for threading rather than async.
lots of things for waiting on a set of futures, but we can't use that here because we don't have individual features for each task https://docs.rs/tokio-util/latest/tokio_util/task/task_tracker/struct.TaskTracker.html, https://docs.rs/tokio/1.49.0/tokio/task/join_set/struct.JoinSet.html#method.join_all, https://docs.rs/futures/latest/futures/stream/struct.FuturesUnordered.html, https://docs.rs/spawn_groups/latest/spawn_groups/struct.SpawnGroup.html

threaded synchronisation primitives (like std::sync::Mutex). if we were unlucky, these can block the tokio runtime. replace std::sync::Arc with a system based on (an even thinner wrapper around) tokio::mspc::sync::channel.

mre

Lgtm.

@thomas-zahner, any thoughts before we merge this?

thomas-zahner · 2026-02-17T13:02:51Z

Very cool PR! I don't see any problems with it.

@katrinafyi Could you add a test to waiter.rs to to test if recursion would really work that way? So that the unused part (// unused for now, but will be used for recursion eventually.) is covered and tested already. This would be great documentation and help me (and others) understand how this is used in a simpler scenario without lychee's additional complexity.

i thought quicksort would be easy...

the Infallible name only really makes sense for Result<T, Infallible>

katrinafyi · 2026-02-18T01:51:45Z

@thomas-zahner That's a really interesting idea. I've added a (hopefully) simple example which you can see here: https://github.com/lycheeverse/lychee/compare/74046a9..b27a34f

into a count

thomas-zahner

@katrinafyi Thank you, that's very cool! This helps my understanding quite a bit.

thomas-zahner · 2026-02-18T08:10:57Z

+/// The given `waiter` will be used to detect when the work has finished and it will
+/// close the channels. Additionally, `waiter` can be omitted to show that without
+/// the [`WaitGroup`], the tasks would not terminate.
+#[allow(dead_code)]


Either move into mod test or annotate with #[cfg(test)], this should resolve the #[allow(dead_code)], right?

Hmm I put it outside of mod tests because I wanted it to be included in the docs.

I tried a few things and it's a bit tricky. We need compiling to work (1) normally, (2) in docs, and (3) in tests.

#[cfg(any(test, doc))] on the examples: dev-dependencies is not available in doc, so tokio-stream has to be in dependencies. but then, it's flagged as an unused crate in normal compilation.

putting inside mod test and making test module #[cfg(any(test, doc))] has the same problems

Do you have thoughts or other suggestions?

Hmm, I personally would really like to not have additional dependencies or code that is tests and documentation but possibly ends up in the final binary. (though in reality it should be optimised away)

I think doc tests would solve the problem. They are tested and great for documentation. It would be possible to highlight only the interesting bits of the code. It even seems possible to use dev dependencies in there!

I just moved it into doctest and it looks great and works well, thanks for the suggestion! I should try and use doctests more often I think.

Awesome 🚀 yeah they are quite powerful and useful. Thanks for addressing my concerns.

I have to admit that I'm confused by #[cfg(all(test, not(doctest)))]. Why is it not(doctest)? I see that it seems like the only working version where clippy doesn't complain. But do you understand why?

I admit I didn't try other options very rigorously. But the thinking is that the unused crate warning appears when the crate is included but not used. Dev dependencies are enabled in test, and in doctest they get used.

So, test and not doctest is precisely the case where it's included but not used. That's the idea at least.

ETA: The not doctest is just adding a bit more precision. The line suppresses unused crate warning but in doctest, the crate is used so it should be unnecessary to suppress the warning.

Aah, yes I see that makes sense. Thanks for the great PR!

Co-authored-by: Thomas Zahner <thomas.zahner@protonmail.ch>

katrinafyi · 2026-02-23T11:59:50Z

idk why that closed

katrinafyi added 13 commits February 13, 2026 16:50

feat: WaitGuard for waiting on a dynamically-determined group of tasks

c6eff7f

race doesnt work

eadf9af

x

a210d77

fix deadlock

1598c8c

fmt

fd2f5d3

i think the deadlock was due to std::sync::Arc internally using

47921b0

threaded synchronisation primitives (like std::sync::Mutex). if we were unlucky, these can block the tokio runtime. replace std::sync::Arc with a system based on (an even thinner wrapper around) tokio::mspc::sync::channel.

fmt

1df0a87

lint

99d7fa1

l2

a5b9816

infallible

79016f4

comment

022b9e0

take_until

9623607

cmt

dc6966c

mre reviewed Feb 16, 2026

View reviewed changes

Comment thread lychee-bin/src/commands/check.rs

Merge branch 'master' into waitgroup

74046a9

thomas-zahner reviewed Feb 17, 2026

View reviewed changes

Comment thread lychee-lib/src/waiter.rs

mre approved these changes Feb 17, 2026

View reviewed changes

katrinafyi added 5 commits February 18, 2026 02:13

working on example...... [no ci]

6ad9092

i thought quicksort would be easy...

fib

c53e913

use Never instead of Infallible

5792470

the Infallible name only really makes sense for Result<T, Infallible>

fix wawrnings

b27a34f

considered

10f3c74

incr channel can be bounded to 1, because it gets polled immediately

0439d47

into a count

thomas-zahner reviewed Feb 18, 2026

View reviewed changes

katrinafyi and others added 3 commits February 18, 2026 20:02

whitespace

2560b34

Co-authored-by: Thomas Zahner <thomas.zahner@protonmail.ch>

move example into doctest

87c19c9

use tokio_stream as _ when not doctest

7718cc8

katrinafyi closed this Feb 23, 2026

katrinafyi reopened this Feb 23, 2026

Merge branch 'master' into waitgroup

fc086fe

thomas-zahner merged commit 0f901b4 into lycheeverse:master Feb 25, 2026
7 checks passed

mre mentioned this pull request Feb 25, 2026

chore: release v0.24.0 #2048

Merged

mre mentioned this pull request Apr 4, 2026

Add recursive option #78

Open

Uh oh!

Conversation

katrinafyi commented Feb 14, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

mre left a comment

Choose a reason for hiding this comment

Uh oh!

thomas-zahner commented Feb 17, 2026

Uh oh!

katrinafyi commented Feb 18, 2026

Uh oh!

thomas-zahner left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

thomas-zahner Feb 18, 2026

Choose a reason for hiding this comment

Uh oh!

katrinafyi Feb 18, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

thomas-zahner Feb 23, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

katrinafyi Feb 23, 2026

Choose a reason for hiding this comment

Uh oh!

thomas-zahner Feb 25, 2026

Choose a reason for hiding this comment

Uh oh!

thomas-zahner Feb 25, 2026

Choose a reason for hiding this comment

Uh oh!

katrinafyi Feb 25, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

thomas-zahner Feb 25, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

katrinafyi commented Feb 23, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

katrinafyi commented Feb 14, 2026 •

edited

Loading

katrinafyi Feb 18, 2026 •

edited

Loading

thomas-zahner Feb 23, 2026 •

edited

Loading

katrinafyi Feb 25, 2026 •

edited

Loading