1
//! Declare the `RetryTime` enumeration and related code.
2

            
3
use derive_more::{From, Into};
4
use std::{
5
    cmp::Ordering,
6
    time::{Duration, Instant},
7
};
8
use strum::EnumDiscriminants;
9

            
10
/// A description of when an operation may be retried.
11
///
12
/// # Retry times values are contextual.
13
///
14
/// Note that retrying is necessarily contextual, depending on what exactly
15
/// we're talking about retrying.
16
///
17
/// For an example of how context matters:  suppose that we try to build a
18
/// circuit, and encounter a failure extending to the second hop.  If we try to
19
/// build a circuit _through the same path_ immediately, it's likely to fail
20
/// again.  But if we try to build a circuit through a different path, then
21
/// there's no reason to expect that same kind of error.
22
///
23
/// Thus, the same inner error condition ("failed to extend to the nth hop") can
24
/// indicate either a "Retry after waiting for a while" or "Retry immediately."
25
///
26
/// # Retry times depend on what we think might change.
27
///
28
/// Whether retrying will help depends on what we think is likely to change in
29
/// the near term.
30
///
31
/// For example, we generally assume an unreachable relay has some likelihood of
32
/// becoming reachable in the near future, and therefore connecting to such a
33
/// relay is worth retrying.
34
///
35
/// On the other hand, we _don't_ assume that the network is changing wildly
36
/// over time.  Thus, if there is currently no relay that supports delivering
37
/// traffic to port 23 (telnet), we say that building a request for such a relay
38
/// is not retriable, even though technically such a relay might appear in the
39
/// next consensus.
40
#[derive(Copy, Clone, Debug, Eq, PartialEq, EnumDiscriminants)]
41
#[non_exhaustive]
42
// We define a discriminant type so we can simplify loose_cmp.
43
#[strum_discriminants(derive(Ord, PartialOrd))]
44
// We don't want to expose RetryTimeDiscriminants.
45
#[strum_discriminants(vis())]
46
pub enum RetryTime {
47
    /// The operation can be retried immediately, and no delay is needed.
48
    ///
49
    /// The recipient of this `RetryTime` variant may retry the operation
50
    /// immediately without waiting.
51
    ///
52
    /// This case should be used cautiously: it risks making code retry in a
53
    /// loop without delay.  It should only be used for error conditions that
54
    /// are necessarily produced via a process that itself introduces a delay.
55
    /// (For example, this case is suitable for errors caused by a remote
56
    /// timeout.)
57
    Immediate,
58

            
59
    /// The operation can be retried after a short delay, to prevent overloading
60
    /// the network.  
61
    ///
62
    /// The recipient of this `RetryTime` variant should delay a short amount of
63
    /// time before retrying.  The amount of time to delay should be randomized,
64
    /// and should tend to grow larger the more failures there have been
65
    /// recently for the given operation.  (The `RetryDelay` type from
66
    /// `tor-basic-utils` is suitable for managing this calculation.)
67
    ///
68
    /// This case should be used for problems that tend to be "self correcting",
69
    /// such as remote server failures (the server might come back up).
70
    AfterWaiting,
71

            
72
    /// The operation can be retried after a particular delay.
73
    ///
74
    /// The recipient of this `RetryTime` variant should wait for at least the
75
    /// given duration before retrying the operation.
76
    ///
77
    /// This case should only be used if there is some reason not to return
78
    /// `AfterWaiting`: for example, if the implementor is providing their own
79
    /// back-off algorithm instead of using `RetryDelay.`
80
    ///
81
    /// (This is a separate variant from `At`, since the constructor may not
82
    /// have convenient access to (a mocked view of) the current time.  If you
83
    /// know that the current time is `now`, then `After(d)` is equivalent to
84
    /// `At(now + d)`.)
85
    After(Duration),
86

            
87
    /// The operation can be retried at some particular time in the future.
88
    ///
89
    /// The recipient of this this `RetryTime` variant should wait until the
90
    /// current time (as returned by `Instant::now` or `SleepProvider::now` as
91
    /// appropriate) is at least this given instant.
92
    ///
93
    /// This case is appropriate for when we have a failure condition caused by
94
    /// waiting for multiple other timeouts.  (For example, if we believe that
95
    /// all our guards are down, then we won't be able to try getting a guard
96
    /// until the next time guard is scheduled to be marked as retriable.)
97
    At(Instant),
98

            
99
    /// Retrying is unlikely to make this operation succeed, unless something
100
    /// else is fixed first.
101
    ///
102
    /// The recipient of this `RetryTime` variant should generally give up, and
103
    /// stop retrying the given operation.
104
    ///
105
    /// We don't mean "literally" that the operation will never succeed: only
106
    /// that retrying it in the near future without fixing the underlying cause
107
    /// is unlikely to help.
108
    ///
109
    /// This case is appropriate for issues like misconfiguration, internal
110
    /// errors, and requests for operations that the network doesn't support.
111
    ///
112
    /// This case is also appropriate for a problem that is "technically"
113
    /// retriable, but where any resolution is likelier to take days or weeks
114
    /// instead  of minutes or hours.
115
    Never,
116
}
117

            
118
/// A `RetryTime` wrapped so that it compares according to [`RetryTime::loose_cmp`]
119
#[derive(From, Into, Copy, Clone, Debug, Eq, PartialEq)]
120
pub struct LooseCmpRetryTime(RetryTime);
121

            
122
/// Trait for an error object that can tell us when the operation which
123
/// generated it can be retried.
124
pub trait HasRetryTime {
125
    /// Return the time when the operation that gave this error can be retried.
126
    ///
127
    /// See all caveats and explanations on [`RetryTime`].
128
    fn retry_time(&self) -> RetryTime;
129

            
130
    /// Return an absolute retry when the operation that gave this error can be
131
    /// retried.
132
    ///
133
    /// Requires that `now` is the current time, and `choose_delay` is a
134
    /// function to choose a delay for [`RetryTime::AfterWaiting`].
135
    fn abs_retry_time<F>(&self, now: Instant, choose_delay: F) -> AbsRetryTime
136
    where
137
        F: FnOnce() -> Duration,
138
        Self: Sized,
139
    {
140
        self.retry_time().absolute(now, choose_delay)
141
    }
142
}
143

            
144
/// An absolute [`RetryTime`].
145
///
146
/// Unlike `RetryTime`, this type always denotes a particular instant in time.
147
/// You can derive it using [`RetryTime::absolute`].
148
#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
149
#[allow(clippy::exhaustive_enums)]
150
pub enum AbsRetryTime {
151
    /// See [`RetryTime::Immediate`].
152
    Immediate,
153
    /// See [`RetryTime::At`].
154
    At(Instant),
155
    /// See [`RetryTime::Never`].
156
    Never,
157
}
158

            
159
impl AbsRetryTime {
160
    /// Construct an AbsRetryTime representing `base` + `plus`.
161
1318
    fn from_sum(base: Instant, plus: Duration) -> Self {
162
1318
        match base.checked_add(plus) {
163
1316
            Some(t) => AbsRetryTime::At(t),
164
2
            None => AbsRetryTime::Never,
165
        }
166
1318
    }
167
}
168

            
169
impl RetryTime {
170
    /// Convert this [`RetryTime`] in to an absolute time.
171
    ///
172
    /// Requires that `now` is the current time, and `choose_delay` is a
173
    /// function to choose a delay for [`RetryTime::AfterWaiting`].
174
154
    pub fn absolute<F>(self, now: Instant, choose_delay: F) -> AbsRetryTime
175
154
    where
176
154
        F: FnOnce() -> Duration,
177
154
    {
178
154
        match self {
179
80
            RetryTime::Immediate => AbsRetryTime::Immediate,
180
64
            RetryTime::AfterWaiting => AbsRetryTime::from_sum(now, choose_delay()),
181
            RetryTime::After(d) => AbsRetryTime::from_sum(now, d),
182
            RetryTime::At(t) => AbsRetryTime::At(t),
183
10
            RetryTime::Never => AbsRetryTime::Never,
184
        }
185
154
    }
186

            
187
    /// Convert all the provided `items` into [`AbsRetryTime`] values, and
188
    /// return the earliest one.
189
    ///
190
    /// Requires that `now` is the current time, and `choose_delay` is a
191
    /// function to choose a delay for [`RetryTime::AfterWaiting`].
192
    ///
193
    /// Differs from `items.map(AbsRetryTime::absolute(now,
194
    /// choose_delay)).min()` in that it calls `choose_delay` at most once.
195
82
    pub fn earliest_absolute<I, F>(items: I, now: Instant, choose_delay: F) -> Option<AbsRetryTime>
196
82
    where
197
82
        I: Iterator<Item = RetryTime>,
198
82
        F: FnOnce() -> Duration,
199
82
    {
200
82
        let chosen_delay = std::cell::LazyCell::new(|| AbsRetryTime::from_sum(now, choose_delay()));
201
82

            
202
82
        items
203
84
            .map(|item| match item {
204
2
                RetryTime::AfterWaiting => *chosen_delay,
205
82
                other => other.absolute(now, || unreachable!()),
206
84
            })
207
82
            .min()
208
82
    }
209

            
210
    /// Return the "approximately earliest" item for an iterator of retry times.
211
    ///
212
    /// This is necessarily an approximation, since we can't be sure what time
213
    /// will be chosen if the retry is supposed to happen at a random time, and
214
    /// therefore cannot tell whether `AfterWaiting` comes before or after
215
    /// particular `At` and `After` instances.
216
    ///
217
    /// If you need an exact answer, use earliest_absolute.
218
    pub fn earliest_approx<I>(items: I) -> Option<RetryTime>
219
    where
220
        I: Iterator<Item = RetryTime>,
221
    {
222
        items.min_by(|a, b| a.loose_cmp(b))
223
    }
224

            
225
    /// A loose-but-total comparison operator, suitable for choosing a retry
226
    /// time when multiple attempts have failed.
227
    ///
228
    /// If you need an absolute comparison operator, convert to [`AbsRetryTime`] first.
229
    ///
230
    /// See also:
231
    /// [`LooseCmpRetryTime`], a wrapper for `RetryTime` that uses this comparison.
232
98
    pub fn loose_cmp(&self, other: &Self) -> Ordering {
233
        use RetryTime as RT;
234

            
235
98
        match (self, other) {
236
            // When we have the same type with an internal embedded duration or time,
237
            // we compare based on the duration or time.
238
8
            (RT::After(d1), RetryTime::After(d2)) => d1.cmp(d2),
239
8
            (RT::At(t1), RetryTime::At(t2)) => t1.cmp(t2),
240

            
241
            // Otherwise, we compare based on discriminant type.
242
            //
243
            // This can't do a perfect "apples-to-apples" comparison for
244
            // `AfterWaiting` vs `At` vs `After`, but at least it imposes a
245
            // total order.
246
82
            (a, b) => RetryTimeDiscriminants::from(a).cmp(&RetryTimeDiscriminants::from(b)),
247
        }
248
98
    }
249
}
250

            
251
impl Ord for LooseCmpRetryTime {
252
    fn cmp(&self, other: &Self) -> Ordering {
253
        self.0.loose_cmp(&other.0)
254
    }
255
}
256
impl PartialOrd for LooseCmpRetryTime {
257
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
258
        Some(self.cmp(other))
259
    }
