hatchet-client 0.1.0

Rust SDK for Hatchet: run workers and trigger tasks
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
//! Worker-side eviction: handing a durable run that is only *waiting* back to
//! the engine, so the `durable` slot it is holding can run something else.
//!
//! Three pieces, deliberately apart:
//!
//! * [`EvictionPolicy`] — what a task declares, and the only public part.
//! * [`EvictionBook`] — the worker's ledger of the durable runs it is holding
//!   and which of them are waiting, kept by [`WaitingGuard`]s so a cancelled
//!   or panicking handler cannot leave a phantom waiter behind.
//! * [`EvictionBook::candidate`] — the rule, as a function that only *reads*
//!   the ledger and is handed the time rather than reading a clock. It can
//!   therefore be tested to the second without a fake clock or a mock engine.
//!
//! The rules are the official Go SDK's, behaviour for behaviour
//! (`sdks/go/internal/eviction/cache.go:179-296`): a wait past its TTL goes
//! first, then — only if nothing is past its TTL — a run that a full worker
//! cannot afford, and among equals the lowest priority and then the longest
//! wait.

use std::collections::{HashMap, HashSet};
use std::sync::{Arc, Mutex, MutexGuard, PoisonError};
use std::time::Duration;

use tokio::time::Instant;
use tokio_util::sync::CancellationToken;

use crate::durable::stream::DurableStream;

/// When a durable run that is waiting may be taken off this worker.
///
/// A durable run parked on the engine — sleeping, waiting for an event,
/// waiting for a child — is doing no work, but it is still holding one of the
/// worker's `durable` slots
/// ([`WorkerBuilder::durable_slots`](crate::WorkerBuilder::durable_slots)). An
/// eviction policy lets the worker hand such a run back: the slot is freed at
/// once, and the engine assigns the task again when what it was waiting for
/// happens. The handler then runs **from the top** with a new
/// [`invocation_count`](crate::DurableContext::invocation_count), replaying
/// its durable log — which is why eviction is safe exactly when a replay is
/// (see [`DurableContext`](crate::DurableContext)).
///
/// Worker-side only: nothing about the policy reaches the engine except the
/// eviction itself, and a task carrying one registers byte for byte as it
/// would without.
///
/// Only a durable task may carry one. A policy on an ordinary
/// [`handler`](crate::TaskBuilder::handler) is an
/// [`Error::InvalidDeclaration`](crate::Error::InvalidDeclaration) at
/// registration rather than a policy that quietly never fires, because it
/// nearly always means the handler was meant to be a
/// [`durable_handler`](crate::TaskBuilder::durable_handler).
///
/// ```
/// use std::time::Duration;
///
/// use hatchet_client::{EvictionPolicy, TaskBuilder};
///
/// let approve = TaskBuilder::<(), ()>::new("approve")
///     .eviction_policy(EvictionPolicy::ttl(Duration::from_secs(5 * 60)).priority(-1))
///     .durable_handler(|ctx, _input| async move {
///         ctx.wait_for_event("approved").await?;
///         Ok(())
///     });
/// # let _ = approve;
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
#[must_use = "an eviction policy changes nothing until a task is declared with it"]
pub struct EvictionPolicy {
    ttl: Duration,
    allow_capacity_eviction: bool,
    priority: i32,
}

impl EvictionPolicy {
    /// Evicts this run once it has been waiting `ttl` without a break.
    ///
    /// The clock starts when the run enters a wait and stops when it leaves
    /// one, so a handler that waits, works, and waits again starts over; waits
    /// nested inside one another count once, dated from the outermost. It is
    /// *not* measured from when the run started, which is the whole point —
    /// a run that is busy is never evicted, however long it has been running.
    ///
    /// [`Duration::ZERO`] means "never on time alone", which is what the rule
    /// does with it; registering a task with a zero TTL is refused, though,
    /// since a policy that can only ever fire under capacity pressure is
    /// almost never what was meant.
    pub fn ttl(ttl: Duration) -> Self {
        Self {
            ttl,
            ..Self::default()
        }
    }

    /// Whether this run may *also* be evicted when every durable slot on the
    /// worker is taken by a waiting run, even though its TTL has not run out.
    ///
    /// `true` by default. Set it to `false` for a run that should be handed
    /// back only on its own schedule.
    pub fn allow_capacity_eviction(mut self, yes: bool) -> Self {
        self.allow_capacity_eviction = yes;
        self
    }

