vaegram 0.3.0

Telegram MTProto client library for users and bots
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
use std::cmp::Ordering;
use std::sync::Arc;
use std::time::Duration;

use tokio::time::Instant;

use super::Entities;
use crate::enums::SkipReason;
use crate::errors::{Error, Result};
use crate::raw::{base, types};
use crate::storage::UpdateState;

// https://core.telegram.org/api/updates#recovering-gaps
const GAP_TIMEOUT: Duration = Duration::from_millis(500);
// The same page tells clients to call getDifference after 15 minutes without updates, in case the server
// stopped pushing.
const IDLE_TIMEOUT: Duration = Duration::from_secs(15 * 60);
const MAX_RETRIES: u32 = 5;
// Past this many held updates for one key the client is too far behind to fill the hole from what it holds, and the
// cap keeps a key that never fills from growing without bound. Held pts, qts and channel updates are dropped, since
// getDifference refetches them; held seq batches are released instead, since they also carry updates getDifference
// may not bring back: channel updates, which it returns only when it chooses to, and updates that move no counter.
pub(super) const MAX_PENDING: usize = 1024;

pub(super) fn channel_of(update: &base::Update) -> Option<i64> {
    let message = match update {
        base::Update::UpdateNewChannelMessage(u) => &u.message,
        base::Update::UpdateEditChannelMessage(u) => &u.message,
        base::Update::UpdateDeleteChannelMessages(u) => return Some(u.channel_id),
        base::Update::UpdateChannelWebPage(u) => return Some(u.channel_id),
        base::Update::UpdatePinnedChannelMessages(u) => return Some(u.channel_id),
        _ => return None,
    };
    let peer = match message {
        base::Message::Message(m) => &m.peer_id,
        base::Message::MessageService(m) => &m.peer_id,
        base::Message::MessageEmpty(m) => m.peer_id.as_ref()?,
    };
    match peer {
        base::Peer::PeerChannel(p) => Some(p.channel_id),
        _ => None,
    }
}

