vyre_primitives/graph/adaptive_traverse/
frontier_plan.rs

1//! Validated adaptive traversal layouts and the resident launch plans derived
2//! from them: frontier shape, in-domain popcount, queue sizing, and grids.
3
4use super::mode_selection::{select_adaptive_traversal_mode, AdaptiveTraversalMode};
5use crate::bitset::{bitset_words, frontier::frontier_tail_mask};
6
7/// Validated adaptive traversal graph layout metadata.
8#[derive(Clone, Copy, Debug, Eq, PartialEq)]
9pub struct AdaptiveTraversalLayout {
10    /// Number of logical CSR edges.
11    pub edge_count: u32,
12    /// Largest CSR row degree in the sparse graph.
13    pub max_row_degree: u32,
14    /// Number of u32 words required by physical edge buffers after padding.
15    pub edge_storage_words: usize,
16    /// Number of u32 words in one frontier bitset.
17    pub words: usize,
18    /// Number of u32 words in the dense reverse-adjacency matrix.
19    pub dense_words: usize,
20}
21
22/// Validated frontier bitset shape for adaptive traversal.
23#[derive(Clone, Copy, Debug, Eq, PartialEq)]
24pub struct AdaptiveFrontierLayout {
25    /// Number of u32 words in one frontier bitset.
26    pub words: usize,
27    /// Number of u32 words in one frontier bitset, narrowed for primitive metadata.
28    pub words_u32: u32,
29}
30
31/// Primitive-owned work classification for a validated adaptive frontier.
32#[derive(Clone, Copy, Debug, Eq, PartialEq)]
33pub struct AdaptiveFrontierWorkPlan {
34    /// Validated frontier layout.
35    pub layout: AdaptiveFrontierLayout,
36    /// Whether any in-domain frontier bit is active.
37    pub has_active_bits: bool,
38}
39
40/// In-domain frontier statistics for adaptive traversal planning.
41#[derive(Clone, Copy, Debug, Eq, PartialEq)]
42pub struct AdaptiveFrontierStats {
43    /// Validated frontier layout.
44    pub layout: AdaptiveFrontierLayout,
45    /// Set bits at node ids `< node_count`, excluding padding in the tail word.
46    pub popcount: u32,
47    /// Packed words with at least one in-domain active bit.
48    pub nonzero_words: usize,
49}
50
51/// Workgroup lane count used by resident linear adaptive traversal kernels.
52pub const ADAPTIVE_TRAVERSAL_LINEAR_WORKGROUP_LANES: u32 = 256;
53/// Workgroup shape for node- and word-linear adaptive traversal kernels.
54pub const ADAPTIVE_TRAVERSAL_LINEAR_WORKGROUP_SIZE: [u32; 3] =
55    [ADAPTIVE_TRAVERSAL_LINEAR_WORKGROUP_LANES, 1, 1];
56/// Byte length of one resident u32 popcount scalar.
57pub const ADAPTIVE_TRAVERSAL_POPCOUNT_BYTES: usize = std::mem::size_of::<u32>();
58
59/// Primitive-owned resident frontier launch and scratch plan.
60#[derive(Clone, Copy, Debug, Eq, PartialEq)]
61pub struct AdaptiveResidentFrontierPlan {
62    /// Validated frontier work classification.
63    pub work: AdaptiveFrontierWorkPlan,
64    /// Number of bytes in one frontier bitset.
65    pub frontier_bytes: usize,
66    /// Number of bytes in one resident popcount scalar.
67    pub popcount_bytes: usize,
68    /// Grid for kernels that process frontier words.
69    pub frontier_word_grid: [u32; 3],
70    /// Grid for kernels that process graph nodes.
71    pub node_grid: [u32; 3],
72}
73
74/// Primitive-owned resident sparse-queue launch and scratch plan.
75#[derive(Clone, Copy, Debug, Eq, PartialEq)]
76pub struct AdaptiveResidentSparseQueuePlan {
77    /// Shared frontier launch and scratch plan.
78    pub frontier: AdaptiveResidentFrontierPlan,
79    /// Packed frontier words with at least one in-domain active bit.
80    pub frontier_nonzero_words: usize,
81    /// Active-source queue capacity in u32 node ids.
82    pub queue_capacity: u32,
83    /// Number of bytes in the resident active-source queue.
84    pub queue_bytes: usize,
85    /// Grid for kernels that process the active-source queue.
86    pub queue_grid: [u32; 3],
87}
88
89/// Primitive-owned auto-mode resident traversal plan.
90#[derive(Clone, Copy, Debug, Eq, PartialEq)]
91pub struct AdaptiveResidentAutoStepPlan {
92    /// Shared frontier launch and scratch plan.
93    pub frontier: AdaptiveResidentFrontierPlan,
94    /// Host-visible frontier popcount used only for mode selection.
95    pub frontier_popcount: u32,
96    /// Selected traversal mode.
97    pub mode: AdaptiveTraversalMode,
98}
99
100/// Validate CSR plus dense reverse-adjacency rows for adaptive traversal.
101///
102/// # Errors
103///
104/// Returns an actionable diagnostic when the layout is empty, malformed,
105/// exceeds u32 edge-count indexing, has non-monotonic offsets, contains
106/// out-of-range CSR targets, or has the wrong dense matrix length.
107pub fn validate_adaptive_traversal_layout(
108    node_count: u32,
109    edge_offsets: &[u32],
110    edge_targets: &[u32],
111    edge_kind_mask: &[u32],
112    adj_rows_dense: &[u32],
113) -> Result<AdaptiveTraversalLayout, String> {
114    if node_count == 0 {
115        return Err("Fix: adaptive traversal requires node_count > 0.".to_string());
116    }
117    let expected_offsets = (node_count as usize).checked_add(1).ok_or_else(|| {
118        format!(
119            "Fix: adaptive traversal node_count + 1 overflows usize for node_count={node_count}."
120        )
121    })?;
122    if edge_offsets.len() != expected_offsets {
123        return Err(format!(
124            "Fix: adaptive traversal expected {expected_offsets} CSR offsets for {node_count} nodes, got {}.",
125            edge_offsets.len()
126        ));
127    }
128    if edge_targets.len() != edge_kind_mask.len() {
129        return Err(format!(
130            "Fix: adaptive traversal target/mask length mismatch: {} targets, {} masks.",
131            edge_targets.len(),
132            edge_kind_mask.len()
133        ));
134    }
135    let edge_count = u32::try_from(edge_targets.len()).map_err(|_| {
136        format!(
137            "Fix: adaptive traversal edge count {} exceeds u32 index space.",
138            edge_targets.len()
139        )
140    })?;
141    let final_offset = edge_offsets[expected_offsets - 1] as usize;
142    if final_offset != edge_targets.len() {
143        return Err(format!(
144            "Fix: adaptive traversal final CSR offset {final_offset} must equal edge_count {}.",
145            edge_targets.len()
146        ));
147    }
148    let mut max_row_degree = 0u32;
149    for (row, pair) in edge_offsets.windows(2).enumerate() {
150        if pair[0] > pair[1] {
151            return Err(format!(
152                "Fix: adaptive traversal CSR offsets are non-monotonic at row {row}: {} > {}.",
153                pair[0], pair[1]
154            ));
155        }
156        max_row_degree = max_row_degree.max(pair[1] - pair[0]);
157    }
158    for (idx, &target) in edge_targets.iter().enumerate() {
159        if target >= node_count {
160            return Err(format!(
161                "Fix: adaptive traversal CSR target[{idx}]={target} is outside node_count {node_count}."
162            ));
163        }
164    }
165
166    let words = bitset_words(node_count) as usize;
167    let dense_words = (node_count as usize).checked_mul(words).ok_or_else(|| {
168        format!(
169            "Fix: adaptive traversal dense adjacency word count overflows usize for {node_count} nodes and {words} words."
170        )
171    })?;
172    if adj_rows_dense.len() != dense_words {
173        return Err(format!(
174            "Fix: adaptive traversal expected {dense_words} dense adjacency words, got {}.",
175            adj_rows_dense.len()
176        ));
177    }
178
179    Ok(AdaptiveTraversalLayout {
180        edge_count,
181        max_row_degree,
182        edge_storage_words: edge_targets.len().max(1),
183        words,
184        dense_words,
185    })
186}
187
188/// Validate a packed frontier bitset for adaptive traversal.
189///
190/// # Errors
191///
192/// Returns an actionable diagnostic when `node_count` is zero or the frontier
193/// slice length does not match `bitset_words(node_count)`.
194pub fn validate_adaptive_frontier(
195    node_count: u32,
196    frontier_in: &[u32],
197) -> Result<AdaptiveFrontierLayout, String> {
198    if node_count == 0 {
199        return Err("Fix: adaptive traversal frontier requires node_count > 0.".to_string());
200    }
201    let words_u32 = bitset_words(node_count);
202    let words = words_u32 as usize;
203    if frontier_in.len() != words {
204        return Err(format!(
205            "Fix: adaptive traversal frontier expected {words} word(s) for node_count={node_count}, got {}.",
206            frontier_in.len()
207        ));
208    }
209    Ok(AdaptiveFrontierLayout { words, words_u32 })
210}
211
212/// Validate and classify an adaptive traversal frontier.
213///
214/// The all-zero frontier is a primitive identity case: every adaptive
215/// traversal variant produces an all-zero output and does not need a resident
216/// popcount, queue compaction, dense traversal, or readback kernel.
217///
218/// # Errors
219///
220/// Returns the same frontier-shape diagnostics as [`validate_adaptive_frontier`].
221pub fn plan_adaptive_frontier_work(
222    node_count: u32,
223    frontier_in: &[u32],
224) -> Result<AdaptiveFrontierWorkPlan, String> {
225    let stats =
226        adaptive_frontier_stats(node_count, frontier_in, "adaptive traversal frontier work")?;
227    Ok(AdaptiveFrontierWorkPlan {
228        layout: stats.layout,
229        has_active_bits: stats.popcount != 0,
230    })
231}
232
233/// Checked physical-word popcount for an adaptive traversal frontier.
234///
235/// # Errors
236///
237/// Returns an actionable diagnostic if the frontier contains more set bits than
238/// can be represented by the primitive's u32 resident popcount scalar.
239pub fn adaptive_frontier_popcount(frontier_in: &[u32], context: &str) -> Result<u32, String> {
240    let mut popcount = 0u32;
241    for &word in frontier_in {
242        popcount = popcount.checked_add(word.count_ones()).ok_or_else(|| {
243            format!(
244                "Fix: {context} frontier popcount exceeds u32::MAX for {} frontier words.",
245                frontier_in.len()
246            )
247        })?;
248    }
249    Ok(popcount)
250}
251
252/// Checked in-domain popcount for an adaptive traversal frontier.
253///
254/// # Errors
255///
256/// Returns frontier-shape diagnostics or an actionable diagnostic if the
257/// in-domain frontier contains more set bits than fit in a u32 scalar.
258pub fn adaptive_frontier_popcount_in_domain(
259    node_count: u32,
260    frontier_in: &[u32],
261    context: &str,
262) -> Result<u32, String> {
263    adaptive_frontier_stats(node_count, frontier_in, context).map(|stats| stats.popcount)
264}
265
266/// Validate and count only frontier bits whose node ids are in domain.
267///
268/// # Errors
269///
270/// Returns frontier-shape diagnostics or an actionable diagnostic if the
271/// in-domain frontier contains more set bits than fit in a u32 scalar.
272pub fn adaptive_frontier_stats(
273    node_count: u32,
274    frontier_in: &[u32],
275    context: &str,
276) -> Result<AdaptiveFrontierStats, String> {
277    let layout = validate_adaptive_frontier(node_count, frontier_in)?;
278    let final_word_mask = frontier_tail_mask(node_count);
279    let mut popcount = 0u32;
280    let mut nonzero_words = 0usize;
281    for (index, &word) in frontier_in.iter().enumerate() {
282        let in_domain_word = if index + 1 == layout.words {
283            word & final_word_mask
284        } else {
285            word
286        };
287        if in_domain_word != 0 {
288            nonzero_words += 1;
289        }
290        popcount = popcount
291            .checked_add(in_domain_word.count_ones())
292            .ok_or_else(|| {
293                format!(
294                    "Fix: {context} frontier popcount exceeds u32::MAX for {} frontier words.",
295                    frontier_in.len()
296                )
297            })?;
298    }
299    Ok(AdaptiveFrontierStats {
300        layout,
301        popcount,
302        nonzero_words,
303    })
304}
305
306/// Validate and plan resident frontier scratch plus launch grids.
307///
308/// # Errors
309///
310/// Returns frontier-shape diagnostics or byte-size overflow diagnostics.
311pub fn plan_adaptive_resident_frontier_step(
312    node_count: u32,
313    frontier_in: &[u32],
314) -> Result<AdaptiveResidentFrontierPlan, String> {
315    let work = plan_adaptive_frontier_work(node_count, frontier_in)?;
316    adaptive_resident_frontier_plan_from_work(node_count, work)
317}
318
319/// Validate and plan a queue-driven resident traversal step.
320///
321/// # Errors
322///
323/// Returns frontier-shape diagnostics or queue/frontier byte-size overflow
324/// diagnostics. The active queue is sized from the host-visible frontier
325/// popcount and rounded to a power-of-two bucket so sparse frontiers do not pay
326/// full-graph queue allocation or launch width.
327pub fn plan_adaptive_resident_sparse_queue_step(
328    node_count: u32,
329    frontier_in: &[u32],
330) -> Result<AdaptiveResidentSparseQueuePlan, String> {
331    let stats = adaptive_frontier_stats(
332        node_count,
333        frontier_in,
334        "adaptive resident sparse queue step",
335    )?;
336    let work = AdaptiveFrontierWorkPlan {
337        layout: stats.layout,
338        has_active_bits: stats.popcount != 0,
339    };
340    let frontier = adaptive_resident_frontier_plan_from_work(node_count, work)?;
341    let queue_capacity = adaptive_sparse_queue_capacity(node_count, stats.popcount);
342    let queue_bytes = adaptive_u32_byte_len(
343        queue_capacity as usize,
344        "adaptive traversal resident active-source queue",
345    )?;
346    Ok(AdaptiveResidentSparseQueuePlan {
347        frontier,
348        frontier_nonzero_words: stats.nonzero_words,
349        queue_capacity,
350        queue_bytes,
351        queue_grid: adaptive_linear_grid(queue_capacity),
352    })
353}
354
355fn adaptive_sparse_queue_capacity(node_count: u32, frontier_popcount: u32) -> u32 {
356    let active = frontier_popcount.min(node_count).max(1);
357    active
358        .checked_next_power_of_two()
359        .unwrap_or(u32::MAX)
360        .min(node_count.max(1))
361}
362
363/// Validate, count, and select resident traversal mode in one primitive-owned plan.
364///
365/// # Errors
366///
367/// Returns frontier-shape diagnostics or byte-size overflow diagnostics.
368pub fn plan_adaptive_resident_auto_step(
369    node_count: u32,
370    edge_count: u32,
371    frontier_in: &[u32],
372    dense_threshold_pct: u32,
373) -> Result<AdaptiveResidentAutoStepPlan, String> {
374    let stats = adaptive_frontier_stats(node_count, frontier_in, "adaptive resident auto step")?;
375    let work = AdaptiveFrontierWorkPlan {
376        layout: stats.layout,
377        has_active_bits: stats.popcount != 0,
378    };
379    let frontier = adaptive_resident_frontier_plan_from_work(node_count, work)?;
380    let mode =
381        select_adaptive_traversal_mode(node_count, edge_count, stats.popcount, dense_threshold_pct);
382    Ok(AdaptiveResidentAutoStepPlan {
383        frontier,
384        frontier_popcount: stats.popcount,
385        mode,
386    })
387}
388
389fn adaptive_resident_frontier_plan_from_work(
390    node_count: u32,
391    work: AdaptiveFrontierWorkPlan,
392) -> Result<AdaptiveResidentFrontierPlan, String> {
393    let frontier_bytes =
394        adaptive_u32_byte_len(work.layout.words, "adaptive traversal resident frontier")?;
395    let frontier_word_grid = adaptive_linear_grid(work.layout.words_u32);
396    Ok(AdaptiveResidentFrontierPlan {
397        work,
398        frontier_bytes,
399        popcount_bytes: ADAPTIVE_TRAVERSAL_POPCOUNT_BYTES,
400        frontier_word_grid,
401        node_grid: adaptive_node_dispatch_grid(node_count),
402    })
403}
404
405fn adaptive_u32_byte_len(words: usize, context: &str) -> Result<usize, String> {
406    words.checked_mul(std::mem::size_of::<u32>()).ok_or_else(|| {
407        format!(
408            "Fix: {context} byte length overflows usize for {words} u32 word(s). Shard the graph before resident dispatch."
409        )
410    })
411}
412
413const fn adaptive_linear_grid(items: u32) -> [u32; 3] {
414    let groups = items.div_ceil(ADAPTIVE_TRAVERSAL_LINEAR_WORKGROUP_LANES);
415    if groups == 0 {
416        [1, 1, 1]
417    } else {
418        [groups, 1, 1]
419    }
420}
421
422/// Dispatch grid for adaptive traversal kernels that process one node per lane.
423#[must_use]
424pub const fn adaptive_node_dispatch_grid(node_count: u32) -> [u32; 3] {
425    adaptive_linear_grid(node_count)
426}
427
428#[cfg(test)]
429mod tests {
430    use super::*;
431    use crate::graph::adaptive_traverse::mode_selection::should_use_dense;
432    use crate::graph::adaptive_traverse::test_graphs::build_dense_adj;
433
434    #[test]
435    fn adaptive_layout_validation_accepts_valid_csr_and_dense_rows() {
436        let layout = validate_adaptive_traversal_layout(
437            3,
438            &[0, 1, 2, 2],
439            &[1, 2],
440            &[1, 1],
441            &build_dense_adj(&[(0, 1), (1, 2)], 3),
442        )
443        .unwrap();
444        assert_eq!(layout.edge_count, 2);
445        assert_eq!(layout.max_row_degree, 1);
446        assert_eq!(layout.edge_storage_words, 2);
447        assert_eq!(layout.words, 1);
448        assert_eq!(layout.dense_words, 3);
449    }
450
451    #[test]
452    fn adaptive_layout_validation_rejects_malformed_layouts() {
453        let dense = build_dense_adj(&[(0, 1)], 2);
454        let err =
455            validate_adaptive_traversal_layout(2, &[0, 2, 1], &[1], &[1], &dense).unwrap_err();
456        assert!(err.contains("final CSR offset") || err.contains("non-monotonic"));
457
458        let err =
459            validate_adaptive_traversal_layout(2, &[0, 1, 1], &[2], &[1], &dense).unwrap_err();
460        assert!(err.contains("outside node_count"));
461
462        let err = validate_adaptive_traversal_layout(2, &[0, 1, 1], &[1], &[1], &[]).unwrap_err();
463        assert!(err.contains("dense adjacency words"));
464    }
465
466    #[test]
467    fn adaptive_frontier_validation_accepts_canonical_frontier() {
468        assert_eq!(
469            validate_adaptive_frontier(64, &[1, 0]).unwrap(),
470            AdaptiveFrontierLayout {
471                words: 2,
472                words_u32: 2,
473            }
474        );
475    }
476
477    #[test]
478    fn adaptive_frontier_work_plan_classifies_zero_and_nonzero_frontiers() {
479        assert_eq!(
480            plan_adaptive_frontier_work(64, &[0, 0]).unwrap(),
481            AdaptiveFrontierWorkPlan {
482                layout: AdaptiveFrontierLayout {
483                    words: 2,
484                    words_u32: 2,
485                },
486                has_active_bits: false,
487            }
488        );
489
490        assert!(
491            plan_adaptive_frontier_work(64, &[0, 1])
492                .unwrap()
493                .has_active_bits
494        );
495    }
496
497    #[test]
498    fn adaptive_frontier_stats_ignore_tail_padding_bits() {
499        let stats = adaptive_frontier_stats(35, &[0b101, u32::MAX & !0b111], "tail stats")
500            .expect("Fix: tail-padded frontier should be valid");
501
502        assert_eq!(stats.popcount, 2);
503        assert_eq!(stats.nonzero_words, 1);
504        assert_eq!(
505            adaptive_frontier_popcount_in_domain(35, &[0b101, u32::MAX & !0b111], "tail popcount")
506                .expect("Fix: tail-padded frontier should count"),
507            2
508        );
509        assert!(
510            !plan_adaptive_frontier_work(35, &[0, u32::MAX & !0b111])
511                .expect("Fix: tail-only padding frontier should be valid")
512                .has_active_bits,
513            "tail padding bits beyond node_count must not trigger resident traversal work"
514        );
515        assert!(
516            !should_use_dense(&[0, u32::MAX & !0b111], 35),
517            "tail padding bits must not push adaptive mode selection toward dense traversal"
518        );
519    }
520
521    #[test]
522    fn adaptive_frontier_validation_rejects_zero_nodes_and_wrong_width() {
523        let err = validate_adaptive_frontier(0, &[]).unwrap_err();
524        assert!(err.contains("node_count > 0"));
525
526        let err = validate_adaptive_frontier(64, &[1]).unwrap_err();
527        assert!(err.contains("expected 2 word"));
528    }
529
530    #[test]
531    fn resident_frontier_plan_centralizes_bytes_and_grids() {
532        let plan = plan_adaptive_resident_frontier_step(8_193, &[1; 257])
533            .expect("Fix: resident frontier plan should accept a correctly shaped frontier");
534
535        assert!(plan.work.has_active_bits);
536        assert_eq!(plan.work.layout.words_u32, 257);
537        assert_eq!(plan.frontier_bytes, 257 * std::mem::size_of::<u32>());
538        assert_eq!(plan.popcount_bytes, std::mem::size_of::<u32>());
539        assert_eq!(plan.frontier_word_grid, [2, 1, 1]);
540        assert_eq!(plan.node_grid, [33, 1, 1]);
541    }
542
543    #[test]
544    fn adaptive_node_dispatch_grid_packs_node_lanes_into_blocks() {
545        assert_eq!(adaptive_node_dispatch_grid(0), [1, 1, 1]);
546        assert_eq!(adaptive_node_dispatch_grid(1), [1, 1, 1]);
547        assert_eq!(adaptive_node_dispatch_grid(256), [1, 1, 1]);
548        assert_eq!(adaptive_node_dispatch_grid(257), [2, 1, 1]);
549        assert_eq!(adaptive_node_dispatch_grid(513), [3, 1, 1]);
550    }
551
552    #[test]
553    fn generated_adaptive_node_dispatch_grid_covers_all_shapes_to_8192() {
554        for node_count in 0..=8_192 {
555            let grid = adaptive_node_dispatch_grid(node_count);
556            assert_eq!(
557                grid[1], 1,
558                "Fix: adaptive node grid y dimension drifted at node_count={node_count}"
559            );
560            assert_eq!(
561                grid[2], 1,
562                "Fix: adaptive node grid z dimension drifted at node_count={node_count}"
563            );
564            assert!(
565                grid[0] >= 1,
566                "Fix: adaptive node grid must keep empty traversal launchable"
567            );
568            assert!(
569                grid[0] * ADAPTIVE_TRAVERSAL_LINEAR_WORKGROUP_LANES >= node_count.max(1),
570                "Fix: adaptive node grid under-covers node_count={node_count}"
571            );
572            assert!(
573                grid[0] == 1
574                    || (grid[0] - 1) * ADAPTIVE_TRAVERSAL_LINEAR_WORKGROUP_LANES
575                        < node_count.max(1),
576                "Fix: adaptive node grid over-launches an avoidable extra block at node_count={node_count}"
577            );
578        }
579    }
580
581    #[test]
582    fn resident_sparse_queue_plan_centralizes_queue_shape() {
583        let plan = plan_adaptive_resident_sparse_queue_step(513, &[1; 17])
584            .expect("Fix: resident sparse-queue plan should accept a correctly shaped frontier");
585
586        assert_eq!(plan.frontier.work.layout.words, 17);
587        assert_eq!(plan.frontier_nonzero_words, 17);
588        assert_eq!(plan.queue_capacity, 32);
589        assert_eq!(plan.queue_bytes, 32 * std::mem::size_of::<u32>());
590        assert_eq!(plan.queue_grid, [1, 1, 1]);
591    }
592
593    #[test]
594    fn resident_sparse_queue_plan_sizes_queue_from_active_frontier() {
595        let node_count = 1_000_000u32;
596        let mut frontier = vec![0u32; bitset_words(node_count) as usize];
597        frontier[0] = 1;
598
599        let single = plan_adaptive_resident_sparse_queue_step(node_count, &frontier)
600            .expect("Fix: resident sparse-queue plan should accept a single active source");
601
602        assert_eq!(single.queue_capacity, 1);
603        assert_eq!(single.frontier_nonzero_words, 1);
604        assert_eq!(single.queue_bytes, std::mem::size_of::<u32>());
605        assert_eq!(single.queue_grid, [1, 1, 1]);
606
607        for node in 1..257u32 {
608            frontier[(node / 32) as usize] |= 1 << (node % 32);
609        }
610        let bucketed = plan_adaptive_resident_sparse_queue_step(node_count, &frontier)
611            .expect("Fix: resident sparse-queue plan should accept a sparse active frontier");
612
613        assert_eq!(bucketed.queue_capacity, 512);
614        assert_eq!(bucketed.frontier_nonzero_words, 9);
615        assert_eq!(bucketed.queue_bytes, 512 * std::mem::size_of::<u32>());
616        assert_eq!(bucketed.queue_grid, [2, 1, 1]);
617    }
618
619    #[test]
620    fn generated_sparse_queue_capacity_covers_active_count_without_graph_sized_overlaunch() {
621        for seed in 0..10_000u32 {
622            let node_count = 1 + (mix32(seed) % 1_000_000);
623            let frontier_popcount = mix32(seed ^ 0xA57A_5A7A);
624            let active = frontier_popcount.min(node_count);
625            let capacity = adaptive_sparse_queue_capacity(node_count, frontier_popcount);
626
627            assert!(capacity >= active.max(1));
628            assert!(capacity <= node_count);
629            if active <= node_count / 2 && active > 0 {
630                assert!(
631                    capacity <= active.saturating_mul(2),
632                    "Fix: sparse queue capacity should bucket active_count={active} tightly, got {capacity}"
633                );
634            }
635        }
636    }
637
638    #[test]
639    fn resident_auto_plan_selects_mode_from_primitive_popcount() {
640        let mut frontier = vec![0u32; bitset_words(1_000) as usize];
641        for node in 0..260u32 {
642            frontier[(node / 32) as usize] |= 1 << (node % 32);
643        }
644
645        let plan = plan_adaptive_resident_auto_step(1_000, 10_000, &frontier, 25)
646            .expect("Fix: resident auto plan should accept a correctly shaped frontier");
647
648        assert_eq!(plan.frontier_popcount, 260);
649        assert_eq!(plan.mode, AdaptiveTraversalMode::SparseDense);
650        assert!(plan.frontier.work.has_active_bits);
651    }
652
653    #[test]
654    fn resident_auto_plan_zero_frontier_keeps_sparse_queue_identity_case() {
655        let plan = plan_adaptive_resident_auto_step(64, 128, &[0, 0], 25)
656            .expect("Fix: zero frontier still has a valid resident auto plan");
657
658        assert_eq!(plan.frontier_popcount, 0);
659        assert_eq!(plan.mode, AdaptiveTraversalMode::SparseQueue);
660        assert!(!plan.frontier.work.has_active_bits);
661    }
662
663    fn mix32(mut value: u32) -> u32 {
664        value ^= value >> 16;
665        value = value.wrapping_mul(0x7feb_352d);
666        value ^= value >> 15;
667        value = value.wrapping_mul(0x846c_a68b);
668        value ^ (value >> 16)
669    }
670}
vyre_primitives/graph/adaptive_traverse/frontier_plan.rs

vyre_primitives/graph/adaptive_traverse/
frontier_plan.rs