    /// Which runs go first when several are eligible at once: **lower goes
    /// first**. `0` by default, and negative values are allowed.
    ///
    /// Runs of equal priority are ordered by their wait: the one that has been
    /// waiting longest goes first.
    pub fn priority(mut self, priority: i32) -> Self {
        self.priority = priority;
        self
    }

    /// Whether this policy's TTL is one the rule can ever act on.
    pub(crate) fn has_ttl(&self) -> bool {
        self.ttl > Duration::ZERO
    }
}

impl Default for EvictionPolicy {
    /// Fifteen minutes, capacity eviction allowed, priority zero — the
    /// official Go SDK's defaults (`sdks/go/eviction_policy.go:21-25`).
    fn default() -> Self {
        Self {
            ttl: Duration::from_secs(15 * 60),
            allow_capacity_eviction: true,
            priority: 0,
        }
    }
}

/// How the eviction manager runs.
///
/// The official Go SDK's `DefaultDurableEvictionConfig`
/// (`sdks/go/internal/eviction/manager.go:19-23`), kept as one constant
/// because nothing has asked to tune it yet — and passed in rather than read
/// from a global so the rule can be tested at any setting.
#[derive(Clone, Copy, Debug)]
pub(crate) struct Config {
    /// How often the book is looked at.
    pub(crate) interval: Duration,
    /// How many durable slots are kept clear of waiting runs before capacity
    /// pressure is declared. Zero, as in Go.
    pub(crate) reserve_slots: usize,
    /// How long a run must have been waiting before capacity pressure may
    /// evict it, so a burst of short waits is not mistaken for congestion.
    pub(crate) min_wait_for_capacity: Duration,
}

/// The settings the worker runs with; see [`Config`].
pub(crate) const CONFIG: Config = Config {
    interval: Duration::from_secs(1),
    reserve_slots: 0,
    min_wait_for_capacity: Duration::from_secs(10),
};

/// The run the rule picked, and what to tell the engine about it.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Candidate {
    /// `task_run_external_id`: the durable task run to hand back.
    pub(crate) task_id: String,
    /// Which attempt is being handed back. The engine ignores an eviction for
    /// an invocation that is no longer current, so this is not decoration.
    pub(crate) invocation_count: i32,
    /// Why, in the words the engine records and the dashboard shows.
    pub(crate) reason: String,
}

/// What the worker knows about one durable run it is holding.
struct Record {
    invocation_count: i32,
    /// `None` for a durable run whose task declared no policy. It is still
    /// recorded, because it occupies a durable slot and capacity pressure is
    /// measured in occupied slots — it simply is never a candidate.
    policy: Option<EvictionPolicy>,
    /// When the *outermost* wait this run is in began, or `None` when it is
    /// working.
    waiting_since: Option<Instant>,
    /// How many waits are open at once. Nested waits are one wait, and the
    /// clock belongs to the outermost of them, exactly as Go counts them
    /// (`cache.go:137-175`).
    waits: usize,
    /// What that outermost wait is on, for the reason string: `("user_event",
    /// "approve")`, `("sleep", "sleep:5000ms")`, `("spawn_child", "child")`.
    wait: (&'static str, String),
    /// Set once this run has been chosen and an eviction is on the wire, so a
    /// later tick does not choose it again while the engine is answering.
    evicting: bool,
}

/// Every durable run this worker is holding, and which of them are waiting.
///
/// Shared through an [`Arc`]: the runner writes to it, every durable wait
/// borrows a [`WaitingGuard`] from it, and the manager reads it once a second.
#[derive(Default)]
pub(crate) struct EvictionBook {
    runs: Mutex<HashMap<String, Record>>,
}

impl EvictionBook {
    fn lock(&self) -> MutexGuard<'_, HashMap<String, Record>> {
        self.runs.lock().unwrap_or_else(PoisonError::into_inner)
    }

    /// Takes a durable run onto the books, working rather than waiting.
    ///
    /// A run already recorded under `task_id` is replaced: the engine has
    /// assigned the task again, and the earlier attempt is over.
    pub(crate) fn register(
        &self,
        task_id: &str,
        invocation_count: i32,
        policy: Option<EvictionPolicy>,
    ) {
        self.lock().insert(
            task_id.to_string(),
            Record {
                invocation_count,
                policy,
                waiting_since: None,
                waits: 0,
                wait: ("wait", String::new()),
                evicting: false,
            },
        );
    }

    /// Forgets a run: it finished, or it has been handed back.
    #[cfg(test)]
    fn unregister(&self, task_id: &str) {
        self.lock().remove(task_id);
    }