260
}
261

            
262
#[cfg(test)]
263
mod test {
264
    // @@ begin test lint list maintained by maint/add_warning @@
265
    #![allow(clippy::bool_assert_comparison)]
266
    #![allow(clippy::clone_on_copy)]
267
    #![allow(clippy::dbg_macro)]
268
    #![allow(clippy::mixed_attributes_style)]
269
    #![allow(clippy::print_stderr)]
270
    #![allow(clippy::print_stdout)]
271
    #![allow(clippy::single_char_pattern)]
272
    #![allow(clippy::unwrap_used)]
273
    #![allow(clippy::unchecked_duration_subtraction)]
274
    #![allow(clippy::useless_vec)]
275
    #![allow(clippy::needless_pass_by_value)]
276
    //! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
277
    use super::*;
278

            
279
    #[test]
280
    fn comparison() {
281
        use RetryTime as RT;
282
        let sec = Duration::from_secs(1);
283
        let now = Instant::now();
284

            
285
        let sorted = vec![
286
            RT::Immediate,
287
            RT::AfterWaiting,
288
            RT::After(sec * 10),
289
            RT::After(sec * 20),
290
            RT::At(now),
291
            RT::At(now + sec * 30),
292
            RT::Never,
293
        ];
294

            
295
        // Verify that these objects are actually in loose-cmp sorted order.
296
        for (i, a) in sorted.iter().enumerate() {
297
            for (j, b) in sorted.iter().enumerate() {
298
                assert_eq!(a.loose_cmp(b), i.cmp(&j));
299
            }
300
        }
301
    }
302

            
303
    #[test]
304
    fn abs_comparison() {
305
        use AbsRetryTime as ART;
306
        let sec = Duration::from_secs(1);
307
        let now = Instant::now();
308

            
309
        let sorted = vec![
310
            ART::Immediate,
311
            ART::At(now),
312
            ART::At(now + sec * 30),
313
            ART::Never,
314
        ];
315

            
316
        // Verify that these objects are actually in loose-cmp sorted order.
317
        for (i, a) in sorted.iter().enumerate() {
318
            for (j, b) in sorted.iter().enumerate() {
319
                assert_eq!(a.cmp(b), i.cmp(&j));
320
            }
321
        }
322
    }
323

            
324
    #[test]
325
    fn earliest_absolute() {
326
        let sec = Duration::from_secs(1);
327
        let now = Instant::now();
328

            
329
        let times = vec![RetryTime::AfterWaiting, RetryTime::Never];
330

            
331
        let earliest = RetryTime::earliest_absolute(times.into_iter(), now, || sec);
332
        assert_eq!(
333
            earliest.expect("no absolute time"),
334
            AbsRetryTime::At(now + sec)
335
        );
336
    }
337

            
338
    #[test]
339
    fn abs_from_sum() {
340
        let base = Instant::now();
341
        let delta = Duration::from_secs(1);
342
        assert_eq!(
343
            AbsRetryTime::from_sum(base, delta),
344
            AbsRetryTime::At(base + delta)
345
        );
346

            
347
        assert_eq!(
348
            AbsRetryTime::from_sum(base, Duration::MAX),
349
            AbsRetryTime::Never
350
        );
351
    }
352
}