sequence.rs 22.8 KB
Newer Older
1
// SPDX-FileCopyrightText: Copyright (c) 2024-2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
2
3
// SPDX-License-Identifier: Apache-2.0

4
use crate::common::protocols::MoveBlock;
5
use derive_getters::Getters;
6
use dynamo_tokens::blocks::UniqueBlock;
7
use dynamo_tokens::{PositionalLineageHash, TokenBlockSequence, Tokens};
8
use rand::random;
9
use validator::Validate;
10

11
12
/// Create unique blocks, block hashes, and positional-lineage hashes from a
/// [`TokenBlockSequence`].
13
fn create_sequence_cache(
14
    tokens: &TokenBlockSequence,
15
16
    block_size: usize,
    enable_prefix_caching: bool,
17
) -> (Vec<UniqueBlock>, Vec<u64>, Vec<PositionalLineageHash>) {
18
19
    let mut unique_blocks = Vec::with_capacity(tokens.blocks().len() + 1);
    let mut block_hashes = Vec::with_capacity(tokens.blocks().len());
20
    let mut plhs = Vec::with_capacity(tokens.blocks().len());
21

22
    for (pos, block) in tokens.blocks().iter().enumerate() {
23
        block_hashes.push(block.block_hash());
24
25
26
27
28
29
30
31
32
33
34
        if enable_prefix_caching {
            unique_blocks.push(UniqueBlock::FullBlock(block.sequence_hash()));
            plhs.push(block.positional_lineage_hash());
        } else {
            unique_blocks.push(UniqueBlock::FullBlock(random::<u64>()));
            plhs.push(PositionalLineageHash::new(
                random::<u64>(),
                None,
                pos as u64,
            ));
        }
35
    }
36
37

    // Only push the partial block if tokens count isn't a multiple of block_size
38
    if !tokens.total_tokens().is_multiple_of(block_size) {
Yan Ru Pei's avatar
Yan Ru Pei committed
39
        unique_blocks.push(UniqueBlock::default());
40
    }
41
    (unique_blocks, block_hashes, plhs)
42
43
44
45
}

/// A sequence that is actively being built, with the ability to add tokens and commit to hashes
/// TODO: reuse tokens
46
#[derive(Debug, Getters, Validate)]
47
48
pub struct ActiveSequence {
    unique_blocks: Vec<UniqueBlock>,
49
    block_hashes: Vec<u64>,
50
    plhs: Vec<PositionalLineageHash>,
51
52
53
54

    tokens: TokenBlockSequence,

    #[getter(copy)]
55
    #[validate(range(min = 2))]
56
    block_size: usize,
57
58
59
60
61
62
63
64
65
66

    #[getter(copy)]
    max_output_tokens: usize,

    #[getter(copy)]
    generated_tokens: usize,

    #[getter(copy)]
    num_input_tokens: usize,

67
68
    #[getter(copy)]
    num_allocated_tokens: usize,
69
70
71

    #[getter(copy)]
    enable_prefix_caching: bool,
72
73
74

    #[getter(copy)]
    emit_token_ids: bool,
75
76
77
78
79
80
81
}

impl ActiveSequence {
    /// Create a new ActiveSequence instance with the provided tokens
    pub fn new(
        tokens: Vec<u32>,
        max_output_tokens: usize,
82
83
        block_size: Option<usize>,
        enable_prefix_caching: bool,
84
        emit_token_ids: bool,
85
86
87
88
    ) -> Self {
        let block_size = block_size.unwrap_or(64);
        let num_input_tokens = tokens.len();

89
        let tokens = Tokens::from(tokens).into_sequence(block_size as u32, Some(1337));
90
        let (unique_blocks, block_hashes, plhs) =
91
            create_sequence_cache(&tokens, block_size, enable_prefix_caching);
92

93
        let seq = Self {
94
            unique_blocks,
95
            block_hashes,
96
            plhs,
97
98
99
100
101
            tokens,
            block_size,
            max_output_tokens,
            generated_tokens: 0,
            num_input_tokens,
102
            num_allocated_tokens: 0,
103
            enable_prefix_caching,
104
            emit_token_ids,
105
106
107
        };
        seq.validate().expect("invalid ActiveSequence");
        seq
108
109
    }

110
    pub fn extra_tokens(&self) -> u32 {
111
        (self.len() % self.block_size) as u32
112
113
114
115
116
117
118
119
120
121
    }