    /// [`register`](Self::register), with the run taken off the books again
    /// when the returned guard is dropped.
    ///
    /// The guard is what the runner holds, for the same reason the slot guard
    /// exists: a run leaves the books however it ends — completing, failing,
    /// panicking, or being dropped where it stands — and a ledger that leaked
    /// would keep a finished run counting towards capacity pressure for ever.
    pub(crate) fn take_on(
        self: &Arc<Self>,
        task_id: &str,
        invocation_count: i32,
        policy: Option<EvictionPolicy>,
    ) -> RunRegistration {
        self.register(task_id, invocation_count, policy);
        RunRegistration {
            book: Arc::clone(self),
            task_id: task_id.to_string(),
            invocation_count,
        }
    }

    /// Forgets a run only if it is still the attempt that `invocation_count`
    /// names.
    ///
    /// The engine assigns an evicted task again roughly a second later, so the
    /// next attempt can be on the books well before the last one has finished
    /// unwinding; this is what keeps the old one's guard from taking the new
    /// one off them.
    pub(crate) fn unregister_matching(&self, task_id: &str, invocation_count: i32) {
        let mut runs = self.lock();
        if runs
            .get(task_id)
            .is_some_and(|record| record.invocation_count == invocation_count)
        {
            runs.remove(task_id);
        }
    }

    /// Records that `task_id` has entered a wait, and hands back the guard
    /// that records its leaving.
    ///
    /// Dropping the guard is the *only* way the wait ends, which is why it is
    /// a guard: a handler that is cancelled mid-wait, or that panics, still
    /// unwinds through it.
    pub(crate) fn mark_waiting(
        self: &Arc<Self>,
        task_id: &str,
        kind: &'static str,
        resource: &str,
    ) -> WaitingGuard {
        self.mark_waiting_at(task_id, kind, resource, Instant::now())
    }

    /// [`mark_waiting`](Self::mark_waiting) with the moment handed in rather
    /// than read from the clock.
    ///
    /// Not a test-only door: taking the time as an argument is what lets the
    /// rule be tested to the second, and the production path simply passes
    /// [`Instant::now`].
    pub(crate) fn mark_waiting_at(
        self: &Arc<Self>,
        task_id: &str,
        kind: &'static str,
        resource: &str,
        at: Instant,
    ) -> WaitingGuard {
        // Which attempt this wait belongs to, so that a guard unwinding late
        // — an evicted handler winding down while the engine has already
        // assigned the task again — cannot tell the *new* attempt that a wait
        // it never entered is over. Zero when there is no record to wait for,
        // which matches nothing and leaves the guard inert.
        let mut invocation_count = 0;
        if let Some(record) = self.lock().get_mut(task_id) {
            invocation_count = record.invocation_count;
            record.waits += 1;
            if record.waits == 1 {
                record.waiting_since = Some(at);
                record.wait = (kind, resource.to_string());
            }
        }
        WaitingGuard {
            book: Arc::clone(self),
            task_id: task_id.to_string(),
            invocation_count,
        }
    }

    /// Records that one of `task_id`'s waits has ended.
    fn left_wait(&self, task_id: &str, invocation_count: i32) {
        if let Some(record) = self
            .lock()
            .get_mut(task_id)
            .filter(|record| record.invocation_count == invocation_count)
        {
            record.waits = record.waits.saturating_sub(1);
            if record.waits == 0 {
                record.waiting_since = None;
            }
        }
    }

    /// Marks a chosen run as being handed back, so the next tick leaves it
    /// alone while the engine answers. `false` when the run has gone in the
    /// meantime, which is the manager's cue to drop it.
    pub(crate) fn begin_eviction(&self, task_id: &str) -> bool {
        match self.lock().get_mut(task_id) {
            Some(record) => {
                record.evicting = true;
                true
            }
            None => false,
        }
    }

    /// Un-marks a run the engine would not take back, so a later tick may try
    /// again.
    pub(crate) fn abandon_eviction(&self, task_id: &str) {
        if let Some(record) = self.lock().get_mut(task_id) {
            record.evicting = false;
        }
    }

