weir/
ifds_shape.rs

1//! IFDS shape, domain sizing, and problem-boundary validation.
2
3use vyre_primitives::bitset::bitset_words;
4use vyre_primitives::graph::exploded::validate_ifds_csr_layout;
5
6#[allow(clippy::too_many_arguments)]
7pub fn validate_ifds_problem(
8    context: &str,
9    num_procs: u32,
10    blocks_per_proc: u32,
11    facts_per_proc: u32,
12    intra_edges: &[(u32, u32, u32)],
13    inter_edges: &[(u32, u32, u32, u32)],
14    flow_gen: &[(u32, u32, u32)],
15    flow_kill: &[(u32, u32, u32)],
16    seed_facts: &[(u32, u32, u32)],
17) -> Result<(), String> {
18    if num_procs == 0 || blocks_per_proc == 0 || facts_per_proc == 0 {
19        return Err(format!(
20            "{context} requires non-zero dimensions, got procs={num_procs}, blocks={blocks_per_proc}, facts={facts_per_proc}. Fix: validate the IFDS problem shape before dispatch."
21        ));
22    }
23    for (idx, &(proc_id, src_block, dst_block)) in intra_edges.iter().enumerate() {
24        if proc_id >= num_procs || src_block >= blocks_per_proc || dst_block >= blocks_per_proc {
25            return Err(format!(
26                "{context} intra edge {idx} is out of domain: proc={proc_id}, src_block={src_block}, dst_block={dst_block}, domain procs={num_procs}, blocks={blocks_per_proc}. Fix: discard or remap malformed CFG edges before IFDS dispatch."
27            ));
28        }
29    }
30    for (idx, &(src_proc, src_block, dst_proc, dst_block)) in inter_edges.iter().enumerate() {
31        if src_proc >= num_procs
32            || dst_proc >= num_procs
33            || src_block >= blocks_per_proc
34            || dst_block >= blocks_per_proc
35        {
36            return Err(format!(
37                "{context} inter edge {idx} is out of domain: src_proc={src_proc}, src_block={src_block}, dst_proc={dst_proc}, dst_block={dst_block}, domain procs={num_procs}, blocks={blocks_per_proc}. Fix: discard or remap malformed callgraph edges before IFDS dispatch."
38            ));
39        }
40    }
41    for (label, triples) in [("GEN", flow_gen), ("KILL", flow_kill), ("seed", seed_facts)] {
42        for (idx, &(proc_id, block_id, fact_id)) in triples.iter().enumerate() {
43            if proc_id >= num_procs || block_id >= blocks_per_proc || fact_id >= facts_per_proc {
44                return Err(format!(
45                    "{context} {label} tuple {idx} is out of domain: proc={proc_id}, block={block_id}, fact={fact_id}, domain procs={num_procs}, blocks={blocks_per_proc}, facts={facts_per_proc}. Fix: discard or remap malformed dataflow facts before IFDS dispatch."
46                ));
47            }
48        }
49    }
50    Ok(())
51}
52
53/// Dispatch geometry for one IFDS BFS step on the GPU.
54#[derive(Debug, Clone, Copy, PartialEq)]
55pub struct IfdsShape {
56    /// Number of procedures in the exploded supergraph.
57    pub num_procs: u32,
58    /// Number of basic blocks encoded per procedure.
59    pub blocks_per_proc: u32,
60    /// Number of dataflow facts encoded per procedure.
61    pub facts_per_proc: u32,
62    /// Number of graph edges in the CSR representation.
63    pub edge_count: u32,
64}
65
66/// Auditable IFDS shape report for release evidence, resident planning, and
67/// dispatch diagnostics.
68#[derive(Debug, Clone, PartialEq, Eq)]
69#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
70pub struct IfdsShapeCertificate {
71    /// Number of procedures in the exploded supergraph.
72    pub num_procs: u32,
73    /// Number of basic blocks encoded per procedure.
74    pub blocks_per_proc: u32,
75    /// Number of dataflow facts encoded per procedure.
76    pub facts_per_proc: u32,
77    /// Number of graph edges in the CSR representation.
78    pub edge_count: u32,
79    /// Whether `edge_count == 0`; valid for disconnected seed-only problems.
80    pub zero_edge_budget: bool,
81    /// Whether the dimensions fit the packed IFDS domain.
82    pub fits: bool,
83    /// Exploded node count when dimensions are valid.
84    pub exploded_nodes: Option<u32>,
85    /// Packed bitset words required for one frontier over `exploded_nodes`.
86    pub bitset_words: Option<u32>,
87    /// Structured rejection reason when the shape exceeds a domain cap.
88    pub cap_reason: Option<String>,
89}
90
91impl IfdsShape {
92    /// Construct an [`IfdsShape`] from individual dimensions.
93    #[inline]
94    #[must_use]
95    pub const fn new(
96        num_procs: u32,
97        blocks_per_proc: u32,
98        facts_per_proc: u32,
99        edge_count: u32,
100    ) -> Self {
101        Self {
102            num_procs,
103            blocks_per_proc,
104            facts_per_proc,
105            edge_count,
106        }
107    }
108
109    /// Number of exploded-supergraph nodes = `procs * blocks * facts`.
110    #[inline]
111    pub fn node_count(&self) -> Result<u32, String> {
112        self.checked_node_count()
113    }
114
115    /// Checked node count for callers that can return structured errors.
116    #[inline]
117    pub fn checked_node_count(&self) -> Result<u32, String> {
118        validate_ifds_csr_layout(
119            self.num_procs,
120            self.blocks_per_proc,
121            self.facts_per_proc,
122            0,
123            0,
124            0,
125        )
126        .map(|layout| layout.total_nodes)
127        .map_err(|error| format!("weir IFDS dimensions invalid: {error}"))
128    }
129
130    /// Shared linear layout domain for the exploded IFDS supergraph.
131    #[inline]
132    pub fn node_domain(&self) -> Result<crate::graph_layout::LinearDomain, String> {
133        self.checked_node_count()
134            .map(crate::graph_layout::LinearDomain::new)
135    }
136
137    /// Pre-flight fit check for 32-bit exploded-node encoding.
138    #[inline]
139    #[must_use]
140    pub fn fits(&self) -> bool {
141        validate_ifds_csr_layout(
142            self.num_procs,
143            self.blocks_per_proc,
144            self.facts_per_proc,
145            0,
146            0,
147            0,
148        )
149        .is_ok()
150    }
151
152    /// Build an auditable shape certificate without duplicating validation
153    /// logic. Invalid shapes return `fits=false` plus the same cap reason used
154    /// by checked dispatch paths.
155    #[must_use]
156    pub fn certificate(&self) -> IfdsShapeCertificate {
157        match self.checked_node_count() {
158            Ok(exploded_nodes) => IfdsShapeCertificate {
159                num_procs: self.num_procs,
160                blocks_per_proc: self.blocks_per_proc,
161                facts_per_proc: self.facts_per_proc,
162                edge_count: self.edge_count,
163                zero_edge_budget: self.edge_count == 0,
164                fits: true,
165                exploded_nodes: Some(exploded_nodes),
166                bitset_words: Some(bitset_words(exploded_nodes)),
167                cap_reason: None,
168            },
169            Err(error) => IfdsShapeCertificate {
170                num_procs: self.num_procs,
171                blocks_per_proc: self.blocks_per_proc,
172                facts_per_proc: self.facts_per_proc,
173                edge_count: self.edge_count,
174                zero_edge_budget: self.edge_count == 0,
175                fits: false,
176                exploded_nodes: None,
177                bitset_words: None,
178                cap_reason: Some(error),
179            },
180        }
181    }
182}
183
184#[cfg(test)]
185mod tests {
186    use super::{validate_ifds_problem, IfdsShape};
187    use vyre_primitives::graph::exploded::{MAX_BLOCK_ID, MAX_FACT_ID, MAX_PROC_ID};
188
189    // ------------------------------------------------------------------
190    // 1. Overflow rejection (u32::MAX dimensions must be rejected).
191    // ------------------------------------------------------------------
192
193    #[test]
194    fn ifds_shape_rejects_u32_max_procs() {
195        let shape = IfdsShape::new(u32::MAX, 1, 1, 0);
196        assert!(!shape.fits());
197        assert!(shape.checked_node_count().is_err());
198        assert!(shape.node_domain().is_err());
199    }
200
201    #[test]
202    fn ifds_shape_rejects_u32_max_blocks() {
203        let shape = IfdsShape::new(1, u32::MAX, 1, 0);
204        assert!(!shape.fits());
205        assert!(shape.checked_node_count().is_err());
206    }
207
208    #[test]
209    fn ifds_shape_rejects_u32_max_facts() {
210        let shape = IfdsShape::new(1, 1, u32::MAX, 0);
211        assert!(!shape.fits());
212        assert!(shape.checked_node_count().is_err());
213    }
214
215    #[test]
216    fn ifds_shape_rejects_product_overflow_with_legal_axes() {
217        // 65536 * 65536 = 2^32, overflowing u32. Each axis is individually
218        // inside the packed encoding limits, but the product overflows.
219        let shape = IfdsShape::new(2, 65536, 65536, 0);
220        assert!(!shape.fits());
221        assert!(shape.checked_node_count().is_err());
222    }
223
224    #[test]
225    fn ifds_shape_rejects_max_proc_id_plus_one() {
226        let shape = IfdsShape::new(MAX_PROC_ID + 2, 1, 1, 0);
227        assert!(!shape.fits());
228        assert!(shape.checked_node_count().is_err());
229    }
230
231    #[test]
232    fn ifds_shape_rejects_max_block_id_plus_one() {
233        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 2, 1, 0);
234        assert!(!shape.fits());
235        assert!(shape.checked_node_count().is_err());
236    }
237
238    #[test]
239    fn ifds_shape_rejects_max_fact_id_plus_one() {
240        let shape = IfdsShape::new(1, 1, MAX_FACT_ID + 2, 0);
241        assert!(!shape.fits());
242        assert!(shape.checked_node_count().is_err());
243    }
244
245    // ------------------------------------------------------------------
246    // 2. Zero-dimension rejection.
247    // ------------------------------------------------------------------
248
249    #[test]
250    fn ifds_shape_rejects_zero_procs() {
251        let shape = IfdsShape::new(0, 1, 1, 0);
252        assert!(!shape.fits());
253        assert!(shape.checked_node_count().is_err());
254    }
255
256    #[test]
257    fn ifds_shape_rejects_zero_blocks() {
258        let shape = IfdsShape::new(1, 0, 1, 0);
259        assert!(!shape.fits());
260        assert!(shape.checked_node_count().is_err());
261    }
262
263    #[test]
264    fn ifds_shape_rejects_zero_facts() {
265        let shape = IfdsShape::new(1, 1, 0, 0);
266        assert!(!shape.fits());
267        assert!(shape.checked_node_count().is_err());
268    }
269
270    #[test]
271    fn validate_ifds_problem_rejects_zero_procs() {
272        let err = validate_ifds_problem("test", 0, 1, 1, &[], &[], &[], &[], &[])
273            .expect_err("zero procs must be rejected");
274        assert!(err.contains("requires non-zero dimensions"));
275    }
276
277    #[test]
278    fn validate_ifds_problem_rejects_zero_blocks() {
279        let err = validate_ifds_problem("test", 1, 0, 1, &[], &[], &[], &[], &[])
280            .expect_err("zero blocks must be rejected");
281        assert!(err.contains("requires non-zero dimensions"));
282    }
283
284    #[test]
285    fn validate_ifds_problem_rejects_zero_facts() {
286        let err = validate_ifds_problem("test", 1, 1, 0, &[], &[], &[], &[], &[])
287            .expect_err("zero facts must be rejected");
288        assert!(err.contains("requires non-zero dimensions"));
289    }
290
291    #[test]
292    fn validate_ifds_problem_accepts_empty_edges_and_seeds() {
293        // Empty edge / seed lists are fine as long as dimensions are non-zero.
294        validate_ifds_problem("test", 1, 1, 1, &[], &[], &[], &[], &[])
295            .expect("empty edges/seeds with valid dims should succeed");
296    }
297
298    #[test]
299    fn validate_ifds_problem_accepts_zero_edge_count() {
300        // edge_count is not validated by validate_ifds_problem.
301        validate_ifds_problem("test", 2, 4, 8, &[], &[], &[], &[], &[])
302            .expect("zero edge count should be accepted");
303    }
304
305    // ------------------------------------------------------------------
306    // 3. fits() on extreme shapes.
307    // ------------------------------------------------------------------
308
309    #[test]
310    fn ifds_shape_fits_at_exact_max_limits() {
311        // MAX_PROC_ID + 1 = 4096, MAX_BLOCK_ID + 1 = 1024, MAX_FACT_ID + 1 = 1024.
312        // The product 4096*1024*1024 overflows u32, so we test the largest encoding
313        // that still fits in the product: 4095 procs × 1024 blocks × 1024 facts.
314        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, MAX_FACT_ID, 0);
315        assert!(shape.fits());
316    }
317
318    #[test]
319    fn ifds_shape_fits_at_one_per_axis() {
320        let shape = IfdsShape::new(1, 1, 1, 0);
321        assert!(shape.fits());
322    }
323
324    #[test]
325    fn ifds_shape_fits_rejects_proc_overflow() {
326        let shape = IfdsShape::new(MAX_PROC_ID + 2, 1, 1, 0);
327        assert!(!shape.fits());
328    }
329
330    #[test]
331    fn ifds_shape_fits_rejects_block_overflow() {
332        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 2, 1, 0);
333        assert!(!shape.fits());
334    }
335
336    #[test]
337    fn ifds_shape_fits_rejects_fact_overflow() {
338        let shape = IfdsShape::new(1, 1, MAX_FACT_ID + 2, 0);
339        assert!(!shape.fits());
340    }
341
342    #[test]
343    fn ifds_shape_fits_rejects_overflow_product() {
344        let shape = IfdsShape::new(2, 65536, 65536, 0);
345        assert!(!shape.fits());
346    }
347
348    #[test]
349    fn ifds_shape_fits_accepts_realistic_dimensions() {
350        let shape = IfdsShape::new(64, 128, 32, 4096);
351        assert!(shape.fits());
352    }
353
354    // ------------------------------------------------------------------
355    // 4. checked_node_count saturation.
356    // ------------------------------------------------------------------
357
358    #[test]
359    fn checked_node_count_computes_small_product_correctly() {
360        let shape = IfdsShape::new(2, 3, 4, 0);
361        assert_eq!(shape.checked_node_count().unwrap(), 24);
362    }
363
364    #[test]
365    fn checked_node_count_saturation_on_proc_overflow() {
366        let shape = IfdsShape::new(MAX_PROC_ID + 2, 1, 1, 0);
367        let err = shape.checked_node_count().expect_err("must error");
368        assert!(err.contains("weir IFDS dimensions invalid"));
369    }
370
371    #[test]
372    fn checked_node_count_saturation_on_block_overflow() {
373        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 2, 1, 0);
374        let err = shape.checked_node_count().expect_err("must error");
375        assert!(err.contains("weir IFDS dimensions invalid"));
376    }
377
378    #[test]
379    fn checked_node_count_saturation_on_fact_overflow() {
380        let shape = IfdsShape::new(1, 1, MAX_FACT_ID + 2, 0);
381        let err = shape.checked_node_count().expect_err("must error");
382        assert!(err.contains("weir IFDS dimensions invalid"));
383    }
384
385    #[test]
386    fn checked_node_count_saturation_on_product_overflow() {
387        let shape = IfdsShape::new(2, 65536, 65536, 0);
388        let err = shape.checked_node_count().expect_err("must error");
389        assert!(err.contains("weir IFDS dimensions invalid"));
390    }
391
392    #[test]
393    fn checked_node_count_at_max_limits() {
394        // Use dimensions that fit both encoding limits and u32 product space.
395        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, MAX_FACT_ID, 0);
396        let count = shape.checked_node_count().unwrap();
397        assert_eq!(
398            count as u64,
399            (MAX_PROC_ID as u64 + 1) * (MAX_BLOCK_ID as u64 + 1) * (MAX_FACT_ID as u64)
400        );
401    }
402
403    #[test]
404    fn node_count_alias_matches_checked_node_count() {
405        let shape = IfdsShape::new(3, 7, 11, 0);
406        assert_eq!(
407            shape.node_count().unwrap(),
408            shape.checked_node_count().unwrap()
409        );
410    }
411
412    // ------------------------------------------------------------------
413    // 5. node_domain() correctness for valid shapes.
414    // ------------------------------------------------------------------
415
416    #[test]
417    fn node_domain_returns_correct_element_count() {
418        let shape = IfdsShape::new(2, 3, 5, 0);
419        let domain = shape.node_domain().unwrap();
420        assert_eq!(domain.element_count(), 30);
421    }
422
423    #[test]
424    fn node_domain_rejects_zero_dimensions() {
425        let shape = IfdsShape::new(0, 1, 1, 0);
426        assert!(shape.node_domain().is_err());
427    }
428
429    #[test]
430    fn node_domain_rejects_overflow_dimensions() {
431        let shape = IfdsShape::new(u32::MAX, 1, 1, 0);
432        assert!(shape.node_domain().is_err());
433    }
434
435    #[test]
436    fn node_domain_at_max_limits_succeeds() {
437        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, MAX_FACT_ID, 0);
438        let domain = shape.node_domain().unwrap();
439        assert_eq!(
440            domain.element_count() as u64,
441            (MAX_PROC_ID as u64 + 1) * (MAX_BLOCK_ID as u64 + 1) * (MAX_FACT_ID as u64)
442        );
443    }
444
445    // ------------------------------------------------------------------
446    // 6. IfdsShape::new with various valid/invalid combinations.
447    // ------------------------------------------------------------------
448
449    #[test]
450    fn new_with_valid_small_dimensions() {
451        let shape = IfdsShape::new(1, 1, 1, 0);
452        assert_eq!(shape.num_procs, 1);
453        assert_eq!(shape.blocks_per_proc, 1);
454        assert_eq!(shape.facts_per_proc, 1);
455        assert_eq!(shape.edge_count, 0);
456        assert!(shape.fits());
457    }
458
459    #[test]
460    fn new_with_large_valid_dimensions() {
461        // 1000³ = 1_000_000_000 fits comfortably inside u32 and encoding limits.
462        let shape = IfdsShape::new(1000, 1000, 1000, 1_000_000);
463        assert!(shape.fits());
464    }
465
466    #[test]
467    fn new_with_invalid_proc_dimension() {
468        let shape = IfdsShape::new(0, 1, 1, 0);
469        assert!(!shape.fits());
470    }
471
472    #[test]
473    fn new_with_invalid_block_dimension() {
474        let shape = IfdsShape::new(1, 0, 1, 0);
475        assert!(!shape.fits());
476    }
477
478    #[test]
479    fn new_with_invalid_fact_dimension() {
480        let shape = IfdsShape::new(1, 1, 0, 0);
481        assert!(!shape.fits());
482    }
483
484    #[test]
485    fn new_preserves_edge_count() {
486        let shape = IfdsShape::new(4, 8, 16, 12345);
487        assert_eq!(shape.edge_count, 12345);
488    }
489
490    #[test]
491    fn new_with_all_axes_at_boundary() {
492        // Use encoding-max dimensions whose product still fits in u32.
493        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, MAX_FACT_ID, u32::MAX);
494        assert!(shape.fits());
495        assert_eq!(shape.edge_count, u32::MAX);
496    }
497
498    // ------------------------------------------------------------------
499    // 7. validate_ifds_problem edge / tuple domain checking.
500    // ------------------------------------------------------------------
501
502    #[test]
503    fn validate_intra_edge_out_of_domain_proc() {
504        let err = validate_ifds_problem(
505            "test",
506            2,
507            4,
508            4,
509            &[(2, 0, 1)], // proc_id == num_procs is OOB
510            &[],
511            &[],
512            &[],
513            &[],
514        )
515        .expect_err("must error");
516        assert!(err.contains("intra edge 0 is out of domain"));
517    }
518
519    #[test]
520    fn validate_intra_edge_out_of_domain_block() {
521        let err = validate_ifds_problem(
522            "test",
523            2,
524            4,
525            4,
526            &[(0, 4, 1)], // src_block == blocks_per_proc is OOB
527            &[],
528            &[],
529            &[],
530            &[],
531        )
532        .expect_err("must error");
533        assert!(err.contains("intra edge 0 is out of domain"));
534    }
535
536    #[test]
537    fn validate_inter_edge_out_of_domain_src_proc() {
538        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[(2, 0, 1, 1)], &[], &[], &[])
539            .expect_err("must error");
540        assert!(err.contains("inter edge 0 is out of domain"));
541    }
542
543    #[test]
544    fn validate_inter_edge_out_of_domain_dst_proc() {
545        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[(0, 0, 2, 1)], &[], &[], &[])
546            .expect_err("must error");
547        assert!(err.contains("inter edge 0 is out of domain"));
548    }
549
550    #[test]
551    fn validate_flow_gen_out_of_domain() {
552        let err = validate_ifds_problem(
553            "test",
554            2,
555            4,
556            4,
557            &[],
558            &[],
559            &[(0, 0, 4)], // fact_id == facts_per_proc is OOB
560            &[],
561            &[],
562        )
563        .expect_err("must error");
564        assert!(err.contains("GEN tuple 0 is out of domain"));
565    }
566
567    #[test]
568    fn validate_flow_kill_out_of_domain() {
569        let err = validate_ifds_problem(
570            "test",
571            2,
572            4,
573            4,
574            &[],
575            &[],
576            &[],
577            &[(1, 4, 0)], // block_id == blocks_per_proc is OOB
578            &[],
579        )
580        .expect_err("must error");
581        assert!(err.contains("KILL tuple 0 is out of domain"));
582    }
583
584    #[test]
585    fn validate_seed_facts_out_of_domain() {
586        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[], &[], &[], &[(0, 0, 4)])
587            .expect_err("must error");
588        assert!(err.contains("seed tuple 0 is out of domain"));
589    }
590
591    #[test]
592    fn validate_multiple_intra_edges_first_oob() {
593        let err =
594            validate_ifds_problem("test", 2, 4, 4, &[(0, 0, 0), (2, 0, 0)], &[], &[], &[], &[])
595                .expect_err("must error");
596        assert!(err.contains("intra edge 1 is out of domain"));
597    }
598
599    #[test]
600    fn validate_mixed_valid_and_invalid() {
601        // Valid edges but invalid seed fact.
602        let err = validate_ifds_problem(
603            "test",
604            2,
605            4,
606            4,
607            &[(0, 0, 1), (1, 2, 3)],
608            &[(0, 0, 1, 1)],
609            &[(0, 0, 0)],
610            &[(1, 1, 1)],
611            &[(0, 0, 4)],
612        )
613        .expect_err("must error");
614        assert!(err.contains("seed tuple 0 is out of domain"));
615    }
616
617    #[test]
618    fn validate_all_valid_edges_and_tuples() {
619        validate_ifds_problem(
620            "test",
621            4,
622            8,
623            8,
624            &[(0, 0, 1), (1, 2, 3)],
625            &[(0, 0, 1, 1), (2, 3, 3, 7)],
626            &[(0, 0, 0), (3, 7, 7)],
627            &[(1, 1, 1)],
628            &[(0, 0, 0), (2, 4, 4)],
629        )
630        .expect("all valid edges and tuples should succeed");
631    }
632
633    #[test]
634    fn validate_problem_context_included_in_error() {
635        let err = validate_ifds_problem("my_context", 0, 1, 1, &[], &[], &[], &[], &[])
636            .expect_err("must error");
637        assert!(err.contains("my_context"));
638    }
639
640    #[test]
641    fn ifds_shape_clone_and_debug() {
642        let shape = IfdsShape::new(2, 4, 8, 16);
643        let cloned = shape;
644        assert_eq!(cloned.num_procs, shape.num_procs);
645        let debug = format!("{:?}", shape);
646        assert!(debug.contains("IfdsShape"));
647    }
648
649    #[test]
650    fn ifds_shape_copy_semantics() {
651        let a = IfdsShape::new(1, 2, 3, 4);
652        let b = a;
653        // a is still usable because IfdsShape is Copy.
654        assert_eq!(a.num_procs, 1);
655        assert_eq!(b.facts_per_proc, 3);
656    }
657
658    #[test]
659    fn fits_with_two_axes_at_boundary() {
660        let shape = IfdsShape::new(MAX_PROC_ID + 1, MAX_BLOCK_ID + 1, 1, 0);
661        assert!(shape.fits());
662        let shape = IfdsShape::new(MAX_PROC_ID + 1, 1, MAX_FACT_ID + 1, 0);
663        assert!(shape.fits());
664        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 1, MAX_FACT_ID + 1, 0);
665        assert!(shape.fits());
666    }
667
668    #[test]
669    fn fits_rejects_two_axes_overflow() {
670        let shape = IfdsShape::new(MAX_PROC_ID + 2, MAX_BLOCK_ID + 2, 1, 0);
671        assert!(!shape.fits());
672        let shape = IfdsShape::new(MAX_PROC_ID + 2, 1, MAX_FACT_ID + 2, 0);
673        assert!(!shape.fits());
674        let shape = IfdsShape::new(1, MAX_BLOCK_ID + 2, MAX_FACT_ID + 2, 0);
675        assert!(!shape.fits());
676    }
677
678    #[test]
679    fn checked_node_count_for_mid_size_shape() {
680        let shape = IfdsShape::new(100, 50, 20, 0);
681        assert_eq!(shape.checked_node_count().unwrap(), 100 * 50 * 20);
682    }
683
684    #[test]
685    fn checked_node_count_rejects_zero_procs() {
686        assert!(IfdsShape::new(0, 1, 1, 0).checked_node_count().is_err());
687    }
688
689    #[test]
690    fn checked_node_count_rejects_zero_blocks() {
691        assert!(IfdsShape::new(1, 0, 1, 0).checked_node_count().is_err());
692    }
693
694    #[test]
695    fn checked_node_count_rejects_zero_facts() {
696        assert!(IfdsShape::new(1, 1, 0, 0).checked_node_count().is_err());
697    }
698
699    #[test]
700    fn node_domain_for_single_node() {
701        let domain = IfdsShape::new(1, 1, 1, 0).node_domain().unwrap();
702        assert_eq!(domain.element_count(), 1);
703    }
704
705    #[test]
706    fn node_domain_for_medium_shape() {
707        let domain = IfdsShape::new(10, 10, 10, 0).node_domain().unwrap();
708        assert_eq!(domain.element_count(), 1000);
709    }
710
711    #[test]
712    fn validate_inter_edge_out_of_domain_src_block() {
713        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[(0, 4, 1, 1)], &[], &[], &[])
714            .expect_err("must error");
715        assert!(err.contains("inter edge 0 is out of domain"));
716    }
717
718    #[test]
719    fn validate_inter_edge_out_of_domain_dst_block() {
720        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[(0, 0, 1, 4)], &[], &[], &[])
721            .expect_err("must error");
722        assert!(err.contains("inter edge 0 is out of domain"));
723    }
724
725    #[test]
726    fn validate_seed_fact_at_exact_boundary_rejected() {
727        // fact_id == facts_per_proc is out of domain.
728        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[], &[], &[], &[(0, 0, 4)])
729            .expect_err("must error");
730        assert!(err.contains("seed tuple 0 is out of domain"));
731    }
732
733    #[test]
734    fn validate_flow_gen_at_exact_boundary_rejected() {
735        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[], &[(0, 4, 0)], &[], &[])
736            .expect_err("must error");
737        assert!(err.contains("GEN tuple 0 is out of domain"));
738    }
739
740    #[test]
741    fn validate_flow_kill_at_exact_boundary_rejected() {
742        let err = validate_ifds_problem("test", 2, 4, 4, &[], &[], &[], &[(2, 0, 0)], &[])
743            .expect_err("must error");
744        assert!(err.contains("KILL tuple 0 is out of domain"));
745    }
746
747    #[test]
748    fn new_with_u32_max_edge_count_preserves_value() {
749        let shape = IfdsShape::new(1, 1, 1, u32::MAX);
750        assert_eq!(shape.edge_count, u32::MAX);
751        assert!(shape.fits());
752    }
753
754    #[test]
755    fn fits_with_all_ones() {
756        assert!(IfdsShape::new(1, 1, 1, 1).fits());
757    }
758
759    #[test]
760    fn node_count_error_contains_weir_prefix() {
761        let err = IfdsShape::new(0, 1, 1, 0)
762            .checked_node_count()
763            .expect_err("must err");
764        assert!(err.starts_with("weir IFDS dimensions invalid"));
765    }
766
767    #[test]
768    fn ifds_shape_certificate_reports_valid_dimensions() {
769        let cert = IfdsShape::new(2, 3, 4, 5).certificate();
770        assert_eq!(cert.num_procs, 2);
771        assert_eq!(cert.blocks_per_proc, 3);
772        assert_eq!(cert.facts_per_proc, 4);
773        assert_eq!(cert.edge_count, 5);
774        assert!(!cert.zero_edge_budget);
775        assert!(cert.fits);
776        assert_eq!(cert.exploded_nodes, Some(24));
777        assert_eq!(cert.bitset_words, Some(1));
778        assert_eq!(cert.cap_reason, None);
779    }
780
781    #[test]
782    fn ifds_shape_certificate_reports_frontier_bitset_width() {
783        let cert = IfdsShape::new(1, 33, 1, 1).certificate();
784        assert!(cert.fits);
785        assert_eq!(cert.exploded_nodes, Some(33));
786        assert_eq!(cert.bitset_words, Some(2));
787    }
788
789    #[test]
790    fn ifds_shape_certificate_preserves_zero_edge_budget() {
791        let cert = IfdsShape::new(2, 2, 2, 0).certificate();
792        assert!(cert.fits);
793        assert!(cert.zero_edge_budget);
794        assert_eq!(cert.exploded_nodes, Some(8));
795        assert_eq!(cert.bitset_words, Some(1));
796        assert_eq!(cert.cap_reason, None);
797    }
798
799    #[test]
800    fn ifds_shape_certificate_reports_zero_dimension_cap_reason() {
801        let cert = IfdsShape::new(0, 1, 1, 0).certificate();
802        assert!(!cert.fits);
803        assert_eq!(cert.exploded_nodes, None);
804        assert_eq!(cert.bitset_words, None);
805        let reason = cert.cap_reason.expect("invalid shape must carry cap reason");
806        assert!(reason.contains("weir IFDS dimensions invalid"), "{reason}");
807        assert!(reason.contains("nonzero"), "{reason}");
808    }
809
810    #[test]
811    fn ifds_shape_certificate_reports_overflow_cap_reason() {
812        let cert = IfdsShape::new(2, 65536, 65536, 0).certificate();
813        assert!(!cert.fits);
814        assert_eq!(cert.exploded_nodes, None);
815        assert_eq!(cert.bitset_words, None);
816        let reason = cert.cap_reason.expect("overflow shape must carry cap reason");
817        assert!(reason.contains("weir IFDS dimensions invalid"), "{reason}");
818    }
819}
weir/ifds_shape.rs

weir/
ifds_shape.rs