    pub fn len(&self) -> usize {
        self.tokens.total_tokens()
    }

    pub fn is_empty(&self) -> bool {
        self.tokens.total_tokens() == 0
    }

122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
    /// Build a `MoveBlock::Use` signal for blocks up to `cumulative_tokens`
    /// without updating internal state. Returns `None` if no new blocks are needed.
    /// Call `commit_allocation` after the signal is successfully processed.
    pub fn prepare_allocation(&self, cumulative_tokens: usize) -> Option<MoveBlock> {
        let prev_blocks = self
            .num_allocated_tokens
            .div_ceil(self.block_size)
            .min(self.unique_blocks.len());
        let target_blocks = cumulative_tokens
            .div_ceil(self.block_size)
            .min(self.unique_blocks.len());
        if target_blocks <= prev_blocks {
            return None;
        }

        let range = prev_blocks..target_blocks;
        let blocks = self.unique_blocks[range.clone()].to_vec();

140
141
142
        let hash_start = prev_blocks.min(self.block_hashes.len());
        let hash_end = target_blocks.min(self.block_hashes.len());
        let hashes = self.block_hashes[hash_start..hash_end].to_vec();
143
144
        // Cached per-sequence PLHs (stable across calls).
        let plhs = self.plhs[hash_start..hash_end].to_vec();
145
146

        let token_ids = if self.emit_token_ids && hash_start < hash_end {
147
148
149
150
151
152
            Some(
                self.tokens.blocks()[hash_start..hash_end]
                    .iter()
                    .map(|b| b.tokens().to_vec())
                    .collect(),
            )
153
154
155
156
        } else {
            None
        };

157
158
159
160
161
        let parent = if prev_blocks > 0 {
            Some(self.unique_blocks[prev_blocks - 1].clone())
        } else {
            None
        };
162
163
164
165
166
        Some(MoveBlock::Use(blocks, hashes, plhs, token_ids, parent))
    }

    /// Positional lineage hashes for all fully-tokenised blocks in the sequence.
    /// Mirrors `block_hashes()` but returns the PLH identity used by kvbm-logical.
167
168
    pub fn positional_lineage_hashes(&self) -> &[PositionalLineageHash] {
        &self.plhs
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
    }

    /// Commit a successful allocation by advancing `num_allocated_tokens`.
    pub fn commit_allocation(&mut self, cumulative_tokens: usize) {
        self.num_allocated_tokens = cumulative_tokens;
    }

    /// Prepare + commit in one call (convenience for paths where failure is impossible).
    pub fn allocate_blocks_for_chunk(&mut self, cumulative_tokens: usize) -> Option<MoveBlock> {
        let signal = self.prepare_allocation(cumulative_tokens);
        self.commit_allocation(cumulative_tokens);
        signal
    }

    /// Allocate all remaining blocks at once (backward compat).
184
    pub fn take_creation_signal(&mut self) -> Option<MoveBlock> {
185
        self.allocate_blocks_for_chunk(self.len())
186
187
    }

188
189
190
191
    /// Create a new ActiveSequence instance and return the creation signal
    pub fn new_with_signal(
        tokens: Vec<u32>,
        max_output_tokens: usize,
192
193
        block_size: Option<usize>,
        enable_prefix_caching: bool,
194
    ) -> (Self, Option<MoveBlock>) {
195
196
197
198
199
200
201
        let mut sequence = Self::new(
            tokens,
            max_output_tokens,
            block_size,
            enable_prefix_caching,
            false,
        );
202
        let signal = sequence.take_creation_signal();
203
204
205
206
207
208
209
210
        (sequence, signal)
    }