    /// The run to hand back now, if any. Reads the book and nothing else —
    /// `now` is handed in, and so are the worker's settings.
    ///
    /// The order, from the official Go SDK (`cache.go:179-253`):
    ///
    /// 1. Only runs that are **waiting** and carry a policy are considered,
    ///    and not one that is already being handed back.
    /// 2. A run whose wait has passed its TTL goes first.
    /// 3. Only if none has, and only under capacity pressure — as many runs
    ///    waiting as there are durable slots, less
    ///    [`Config::reserve_slots`] — a run that allows capacity eviction and
    ///    has been waiting at least [`Config::min_wait_for_capacity`].
    /// 4. Among those: lowest [`priority`](EvictionPolicy::priority) first,
    ///    and then the longest wait.
    pub(crate) fn candidate(
        &self,
        now: Instant,
        durable_slots: usize,
        config: Config,
    ) -> Option<Candidate> {
        let runs = self.lock();
        // Every waiting run counts towards pressure, policy or not: what
        // crowds a worker is an occupied slot, not a configured one.
        let waiting = runs
            .iter()
            .filter(|(_, record)| record.waiting_since.is_some());
        let mut eligible = Vec::new();
        let mut waiting_count = 0_usize;
        for (task_id, record) in waiting {
            waiting_count += 1;
            if record.evicting {
                continue;
            }
            let Some(policy) = &record.policy else {
                continue;
            };
            let waited = now.saturating_duration_since(
                record.waiting_since.expect("filtered to the waiting runs"),
            );
            eligible.push((task_id.as_str(), record, policy, waited));
        }

        let by_ttl = eligible
            .iter()
            .copied()
            .filter(|(_, _, policy, waited)| policy.has_ttl() && *waited >= policy.ttl);
        if let Some((task_id, record, policy, _)) = pick(by_ttl) {
            return Some(Candidate {
                task_id: task_id.to_string(),
                invocation_count: record.invocation_count,
                reason: format!(
                    "wait TTL ({:?}) exceeded while waiting on {}",
                    policy.ttl,
                    waited_on(record)
                ),
            });
        }

        if !under_pressure(durable_slots, config.reserve_slots, waiting_count) {
            return None;
        }
        let by_capacity = eligible.iter().copied().filter(|(_, _, policy, waited)| {
            policy.allow_capacity_eviction && *waited >= config.min_wait_for_capacity
        });
        let (task_id, record, _, _) = pick(by_capacity)?;
        Some(Candidate {
            task_id: task_id.to_string(),
            invocation_count: record.invocation_count,
            reason: format!("worker at capacity while waiting on {}", waited_on(record)),
        })
    }
}

/// `user_event(approve)` — what a reason string says the run was parked on.
fn waited_on(record: &Record) -> String {
    let (kind, resource) = &record.wait;
    format!("{kind}({resource})")
}

/// Lowest priority first, then the longest wait. Ties beyond that are the
/// map's own order, which is arbitrary — and harmless: two runs alike in
/// policy and wait are interchangeable, and the next tick takes the other one.
fn pick<'a>(
    candidates: impl Iterator<Item = (&'a str, &'a Record, &'a EvictionPolicy, Duration)>,
) -> Option<(&'a str, &'a Record, &'a EvictionPolicy, Duration)> {
    candidates.min_by(|left, right| {
        let (_, _, left_policy, left_waited) = left;
        let (_, _, right_policy, right_waited) = right;
        left_policy
            .priority
            .cmp(&right_policy.priority)
            .then(right_waited.cmp(left_waited))
    })
}

/// Whether a worker is crowded enough for capacity eviction:
/// as many runs waiting as there are durable slots to spare.
///
/// Measured in *waiting runs* rather than in free slot permits, as Go measures
/// it (`cache.go:255-264`): a worker whose durable slots are all held by runs
/// that are parked on the engine is doing nothing with them, whatever the
/// semaphore says.
fn under_pressure(durable_slots: usize, reserve_slots: usize, waiting: usize) -> bool {
    let available = durable_slots.saturating_sub(reserve_slots);
    durable_slots > 0 && available > 0 && waiting >= available
}

/// One open wait of one durable run. Dropping it ends that wait.
pub(crate) struct WaitingGuard {
    book: Arc<EvictionBook>,
    task_id: String,
    invocation_count: i32,
}

impl Drop for WaitingGuard {
    fn drop(&mut self) {
        self.book.left_wait(&self.task_id, self.invocation_count);
    }
}

/// One durable run's place on the books, given up when the run ends.
pub(crate) struct RunRegistration {
    book: Arc<EvictionBook>,
    task_id: String,
    invocation_count: i32,
}

impl Drop for RunRegistration {
    fn drop(&mut self) {
        self.book
            .unregister_matching(&self.task_id, self.invocation_count);
    }
}

