vyre_primitives/graph/adaptive_traverse/
plan_cache_key.rs

1//! Resident adaptive traversal program identity: the shape-only cache key
2//! every dispatch layer keys compiled programs on, plus the in-session content
3//! hashes for resident graph uploads.
4
5use std::hash::{Hash, Hasher};
6
7/// Primitive-owned resident adaptive traversal program identity.
8///
9/// Self-substrate and future CUDA/WGSL/SPIR-V dispatch layers use this as the
10/// stable cache-key taxonomy instead of forking per-wrapper enums.
11#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
12pub enum AdaptiveTraversalProgramKind {
13    /// Count set bits in the input frontier.
14    Popcount,
15    /// Clear the output frontier before an OR-writing traversal kernel.
16    ClearFrontierOut,
17    /// Initialize the active queue length before sparse queue compaction.
18    QueueLenInit,
19    /// Device-selected CSR/dense reverse-bitmatrix traversal.
20    SparseDense,
21    /// Compact active source ids from a frontier bitset into a queue.
22    FrontierToQueue,
23    /// Compute per-word active-node prefix counts for packed-frontier queues.
24    FrontierWordCounts,
25    /// Convert packed-frontier block totals into exclusive block offsets.
26    FrontierWordBlockOffsets,
27    /// Scatter packed frontier words into a deterministic active-source queue.
28    FrontierWordPrefixQueue,
29    /// Scatter packed frontier words using precomputed block offsets.
30    FrontierWordBlockOffsetsQueue,
31    /// Consume a compacted active-source queue through CSR rows.
32    QueueForward,
33    /// Consume a compacted active-source queue with lane teams for skewed rows.
34    QueueForwardStrided,
35    /// Expand low-degree queued rows and compact only high-degree rows.
36    QueueSplitLow,
37    /// Dense graph traversal through a reusable Four-Russians byte-tile LUT.
38    FourRussiansDense,
39}
40
41/// Stable cache key for resident adaptive traversal Programs.
42///
43/// The key deliberately includes program layout identity, frontier width, queue
44/// capacity, traversal masks, threshold policy, and backend feature bits so a
45/// cached Program cannot be reused across incompatible CUDA/WGSL/SPIR-V shapes.
46/// Resident graph contents are represented by dispatch handles, not shader
47/// source, so same-shape resident graphs reuse compiled Programs.
48#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
49pub struct AdaptiveTraversalPlanCacheKey {
50    /// Shape-only hash of the resident Program layout.
51    pub layout_hash: u64,
52    /// Number of graph nodes.
53    pub node_count: u32,
54    /// Number of logical CSR edges.
55    pub edge_count: u32,
56    /// Number of u32 words in one frontier bitset.
57    pub words: u32,
58    /// Active-source queue capacity for sparse-queue Programs.
59    pub queue_capacity: u32,
60    /// Allowed edge-kind mask baked into traversal Programs.
61    pub allow_mask: u32,
62    /// Dense cutover threshold baked into sparse/dense Programs.
63    pub dense_threshold_pct: u32,
64    /// Backend feature fingerprint from the dispatcher.
65    pub device_features: u64,
66    /// Resident Program shape represented by this key.
67    pub kind: AdaptiveTraversalProgramKind,
68}
69
70impl AdaptiveTraversalPlanCacheKey {
71    /// Construct a cache key for a resident adaptive traversal Program.
72    #[must_use]
73    #[allow(clippy::too_many_arguments)]
74    pub const fn new(
75        layout_hash: u64,
76        node_count: u32,
77        edge_count: u32,
78        words: u32,
79        queue_capacity: u32,
80        allow_mask: u32,
81        dense_threshold_pct: u32,
82        device_features: u64,
83        kind: AdaptiveTraversalProgramKind,
84    ) -> Self {
85        Self {
86            layout_hash,
87            node_count,
88            edge_count,
89            words,
90            queue_capacity,
91            allow_mask,
92            dense_threshold_pct,
93            device_features,
94            kind,
95        }
96    }
97
98    /// Cache key for the frontier popcount Program.
99    #[must_use]
100    pub const fn popcount(
101        _layout_hash: u64,
102        node_count: u32,
103        edge_count: u32,
104        words: u32,
105        device_features: u64,
106    ) -> Self {
107        let layout_hash = adaptive_traversal_program_layout_hash(
108            node_count,
109            edge_count,
110            words,
111            0,
112            AdaptiveTraversalProgramKind::Popcount,
113        );
114        Self::new(
115            layout_hash,
116            node_count,
117            edge_count,
118            words,
119            0,
120            0,
121            0,
122            device_features,
123            AdaptiveTraversalProgramKind::Popcount,
124        )
125    }
126
127    /// Cache key for clearing the output frontier.
128    #[must_use]
129    pub const fn clear_frontier_out(
130        _layout_hash: u64,
131        node_count: u32,
132        edge_count: u32,
133        words: u32,
134        device_features: u64,
135    ) -> Self {
136        let layout_hash = adaptive_traversal_program_layout_hash(
137            node_count,
138            edge_count,
139            words,
140            0,
141            AdaptiveTraversalProgramKind::ClearFrontierOut,
142        );
143        Self::new(
144            layout_hash,
145            node_count,
146            edge_count,
147            words,
148            0,
149            0,
150            0,
151            device_features,
152            AdaptiveTraversalProgramKind::ClearFrontierOut,
153        )
154    }
155
156    /// Cache key for device-selected sparse/dense traversal.
157    #[must_use]
158    pub const fn sparse_dense(
159        _layout_hash: u64,
160        node_count: u32,
161        edge_count: u32,
162        words: u32,
163        allow_mask: u32,
164        dense_threshold_pct: u32,
165        device_features: u64,
166    ) -> Self {
167        let layout_hash = adaptive_traversal_program_layout_hash(
168            node_count,
169            edge_count,
170            words,
171            0,
172            AdaptiveTraversalProgramKind::SparseDense,
173        );
174        Self::new(
175            layout_hash,
176            node_count,
177            edge_count,
178            words,
179            0,
180            allow_mask,
181            dense_threshold_pct,
182            device_features,
183            AdaptiveTraversalProgramKind::SparseDense,
184        )
185    }
186
187    /// Cache key for the active-queue length initialization Program.
188    #[must_use]
189    pub const fn queue_len_init(
190        _layout_hash: u64,
191        node_count: u32,
192        edge_count: u32,
193        words: u32,
194        queue_capacity: u32,
195        device_features: u64,
196    ) -> Self {
197        let layout_hash = adaptive_traversal_program_layout_hash(
198            node_count,
199            edge_count,
200            words,
201            queue_capacity,
202            AdaptiveTraversalProgramKind::QueueLenInit,
203        );
204        Self::new(
205            layout_hash,
206            node_count,
207            edge_count,
208            words,
209            queue_capacity,
210            0,
211            0,
212            device_features,
213            AdaptiveTraversalProgramKind::QueueLenInit,
214        )
215    }
216
217    /// Cache key for frontier-to-active-queue compaction.
218    #[must_use]
219    pub const fn frontier_to_queue(
220        _layout_hash: u64,
221        node_count: u32,
222        edge_count: u32,
223        words: u32,
224        queue_capacity: u32,
225        device_features: u64,
226    ) -> Self {
227        let layout_hash = adaptive_traversal_program_layout_hash(
228            node_count,
229            edge_count,
230            words,
231            queue_capacity,
232            AdaptiveTraversalProgramKind::FrontierToQueue,
233        );
234        Self::new(
235            layout_hash,
236            node_count,
237            edge_count,
238            words,
239            queue_capacity,
240            0,
241            0,
242            device_features,
243            AdaptiveTraversalProgramKind::FrontierToQueue,
244        )
245    }
246
247    /// Cache key for packed-frontier word-count scan.
248    #[must_use]
249    pub const fn frontier_word_counts(
250        _layout_hash: u64,
251        node_count: u32,
252        edge_count: u32,
253        words: u32,
254        device_features: u64,
255    ) -> Self {
256        let layout_hash = adaptive_traversal_program_layout_hash(
257            node_count,
258            edge_count,
259            words,
260            0,
261            AdaptiveTraversalProgramKind::FrontierWordCounts,
262        );
263        Self::new(
264            layout_hash,
265            node_count,
266            edge_count,
267            words,
268            0,
269            0,
270            0,
271            device_features,
272            AdaptiveTraversalProgramKind::FrontierWordCounts,
273        )
274    }
275
276    /// Cache key for packed-frontier block-offset scan.
277    #[must_use]
278    pub const fn frontier_word_block_offsets(
279        _layout_hash: u64,
280        node_count: u32,
281        edge_count: u32,
282        words: u32,
283        device_features: u64,
284    ) -> Self {
285        let layout_hash = adaptive_traversal_program_layout_hash(
286            node_count,
287            edge_count,
288            words,
289            0,
290            AdaptiveTraversalProgramKind::FrontierWordBlockOffsets,
291        );
292        Self::new(
293            layout_hash,
294            node_count,
295            edge_count,
296            words,
297            0,
298            0,
299            0,
300            device_features,
301            AdaptiveTraversalProgramKind::FrontierWordBlockOffsets,
302        )
303    }
304
305    /// Cache key for deterministic packed-frontier queue scatter.
306    #[must_use]
307    pub const fn frontier_word_prefix_queue(
308        _layout_hash: u64,
309        node_count: u32,
310        edge_count: u32,
311        words: u32,
312        queue_capacity: u32,
313        device_features: u64,
314    ) -> Self {
315        let layout_hash = adaptive_traversal_program_layout_hash(
316            node_count,
317            edge_count,
318            words,
319            queue_capacity,
320            AdaptiveTraversalProgramKind::FrontierWordPrefixQueue,
321        );
322        Self::new(
323            layout_hash,
324            node_count,
325            edge_count,
326            words,
327            queue_capacity,
328            0,
329            0,
330            device_features,
331            AdaptiveTraversalProgramKind::FrontierWordPrefixQueue,
332        )
333    }
334
335    /// Cache key for deterministic packed-frontier queue scatter with block offsets.
336    #[must_use]
337    pub const fn frontier_word_block_offsets_queue(
338        _layout_hash: u64,
339        node_count: u32,
340        edge_count: u32,
341        words: u32,
342        queue_capacity: u32,
343        device_features: u64,
344    ) -> Self {
345        let layout_hash = adaptive_traversal_program_layout_hash(
346            node_count,
347            edge_count,
348            words,
349            queue_capacity,
350            AdaptiveTraversalProgramKind::FrontierWordBlockOffsetsQueue,
351        );
352        Self::new(
353            layout_hash,
354            node_count,
355            edge_count,
356            words,
357            queue_capacity,
358            0,
359            0,
360            device_features,
361            AdaptiveTraversalProgramKind::FrontierWordBlockOffsetsQueue,
362        )
363    }
364
365    /// Cache key for queue-driven CSR traversal.
366    #[must_use]
367    pub const fn queue_forward(
368        _layout_hash: u64,
369        node_count: u32,
370        edge_count: u32,
371        words: u32,
372        queue_capacity: u32,
373        allow_mask: u32,
374        device_features: u64,
375    ) -> Self {
376        let layout_hash = adaptive_traversal_program_layout_hash(
377            node_count,
378            edge_count,
379            words,
380            queue_capacity,
381            AdaptiveTraversalProgramKind::QueueForward,
382        );
383        Self::new(
384            layout_hash,
385            node_count,
386            edge_count,
387            words,
388            queue_capacity,
389            allow_mask,
390            0,
391            device_features,
392            AdaptiveTraversalProgramKind::QueueForward,
393        )
394    }
395
396    /// Cache key for row-strided queue-driven CSR traversal.
397    #[must_use]
398    pub const fn queue_forward_strided(
399        _layout_hash: u64,
400        node_count: u32,
401        edge_count: u32,
402        words: u32,
403        queue_capacity: u32,
404        allow_mask: u32,
405        device_features: u64,
406    ) -> Self {
407        let layout_hash = adaptive_traversal_program_layout_hash(
408            node_count,
409            edge_count,
410            words,
411            queue_capacity,
412            AdaptiveTraversalProgramKind::QueueForwardStrided,
413        );
414        Self::new(
415            layout_hash,
416            node_count,
417            edge_count,
418            words,
419            queue_capacity,
420            allow_mask,
421            0,
422            device_features,
423            AdaptiveTraversalProgramKind::QueueForwardStrided,
424        )
425    }
426
427    /// Cache key for the low-row half of mixed queue-driven CSR traversal.
428    #[must_use]
429    #[allow(clippy::too_many_arguments)]
430    pub const fn queue_split_low(
431        _layout_hash: u64,
432        node_count: u32,
433        edge_count: u32,
434        words: u32,
435        queue_capacity: u32,
436        high_queue_capacity: u32,
437        high_degree_threshold: u32,
438        allow_mask: u32,
439        device_features: u64,
440    ) -> Self {
441        let layout_hash = adaptive_traversal_split_program_layout_hash(
442            node_count,
443            edge_count,
444            words,
445            queue_capacity,
446            high_queue_capacity,
447            high_degree_threshold,
448            AdaptiveTraversalProgramKind::QueueSplitLow,
449        );
450        Self::new(
451            layout_hash,
452            node_count,
453            edge_count,
454            words,
455            queue_capacity,
456            allow_mask,
457            0,
458            device_features,
459            AdaptiveTraversalProgramKind::QueueSplitLow,
460        )
461    }
462
463    /// Cache key for dense Four-Russians traversal through a resident LUT.
464    #[must_use]
465    pub const fn four_russians_dense(
466        _layout_hash: u64,
467        node_count: u32,
468        words: u32,
469        device_features: u64,
470    ) -> Self {
471        let layout_hash = adaptive_traversal_program_layout_hash(
472            node_count,
473            0,
474            words,
475            0,
476            AdaptiveTraversalProgramKind::FourRussiansDense,
477        );
478        Self::new(
479            layout_hash,
480            node_count,
481            0,
482            words,
483            0,
484            0,
485            0,
486            device_features,
487            AdaptiveTraversalProgramKind::FourRussiansDense,
488        )
489    }
490}
491
492const fn adaptive_traversal_program_kind_tag(kind: AdaptiveTraversalProgramKind) -> u64 {
493    match kind {
494        AdaptiveTraversalProgramKind::Popcount => 1,
495        AdaptiveTraversalProgramKind::ClearFrontierOut => 2,
496        AdaptiveTraversalProgramKind::SparseDense => 3,
497        AdaptiveTraversalProgramKind::QueueLenInit => 4,
498        AdaptiveTraversalProgramKind::FrontierToQueue => 5,
499        AdaptiveTraversalProgramKind::QueueForward => 6,
500        AdaptiveTraversalProgramKind::FourRussiansDense => 7,
501        AdaptiveTraversalProgramKind::FrontierWordCounts => 8,
502        AdaptiveTraversalProgramKind::FrontierWordPrefixQueue => 9,
503        AdaptiveTraversalProgramKind::FrontierWordBlockOffsets => 10,
504        AdaptiveTraversalProgramKind::FrontierWordBlockOffsetsQueue => 11,
505        AdaptiveTraversalProgramKind::QueueForwardStrided => 12,
506        AdaptiveTraversalProgramKind::QueueSplitLow => 13,
507    }
508}
509
510const fn adaptive_traversal_hash_mix(hash: u64, value: u64) -> u64 {
511    (hash ^ value).wrapping_mul(0x0000_0100_0000_01B3)
512}
513
514/// Shape-only hash for resident adaptive traversal program layouts.
515///
516/// This excludes resident graph contents and dense LUT source rows; those are
517/// already bound through resident handles. Including content here fragments the
518/// compiled-program cache without changing generated code.
519#[must_use]
520pub const fn adaptive_traversal_program_layout_hash(
521    node_count: u32,
522    edge_count: u32,
523    words: u32,
524    queue_capacity: u32,
525    kind: AdaptiveTraversalProgramKind,
526) -> u64 {
527    let hash = adaptive_traversal_hash_mix(0xcbf2_9ce4_8422_2325, 0x4154_5241_5645_5253);
528    let hash = adaptive_traversal_hash_mix(hash, node_count as u64);
529    let hash = adaptive_traversal_hash_mix(hash, edge_count as u64);
530    let hash = adaptive_traversal_hash_mix(hash, words as u64);
531    let hash = adaptive_traversal_hash_mix(hash, queue_capacity as u64);
532    adaptive_traversal_hash_mix(hash, adaptive_traversal_program_kind_tag(kind))
533}
534
535/// Shape-only hash for mixed queue traversal programs whose low-row half also
536/// depends on high-row queue capacity and the high-degree threshold.
537#[must_use]
538pub const fn adaptive_traversal_split_program_layout_hash(
539    node_count: u32,
540    edge_count: u32,
541    words: u32,
542    queue_capacity: u32,
543    high_queue_capacity: u32,
544    high_degree_threshold: u32,
545    kind: AdaptiveTraversalProgramKind,
546) -> u64 {
547    let hash =
548        adaptive_traversal_program_layout_hash(node_count, edge_count, words, queue_capacity, kind);
549    let hash = adaptive_traversal_hash_mix(hash, high_queue_capacity as u64);
550    adaptive_traversal_hash_mix(hash, high_degree_threshold as u64)
551}
552
553/// In-session content hash for resident adaptive CSR+dense graph uploads.
554///
555/// This hashes graph contents, unlike [`adaptive_traversal_program_layout_hash`],
556/// which intentionally hashes only generated-program shape. Resident upload
557/// wrappers use this to identify uploaded graph layouts without forking the
558/// primitive's graph identity contract.
559#[must_use]
560pub fn adaptive_traversal_graph_content_hash(
561    node_count: u32,
562    edge_offsets: &[u32],
563    edge_targets: &[u32],
564    edge_kind_mask: &[u32],
565    adj_rows_dense: &[u32],
566) -> u64 {
567    let mut hasher = std::collections::hash_map::DefaultHasher::new();
568    node_count.hash(&mut hasher);
569    edge_offsets.hash(&mut hasher);
570    edge_targets.hash(&mut hasher);
571    edge_kind_mask.hash(&mut hasher);
572    adj_rows_dense.hash(&mut hasher);
573    hasher.finish()
574}
575
576/// In-session content hash for resident adaptive sparse-queue CSR uploads.
577#[must_use]
578pub fn adaptive_sparse_queue_graph_content_hash(
579    node_count: u32,
580    edge_offsets: &[u32],
581    edge_targets: &[u32],
582    edge_kind_mask: &[u32],
583) -> u64 {
584    let mut hasher = std::collections::hash_map::DefaultHasher::new();
585    node_count.hash(&mut hasher);
586    edge_offsets.hash(&mut hasher);
587    edge_targets.hash(&mut hasher);
588    edge_kind_mask.hash(&mut hasher);
589    hasher.finish()
590}
591
592/// In-session content hash for resident adaptive Four-Russians dense LUT uploads.
593#[must_use]
594pub fn adaptive_four_russians_graph_content_hash(node_count: u32, adj_rows_dense: &[u32]) -> u64 {
595    let mut hasher = std::collections::hash_map::DefaultHasher::new();
596    node_count.hash(&mut hasher);
597    adj_rows_dense.hash(&mut hasher);
598    hasher.finish()
599}
600
601#[cfg(test)]
602mod resident_content_hash_tests {
603    use super::*;
604
605    #[test]
606    fn graph_content_hash_tracks_csr_masks_and_dense_rows() {
607        let offsets = [0, 1, 1];
608        let targets = [1];
609        let masks = [7];
610        let dense = [0b10, 0];
611        let baseline = adaptive_traversal_graph_content_hash(2, &offsets, &targets, &masks, &dense);
612        let changed_mask =
613            adaptive_traversal_graph_content_hash(2, &offsets, &targets, &[3], &dense);
614        let changed_dense =
615            adaptive_traversal_graph_content_hash(2, &offsets, &targets, &masks, &[0, 1]);
616
617        assert_ne!(baseline, changed_mask);
618        assert_ne!(baseline, changed_dense);
619    }
620
621    #[test]
622    fn sparse_queue_content_hash_tracks_csr_without_dense_rows() {
623        let offsets = [0, 1, 1];
624        let targets = [1];
625        let masks = [7];
626        let baseline = adaptive_sparse_queue_graph_content_hash(2, &offsets, &targets, &masks);
627        let changed_mask = adaptive_sparse_queue_graph_content_hash(2, &offsets, &targets, &[3]);
628        let changed_target = adaptive_sparse_queue_graph_content_hash(2, &offsets, &[0], &masks);
629
630        assert_ne!(baseline, changed_mask);
631        assert_ne!(baseline, changed_target);
632    }
633
634    #[test]
635    fn four_russians_content_hash_tracks_lut_source_rows() {
636        let baseline = adaptive_four_russians_graph_content_hash(8, &[1, 0, 0, 0, 0, 0, 0, 0]);
637        let changed = adaptive_four_russians_graph_content_hash(8, &[2, 0, 0, 0, 0, 0, 0, 0]);
638
639        assert_ne!(baseline, changed);
640    }
641}
642
643#[cfg(test)]
644mod tests {
645    use super::*;
646
647    #[test]
648    fn adaptive_plan_cache_keys_pin_resident_program_identity() {
649        let sparse_dense =
650            AdaptiveTraversalPlanCacheKey::sparse_dense(7, 64, 9, 2, 0x55, 25, 0xA11CE);
651        assert_eq!(sparse_dense.kind, AdaptiveTraversalProgramKind::SparseDense);
652        assert_eq!(
653            sparse_dense.layout_hash,
654            adaptive_traversal_program_layout_hash(
655                64,
656                9,
657                2,
658                0,
659                AdaptiveTraversalProgramKind::SparseDense,
660            )
661        );
662        assert_eq!(sparse_dense.queue_capacity, 0);
663        assert_eq!(sparse_dense.allow_mask, 0x55);
664        assert_eq!(sparse_dense.dense_threshold_pct, 25);
665        assert_eq!(
666            sparse_dense,
667            AdaptiveTraversalPlanCacheKey::sparse_dense(99, 64, 9, 2, 0x55, 25, 0xA11CE),
668            "resident graph contents must not fragment adaptive traversal Program caches"
669        );
670
671        assert_ne!(
672            sparse_dense,
673            AdaptiveTraversalPlanCacheKey::sparse_dense(7, 64, 9, 2, 0xAA, 25, 0xA11CE),
674            "edge-mask policy must be part of sparse/dense resident Program identity"
675        );
676        assert_ne!(
677            sparse_dense,
678            AdaptiveTraversalPlanCacheKey::sparse_dense(7, 64, 9, 2, 0x55, 50, 0xA11CE),
679            "dense cutover policy must be part of sparse/dense resident Program identity"
680        );
681        assert_ne!(
682            sparse_dense,
683            AdaptiveTraversalPlanCacheKey::sparse_dense(7, 64, 9, 2, 0x55, 25, 0xC0DA),
684            "backend feature bits must be part of resident Program identity"
685        );
686
687        let queue_forward =
688            AdaptiveTraversalPlanCacheKey::queue_forward(7, 64, 9, 2, 64, 0x55, 0xA11CE);
689        assert_eq!(
690            queue_forward.kind,
691            AdaptiveTraversalProgramKind::QueueForward
692        );
693        assert_eq!(queue_forward.queue_capacity, 64);
694        assert_eq!(queue_forward.allow_mask, 0x55);
695        let queue_forward_strided =
696            AdaptiveTraversalPlanCacheKey::queue_forward_strided(7, 64, 9, 2, 64, 0x55, 0xA11CE);
697        assert_eq!(
698            queue_forward_strided.kind,
699            AdaptiveTraversalProgramKind::QueueForwardStrided
700        );
701        assert_ne!(
702            queue_forward, queue_forward_strided,
703            "serial and row-strided queue consumers must not alias in resident Program caches"
704        );
705        let queue_split_low =
706            AdaptiveTraversalPlanCacheKey::queue_split_low(7, 64, 9, 2, 64, 4, 1024, 0x55, 0xA11CE);
707        assert_eq!(
708            queue_split_low.kind,
709            AdaptiveTraversalProgramKind::QueueSplitLow
710        );
711        assert_eq!(queue_split_low.queue_capacity, 64);
712        assert_eq!(queue_split_low.dense_threshold_pct, 0);
713        assert_ne!(
714            queue_split_low,
715            AdaptiveTraversalPlanCacheKey::queue_split_low(7, 64, 9, 2, 64, 8, 1024, 0x55, 0xA11CE,),
716            "mixed split queue programs must distinguish high-row queue capacity"
717        );
718        assert_ne!(
719            queue_split_low,
720            AdaptiveTraversalPlanCacheKey::queue_split_low(7, 64, 9, 2, 64, 4, 2048, 0x55, 0xA11CE,),
721            "mixed split queue programs must distinguish high-degree threshold"
722        );
723        assert_ne!(
724            queue_forward,
725            AdaptiveTraversalPlanCacheKey::frontier_to_queue(7, 64, 9, 2, 64, 0xA11CE)
726        );
727        let word_counts =
728            AdaptiveTraversalPlanCacheKey::frontier_word_counts(7, 8_192, 9, 256, 0xA11CE);
729        assert_eq!(
730            word_counts.kind,
731            AdaptiveTraversalProgramKind::FrontierWordCounts
732        );
733        assert_eq!(word_counts.queue_capacity, 0);
734        let block_offsets = AdaptiveTraversalPlanCacheKey::frontier_word_block_offsets(
735            7, 32_897, 9, 1_029, 0xA11CE,
736        );
737        assert_eq!(
738            block_offsets.kind,
739            AdaptiveTraversalProgramKind::FrontierWordBlockOffsets
740        );
741        assert_eq!(block_offsets.queue_capacity, 0);
742        let word_prefix = AdaptiveTraversalPlanCacheKey::frontier_word_prefix_queue(
743            7, 8_192, 9, 256, 8_192, 0xA11CE,
744        );
745        assert_eq!(
746            word_prefix.kind,
747            AdaptiveTraversalProgramKind::FrontierWordPrefixQueue
748        );
749        assert_eq!(word_prefix.queue_capacity, 8_192);
750        assert_ne!(
751            word_prefix,
752            AdaptiveTraversalPlanCacheKey::frontier_to_queue(7, 8_192, 9, 256, 8_192, 0xA11CE),
753            "deterministic word-prefix queue programs must not alias atomic queue builders"
754        );
755        let block_offset_queue = AdaptiveTraversalPlanCacheKey::frontier_word_block_offsets_queue(
756            7, 32_897, 9, 1_029, 32_897, 0xA11CE,
757        );
758        assert_eq!(
759            block_offset_queue.kind,
760            AdaptiveTraversalProgramKind::FrontierWordBlockOffsetsQueue
761        );
762        assert_eq!(block_offset_queue.queue_capacity, 32_897);
763        assert_ne!(
764            block_offset_queue, word_prefix,
765            "block-offset queue programs must not alias the previous-block-loop scatter"
766        );
767
768        let dense = AdaptiveTraversalPlanCacheKey::four_russians_dense(99, 128, 4, 0xA11CE);
769        assert_eq!(dense.kind, AdaptiveTraversalProgramKind::FourRussiansDense);
770        assert_eq!(dense.edge_count, 0);
771        assert_eq!(dense.queue_capacity, 0);
772        assert_eq!(
773            dense,
774            AdaptiveTraversalPlanCacheKey::four_russians_dense(7, 128, 4, 0xA11CE),
775            "resident Four-Russians LUT contents must not fragment dense Program caches"
776        );
777    }
778}
vyre_primitives/graph/adaptive_traverse/plan_cache_key.rs

vyre_primitives/graph/adaptive_traverse/
plan_cache_key.rs