    /// Push a token to the sequence
    pub fn push(&mut self, token: u32) -> Option<Vec<MoveBlock>> {
        self.tokens.append(token).expect("Token push failed.");
        self.generated_tokens += 1;

211
        if self.len() % self.block_size != 1 {
212
213
214
215
216
217
218
219
220
            return None;
        }

        // Add a partial block for the first token in a new partial sequence
        // Send Use signal (to allocate space for this new generation block)
        let mut signals = Vec::new();

        // Replace last partial block with full block if it exists
        if let Some(UniqueBlock::PartialBlock(uuid)) = self.unique_blocks.last().cloned() {
221
            let last_complete = self.tokens.last_complete_block().unwrap();
Yan Ru Pei's avatar
Yan Ru Pei committed
222
            let last_seq_hash = if self.enable_prefix_caching {
223
                last_complete.sequence_hash()
224
225
226
            } else {
                random::<u64>()
            };
227
            let last_block_hash = last_complete.block_hash();
228
229
230
231
232
233
234
235
236
            // Same randomization story as `last_seq_hash`: with prefix caching off,
            // two identical prompts must not share blocks, so the PLH we promote
            // with must also be unique — otherwise `process_promote`'s
            // `match_blocks(&[plh])` lookup would reuse another request's block.
            let last_plh = if self.enable_prefix_caching {
                last_complete.positional_lineage_hash()
            } else {
                PositionalLineageHash::new(random::<u64>(), None, self.block_hashes.len() as u64)
            };
237
238
239
240
241
            let promote_token_ids = if self.emit_token_ids {
                Some(last_complete.tokens().to_vec())
            } else {
                None
            };
242
            self.block_hashes.push(last_block_hash);
243
            self.plhs.push(last_plh);
244
            self.unique_blocks.pop();
Yan Ru Pei's avatar
Yan Ru Pei committed
245
246
247
248
249
250
251

            // After pop, the last element is the parent block
            let second_to_last_hash = self.unique_blocks.last().map(|block| match block {
                UniqueBlock::FullBlock(hash) => *hash,
                UniqueBlock::PartialBlock(_) => panic!("Cannot have a partial block as parent"),
            });

252
            self.unique_blocks
Yan Ru Pei's avatar
Yan Ru Pei committed
253
                .push(UniqueBlock::FullBlock(last_seq_hash));
254
255
            signals.push(MoveBlock::Promote(
                uuid,
Yan Ru Pei's avatar
Yan Ru Pei committed
256
257
                last_seq_hash,
                second_to_last_hash,
258
                last_block_hash,
259
                last_plh,
260
                promote_token_ids,
261
            ));
262
263
264
265
        }

        let new_partial_block = UniqueBlock::default();
        self.unique_blocks.push(new_partial_block.clone());
266
267
268
269
270
271
272
        signals.push(MoveBlock::Use(
            vec![new_partial_block],
            vec![],
            vec![],
            None,
            None,
        ));
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
        Some(signals)
    }

    /// Generate a random token, push it to the sequence, and increment generation count.
    ///
    /// This function:
    /// - Generates a random token and adds it to the current sequence
    /// - Acquires a new partial block if needed or promotes an existing partial block to a full block
    /// - Returns appropriate signals for the KvManager to process
    ///
    /// # Panics
    ///
    /// Calling this function when max_output_tokens has already been reached will cause a panic.
    /// Always check `generated_tokens < max_output_tokens` before calling this method.
    pub fn generate(&mut self) -> Vec<MoveBlock> {
        // Assert that we haven't reached the maximum output tokens
        assert!(
            self.generated_tokens < self.max_output_tokens,
            "Cannot generate more tokens: reached max_output_tokens limit"
        );

        // Generate a random token
        let token = random::<u32>();

        // Collect signals
        let mut signals = Vec::new();

        // Push the token to the sequence and collect any signals
        if let Some(move_blocks) = self.push(token) {
            signals.extend(move_blocks);
        }

        // Check if we've reached the limit after pushing
        if self.generated_tokens != self.max_output_tokens {
            return signals;
        }

        // Free all blocks when we reach max tokens
311
        signals.extend(self.free_signal_for_tokens(self.len()));
312
313
314
        signals
    }

315
316
317
318
319
    fn free_signal_for_tokens(&self, active_tokens: usize) -> Vec<MoveBlock> {
        let active_blocks = active_tokens
            .div_ceil(self.block_size)
            .min(self.unique_blocks.len());
        self.unique_blocks[..active_blocks]
320
321
322
323
            .iter()
            .rev()
            .map(|block| match block {
                UniqueBlock::PartialBlock(uuid) => {
324
                    MoveBlock::Deref(vec![UniqueBlock::PartialBlock(*uuid)])
325
326
327
328
329
330
331
332
                }
                UniqueBlock::FullBlock(hash) => {
                    MoveBlock::Deref(vec![UniqueBlock::FullBlock(*hash)])
                }
            })
            .collect()
    }

333
334
335
336
337
    /// Free the currently active allocation footprint.
    pub fn free_signal(&self) -> Vec<MoveBlock> {
        self.free_signal_for_tokens(self.num_allocated_tokens)
    }

338
    /// Move the request to a preempted state and return the free signals from freeing current blocks.
339
    /// Upon preemption, the sequence retains the tokens generated during the decode phase (if any).
340
    /// Resets `num_allocated_tokens` so re-admission will re-allocate from scratch.
341
342
    pub fn reset_with_signal(&mut self) -> Vec<MoveBlock> {
        let free_signal = self.free_signal();
343
        self.num_allocated_tokens = 0;
344
345
346
        free_signal
    }

347
348
349
350
351
352
353
    /// Pops the last token in the sequence.
    ///
    /// This is only used to undo a freshly generated decode token after a failed
    /// allocation/preemption path. Under that invariant, the token being removed
    /// must be in the current partial block, so we only need to drop the trailing
    /// partial `UniqueBlock` when the sequence length returns to an exact block
    /// boundary. Using this to unwind arbitrary prompt history would be incorrect.
354
355
356
357
358
    pub fn pop(&mut self) {
        self.tokens.pop();
        self.generated_tokens = self.generated_tokens.saturating_sub(1);

        // Reverts to the last full block
359
        if self.tokens.total_tokens().is_multiple_of(self.block_size) {
360
361
362
363
364
365
366
367
368
            self.unique_blocks.pop();
        }
    }
}

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