/// Looks at the book every [`Config::interval`] and hands back the runs that
/// have waited too long, or that a full worker cannot afford.
///
/// One eviction at a time, and in that order: the request goes out, its
/// `eviction_ack` is awaited, and only **then** is the run cancelled — a run
/// dropped before the engine had recorded the eviction would be one nothing is
/// coming back for. `cancel` is the runner's ordinary cancellation, which
/// stops the handler, suppresses its terminal event (a run handed back belongs
/// to the engine, exactly as a cancelled one does), and releases the durable
/// slot as the run's future unwinds.
///
/// A tick keeps choosing until the book offers nothing new, so a badly
/// over-subscribed worker sheds several runs in one pass, as Go does
/// (`manager.go:141-182`). An engine that will not acknowledge an eviction
/// ends the tick: the worker is evidently not being heard, and shedding more
/// runs into that silence would only lose them.
///
/// Ends when `stop` fires. There is deliberately **no** eviction at shutdown,
/// unlike Go's `EvictAllWaiting` (`manager.go:207-236`): this SDK's graceful
/// shutdown waits for the runs in flight, and throwing the waiting ones off
/// the worker would take away the very thing the drain is there to give them.
pub(crate) async fn run(
    book: Arc<EvictionBook>,
    stream: DurableStream,
    cancel: impl Fn(&str) + Send + 'static,
    durable_slots: usize,
    config: Config,
    stop: CancellationToken,
) {
    let mut ticker = tokio::time::interval(config.interval);
    // The book is a snapshot of *now*, so a tick that was missed while the
    // manager was waiting for an ack has nothing to catch up on.
    ticker.set_missed_tick_behavior(tokio::time::MissedTickBehavior::Delay);
    loop {
        tokio::select! {
            () = stop.cancelled() => return,
            _ = ticker.tick() => {}
        }
        // Each id once per tick: a candidate the engine refuses is left on the
        // books, and choosing it again in the same pass would spin.
        let mut tried: HashSet<String> = HashSet::new();
        while let Some(candidate) = book.candidate(Instant::now(), durable_slots, config) {
            if !tried.insert(candidate.task_id.clone()) {
                break;
            }
            if !book.begin_eviction(&candidate.task_id) {
                // It finished on its own between the choice and here.
                continue;
            }
            tracing::info!(
                task_run_external_id = %candidate.task_id,
                invocation_count = candidate.invocation_count,
                reason = %candidate.reason,
                "handing a waiting durable run back to the engine",
            );
            // Not inside the `select!` above: `stop` closes the durable
            // stream, and a pending eviction wakes out of this on its own when
            // it does.
            match stream
                .send_evict(
                    &candidate.task_id,
                    candidate.invocation_count,
                    Some(candidate.reason.clone()),
                )
                .await
            {
                Ok(()) => {
                    // The engine has recorded the eviction. If the wait
                    // completed in the few milliseconds since the candidate
                    // was picked, the run is cancelled anyway — the engine's
                    // view wins, exactly as in the official SDKs' manager.
                    book.unregister_matching(&candidate.task_id, candidate.invocation_count);
                    cancel(&candidate.task_id);
                }
                Err(error) => {
                    book.abandon_eviction(&candidate.task_id);
                    tracing::warn!(
                        task_run_external_id = %candidate.task_id,
                        invocation_count = candidate.invocation_count,
                        %error,
                        "the engine did not acknowledge an eviction; leaving the run alone",
                    );
                    break;
                }
            }
        }
    }
}

/// What the version gate calls this, in the worker's warning.
pub(crate) const EVICTION_FEATURE: &str = "durable eviction";

/// Whether `engine_version` is new enough to take an eviction.
///
/// An engine whose version cannot be read is treated as capable, exactly as
/// the official Go SDK treats it (`sdks/go/client.go:503-510`): the check is
/// skipped, not failed. Refusing to evict because a version string was
/// unfamiliar would turn a cosmetic problem into a worker that fills up.
///
/// In this SDK the answer is always `true` in practice —
/// [`EVICTION_MIN_ENGINE_VERSION`](crate::version::EVICTION_MIN_ENGINE_VERSION)
/// is the same version as
/// [`MIN_ENGINE_VERSION`](crate::MIN_ENGINE_VERSION), which
/// [`WorkerBuilder::build`](crate::WorkerBuilder::build) already refuses to go
/// below. It is written out anyway, and called, so that the day the floor
/// moves down the policies are dropped with a warning rather than sent to an
/// engine that cannot honour them.
pub(crate) fn supported(engine_version: &str) -> bool {
    !matches!(
        crate::version::ensure_feature(
            EVICTION_FEATURE,
            crate::version::EVICTION_MIN_ENGINE_VERSION,
            engine_version,
        ),
        Err(crate::Error::UnsupportedFeature { .. })
    )
}

