sequence.rs 22.9 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
167
168
169
170
171
172
        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.
    pub fn positional_lineage_hashes(&self) -> Vec<PositionalLineageHash> {
        self.tokens
            .blocks()
            .iter()
            .map(|block| block.positional_lineage_hash())
            .collect()
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
    }

    /// 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).
188
    pub fn take_creation_signal(&mut self) -> Option<MoveBlock> {
189
        self.allocate_blocks_for_chunk(self.len())
190
191
    }

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

215
        if self.len() % self.block_size != 1 {
216
217
218
219
220
221
222
223
224
            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() {
225
            let last_complete = self.tokens.last_complete_block().unwrap();
Yan Ru Pei's avatar
Yan Ru Pei committed
226
            let last_seq_hash = if self.enable_prefix_caching {
227
                last_complete.sequence_hash()
228
229
230
            } else {
                random::<u64>()
            };
231
            let last_block_hash = last_complete.block_hash();
232
233
234
235
236
237
238
239
240
            // 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)
            };
241
242
243
244
245
            let promote_token_ids = if self.emit_token_ids {
                Some(last_complete.tokens().to_vec())
            } else {
                None
            };
246
            self.block_hashes.push(last_block_hash);
247
            self.plhs.push(last_plh);
248
            self.unique_blocks.pop();
Yan Ru Pei's avatar
Yan Ru Pei committed
249
250
251
252
253
254
255

            // 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"),
            });

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

        let new_partial_block = UniqueBlock::default();
        self.unique_blocks.push(new_partial_block.clone());
270
271
272
273
274
275
276
        signals.push(MoveBlock::Use(
            vec![new_partial_block],
            vec![],
            vec![],
            None,
            None,
        ));
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
        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
315
        signals.extend(self.free_signal_for_tokens(self.len()));
316
317
318
        signals
    }

319
320
321
322
323
    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]
324
325
326
327
            .iter()
            .rev()
            .map(|block| match block {
                UniqueBlock::PartialBlock(uuid) => {
328
                    MoveBlock::Deref(vec![UniqueBlock::PartialBlock(*uuid)])
329
330
331
332
333
334
335
336
                }
                UniqueBlock::FullBlock(hash) => {
                    MoveBlock::Deref(vec![UniqueBlock::FullBlock(*hash)])
                }
            })
            .collect()
    }

337
338
339
340
341
    /// Free the currently active allocation footprint.
    pub fn free_signal(&self) -> Vec<MoveBlock> {
        self.free_signal_for_tokens(self.num_allocated_tokens)
    }

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

351
352
353
354
355
356
357
    /// 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.
358
359
360
361
362
    pub fn pop(&mut self) {
        self.tokens.pop();
        self.generated_tokens = self.generated_tokens.saturating_sub(1);

        // Reverts to the last full block
363
        if self.tokens.total_tokens().is_multiple_of(self.block_size) {
364
365
366
367
368
369
370
371
372
            self.unique_blocks.pop();
        }
    }
}

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

373
374
375
376
377
378
379
    fn block_hashes_from_tokens(seq: &ActiveSequence) -> Vec<u64> {
        seq.tokens
            .blocks()
            .iter()
            .map(|block| block.block_hash())
            .collect()
    }
380

381
382
383
384
385
386
387
388
389
390
    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"
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
    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"),
        }
    }
418

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

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

    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"),
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
    }

    #[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"
        );
    }
485

486
487
488
489
490
491
    #[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);
492
493

        let extended_tokens: Vec<u32> = (0..16).collect();
494
        let (mut seq2, _) = ActiveSequence::new_with_signal(extended_tokens, 100, Some(16), true);
495
496
497
498
        seq2.push(16);
        seq2.pop();
        seq2.push(16);

499
500
501
        assert_eq!(seq1.unique_blocks()[0], seq2.unique_blocks()[0]);
        assert_ne!(seq1.unique_blocks()[1], seq2.unique_blocks()[1]);
    }
502

503
504
505
506
507
508
    #[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);
509

510
511
512
513
        seq.push(17);
        seq.pop();
        seq.pop();
        seq.push(16);
514

515
516
517
518
519
520
        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);
521
        for token in 17..33 {
522
523
            seq.push(token);
            seq_equiv.push(token);
524
525
526
        }

        assert_eq!(
527
528
529
            &seq.unique_blocks()[0..2],
            &seq_equiv.unique_blocks()[0..2],
            "first two full blocks should remain identical"
530
531
        );

532
        for token in 33..48 {
533
            seq.push(token);
534
535
        }

536
537
538
        let signal = seq
            .push(48)
            .expect("Expected promote when opening next partial");
539

540
541
542
543
544
545
        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]);
    }
546

547
548
549
550
551
552
553
    #[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());
554

555
        let free_signals = seq.reset_with_signal();
556

557
        assert!(!free_signals.is_empty());
558
559
        assert_eq!(seq.num_allocated_tokens(), 0);
        assert_eq!(seq.generated_tokens(), 2);
560
561
562
563
564
565
    }

    #[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();
566
        let (mut seq, signal) = ActiveSequence::new_with_signal(initial_tokens, 5, Some(16), true);
567
568

        // Initial signal - should have received a Use signal for the partial block
569
        assert_single_partial_use(signal.as_ref().expect("Expected initial Use signal"));
570
571
572
573
574
575
576
577
578
579

        // 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);

580
        // First signal should be Promote
581
        assert_promote_parent(&signals_second[0], None);
582
583

        // Second signal should be Use for new partial block
584
        assert_single_partial_use(&signals_second[1]);
585
586
587
588
589

        // 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);

590
        // Generate last token - we reach max_output_tokens, should trigger Deref signals
591
592
593
        let signals_last = seq.generate();
        assert_eq!(signals_last.len(), 2);

594
595
        // First signal should be Deref for the partial block
        assert_deref_partial(&signals_last[0]);
596
597

        // Second signal should be Deref for the full block
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
        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);
660
661
    }
}