/// The counter `update` moves, with its value before and after the update, or `None` when no counter numbers it;
/// `channel` is [`channel_of`] the update, and whether it is numbered doesn't depend on it. A pts or qts of 0 numbers
/// nothing: Telegram sends it on updates it doesn't order, which grammers (`NO_PTS`) and mtcute (`pts ? … : undefined`)
/// apply in any order. Checked against a counter, it would always pass for one already seen.
pub(super) fn counter_of(update: &base::Update, channel: Option<i64>) -> Option<(Key, i32, i32)> {
    if let Some((pts, count)) = update.pts().filter(|&(pts, _)| pts != 0) {
        return Some((channel.map_or(Key::Pts, Key::Channel), pts.wrapping_sub(count), pts));
    }
    update.qts().filter(|&qts| qts != 0).map(|qts| (Key::Qts, qts.wrapping_sub(1), qts))
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub(super) enum Key {
    Pts,
    Qts,
    Seq,
    Channel(i64),
}

pub(super) enum Item {
    Update(base::Update, Arc<Entities>),
    Batch(Vec<base::Update>, Arc<Entities>, i32, bool),
    Counter,
}

#[derive(Debug, PartialEq)]
pub(super) struct Skipped {
    pub(super) key: Key,
    pub(super) from: i32,
    pub(super) to: i32,
    pub(super) reason: SkipReason,
}

pub(super) struct Pending {
    pub(super) key: Key,
    pub(super) before: i32,
    pub(super) after: i32,
    pub(super) item: Item,
}

#[derive(Default)]
pub(super) struct Tracker {
    pub(super) state: UpdateState,
    pub(super) pending: Vec<(Instant, Pending)>,
    pub(super) retries: Vec<(Instant, Key)>,
    // Per key, the counter value the cap dropped held updates up to, kept until a fetch for the key settles: a fetch
    // given up on reports that range as skipped.
    pub(super) dropped: Vec<(Key, i32)>,
    pub(super) failures: Vec<(Key, u32)>,
    pub(super) idle: Option<Instant>,
    pub(super) due: Vec<Key>,
    pub(super) ready: Vec<(base::Update, Arc<Entities>)>,
    // updatePtsChanged came, or getDifference refused the stored pts: the common box has to be read again with
    // updates.getState.
    pub(super) refetch: bool,
    // After a failed getState, when it may be asked again, and how many failed in a row.
    pub(super) refetch_after: Option<Instant>,
    pub(super) refetch_failures: u32,
}

impl Tracker {
    pub(super) fn set_state(&mut self, s: &types::updates::State) {
        let state = &mut self.state;
        (state.pts, state.qts, state.date, state.seq) = (s.pts, s.qts, s.date, s.seq);
    }

    /// The state updates.getState gave after updatePtsChanged, or after getDifference refused the stored pts.
    /// Updates held for a pts gap were numbered the old way, so they go, and so do the common box's updates in held
    /// seq batches, which would otherwise be offered to the new pts. Only that box was renumbered
    /// (https://core.telegram.org/constructor/updatePtsChanged), so held qts, channel and seq ones are checked against
    /// the fresh counters.
    pub(super) fn restate(&mut self, s: &types::updates::State) {
        self.set_state(s);
        self.pending.retain(|(_, p)| p.key != Key::Pts);
        self.dropped.retain(|(k, _)| *k != Key::Pts);
        for (_, p) in &mut self.pending {
            if let Item::Batch(updates, ..) = &mut p.item {
                updates.retain(|u| !matches!(counter_of(u, channel_of(u)), Some((Key::Pts, ..))));
            }
        }
        self.drain(Key::Qts);
        self.drain(Key::Seq);
    }

    /// Whether updates.getState is to be asked now: it was asked for, and no wait after a failed one runs.
    pub(super) fn refetch_now(&self, now: Instant) -> bool {
        self.refetch && self.refetch_after.is_none_or(|after| after <= now)
    }

    /// After an updates.getState. A success clears the wait. A failure is asked again after a wait that doubles from
    /// `GAP_TIMEOUT` up to the gap back-off's last (`backoff`), and lasts at least a FLOOD_WAIT's, as `recover` waits.
    /// It never gives up: until the state comes, nothing else can be fetched from the right pts.
    pub(super) fn refetched(&mut self, result: &Result<()>, now: Instant) {
        let Err(error) = result else {
            (self.refetch, self.refetch_after, self.refetch_failures) = (false, None, 0);
            return;
        };
        self.refetch = true;
        self.refetch_failures = self.refetch_failures.saturating_add(1);
        let wait = GAP_TIMEOUT * 2u32.pow(self.refetch_failures.min(MAX_RETRIES) - 1);
        let wait = error.flood_wait().map_or(wait, |flood| wait.max(flood));
        self.refetch_after = Some(now + wait);
    }

    pub(super) fn counter(&mut self, key: Key) -> &mut i32 {
        match key {
            Key::Pts => &mut self.state.pts,
            Key::Qts => &mut self.state.qts,
            Key::Seq => &mut self.state.seq,
            Key::Channel(id) => self.state.channels.entry(id).or_insert(0),
        }
    }

    pub(super) fn mark(&mut self, key: Key) {
        let key = if let Key::Channel(_) = key { key } else { Key::Pts };
        // A scheduled retry (a FLOOD_WAIT or a back-off) already covers it; asking sooner only fails again.
        if !self.due.contains(&key) && !self.retries.iter().any(|(_, k)| *k == key) {
            self.due.push(key);
        }
    }

    pub(super) fn emit(&mut self, update: base::Update, entities: &Arc<Entities>) {
        self.ready.push((update, entities.clone()));
    }

    pub(super) fn deadline(&self) -> Option<Instant> {
        let refetch = self.refetch_after.filter(|_| self.refetch);
        // While getState waits, no difference is asked for the common box, so what it holds waits for getState too;
        // a deadline already past would wake the loop for nothing, again and again.
        let pending = self.pending.iter().map(|(d, p)| match (refetch, p.key) {
            (Some(after), Key::Pts | Key::Qts | Key::Seq) => (*d).max(after),
            _ => *d,
        });
        let retries = self.retries.iter().map(|(d, _)| *d).chain(refetch);
        pending.chain(retries).chain(self.idle).min()
    }

    pub(super) fn touch(&mut self, now: Instant) {
        self.idle = Some(now + IDLE_TIMEOUT);
    }

    pub(super) fn update(&mut self, update: base::Update, entities: &Arc<Entities>, quiet: bool) {
        if let base::Update::UpdateChannelTooLong(u) = &update {
            // https://core.telegram.org/constructor/updateChannelTooLong: a channel with no stored pts is fetched from
            // the one given, as mtcute does (tdlib probes from pts 1 instead). A stored one is kept, since fetching
            // from it misses nothing; without either, `channel_difference` reports the channel's updates as skipped.
            // The value is trusted: one above the channel's real pts makes its updates look seen until an answer to
            // getChannelDifference carries the channel's pts, or PERSISTENT_TIMESTAMP_INVALID has it forgotten.
            if let Some(pts) = u.pts.filter(|&pts| pts != 0) {
                self.state.channels.entry(u.channel_id).or_insert(pts);
            }
            return self.mark(Key::Channel(u.channel_id));
        }
        // https://core.telegram.org/constructor/updatePtsChanged: the pts were renumbered. Raw handlers still get it.
        if matches!(update, base::Update::UpdatePtsChanged) {
            self.refetch = true;
        }
        let channel = channel_of(&update);
        let channel_message =
            matches!(update, base::Update::UpdateNewChannelMessage(_) | base::Update::UpdateEditChannelMessage(_));
        if channel.is_none() && channel_message {
            return;
        }
        let Some((key, before, after)) = counter_of(&update, channel) else {
            if !quiet {
                self.emit(update, entities);
            }
            return;
        };
        let item = if quiet { Item::Counter } else { Item::Update(update, entities.clone()) };
        self.offer(Pending { key, before, after, item });
    }

    pub(super) fn short(&mut self, pts: i32, count: i32, quiet: bool) {
        let before = pts.wrapping_sub(count);
        if quiet {
            self.offer(Pending { key: Key::Pts, before, after: pts, item: Item::Counter });
        } else if self.state.pts <= before {
            // Short updates lack the sender and chat; getDifference returns the full message.
            self.mark(Key::Pts);
        }
    }

    pub(super) fn batch(
        &mut self,
        updates: Vec<base::Update>,
        entities: Arc<Entities>,
        (date, seq_start, seq): (i32, i32, i32),
        quiet: bool,
    ) {
        if seq_start == 0 {
            for update in updates {
                self.update(update, &entities, quiet);
            }
        } else {
            let item = Item::Batch(updates, entities, date, quiet);
            self.offer(Pending { key: Key::Seq, before: seq_start.wrapping_sub(1), after: seq, item });
        }
    }

    pub(super) fn offer(&mut self, p: Pending) {
        let local = match p.key {
            Key::Channel(id) => *self.state.channels.entry(id).or_insert(p.before),
            key => *self.counter(key),
        };
        match local.cmp(&p.before) {
            Ordering::Greater => self.stale(p),
            Ordering::Equal => {
                let key = p.key;
                self.apply(p);
                self.drain(key);
            }
            Ordering::Less => {
                if self.pending.iter().filter(|(_, held)| held.key == p.key).count() >= MAX_PENDING {
                    let key = p.key;
                    if key == Key::Seq {
                        // Give the seq hole up, but release every held batch in order through each update's own
                        // key: the seq counter moves past the hole, so the next batches apply whatever the
                        // difference leaves seq at, and getDifference refetches the pts and qts the hole held.
                        self.pending.push((Instant::now(), p));
                        self.settle(|k| k == Key::Seq, None);
                    } else {
                        // The hole is too deep to fill from the held updates: give the key up to getDifference,
                        // which refetches them from the stored state. The range dropped is kept, so a fetch given
                        // up on still reports it.
                        let mut to = p.after;
                        self.pending.retain(|(_, held)| {
                            if held.key == key {
                                to = to.max(held.after);
                            }
                            held.key != key
                        });
                        match self.dropped.iter_mut().find(|(k, _)| *k == key) {
                            Some((_, lost)) => *lost = (*lost).max(to),
                            None => self.dropped.push((key, to)),
                        }
                    }
                    self.mark(key);
                    return;
                }
                self.pending.push((Instant::now() + GAP_TIMEOUT, p));
            }
        }
    }

    pub(super) fn drain(&mut self, key: Key) {
        loop {
            let local = *self.counter(key);
            let passed = |p: &Pending| p.key == key && p.before < local;
            if key == Key::Seq {
                // Passed batches go through `stale`, oldest first; only batches are keyed by seq.
                let oldest = |pending: &[(Instant, Pending)]| {
                    let candidates = pending.iter().enumerate().filter(|(_, (_, p))| passed(p));
                    candidates.min_by_key(|(_, (_, p))| p.before).map(|(i, _)| i)
                };
                while let Some(i) = oldest(&self.pending[..]) {
                    let (_, p) = self.pending.remove(i);
                    self.stale(p);
                }
            } else {
                // What `stale` does with an update or a counter: nothing.
                self.pending.retain(|(_, p)| !passed(p));
            }
            let Some(i) = self.pending.iter().position(|(_, p)| p.key == key && p.before == local) else { return };
            let (_, p) = self.pending.swap_remove(i);
            self.apply(p);
        }
    }

    /// An item its key says was applied already. The seq can move past a batch without its updates having been
    /// applied, through a getDifference, which brings channel updates only when it chooses to; so, as the spec orders
    /// and tdlib does, an update a pts or qts numbers is checked against its own counter, which delivers it when it is
    /// new and drops it when it is not. One that moves its counter by 0 (`pts_count` 0) can't be told from a copy
    /// already applied by that counter, the batch's seq being its only check, so it goes with the rest.
    fn stale(&mut self, p: Pending) {
        let Item::Batch(updates, entities, _, quiet) = p.item else { return };
        for update in updates {
            if counter_of(&update, None).is_some_and(|(_, before, after)| before != after) {
                self.update(update, &entities, quiet);
            }
        }
    }

    pub(super) fn apply(&mut self, p: Pending) {
        let counter = self.counter(p.key);
        *counter = (*counter).max(p.after);
        match p.item {
            Item::Update(update, entities) => self.ready.push((update, entities)),
            Item::Batch(updates, entities, date, quiet) => {
                // Batches can arrive out of date order; the state's date only moves forward, or getDifference
                // would be asked from before updates already applied.
                self.state.date = self.state.date.max(date);
                for update in updates {
                    self.update(update, &entities, quiet);
                }
            }
            Item::Counter => {}
        }
    }

    pub(super) fn expire(&mut self, now: Instant) {
        for i in 0..self.pending.len() {
            if self.pending[i].0 <= now {
                self.mark(self.pending[i].1.key);
            }
        }
        let mut i = 0;
        while i < self.retries.len() {
            if self.retries[i].0 <= now {
                let (_, key) = self.retries.swap_remove(i);
                self.mark(key);
            } else {
                i += 1;
            }
        }
        if self.idle.is_some_and(|idle| idle <= now) {
            self.mark(Key::Pts);
            self.touch(now);
        }
    }

    /// The pts ranges given up on, when the fetch for `key` won't be retried.
    pub(super) fn recover(&mut self, result: &Result<()>, key: Key) -> Vec<Skipped> {
        let due = |k: Key| match key {
            Key::Channel(_) => k == key,
            _ => !matches!(k, Key::Channel(_)),
        };
        let flood = result.as_ref().err().and_then(Error::flood_wait);
        let retry = match (result, flood) {
            (Ok(()), _) => Err(None),
            // FLOOD_WAIT_X and friends: asking before X seconds pass only fails again.
            (_, Some(wait)) => Ok(wait.max(Duration::from_secs(1))),
            (Err(Error::Rpc(e)), _) if !(400..500).contains(&e.code) => self.backoff(key),
            (
                Err(Error::Io(_) | Error::Transport(_) | Error::Disconnected | Error::Timeout | Error::BadMessage(_)),
                _,
            ) => self.backoff(key),
            // 4xx refusals and bad answers fail the same way next time, so deliver what we hold and give up on the gap.
            (Err(_), _) => Err(Some(SkipReason::Refused)),
        };
        self.retries.retain(|(_, k)| *k != key);
        let delay = match retry {
            Ok(delay) => delay,
            Err(reason) => {
                self.failures.retain(|(k, _)| *k != key);
                let mut skipped = self.settle(due, reason);
                // What the cap dropped past the last update delivered is lost too, unless the fetch read it.
                let dropped = self.dropped.iter().find(|(k, _)| *k == key).map(|(_, to)| *to);
                self.dropped.retain(|(k, _)| !due(*k));
                if let (Some(reason), Some(to), Key::Pts | Key::Channel(_)) = (reason, dropped, key) {
                    let at = self.counter(key);
                    if *at < to {
                        skipped.push(Skipped { key, from: *at, to, reason });
                        *at = to;
                    }
                }
                // A gap only in qts, held or dropped by the cap, has no pts range: it is reported where pts is.
                if let (Some(reason), true, Key::Pts | Key::Channel(_)) = (reason, skipped.is_empty(), key) {
                    let at = *self.counter(key);
                    skipped.push(Skipped { key, from: at, to: at, reason });
                }
                return skipped;
            }
        };
        let deadline = Instant::now() + delay;
        for (d, _) in self.pending.iter_mut().filter(|(_, p)| due(p.key)) {
            *d = deadline;
        }
        // After updatesTooLong nothing may be pending, so the retry keeps its own deadline.
        self.retries.push((deadline, key));
        Vec::new()
    }

    fn backoff(&mut self, key: Key) -> std::result::Result<Duration, Option<SkipReason>> {
        let n = match self.failures.iter_mut().find(|(k, _)| *k == key) {
            Some((_, n)) => {
                *n += 1;
                *n
            }
            None => {
                self.failures.push((key, 1));
                1
            }
        };
        (n <= MAX_RETRIES).then(|| GAP_TIMEOUT * 2u32.pow(n - 1)).ok_or(Some(SkipReason::GaveUp))
    }

    /// Delivers what is held for the `due` keys; with a `reason`, the pts holes left before them are reported.
    pub(super) fn settle(&mut self, due: impl Fn(Key) -> bool, reason: Option<SkipReason>) -> Vec<Skipped> {
        let (mut settled, rest): (Vec<_>, Vec<_>) =
            std::mem::take(&mut self.pending).into_iter().partition(|(_, p)| due(p.key));
        self.pending = rest;
        settled.sort_unstable_by_key(|(_, p)| (p.key, p.before));
        let mut skipped = Vec::new();
        for (_, p) in settled {
            let local = *self.counter(p.key);
            if local >= p.after {
                self.stale(p);
                continue;
            }
            if let (Some(reason), Key::Pts | Key::Channel(_)) = (reason, p.key) {
                if local < p.before {
                    skipped.push(Skipped { key: p.key, from: local, to: p.before, reason });
                }
            }
            self.apply(p);
        }
        skipped
    }
}

#[cfg(test)]
mod tests {
    use super::{
        Arc, Duration, Entities, Error, GAP_TIMEOUT, IDLE_TIMEOUT, Instant, Key, MAX_PENDING, SkipReason, Skipped,
        Tracker, UpdateState, base, types,
    };
    use crate::errors::RpcError;

    fn delete(pts: i32, pts_count: i32) -> base::Update {
        base::Update::UpdateDeleteMessages(Box::new(types::UpdateDeleteMessages {
            messages: Vec::new(),
            pts,
            pts_count,
        }))
    }

    fn stopped(qts: i32) -> base::Update {
        base::Update::UpdateBotStopped(Box::new(types::UpdateBotStopped { user_id: 1, date: 0, stopped: true, qts }))
    }

    fn channel(channel_id: i64, pts: i32) -> base::Update {
        base::Update::UpdateDeleteChannelMessages(Box::new(types::UpdateDeleteChannelMessages {
            channel_id,
            messages: Vec::new(),
            pts,
            pts_count: 1,
        }))
    }

    fn tracker(pts: i32, qts: i32, seq: i32) -> Tracker {
        Tracker { state: UpdateState { pts, qts, seq, ..UpdateState::default() }, ..Tracker::default() }
    }

    fn delivered(t: &mut Tracker) -> Vec<i32> {
        t.ready.drain(..).map(|(u, _)| u.pts().map_or_else(|| u.qts().unwrap_or(0), |(pts, _)| pts)).collect()
    }

    fn offline() -> Error {
        Error::Io(std::io::Error::other("offline"))
    }

    #[test]
    fn buffers_pts_gap_until_filled() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.update(delete(12, 1), &e, false);
        assert!(delivered(&mut t).is_empty() && t.deadline().is_some());
        t.update(delete(11, 1), &e, false);
        assert_eq!((delivered(&mut t), t.state.pts, t.deadline()), (vec![11, 12], 12, None));
        t.update(delete(12, 1), &e, false);
        t.update(delete(14, 3), &e, false);
        assert_eq!((delivered(&mut t), t.pending.len()), (vec![], 0));
        t.update(delete(15, 3), &e, false);
        assert_eq!(delivered(&mut t), [15]);
    }

    #[test]
    fn a_key_over_the_pending_cap_falls_back_to_get_difference() {
        let (mut t, e) = (tracker(0, 0, 0), Arc::default());
        t.update(channel(5, 4), &e, false);
        t.update(channel(5, 6), &e, false);
        assert_eq!(delivered(&mut t), [4]);
        for pts in 2..=(MAX_PENDING as i32 + 1) {
            t.update(delete(pts, 1), &e, false);
        }
        assert_eq!((t.pending.len(), t.due.clone()), (MAX_PENDING + 1, vec![]));
        // The update past the cap hands the key to getDifference instead of growing the buffer; the other key keeps
        // its held updates, and neither counter moves.
        t.update(delete(MAX_PENDING as i32 + 2, 1), &e, false);
        assert_eq!((t.pending.len(), t.due.clone(), t.state.pts), (1, vec![Key::Pts], 0));

        // Per key: a channel over its own cap asks for that channel's difference, not the common box's.
        let (mut t, e) = (tracker(0, 0, 0), Arc::default());
        t.update(channel(5, 4), &e, false);
        for pts in 6..=(MAX_PENDING as i32 + 5) {
            t.update(channel(5, pts), &e, false);
        }
        assert_eq!((t.pending.len(), t.due.clone()), (MAX_PENDING, vec![]));
        t.update(channel(5, MAX_PENDING as i32 + 6), &e, false);
        assert_eq!((t.pending.len(), t.due.clone()), (0, vec![Key::Channel(5)]));
    }

    // Seq 2 never comes; each batch after it carries the next update of channel 5 and one that moves no counter.
    fn hold_seq_batches(t: &mut Tracker, e: &Arc<Entities>) -> i32 {
        for n in 1..=MAX_PENDING as i32 {
            t.batch(vec![channel(5, n), base::Update::UpdateConfig], Arc::clone(e), (n, n + 2, n + 2), false);
        }
        assert_eq!((t.ready.len(), t.pending.len(), t.due.clone()), (0, MAX_PENDING, vec![]));
        let last = MAX_PENDING as i32 + 1;
        t.batch(vec![channel(5, last)], Arc::clone(e), (last, last + 2, last + 2), false);
        last
    }

    #[test]
    fn seq_batches_over_the_cap_are_released_not_dropped() {
        let (mut t, e) = (tracker(0, 0, 1), Arc::default());
        let last = hold_seq_batches(&mut t, &e);
        // getDifference may not bring back channel updates or ones that move no counter, so every held batch goes
        // out in seq order through its updates' own keys before getDifference fetches what the hole held.
        let mut expected: Vec<i32> = (1..last).flat_map(|n| [n, 0]).collect();
        expected.push(last);
        let s = &t.state;
        assert_eq!((s.seq, s.date, s.channels[&5], s.pts), (last + 2, last, last, 0));
        assert_eq!((delivered(&mut t), t.pending.len(), t.due.clone()), (expected, 0, vec![Key::Pts]));
    }

    #[test]
    fn a_difference_that_leaves_seq_alone_does_not_refill_the_cap() {
        let (mut t, e) = (tracker(0, 0, 1), Arc::default());
        let last = hold_seq_batches(&mut t, &e);
        t.ready.clear();
        // updates.differenceTooLong with an unchanged pts sets no state, so seq stays where the release left it.
        assert_eq!(t.due.pop(), Some(Key::Pts));
        assert_eq!(t.recover(&Ok(()), Key::Pts), []);
        // The next batch follows on and goes straight out: nothing builds up towards the cap again.
        t.batch(vec![channel(5, last + 1)], e, (last + 1, last + 3, last + 3), false);
        assert_eq!((delivered(&mut t), t.pending.len(), t.due.clone()), (vec![last + 1], 0, vec![]));
        assert_eq!(t.state.seq, last + 3);
    }

    #[test]
    fn giving_up_after_the_cap_reports_what_it_dropped() {
        let (mut t, e) = (tracker(0, 0, 0), Arc::default());
        // A retry is already scheduled when pts 1 goes missing and the cap is reached, so marking the key is a no-op.
        t.recover(&Err(offline()), Key::Pts);
        let last = MAX_PENDING as i32 + 2;
        for pts in 2..=last {
            t.update(delete(pts, 1), &e, false);
        }
        assert_eq!((t.pending.len(), t.due.clone()), (0, vec![]));
        let skipped = t.recover(&Err(Error::Rpc(RpcError::parse(400, "CHANNEL_PRIVATE"))), Key::Pts);
        assert_eq!(skipped, [Skipped { key: Key::Pts, from: 0, to: last, reason: SkipReason::Refused }]);
        // The counter moves past what was given up on, so the next update goes straight out.
        t.update(delete(last + 1, 1), &e, false);
        assert_eq!((delivered(&mut t), t.state.pts), (vec![last + 1], last + 1));

        // A fetch that reads the hole forgets the dropped range: nothing is reported when a later one gives up.
        let (mut t, e) = (tracker(0, 0, 0), Arc::default());
        for pts in 2..=last {
            t.update(delete(pts, 1), &e, false);
        }
        t.state.pts = last;
        assert_eq!(t.recover(&Ok(()), Key::Pts), []);
        let refused = t.recover(&Err(Error::Rpc(RpcError::parse(400, "CHANNEL_PRIVATE"))), Key::Pts);
        assert_eq!(refused, [Skipped { key: Key::Pts, from: last, to: last, reason: SkipReason::Refused }]);
    }

    #[test]
    fn expired_gap_requests_difference() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.update(delete(12, 1), &e, false);
        t.expire(Instant::now());
        assert!(t.due.is_empty());
        t.expire(Instant::now() + GAP_TIMEOUT);
        assert_eq!(t.due, [Key::Pts]);
    }

    #[test]
    fn difference_covers_buffered_updates() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.update(delete(12, 1), &e, false);
        t.update(delete(14, 1), &e, false);
        t.state.pts = 12;
        t.settle(|key| key == Key::Pts, None);
        assert_eq!((delivered(&mut t), t.state.pts, t.pending.len()), (vec![14], 14, 0));
    }

    #[test]
    fn empty_difference_moves_qts_forward() {
        let (mut t, e) = (tracker(0, 5, 0), Arc::default());
        t.update(stopped(7), &e, false);
        assert!(delivered(&mut t).is_empty());
        t.settle(|key| !matches!(key, Key::Channel(_)), None);
        assert_eq!((delivered(&mut t), t.state.qts), (vec![7], 7));
        t.update(stopped(8), &e, false);
        assert_eq!(delivered(&mut t), [8]);
    }

    #[test]
    fn seq_gap_buffers_whole_batch() {
        let (mut t, e) = (tracker(10, 0, 1), Arc::default());
        t.batch(vec![delete(12, 1)], Arc::clone(&e), (5, 3, 3), false);
        assert!(delivered(&mut t).is_empty());
        t.batch(vec![delete(11, 1)], Arc::clone(&e), (4, 2, 2), false);
        let s = &t.state;
        assert_eq!((s.seq, s.date, s.pts), (3, 5, 12));
        assert_eq!(delivered(&mut t), [11, 12]);
        // Seq 3 was applied: of the same batch again, the update its own counter has seen and the uncounted one go.
        t.batch(vec![delete(12, 1), base::Update::UpdateConfig], e, (6, 3, 3), false);
        assert!(delivered(&mut t).is_empty());
    }

    #[test]
    fn a_stale_seq_batch_still_applies_what_its_own_counters_have_not_seen() {
        let (mut t, e) = (tracker(10, 0, 5), Arc::default());
        t.state.channels.insert(5, 3);
        t.state.channels.insert(6, 2);
        // Seq 4 came through a getDifference that brought no channel updates: channel 5's is new, channel 6's and the
        // common box's were seen, and the uncounted one came with seq 4.
        let updates = vec![channel(5, 4), channel(6, 2), delete(10, 1), base::Update::UpdateConfig];
        t.batch(updates, e, (9, 4, 4), false);
        let s = &t.state;
        assert_eq!((s.seq, s.date, s.channels[&5], s.channels[&6], s.pts), (5, 0, 4, 2, 10));
        assert_eq!((delivered(&mut t), t.pending.len()), (vec![4], 0));
    }

    #[test]
    fn a_held_seq_batch_the_seq_passes_still_applies_its_counted_updates() {
        // A later batch passes the held one's seq: the held one's channel update is still new for the channel.
        let (mut t, e) = (tracker(0, 0, 1), Arc::default());
        t.batch(vec![channel(5, 1)], Arc::clone(&e), (1, 3, 3), false);
        t.batch(vec![base::Update::UpdateConfig], Arc::clone(&e), (2, 2, 4), false);
        let s = &t.state;
        assert_eq!((s.seq, s.channels[&5], t.pending.len()), (4, 1, 0));
        assert_eq!(delivered(&mut t), [0, 1]);

        // A later batch covers the held one's seq and carries its channel update too, which goes out once.
        let (mut t, e) = (tracker(0, 0, 1), Arc::default());
        t.batch(vec![channel(5, 1), base::Update::UpdateConfig], Arc::clone(&e), (1, 3, 3), false);
        t.batch(vec![channel(5, 1), channel(5, 2), base::Update::UpdateConfig], Arc::clone(&e), (2, 2, 4), false);
        assert_eq!((delivered(&mut t), t.state.seq, t.pending.len()), (vec![1, 2, 0], 4, 0));

        // A getDifference moves seq past a held batch: its channel update is still new for the channel.
        let (mut t, e) = (tracker(0, 0, 1), Arc::default());
        t.batch(vec![channel(5, 1), base::Update::UpdateConfig], e, (1, 3, 3), false);
        t.state.seq = 3;
        t.settle(|key| !matches!(key, Key::Channel(_)), None);
        assert_eq!((delivered(&mut t), t.state.channels[&5], t.pending.len()), (vec![1], 1, 0));
    }

    #[test]
    fn a_stale_seq_batch_never_delivers_an_update_that_moves_no_counter_again() {
        // Seq 2 again: delete(10, 0) moves pts by 0, so only the batch's seq tells the copy from the original.
        let (mut t, e) = (tracker(10, 0, 1), Arc::default());
        t.batch(vec![delete(10, 0)], Arc::clone(&e), (1, 2, 2), false);
        assert_eq!(delivered(&mut t), [10]);
        t.batch(vec![delete(10, 0)], Arc::clone(&e), (1, 2, 2), false);
        assert_eq!((delivered(&mut t), t.state.pts, t.pending.len()), (vec![], 10, 0));

        // A getDifference hands the update over itself and moves seq past the batch held with it.
        let (mut t, e) = (tracker(10, 0, 1), Arc::default());
        t.batch(vec![delete(10, 0)], Arc::clone(&e), (1, 3, 3), false);
        t.emit(delete(10, 0), &e);
        t.state.seq = 3;
        t.settle(|key| !matches!(key, Key::Channel(_)), None);
        assert_eq!((delivered(&mut t), t.pending.len()), (vec![10], 0));
    }

    #[test]
    fn updates_pts_changed_drops_the_old_numbered_updates_of_held_seq_batches() {
        let (mut t, e) = (tracker(10, 0, 1), Arc::default());
        t.batch(vec![delete(500, 1), channel(5, 1)], Arc::clone(&e), (1, 3, 3), false);
        t.batch(vec![delete(501, 1), base::Update::UpdateConfig], e, (1, 4, 4), false);
        // getState renumbered pts down to 3 and put seq at 3: one held batch has passed, the next follows on.
        t.restate(&types::updates::State { pts: 3, qts: 0, date: 0, seq: 3, unread_count: 0 });
        let s = &t.state;
        assert_eq!((s.pts, s.seq, s.channels[&5], t.pending.len()), (3, 4, 1, 0));
        assert_eq!(delivered(&mut t), [1, 0]);
    }

    #[test]
    fn updates_with_a_pts_or_qts_of_0_go_out_and_move_no_counter() {
        let (mut t, e) = (tracker(10, 5, 0), Arc::default());
        t.update(delete(0, 0), &e, false);
        t.update(stopped(0), &e, false);
        t.update(channel(5, 0), &e, false);
        assert_eq!(delivered(&mut t), [0, 0, 0]);
        let s = &t.state;
        assert_eq!((s.pts, s.qts, s.channels.get(&5), t.pending.len()), (10, 5, None, 0));
        // Quiet, one is neither delivered nor counted; the next numbered update follows on as before.
        t.update(delete(0, 1), &e, true);
        t.update(delete(11, 1), &e, false);
        assert_eq!((delivered(&mut t), t.state.pts), (vec![11], 11));
        t.update(stopped(6), &e, false);
        assert_eq!((delivered(&mut t), t.state.qts), (vec![6], 6));

        // A channel with a stored counter, the case the rule is for: against 20, pts 0 would pass for one seen.
        t.state.channels.insert(5, 20);
        t.update(channel(5, 0), &e, false);
        assert_eq!((delivered(&mut t), t.state.channels[&5], t.pending.len()), (vec![0], 20, 0));
        t.update(channel(5, 21), &e, false);
        assert_eq!((delivered(&mut t), t.state.channels[&5]), (vec![21], 21));
    }

    #[test]
    fn channel_too_long_starts_an_unknown_channel_at_the_pts_given() {
        let (mut t, e) = (tracker(0, 0, 0), Arc::default());
        let too_long = |channel_id, pts| {
            base::Update::UpdateChannelTooLong(Box::new(types::UpdateChannelTooLong { channel_id, pts }))
        };
        t.state.channels.insert(6, 7);
        t.update(too_long(5, Some(40)), &e, false);
        t.update(too_long(6, Some(40)), &e, false);
        t.update(too_long(8, None), &e, false);
        t.update(too_long(9, Some(0)), &e, false);
        // A stored pts is kept, since fetching from it misses nothing; with none at all there is nothing to store.
        let stored: Vec<_> = [5_i64, 6, 8, 9].iter().map(|id| t.state.channels.get(id).copied()).collect();
        assert_eq!(stored, [Some(40), Some(7), None, None]);
        let due = [5, 6, 8, 9].map(Key::Channel).to_vec();
        assert_eq!((t.due.clone(), delivered(&mut t)), (due, vec![]));
    }

    #[test]
    fn an_older_batch_does_not_move_the_date_back() {
        let (mut t, e) = (tracker(10, 0, 1), Arc::default());
        t.batch(vec![delete(11, 1)], Arc::clone(&e), (5, 2, 2), false);
        assert_eq!((t.state.seq, t.state.date), (2, 5));
        t.batch(vec![delete(12, 1)], e, (4, 3, 3), false);
        assert_eq!((delivered(&mut t), t.state.seq, t.state.date), (vec![11, 12], 3, 5));
    }

    #[test]
    fn quiet_updates_move_counters_silently() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.short(12, 1, true);
        t.update(delete(11, 1), &e, false);
        assert_eq!((delivered(&mut t), t.state.pts), (vec![11], 12));
        t.update(delete(13, 1), &e, true);
        assert_eq!((delivered(&mut t), t.state.pts), (vec![], 13));
    }

    #[test]
    fn failed_difference_keeps_the_gap() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.update(delete(12, 1), &e, false);
        t.recover(&Err(offline()), Key::Pts);
        t.recover(&Err(Error::Timeout), Key::Pts);
        assert_eq!((delivered(&mut t), t.state.pts, t.pending.len()), (vec![], 10, 1));
        t.update(delete(11, 1), &e, false);
        assert_eq!(delivered(&mut t), [11, 12]);
    }

    #[test]
    fn refused_difference_delivers_held_updates() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.update(delete(12, 1), &e, false);
        let skipped = t.recover(&Err(Error::Rpc(RpcError::parse(400, "CHANNEL_PRIVATE"))), Key::Pts);
        assert_eq!(skipped, [Skipped { key: Key::Pts, from: 10, to: 11, reason: SkipReason::Refused }]);
        assert_eq!(delivered(&mut t), [12]);
        t.update(delete(14, 1), &e, false);
        t.recover(&Err(Error::Unexpected("bad difference")), Key::Pts);
        assert_eq!((delivered(&mut t), t.pending.len(), t.deadline()), (vec![14], 0, None));
    }

    #[test]
    fn silence_requests_difference() {
        let mut t = tracker(10, 0, 0);
        let start = Instant::now();
        t.touch(start);
        t.expire(start + IDLE_TIMEOUT - GAP_TIMEOUT);
        t.touch(start + GAP_TIMEOUT);
        t.expire(start + IDLE_TIMEOUT);
        assert!(t.due.is_empty());
        t.expire(start + GAP_TIMEOUT + IDLE_TIMEOUT);
        assert_eq!((t.due.clone(), t.deadline()), (vec![Key::Pts], Some(start + GAP_TIMEOUT + 2 * IDLE_TIMEOUT)));
    }

    #[test]
    fn flood_wait_retries_after_the_wait() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.update(delete(12, 1), &e, false);
        t.recover(&Err(Error::Rpc(RpcError::parse(420, "FLOOD_WAIT_30"))), Key::Pts);
        assert!(delivered(&mut t).is_empty());
        t.expire(Instant::now() + GAP_TIMEOUT);
        assert!(t.due.is_empty());
        t.expire(Instant::now() + Duration::from_secs(31));
        assert_eq!(t.due, [Key::Pts]);
    }

    #[test]
    fn new_gaps_wait_for_a_scheduled_retry() {
        let mut t = tracker(10, 0, 0);
        t.recover(&Err(Error::Rpc(RpcError::parse(420, "FLOOD_WAIT_30"))), Key::Pts);
        t.mark(Key::Pts);
        t.mark(Key::Qts);
        assert!(t.due.is_empty());
        t.expire(Instant::now() + Duration::from_secs(31));
        assert_eq!(t.due, [Key::Pts]);
    }

    #[test]
    fn failed_catch_up_retries_with_nothing_held() {
        let mut t = tracker(10, 0, 0);
        t.recover(&Err(offline()), Key::Pts);
        t.recover(&Err(offline()), Key::Channel(1));
        assert!(t.deadline().is_some());
        t.expire(Instant::now() + GAP_TIMEOUT);
        assert_eq!((t.due.clone(), t.deadline()), (vec![Key::Pts, Key::Channel(1)], None));
        t.recover(&Err(offline()), Key::Pts);
        t.recover(&Ok(()), Key::Pts);
        assert!(t.deadline().is_none());
    }

    #[test]
    fn repeated_failures_back_off_then_give_up() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.update(delete(12, 1), &e, false);
        for n in 0..5 {
            let start = Instant::now();
            t.recover(&Err(offline()), Key::Pts);
            assert!(t.deadline() >= Some(start + GAP_TIMEOUT * 2u32.pow(n)));
        }
        let skipped = t.recover(&Err(offline()), Key::Pts);
        assert_eq!(skipped, [Skipped { key: Key::Pts, from: 10, to: 11, reason: SkipReason::GaveUp }]);
        assert_eq!((delivered(&mut t), t.pending.len(), t.deadline()), (vec![12], 0, None));
    }

    #[test]
    fn giving_up_with_nothing_held_reports_where_it_stopped() {
        let mut t = tracker(0, 0, 0);
        t.state.channels.insert(1, 7);
        let skipped = t.recover(&Err(Error::Rpc(RpcError::parse(400, "CHANNEL_PRIVATE"))), Key::Channel(1));
        assert_eq!(skipped, [Skipped { key: Key::Channel(1), from: 7, to: 7, reason: SkipReason::Refused }]);
        assert!(t.recover(&Ok(()), Key::Pts).is_empty());
    }

    #[test]
    fn quiet_channel_updates_move_channel_counters() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        t.update(channel(5, 20), &e, true);
        t.update(channel(5, 21), &e, false);
        assert_eq!((delivered(&mut t), t.state.channels[&5], t.state.pts), (vec![21], 21, 10));
    }

    #[test]
    fn channel_message_without_peer_is_skipped() {
        let (mut t, e) = (tracker(10, 0, 0), Arc::default());
        let message = base::Message::MessageEmpty(Box::new(types::MessageEmpty { id: 1, peer_id: None }));
        let update = types::UpdateNewChannelMessage { message, pts: 11, pts_count: 1 };
        t.update(base::Update::UpdateNewChannelMessage(Box::new(update)), &e, false);
        assert_eq!((delivered(&mut t), t.state.pts, t.pending.len()), (vec![], 10, 0));
    }

    #[test]
    fn channel_gaps_are_per_channel() {
        let (mut t, e) = (tracker(0, 0, 0), Arc::default());
        t.update(channel(1, 5), &e, false);
        t.update(channel(2, 9), &e, false);
        assert_eq!(delivered(&mut t), [5, 9]);
        t.update(channel(1, 7), &e, false);
        t.update(channel(2, 10), &e, false);
        assert_eq!(delivered(&mut t), [10]);
        t.expire(Instant::now() + GAP_TIMEOUT);
        let too_long = types::UpdateChannelTooLong { channel_id: 1, pts: None };
        t.update(base::Update::UpdateChannelTooLong(Box::new(too_long)), &e, false);
        assert_eq!(t.due, [Key::Channel(1)]);
        t.state.channels.insert(1, 7);
        t.settle(|key| key == Key::Channel(1), None);
        assert_eq!((delivered(&mut t), t.pending.len()), (vec![], 0));
    }

    #[test]
    fn a_refused_qts_fetch_is_not_reported_as_a_pts_range() {
        let mut t = tracker(10, 5, 0);
        let refused = Err(Error::Rpc(crate::errors::RpcError::parse(400, "CHANNEL_PRIVATE")));
        assert_eq!(t.recover(&refused, Key::Qts), []);
    }
}