#[cfg(test)]
mod tests {
    use super::*;

    fn at(base: Instant, secs: u64) -> Instant {
        base + Duration::from_secs(secs)
    }

    /// A book holding `runs`, each waiting since the given offset in seconds,
    /// with those waits held open for as long as the test holds the book.
    struct Held {
        book: Arc<EvictionBook>,
        _waits: Vec<WaitingGuard>,
    }

    impl std::ops::Deref for Held {
        type Target = Arc<EvictionBook>;

        fn deref(&self) -> &Arc<EvictionBook> {
            &self.book
        }
    }

    fn book(base: Instant, runs: &[(&str, EvictionPolicy, Option<u64>)]) -> Held {
        let book = Arc::new(EvictionBook::default());
        let mut waits = Vec::new();
        for (id, policy, waiting_since) in runs {
            book.register(id, 1, Some(policy.clone()));
            if let Some(offset) = waiting_since {
                waits.push(book.mark_waiting_at(id, "user_event", "approve", at(base, *offset)));
            }
        }
        Held {
            book,
            _waits: waits,
        }
    }

    #[test]
    fn nothing_is_evicted_while_nothing_is_waiting() {
        let base = Instant::now();
        let book = book(
            base,
            &[("run-1", EvictionPolicy::ttl(Duration::from_secs(1)), None)],
        );
        assert!(book.candidate(at(base, 600), 1, CONFIG).is_none());
    }

    #[test]
    fn a_wait_past_its_ttl_is_evicted_and_the_reason_says_what_it_was_waiting_on() {
        let base = Instant::now();
        let book = book(
            base,
            &[(
                "run-1",
                EvictionPolicy::ttl(Duration::from_secs(30)),
                Some(0),
            )],
        );
        assert!(
            book.candidate(at(base, 29), 1000, CONFIG).is_none(),
            "a second short of the TTL is not yet due",
        );
        let chosen = book
            .candidate(at(base, 30), 1000, CONFIG)
            .expect("past the TTL");
        assert_eq!(chosen.task_id, "run-1");
        assert_eq!(chosen.invocation_count, 1);
        assert!(chosen.reason.contains("TTL"), "{}", chosen.reason);
        assert!(chosen.reason.contains("user_event"), "{}", chosen.reason);
        assert!(chosen.reason.contains("approve"), "{}", chosen.reason);
    }

    /// The TTL is measured from the wait, not from the registration: a run
    /// that was on this worker for an hour but has only just parked is not
    /// due.
    #[test]
    fn the_clock_starts_at_the_wait_and_not_at_the_registration() {
        let base = Instant::now();
        let book = book(
            base,
            &[(
                "run-1",
                EvictionPolicy::ttl(Duration::from_secs(30)),
                Some(3600),
            )],
        );
        assert!(book.candidate(at(base, 3629), 1000, CONFIG).is_none());
        assert!(book.candidate(at(base, 3630), 1000, CONFIG).is_some());
    }

    /// A TTL of zero means "never on time alone" — the way Go reads it
    /// (`cache.go:199-211` tests `policy.TTL > 0`). Declaring one is refused
    /// at registration, so this only pins the rule itself.
    #[test]
    fn a_zero_ttl_is_never_evicted_on_time() {
        let base = Instant::now();
        let book = book(
            base,
            &[("run-1", EvictionPolicy::ttl(Duration::ZERO), Some(0))],
        );
        assert!(book.candidate(at(base, 86_400), 1000, CONFIG).is_none());
    }

    #[test]
    fn capacity_pressure_needs_every_slot_waiting_and_a_wait_past_the_floor() {
        let base = Instant::now();
        let long = EvictionPolicy::ttl(Duration::from_secs(3600));
        let book = book(
            base,
            &[("run-1", long.clone(), Some(0)), ("run-2", long, Some(5))],
        );
        assert!(
            book.candidate(at(base, 60), 3, CONFIG).is_none(),
            "three slots and two waiting is not pressure",
        );
        let chosen = book
            .candidate(at(base, 11), 2, CONFIG)
            .expect("two slots, two waiting");
        assert_eq!(
            chosen.task_id, "run-1",
            "the only one past the ten-second floor",
        );
        assert!(chosen.reason.contains("capacity"), "{}", chosen.reason);
        assert!(
            book.candidate(at(base, 9), 2, CONFIG).is_none(),
            "neither has waited the floor out yet",
        );
    }

