1
//! Executor for running tests with mocked environment
2
//!
3
//! See [`MockExecutor`]
4

            
5
use std::any::Any;
6
use std::cell::Cell;
7
use std::collections::VecDeque;
8
use std::fmt::{self, Debug, Display};
9
use std::future::Future;
10
use std::io::{self, Write as _};
11
use std::iter;
12
use std::panic::{catch_unwind, panic_any, AssertUnwindSafe};
13
use std::pin::{pin, Pin};
14
use std::sync::{Arc, Mutex, MutexGuard, Weak};
15
use std::task::{Context, Poll, RawWaker, RawWakerVTable, Waker};
16

            
17
use futures::future::Map;
18
use futures::pin_mut;
19
use futures::task::{FutureObj, Spawn, SpawnError};
20
use futures::FutureExt as _;
21

            
22
use assert_matches::assert_matches;
23
use educe::Educe;
24
use itertools::Either::{self, *};
25
use itertools::{chain, izip};
26
use slotmap_careful::DenseSlotMap;
27
use std::backtrace::Backtrace;
28
use strum::EnumIter;
29

            
30
// NB: when using traced_test, the trace! and error! output here is generally suppressed
31
// in tests of other crates.  To see it, you can write something like this
32
// (in the dev-dependencies of the crate whose tests you're running):
33
//    tracing-test = { version = "0.2.4", features = ["no-env-filter"] }
34
use tracing::{error, trace};
35

            
36
use oneshot_fused_workaround::{self as oneshot, Canceled, Receiver};
37
use tor_error::error_report;
38
use tor_rtcompat::{Blocking, ToplevelBlockOn};
39

            
40
use Poll::*;
41
use TaskState::*;
42

            
43
/// Type-erased future, one for each of our (normal) tasks
44
type TaskFuture = FutureObj<'static, ()>;
45

            
46
/// Future for the argument to `block_on`, which is handled specially
47
type 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)]
83
pub 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)]
93
struct 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
104
mod 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
}
112
use 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
56452
#[derive(Educe, derive_more::Debug)]
139
#[educe(Default)]
140
struct Data {
141
    /// Tasks
142
    ///
143
    /// Includes tasks spawned with `spawn`,
144
    /// and also the future passed to `block_on`.
145
2
    #[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
2
    #[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
592
#[derive(Debug, Clone, Default, EnumIter)]
178
#[non_exhaustive]
179
pub 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`.
197
struct 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)]
223
enum 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)]
239
enum 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.
257
struct 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)]
286
struct 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)]
307
struct 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)]
323
enum 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)]
339
struct 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)]
343
struct SetAwake;
344

            
345
thread_local! {
346
    /// Identifies this thread.
347
    pub static THREAD_DESCRIPTOR: Cell<ThreadDescriptor> = const {
348
        Cell::new(ThreadDescriptor::Foreign)
349
    };
350
}
351

            
352
//---------- creation ----------
353

            
354
impl MockExecutor {
355
    /// Make a `MockExecutor` with default parameters
356
4
    pub fn new() -> Self {
357
4
        Self::default()
358
4
    }
359

            
360
    /// Make a `MockExecutor` with a specific `SchedulingPolicy`
361
7113
    pub fn with_scheduling(scheduling: SchedulingPolicy) -> Self {
362
7113
        Data {
363
7113
            scheduling,
364
7113
            ..Default::default()
365
7113
        }
366
7113
        .into()
367
7113
    }
368
}
369

            
370
impl From<Data> for MockExecutor {
371
7113
    fn from(data: Data) -> MockExecutor {
372
7113
        let shared = Shared {
373
7113
            data: Mutex::new(data),
374
7113
            thread_condvar: std::sync::Condvar::new(),
375
7113
        };
376
7113
        MockExecutor {
377
7113
            shared: Arc::new(shared),
378
7113
        }
379
7113
    }
380
}
381

            
382
//---------- spawning ----------
383

            
384
impl 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
186
    pub fn spawn_identified(
397
186
        &self,
398
186
        desc: impl Display,
399
186
        fut: impl Future<Output = ()> + Send + 'static,
400
186
    ) -> impl Debug + Clone + Send + 'static {
401
186
        self.spawn_internal(desc.to_string(), FutureObj::from(Box::new(fut)))
402
186
    }
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
16
    pub fn spawn_join<T: Debug + Send + 'static>(
409
16
        &self,
410
16
        desc: impl Display,
411
16
        fut: impl Future<Output = T> + Send + 'static,
412
16
    ) -> impl Future<Output = T> {
413
16
        let (tx, rx) = oneshot::channel();
414
16
        self.spawn_identified(desc, async move {
415
16
            let res = fut.await;
416
16
            tx.send(res)
417
16
                .expect("Failed to send future's output, did future panic?");
418
16
        });
419
16
        rx.map(|m| m.expect("Failed to receive future's output"))
420
16
    }
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
67235
    fn spawn_internal(&self, desc: String, fut: TaskFuture) -> TaskId {
427
67235
        let mut data = self.shared.lock();
428
67235
        data.insert_task(desc, TaskFutureInfo::Normal(fut))
429
67235
    }
430
}
431

            
432
impl Data {
433
    /// Insert a task given its `TaskFutureInfo` and return its `TaskId`.
434
74723
    fn insert_task(&mut self, desc: String, fut: TaskFutureInfo) -> TaskId {
435
74723
        let state = Awake;
436
74723
        let id = self.tasks.insert(Task {
437
74723
            state,
438
74723
            desc,
439
74723
            fut: Some(fut),
440
74723
        });
441
74723
        self.awake.push_back(id);
442
74723
        trace!("MockExecutor spawned {:?}={:?}", id, self.tasks[id]);
443
74723
        id
444
74723
    }
445
}
446

            
447
impl Spawn for MockExecutor {
448
64158
    fn spawn_obj(&self, future: TaskFuture) -> Result<(), SpawnError> {
449
64158
        self.spawn_internal("spawn_obj".into(), future);
450
64158
        Ok(())
451
64158
    }
452
}
453

            
454
impl MockExecutor {
455
    /// Implementation of `spawn_blocking` and `blocking_io`
456
4
    fn spawn_thread_inner<F, T>(&self, f: F) -> <Self as Blocking>::ThreadHandle<T>
457
4
    where
458
4
        F: FnOnce() -> T + Send + 'static,
459
4
        T: Send + 'static,
460
4
    {
461
4
        // For the mock executor, everything runs on the same thread.
462
4
        // If we need something more complex in the future, we can change this.
463
4
        let (tx, rx) = oneshot::channel();
464
4
        self.spawn_identified("Blocking".to_string(), async move {
465
4
            match tx.send(f()) {
466
4
                Ok(()) => (),
467
                Err(_) => panic!("Failed to send future's output, did future panic?"),
468
            }
469
4
        });
470
4
        rx.map(Box::new(|m| m.expect("Failed to receive future's output")))
471
4
    }
472
}
473

            
474
impl Blocking for MockExecutor {
475
    type ThreadHandle<T: Send + 'static> =
476
        Map<Receiver<T>, Box<dyn FnOnce(Result<T, Canceled>) -> T>>;
477

            
478
4
    fn spawn_blocking<F, T>(&self, f: F) -> Self::ThreadHandle<T>
479
4
    where
480
4
        F: FnOnce() -> T + Send + 'static,
481
4
        T: Send + 'static,
482
4
    {
483
        assert_matches!(
484
4
            THREAD_DESCRIPTOR.get(),
485
            ThreadDescriptor::Executor | ThreadDescriptor::Subthread(_),
486
 "MockExecutor::spawn_blocking_io only allowed from future or subthread, being run by this executor"
487
        );
488
4
        self.spawn_thread_inner(f)
489
4
    }
490

            
491
    fn reenter_block_on<F>(&self, future: F) -> F::Output
492
    where
493
        F: Future,
494
        F::Output: Send + 'static,
495
    {
496
        self.subthread_block_on_future(future)
497
    }
498

            
499
    fn blocking_io<F, T>(&self, f: F) -> impl Future<Output = T>
500
    where
501
        F: FnOnce() -> T + Send + 'static,
502
        T: Send + 'static,
503
    {
504
        assert_eq!(
505
            THREAD_DESCRIPTOR.get(),
506
            ThreadDescriptor::Executor,
507
            "MockExecutor::blocking_io only allowed from future being polled by this executor"
508
        );
509
        self.spawn_thread_inner(f)
510
    }
511
}
512

            
513
//---------- block_on ----------
514

            
515
impl ToplevelBlockOn for MockExecutor {
516
326
    fn block_on<F>(&self, input_fut: F) -> F::Output
517
326
    where
518
326
        F: Future,
519
326
    {
520
326
        let mut value: Option<F::Output> = None;
521
326

            
522
326
        // Box this just so that we can conveniently control precisely when it's dropped.
523
326
        // (We could do this with Option and Pin::set but that seems clumsier.)
524
326
        let mut input_fut = Box::pin(input_fut);
525
326

            
526
326
        let run_store_fut = {
527
326
            let value = &mut value;
528
326
            let input_fut = &mut input_fut;
529
326
            async {
530
326
                trace!("MockExecutor block_on future...");
531
326
                let t = input_fut.await;
532
326
                trace!("MockExecutor block_on future returned...");
533
326
                *value = Some(t);
534
326
                trace!("MockExecutor block_on future exiting.");
535
326
            }
536
        };
537

            
538
        {
539
326
            pin_mut!(run_store_fut);
540
326

            
541
326
            let main_id = self
542
326
                .shared
543
326
                .lock()
544
326
                .insert_task("main".into(), TaskFutureInfo::Main);
545
326
            trace!("MockExecutor {main_id:?} is task for block_on");
546
326
            self.execute_to_completion(run_store_fut);
547
326
        }
548
326

            
549
326
        #[allow(clippy::let_and_return)] // clarity
550
326
        let value = value.take().unwrap_or_else(|| {
551
            // eprintln can be captured by libtest, but the debug_dump goes to io::stderr.
552
            // use the latter, so that the debug dump is prefixed by this message.
553
            let _: io::Result<()> = writeln!(io::stderr(), "all futures blocked, crashing...");
554
            // write to tracing too, so the tracing log is clear about when we crashed
555
            error!("all futures blocked, crashing...");
556

            
557
            // Sequencing here is subtle.
558
            //
559
            // We should do the dump before dropping the input future, because the input
560
            // future is likely to own things that, when dropped, wake up other tasks,
561
            // rendering the dump inaccurate.
562
            //
563
            // But also, dropping the input future may well drop a ProgressUntilStalledFuture
564
            // which then reenters us.  More generally, we mustn't call user code
565
            // with the lock held.
566
            //
567
            // And, we mustn't panic with the data lock held.
568
            //
569
            // If value was Some, then this closure is dropped without being called,
570
            // which drops the future after it has yielded the value, which is correct.
571
            {
572
                let mut data = self.shared.lock();
573
                data.debug_dump();
574
            }
575
            drop(input_fut);
576

            
577
            panic!(
578
                r"
579
all futures blocked. waiting for the real world? or deadlocked (waiting for each other) ?
580
"
581
            );
582
326
        });
583
326

            
584
326
        value
585
326
    }
586
}
587

            
588
//---------- execution - core implementation ----------
589

            
590
impl MockExecutor {
591
    /// Keep polling tasks until nothing more can be done
592
    ///
593
    /// Ie, stop when `awake` is empty and `progressing_until_stalled` is `None`.
594
7480
    fn execute_to_completion(&self, mut main_fut: MainFuture) {
595
7480
        trace!("MockExecutor execute_to_completion...");
596
        loop {
597
1054259
            self.execute_until_first_stall(main_fut.as_mut());
598

            
599
            // Handle `progressing_until_stalled`
600
1046779
            let pus_waker = {
601
1054259
                let mut data = self.shared.lock();
602
1054259
                let pus = &mut data.progressing_until_stalled;
603
1054259
                trace!("MockExecutor execute_to_completion PUS={:?}", &pus);
604
1054259
                let Some(pus) = pus else {
605
                    // No progressing_until_stalled, we're actually done.
606
7480
                    break;
607
                };
608
1046779
                assert_eq!(
609
                    pus.finished, Pending,
610
                    "ProgressingUntilStalled finished twice?!"
611
                );
612
1046779
                pus.finished = Ready(());
613
1046779

            
614
1046779
                // Release the lock temporarily so that ActualWaker::clone doesn't deadlock
615
1046779
                let waker = pus
616
1046779
                    .waker
617
1046779
                    .take()
618
1046779
                    .expect("ProgressUntilStalledFuture not ever polled!");
619
1046779
                drop(data);
620
1046779
                let waker_copy = waker.clone();
621
1046779
                let mut data = self.shared.lock();
622
1046779

            
623
1046779
                let pus = &mut data.progressing_until_stalled;
624
1046779
                if let Some(double) = pus
625
1046779
                    .as_mut()
626
1046779
                    .expect("progressing_until_stalled updated under our feet!")
627
1046779
                    .waker
628
1046779
                    .replace(waker)
629
                {
630
                    panic!("double progressing_until_stalled.waker! {double:?}");
631
1046779
                }
632
1046779

            
633
1046779
                waker_copy
634
1046779
            };
635
1046779
            pus_waker.wake();
636
        }
637
7480
        trace!("MockExecutor execute_to_completion done");
638
7480
    }
639

            
640
    /// Keep polling tasks until `awake` is empty
641
    ///
642
    /// (Ignores `progressing_until_stalled` - so if one is active,
643
    /// will return when all other tasks have blocked.)
644
    ///
645
    /// # Panics
646
    ///
647
    /// Might malfunction or panic if called reentrantly
648
1054259
    fn execute_until_first_stall(&self, main_fut: MainFuture) {
649
1054259
        trace!("MockExecutor execute_until_first_stall ...");
650

            
651
1054259
        assert_eq!(
652
1054259
            THREAD_DESCRIPTOR.get(),
653
            ThreadDescriptor::Foreign,
654
            "MockExecutor executor re-entered"
655
        );
656
1054259
        THREAD_DESCRIPTOR.set(ThreadDescriptor::Executor);
657
1054259

            
658
1074998
        let r = catch_unwind(AssertUnwindSafe(|| self.executor_main_loop(main_fut)));
659
1054259

            
660
1054259
        THREAD_DESCRIPTOR.set(ThreadDescriptor::Foreign);
661
1054259

            
662
1054259
        match r {
663
1054259
            Ok(()) => trace!("MockExecutor execute_until_first_stall done."),
664
            Err(e) => {
665
                trace!("MockExecutor executor, or async task, panicked!");
666
                panic_any(e)
667
            }
668
        }
669
1054259
    }
670

            
671
    /// Keep polling tasks until `awake` is empty (inner, executor main loop)
672
    ///
673
    /// This is only called from [`MockExecutor::execute_until_first_stall`],
674
    /// so it could also be called `execute_until_first_stall_inner`.
675
    #[allow(clippy::cognitive_complexity)]
676
1054259
    fn executor_main_loop(&self, mut main_fut: MainFuture) {
677
        'outer: loop {
678
            // Take a `Awake` task off `awake` and make it `Asleep`
679
1382921
            let (id, mut fut) = 'inner: loop {
680
2438253
                let mut data = self.shared.lock();
681
2438253
                let Some(id) = data.schedule() else {
682
1054259
                    break 'outer;
683
                };
684
1383994
                let Some(task) = data.tasks.get_mut(id) else {
685
1073
                    trace!("MockExecutor {id:?} vanished");
686
1073
                    continue;
687
                };
688
1382921
                task.state = Asleep(vec![]);
689
1382921
                let fut = task.fut.take().expect("future missing from task!");
690
1382921
                break 'inner (id, fut);
691
1382921
            };
692
1382921

            
693
1382921
            // Poll the selected task
694
1382921
            trace!("MockExecutor {id:?} polling...");
695
1382921
            let waker = ActualWaker::make_waker(&self.shared, id);
696
1382921
            let mut cx = Context::from_waker(&waker);
697
1382921
            let r: Either<Poll<()>, IsSubthread> = match &mut fut {
698
83209
                TaskFutureInfo::Normal(fut) => Left(fut.poll_unpin(&mut cx)),
699
1299652
                TaskFutureInfo::Main => Left(main_fut.as_mut().poll(&mut cx)),
700
60
                TaskFutureInfo::Subthread => Right(IsSubthread),
701
            };
702

            
703
            // Deal with the returned `Poll`
704
            let _fut_drop_late;
705
            {
706
1382921
                let mut data = self.shared.lock();
707
1382921
                let task = data
708
1382921
                    .tasks
709
1382921
                    .get_mut(id)
710
1382921
                    .expect("task vanished while we were polling it");
711

            
712
1382861
                match r {
713
                    Left(Pending) => {
714
1345482
                        trace!("MockExecutor {id:?} -> Pending");
715
1345482
                        if task.fut.is_some() {
716
                            panic!("task reinserted while we polled it?!");
717
1345482
                        }
718
1345482
                        // The task might have been woken *by its own poll method*.
719
1345482
                        // That's why we set it to `Asleep` *earlier* rather than here.
720
1345482
                        // All we need to do is put the future back.
721
1345482
                        task.fut = Some(fut);
722
                    }
723
                    Left(Ready(())) => {
724
37379
                        trace!("MockExecutor {id:?} -> Ready");
725
                        // Oh, it finished!
726
                        // It might be in `awake`, but that's allowed to contain stale tasks,
727
                        // so we *don't* need to scan that list and remove it.
728
37379
                        data.tasks.remove(id);
729
37379
                        // It is important that we don't drop `fut` until we have released
730
37379
                        // the data lock, since it is an external type and might try to reenter
731
37379
                        // us (eg by calling spawn).  If we do that here, we risk deadlock.
732
37379
                        // So, move `fut` to a variable with scope outside the block with `data`.
733
37379
                        _fut_drop_late = fut;
734
                    }
735
                    Right(IsSubthread) => {
736
60
                        trace!("MockExecutor {id:?} -> Ready, waking Subthread");
737
                        // Task is a subthread, which has called thread_context_switch
738
                        // to switch to us.  We "poll" it by switching back.
739

            
740
                        // Put back `TFI::Subthread`, which was moved out temporarily, above.
741
60
                        task.fut = Some(fut);
742
60

            
743
60
                        self.shared.thread_context_switch(
744
60
                            data,
745
60
                            ThreadDescriptor::Executor,
746
60
                            ThreadDescriptor::Subthread(id),
747
60
                        );
748

            
749
                        // Now, if the Subthread still exists, that's because it's switched
750
                        // back to us, and is waiting in subthread_block_on_future again.
751
                        // Or it might have ended, in which case it's not in `tasks` any more.
752
                        // In any case we can go back to scheduling futures.
753
                    }
754
                }
755
            }
756
        }
757
1054259
    }
758
}
759

            
760
impl Data {
761
    /// Return the next task to run
762
    ///
763
    /// The task is removed from `awake`, but **`state` is not set to `Asleep`**.
764
    /// The caller must restore the invariant!
765
2438253
    fn schedule(&mut self) -> Option<TaskId> {
766
        use SchedulingPolicy as SP;
767
2438253
        match self.scheduling {
768
1223890
            SP::Stack => self.awake.pop_back(),
769
1214363
            SP::Queue => self.awake.pop_front(),
770
        }
771
2438253
    }
772
}
773

            
774
impl ActualWaker {
775
    /// Obtain a strong reference to the executor's data
776
6044289
    fn upgrade_data(&self) -> Option<Arc<Shared>> {
777
6044289
        self.data.upgrade()
778
6044289
    }
779

            
780
    /// Wake the task corresponding to this `ActualWaker`
781
    ///
782
    /// This is like `<Self as std::task::Wake>::wake()` but takes `&self`, not `Arc`
783
1824582
    fn wake(&self) {
784
1824582
        let Some(data) = self.upgrade_data() else {
785
            // The executor is gone!  Don't try to wake.
786
4
            return;
787
        };
788
1824578
        let mut data = data.lock();
789
1824578
        let data = &mut *data;
790
1824578
        trace!("MockExecutor {:?} wake", &self.id);
791
1824578
        let Some(task) = data.tasks.get_mut(self.id) else {
792
2754
            return;
793
        };
794
1821824
        task.set_awake(self.id, &mut data.awake);
795
1824582
    }
796

            
797
    /// Create and return a `Waker` for task `id`
798
1382949
    fn make_waker(shared: &Arc<Shared>, id: TaskId) -> Waker {
799
1382949
        ActualWaker {
800
1382949
            data: Arc::downgrade(shared),
801
1382949
            id,
802
1382949
        }
803
1382949
        .new_waker()
804
1382949
    }
805
}
806

            
807
//---------- "progress until stalled" functionality ----------
808

            
809
impl MockExecutor {
810
    /// Run tasks in the current executor until every other task is waiting
811
    ///
812
    /// # Panics
813
    ///
814
    /// Might malfunction or panic if more than one such call is running at once.
815
    ///
816
    /// (Ie, you must `.await` or drop the returned `Future`
817
    /// before calling this method again.)
818
    ///
819
    /// Must be called and awaited within a future being run by `self`.
820
1046779
    pub fn progress_until_stalled(&self) -> impl Future<Output = ()> {
821
1046779
        let mut data = self.shared.lock();
822
1046779
        assert!(
823
1046779
            data.progressing_until_stalled.is_none(),
824
            "progress_until_stalled called more than once"
825
        );
826
1046779
        trace!("MockExecutor progress_until_stalled...");
827
1046779
        data.progressing_until_stalled = Some(ProgressingUntilStalled {
828
1046779
            finished: Pending,
829
1046779
            waker: None,
830
1046779
        });
831
1046779
        ProgressUntilStalledFuture {
832
1046779
            shared: self.shared.clone(),
833
1046779
        }
834
1046779
    }
835
}
836

            
837
impl Future for ProgressUntilStalledFuture {
838
    type Output = ();
839

            
840
2093558
    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<()> {
841
2093558
        let waker = cx.waker().clone();
842
2093558
        let mut data = self.shared.lock();
843
2093558
        let pus = data.progressing_until_stalled.as_mut();
844
2093558
        trace!("MockExecutor progress_until_stalled polling... {:?}", &pus);
845
2093558
        let pus = pus.expect("ProgressingUntilStalled missing");
846
2093558
        pus.waker = Some(waker);
847
2093558
        pus.finished
848
2093558
    }
849
}
850

            
851
impl Drop for ProgressUntilStalledFuture {
852
1046779
    fn drop(&mut self) {
853
1046779
        self.shared.lock().progressing_until_stalled = None;
854
1046779
    }
855
}
856

            
857
//---------- (sub)threads ----------
858

            
859
impl MockExecutor {
860
    /// Spawn a "Subthread", for processing in a sync context
861
    ///
862
    /// `call` will be run on a separate thread, called a "Subthread".
863
    ///
864
    /// But it will **not run simultaneously** with the executor,
865
    /// nor with other Subthreads.
866
    /// So Subthreads are somewhat like coroutines.
867
    ///
868
    /// `call` must be capable of making progress without waiting for any other Subthreads.
869
    /// `call` may wait for async futures, using
870
    /// [`subthread_block_on_future`](MockExecutor::subthread_block_on_future).
871
    ///
872
    /// Subthreads may be used for cpubound activity,
873
    /// or synchronous IO (such as large volumes of disk activity),
874
    /// provided that the synchronous code will reliably make progress,
875
    /// without waiting (directly or indirectly) for any async task or Subthread -
876
    /// except via `subthread_block_on_future`.
877
    ///
878
    /// # Subthreads vs raw `std::thread` threads
879
    ///
880
    /// Programs using `MockExecutor` may use `std::thread` threads directly.
881
    /// However, this is not recommended.  There are severe limitations:
882
    ///
883
    ///  * Only a Subthread can re-enter the async context from sync code:
884
    ///    this must be done with
885
    ///    using [`subthread_block_on_future`](MockExecutor::subthread_block_on_future).
886
    ///    (Re-entering the executor with
887
    ///    [`block_on`](tor_rtcompat::ToplevelBlockOn::block_on)
888
    ///    is not allowed.)
889
    ///  * If async tasks want to suspend waiting for synchronous code,
890
    ///    the synchronous code must run on a Subthread.
891
    ///    This allows the `MockExecutor` to know when
892
    ///    that synchronous code is still making progress.
893
    ///    (This is needed for
894
    ///    [`progress_until_stalled`](MockExecutor::progress_until_stalled)
895
    ///    and the facilities which use it, such as
896
    ///    [`MockRuntime::advance_until_stalled`](crate::MockRuntime::advance_until_stalled).)
897
    ///  * Subthreads never run in parallel -
898
    ///    they only run as scheduled deterministically by the `MockExecutor`.
899
    ///    So using Subthreads eliminates a source of test nonndeterminism.
900
    ///    (Execution order is still varied due to explicitly varying the scheduling policy.)
901
    ///
902
    /// # Panics, abuse, and malfunctions
903
    ///
904
    /// If `call` panics and unwinds, `spawn_subthread` yields `Err`.
905
    /// The application code should to do something about it if this happens,
906
    /// typically, logging errors, tearing things down, or failing a test case.
907
    ///
908
    /// If the executor doesn't run, the subthread will not run either, and will remain stuck.
909
    /// (So, typically, if the thread supposed to run the executor panics,
910
    /// for example because a future or the executor itself panics,
911
    /// all the subthreads will become stuck - effectively, they'll be leaked.)
912
    ///
913
    /// `spawn_subthread` panics if OS thread spawning fails.
914
    /// (Like `std::thread::spawn()` does.)
915
    ///
916
    /// `MockExecutor`s will malfunction or panic if
917
    /// any executor invocation method (eg `block_on`) is called on a Subthread.
918
8
    pub fn subthread_spawn<T: Send + 'static>(
919
8
        &self,
920
8
        desc: impl Display,
921
8
        call: impl FnOnce() -> T + Send + 'static,
922
8
    ) -> impl Future<Output = Result<T, Box<dyn Any + Send>>> + Unpin + Send + Sync + 'static {
923
8
        let desc = desc.to_string();
924
8
        let (output_tx, output_rx) = oneshot::channel();
925
8

            
926
8
        // NB: we don't know which thread we're on!
927
8
        // In principle we might be on another Subthread.
928
8
        // So we can't context switch here.  That would be very confusing.
929
8
        //
930
8
        // Instead, we prepare the new Subthread as follows:
931
8
        //   - There is a task in the executor
932
8
        //   - The task is ready to be polled, whenever the executor decides to
933
8
        //   - The thread starts running right away, but immediately waits until it is scheduled
934
8
        // See `subthread_entrypoint`.
935
8

            
936
8
        {
937
8
            let mut data = self.shared.lock();
938
8
            let id = data.insert_task(desc.clone(), TaskFutureInfo::Subthread);
939
8

            
940
8
            let _: std::thread::JoinHandle<()> = std::thread::Builder::new()
941
8
                .name(desc)
942
8
                .spawn({
943
8
                    let shared = self.shared.clone();
944
8
                    move || shared.subthread_entrypoint(id, call, output_tx)
945
8
                })
946
8
                .expect("spawn failed");
947
8
        }
948
8

            
949
8
        output_rx.map(|r| {
950
8
            r.unwrap_or_else(|_: Canceled| panic!("Subthread cancelled but should be impossible!"))
951
8
        })
952
8
    }
953

            
954
    /// Call an async `Future` from a Subthread
955
    ///
956
    /// Blocks the Subthread, and arranges to run async tasks,
957
    /// including `fut`, until `fut` completes.
958
    ///
959
    /// `fut` is polled on the executor thread, not on the Subthread.
960
    /// (We may change that in the future, allowing passing a non-`Send` future.)
961
    ///
962
    /// # Panics, abuse, and malfunctions
963
    ///
964
    /// `subthread_block_on_future` will malfunction or panic
965
    /// if called on a thread that isn't a Subthread from the same `MockExecutor`
966
    /// (ie a thread made with [`spawn_subthread`](MockExecutor::subthread_spawn)).
967
    ///
968
    /// If `fut` itself panics, the executor will panic.
969
    ///
970
    /// If the executor isn't running, `subthread_block_on_future` will hang indefinitely.
971
    /// See `spawn_subthread`.
972
    #[allow(clippy::cognitive_complexity)] // Splitting this up would be worse
973
24
    pub fn subthread_block_on_future<T: Send + 'static>(&self, fut: impl Future<Output = T>) -> T {
974
24
        let id = match THREAD_DESCRIPTOR.get() {
975
24
            ThreadDescriptor::Subthread(id) => id,
976
            ThreadDescriptor::Executor => {
977
                panic!("subthread_block_on_future called from MockExecutor thread (async task?)")
978
            }
979
            ThreadDescriptor::Foreign => panic!(
980
    "subthread_block_on_future called on foreign thread (not spawned with spawn_subthread)"
981
            ),
982
        };
983
24
        trace!("MockExecutor thread {id:?}, subthread_block_on_future...");
984
24
        let mut fut = pin!(fut);
985
24

            
986
24
        // We yield once before the first poll, and once after Ready, to shake up the
987
24
        // execution order a bit, depending on the scheduling policy.
988
52
        let yield_ = |set_awake| self.shared.subthread_yield(id, set_awake);
989
24
        yield_(Some(SetAwake));
990

            
991
24
        let ret = loop {
992
            // Poll the provided future
993
28
            trace!("MockExecutor thread {id:?}, s.t._block_on_future polling...");
994
28
            let waker = ActualWaker::make_waker(&self.shared, id);
995
28
            let mut cx = Context::from_waker(&waker);
996
28
            let r: Poll<T> = fut.as_mut().poll(&mut cx);
997

            
998
28
            if let Ready(r) = r {
999
24
                trace!("MockExecutor thread {id:?}, s.t._block_on_future poll -> Ready");
24
                break r;
4
            }
4

            
4
            // Pending.  Switch back to the exeuctor thread.
4
            // When the future becomes ready, the Waker will be woken, waking the task,
4
            // so that the executor will "poll" us again.
4
            trace!("MockExecutor thread {id:?}, s.t._block_on_future poll -> Pending");
4
            yield_(None);
        };
24
        yield_(Some(SetAwake));
24

            
24
        trace!("MockExecutor thread {id:?}, subthread_block_on_future complete.");
24
        ret
24
    }
}
impl Shared {
    /// Main entrypoint function for a Subthread
    ///
    /// Entered on a new `std::thread` thread created by
    /// [`subthread_spawn`](MockExecutor::subthread_spawn).
    ///
    /// When `call` completes, sends its returned value `T` to `output_tx`.
8
    fn subthread_entrypoint<T: Send + 'static>(
8
        self: Arc<Self>,
8
        id: TaskId,
8
        call: impl FnOnce() -> T + Send + 'static,
8
        output_tx: oneshot::Sender<Result<T, Box<dyn Any + Send>>>,
8
    ) {
8
        THREAD_DESCRIPTOR.set(ThreadDescriptor::Subthread(id));
8
        trace!("MockExecutor thread {id:?}, entrypoint");
        // We start out Awake, but we wait for the executor to tell us to run.
        // This will be done the first time the task is "polled".
8
        {
8
            let data = self.lock();
8
            self.thread_context_switch_waitfor_instruction_to_run(
8
                data,
8
                ThreadDescriptor::Subthread(id),
8
            );
8
        }
8

            
8
        trace!("MockExecutor thread {id:?}, entering user code");
        // Run the user's actual thread function.
        // This will typically reenter us via subthread_block_on_future.
8
        let ret = catch_unwind(AssertUnwindSafe(call));
8

            
8
        trace!("MockExecutor thread {id:?}, completed user code");
        // This makes the return value from subthread_spawn ready.
        // It will be polled by the executor in due course, presumably.
8
        output_tx.send(ret).unwrap_or_else(
8
            #[allow(clippy::unnecessary_lazy_evaluations)]
8
            |_| {}, // receiver dropped, maybe executor dropped or something?
8
        );
8

            
8
        {
8
            let mut data = self.lock();
8

            
8
            // Never poll this task again (so never schedule this thread)
8
            let _: Task = data.tasks.remove(id).expect("Subthread task vanished!");
8

            
8
            // Tell the executor it is scheduled now.
8
            // We carry on exiting, in parallel (holding the data lock).
8
            self.thread_context_switch_send_instruction_to_run(
8
                &mut data,
8
                ThreadDescriptor::Subthread(id),
8
                ThreadDescriptor::Executor,
8
            );
8
        }
8
    }
    /// Yield back to the executor from a subthread
    ///
    /// Checks that things are in order
    /// (in particular, that this task is in the data structure as a subhtread)
    /// and switches to the executor thread.
    ///
    /// The caller must arrange that the task gets woken.
    ///
    /// With [`SetAwake`], sets our task awake, so that we'll be polled
    /// again as soon as we get to the top of the executor's queue.
    /// Otherwise, we'll be reentered after someone wakes a [`Waker`] for the task.
52
    fn subthread_yield(&self, us: TaskId, set_awake: Option<SetAwake>) {
52
        let mut data = self.lock();
52
        {
52
            let data = &mut *data;
52
            let task = data.tasks.get_mut(us).expect("Subthread task vanished!");
52
            match &task.fut {
52
                Some(TaskFutureInfo::Subthread) => {}
                other => panic!("subthread_block_on_future but TFI {other:?}"),
            };
52
            if let Some(SetAwake) = set_awake {
48
                task.set_awake(us, &mut data.awake);
48
            }
        }
52
        self.thread_context_switch(
52
            data,
52
            ThreadDescriptor::Subthread(us),
52
            ThreadDescriptor::Executor,
52
        );
52
    }
    /// Switch from (sub)thread `us` to (sub)thread `them`
    ///
    /// Returns when someone calls `thread_context_switch(.., us)`.
112
    fn thread_context_switch(
112
        &self,
112
        mut data: MutexGuard<Data>,
112
        us: ThreadDescriptor,
112
        them: ThreadDescriptor,
112
    ) {
112
        trace!("MockExecutor thread {us:?}, switching to {them:?}");
112
        self.thread_context_switch_send_instruction_to_run(&mut data, us, them);
112
        self.thread_context_switch_waitfor_instruction_to_run(data, us);
112
    }
    /// Instruct the (sub)thread `them` to run
    ///
    /// Update `thread_to_run`, which will wake up `them`'s
    /// call to `thread_context_switch_waitfor_instruction_to_run`.
    ///
    /// Must be called from (sub)thread `us`.
    /// Part of `thread_context_switch`, not normally called directly.
120
    fn thread_context_switch_send_instruction_to_run(
120
        &self,
120
        data: &mut MutexGuard<Data>,
120
        us: ThreadDescriptor,
120
        them: ThreadDescriptor,
120
    ) {
120
        assert_eq!(data.thread_to_run, us);
120
        data.thread_to_run = them;
120
        self.thread_condvar.notify_all();
120
    }
    /// Await an instruction for this thread, `us`, to run
    ///
    /// Waits for `thread_to_run` to be `us`,
    /// waiting for `thread_condvar` as necessary.
    ///
    /// Part of `thread_context_switch`, not normally called directly.
120
    fn thread_context_switch_waitfor_instruction_to_run(
120
        &self,
120
        data: MutexGuard<Data>,
120
        us: ThreadDescriptor,
120
    ) {
120
        #[allow(let_underscore_lock)]
120
        let _: MutexGuard<_> = self
120
            .thread_condvar
300
            .wait_while(data, |data| {
240
                let live = data.thread_to_run;
240
                let resume = live == us;
240
                if resume {
120
                    trace!("MockExecutor thread {us:?}, resuming");
                } else {
120
                    trace!("MockExecutor thread {us:?}, waiting for {live:?}");
                }
                // We're in `.wait_while`, not `.wait_until`.  Confusing.
240
                !resume
300
            })
120
            .expect("data lock poisoned");
120
    }
}
//---------- ancillary and convenience functions ----------
/// Trait to let us assert at compile time that something is nicely `Sync` etc.
#[allow(dead_code)] // yes, we don't *use* anything from this trait
trait EnsureSyncSend: Sync + Send + 'static {}
impl EnsureSyncSend for ActualWaker {}
impl EnsureSyncSend for MockExecutor {}
impl MockExecutor {
    /// Return the number of tasks running in this executor
    ///
    /// One possible use is for a test case to check that task(s)
    /// that ought to have exited, have indeed done so.
    ///
    /// In the usual case, the answer will be at least 1,
    /// because it counts the future passed to
    /// [`block_on`](MockExecutor::block_on)
    /// (perhaps via [`MockRuntime::test_with_various`](crate::MockRuntime::test_with_various)).
204
    pub fn n_tasks(&self) -> usize {
204
        self.shared.lock().tasks.len()
204
    }
}
impl Shared {
    /// Lock and obtain the guard
    ///
    /// Convenience method which panics on poison
16228610
    fn lock(&self) -> MutexGuard<Data> {
16228610
        self.data.lock().expect("data lock poisoned")
16228610
    }
}
impl Task {
    /// Set task `id` to `Awake` and arrange that it will be polled.
1821872
    fn set_awake(&mut self, id: TaskId, data_awake: &mut VecDeque<TaskId>) {
1821872
        match self.state {
481695
            Awake => {}
1340177
            Asleep(_) => {
1340177
                self.state = Awake;
1340177
                data_awake.push_back(id);
1340177
            }
        }
1821872
    }
}
//---------- ActualWaker as RawWaker ----------
/// Using [`ActualWaker`] in a [`RawWaker`]
///
/// We need to make a
/// [`Waker`] (the safe, type-erased, waker, used by actual futures)
/// which contains an
/// [`ActualWaker`] (our actual waker implementation, also safe).
///
/// `std` offers `Waker::from<Arc<impl Wake>>`.
/// But we want a bespoke `Clone` implementation, so we don't want to use `Arc`.
///
/// So instead, we implement the `RawWaker` API in terms of `ActualWaker`.
/// We keep the `ActualWaker` in a `Box`, and actually `clone` it (and the `Box`).
///
/// SAFETY
///
///  * The data pointer is `Box::<ActualWaker>::into_raw()`
///  * We share these when we clone
///  * No-one is allowed `&mut ActualWaker` unless there are no other clones
///  * So we may make references `&ActualWaker`
impl ActualWaker {
    /// Wrap up an [`ActualWaker`] as a type-erased [`Waker`] for passing to futures etc.
1382949
    fn new_waker(self) -> Waker {
1382949
        unsafe { Waker::from_raw(self.raw_new()) }
1382949
    }
    /// Helper: wrap up an [`ActualWaker`] as a [`RawWaker`].
5602656
    fn raw_new(self) -> RawWaker {
5602656
        let self_: Box<ActualWaker> = self.into();
5602656
        let self_: *mut ActualWaker = Box::into_raw(self_);
5602656
        let self_: *const () = self_ as _;
5602656
        RawWaker::new(self_, &RAW_WAKER_VTABLE)
5602656
    }
    /// Implementation of [`RawWakerVTable`]'s `clone`
4219707
    unsafe fn raw_clone(self_: *const ()) -> RawWaker {
4219707
        let self_: *const ActualWaker = self_ as _;
4219707
        let self_: &ActualWaker = self_.as_ref().unwrap_unchecked();
4219707
        let copy: ActualWaker = self_.clone();
4219707
        copy.raw_new()
4219707
    }
    /// Implementation of [`RawWakerVTable`]'s `wake`
1336767
    unsafe fn raw_wake(self_: *const ()) {
1336767
        Self::raw_wake_by_ref(self_);
1336767
        Self::raw_drop(self_);
1336767
    }
    /// Implementation of [`RawWakerVTable`]'s `wake_ref_by`
1824582
    unsafe fn raw_wake_by_ref(self_: *const ()) {
1824582
        let self_: *const ActualWaker = self_ as _;
1824582
        let self_: &ActualWaker = self_.as_ref().unwrap_unchecked();
1824582
        self_.wake();
1824582
    }
    /// Implementation of [`RawWakerVTable`]'s `drop`
5579196
    unsafe fn raw_drop(self_: *const ()) {
5579196
        let self_: *mut ActualWaker = self_ as _;
5579196
        let self_: Box<ActualWaker> = Box::from_raw(self_);
5579196
        drop(self_);
5579196
    }
}
/// vtable for `Box<ActualWaker>` as `RawWaker`
//
// This ought to be in the impl block above, but
//   "associated `static` items are not allowed"
static RAW_WAKER_VTABLE: RawWakerVTable = RawWakerVTable::new(
    ActualWaker::raw_clone,
    ActualWaker::raw_wake,
    ActualWaker::raw_wake_by_ref,
    ActualWaker::raw_drop,
);
//---------- Sleep location tracking and dumping ----------
/// We record "where a future went to sleep" as (just) a backtrace
///
/// This type alias allows us to mock `Backtrace` for miri.
/// (It also insulates from future choices about sleep location representation.0
#[cfg(not(miri))]
type SleepLocation = Backtrace;
impl Data {
    /// Dump tasks and their sleep location backtraces
2
    fn dump_backtraces(&self, f: &mut fmt::Formatter) -> fmt::Result {
8
        for (id, task) in self.tasks.iter() {
12
            let prefix = |f: &mut fmt::Formatter| write!(f, "{id:?}={task:?}: ");
8
            match &task.state {
                Awake => {
2
                    prefix(f)?;
2
                    writeln!(f, "awake")?;
                }
6
                Asleep(locs) => {
6
                    let n = locs.len();
6
                    for (i, loc) in locs.iter().enumerate() {
6
                        prefix(f)?;
6
                        writeln!(f, "asleep, backtrace {i}/{n}:\n{loc}",)?;
                    }
6
                    if n == 0 {
                        prefix(f)?;
                        writeln!(f, "asleep, no backtraces, Waker never cloned, stuck!",)?;
6
                    }
                }
            }
        }
2
        writeln!(
2
            f,
2
            "\nNote: there might be spurious traces, see docs for MockExecutor::debug_dump\n"
2
        )?;
2
        Ok(())
2
    }
}
/// Track sleep locations via `<Waker as Clone>`.
///
/// See [`MockExecutor::debug_dump`] for the explanation.
impl Clone for ActualWaker {
4219707
    fn clone(&self) -> Self {
4219707
        let id = self.id;
4219707
        if let Some(data) = self.upgrade_data() {
            // If the executor is gone, there is nothing to adjust
4219707
            let mut data = data.lock();
4219707
            if let Some(task) = data.tasks.get_mut(self.id) {
4219707
                match &mut task.state {
236181
                    Awake => trace!("MockExecutor cloned waker for awake task {id:?}"),
3983526
                    Asleep(locs) => locs.push(SleepLocation::force_capture()),
                }
            } else {
                trace!("MockExecutor cloned waker for dead task {id:?}");
            }
        }
4219707
        ActualWaker {
4219707
            data: self.data.clone(),
4219707
            id,
4219707
        }
4219707
    }
}
//---------- API for full debug dump ----------
/// Debugging dump of a `MockExecutor`'s state
///
/// Returned by [`MockExecutor::as_debug_dump`]
//
// Existence implies backtraces have been resolved
//
// We use `Either` so that we can also use this internally when we have &mut Data.
pub struct DebugDump<'a>(Either<&'a Data, MutexGuard<'a, Data>>);
impl MockExecutor {
    /// Dump the executor's state including backtraces of waiting tasks, to stderr
    ///
    /// This is considerably more extensive than simply
    /// `MockExecutor as Debug`.
    ///
    /// (This is a convenience method, which wraps
    /// [`MockExecutor::as_debug_dump()`].
    ///
    /// ### Backtrace salience (possible spurious traces)
    ///
    /// **Summary**
    ///
    /// The technique used to capture backtraces when futures sleep is not 100% exact.
    /// It will usually show all the actual sleeping sites,
    /// but it might also show other backtraces which were part of
    /// the implementation of some complex relevant future.
    ///
    /// **Details**
    ///
    /// When a future's implementation wants to sleep,
    /// it needs to record the [`Waker`] (from the [`Context`])
    /// so that the "other end" can call `.wake()` on it later,
    /// when the future should be woken.
    ///
    /// Since `Context.waker()` gives `&Waker`, borrowed from the `Context`,
    /// the future must clone the `Waker`,
    /// and it must do so in within the `poll()` call.
    ///
    /// A future which is waiting in a `select!` will typically
    /// show multiple traces, one for each branch.
    /// But,
    /// if a future sleeps on one thing, and then when polled again later,
    /// sleeps on something different, without waking up in between,
    /// both backtrace locations will be shown.
    /// And,
    /// a complicated future contraption *might* clone the `Waker` more times.
    /// So not every backtrace will necessarily be informative.
    ///
    /// ### Panics
    ///
    /// Panics on write errors.
2
    pub fn debug_dump(&self) {
2
        self.as_debug_dump().to_stderr();
2
    }
    /// Dump the executor's state including backtraces of waiting tasks
    ///
    /// This is considerably more extensive than simply
    /// `MockExecutor as Debug`.
    ///
    /// Returns an object for formatting with [`Debug`].
    /// To simply print the dump to stderr (eg in a test),
    /// use [`.debug_dump()`](MockExecutor::debug_dump).
    ///
    /// **Backtrace salience (possible spurious traces)** -
    /// see [`.debug_dump()`](MockExecutor::debug_dump).
2
    pub fn as_debug_dump(&self) -> DebugDump {
2
        let data = self.shared.lock();
2
        DebugDump(Right(data))
2
    }
}
impl Data {
    /// Convenience function: dump including backtraces, to stderr
    fn debug_dump(&mut self) {
        DebugDump(Left(self)).to_stderr();
    }
}
impl DebugDump<'_> {
    /// Convenience function: dump tasks and backtraces to stderr
    #[allow(clippy::wrong_self_convention)] // "to_stderr" doesn't mean "convert to stderr"
2
    fn to_stderr(self) {
2
        write!(io::stderr().lock(), "{:?}", self)
2
            .unwrap_or_else(|e| error_report!(e, "failed to write debug dump to stderr"));
2
    }
}
//---------- bespoke Debug impls ----------
impl Debug for DebugDump<'_> {
2
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2
        let self_: &Data = &self.0;
2

            
2
        writeln!(f, "MockExecutor state:\n{self_:#?}")?;
2
        writeln!(f, "MockExecutor task dump:")?;
2
        self_.dump_backtraces(f)?;
2
        Ok(())
2
    }
}
// See `impl Debug for Data` for notes on the output
impl Debug for Task {
122
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
122
        let Task { desc, state, fut } = self;
122
        write!(f, "{:?}", desc)?;
122
        write!(f, "=")?;
118
        match fut {
4
            None => write!(f, "P")?,
80
            Some(TaskFutureInfo::Normal(_)) => write!(f, "f")?,
30
            Some(TaskFutureInfo::Main) => write!(f, "m")?,
8
            Some(TaskFutureInfo::Subthread) => write!(f, "T")?,
        }
122
        match state {
110
            Awake => write!(f, "W")?,
12
            Asleep(locs) => write!(f, "s{}", locs.len())?,
        };
122
        Ok(())
122
    }
}
/// Helper: `Debug`s as a list of tasks, given the `Data` for lookups and a list of the ids
///
/// `Task`s in `Data` are printed as `Ti(ID)"SPEC"=FLAGS"`.
///
/// `FLAGS` are:
///
///  * `T`: this task is for a Subthread (from subthread_spawn).
///  * `P`: this task is being polled (its `TaskFutureInfo` is absent)
///  * `f`: this is a normal task with a future and its future is present in `Data`
///  * `m`: this is the main task from `block_on`
///
///  * `W`: the task is awake
///  * `s<n>`: the task is asleep, and `<n>` is the number of recorded sleeping locations
//
// We do it this way because the naive dump from derive is very expansive
// and makes it impossible to see the wood for the trees.
// This very compact representation it easier to find a task of interest in the output.
//
// This is implemented in `impl Debug for Task`.
//
//
// rustc doesn't think automatically-derived Debug impls count for whether a thing is used.
// This has caused quite some fallout.  https://github.com/rust-lang/rust/pull/85200
// I think derive_more emits #[automatically_derived], so that even though we use this
// in our Debug impl, that construction is unused.
#[allow(dead_code)]
struct DebugTasks<'d, F>(&'d Data, F);
// See `impl Debug for Data` for notes on the output
impl<F, I> Debug for DebugTasks<'_, F>
where
    F: Fn() -> I,
    I: Iterator<Item = TaskId>,
{
4
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
4
        let DebugTasks(data, ids) = self;
10
        for (id, delim) in izip!(ids(), chain!(iter::once(""), iter::repeat(" ")),) {
10
            write!(f, "{delim}{id:?}")?;
10
            match data.tasks.get(id) {
                None => write!(f, "-")?,
10
                Some(task) => write!(f, "={task:?}")?,
            }
        }
4
        Ok(())
4
    }
}
/// Mock `Backtrace` for miri
///
/// See also the not-miri `type SleepLocation`, alias above.
#[cfg(miri)]
mod miri_sleep_location {
    #[derive(Debug, derive_more::Display)]
    #[display("<SleepLocation>")]
    pub(super) struct SleepLocation {}
    impl SleepLocation {
        pub(super) fn force_capture() -> Self {
            SleepLocation {}
        }
    }
}
#[cfg(miri)]
use miri_sleep_location::SleepLocation;
#[cfg(test)]
mod test {
    // @@ begin test lint list maintained by maint/add_warning @@
    #![allow(clippy::bool_assert_comparison)]
    #![allow(clippy::clone_on_copy)]
    #![allow(clippy::dbg_macro)]
    #![allow(clippy::mixed_attributes_style)]
    #![allow(clippy::print_stderr)]
    #![allow(clippy::print_stdout)]
    #![allow(clippy::single_char_pattern)]
    #![allow(clippy::unwrap_used)]
    #![allow(clippy::unchecked_duration_subtraction)]
    #![allow(clippy::useless_vec)]
    #![allow(clippy::needless_pass_by_value)]
    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
    use super::*;
    use futures::channel::mpsc;
    use futures::{SinkExt as _, StreamExt as _};
    use strum::IntoEnumIterator;
    use tracing::info;
    #[cfg(not(miri))] // trace! asks for the time, which miri doesn't support
    use tracing_test::traced_test;
    fn various_mock_executors() -> impl Iterator<Item = MockExecutor> {
        // This duplicates the part of the logic in MockRuntime::test_with_various which
        // relates to MockExecutor, because we don't have a MockRuntime::builder.
        // The only parameter to MockExecutor is its scheduling policy, so this seems fine.
        SchedulingPolicy::iter().map(|scheduling| {
            eprintln!("===== MockExecutor::with_scheduling({scheduling:?}) =====");
            MockExecutor::with_scheduling(scheduling)
        })
    }
    #[cfg_attr(not(miri), traced_test)]
    #[test]
    fn simple() {
        let runtime = MockExecutor::default();
        let val = runtime.block_on(async { 42 });
        assert_eq!(val, 42);
    }
    #[cfg_attr(not(miri), traced_test)]
    #[test]
    fn stall() {
        let runtime = MockExecutor::default();
        runtime.block_on({
            let runtime = runtime.clone();
            async move {
                const N: usize = 3;
                let (mut txs, mut rxs): (Vec<_>, Vec<_>) =
                    (0..N).map(|_| mpsc::channel::<usize>(5)).unzip();
                let mut rx_n = rxs.pop().unwrap();
                for (i, mut rx) in rxs.into_iter().enumerate() {
                    runtime.spawn_identified(i, {
                        let mut txs = txs.clone();
                        async move {
                            loop {
                                eprintln!("task {i} rx...");
                                let v = rx.next().await.unwrap();
                                let nv = v + 1;
                                eprintln!("task {i} rx {v}, tx {nv}");
                                let v = nv;
                                txs[v].send(v).await.unwrap();
                            }
                        }
                    });
                }
                dbg!();
                let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
                dbg!();
                runtime.progress_until_stalled().await;
                dbg!();
                let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
                dbg!();
                txs[0].send(0).await.unwrap();
                dbg!();
                runtime.progress_until_stalled().await;
                dbg!();
                let r = rx_n.next().await;
                assert_eq!(r, Some(N - 1));
                dbg!();
                let _: mpsc::TryRecvError = rx_n.try_next().unwrap_err();
                runtime.spawn_identified("tx", {
                    let txs = txs.clone();
                    async {
                        eprintln!("sending task...");
                        for (i, mut tx) in txs.into_iter().enumerate() {
                            eprintln!("sending 0 to {i}...");
                            tx.send(0).await.unwrap();
                        }
                        eprintln!("sending task done");
                    }
                });
                runtime.debug_dump();
                for i in 0..txs.len() {
                    eprintln!("main {i} wait stall...");
                    runtime.progress_until_stalled().await;
                    eprintln!("main {i} rx wait...");
                    let r = rx_n.next().await;
                    eprintln!("main {i} rx = {r:?}");
                    assert!(r == Some(0) || r == Some(N - 1));
                }
                eprintln!("finishing...");
                runtime.progress_until_stalled().await;
                eprintln!("finished.");
            }
        });
    }
    #[cfg_attr(not(miri), traced_test)]
    #[test]
    fn spawn_blocking() {
        let runtime = MockExecutor::default();
        runtime.block_on({
            let runtime = runtime.clone();
            async move {
                let thr_1 = runtime.spawn_blocking(|| 42);
                let thr_2 = runtime.spawn_blocking(|| 99);
                assert_eq!(thr_2.await, 99);
                assert_eq!(thr_1.await, 42);
            }
        });
    }
    #[cfg_attr(not(miri), traced_test)]
    #[test]
    fn drop_reentrancy() {
        // Check that dropping a completed task future is done *outside* the data lock.
        // Involves a contrived future whose Drop impl reenters the executor.
        //
        // If `_fut_drop_late = fut` in execute_until_first_stall (the main loop)
        // is replaced with `drop(fut)` (dropping the future at the wrong moment),
        // we do indeed get deadlock, so this test case is working.
        struct ReentersOnDrop {
            runtime: MockExecutor,
        }
        impl Future for ReentersOnDrop {
            type Output = ();
            fn poll(self: Pin<&mut Self>, _cx: &mut Context) -> Poll<()> {
                Poll::Ready(())
            }
        }
        impl Drop for ReentersOnDrop {
            fn drop(&mut self) {
                self.runtime
                    .spawn_identified("dummy", futures::future::ready(()));
            }
        }
        for runtime in various_mock_executors() {
            runtime.block_on(async {
                runtime.spawn_identified("trapper", {
                    let runtime = runtime.clone();
                    ReentersOnDrop { runtime }
                });
            });
        }
    }
    #[cfg_attr(not(miri), traced_test)]
    #[test]
    fn subthread_oneshot() {
        for runtime in various_mock_executors() {
            runtime.block_on(async {
                let (tx, rx) = oneshot::channel();
                info!("spawning subthread");
                let thr = runtime.subthread_spawn("thr1", {
                    let runtime = runtime.clone();
                    move || {
                        info!("subthread_block_on_future...");
                        let i = runtime.subthread_block_on_future(rx).unwrap();
                        info!("subthread_block_on_future => {i}");
                        i + 1
                    }
                });
                info!("main task sending");
                tx.send(12).unwrap();
                info!("main task sent");
                let r = thr.await.unwrap();
                info!("main task thr => {r}");
                assert_eq!(r, 13);
            });
        }
    }
    #[cfg_attr(not(miri), traced_test)]
    #[test]
    #[allow(clippy::cognitive_complexity)] // It's is not that complicated, really.
    fn subthread_pingpong() {
        for runtime in various_mock_executors() {
            runtime.block_on(async {
                let (mut i_tx, mut i_rx) = mpsc::channel(1);
                let (mut o_tx, mut o_rx) = mpsc::channel(1);
                info!("spawning subthread");
                let thr = runtime.subthread_spawn("thr", {
                    let runtime = runtime.clone();
                    move || {
                        while let Some(i) = {
                            info!("thread receiving ...");
                            runtime.subthread_block_on_future(i_rx.next())
                        } {
                            let o = i + 12;
                            info!("thread received {i}, sending {o}");
                            runtime.subthread_block_on_future(o_tx.send(o)).unwrap();
                            info!("thread sent {o}");
                        }
                        info!("thread exiting");
                        42
                    }
                });
                for i in 0..2 {
                    info!("main task sending {i}");
                    i_tx.send(i).await.unwrap();
                    info!("main task sent {i}");
                    let o = o_rx.next().await.unwrap();
                    info!("main task recv => {o}");
                    assert_eq!(o, i + 12);
                }
                info!("main task dropping sender");
                drop(i_tx);
                info!("main task awaiting thread");
                let r = thr.await.unwrap();
                info!("main task complete");
                assert_eq!(r, 42);
            });
        }
    }
}