Skip to main content

tor_rtmock/
task.rs

1//! Executor for running tests with mocked environment
2//!
3//! See [`MockExecutor`]
4
5use std::any::Any;
6use std::cell::Cell;
7use std::collections::VecDeque;
8use std::fmt::{self, Debug, Display};
9use std::future::Future;
10use std::io::{self, Write as _};
11use std::iter;
12use std::panic::{AssertUnwindSafe, catch_unwind, panic_any};
13use std::pin::{Pin, pin};
14use std::sync::{Arc, Mutex, MutexGuard, Weak};
15use std::task::{Context, Poll, RawWaker, RawWakerVTable, Waker};
16
17use futures::FutureExt as _;
18use futures::pin_mut;
19use futures::task::{FutureObj, Spawn, SpawnError};
20
21use assert_matches::assert_matches;
22use educe::Educe;
23use itertools::Either::{self, *};
24use itertools::{chain, izip};
25use slotmap_careful::DenseSlotMap;
26use std::backtrace::Backtrace;
27use strum::EnumIter;
28
29// NB: when using traced_test, the trace! and error! output here is generally suppressed
30// in tests of other crates.  To see it, you can write something like this
31// (in the dev-dependencies of the crate whose tests you're running):
32//    tracing-test = { version = "0.2.4", features = ["no-env-filter"] }
33use tracing::{error, trace};
34
35use oneshot_fused_workaround::{self as oneshot, Canceled};
36use tor_error::error_report;
37use tor_rtcompat::join_set::FuturesJoinSet;
38use tor_rtcompat::{Blocking, JoinSetProvider, ToplevelBlockOn};
39
40use Poll::*;
41use TaskState::*;
42
43/// Type-erased future, one for each of our (normal) tasks
44type TaskFuture = FutureObj<'static, ()>;
45
46/// Future for the argument to `block_on`, which is handled specially
47type MainFuture<'m> = Pin<&'m mut dyn Future<Output = ()>>;
48
49//---------- principal data structures ----------
50
51/// Executor for running tests with mocked environment
52///
53/// For test cases which don't actually wait for anything in the real world.
54///
55/// This is the executor.
56/// It implements [`Spawn`] and [`ToplevelBlockOn`]
57///
58/// It will usually be used as part of a `MockRuntime`.
59///
60/// To run futures, call [`ToplevelBlockOn::block_on`]
61///
62/// # Restricted environment
63///
64/// Tests run with this executor must not attempt to block
65/// on anything "outside":
66/// every future that anything awaits must (eventually) be woken directly
67/// *by some other task* in the same test case.
68///
69/// (By directly we mean that the [`Waker::wake`] call is made
70/// by that waking future, before that future itself awaits anything.)
71///
72/// # Panics
73///
74/// The executor will panic
75/// if the toplevel future (passed to `block_on`)
76/// doesn't complete (without externally blocking),
77/// but instead waits for something.
78///
79/// The executor will malfunction or panic if reentered.
80/// (Eg, if `block_on` is reentered.)
81#[derive(Clone, Default, Educe)]
82#[educe(Debug)]
83pub struct MockExecutor {
84    /// Mutable state
85    #[educe(Debug(ignore))]
86    shared: Arc<Shared>,
87}
88
89/// Shared state and ancillary information
90///
91/// This is always within an `Arc`.
92#[derive(Default)]
93struct Shared {
94    /// Shared state
95    data: Mutex<Data>,
96    /// Condition variable for thread scheduling
97    ///
98    /// Signaled when [`Data.thread_to_run`](struct.Data.html#structfield.thread_to_run)
99    /// is modified.
100    thread_condvar: std::sync::Condvar,
101}
102
103/// Task id, module to hide `Ti` alias
104mod task_id {
105    slotmap_careful::new_key_type! {
106        /// Task ID, usually called `TaskId`
107        ///
108        /// Short name in special `task_id` module so that [`Debug`] is nice
109        pub(super) struct Ti;
110    }
111}
112use task_id::Ti as TaskId;
113
114/// Executor's state
115///
116/// ### Task state machine
117///
118/// A task is created in `tasks`, `Awake`, so also in `awake`.
119///
120/// When we poll it, we take it out of `awake` and set it to `Asleep`,
121/// and then call `poll()`.
122/// Any time after that, it can be made `Awake` again (and put back onto `awake`)
123/// by the waker ([`ActualWaker`], wrapped in [`Waker`]).
124///
125/// The task's future is of course also present here in this data structure.
126/// However, during poll we must release the lock,
127/// so we cannot borrow the future from `Data`.
128/// Instead, we move it out.  So `Task.fut` is an `Option`.
129///
130/// ### "Main" task - the argument to `block_on`
131///
132/// The signature of `BlockOn::block_on` accepts a non-`'static` future
133/// (and a non-`Send`/`Sync` one).
134///
135/// So we cannot store that future in `Data` because `Data` is `'static`.
136/// Instead, this main task future is passed as an argument down the call stack.
137/// In the data structure we simply store a placeholder, `TaskFutureInfo::Main`.
138#[derive(Educe, derive_more::Debug)]
139#[educe(Default)]
140struct Data {
141    /// Tasks
142    ///
143    /// Includes tasks spawned with `spawn`,
144    /// and also the future passed to `block_on`.
145    #[debug("{:?}", DebugTasks(self, || tasks.keys()))]
146    tasks: DenseSlotMap<TaskId, Task>,
147
148    /// `awake` lists precisely: tasks that are `Awake`, plus maybe stale `TaskId`s
149    ///
150    /// Tasks are pushed onto the *back* when woken,
151    /// so back is the most recently woken.
152    #[debug("{:?}", DebugTasks(self, || awake.iter().cloned()))]
153    awake: VecDeque<TaskId>,
154
155    /// If a future from `progress_until_stalled` exists
156    progressing_until_stalled: Option<ProgressingUntilStalled>,
157
158    /// Scheduling policy
159    scheduling: SchedulingPolicy,
160
161    /// (Sub)thread we want to run now
162    ///
163    /// At any one time only one thread is meant to be running.
164    /// Other threads are blocked in condvar wait, waiting for this to change.
165    ///
166    /// **Modified only** within
167    /// [`thread_context_switch_send_instruction_to_run`](Shared::thread_context_switch_send_instruction_to_run),
168    /// which takes responsibility for preserving the following **invariants**:
169    ///
170    ///  1. no-one but the named thread is allowed to modify this field.
171    ///  2. after modifying this field, signal `thread_condvar`
172    #[educe(Default(expression = "ThreadDescriptor::Executor"))]
173    thread_to_run: ThreadDescriptor,
174}
175
176/// How we should schedule?
177#[derive(Debug, Clone, Default, EnumIter)]
178#[non_exhaustive]
179pub enum SchedulingPolicy {
180    /// Task *most* recently woken is run
181    ///
182    /// This is the default.
183    ///
184    /// It will expose starvation bugs if a task never sleeps.
185    /// (Which is a good thing in tests.)
186    #[default]
187    Stack,
188    /// Task *least* recently woken is run.
189    Queue,
190}
191
192/// Record of a single task
193///
194/// Tracks a spawned task, or the main task (the argument to `block_on`).
195///
196/// Stored in [`Data`]`.tasks`.
197struct Task {
198    /// For debugging output
199    desc: String,
200    /// Has this been woken via a waker?  (And is it in `Data.awake`?)
201    ///
202    /// **Set to `Awake` only by [`Task::set_awake`]**,
203    /// preserving the invariant that
204    /// every `Awake` task is in [`Data.awake`](struct.Data.html#structfield.awake).
205    state: TaskState,
206    /// The actual future (or a placeholder for it)
207    ///
208    /// May be `None` briefly in the executor main loop, because we've
209    /// temporarily moved it out so we can poll it,
210    /// or if this is a Subthread task which is currently running sync code
211    /// (in which case we're blocked in the executor waiting to be
212    /// woken up by [`thread_context_switch`](Shared::thread_context_switch).
213    ///
214    /// Note that the `None` can be observed outside the main loop, because
215    /// the main loop unlocks while it polls, so other (non-main-loop) code
216    /// might see it.
217    fut: Option<TaskFutureInfo>,
218}
219
220/// A future as stored in our record of a [`Task`]
221#[derive(Educe)]
222#[educe(Debug)]
223enum TaskFutureInfo {
224    /// The [`Future`].  All is normal.
225    Normal(#[educe(Debug(ignore))] TaskFuture),
226    /// The future isn't here because this task is the main future for `block_on`
227    Main,
228    /// This task is actually a [`Subthread`](MockExecutor::subthread_spawn)
229    ///
230    /// Instead of polling it, we'll switch to it with
231    /// [`thread_context_switch`](Shared::thread_context_switch).
232    Subthread,
233}
234
235/// State of a task - do we think it needs to be polled?
236///
237/// Stored in [`Task`]`.state`.
238#[derive(Debug)]
239enum TaskState {
240    /// Awake - needs to be polled
241    ///
242    /// Established by [`waker.wake()`](Waker::wake)
243    Awake,
244    /// Asleep - does *not* need to be polled
245    ///
246    /// Established each time just before we call the future's [`poll`](Future::poll)
247    Asleep(Vec<SleepLocation>),
248}
249
250/// Actual implementor of `Wake` for use in a `Waker`
251///
252/// Futures (eg, channels from [`futures`]) will use this to wake a task
253/// when it should be polled.
254///
255/// This type must not be `Cloned` with the `Data` lock held.
256/// Consequently, a `Waker` mustn't either.
257struct ActualWaker {
258    /// Executor state
259    ///
260    /// The Waker mustn't to hold a strong reference to the executor,
261    /// since typically a task holds a future that holds a Waker,
262    /// and the executor holds the task - so that would be a cycle.
263    data: Weak<Shared>,
264
265    /// Which task this is
266    id: TaskId,
267}
268
269/// State used for an in-progress call to
270/// [`progress_until_stalled`][`MockExecutor::progress_until_stalled`]
271///
272/// If present in [`Data`], an (async) call to `progress_until_stalled`
273/// is in progress.
274///
275/// The future from `progress_until_stalled`, [`ProgressUntilStalledFuture`]
276/// is a normal-ish future.
277/// It can be polled in the normal way.
278/// When it is polled, it looks here, in `finished`, to see if it's `Ready`.
279///
280/// The future is made ready, and woken (via `waker`),
281/// by bespoke code in the task executor loop.
282///
283/// When `ProgressUntilStalledFuture` (maybe completes and) is dropped,
284/// its `Drop` impl is used to remove this from `Data.progressing_until_stalled`.
285#[derive(Debug)]
286struct ProgressingUntilStalled {
287    /// Have we, in fact, stalled?
288    ///
289    /// Made `Ready` by special code in the executor loop
290    finished: Poll<()>,
291
292    /// Waker
293    ///
294    /// Signalled by special code in the executor loop
295    waker: Option<Waker>,
296}
297
298/// Future from
299/// [`progress_until_stalled`][`MockExecutor::progress_until_stalled`]
300///
301/// See [`ProgressingUntilStalled`] for an overview of this aspect of the contraption.
302///
303/// Existence of this struct implies `Data.progressing_until_stalled` is `Some`.
304/// There can only be one at a time.
305#[derive(Educe)]
306#[educe(Debug)]
307struct ProgressUntilStalledFuture {
308    /// Executor's state; this future's state is in `.progressing_until_stalled`
309    #[educe(Debug(ignore))]
310    shared: Arc<Shared>,
311}
312
313/// Identifies a thread we know about - the executor thread, or a Subthread
314///
315/// Not related to `std::thread::ThreadId`.
316///
317/// See [`spawn_subthread`](MockExecutor::subthread_spawn) for definition of a Subthread.
318///
319/// This being a thread-local and not scoped by which `MockExecutor` we're talking about
320/// means that we can't cope if there are multiple `MockExecutor`s involved in the same thread.
321/// That's OK (and documented).
322#[derive(Copy, Clone, Eq, PartialEq, derive_more::Debug)]
323enum ThreadDescriptor {
324    /// Foreign - neither the (running) executor, nor a Subthread
325    #[debug("FOREIGN")]
326    Foreign,
327    /// The executor.
328    #[debug("Exe")]
329    Executor,
330    /// This task, which is a Subthread.
331    #[debug("{_0:?}")]
332    Subthread(TaskId),
333}
334
335/// Marker indicating that this task is a Subthread, not an async task.
336///
337/// See [`spawn_subthread`](MockExecutor::subthread_spawn) for definition of a Subthread.
338#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
339struct IsSubthread;
340
341/// [`Shared::subthread_yield`] should set our task awake before switching to the executor
342#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
343struct SetAwake;
344
345thread_local! {
346    /// Identifies this thread.
347    pub static THREAD_DESCRIPTOR: Cell<ThreadDescriptor> = const {
348        Cell::new(ThreadDescriptor::Foreign)
349    };
350}
351
352//---------- creation ----------
353
354impl MockExecutor {
355    /// Make a `MockExecutor` with default parameters
356    pub fn new() -> Self {
357        Self::default()
358    }
359
360    /// Make a `MockExecutor` with a specific `SchedulingPolicy`
361    pub fn with_scheduling(scheduling: SchedulingPolicy) -> Self {
362        Data {
363            scheduling,
364            ..Default::default()
365        }
366        .into()
367    }
368}
369
370impl From<Data> for MockExecutor {
371    fn from(data: Data) -> MockExecutor {
372        let shared = Shared {
373            data: Mutex::new(data),
374            thread_condvar: std::sync::Condvar::new(),
375        };
376        MockExecutor {
377            shared: Arc::new(shared),
378        }
379    }
380}
381
382//---------- spawning ----------
383
384impl MockExecutor {
385    /// Spawn a task and return something to identify it
386    ///
387    /// `desc` should `Display` as some kind of short string (ideally without spaces)
388    /// and will be used in the `Debug` impl and trace log messages from `MockExecutor`.
389    ///
390    /// The returned value is an opaque task identifier which is very cheap to clone
391    /// and which can be used by the caller in debug logging,
392    /// if it's desired to correlate with the debug output from `MockExecutor`.
393    /// Most callers will want to ignore it.
394    ///
395    /// This method is infallible.  (The `MockExecutor` cannot be shut down.)
396    pub fn spawn_identified(
397        &self,
398        desc: impl Display,
399        fut: impl Future<Output = ()> + Send + 'static,
400    ) -> impl Debug + Clone + Send + 'static {
401        self.spawn_internal(desc.to_string(), FutureObj::from(Box::new(fut)))
402    }
403
404    /// Spawn a task and return its output for further usage
405    ///
406    /// `desc` should `Display` as some kind of short string (ideally without spaces)
407    /// and will be used in the `Debug` impl and trace log messages from `MockExecutor`.
408    pub fn spawn_join<T: Debug + Send + 'static>(
409        &self,
410        desc: impl Display,
411        fut: impl Future<Output = T> + Send + 'static,
412    ) -> impl Future<Output = T> {
413        let (tx, rx) = oneshot::channel();
414        self.spawn_identified(desc, async move {
415            let res = fut.await;
416            tx.send(res)
417                .expect("Failed to send future's output, did future panic?");
418        });
419        rx.map(|m| m.expect("Failed to receive future's output"))
420    }
421
422    /// Spawn a task and return its `TaskId`
423    ///
424    /// Convenience method for use by `spawn_identified` and `spawn_obj`.
425    /// The future passed to `block_on` is not handled here.
426    fn spawn_internal(&self, desc: String, fut: TaskFuture) -> TaskId {
427        let mut data = self.shared.lock();
428        data.insert_task(desc, TaskFutureInfo::Normal(fut))
429    }
430}
431
432impl Data {
433    /// Insert a task given its `TaskFutureInfo` and return its `TaskId`.
434    fn insert_task(&mut self, desc: String, fut: TaskFutureInfo) -> TaskId {
435        let state = Awake;
436        let id = self.tasks.insert(Task {
437            state,
438            desc,
439            fut: Some(fut),
440        });
441        self.awake.push_back(id);
442        trace!("MockExecutor spawned {:?}={:?}", id, self.tasks[id]);
443        id
444    }
445}
446
447impl Spawn for MockExecutor {
448    fn spawn_obj(&self, future: TaskFuture) -> Result<(), SpawnError> {
449        self.spawn_internal("spawn_obj".into(), future);
450        Ok(())
451    }
452}
453
454impl Blocking for MockExecutor {
455    type ThreadHandle<T: Send + 'static> = Pin<Box<dyn Future<Output = T>>>;
456
457    fn spawn_blocking<F, T>(&self, f: F) -> Self::ThreadHandle<T>
458    where
459        F: FnOnce() -> T + Send + 'static,
460        T: Send + 'static,
461    {
462        assert_matches!(
463            THREAD_DESCRIPTOR.get(),
464            ThreadDescriptor::Executor | ThreadDescriptor::Subthread(_),
465            "MockExecutor::spawn_blocking_io only allowed from future or subthread, being run by this executor"
466        );
467        Box::pin(
468            self.subthread_spawn("spawn_blocking", f)
469                .map(|x| x.expect("Error in spawn_blocking subthread.")),
470        )
471    }
472
473    fn reenter_block_on<F>(&self, future: F) -> F::Output
474    where
475        F: Future,
476        F::Output: Send + 'static,
477    {
478        self.subthread_block_on_future(future)
479    }
480}
481
482impl JoinSetProvider for MockExecutor {
483    type JoinSet<T: Send + Sync + 'static> = FuturesJoinSet<T, Self>;
484
485    fn new_join_set<T>(&self) -> Self::JoinSet<T>
486    where
487        T: Send + Sync + 'static,
488    {
489        FuturesJoinSet::new(self.clone())
490    }
491}
492
493//---------- block_on ----------
494
495impl ToplevelBlockOn for MockExecutor {
496    fn block_on<F>(&self, input_fut: F) -> F::Output
497    where
498        F: Future,
499    {
500        let mut value: Option<F::Output> = None;
501
502        // Box this just so that we can conveniently control precisely when it's dropped.
503        // (We could do this with Option and Pin::set but that seems clumsier.)
504        let mut input_fut = Box::pin(input_fut);
505
506        let run_store_fut = {
507            let value = &mut value;
508            let input_fut = &mut input_fut;
509            async {
510                trace!("MockExecutor block_on future...");
511                let t = input_fut.await;
512                trace!("MockExecutor block_on future returned...");
513                *value = Some(t);
514                trace!("MockExecutor block_on future exiting.");
515            }
516        };
517
518        {
519            pin_mut!(run_store_fut);
520
521            let main_id = self
522                .shared
523                .lock()
524                .insert_task("main".into(), TaskFutureInfo::Main);
525            trace!("MockExecutor {main_id:?} is task for block_on");
526            self.execute_to_completion(run_store_fut);
527        }
528
529        #[allow(clippy::let_and_return)] // clarity
530        let value = value.take().unwrap_or_else(|| {
531            // eprintln can be captured by libtest, but the debug_dump goes to io::stderr.
532            // use the latter, so that the debug dump is prefixed by this message.
533            let _: io::Result<()> = writeln!(io::stderr(), "all futures blocked, crashing...");
534            // write to tracing too, so the tracing log is clear about when we crashed
535            error!("all futures blocked, crashing...");
536
537            // Sequencing here is subtle.
538            //
539            // We should do the dump before dropping the input future, because the input
540            // future is likely to own things that, when dropped, wake up other tasks,
541            // rendering the dump inaccurate.
542            //
543            // But also, dropping the input future may well drop a ProgressUntilStalledFuture
544            // which then reenters us.  More generally, we mustn't call user code
545            // with the lock held.
546            //
547            // And, we mustn't panic with the data lock held.
548            //
549            // If value was Some, then this closure is dropped without being called,
550            // which drops the future after it has yielded the value, which is correct.
551            {
552                let mut data = self.shared.lock();
553                data.debug_dump();
554            }
555            drop(input_fut);
556
557            panic!(
558                r"
559all futures blocked. waiting for the real world? or deadlocked (waiting for each other) ?
560"
561            );
562        });
563
564        value
565    }
566}
567
568//---------- execution - core implementation ----------
569
570impl MockExecutor {
571    /// Keep polling tasks until nothing more can be done
572    ///
573    /// Ie, stop when `awake` is empty and `progressing_until_stalled` is `None`.
574    fn execute_to_completion(&self, mut main_fut: MainFuture) {
575        trace!("MockExecutor execute_to_completion...");
576        loop {
577            self.execute_until_first_stall(main_fut.as_mut());
578
579            // Handle `progressing_until_stalled`
580            let pus_waker = {
581                let mut data = self.shared.lock();
582                let pus = &mut data.progressing_until_stalled;
583                trace!("MockExecutor execute_to_completion PUS={:?}", &pus);
584                let Some(pus) = pus else {
585                    // No progressing_until_stalled, we're actually done.
586                    break;
587                };
588                assert_eq!(
589                    pus.finished, Pending,
590                    "ProgressingUntilStalled finished twice?!"
591                );
592                pus.finished = Ready(());
593
594                // Release the lock temporarily so that ActualWaker::clone doesn't deadlock
595                let waker = pus
596                    .waker
597                    .take()
598                    .expect("ProgressUntilStalledFuture not ever polled!");
599                drop(data);
600                let waker_copy = waker.clone();
601                let mut data = self.shared.lock();
602
603                let pus = &mut data.progressing_until_stalled;
604                if let Some(double) = pus
605                    .as_mut()
606                    .expect("progressing_until_stalled updated under our feet!")
607                    .waker
608                    .replace(waker)
609                {
610                    panic!("double progressing_until_stalled.waker! {double:?}");
611                }
612
613                waker_copy
614            };
615            pus_waker.wake();
616        }
617        trace!("MockExecutor execute_to_completion done");
618    }
619
620    /// Keep polling tasks until `awake` is empty
621    ///
622    /// (Ignores `progressing_until_stalled` - so if one is active,
623    /// will return when all other tasks have blocked.)
624    ///
625    /// # Panics
626    ///
627    /// Might malfunction or panic if called reentrantly
628    fn execute_until_first_stall(&self, main_fut: MainFuture) {
629        trace!("MockExecutor execute_until_first_stall ...");
630
631        assert_eq!(
632            THREAD_DESCRIPTOR.get(),
633            ThreadDescriptor::Foreign,
634            "MockExecutor executor re-entered"
635        );
636        THREAD_DESCRIPTOR.set(ThreadDescriptor::Executor);
637
638        let r = catch_unwind(AssertUnwindSafe(|| self.executor_main_loop(main_fut)));
639
640        THREAD_DESCRIPTOR.set(ThreadDescriptor::Foreign);
641
642        match r {
643            Ok(()) => trace!("MockExecutor execute_until_first_stall done."),
644            Err(e) => {
645                trace!("MockExecutor executor, or async task, panicked!");
646                panic_any(e)
647            }
648        }
649    }
650
651    /// Keep polling tasks until `awake` is empty (inner, executor main loop)
652    ///
653    /// This is only called from [`MockExecutor::execute_until_first_stall`],
654    /// so it could also be called `execute_until_first_stall_inner`.
655    fn executor_main_loop(&self, mut main_fut: MainFuture) {
656        'outer: loop {
657            // Take a `Awake` task off `awake` and make it `Asleep`
658            let (id, mut fut) = 'inner: loop {
659                let mut data = self.shared.lock();
660                let Some(id) = data.schedule() else {
661                    break 'outer;
662                };
663                let Some(task) = data.tasks.get_mut(id) else {
664                    trace!("MockExecutor {id:?} vanished");
665                    continue;
666                };
667                task.state = Asleep(vec![]);
668                let fut = task.fut.take().expect("future missing from task!");
669                break 'inner (id, fut);
670            };
671
672            // Poll the selected task
673            trace!("MockExecutor {id:?} polling...");
674            let waker = ActualWaker::make_waker(&self.shared, id);
675            let mut cx = Context::from_waker(&waker);
676            let r: Either<Poll<()>, IsSubthread> = match &mut fut {
677                TaskFutureInfo::Normal(fut) => Left(fut.poll_unpin(&mut cx)),
678                TaskFutureInfo::Main => Left(main_fut.as_mut().poll(&mut cx)),
679                TaskFutureInfo::Subthread => Right(IsSubthread),
680            };
681
682            // Deal with the returned `Poll`
683            let _fut_drop_late;
684            {
685                let mut data = self.shared.lock();
686                let task = data
687                    .tasks
688                    .get_mut(id)
689                    .expect("task vanished while we were polling it");
690
691                match r {
692                    Left(Pending) => {
693                        trace!("MockExecutor {id:?} -> Pending");
694                        if task.fut.is_some() {
695                            panic!("task reinserted while we polled it?!");
696                        }
697                        // The task might have been woken *by its own poll method*.
698                        // That's why we set it to `Asleep` *earlier* rather than here.
699                        // All we need to do is put the future back.
700                        task.fut = Some(fut);
701                    }
702                    Left(Ready(())) => {
703                        trace!("MockExecutor {id:?} -> Ready");
704                        // Oh, it finished!
705                        // It might be in `awake`, but that's allowed to contain stale tasks,
706                        // so we *don't* need to scan that list and remove it.
707                        data.tasks.remove(id);
708                        // It is important that we don't drop `fut` until we have released
709                        // the data lock, since it is an external type and might try to reenter
710                        // us (eg by calling spawn).  If we do that here, we risk deadlock.
711                        // So, move `fut` to a variable with scope outside the block with `data`.
712                        _fut_drop_late = fut;
713                    }
714                    Right(IsSubthread) => {
715                        trace!("MockExecutor {id:?} -> Ready, waking Subthread");
716                        // Task is a subthread, which has called thread_context_switch
717                        // to switch to us.  We "poll" it by switching back.
718
719                        // Put back `TFI::Subthread`, which was moved out temporarily, above.
720                        task.fut = Some(fut);
721
722                        self.shared.thread_context_switch(
723                            data,
724                            ThreadDescriptor::Executor,
725                            ThreadDescriptor::Subthread(id),
726                        );
727
728                        // Now, if the Subthread still exists, that's because it's switched
729                        // back to us, and is waiting in subthread_block_on_future again.
730                        // Or it might have ended, in which case it's not in `tasks` any more.
731                        // In any case we can go back to scheduling futures.
732                    }
733                }
734            }
735        }
736    }
737}
738
739impl Data {
740    /// Return the next task to run
741    ///
742    /// The task is removed from `awake`, but **`state` is not set to `Asleep`**.
743    /// The caller must restore the invariant!
744    fn schedule(&mut self) -> Option<TaskId> {
745        use SchedulingPolicy as SP;
746        match self.scheduling {
747            SP::Stack => self.awake.pop_back(),
748            SP::Queue => self.awake.pop_front(),
749        }
750    }
751}
752
753impl ActualWaker {
754    /// Obtain a strong reference to the executor's data
755    fn upgrade_data(&self) -> Option<Arc<Shared>> {
756        self.data.upgrade()
757    }
758
759    /// Wake the task corresponding to this `ActualWaker`
760    ///
761    /// This is like `<Self as std::task::Wake>::wake()` but takes `&self`, not `Arc`
762    fn wake(&self) {
763        let Some(data) = self.upgrade_data() else {
764            // The executor is gone!  Don't try to wake.
765            return;
766        };
767        let mut data = data.lock();
768        let data = &mut *data;
769        trace!("MockExecutor {:?} wake", &self.id);
770        let Some(task) = data.tasks.get_mut(self.id) else {
771            return;
772        };
773        task.set_awake(self.id, &mut data.awake);
774    }
775
776    /// Create and return a `Waker` for task `id`
777    fn make_waker(shared: &Arc<Shared>, id: TaskId) -> Waker {
778        ActualWaker {
779            data: Arc::downgrade(shared),
780            id,
781        }
782        .new_waker()
783    }
784}
785
786//---------- "progress until stalled" functionality ----------
787
788impl MockExecutor {
789    /// Run tasks in the current executor until every other task is waiting
790    ///
791    /// # Panics
792    ///
793    /// Might malfunction or panic if more than one such call is running at once.
794    ///
795    /// (Ie, you must `.await` or drop the returned `Future`
796    /// before calling this method again.)
797    ///
798    /// Must be called and awaited within a future being run by `self`.
799    pub fn progress_until_stalled(&self) -> impl Future<Output = ()> + use<> {
800        let mut data = self.shared.lock();
801        assert!(
802            data.progressing_until_stalled.is_none(),
803            "progress_until_stalled called more than once"
804        );
805        trace!("MockExecutor progress_until_stalled...");
806        data.progressing_until_stalled = Some(ProgressingUntilStalled {
807            finished: Pending,
808            waker: None,
809        });
810        ProgressUntilStalledFuture {
811            shared: self.shared.clone(),
812        }
813    }
814}
815
816impl Future for ProgressUntilStalledFuture {
817    type Output = ();
818
819    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<()> {
820        let waker = cx.waker().clone();
821        let mut data = self.shared.lock();
822        let pus = data.progressing_until_stalled.as_mut();
823        trace!("MockExecutor progress_until_stalled polling... {:?}", &pus);
824        let pus = pus.expect("ProgressingUntilStalled missing");
825        pus.waker = Some(waker);
826        pus.finished
827    }
828}
829
830impl Drop for ProgressUntilStalledFuture {
831    fn drop(&mut self) {
832        self.shared.lock().progressing_until_stalled = None;
833    }
834}
835
836//---------- (sub)threads ----------
837
838impl MockExecutor {
839    /// Spawn a "Subthread", for processing in a sync context
840    ///
841    /// `call` will be run on a separate thread, called a "Subthread".
842    ///
843    /// But it will **not run simultaneously** with the executor,
844    /// nor with other Subthreads.
845    /// So Subthreads are somewhat like coroutines.
846    ///
847    /// `call` must be capable of making progress without waiting for any other Subthreads.
848    /// `call` may wait for async futures, using
849    /// [`subthread_block_on_future`](MockExecutor::subthread_block_on_future).
850    ///
851    /// Subthreads may be used for cpubound activity,
852    /// or synchronous IO (such as large volumes of disk activity),
853    /// provided that the synchronous code will reliably make progress,
854    /// without waiting (directly or indirectly) for any async task or Subthread -
855    /// except via `subthread_block_on_future`.
856    ///
857    /// # Subthreads vs raw `std::thread` threads
858    ///
859    /// Programs using `MockExecutor` may use `std::thread` threads directly.
860    /// However, this is not recommended.  There are severe limitations:
861    ///
862    ///  * Only a Subthread can re-enter the async context from sync code:
863    ///    this must be done with
864    ///    using [`subthread_block_on_future`](MockExecutor::subthread_block_on_future).
865    ///    (Re-entering the executor with
866    ///    [`block_on`](tor_rtcompat::ToplevelBlockOn::block_on)
867    ///    is not allowed.)
868    ///  * If async tasks want to suspend waiting for synchronous code,
869    ///    the synchronous code must run on a Subthread.
870    ///    This allows the `MockExecutor` to know when
871    ///    that synchronous code is still making progress.
872    ///    (This is needed for
873    ///    [`progress_until_stalled`](MockExecutor::progress_until_stalled)
874    ///    and the facilities which use it, such as
875    ///    [`MockRuntime::advance_until_stalled`](crate::MockRuntime::advance_until_stalled).)
876    ///  * Subthreads never run in parallel -
877    ///    they only run as scheduled deterministically by the `MockExecutor`.
878    ///    So using Subthreads eliminates a source of test nonndeterminism.
879    ///    (Execution order is still varied due to explicitly varying the scheduling policy.)
880    ///
881    /// # Panics, abuse, and malfunctions
882    ///
883    /// If `call` panics and unwinds, `spawn_subthread` yields `Err`.
884    /// The application code should to do something about it if this happens,
885    /// typically, logging errors, tearing things down, or failing a test case.
886    ///
887    /// If the executor doesn't run, the subthread will not run either, and will remain stuck.
888    /// (So, typically, if the thread supposed to run the executor panics,
889    /// for example because a future or the executor itself panics,
890    /// all the subthreads will become stuck - effectively, they'll be leaked.)
891    ///
892    /// `spawn_subthread` panics if OS thread spawning fails.
893    /// (Like `std::thread::spawn()` does.)
894    ///
895    /// `MockExecutor`s will malfunction or panic if
896    /// any executor invocation method (eg `block_on`) is called on a Subthread.
897    pub fn subthread_spawn<T: Send + 'static>(
898        &self,
899        desc: impl Display,
900        call: impl FnOnce() -> T + Send + 'static,
901    ) -> impl Future<Output = Result<T, Box<dyn Any + Send>>> + Unpin + Send + Sync + 'static {
902        let desc = desc.to_string();
903        let (output_tx, output_rx) = oneshot::channel();
904
905        // NB: we don't know which thread we're on!
906        // In principle we might be on another Subthread.
907        // So we can't context switch here.  That would be very confusing.
908        //
909        // Instead, we prepare the new Subthread as follows:
910        //   - There is a task in the executor
911        //   - The task is ready to be polled, whenever the executor decides to
912        //   - The thread starts running right away, but immediately waits until it is scheduled
913        // See `subthread_entrypoint`.
914
915        {
916            let mut data = self.shared.lock();
917            let id = data.insert_task(desc.clone(), TaskFutureInfo::Subthread);
918
919            let _: std::thread::JoinHandle<()> = std::thread::Builder::new()
920                .name(desc)
921                .spawn({
922                    let shared = self.shared.clone();
923                    move || shared.subthread_entrypoint(id, call, output_tx)
924                })
925                .expect("spawn failed");
926        }
927
928        output_rx.map(|r| {
929            r.unwrap_or_else(|_: Canceled| panic!("Subthread cancelled but should be impossible!"))
930        })
931    }
932
933    /// Call an async `Future` from a Subthread
934    ///
935    /// Blocks the Subthread, and arranges to run async tasks,
936    /// including `fut`, until `fut` completes.
937    ///
938    /// `fut` is polled on the executor thread, not on the Subthread.
939    /// (We may change that in the future, allowing passing a non-`Send` future.)
940    ///
941    /// # Panics, abuse, and malfunctions
942    ///
943    /// `subthread_block_on_future` will malfunction or panic
944    /// if called on a thread that isn't a Subthread from the same `MockExecutor`
945    /// (ie a thread made with [`spawn_subthread`](MockExecutor::subthread_spawn)).
946    ///
947    /// If `fut` itself panics, the executor will panic.
948    ///
949    /// If the executor isn't running, `subthread_block_on_future` will hang indefinitely.
950    /// See `spawn_subthread`.
951    pub fn subthread_block_on_future<T: Send + 'static>(&self, fut: impl Future<Output = T>) -> T {
952        let id = match THREAD_DESCRIPTOR.get() {
953            ThreadDescriptor::Subthread(id) => id,
954            ThreadDescriptor::Executor => {
955                panic!("subthread_block_on_future called from MockExecutor thread (async task?)")
956            }
957            ThreadDescriptor::Foreign => panic!(
958                "subthread_block_on_future called on foreign thread (not spawned with spawn_subthread)"
959            ),
960        };
961        trace!("MockExecutor thread {id:?}, subthread_block_on_future...");
962        let mut fut = pin!(fut);
963
964        // We yield once before the first poll, and once after Ready, to shake up the
965        // execution order a bit, depending on the scheduling policy.
966        let yield_ = |set_awake| self.shared.subthread_yield(id, set_awake);
967        yield_(Some(SetAwake));
968
969        let ret = loop {
970            // Poll the provided future
971            trace!("MockExecutor thread {id:?}, s.t._block_on_future polling...");
972            let waker = ActualWaker::make_waker(&self.shared, id);
973            let mut cx = Context::from_waker(&waker);
974            let r: Poll<T> = fut.as_mut().poll(&mut cx);
975
976            if let Ready(r) = r {
977                trace!("MockExecutor thread {id:?}, s.t._block_on_future poll -> Ready");
978                break r;
979            }
980
981            // Pending.  Switch back to the executor thread.
982            // When the future becomes ready, the Waker will be woken, waking the task,
983            // so that the executor will "poll" us again.
984            trace!("MockExecutor thread {id:?}, s.t._block_on_future poll -> Pending");
985
986            yield_(None);
987        };
988
989        yield_(Some(SetAwake));
990
991        trace!("MockExecutor thread {id:?}, subthread_block_on_future complete.");
992
993        ret
994    }
995}
996
997impl Shared {
998    /// Main entrypoint function for a Subthread
999    ///
1000    /// Entered on a new `std::thread` thread created by
1001    /// [`subthread_spawn`](MockExecutor::subthread_spawn).
1002    ///
1003    /// When `call` completes, sends its returned value `T` to `output_tx`.
1004    fn subthread_entrypoint<T: Send + 'static>(
1005        self: Arc<Self>,
1006        id: TaskId,
1007        call: impl FnOnce() -> T + Send + 'static,
1008        output_tx: oneshot::Sender<Result<T, Box<dyn Any + Send>>>,
1009    ) {
1010        THREAD_DESCRIPTOR.set(ThreadDescriptor::Subthread(id));
1011        trace!("MockExecutor thread {id:?}, entrypoint");
1012
1013        // We start out Awake, but we wait for the executor to tell us to run.
1014        // This will be done the first time the task is "polled".
1015        {
1016            let data = self.lock();
1017            self.thread_context_switch_waitfor_instruction_to_run(
1018                data,
1019                ThreadDescriptor::Subthread(id),
1020            );
1021        }
1022
1023        trace!("MockExecutor thread {id:?}, entering user code");
1024
1025        // Run the user's actual thread function.
1026        // This will typically reenter us via subthread_block_on_future.
1027        let ret = catch_unwind(AssertUnwindSafe(call));
1028
1029        trace!("MockExecutor thread {id:?}, completed user code");
1030
1031        // This makes the return value from subthread_spawn ready.
1032        // It will be polled by the executor in due course, presumably.
1033
1034        output_tx.send(ret).unwrap_or_else(
1035            #[allow(clippy::unnecessary_lazy_evaluations)]
1036            |_| {}, // receiver dropped, maybe executor dropped or something?
1037        );
1038
1039        {
1040            let mut data = self.lock();
1041
1042            // Never poll this task again (so never schedule this thread)
1043            let _: Task = data.tasks.remove(id).expect("Subthread task vanished!");
1044
1045            // Tell the executor it is scheduled now.
1046            // We carry on exiting, in parallel (holding the data lock).
1047            self.thread_context_switch_send_instruction_to_run(
1048                &mut data,
1049                ThreadDescriptor::Subthread(id),
1050                ThreadDescriptor::Executor,
1051            );
1052        }
1053    }
1054
1055    /// Yield back to the executor from a subthread
1056    ///
1057    /// Checks that things are in order
1058    /// (in particular, that this task is in the data structure as a subhtread)
1059    /// and switches to the executor thread.
1060    ///
1061    /// The caller must arrange that the task gets woken.
1062    ///
1063    /// With [`SetAwake`], sets our task awake, so that we'll be polled
1064    /// again as soon as we get to the top of the executor's queue.
1065    /// Otherwise, we'll be reentered after someone wakes a [`Waker`] for the task.
1066    fn subthread_yield(&self, us: TaskId, set_awake: Option<SetAwake>) {
1067        let mut data = self.lock();
1068        {
1069            let data = &mut *data;
1070            let task = data.tasks.get_mut(us).expect("Subthread task vanished!");
1071            match &task.fut {
1072                Some(TaskFutureInfo::Subthread) => {}
1073                other => panic!("subthread_block_on_future but TFI {other:?}"),
1074            };
1075            if let Some(SetAwake) = set_awake {
1076                task.set_awake(us, &mut data.awake);
1077            }
1078        }
1079        self.thread_context_switch(
1080            data,
1081            ThreadDescriptor::Subthread(us),
1082            ThreadDescriptor::Executor,
1083        );
1084    }
1085
1086    /// Switch from (sub)thread `us` to (sub)thread `them`
1087    ///
1088    /// Returns when someone calls `thread_context_switch(.., us)`.
1089    fn thread_context_switch(
1090        &self,
1091        mut data: MutexGuard<Data>,
1092        us: ThreadDescriptor,
1093        them: ThreadDescriptor,
1094    ) {
1095        trace!("MockExecutor thread {us:?}, switching to {them:?}");
1096        self.thread_context_switch_send_instruction_to_run(&mut data, us, them);
1097        self.thread_context_switch_waitfor_instruction_to_run(data, us);
1098    }
1099
1100    /// Instruct the (sub)thread `them` to run
1101    ///
1102    /// Update `thread_to_run`, which will wake up `them`'s
1103    /// call to `thread_context_switch_waitfor_instruction_to_run`.
1104    ///
1105    /// Must be called from (sub)thread `us`.
1106    /// Part of `thread_context_switch`, not normally called directly.
1107    fn thread_context_switch_send_instruction_to_run(
1108        &self,
1109        data: &mut MutexGuard<Data>,
1110        us: ThreadDescriptor,
1111        them: ThreadDescriptor,
1112    ) {
1113        assert_eq!(data.thread_to_run, us);
1114        data.thread_to_run = them;
1115        self.thread_condvar.notify_all();
1116    }
1117
1118    /// Await an instruction for this thread, `us`, to run
1119    ///
1120    /// Waits for `thread_to_run` to be `us`,
1121    /// waiting for `thread_condvar` as necessary.
1122    ///
1123    /// Part of `thread_context_switch`, not normally called directly.
1124    fn thread_context_switch_waitfor_instruction_to_run(
1125        &self,
1126        data: MutexGuard<Data>,
1127        us: ThreadDescriptor,
1128    ) {
1129        #[allow(let_underscore_lock)]
1130        let _: MutexGuard<_> = self
1131            .thread_condvar
1132            .wait_while(data, |data| {
1133                let live = data.thread_to_run;
1134                let resume = live == us;
1135                if resume {
1136                    trace!("MockExecutor thread {us:?}, resuming");
1137                } else {
1138                    trace!("MockExecutor thread {us:?}, waiting for {live:?}");
1139                }
1140                // We're in `.wait_while`, not `.wait_until`.  Confusing.
1141                !resume
1142            })
1143            .expect("data lock poisoned");
1144    }
1145}
1146
1147//---------- ancillary and convenience functions ----------
1148
1149/// Trait to let us assert at compile time that something is nicely `Sync` etc.
1150#[allow(dead_code)] // yes, we don't *use* anything from this trait
1151trait EnsureSyncSend: Sync + Send + 'static {}
1152impl EnsureSyncSend for ActualWaker {}
1153impl EnsureSyncSend for MockExecutor {}
1154
1155impl MockExecutor {
1156    /// Return the number of tasks running in this executor
1157    ///
1158    /// One possible use is for a test case to check that task(s)
1159    /// that ought to have exited, have indeed done so.
1160    ///
1161    /// In the usual case, the answer will be at least 1,
1162    /// because it counts the future passed to
1163    /// [`block_on`](MockExecutor::block_on)
1164    /// (perhaps via [`MockRuntime::test_with_various`](crate::MockRuntime::test_with_various)).
1165    pub fn n_tasks(&self) -> usize {
1166        self.shared.lock().tasks.len()
1167    }
1168}
1169
1170impl Shared {
1171    /// Lock and obtain the guard
1172    ///
1173    /// Convenience method which panics on poison
1174    fn lock(&self) -> MutexGuard<Data> {
1175        self.data.lock().expect("data lock poisoned")
1176    }
1177}
1178
1179impl Task {
1180    /// Set task `id` to `Awake` and arrange that it will be polled.
1181    fn set_awake(&mut self, id: TaskId, data_awake: &mut VecDeque<TaskId>) {
1182        match self.state {
1183            Awake => {}
1184            Asleep(_) => {
1185                self.state = Awake;
1186                data_awake.push_back(id);
1187            }
1188        }
1189    }
1190}
1191
1192//---------- ActualWaker as RawWaker ----------
1193
1194/// Using [`ActualWaker`] in a [`RawWaker`]
1195///
1196/// We need to make a
1197/// [`Waker`] (the safe, type-erased, waker, used by actual futures)
1198/// which contains an
1199/// [`ActualWaker`] (our actual waker implementation, also safe).
1200///
1201/// `std` offers `Waker::from<Arc<impl Wake>>`.
1202/// But we want a bespoke `Clone` implementation, so we don't want to use `Arc`.
1203///
1204/// So instead, we implement the `RawWaker` API in terms of `ActualWaker`.
1205/// We keep the `ActualWaker` in a `Box`, and actually `clone` it (and the `Box`).
1206///
1207/// SAFETY
1208///
1209///  * The data pointer is `Box::<ActualWaker>::into_raw()`
1210///  * We share these when we clone
1211///  * No-one is allowed `&mut ActualWaker` unless there are no other clones
1212///  * So we may make references `&ActualWaker`
1213impl ActualWaker {
1214    /// Wrap up an [`ActualWaker`] as a type-erased [`Waker`] for passing to futures etc.
1215    fn new_waker(self) -> Waker {
1216        unsafe { Waker::from_raw(self.raw_new()) }
1217    }
1218
1219    /// Helper: wrap up an [`ActualWaker`] as a [`RawWaker`].
1220    fn raw_new(self) -> RawWaker {
1221        let self_: Box<ActualWaker> = self.into();
1222        let self_: *mut ActualWaker = Box::into_raw(self_);
1223        let self_: *const () = self_ as _;
1224        RawWaker::new(self_, &RAW_WAKER_VTABLE)
1225    }
1226
1227    /// Implementation of [`RawWakerVTable`]'s `clone`
1228    unsafe fn raw_clone(self_: *const ()) -> RawWaker {
1229        unsafe {
1230            let self_: *const ActualWaker = self_ as _;
1231            let self_: &ActualWaker = self_.as_ref().unwrap_unchecked();
1232            let copy: ActualWaker = self_.clone();
1233            copy.raw_new()
1234        }
1235    }
1236
1237    /// Implementation of [`RawWakerVTable`]'s `wake`
1238    unsafe fn raw_wake(self_: *const ()) {
1239        unsafe {
1240            Self::raw_wake_by_ref(self_);
1241            Self::raw_drop(self_);
1242        }
1243    }
1244
1245    /// Implementation of [`RawWakerVTable`]'s `wake_ref_by`
1246    unsafe fn raw_wake_by_ref(self_: *const ()) {
1247        unsafe {
1248            let self_: *const ActualWaker = self_ as _;
1249            let self_: &ActualWaker = self_.as_ref().unwrap_unchecked();
1250            self_.wake();
1251        }
1252    }
1253
1254    /// Implementation of [`RawWakerVTable`]'s `drop`
1255    unsafe fn raw_drop(self_: *const ()) {
1256        unsafe {
1257            let self_: *mut ActualWaker = self_ as _;
1258            let self_: Box<ActualWaker> = Box::from_raw(self_);
1259            drop(self_);
1260        }
1261    }
1262}
1263
1264/// vtable for `Box<ActualWaker>` as `RawWaker`
1265//
1266// This ought to be in the impl block above, but
1267//   "associated `static` items are not allowed"
1268static RAW_WAKER_VTABLE: RawWakerVTable = RawWakerVTable::new(
1269    ActualWaker::raw_clone,
1270    ActualWaker::raw_wake,
1271    ActualWaker::raw_wake_by_ref,
1272    ActualWaker::raw_drop,
1273);
1274
1275//---------- Sleep location tracking and dumping ----------
1276
1277/// We record "where a future went to sleep" as (just) a backtrace
1278///
1279/// This type alias allows us to mock `Backtrace` for miri.
1280/// (It also insulates from future choices about sleep location representation.0
1281#[cfg(not(miri))]
1282type SleepLocation = Backtrace;
1283
1284impl Data {
1285    /// Dump tasks and their sleep location backtraces
1286    fn dump_backtraces(&self, f: &mut fmt::Formatter) -> fmt::Result {
1287        for (id, task) in self.tasks.iter() {
1288            let prefix = |f: &mut fmt::Formatter| write!(f, "{id:?}={task:?}: ");
1289            match &task.state {
1290                Awake => {
1291                    prefix(f)?;
1292                    writeln!(f, "awake")?;
1293                }
1294                Asleep(locs) => {
1295                    let n = locs.len();
1296                    for (i, loc) in locs.iter().enumerate() {
1297                        prefix(f)?;
1298                        writeln!(f, "asleep, backtrace {i}/{n}:\n{loc}",)?;
1299                    }
1300                    if n == 0 {
1301                        prefix(f)?;
1302                        writeln!(f, "asleep, no backtraces, Waker never cloned, stuck!",)?;
1303                    }
1304                }
1305            }
1306        }
1307        writeln!(
1308            f,
1309            "\nNote: there might be spurious traces, see docs for MockExecutor::debug_dump\n"
1310        )?;
1311        Ok(())
1312    }
1313}
1314
1315/// Track sleep locations via `<Waker as Clone>`.
1316///
1317/// See [`MockExecutor::debug_dump`] for the explanation.
1318impl Clone for ActualWaker {
1319    fn clone(&self) -> Self {
1320        let id = self.id;
1321
1322        if let Some(data) = self.upgrade_data() {
1323            // If the executor is gone, there is nothing to adjust
1324            let mut data = data.lock();
1325            if let Some(task) = data.tasks.get_mut(self.id) {
1326                match &mut task.state {
1327                    Awake => trace!("MockExecutor cloned waker for awake task {id:?}"),
1328                    Asleep(locs) => locs.push(SleepLocation::force_capture()),
1329                }
1330            } else {
1331                trace!("MockExecutor cloned waker for dead task {id:?}");
1332            }
1333        }
1334
1335        ActualWaker {
1336            data: self.data.clone(),
1337            id,
1338        }
1339    }
1340}
1341
1342//---------- API for full debug dump ----------
1343
1344/// Debugging dump of a `MockExecutor`'s state
1345///
1346/// Returned by [`MockExecutor::as_debug_dump`]
1347//
1348// Existence implies backtraces have been resolved
1349//
1350// We use `Either` so that we can also use this internally when we have &mut Data.
1351pub struct DebugDump<'a>(Either<&'a Data, MutexGuard<'a, Data>>);
1352
1353impl MockExecutor {
1354    /// Dump the executor's state including backtraces of waiting tasks, to stderr
1355    ///
1356    /// This is considerably more extensive than simply
1357    /// `MockExecutor as Debug`.
1358    ///
1359    /// (This is a convenience method, which wraps
1360    /// [`MockExecutor::as_debug_dump()`].
1361    ///
1362    /// ### Backtrace salience (possible spurious traces)
1363    ///
1364    /// **Summary**
1365    ///
1366    /// The technique used to capture backtraces when futures sleep is not 100% exact.
1367    /// It will usually show all the actual sleeping sites,
1368    /// but it might also show other backtraces which were part of
1369    /// the implementation of some complex relevant future.
1370    ///
1371    /// **Details**
1372    ///
1373    /// When a future's implementation wants to sleep,
1374    /// it needs to record the [`Waker`] (from the [`Context`])
1375    /// so that the "other end" can call `.wake()` on it later,
1376    /// when the future should be woken.
1377    ///
1378    /// Since `Context.waker()` gives `&Waker`, borrowed from the `Context`,
1379    /// the future must clone the `Waker`,
1380    /// and it must do so in within the `poll()` call.
1381    ///
1382    /// A future which is waiting in a `select!` will typically
1383    /// show multiple traces, one for each branch.
1384    /// But,
1385    /// if a future sleeps on one thing, and then when polled again later,
1386    /// sleeps on something different, without waking up in between,
1387    /// both backtrace locations will be shown.
1388    /// And,
1389    /// a complicated future contraption *might* clone the `Waker` more times.
1390    /// So not every backtrace will necessarily be informative.
1391    ///
1392    /// ### Panics
1393    ///
1394    /// Panics on write errors.
1395    pub fn debug_dump(&self) {
1396        self.as_debug_dump().to_stderr();
1397    }
1398
1399    /// Dump the executor's state including backtraces of waiting tasks
1400    ///
1401    /// This is considerably more extensive than simply
1402    /// `MockExecutor as Debug`.
1403    ///
1404    /// Returns an object for formatting with [`Debug`].
1405    /// To simply print the dump to stderr (eg in a test),
1406    /// use [`.debug_dump()`](MockExecutor::debug_dump).
1407    ///
1408    /// **Backtrace salience (possible spurious traces)** -
1409    /// see [`.debug_dump()`](MockExecutor::debug_dump).
1410    pub fn as_debug_dump(&self) -> DebugDump {
1411        let data = self.shared.lock();
1412        DebugDump(Right(data))
1413    }
1414}
1415
1416impl Data {
1417    /// Convenience function: dump including backtraces, to stderr
1418    fn debug_dump(&mut self) {
1419        DebugDump(Left(self)).to_stderr();
1420    }
1421}
1422
1423impl DebugDump<'_> {
1424    /// Convenience function: dump tasks and backtraces to stderr
1425    #[allow(clippy::wrong_self_convention)] // "to_stderr" doesn't mean "convert to stderr"
1426    fn to_stderr(self) {
1427        write!(io::stderr().lock(), "{:?}", self)
1428            .unwrap_or_else(|e| error_report!(e, "failed to write debug dump to stderr"));
1429    }
1430}
1431
1432//---------- bespoke Debug impls ----------
1433
1434impl Debug for DebugDump<'_> {
1435    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1436        let self_: &Data = &self.0;
1437
1438        writeln!(f, "MockExecutor state:\n{self_:#?}")?;
1439        writeln!(f, "MockExecutor task dump:")?;
1440        self_.dump_backtraces(f)?;
1441
1442        Ok(())
1443    }
1444}
1445
1446// See `impl Debug for Data` for notes on the output
1447impl Debug for Task {
1448    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1449        let Task { desc, state, fut } = self;
1450        write!(f, "{:?}", desc)?;
1451        write!(f, "=")?;
1452        match fut {
1453            None => write!(f, "P")?,
1454            Some(TaskFutureInfo::Normal(_)) => write!(f, "f")?,
1455            Some(TaskFutureInfo::Main) => write!(f, "m")?,
1456            Some(TaskFutureInfo::Subthread) => write!(f, "T")?,
1457        }
1458        match state {
1459            Awake => write!(f, "W")?,
1460            Asleep(locs) => write!(f, "s{}", locs.len())?,
1461        };
1462        Ok(())
1463    }
1464}
1465
1466/// Helper: `Debug`s as a list of tasks, given the `Data` for lookups and a list of the ids
1467///
1468/// `Task`s in `Data` are printed as `Ti(ID)"SPEC"=FLAGS"`.
1469///
1470/// `FLAGS` are:
1471///
1472///  * `T`: this task is for a Subthread (from subthread_spawn).
1473///  * `P`: this task is being polled (its `TaskFutureInfo` is absent)
1474///  * `f`: this is a normal task with a future and its future is present in `Data`
1475///  * `m`: this is the main task from `block_on`
1476///
1477///  * `W`: the task is awake
1478///  * `s<n>`: the task is asleep, and `<n>` is the number of recorded sleeping locations
1479//
1480// We do it this way because the naive dump from derive is very expansive
1481// and makes it impossible to see the wood for the trees.
1482// This very compact representation it easier to find a task of interest in the output.
1483//
1484// This is implemented in `impl Debug for Task`.
1485//
1486//
1487// rustc doesn't think automatically-derived Debug impls count for whether a thing is used.
1488// This has caused quite some fallout.  https://github.com/rust-lang/rust/pull/85200
1489// I think derive_more emits #[automatically_derived], so that even though we use this
1490// in our Debug impl, that construction is unused.
1491#[allow(dead_code)]
1492struct DebugTasks<'d, F>(&'d Data, F);
1493
1494// See `impl Debug for Data` for notes on the output
1495impl<F, I> Debug for DebugTasks<'_, F>
1496where
1497    F: Fn() -> I,
1498    I: Iterator<Item = TaskId>,
1499{
1500    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1501        let DebugTasks(data, ids) = self;
1502        for (id, delim) in izip!(ids(), chain!(iter::once(""), iter::repeat(" ")),) {
1503            write!(f, "{delim}{id:?}")?;
1504            match data.tasks.get(id) {
1505                None => write!(f, "-")?,
1506                Some(task) => write!(f, "={task:?}")?,
1507            }
1508        }
1509        Ok(())
1510    }
1511}
1512
1513/// Mock `Backtrace` for miri
1514///
1515/// See also the not-miri `type SleepLocation`, alias above.
1516#[cfg(miri)]
1517mod miri_sleep_location {
1518    #[derive(Debug, derive_more::Display)]
1519    #[display("<SleepLocation>")]
1520    pub(super) struct SleepLocation {}
1521
1522    impl SleepLocation {
1523        pub(super) fn force_capture() -> Self {
1524            SleepLocation {}
1525        }
1526    }
1527}
1528#[cfg(miri)]
1529use miri_sleep_location::SleepLocation;
1530
1531#[cfg(test)]
1532mod test {
1533    // @@ begin test lint list maintained by maint/add_warning @@
1534    #![allow(clippy::bool_assert_comparison)]
1535    #![allow(clippy::clone_on_copy)]
1536    #![allow(clippy::dbg_macro)]
1537    #![allow(clippy::mixed_attributes_style)]
1538    #![allow(clippy::print_stderr)]
1539    #![allow(clippy::print_stdout)]
1540    #![allow(clippy::single_char_pattern)]
1541    #![allow(clippy::unwrap_used)]
1542    #![allow(clippy::unchecked_time_subtraction)]
1543    #![allow(clippy::useless_vec)]
1544    #![allow(clippy::needless_pass_by_value)]
1545    #![allow(clippy::string_slice)] // See arti#2571
1546    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
1547    use super::*;
1548    use futures::channel::mpsc;
1549    use futures::{SinkExt as _, StreamExt as _};
1550    use strum::IntoEnumIterator;
1551    use tracing::info;
1552
1553    #[cfg(not(miri))] // trace! asks for the time, which miri doesn't support
1554    use tracing_test::traced_test;
1555
1556    fn various_mock_executors() -> impl Iterator<Item = MockExecutor> {
1557        // This duplicates the part of the logic in MockRuntime::test_with_various which
1558        // relates to MockExecutor, because we don't have a MockRuntime::builder.
1559        // The only parameter to MockExecutor is its scheduling policy, so this seems fine.
1560        SchedulingPolicy::iter().map(|scheduling| {
1561            eprintln!("===== MockExecutor::with_scheduling({scheduling:?}) =====");
1562            MockExecutor::with_scheduling(scheduling)
1563        })
1564    }
1565
1566    #[cfg_attr(not(miri), traced_test)]
1567    #[test]
1568    fn simple() {
1569        let runtime = MockExecutor::default();
1570        let val = runtime.block_on(async { 42 });
1571        assert_eq!(val, 42);
1572    }
1573
1574    #[cfg_attr(not(miri), traced_test)]
1575    #[test]
1576    fn stall() {
1577        let runtime = MockExecutor::default();
1578
1579        runtime.block_on({
1580            let runtime = runtime.clone();
1581            async move {
1582                const N: usize = 3;
1583                let (mut txs, mut rxs): (Vec<_>, Vec<_>) =
1584                    (0..N).map(|_| mpsc::channel::<usize>(5)).unzip();
1585
1586                let mut rx_n = rxs.pop().unwrap();
1587
1588                for (i, mut rx) in rxs.into_iter().enumerate() {
1589                    runtime.spawn_identified(i, {
1590                        let mut txs = txs.clone();
1591                        async move {
1592                            loop {
1593                                eprintln!("task {i} rx...");
1594                                let v = rx.next().await.unwrap();
1595                                let nv = v + 1;
1596                                eprintln!("task {i} rx {v}, tx {nv}");
1597                                let v = nv;
1598                                txs[v].send(v).await.unwrap();
1599                            }
1600                        }
1601                    });
1602                }
1603
1604                dbg!();
1605                #[allow(deprecated)] // TODO(#2386)
1606                let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
1607
1608                dbg!();
1609                runtime.progress_until_stalled().await;
1610
1611                dbg!();
1612                #[allow(deprecated)] // TODO(#2386)
1613                let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
1614
1615                dbg!();
1616                txs[0].send(0).await.unwrap();
1617
1618                dbg!();
1619                runtime.progress_until_stalled().await;
1620
1621                dbg!();
1622                let r = rx_n.next().await;
1623                assert_eq!(r, Some(N - 1));
1624
1625                dbg!();
1626                #[allow(deprecated)] // TODO(#2386)
1627                let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
1628
1629                runtime.spawn_identified("tx", {
1630                    let txs = txs.clone();
1631                    async {
1632                        eprintln!("sending task...");
1633                        for (i, mut tx) in txs.into_iter().enumerate() {
1634                            eprintln!("sending 0 to {i}...");
1635                            tx.send(0).await.unwrap();
1636                        }
1637                        eprintln!("sending task done");
1638                    }
1639                });
1640
1641                runtime.debug_dump();
1642
1643                for i in 0..txs.len() {
1644                    eprintln!("main {i} wait stall...");
1645                    runtime.progress_until_stalled().await;
1646                    eprintln!("main {i} rx wait...");
1647                    let r = rx_n.next().await;
1648                    eprintln!("main {i} rx = {r:?}");
1649                    assert!(r == Some(0) || r == Some(N - 1));
1650                }
1651
1652                eprintln!("finishing...");
1653                runtime.progress_until_stalled().await;
1654                eprintln!("finished.");
1655            }
1656        });
1657    }
1658
1659    #[cfg_attr(not(miri), traced_test)]
1660    #[test]
1661    fn spawn_blocking() {
1662        let runtime = MockExecutor::default();
1663
1664        runtime.block_on({
1665            let runtime = runtime.clone();
1666            async move {
1667                let thr_1 = runtime.spawn_blocking(|| 42);
1668                let thr_2 = runtime.spawn_blocking(|| 99);
1669
1670                assert_eq!(thr_2.await, 99);
1671                assert_eq!(thr_1.await, 42);
1672            }
1673        });
1674    }
1675
1676    #[cfg_attr(not(miri), traced_test)]
1677    #[test]
1678    fn drop_reentrancy() {
1679        // Check that dropping a completed task future is done *outside* the data lock.
1680        // Involves a contrived future whose Drop impl reenters the executor.
1681        //
1682        // If `_fut_drop_late = fut` in execute_until_first_stall (the main loop)
1683        // is replaced with `drop(fut)` (dropping the future at the wrong moment),
1684        // we do indeed get deadlock, so this test case is working.
1685
1686        struct ReentersOnDrop {
1687            runtime: MockExecutor,
1688        }
1689        impl Future for ReentersOnDrop {
1690            type Output = ();
1691            fn poll(self: Pin<&mut Self>, _cx: &mut Context) -> Poll<()> {
1692                Poll::Ready(())
1693            }
1694        }
1695        impl Drop for ReentersOnDrop {
1696            fn drop(&mut self) {
1697                self.runtime
1698                    .spawn_identified("dummy", futures::future::ready(()));
1699            }
1700        }
1701
1702        for runtime in various_mock_executors() {
1703            runtime.block_on(async {
1704                runtime.spawn_identified("trapper", {
1705                    let runtime = runtime.clone();
1706                    ReentersOnDrop { runtime }
1707                });
1708            });
1709        }
1710    }
1711
1712    #[cfg_attr(not(miri), traced_test)]
1713    #[test]
1714    fn subthread_oneshot() {
1715        for runtime in various_mock_executors() {
1716            runtime.block_on(async {
1717                let (tx, rx) = oneshot::channel();
1718                info!("spawning subthread");
1719                let thr = runtime.subthread_spawn("thr1", {
1720                    let runtime = runtime.clone();
1721                    move || {
1722                        info!("subthread_block_on_future...");
1723                        let i = runtime.subthread_block_on_future(rx).unwrap();
1724                        info!("subthread_block_on_future => {i}");
1725                        i + 1
1726                    }
1727                });
1728                info!("main task sending");
1729                tx.send(12).unwrap();
1730                info!("main task sent");
1731                let r = thr.await.unwrap();
1732                info!("main task thr => {r}");
1733                assert_eq!(r, 13);
1734            });
1735        }
1736    }
1737
1738    #[cfg_attr(not(miri), traced_test)]
1739    #[test]
1740    fn subthread_pingpong() {
1741        for runtime in various_mock_executors() {
1742            runtime.block_on(async {
1743                let (mut i_tx, mut i_rx) = mpsc::channel(1);
1744                let (mut o_tx, mut o_rx) = mpsc::channel(1);
1745                info!("spawning subthread");
1746                let thr = runtime.subthread_spawn("thr", {
1747                    let runtime = runtime.clone();
1748                    move || {
1749                        while let Some(i) = {
1750                            info!("thread receiving ...");
1751                            runtime.subthread_block_on_future(i_rx.next())
1752                        } {
1753                            let o = i + 12;
1754                            info!("thread received {i}, sending {o}");
1755                            runtime.subthread_block_on_future(o_tx.send(o)).unwrap();
1756                            info!("thread sent {o}");
1757                        }
1758                        info!("thread exiting");
1759                        42
1760                    }
1761                });
1762                for i in 0..2 {
1763                    info!("main task sending {i}");
1764                    i_tx.send(i).await.unwrap();
1765                    info!("main task sent {i}");
1766                    let o = o_rx.next().await.unwrap();
1767                    info!("main task recv => {o}");
1768                    assert_eq!(o, i + 12);
1769                }
1770                info!("main task dropping sender");
1771                drop(i_tx);
1772                info!("main task awaiting thread");
1773                let r = thr.await.unwrap();
1774                info!("main task complete");
1775                assert_eq!(r, 42);
1776            });
1777        }
1778    }
1779}