    #[test]
    fn a_run_that_forbids_capacity_eviction_is_never_chosen_for_it() {
        let base = Instant::now();
        let forbidden = book(
            base,
            &[(
                "run-1",
                EvictionPolicy::ttl(Duration::from_secs(3600)).allow_capacity_eviction(false),
                Some(0),
            )],
        );
        assert!(forbidden.candidate(at(base, 600), 1, CONFIG).is_none());
        // The control: the same run, the same pressure, capacity eviction
        // allowed.
        let allowed = book(
            base,
            &[(
                "run-1",
                EvictionPolicy::ttl(Duration::from_secs(3600)),
                Some(0),
            )],
        );
        assert_eq!(
            allowed
                .candidate(at(base, 600), 1, CONFIG)
                .expect("allowed, and long past the floor")
                .task_id,
            "run-1",
        );
    }

    /// Forbidding capacity eviction does not exempt a run from its own TTL.
    #[test]
    fn a_run_that_forbids_capacity_eviction_still_answers_to_its_ttl() {
        let base = Instant::now();
        let book = book(
            base,
            &[(
                "run-1",
                EvictionPolicy::ttl(Duration::from_secs(30)).allow_capacity_eviction(false),
                Some(0),
            )],
        );
        let chosen = book.candidate(at(base, 30), 1000, CONFIG).expect("due");
        assert!(chosen.reason.contains("TTL"), "{}", chosen.reason);
    }

    #[test]
    fn the_lowest_priority_goes_first_and_ties_break_on_the_longest_wait() {
        let base = Instant::now();
        let ttl = Duration::from_secs(10);
        let book = book(
            base,
            &[
                ("high", EvictionPolicy::ttl(ttl).priority(5), Some(0)),
                ("low", EvictionPolicy::ttl(ttl).priority(1), Some(5)),
                ("low-older", EvictionPolicy::ttl(ttl).priority(1), Some(2)),
            ],
        );
        let chosen = book
            .candidate(at(base, 60), 1000, CONFIG)
            .expect("all three are past the TTL");
        assert_eq!(chosen.task_id, "low-older");
    }

    /// The reference count: a run in two waits at once is one waiting run, and
    /// its clock starts at the outer one.
    #[test]
    fn nested_waits_count_once_and_date_from_the_outer_one() {
        let base = Instant::now();
        let book = Arc::new(EvictionBook::default());
        book.register(
            "run-1",
            1,
            Some(EvictionPolicy::ttl(Duration::from_secs(10))),
        );
        let outer = book.mark_waiting_at("run-1", "spawn_child", "child", at(base, 0));
        let inner = book.mark_waiting_at("run-1", "sleep", "sleep:5000ms", at(base, 5));
        drop(inner);
        let chosen = book
            .candidate(at(base, 10), 1000, CONFIG)
            .expect("ten seconds since the outer wait began");
        assert_eq!(chosen.task_id, "run-1");
        assert!(
            chosen.reason.contains("spawn_child"),
            "the outer wait is the one named: {}",
            chosen.reason,
        );
        drop(outer);
        assert!(
            book.candidate(at(base, 600), 1000, CONFIG).is_none(),
            "no longer waiting",
        );
    }

    /// Leaving a wait and entering another starts the clock again.
    #[test]
    fn a_run_that_goes_back_to_work_starts_its_clock_over() {
        let base = Instant::now();
        let book = Arc::new(EvictionBook::default());
        book.register(
            "run-1",
            1,
            Some(EvictionPolicy::ttl(Duration::from_secs(10))),
        );
        drop(book.mark_waiting_at("run-1", "sleep", "sleep:1000ms", at(base, 0)));
        let second = book.mark_waiting_at("run-1", "user_event", "approve", at(base, 100));
        assert!(
            book.candidate(at(base, 109), 1000, CONFIG).is_none(),
            "nine seconds into the second wait, not a hundred and nine",
        );
        assert!(book.candidate(at(base, 110), 1000, CONFIG).is_some());
        drop(second);
    }

    #[test]
    fn a_run_with_no_policy_is_never_a_candidate() {
        let base = Instant::now();
        let book = Arc::new(EvictionBook::default());
        book.register("run-1", 1, None);
        let _waiting = book.mark_waiting_at("run-1", "sleep", "sleep:1000ms", at(base, 0));
        assert!(book.candidate(at(base, 86_400), 1, CONFIG).is_none());
    }