369
370
371
372
373
374
375
    fn block_hashes_from_tokens(seq: &ActiveSequence) -> Vec<u64> {
        seq.tokens
            .blocks()
            .iter()
            .map(|block| block.block_hash())
            .collect()
    }
376

377
378
379
380
381
382
383
384
385
386
    fn assert_cached_hashes_match_promoted_blocks(seq: &ActiveSequence) {
        let num_full_unique_blocks = seq
            .unique_blocks()
            .iter()
            .filter(|block| matches!(block, UniqueBlock::FullBlock(_)))
            .count();
        assert_eq!(
            seq.block_hashes().as_slice(),
            &block_hashes_from_tokens(seq)[..num_full_unique_blocks],
            "cached block hashes should match the promoted full blocks"
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
    fn assert_use_signal(
        signal: &MoveBlock,
        expected_blocks: &[UniqueBlock],
        expected_hashes: &[u64],
    ) {
        match signal {
            MoveBlock::Use(blocks, hashes, ..) => {
                assert_eq!(blocks, expected_blocks);
                assert_eq!(hashes, expected_hashes);
            }
            _ => panic!("Expected MoveBlock::Use"),
        }
    }

    fn assert_single_partial_use(signal: &MoveBlock) {
        match signal {
            MoveBlock::Use(blocks, hashes, ..) => {
                assert_eq!(blocks.len(), 1);
                assert!(matches!(blocks[0], UniqueBlock::PartialBlock(_)));
                assert!(hashes.is_empty());
            }
            _ => panic!("Expected MoveBlock::Use with a single partial block"),
        }
    }
414

415
416
    fn assert_promote_parent(signal: &MoveBlock, expected_parent: Option<u64>) {
        match signal {
417
            MoveBlock::Promote(_, _, parent_hash, _hash, ..) => {
418
                assert_eq!(*parent_hash, expected_parent);
419
            }
420
            _ => panic!("Expected MoveBlock::Promote"),
421
        }
422
    }
423

424
    fn assert_deref_partial(signal: &MoveBlock) {
425
        match signal {
426
            MoveBlock::Deref(blocks) => {
427
428
429
                assert_eq!(blocks.len(), 1);
                assert!(matches!(blocks[0], UniqueBlock::PartialBlock(_)));
            }
430
            _ => panic!("Expected MoveBlock::Deref for partial block"),
431
432
433
434
435
436
437
438
439
440
        }
    }

    fn assert_deref_full(signal: &MoveBlock) {
        match signal {
            MoveBlock::Deref(blocks) => {
                assert_eq!(blocks.len(), 1);
                assert!(matches!(blocks[0], UniqueBlock::FullBlock(_)));
            }
            _ => panic!("Expected MoveBlock::Deref for full block"),
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
    }

    #[test]
    fn test_new_with_signal_creates_initial_partial_block() {
        let initial_tokens: Vec<u32> = (0..15).collect();
        let (seq, signal) = ActiveSequence::new_with_signal(initial_tokens, 100, Some(16), true);

        assert_eq!(seq.num_input_tokens(), 15);
        assert_eq!(seq.len(), 15);
        assert_single_partial_use(signal.as_ref().expect("Expected initial Use signal"));
    }

    #[test]
    fn test_push_across_block_boundary_promotes_and_allocates_partial() {
        let initial_tokens: Vec<u32> = (0..15).collect();
        let (mut seq, _) = ActiveSequence::new_with_signal(initial_tokens, 100, Some(16), true);

        let signal_15 = seq.push(15);
        assert!(
            signal_15.is_none(),
            "Completing a block should not trigger signals"
        );

        let signal_16 = seq.push(16).expect("Expected boundary crossing signals");
        assert_eq!(signal_16.len(), 2);
        assert_promote_parent(&signal_16[0], None);
        assert_single_partial_use(&signal_16[1]);

        assert_eq!(
            seq.unique_blocks().len(),
            2,
            "sequence should have one full block and one partial block"
        );
        assert_eq!(
            seq.len() % seq.block_size(),
            1,
            "sequence should have one token in the new partial block"
        );
    }
481

482
483
484
485
486
487
    #[test]
    fn test_equivalent_histories_preserve_full_block_identity() {
        let initial_tokens: Vec<u32> = (0..15).collect();
        let (mut seq1, _) = ActiveSequence::new_with_signal(initial_tokens, 100, Some(16), true);
        seq1.push(15);
        seq1.push(16);
488
489

        let extended_tokens: Vec<u32> = (0..16).collect();
490
        let (mut seq2, _) = ActiveSequence::new_with_signal(extended_tokens, 100, Some(16), true);
491
492
493
494
        seq2.push(16);
        seq2.pop();
        seq2.push(16);

495
496
497
        assert_eq!(seq1.unique_blocks()[0], seq2.unique_blocks()[0]);
        assert_ne!(seq1.unique_blocks()[1], seq2.unique_blocks()[1]);
    }
498

499
500
501
502
503
504
    #[test]
    fn test_promote_uses_previous_full_block_as_parent() {
        let initial_tokens: Vec<u32> = (0..15).collect();
        let (mut seq, _) = ActiveSequence::new_with_signal(initial_tokens, 100, Some(16), true);
        seq.push(15);
        seq.push(16);
505

506
507
508
509
        seq.push(17);
        seq.pop();
        seq.pop();
        seq.push(16);
510

511
512
513
514
515
516
        let extended_tokens: Vec<u32> = (0..16).collect();
        let (mut seq_equiv, _) =
            ActiveSequence::new_with_signal(extended_tokens, 100, Some(16), true);
        seq_equiv.push(16);
        seq_equiv.pop();
        seq_equiv.push(16);
517
        for token in 17..33 {
518
519
            seq.push(token);
            seq_equiv.push(token);
520
521
522
        }

        assert_eq!(
523
524
525
            &seq.unique_blocks()[0..2],
            &seq_equiv.unique_blocks()[0..2],
            "first two full blocks should remain identical"
526
527
        );

528
        for token in 33..48 {
529
            seq.push(token);
530
531
        }

532
533
534
        let signal = seq
            .push(48)
            .expect("Expected promote when opening next partial");
535

536
537
538
539
540
541
        let UniqueBlock::FullBlock(expected_hash) = seq.unique_blocks()[1] else {
            panic!("unique_blocks[1] should be a full block");
        };
        assert_promote_parent(&signal[0], Some(expected_hash));
        assert_single_partial_use(&signal[1]);
    }
542

543
544
545
546
547
548
549
    #[test]
    fn test_reset_with_signal_frees_blocks_and_resets_allocation() {
        let initial_tokens: Vec<u32> = (0..15).collect();
        let (mut seq, _) = ActiveSequence::new_with_signal(initial_tokens, 100, Some(16), true);
        seq.push(15);
        seq.push(16);
        seq.commit_allocation(seq.len());
550

551
        let free_signals = seq.reset_with_signal();
552

553
        assert!(!free_signals.is_empty());
554
555
        assert_eq!(seq.num_allocated_tokens(), 0);
        assert_eq!(seq.generated_tokens(), 2);
556
557
558
559
560
561
    }

    #[test]
    fn test_active_sequence_generate_signals() {
        // Create a sequence with block size 16, max_output_tokens 4, initialized with tokens [0..14)
        let initial_tokens: Vec<u32> = (0..14).collect();
562
        let (mut seq, signal) = ActiveSequence::new_with_signal(initial_tokens, 5, Some(16), true);
563
564

        // Initial signal - should have received a Use signal for the partial block
565
        assert_single_partial_use(signal.as_ref().expect("Expected initial Use signal"));
566
567
568
569
570
571
572
573
574
575

        // Generate first two tokens - should not trigger new signals
        seq.generate();
        let signals_first = seq.generate();
        assert_eq!(signals_first.len(), 0);

        // Generate third token - this fills the block and should trigger both Promote and Use signals
        let signals_second = seq.generate();
        assert_eq!(signals_second.len(), 2);

576
        // First signal should be Promote
577
        assert_promote_parent(&signals_second[0], None);
578
579

        // Second signal should be Use for new partial block
580
        assert_single_partial_use(&signals_second[1]);
581
582
583
584
585

        // Generate fourth token - should not trigger new signals as it's adding to partial block
        let signals_third = seq.generate();
        assert_eq!(signals_third.len(), 0);

586
        // Generate last token - we reach max_output_tokens, should trigger Deref signals
587
588
589
        let signals_last = seq.generate();
        assert_eq!(signals_last.len(), 2);

590
591
        // First signal should be Deref for the partial block
        assert_deref_partial(&signals_last[0]);
592
593

        // Second signal should be Deref for the full block
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
        assert_deref_full(&signals_last[1]);
    }

    #[test]
    fn test_prepare_allocation_slices_full_and_partial_blocks() {
        let tokens: Vec<u32> = (0..10).collect();
        let seq = ActiveSequence::new(tokens, 4, Some(4), true, false);

        let first = seq.prepare_allocation(4).unwrap();
        assert_use_signal(
            &first,
            &seq.unique_blocks()[0..1],
            &seq.block_hashes()[0..1],
        );

        let second = seq.prepare_allocation(8).unwrap();
        assert_use_signal(
            &second,
            &seq.unique_blocks()[0..2],
            &seq.block_hashes()[0..2],
        );

        let third = seq.prepare_allocation(10).unwrap();
        assert_use_signal(
            &third,
            &seq.unique_blocks()[0..3],
            &seq.block_hashes()[0..2],
        );
    }

    #[test]
    fn test_prepare_allocation_is_stable_until_commit() {
        let tokens: Vec<u32> = (0..10).collect();
        let mut seq = ActiveSequence::new(tokens, 4, Some(4), true, false);

        let first = seq.prepare_allocation(4).unwrap();
        let second = seq.prepare_allocation(4).unwrap();
        assert_eq!(first, second);

        seq.commit_allocation(4);
        let next = seq.prepare_allocation(8).unwrap();
        assert_use_signal(&next, &seq.unique_blocks()[1..2], &seq.block_hashes()[1..2]);
    }

    #[test]
    fn test_block_hash_cache_stays_in_sync_after_promote_and_pop() {
        let initial_tokens: Vec<u32> = (0..15).collect();
        let (mut seq, _) = ActiveSequence::new_with_signal(initial_tokens, 4, Some(16), true);

        assert_cached_hashes_match_promoted_blocks(&seq);

        seq.push(15);
        assert_cached_hashes_match_promoted_blocks(&seq);

        let promote_signals = seq.push(16).unwrap();
        assert_eq!(promote_signals.len(), 2);
        assert_cached_hashes_match_promoted_blocks(&seq);

        // `pop()` is only valid for undoing a freshly generated token from the
        // current partial block; this is the replay/preemption path we rely on.
        seq.pop();
        assert_cached_hashes_match_promoted_blocks(&seq);
656
657
    }
}