    /// …but it does crowd the worker, which is why it is on the books at all.
    #[test]
    fn a_run_with_no_policy_still_counts_towards_capacity_pressure() {
        let base = Instant::now();
        let book = Arc::new(EvictionBook::default());
        book.register("no-policy", 1, None);
        book.register(
            "policy",
            1,
            Some(EvictionPolicy::ttl(Duration::from_secs(3600))),
        );
        let _one = book.mark_waiting_at("no-policy", "user_event", "approve", at(base, 0));
        let _two = book.mark_waiting_at("policy", "user_event", "approve", at(base, 0));
        assert!(
            book.candidate(at(base, 60), 3, CONFIG).is_none(),
            "three slots, two waiting",
        );
        assert_eq!(
            book.candidate(at(base, 60), 2, CONFIG)
                .expect("two slots, two waiting")
                .task_id,
            "policy",
            "the one without a policy is counted but never chosen",
        );
    }

    #[test]
    fn a_run_already_being_handed_back_is_not_chosen_twice() {
        let base = Instant::now();
        let book = book(
            base,
            &[(
                "run-1",
                EvictionPolicy::ttl(Duration::from_secs(10)),
                Some(0),
            )],
        );
        assert!(book.candidate(at(base, 60), 1000, CONFIG).is_some());
        assert!(book.begin_eviction("run-1"));
        assert!(book.candidate(at(base, 60), 1000, CONFIG).is_none());
        // An engine that refused it leaves it choosable again.
        book.abandon_eviction("run-1");
        assert!(book.candidate(at(base, 60), 1000, CONFIG).is_some());
        assert!(
            !book.begin_eviction("gone"),
            "a run that is no longer on the books cannot be handed back",
        );
    }

    /// A guard from the attempt that was evicted must not disturb the attempt
    /// the engine assigned in its place.
    #[test]
    fn a_late_guard_from_an_evicted_attempt_leaves_the_next_one_alone() {
        let base = Instant::now();
        let book = Arc::new(EvictionBook::default());
        book.register(
            "run-1",
            1,
            Some(EvictionPolicy::ttl(Duration::from_secs(10))),
        );
        let stale = book.mark_waiting_at("run-1", "user_event", "approve", at(base, 0));
        // Evicted, and assigned again as a second invocation that parks too.
        book.unregister("run-1");
        book.register(
            "run-1",
            2,
            Some(EvictionPolicy::ttl(Duration::from_secs(10))),
        );
        let fresh = book.mark_waiting_at("run-1", "user_event", "approve", at(base, 100));
        drop(stale);
        let chosen = book
            .candidate(at(base, 110), 1000, CONFIG)
            .expect("the second attempt is still waiting");
        assert_eq!(chosen.invocation_count, 2);
        drop(fresh);
        assert!(book.candidate(at(base, 600), 1000, CONFIG).is_none());
    }

    #[test]
    fn an_unregistered_run_leaves_nothing_behind() {
        let base = Instant::now();
        let book = book(
            base,
            &[(
                "run-1",
                EvictionPolicy::ttl(Duration::from_secs(1)),
                Some(0),
            )],
        );
        book.unregister("run-1");
        assert!(book.candidate(at(base, 600), 1, CONFIG).is_none());
        // A guard outliving the record must not resurrect it.
        let guard = book.mark_waiting_at("run-1", "sleep", "sleep:1000ms", at(base, 0));
        drop(guard);
        assert!(book.candidate(at(base, 600), 1, CONFIG).is_none());
    }

    #[test]
    fn a_worker_with_no_durable_slots_is_never_under_pressure() {
        assert!(!under_pressure(0, 0, 10));
        assert!(!under_pressure(2, 2, 10));
        assert!(!under_pressure(2, 3, 10));
        assert!(under_pressure(2, 0, 2));
        assert!(!under_pressure(2, 0, 1));
        assert!(under_pressure(2, 1, 1));
    }

    #[test]
    fn the_defaults_are_the_official_go_sdks() {
        let policy = EvictionPolicy::default();
        assert_eq!(policy.ttl, Duration::from_secs(15 * 60));
        assert!(policy.allow_capacity_eviction);
        assert_eq!(policy.priority, 0);
        assert_eq!(EvictionPolicy::ttl(Duration::from_secs(1)).priority, 0);
    }

    #[test]
    fn eviction_is_supported_from_the_version_the_official_sdks_gate_on() {
        assert!(!supported("v0.79.0"));
        assert!(supported(crate::version::MIN_ENGINE_VERSION));
        assert!(supported("v0.107.0"));
        // An engine that will not say is treated as capable, as Go does
        // (`sdks/go/client.go:503-510`): the check is skipped, not failed.
        assert!(supported("not a version"));
    }
}