Skip to main content

faultscope_core/
dem_sampling.rs

1use std::collections::HashMap;
2use std::sync::Arc;
3
4use crate::dem_canonical::{canonical_id_order, parity_canonicalize};
5use crate::labels::LocationCatalogBuilder;
6use crate::{
7    convert_detector_batch, for_each_bernoulli_event, packed_corrections_to_masks,
8    validate_decoder_detector_ids, validate_decoder_observable_ids, word_count,
9    CorrectionMaskBatch, DemBatch, DemEvent, DemHotspotEstimate, DemLocationGroup, DetectorBatch,
10    DetectorBatchFormat, DetectorBatchView, DetectorErrorEdge, DetectorErrorModel, LocationCatalog,
11    LocationId, Mask, NpError, NpResult, PackedObservableShotBatch, SmallRng,
12};
13
14#[derive(Debug, Clone, PartialEq)]
15pub(crate) struct DemProgramEdge {
16    pub(crate) probability: f64,
17    pub(crate) detectors: Vec<i64>,
18    pub(crate) observables: Vec<i64>,
19}
20
21#[derive(Debug, Clone, PartialEq)]
22pub(crate) struct DemProgramEdgeMetadata {
23    pub(crate) location_id: LocationId,
24    pub(crate) event: DemEvent,
25}
26
27#[derive(Debug, Clone, PartialEq)]
28pub(crate) struct DemProgramLocationGroup {
29    pub(crate) location_id: LocationId,
30    pub(crate) edge_indices: Vec<usize>,
31    pub(crate) total_probability: f64,
32}
33
34struct CompiledDemEdges {
35    edges: Vec<DemProgramEdge>,
36    metadata: Option<Vec<DemProgramEdgeMetadata>>,
37    catalog: LocationCatalog,
38    location_groups: Vec<DemProgramLocationGroup>,
39}
40
41/// Bit-packed detector-error-model sampler and hotspot estimator.
42///
43/// This simulator samples DEM edges as independent Bernoulli error
44/// instructions, computes detector and observable masks, and can aggregate
45/// edge and location hotspot estimates entirely in Rust.
46#[derive(Debug, Clone, PartialEq)]
47pub struct DemHotspotEstimator {
48    /// Construction-time detector ID mirror retained for source compatibility.
49    ///
50    /// Operational methods use [`Self::detector_ids`] instead. Mutating this
51    /// field does not recompile or otherwise change the estimator.
52    pub detector_ids: Vec<i64>,
53    /// Construction-time observable ID mirror retained for source compatibility.
54    ///
55    /// Operational methods use [`Self::observable_ids`] instead. Mutating this
56    /// field does not recompile or otherwise change the estimator.
57    pub observable_ids: Vec<i64>,
58    canonical_detector_ids: Arc<[i64]>,
59    canonical_observable_ids: Arc<[i64]>,
60    edges: Vec<DemProgramEdge>,
61    edge_metadata: Option<Vec<DemProgramEdgeMetadata>>,
62    location_catalog: LocationCatalog,
63    location_groups: Vec<DemProgramLocationGroup>,
64    hotspot_layout_identity: Arc<()>,
65}
66
67#[derive(Debug, Clone, PartialEq)]
68pub struct PackedDemShotBatch {
69    pub shots: usize,
70    pub detector_data: Vec<u8>,
71    pub detector_byte_count: usize,
72    pub observable_ids: Vec<i64>,
73    pub observable_data: Vec<u8>,
74    pub observable_byte_count: usize,
75}
76
77#[derive(Debug, Clone, PartialEq)]
78pub struct DetectorEventDemShotBatch {
79    pub shots: usize,
80    pub offsets: Vec<usize>,
81    pub events: Vec<usize>,
82    pub observable_ids: Vec<i64>,
83    pub observable_data: Vec<u8>,
84    pub observable_byte_count: usize,
85}
86
87/// Read-only edge-event data used only by FaultScope's attribution pipeline.
88#[derive(Debug, Clone, PartialEq)]
89pub struct DemAttributionTrace {
90    shots: usize,
91    edge_event_masks: Vec<Mask>,
92    sampler_identity: Arc<()>,
93}
94
95impl DemAttributionTrace {
96    pub fn shots(&self) -> usize {
97        self.shots
98    }
99
100    pub fn edge_event_masks(&self) -> &[Mask] {
101        &self.edge_event_masks
102    }
103
104    fn matches_sampler(&self, identity: &Arc<()>) -> bool {
105        Arc::ptr_eq(&self.sampler_identity, identity)
106    }
107}
108
109/// Observable truth in the layout fixed by the negotiated detector input format.
110#[derive(Debug, Clone, PartialEq)]
111pub enum DemObservableBatch {
112    Masks(CorrectionMaskBatch),
113    Packed(PackedObservableShotBatch),
114}
115
116impl DemObservableBatch {
117    pub fn observable_ids(&self) -> &[i64] {
118        match self {
119            Self::Masks(batch) => &batch.observable_ids,
120            Self::Packed(batch) => &batch.observable_ids,
121        }
122    }
123
124    pub fn shots(&self) -> usize {
125        match self {
126            Self::Masks(batch) => batch.shots,
127            Self::Packed(batch) => batch.shots,
128        }
129    }
130
131    pub fn as_masks(&self) -> NpResult<CorrectionMaskBatch> {
132        match self {
133            Self::Masks(batch) => Ok(batch.clone()),
134            Self::Packed(batch) => packed_corrections_to_masks(batch.clone()),
135        }
136    }
137
138    pub fn as_packed(&self) -> NpResult<PackedObservableShotBatch> {
139        match self {
140            Self::Masks(batch) => crate::mask_corrections_to_packed(batch.clone()),
141            Self::Packed(batch) => Ok(batch.clone()),
142        }
143    }
144}
145
146/// Cross-crate result of one negotiated DEM sampling pass.
147#[derive(Debug, Clone, PartialEq)]
148pub struct DemSamplingResult {
149    syndrome: DetectorBatch,
150    observables: DemObservableBatch,
151    detail_detector_ids: Vec<i64>,
152    detail_detector_masks: Vec<Mask>,
153    all_mask: Mask,
154    attribution: Option<DemAttributionTrace>,
155    sampler_identity: Arc<()>,
156}
157
158impl DemSamplingResult {
159    pub fn shots(&self) -> usize {
160        self.syndrome.shots()
161    }
162
163    pub fn syndrome(&self) -> DetectorBatchView<'_> {
164        self.syndrome.view()
165    }
166
167    pub fn syndrome_batch(&self) -> &DetectorBatch {
168        &self.syndrome
169    }
170
171    pub fn observables(&self) -> &DemObservableBatch {
172        &self.observables
173    }
174
175    pub fn detail_detector_ids(&self) -> &[i64] {
176        &self.detail_detector_ids
177    }
178
179    pub fn detail_detector_masks(&self) -> &[Mask] {
180        &self.detail_detector_masks
181    }
182
183    pub fn detector_detail_mask(&self, detector_id: i64) -> Option<&Mask> {
184        self.detail_detector_ids
185            .iter()
186            .position(|id| *id == detector_id)
187            .and_then(|index| self.detail_detector_masks.get(index))
188    }
189
190    pub fn all_mask(&self) -> &Mask {
191        &self.all_mask
192    }
193
194    pub fn attribution(&self) -> Option<&DemAttributionTrace> {
195        self.attribution.as_ref()
196    }
197
198    pub fn into_dem_batch(self) -> NpResult<DemBatch> {
199        let masks = convert_detector_batch(self.syndrome.view(), DetectorBatchFormat::Masks)?;
200        let DetectorBatch::Masks {
201            detector_ids,
202            masks,
203            shots,
204        } = masks
205        else {
206            unreachable!("Masks conversion returns Masks storage")
207        };
208        let detectors = detector_ids.into_iter().zip(masks).collect();
209        let observable_masks = self.observables.as_masks()?;
210        let observables = observable_masks
211            .observable_ids
212            .into_iter()
213            .zip(observable_masks.masks)
214            .collect::<HashMap<_, _>>();
215        let mut loss_mask = Mask::zero(word_count(shots));
216        for observable in observables.values() {
217            loss_mask.or_assign(observable);
218        }
219        loss_mask.and_assign(&self.all_mask);
220        Ok(DemBatch::new(
221            shots,
222            self.all_mask,
223            detectors,
224            observables,
225            self.attribution.map(|trace| trace.edge_event_masks),
226            loss_mask,
227            self.sampler_identity,
228        ))
229    }
230}
231
232/// Precomputed detector and observable layouts for repeated DEM sampling.
233///
234/// The plan is immutable and independent of [`DemHotspotEstimator`], so it
235/// remains valid even when callers mutate the estimator's public fields.
236#[derive(Debug, Clone, PartialEq)]
237pub struct CompiledDemSamplingPlan {
238    detector_ids: Vec<i64>,
239    observable_ids: Vec<i64>,
240    format: DetectorBatchFormat,
241    detail_detector_ids: Vec<i64>,
242    record_attribution: bool,
243    sampler_identity: Arc<()>,
244    edges: Vec<CompiledSamplingEdge>,
245    detector_byte_count: usize,
246    observable_byte_count: usize,
247}
248
249#[derive(Debug, Clone, PartialEq)]
250struct CompiledSamplingEdge {
251    probability: f64,
252    detector_columns: Vec<usize>,
253    packed_detector_columns: Vec<(usize, u8)>,
254    detail_detector_columns: Vec<usize>,
255    observable_mask_columns: Vec<usize>,
256    observable_columns: Vec<(usize, u8)>,
257}
258
259/// Precomputed observable layout for counting logical failures without a decoder.
260#[derive(Debug, Clone, PartialEq)]
261pub struct CompiledDemLogicalCountPlan {
262    observable_ids: Vec<i64>,
263    edges: Vec<CompiledLogicalCountEdge>,
264    single_observable_flip_edge_count: usize,
265}
266
267#[derive(Debug, Clone, PartialEq)]
268struct CompiledLogicalCountEdge {
269    probability: f64,
270    observable_columns: Vec<usize>,
271    single_observable_flip: bool,
272}
273
274impl DemHotspotEstimator {
275    pub(crate) fn from_compact_sampling_parts(
276        detector_ids: Vec<i64>,
277        observable_ids: Vec<i64>,
278        edges: Vec<DemProgramEdge>,
279    ) -> Self {
280        let (detector_ids, observable_ids, edges) =
281            canonicalize_program_parts(detector_ids, observable_ids, edges)
282                .expect("generated DEM declarations must have unique ids");
283        Self {
284            canonical_detector_ids: Arc::from(detector_ids.as_slice()),
285            canonical_observable_ids: Arc::from(observable_ids.as_slice()),
286            detector_ids,
287            observable_ids,
288            edges,
289            edge_metadata: None,
290            location_catalog: LocationCatalog::default(),
291            location_groups: Vec::new(),
292            hotspot_layout_identity: Arc::new(()),
293        }
294    }
295
296    pub(crate) fn from_program_parts(
297        detector_ids: Vec<i64>,
298        observable_ids: Vec<i64>,
299        edges: Vec<DemProgramEdge>,
300        edge_metadata: Vec<DemProgramEdgeMetadata>,
301        location_catalog: LocationCatalog,
302    ) -> Self {
303        debug_assert_eq!(edges.len(), edge_metadata.len());
304        let (detector_ids, observable_ids, edges) =
305            canonicalize_program_parts(detector_ids, observable_ids, edges)
306                .expect("generated DEM declarations must have unique ids");
307        let location_groups =
308            build_dem_program_location_groups(&edges, &edge_metadata, location_catalog.len());
309        Self {
310            canonical_detector_ids: Arc::from(detector_ids.as_slice()),
311            canonical_observable_ids: Arc::from(observable_ids.as_slice()),
312            detector_ids,
313            observable_ids,
314            edges,
315            edge_metadata: Some(edge_metadata),
316            location_catalog,
317            location_groups,
318            hotspot_layout_identity: Arc::new(()),
319        }
320    }
321
322    /// Build a simulator from a typed detector error model.
323    pub fn new(dem: DetectorErrorModel) -> NpResult<Self> {
324        let detector_ids = dem.detectors.iter().map(|detector| detector.id).collect();
325        let observable_ids = dem
326            .observables
327            .iter()
328            .map(|observable| observable.id)
329            .collect();
330        Self::from_parts(detector_ids, observable_ids, dem.edges)
331    }
332
333    /// Build a simulator from pre-extracted ids and sampler edges.
334    pub fn from_parts(
335        detector_ids: Vec<i64>,
336        observable_ids: Vec<i64>,
337        edges: Vec<DetectorErrorEdge>,
338    ) -> NpResult<Self> {
339        let compiled = compile_dem_edges(edges, true)?;
340        let (detector_ids, observable_ids, edges) =
341            canonicalize_program_parts(detector_ids, observable_ids, compiled.edges)?;
342        Ok(Self {
343            canonical_detector_ids: Arc::from(detector_ids.as_slice()),
344            canonical_observable_ids: Arc::from(observable_ids.as_slice()),
345            detector_ids,
346            observable_ids,
347            edges,
348            edge_metadata: compiled.metadata,
349            location_catalog: compiled.catalog,
350            location_groups: compiled.location_groups,
351            hotspot_layout_identity: Arc::new(()),
352        })
353    }
354
355    /// Build a simulator for sampling only, without hotspot location metadata.
356    pub fn from_sampling_parts(
357        detector_ids: Vec<i64>,
358        observable_ids: Vec<i64>,
359        edges: Vec<DetectorErrorEdge>,
360    ) -> NpResult<Self> {
361        let compiled = compile_dem_edges(edges, false)?;
362        debug_assert!(compiled.metadata.is_none());
363        debug_assert!(compiled.catalog.is_empty());
364        let (detector_ids, observable_ids, edges) =
365            canonicalize_program_parts(detector_ids, observable_ids, compiled.edges)?;
366        Ok(Self {
367            canonical_detector_ids: Arc::from(detector_ids.as_slice()),
368            canonical_observable_ids: Arc::from(observable_ids.as_slice()),
369            detector_ids,
370            observable_ids,
371            edges,
372            edge_metadata: None,
373            location_catalog: LocationCatalog::default(),
374            location_groups: Vec::new(),
375            hotspot_layout_identity: Arc::new(()),
376        })
377    }
378
379    /// Number of compiled DEM edges.
380    pub fn edge_count(&self) -> usize {
381        self.edges.len()
382    }
383
384    /// Detector IDs in the immutable canonical sampling order.
385    pub fn detector_ids(&self) -> &[i64] {
386        self.canonical_detector_ids.as_ref()
387    }
388
389    /// Observable IDs in the immutable canonical sampling order.
390    pub fn observable_ids(&self) -> &[i64] {
391        self.canonical_observable_ids.as_ref()
392    }
393
394    /// Materialize one user-facing DEM edge at the output boundary.
395    pub fn edge(&self, edge_index: usize) -> Option<DetectorErrorEdge> {
396        self.edges.get(edge_index).map(|edge| {
397            materialize_dem_edge(
398                edge,
399                self.edge_metadata
400                    .as_ref()
401                    .and_then(|metadata| metadata.get(edge_index)),
402                &self.location_catalog,
403            )
404        })
405    }
406
407    /// Materialize all user-facing DEM edges at the output boundary.
408    pub fn edges(&self) -> Vec<DetectorErrorEdge> {
409        self.edges
410            .iter()
411            .enumerate()
412            .map(|(edge_index, edge)| {
413                materialize_dem_edge(
414                    edge,
415                    self.edge_metadata
416                        .as_ref()
417                        .and_then(|metadata| metadata.get(edge_index)),
418                    &self.location_catalog,
419                )
420            })
421            .collect()
422    }
423
424    /// Materialize grouped location metadata at the output boundary.
425    pub fn location_groups(&self) -> Vec<DemLocationGroup> {
426        self.location_groups
427            .iter()
428            .map(|group| DemLocationGroup {
429                location_id: self.location_catalog.label(group.location_id).to_string(),
430                edge_indices: group.edge_indices.clone(),
431                total_probability: group.total_probability,
432            })
433            .collect()
434    }
435
436    /// Run DEM sampling for `shots`.
437    pub fn run_batch(
438        &self,
439        shots: usize,
440        seed: Option<u64>,
441        return_edge_events: bool,
442    ) -> NpResult<DemBatch> {
443        if shots == 0 {
444            return Err(NpError::new("shots must be positive"));
445        }
446        let mut rng = SmallRng::new(seed.unwrap_or(0x95f2_04dc_4291_a715));
447        Ok(self.run_batch_with_rng(shots, &mut rng, return_edge_events))
448    }
449
450    /// Run DEM sampling with a caller-owned core RNG.
451    pub fn run_batch_with_rng(
452        &self,
453        shots: usize,
454        rng: &mut SmallRng,
455        return_edge_events: bool,
456    ) -> DemBatch {
457        self.compile_decoder_sampling_plan(
458            self.detector_ids(),
459            self.observable_ids(),
460            DetectorBatchFormat::Masks,
461            &[],
462            return_edge_events,
463        )
464        .expect("canonical DEM layouts compile")
465        .run_sampling_result_with_rng(shots, rng)
466        .expect("canonical DEM sampling cannot fail")
467        .into_dem_batch()
468        .expect("canonical DEM batches materialize")
469    }
470
471    pub fn run_packed_shot_batch_with_rng(
472        &self,
473        shots: usize,
474        rng: &mut SmallRng,
475        detector_ids: &[i64],
476        observable_ids: &[i64],
477    ) -> NpResult<PackedDemShotBatch> {
478        Ok(self
479            .compile_sampling_plan(detector_ids, observable_ids)?
480            .run_packed_shot_batch_with_rng(shots, rng))
481    }
482
483    pub fn run_detector_event_shot_batch_with_rng(
484        &self,
485        shots: usize,
486        rng: &mut SmallRng,
487        detector_ids: &[i64],
488        observable_ids: &[i64],
489    ) -> NpResult<DetectorEventDemShotBatch> {
490        Ok(compile_dem_sampling_plan(DemSamplingPlanSpec {
491            sampling_detector_ids: self.detector_ids(),
492            sampling_observable_ids: self.observable_ids(),
493            edges: &self.edges,
494            detector_ids,
495            observable_ids,
496            format: DetectorBatchFormat::Events,
497            detail_detector_ids: &[],
498            record_attribution: false,
499            sampler_identity: &self.hotspot_layout_identity,
500            sampler_name: "detector-event DEM sampler",
501        })?
502        .run_detector_event_shot_batch_with_rng(shots, rng))
503    }
504
505    /// Compile detector and observable layouts for repeated packed DEM batches.
506    pub fn compile_sampling_plan(
507        &self,
508        detector_ids: &[i64],
509        observable_ids: &[i64],
510    ) -> NpResult<CompiledDemSamplingPlan> {
511        compile_dem_sampling_plan(DemSamplingPlanSpec {
512            sampling_detector_ids: self.detector_ids(),
513            sampling_observable_ids: self.observable_ids(),
514            edges: &self.edges,
515            detector_ids,
516            observable_ids,
517            format: DetectorBatchFormat::Packed,
518            detail_detector_ids: &[],
519            record_attribution: false,
520            sampler_identity: &self.hotspot_layout_identity,
521            sampler_name: "packed DEM sampler",
522        })
523    }
524
525    /// Compile one decoder-oriented sampling plan with optional detail and attribution sidecars.
526    pub fn compile_decoder_sampling_plan(
527        &self,
528        detector_ids: &[i64],
529        observable_ids: &[i64],
530        format: DetectorBatchFormat,
531        detail_detector_ids: &[i64],
532        record_attribution: bool,
533    ) -> NpResult<CompiledDemSamplingPlan> {
534        compile_dem_sampling_plan(DemSamplingPlanSpec {
535            sampling_detector_ids: self.detector_ids(),
536            sampling_observable_ids: self.observable_ids(),
537            edges: &self.edges,
538            detector_ids,
539            observable_ids,
540            format,
541            detail_detector_ids,
542            record_attribution,
543            sampler_identity: &self.hotspot_layout_identity,
544            sampler_name: "decoder DEM sampler",
545        })
546    }
547
548    /// Compile the observable-only path used to count default logical failures.
549    pub fn compile_logical_count_plan(&self) -> CompiledDemLogicalCountPlan {
550        CompiledDemLogicalCountPlan::new(self.observable_ids(), &self.edges)
551    }
552
553    /// Run a batch and estimate hotspots using the default logical loss mask.
554    pub fn estimate_default(
555        &self,
556        shots: usize,
557        seed: Option<u64>,
558        baseline: Option<f64>,
559        top_k: usize,
560    ) -> NpResult<DemHotspotEstimate> {
561        let batch = self.run_batch(shots, seed, true)?;
562        self.estimate_from_loss(&batch, &batch.loss_mask, baseline, top_k)
563    }
564
565    /// Estimate hotspots from an externally supplied loss mask.
566    ///
567    /// The batch must come from this estimator (or one of its clones) and must
568    /// have edge-event recording enabled.
569    pub fn estimate_from_loss(
570        &self,
571        batch: &DemBatch,
572        loss_mask: &Mask,
573        baseline: Option<f64>,
574        top_k: usize,
575    ) -> NpResult<DemHotspotEstimate> {
576        if !batch.matches_hotspot_layout(&self.hotspot_layout_identity) {
577            return Err(NpError::new(
578                "hotspot batch layout does not match the current DEM estimator",
579            ));
580        }
581        if batch.shots() == 0 {
582            return Err(NpError::new(
583                "DEM hotspot estimation requires shots to be positive",
584            ));
585        }
586        if !batch.records_edge_events() {
587            return Err(NpError::new(
588                "DEM hotspot estimation requires recorded event masks",
589            ));
590        }
591        crate::hotspot::validate_loss_mask_width("DEM hotspot", batch.shots(), loss_mask)?;
592        Ok(crate::hotspot::compute_dem_estimate(
593            crate::hotspot::DemEstimateProgram {
594                edges: &self.edges,
595                edge_metadata: self.edge_metadata.as_deref().unwrap_or(&[]),
596                location_groups: &self.location_groups,
597                catalog: &self.location_catalog,
598            },
599            batch,
600            loss_mask,
601            baseline,
602            top_k,
603        ))
604    }
605
606    /// Estimate hotspots from the attribution sidecar produced by a negotiated sampler plan.
607    pub fn estimate_from_attribution(
608        &self,
609        trace: &DemAttributionTrace,
610        loss_mask: &Mask,
611        baseline: Option<f64>,
612        top_k: usize,
613    ) -> NpResult<DemHotspotEstimate> {
614        if !trace.matches_sampler(&self.hotspot_layout_identity) {
615            return Err(NpError::new(
616                "hotspot attribution trace does not match the current DEM estimator",
617            ));
618        }
619        if trace.shots == 0 {
620            return Err(NpError::new(
621                "DEM hotspot estimation requires shots to be positive",
622            ));
623        }
624        if trace.edge_event_masks.len() != self.edges.len() {
625            return Err(NpError::new(format!(
626                "hotspot attribution trace has {} edge masks; expected {}",
627                trace.edge_event_masks.len(),
628                self.edges.len()
629            )));
630        }
631        crate::hotspot::validate_loss_mask_width("DEM hotspot", trace.shots, loss_mask)?;
632        let all_mask = Mask::all(trace.shots);
633        Ok(crate::hotspot::compute_dem_estimate_from_trace(
634            crate::hotspot::DemEstimateProgram {
635                edges: &self.edges,
636                edge_metadata: self.edge_metadata.as_deref().unwrap_or(&[]),
637                location_groups: &self.location_groups,
638                catalog: &self.location_catalog,
639            },
640            trace.shots,
641            &all_mask,
642            &trace.edge_event_masks,
643            loss_mask,
644            baseline,
645            top_k,
646        ))
647    }
648}
649
650struct DemSamplingPlanSpec<'a> {
651    sampling_detector_ids: &'a [i64],
652    sampling_observable_ids: &'a [i64],
653    edges: &'a [DemProgramEdge],
654    detector_ids: &'a [i64],
655    observable_ids: &'a [i64],
656    format: DetectorBatchFormat,
657    detail_detector_ids: &'a [i64],
658    record_attribution: bool,
659    sampler_identity: &'a Arc<()>,
660    sampler_name: &'a str,
661}
662
663fn compile_dem_sampling_plan(spec: DemSamplingPlanSpec<'_>) -> NpResult<CompiledDemSamplingPlan> {
664    let DemSamplingPlanSpec {
665        sampling_detector_ids,
666        sampling_observable_ids,
667        edges,
668        detector_ids,
669        observable_ids,
670        format,
671        detail_detector_ids,
672        record_attribution,
673        sampler_identity,
674        sampler_name,
675    } = spec;
676    validate_decoder_detector_ids(detector_ids)?;
677    validate_decoder_detector_ids(detail_detector_ids)?;
678    validate_decoder_observable_ids(observable_ids)?;
679    let sampling_detector_index = sampling_detector_ids
680        .iter()
681        .copied()
682        .enumerate()
683        .map(|(index, id)| (id, index))
684        .collect::<HashMap<_, _>>();
685    for detector_id in detector_ids {
686        if !sampling_detector_index.contains_key(detector_id) {
687            return Err(NpError::new(format!(
688                "{sampler_name} requested detector id {detector_id}, but it is not declared by the DEM"
689            )));
690        }
691    }
692    for detector_id in detail_detector_ids {
693        if !sampling_detector_index.contains_key(detector_id) {
694            return Err(NpError::new(format!(
695                "{sampler_name} requested detail detector id {detector_id}, but it is not declared by the DEM"
696            )));
697        }
698    }
699    let detector_index = detector_ids
700        .iter()
701        .copied()
702        .enumerate()
703        .map(|(index, id)| (id, index))
704        .collect::<HashMap<_, _>>();
705    let detail_detector_index = detail_detector_ids
706        .iter()
707        .copied()
708        .enumerate()
709        .map(|(index, id)| (id, index))
710        .collect::<HashMap<_, _>>();
711
712    let sampling_observable_index = sampling_observable_ids
713        .iter()
714        .copied()
715        .enumerate()
716        .map(|(index, id)| (id, index))
717        .collect::<HashMap<_, _>>();
718    for observable_id in observable_ids {
719        if !sampling_observable_index.contains_key(observable_id) {
720            return Err(NpError::new(format!(
721                "{sampler_name} requested observable id {observable_id}, but it is not declared by the DEM"
722            )));
723        }
724    }
725    let observable_index = observable_ids
726        .iter()
727        .copied()
728        .enumerate()
729        .map(|(index, id)| (id, index))
730        .collect::<HashMap<_, _>>();
731
732    let compiled_edges = edges
733        .iter()
734        .map(|edge| {
735            let detector_columns = edge
736                .detectors
737                .iter()
738                .filter_map(|detector_id| detector_index.get(detector_id).copied())
739                .collect::<Vec<_>>();
740            let packed_detector_columns = detector_columns
741                .iter()
742                .map(|column| (column >> 3, 1u8 << (column & 7)))
743                .collect();
744            let detail_detector_columns = edge
745                .detectors
746                .iter()
747                .filter_map(|detector_id| detail_detector_index.get(detector_id).copied())
748                .collect();
749            let mut observable_mask_columns = Vec::with_capacity(edge.observables.len());
750            let mut observable_columns = Vec::with_capacity(edge.observables.len());
751            for observable_id in &edge.observables {
752                let column = packed_column_for_id(*observable_id, &observable_index)?;
753                observable_mask_columns.push(column);
754                observable_columns.push((column >> 3, 1u8 << (column & 7)));
755            }
756            Ok(CompiledSamplingEdge {
757                probability: edge.probability,
758                detector_columns,
759                packed_detector_columns,
760                detail_detector_columns,
761                observable_mask_columns,
762                observable_columns,
763            })
764        })
765        .collect::<NpResult<Vec<_>>>()?;
766
767    Ok(CompiledDemSamplingPlan {
768        detector_ids: detector_ids.to_vec(),
769        observable_ids: observable_ids.to_vec(),
770        format,
771        detail_detector_ids: detail_detector_ids.to_vec(),
772        record_attribution,
773        sampler_identity: sampler_identity.clone(),
774        edges: compiled_edges,
775        detector_byte_count: detector_ids.len().div_ceil(8),
776        observable_byte_count: observable_ids.len().div_ceil(8),
777    })
778}
779
780impl CompiledDemSamplingPlan {
781    /// Detector ids in the packed output order.
782    pub fn detector_ids(&self) -> &[i64] {
783        &self.detector_ids
784    }
785
786    /// Observable ids in the packed output order.
787    pub fn observable_ids(&self) -> &[i64] {
788        &self.observable_ids
789    }
790
791    pub fn format(&self) -> DetectorBatchFormat {
792        self.format
793    }
794
795    pub fn detail_detector_ids(&self) -> &[i64] {
796        &self.detail_detector_ids
797    }
798
799    pub fn records_attribution(&self) -> bool {
800        self.record_attribution
801    }
802
803    /// Sample syndrome, observable truth, optional detector detail, and an optional
804    /// attribution trace in a single RNG pass.
805    pub fn run_sampling_result_with_rng(
806        &self,
807        shots: usize,
808        rng: &mut SmallRng,
809    ) -> NpResult<DemSamplingResult> {
810        let words = word_count(shots);
811        let detector_len = shots
812            .checked_mul(self.detector_byte_count)
813            .ok_or_else(|| NpError::new("DEM detector batch length overflowed usize"))?;
814        let observable_len = shots
815            .checked_mul(self.observable_byte_count)
816            .ok_or_else(|| NpError::new("DEM observable batch length overflowed usize"))?;
817
818        let mut detector_masks = (self.format == DetectorBatchFormat::Masks)
819            .then(|| vec![Mask::zero(words); self.detector_ids.len()]);
820        let mut detector_data =
821            (self.format == DetectorBatchFormat::Packed).then(|| vec![0u8; detector_len]);
822        let mut event_counts =
823            (self.format == DetectorBatchFormat::Events).then(|| vec![0usize; shots]);
824        let mut raw_events = Vec::<(usize, usize)>::new();
825
826        let mut observable_masks = (self.format == DetectorBatchFormat::Masks)
827            .then(|| vec![Mask::zero(words); self.observable_ids.len()]);
828        let mut observable_data =
829            (self.format != DetectorBatchFormat::Masks).then(|| vec![0u8; observable_len]);
830        let mut detail_detector_masks = vec![Mask::zero(words); self.detail_detector_ids.len()];
831        let mut trace_masks = self
832            .record_attribution
833            .then(|| Vec::with_capacity(self.edges.len()));
834        let mut count_overflowed = false;
835
836        for edge in &self.edges {
837            let mut trace_mask = self.record_attribution.then(|| Mask::zero(words));
838            for_each_bernoulli_event(rng, shots, edge.probability, |shot, _| {
839                let shot_word = shot >> 6;
840                let shot_bit = 1u64 << (shot & 63);
841                if let Some(mask) = &mut trace_mask {
842                    mask.words[shot_word] |= shot_bit;
843                }
844                if let Some(masks) = &mut detector_masks {
845                    for detector in &edge.detector_columns {
846                        masks[*detector].words[shot_word] ^= shot_bit;
847                    }
848                } else if let Some(data) = &mut detector_data {
849                    let row = shot * self.detector_byte_count;
850                    for (byte, bit) in &edge.packed_detector_columns {
851                        data[row + byte] ^= bit;
852                    }
853                } else if let Some(counts) = &mut event_counts {
854                    match counts[shot].checked_add(edge.detector_columns.len()) {
855                        Some(count) => counts[shot] = count,
856                        None => count_overflowed = true,
857                    }
858                    raw_events.extend(
859                        edge.detector_columns
860                            .iter()
861                            .copied()
862                            .map(|detector| (shot, detector)),
863                    );
864                }
865
866                if let Some(masks) = &mut observable_masks {
867                    for observable in &edge.observable_mask_columns {
868                        masks[*observable].words[shot_word] ^= shot_bit;
869                    }
870                } else if let Some(data) = &mut observable_data {
871                    let row = shot * self.observable_byte_count;
872                    for (byte, bit) in &edge.observable_columns {
873                        data[row + byte] ^= bit;
874                    }
875                }
876                for detector in &edge.detail_detector_columns {
877                    detail_detector_masks[*detector].words[shot_word] ^= shot_bit;
878                }
879            });
880            if let (Some(masks), Some(mask)) = (&mut trace_masks, trace_mask) {
881                masks.push(mask);
882            }
883        }
884        if count_overflowed {
885            return Err(NpError::new("DEM detector event count overflowed usize"));
886        }
887
888        let syndrome = match self.format {
889            DetectorBatchFormat::Masks => DetectorBatch::Masks {
890                detector_ids: self.detector_ids.clone(),
891                masks: detector_masks.expect("Masks plan allocates mask-major syndrome"),
892                shots,
893            },
894            DetectorBatchFormat::Packed => DetectorBatch::Packed {
895                detector_ids: self.detector_ids.clone(),
896                data: detector_data.expect("Packed plan allocates packed syndrome"),
897                shots,
898                detector_byte_count: self.detector_byte_count,
899            },
900            DetectorBatchFormat::Events => {
901                let counts = event_counts.expect("Events plan allocates event counts");
902                let mut offsets = crate::decoder::empty_detector_event_offsets(shots)?;
903                for count in counts {
904                    let next = offsets
905                        .last()
906                        .copied()
907                        .expect("offset zero is present")
908                        .checked_add(count)
909                        .ok_or_else(|| {
910                            NpError::new("DEM detector event offset overflowed usize")
911                        })?;
912                    offsets.push(next);
913                }
914                let mut events = vec![0usize; offsets.last().copied().unwrap_or(0)];
915                let mut next = offsets.clone();
916                for (shot, detector) in raw_events {
917                    events[next[shot]] = detector;
918                    next[shot] += 1;
919                }
920                DetectorBatch::Events {
921                    detector_ids: self.detector_ids.clone(),
922                    offsets,
923                    events,
924                    shots,
925                }
926            }
927        };
928        syndrome.validate_shape()?;
929
930        let observables = if self.format == DetectorBatchFormat::Masks {
931            DemObservableBatch::Masks(CorrectionMaskBatch::new(
932                self.observable_ids.clone(),
933                observable_masks.expect("Masks plan allocates mask-major observables"),
934                shots,
935            )?)
936        } else {
937            DemObservableBatch::Packed(PackedObservableShotBatch::new(
938                self.observable_ids.clone(),
939                observable_data.expect("non-Masks plan allocates packed observables"),
940                shots,
941            )?)
942        };
943        let all_mask = Mask::all(shots);
944        let attribution = trace_masks.map(|edge_event_masks| DemAttributionTrace {
945            shots,
946            edge_event_masks,
947            sampler_identity: self.sampler_identity.clone(),
948        });
949        Ok(DemSamplingResult {
950            syndrome,
951            observables,
952            detail_detector_ids: self.detail_detector_ids.clone(),
953            detail_detector_masks,
954            all_mask,
955            attribution,
956            sampler_identity: self.sampler_identity.clone(),
957        })
958    }
959
960    /// Sample a shot-major bit-packed detector and observable batch.
961    pub fn run_packed_shot_batch_with_rng(
962        &self,
963        shots: usize,
964        rng: &mut SmallRng,
965    ) -> PackedDemShotBatch {
966        let mut detector_data = vec![0; shots * self.detector_byte_count];
967        let mut observable_data = vec![0; shots * self.observable_byte_count];
968
969        for columns in &self.edges {
970            for_each_bernoulli_event(rng, shots, columns.probability, |shot, _| {
971                let detector_row = shot * self.detector_byte_count;
972                for (byte_index, bit_mask) in &columns.packed_detector_columns {
973                    detector_data[detector_row + byte_index] ^= bit_mask;
974                }
975                let observable_row = shot * self.observable_byte_count;
976                for (byte_index, bit_mask) in &columns.observable_columns {
977                    observable_data[observable_row + byte_index] ^= bit_mask;
978                }
979            });
980        }
981
982        PackedDemShotBatch {
983            shots,
984            detector_data,
985            detector_byte_count: self.detector_byte_count,
986            observable_ids: self.observable_ids.clone(),
987            observable_data,
988            observable_byte_count: self.observable_byte_count,
989        }
990    }
991
992    /// Sample a detector-event batch using the precomputed detector indices.
993    pub fn run_detector_event_shot_batch_with_rng(
994        &self,
995        shots: usize,
996        rng: &mut SmallRng,
997    ) -> DetectorEventDemShotBatch {
998        let mut observable_data = vec![0; shots * self.observable_byte_count];
999        let mut event_counts = vec![0usize; shots];
1000        let mut raw_events = Vec::<(usize, usize)>::new();
1001
1002        for columns in &self.edges {
1003            for_each_bernoulli_event(rng, shots, columns.probability, |shot, _| {
1004                event_counts[shot] += columns.detector_columns.len();
1005                raw_events.extend(
1006                    columns
1007                        .detector_columns
1008                        .iter()
1009                        .copied()
1010                        .map(|detector| (shot, detector)),
1011                );
1012                let observable_row = shot * self.observable_byte_count;
1013                for (byte_index, bit_mask) in &columns.observable_columns {
1014                    observable_data[observable_row + byte_index] ^= bit_mask;
1015                }
1016            });
1017        }
1018
1019        let mut offsets = Vec::with_capacity(shots + 1);
1020        offsets.push(0);
1021        for count in event_counts {
1022            offsets.push(offsets.last().copied().unwrap_or(0) + count);
1023        }
1024
1025        let mut events = vec![0usize; offsets.last().copied().unwrap_or(0)];
1026        let mut next = offsets.clone();
1027        for (shot, detector) in raw_events {
1028            let index = next[shot];
1029            events[index] = detector;
1030            next[shot] += 1;
1031        }
1032
1033        DetectorEventDemShotBatch {
1034            shots,
1035            offsets,
1036            events,
1037            observable_ids: self.observable_ids.clone(),
1038            observable_data,
1039            observable_byte_count: self.observable_byte_count,
1040        }
1041    }
1042}
1043
1044impl CompiledDemLogicalCountPlan {
1045    fn new(observable_ids: &[i64], edges: &[DemProgramEdge]) -> Self {
1046        let compiled_observable_ids = observable_ids.to_vec();
1047        let observable_index = id_index(observable_ids);
1048        let compiled_edges = edges
1049            .iter()
1050            .map(|edge| {
1051                let observable_columns = edge
1052                    .observables
1053                    .iter()
1054                    .map(|observable_id| {
1055                        *observable_index
1056                            .get(observable_id)
1057                            .expect("canonical DEM layout must include every edge observable")
1058                    })
1059                    .collect::<Vec<_>>();
1060                let single_observable_flip = observable_columns
1061                    .iter()
1062                    .filter(|column| **column == 0)
1063                    .count()
1064                    % 2
1065                    != 0;
1066                CompiledLogicalCountEdge {
1067                    probability: edge.probability,
1068                    observable_columns,
1069                    single_observable_flip,
1070                }
1071            })
1072            .collect::<Vec<_>>();
1073        let single_observable_flip_edge_count = compiled_edges
1074            .iter()
1075            .filter(|edge| edge.single_observable_flip)
1076            .count();
1077        Self {
1078            observable_ids: compiled_observable_ids,
1079            edges: compiled_edges,
1080            single_observable_flip_edge_count,
1081        }
1082    }
1083
1084    /// Observable ids included in the default logical loss mask.
1085    pub fn observable_ids(&self) -> &[i64] {
1086        &self.observable_ids
1087    }
1088
1089    /// Count shots where at least one logical observable is set.
1090    pub fn sample_logical_error_count_with_rng(&self, shots: usize, rng: &mut SmallRng) -> usize {
1091        if self.observable_ids.len() == 1 {
1092            return self.sample_single_observable_count(shots, rng);
1093        }
1094        let words = word_count(shots);
1095        let mut observable_words = vec![0u64; self.observable_ids.len() * words];
1096        let mut event_words = vec![0u64; words];
1097
1098        for edge in &self.edges {
1099            fill_bernoulli_words(&mut event_words, shots, edge.probability, rng);
1100            for observable_column in &edge.observable_columns {
1101                let start = observable_column * words;
1102                for (observable, event) in observable_words[start..start + words]
1103                    .iter_mut()
1104                    .zip(&event_words)
1105                {
1106                    *observable ^= event;
1107                }
1108            }
1109        }
1110
1111        (0..words)
1112            .map(|word| {
1113                (0..self.observable_ids.len())
1114                    .fold(0u64, |loss, observable| {
1115                        loss | observable_words[observable * words + word]
1116                    })
1117                    .count_ones() as usize
1118            })
1119            .sum()
1120    }
1121
1122    fn sample_single_observable_count(&self, shots: usize, rng: &mut SmallRng) -> usize {
1123        if self.single_observable_flip_edge_count <= 1 {
1124            let mut errors = 0usize;
1125            for edge in &self.edges {
1126                if edge.probability <= 0.0 {
1127                    continue;
1128                }
1129                if edge.probability >= 1.0 {
1130                    if edge.single_observable_flip {
1131                        errors += shots;
1132                    }
1133                    continue;
1134                }
1135                if edge.single_observable_flip {
1136                    for_each_bernoulli_event(rng, shots, edge.probability, |_, _| errors += 1);
1137                } else {
1138                    for_each_bernoulli_event(rng, shots, edge.probability, |_, _| {});
1139                }
1140            }
1141            return errors;
1142        }
1143
1144        const STACK_WORDS: usize = 8;
1145        let words = word_count(shots);
1146        if words <= STACK_WORDS {
1147            let mut logical_words = [0u64; STACK_WORDS];
1148            sample_single_observable_words(&self.edges, shots, rng, &mut logical_words[..words]);
1149            logical_words[..words]
1150                .iter()
1151                .map(|word| word.count_ones() as usize)
1152                .sum()
1153        } else {
1154            let mut logical_words = vec![0u64; words];
1155            sample_single_observable_words(&self.edges, shots, rng, &mut logical_words);
1156            logical_words
1157                .iter()
1158                .map(|word| word.count_ones() as usize)
1159                .sum()
1160        }
1161    }
1162}
1163
1164fn sample_single_observable_words(
1165    edges: &[CompiledLogicalCountEdge],
1166    shots: usize,
1167    rng: &mut SmallRng,
1168    logical_words: &mut [u64],
1169) {
1170    for edge in edges {
1171        if edge.probability <= 0.0 {
1172            continue;
1173        }
1174        if edge.probability >= 1.0 {
1175            if edge.single_observable_flip {
1176                for word in logical_words.iter_mut() {
1177                    *word ^= u64::MAX;
1178                }
1179                let remainder = shots % 64;
1180                if remainder != 0 {
1181                    *logical_words.last_mut().expect("non-empty shot mask") &=
1182                        (1u64 << remainder) - 1;
1183                }
1184            }
1185            continue;
1186        }
1187        if edge.single_observable_flip {
1188            for_each_bernoulli_event(rng, shots, edge.probability, |shot, _| {
1189                logical_words[shot / 64] ^= 1u64 << (shot % 64);
1190            });
1191        } else {
1192            for_each_bernoulli_event(rng, shots, edge.probability, |_, _| {});
1193        }
1194    }
1195}
1196
1197fn fill_bernoulli_words(words: &mut [u64], shots: usize, probability: f64, rng: &mut SmallRng) {
1198    words.fill(0);
1199    if probability <= 0.0 {
1200        return;
1201    }
1202    if probability >= 1.0 {
1203        words.fill(u64::MAX);
1204        if let (Some(last), remainder) = (words.last_mut(), shots % 64) {
1205            if remainder != 0 {
1206                *last &= (1u64 << remainder) - 1;
1207            }
1208        }
1209        return;
1210    }
1211    for_each_bernoulli_event(rng, shots, probability, |shot, _| {
1212        words[shot / 64] |= 1u64 << (shot % 64);
1213    });
1214}
1215
1216fn packed_column_for_id(id: i64, index: &HashMap<i64, usize>) -> NpResult<usize> {
1217    index.get(&id).copied().ok_or_else(|| {
1218        NpError::new(format!(
1219            "packed DEM sampler edge references unknown id {id}"
1220        ))
1221    })
1222}
1223
1224fn canonicalize_program_parts(
1225    detector_ids: Vec<i64>,
1226    observable_ids: Vec<i64>,
1227    mut edges: Vec<DemProgramEdge>,
1228) -> NpResult<(Vec<i64>, Vec<i64>, Vec<DemProgramEdge>)> {
1229    let detector_ids = canonical_id_order(
1230        &detector_ids,
1231        edges.iter().map(|edge| edge.detectors.as_slice()),
1232        "detector ids must be unique",
1233    )?;
1234    let observable_ids = canonical_id_order(
1235        &observable_ids,
1236        edges.iter().map(|edge| edge.observables.as_slice()),
1237        "logical observable ids must be unique",
1238    )?;
1239    for edge in &mut edges {
1240        parity_canonicalize(&mut edge.detectors);
1241        parity_canonicalize(&mut edge.observables);
1242    }
1243    Ok((detector_ids, observable_ids, edges))
1244}
1245
1246fn id_index(ids: &[i64]) -> HashMap<i64, usize> {
1247    ids.iter()
1248        .copied()
1249        .enumerate()
1250        .map(|(index, id)| (id, index))
1251        .collect()
1252}
1253
1254fn compile_dem_edges(
1255    edges: Vec<DetectorErrorEdge>,
1256    preserve_metadata: bool,
1257) -> NpResult<CompiledDemEdges> {
1258    let mut catalog = preserve_metadata.then(|| LocationCatalogBuilder::with_capacity(edges.len()));
1259    let mut compiled = Vec::with_capacity(edges.len());
1260    let mut metadata = preserve_metadata.then(|| Vec::with_capacity(edges.len()));
1261    for edge in edges {
1262        edge.validate()?;
1263        let DetectorErrorEdge {
1264            probability,
1265            detectors,
1266            observables,
1267            location_id,
1268            event,
1269            tags,
1270        } = edge;
1271        if let (Some(catalog), Some(metadata)) = (&mut catalog, &mut metadata) {
1272            metadata.push(DemProgramEdgeMetadata {
1273                location_id: catalog.intern(location_id, tags),
1274                event,
1275            });
1276        }
1277        compiled.push(DemProgramEdge {
1278            probability,
1279            detectors,
1280            observables,
1281        });
1282    }
1283    let catalog = catalog
1284        .map(LocationCatalogBuilder::finish)
1285        .unwrap_or_default();
1286    let groups = metadata
1287        .as_deref()
1288        .map(|metadata| build_dem_program_location_groups(&compiled, metadata, catalog.len()))
1289        .unwrap_or_default();
1290    Ok(CompiledDemEdges {
1291        edges: compiled,
1292        metadata,
1293        catalog,
1294        location_groups: groups,
1295    })
1296}
1297
1298fn build_dem_program_location_groups(
1299    edges: &[DemProgramEdge],
1300    edge_metadata: &[DemProgramEdgeMetadata],
1301    location_count: usize,
1302) -> Vec<DemProgramLocationGroup> {
1303    let mut group_indices = vec![None; location_count];
1304    let mut groups = Vec::with_capacity(location_count);
1305    for (edge_index, metadata) in edge_metadata.iter().enumerate() {
1306        let location_index = metadata.location_id.index();
1307        let group_index = match group_indices[location_index] {
1308            Some(group_index) => group_index,
1309            None => {
1310                let group_index = groups.len();
1311                group_indices[location_index] = Some(group_index);
1312                groups.push(DemProgramLocationGroup {
1313                    location_id: metadata.location_id,
1314                    edge_indices: Vec::new(),
1315                    total_probability: 0.0,
1316                });
1317                group_index
1318            }
1319        };
1320        let group = &mut groups[group_index];
1321        group.edge_indices.push(edge_index);
1322        group.total_probability += edges[edge_index].probability;
1323    }
1324    groups
1325}
1326
1327fn materialize_dem_edge(
1328    edge: &DemProgramEdge,
1329    metadata: Option<&DemProgramEdgeMetadata>,
1330    catalog: &LocationCatalog,
1331) -> DetectorErrorEdge {
1332    let (location_id, event, tags) = match metadata {
1333        Some(metadata) => (
1334            catalog.label(metadata.location_id).to_string(),
1335            metadata.event.clone(),
1336            catalog.tags(metadata.location_id).clone(),
1337        ),
1338        None => (String::new(), DemEvent::Bool(false), HashMap::new()),
1339    };
1340    DetectorErrorEdge {
1341        probability: edge.probability,
1342        detectors: edge.detectors.clone(),
1343        observables: edge.observables.clone(),
1344        location_id,
1345        event,
1346        tags,
1347    }
1348}
1349
1350#[cfg(test)]
1351mod tests {
1352    use super::*;
1353
1354    fn edge(probability: f64, detectors: Vec<i64>, observables: Vec<i64>) -> DetectorErrorEdge {
1355        DetectorErrorEdge {
1356            probability,
1357            detectors,
1358            observables,
1359            location_id: "test".to_string(),
1360            event: crate::DemEvent::Pauli("X".to_string()),
1361            tags: HashMap::new(),
1362        }
1363    }
1364
1365    #[test]
1366    fn sampling_only_edges_keep_metadata_out_of_the_hot_representation() {
1367        let simulator = DemHotspotEstimator::from_sampling_parts(
1368            vec![1],
1369            vec![2],
1370            vec![edge(0.25, vec![1], vec![2])],
1371        )
1372        .unwrap();
1373
1374        assert!(simulator.edge_metadata.is_none());
1375        assert!(simulator.location_catalog.is_empty());
1376        let materialized = simulator.edge(0).unwrap();
1377        assert_eq!(materialized.probability, 0.25);
1378        assert_eq!(materialized.detectors, vec![1]);
1379        assert_eq!(materialized.observables, vec![2]);
1380        assert!(materialized.location_id.is_empty());
1381        assert_eq!(materialized.event, DemEvent::Bool(false));
1382        assert!(materialized.tags.is_empty());
1383    }
1384
1385    fn packed_reference(
1386        batch: &DemBatch,
1387        detector_ids: &[i64],
1388        observable_ids: &[i64],
1389    ) -> (Vec<u8>, Vec<u8>) {
1390        let detector_bytes = detector_ids.len().div_ceil(8);
1391        let observable_bytes = observable_ids.len().div_ceil(8);
1392        let mut detectors = vec![0u8; batch.shots() * detector_bytes];
1393        let mut observables = vec![0u8; batch.shots() * observable_bytes];
1394        for shot in 0..batch.shots() {
1395            for (column, detector_id) in detector_ids.iter().enumerate() {
1396                if batch.detectors[detector_id].words[shot / 64] & (1u64 << (shot % 64)) != 0 {
1397                    detectors[shot * detector_bytes + column / 8] |= 1u8 << (column % 8);
1398                }
1399            }
1400            for (column, observable_id) in observable_ids.iter().enumerate() {
1401                if batch.observables[observable_id].words[shot / 64] & (1u64 << (shot % 64)) != 0 {
1402                    observables[shot * observable_bytes + column / 8] |= 1u8 << (column % 8);
1403                }
1404            }
1405        }
1406        (detectors, observables)
1407    }
1408
1409    fn mask_batch_parts(batch: DetectorBatch) -> (Vec<i64>, Vec<Mask>, usize) {
1410        let DetectorBatch::Masks {
1411            detector_ids,
1412            masks,
1413            shots,
1414        } = batch
1415        else {
1416            unreachable!("requested Masks conversion")
1417        };
1418        (detector_ids, masks, shots)
1419    }
1420
1421    #[test]
1422    fn negotiated_sampling_formats_preserve_syndrome_truth_rng_detail_and_attribution() {
1423        let simulator = DemHotspotEstimator::from_parts(
1424            vec![10, 20, 30],
1425            vec![7, 9],
1426            vec![
1427                edge(0.0, vec![10], vec![7]),
1428                edge(0.13, vec![20, 30], vec![9]),
1429                edge(0.71, vec![10, 30], vec![7, 9]),
1430                edge(1.0, vec![20], vec![]),
1431                edge(0.37, vec![10, 20], vec![7]),
1432            ],
1433        )
1434        .unwrap();
1435        let detector_ids = [30, 10, 20];
1436        let observable_ids = [9, 7];
1437        let detail_ids = [20, 10];
1438        type ExpectedSampling = (
1439            Vec<Mask>,
1440            CorrectionMaskBatch,
1441            Vec<Mask>,
1442            Vec<Mask>,
1443            u64,
1444            Option<DemHotspotEstimate>,
1445        );
1446
1447        for shots in [0, 1, 7, 8, 63, 64, 65, 129] {
1448            let mut expected: Option<ExpectedSampling> = None;
1449            for format in DetectorBatchFormat::STABLE_ORDER {
1450                let plan = simulator
1451                    .compile_decoder_sampling_plan(
1452                        &detector_ids,
1453                        &observable_ids,
1454                        format,
1455                        &detail_ids,
1456                        true,
1457                    )
1458                    .unwrap();
1459                assert_eq!(plan.format(), format);
1460                assert_eq!(plan.detail_detector_ids(), detail_ids);
1461                assert!(plan.records_attribution());
1462
1463                let mut rng = SmallRng::new(0xdec0de);
1464                let sampled = plan.run_sampling_result_with_rng(shots, &mut rng).unwrap();
1465                let next = rng.next_u64();
1466                let (_, syndrome_masks, sampled_shots) = mask_batch_parts(
1467                    convert_detector_batch(sampled.syndrome(), DetectorBatchFormat::Masks).unwrap(),
1468                );
1469                assert_eq!(sampled_shots, shots);
1470                let observable_masks = sampled.observables().as_masks().unwrap();
1471                let detail_masks = sampled.detail_detector_masks().to_vec();
1472                let trace = sampled.attribution().expect("attribution was requested");
1473                assert_eq!(trace.shots(), shots);
1474                let trace_masks = trace.edge_event_masks().to_vec();
1475                let estimate = if shots == 0 {
1476                    None
1477                } else {
1478                    let mut loss = Mask::zero(word_count(shots));
1479                    for mask in &observable_masks.masks {
1480                        loss.or_assign(mask);
1481                    }
1482                    Some(
1483                        simulator
1484                            .estimate_from_attribution(trace, &loss, None, simulator.edge_count())
1485                            .unwrap(),
1486                    )
1487                };
1488
1489                let actual = (
1490                    syndrome_masks,
1491                    observable_masks,
1492                    detail_masks,
1493                    trace_masks,
1494                    next,
1495                    estimate,
1496                );
1497                if let Some(expected) = &expected {
1498                    assert_eq!(&actual, expected);
1499                } else {
1500                    expected = Some(actual);
1501                }
1502            }
1503        }
1504    }
1505
1506    #[test]
1507    fn ordinary_negotiated_sampling_does_not_record_attribution() {
1508        let simulator = DemHotspotEstimator::from_sampling_parts(
1509            vec![1],
1510            vec![2],
1511            vec![edge(0.25, vec![1], vec![2])],
1512        )
1513        .unwrap();
1514        for format in DetectorBatchFormat::STABLE_ORDER {
1515            let plan = simulator
1516                .compile_decoder_sampling_plan(&[1], &[2], format, &[], false)
1517                .unwrap();
1518            assert!(!plan.records_attribution());
1519            let sampled = plan
1520                .run_sampling_result_with_rng(65, &mut SmallRng::new(4))
1521                .unwrap();
1522            assert!(sampled.attribution().is_none());
1523            assert!(sampled.detail_detector_ids().is_empty());
1524            assert!(sampled.detail_detector_masks().is_empty());
1525        }
1526    }
1527
1528    #[test]
1529    fn compiled_sampling_matches_generic_batch_across_word_boundaries() {
1530        let simulator = DemHotspotEstimator::from_sampling_parts(
1531            vec![10, 20, 30],
1532            vec![7, 9],
1533            vec![
1534                edge(0.0, vec![10], vec![7]),
1535                edge(0.13, vec![20, 30], vec![9]),
1536                edge(0.71, vec![10, 30], vec![7, 9]),
1537                edge(1.0, vec![20], vec![]),
1538            ],
1539        )
1540        .unwrap();
1541        let detector_ids = [30, 10, 20];
1542        let observable_ids = [9, 7];
1543        let plan = simulator
1544            .compile_sampling_plan(&detector_ids, &observable_ids)
1545            .unwrap();
1546
1547        for shots in [1, 63, 64, 65, 129] {
1548            for seed in [0, 1, 0xdead_beef] {
1549                let mut generic_rng = SmallRng::new(seed);
1550                let generic = simulator.run_batch_with_rng(shots, &mut generic_rng, false);
1551                let expected = packed_reference(&generic, &detector_ids, &observable_ids);
1552                let mut compiled_rng = SmallRng::new(seed);
1553                let actual = plan.run_packed_shot_batch_with_rng(shots, &mut compiled_rng);
1554                assert_eq!(actual.detector_data, expected.0);
1555                assert_eq!(actual.observable_data, expected.1);
1556                assert_eq!(compiled_rng.next_u64(), generic_rng.next_u64());
1557            }
1558        }
1559    }
1560
1561    #[test]
1562    fn compiled_event_batch_emits_parity_canonical_events() {
1563        let simulator = DemHotspotEstimator::from_sampling_parts(
1564            vec![10, 20],
1565            vec![7, 9],
1566            vec![
1567                edge(1.0, vec![20, 10, 20], vec![9]),
1568                edge(1.0, vec![10], vec![9, 9, 7]),
1569            ],
1570        )
1571        .unwrap();
1572        let plan = simulator.compile_sampling_plan(&[20, 10], &[9, 7]).unwrap();
1573        let batch = plan.run_detector_event_shot_batch_with_rng(2, &mut SmallRng::new(4));
1574
1575        assert_eq!(batch.offsets, vec![0, 2, 4]);
1576        assert_eq!(batch.events, vec![1, 1, 1, 1]);
1577        assert_eq!(batch.observable_data, vec![0b11, 0b11]);
1578    }
1579
1580    #[test]
1581    fn estimator_canonicalizes_implicit_ids_and_parity_once() {
1582        let simulator = DemHotspotEstimator::from_sampling_parts(
1583            Vec::new(),
1584            Vec::new(),
1585            vec![edge(1.0, vec![1, 1], vec![9, 9])],
1586        )
1587        .unwrap();
1588
1589        assert_eq!(simulator.detector_ids, vec![1]);
1590        assert_eq!(simulator.observable_ids, vec![9]);
1591        assert_eq!(simulator.edge_count(), 1);
1592        assert!(simulator.edge(0).unwrap().detectors.is_empty());
1593        assert!(simulator.edge(0).unwrap().observables.is_empty());
1594
1595        let mut generic_rng = SmallRng::new(13);
1596        let generic = simulator.run_batch_with_rng(4, &mut generic_rng, true);
1597        assert_eq!(generic.detectors[&1].bit_count(), 0);
1598        assert_eq!(generic.observables[&9].bit_count(), 0);
1599        assert_eq!(generic.edge_event_masks().len(), 1);
1600        assert_eq!(generic.edge_event_masks()[0].bit_count(), 4);
1601
1602        let plan = simulator.compile_sampling_plan(&[1], &[9]).unwrap();
1603        let mut packed_rng = SmallRng::new(13);
1604        let packed = plan.run_packed_shot_batch_with_rng(4, &mut packed_rng);
1605        assert_eq!(packed.detector_data, vec![0; 4]);
1606        assert_eq!(packed.observable_data, vec![0; 4]);
1607        assert_eq!(generic_rng.next_u64(), packed_rng.next_u64());
1608    }
1609
1610    #[test]
1611    fn parity_cancelled_edges_preserve_rng_across_sampling_paths() {
1612        for cancelled_probability in [0.0, 0.37, 1.0] {
1613            let simulator = DemHotspotEstimator::from_sampling_parts(
1614                Vec::new(),
1615                Vec::new(),
1616                vec![
1617                    edge(cancelled_probability, vec![1, 1], vec![9, 9]),
1618                    edge(0.43, vec![2], vec![10]),
1619                ],
1620            )
1621            .unwrap();
1622            let detector_ids = simulator.detector_ids();
1623            let observable_ids = simulator.observable_ids();
1624            let plan = simulator
1625                .compile_sampling_plan(detector_ids, observable_ids)
1626                .unwrap();
1627
1628            let mut generic_rng = SmallRng::new(123);
1629            let generic = simulator.run_batch_with_rng(129, &mut generic_rng, true);
1630            let expected = packed_reference(&generic, detector_ids, observable_ids);
1631            let generic_next = generic_rng.next_u64();
1632            assert_eq!(generic.edge_event_masks().len(), 2);
1633            assert_eq!(generic.detectors[&1].bit_count(), 0);
1634            assert_eq!(generic.observables[&9].bit_count(), 0);
1635
1636            let mut packed_rng = SmallRng::new(123);
1637            let packed = plan.run_packed_shot_batch_with_rng(129, &mut packed_rng);
1638            assert_eq!(packed.detector_data, expected.0);
1639            assert_eq!(packed.observable_data, expected.1);
1640            assert_eq!(packed_rng.next_u64(), generic_next);
1641
1642            let mut expected_offsets = Vec::with_capacity(130);
1643            let mut expected_events = Vec::new();
1644            expected_offsets.push(0);
1645            for shot in 0..129 {
1646                if generic.detectors[&2].words[shot / 64] & (1u64 << (shot % 64)) != 0 {
1647                    expected_events.push(1);
1648                }
1649                expected_offsets.push(expected_events.len());
1650            }
1651            let mut event_rng = SmallRng::new(123);
1652            let events = plan.run_detector_event_shot_batch_with_rng(129, &mut event_rng);
1653            assert_eq!(events.offsets, expected_offsets);
1654            assert_eq!(events.events, expected_events);
1655            assert_eq!(events.observable_data, expected.1);
1656            assert_eq!(event_rng.next_u64(), generic_next);
1657        }
1658    }
1659
1660    #[test]
1661    fn public_id_mirrors_do_not_mutate_the_canonical_sampling_layout() {
1662        let mut simulator = DemHotspotEstimator::from_sampling_parts(
1663            Vec::new(),
1664            Vec::new(),
1665            vec![edge(0.43, vec![7], vec![9])],
1666        )
1667        .unwrap();
1668        let mut expected_rng = SmallRng::new(17);
1669        let expected = simulator.run_batch_with_rng(129, &mut expected_rng, false);
1670        let expected_rng_next = expected_rng.next_u64();
1671        let expected_packed = packed_reference(&expected, &[7], &[9]);
1672
1673        simulator.detector_ids.clear();
1674        simulator.detector_ids.push(70);
1675        simulator.observable_ids.clear();
1676        simulator.observable_ids.push(90);
1677
1678        assert_eq!(simulator.detector_ids(), &[7]);
1679        assert_eq!(simulator.observable_ids(), &[9]);
1680        assert_eq!(simulator.run_batch(129, Some(17), false).unwrap(), expected);
1681        assert_eq!(
1682            simulator.compile_logical_count_plan().observable_ids(),
1683            &[9]
1684        );
1685        let plan = simulator
1686            .compile_sampling_plan(simulator.detector_ids(), simulator.observable_ids())
1687            .unwrap();
1688        assert_eq!(plan.detector_ids(), &[7]);
1689        assert_eq!(plan.observable_ids(), &[9]);
1690
1691        let mut packed_rng = SmallRng::new(17);
1692        let packed = plan.run_packed_shot_batch_with_rng(129, &mut packed_rng);
1693        assert_eq!(packed.detector_data, expected_packed.0);
1694        assert_eq!(packed.observable_data, expected_packed.1);
1695        assert_eq!(packed_rng.next_u64(), expected_rng_next);
1696
1697        let mut expected_offsets = Vec::with_capacity(130);
1698        let mut expected_events = Vec::new();
1699        expected_offsets.push(0);
1700        for shot in 0..129 {
1701            if expected.detectors[&7].words[shot / 64] & (1u64 << (shot % 64)) != 0 {
1702                expected_events.push(0);
1703            }
1704            expected_offsets.push(expected_events.len());
1705        }
1706        let mut event_rng = SmallRng::new(17);
1707        let events = plan.run_detector_event_shot_batch_with_rng(129, &mut event_rng);
1708        assert_eq!(events.offsets, expected_offsets);
1709        assert_eq!(events.events, expected_events);
1710        assert_eq!(events.observable_data, expected_packed.1);
1711        assert_eq!(event_rng.next_u64(), expected_rng_next);
1712    }
1713
1714    #[test]
1715    fn estimator_rejects_duplicate_declared_ids() {
1716        let err = DemHotspotEstimator::from_sampling_parts(vec![1, 1], Vec::new(), Vec::new())
1717            .unwrap_err();
1718
1719        assert_eq!(err.message(), "detector ids must be unique");
1720    }
1721
1722    #[test]
1723    fn compiled_logical_count_matches_generic_loss_and_rng_sequence() {
1724        let simulator = DemHotspotEstimator::from_sampling_parts(
1725            vec![1],
1726            vec![5],
1727            vec![
1728                edge(0.17, vec![1], vec![]),
1729                edge(0.0, vec![], vec![5]),
1730                edge(0.23, vec![], vec![5, 9]),
1731                edge(0.61, vec![], vec![9, 9]),
1732                edge(1.0, vec![], vec![11]),
1733            ],
1734        )
1735        .unwrap();
1736        let plan = simulator.compile_logical_count_plan();
1737        assert_eq!(plan.observable_ids(), &[5, 9, 11]);
1738
1739        for shots in [0, 1, 63, 64, 65, 129] {
1740            for seed in [0, 1, 99] {
1741                let mut generic_rng = SmallRng::new(seed);
1742                let generic = simulator.run_batch_with_rng(shots, &mut generic_rng, false);
1743                let mut compiled_rng = SmallRng::new(seed);
1744                let actual = plan.sample_logical_error_count_with_rng(shots, &mut compiled_rng);
1745                assert_eq!(actual, generic.loss_mask.bit_count());
1746                assert_eq!(compiled_rng.next_u64(), generic_rng.next_u64());
1747            }
1748        }
1749    }
1750
1751    #[test]
1752    fn single_observable_zero_allocation_path_preserves_xor_and_rng() {
1753        let simulator = DemHotspotEstimator::from_sampling_parts(
1754            vec![1],
1755            vec![5],
1756            vec![
1757                edge(0.19, vec![1], vec![]),
1758                edge(0.23, vec![], vec![5]),
1759                edge(0.61, vec![], vec![5]),
1760                edge(0.47, vec![], vec![5, 5]),
1761                edge(1.0, vec![], vec![5]),
1762            ],
1763        )
1764        .unwrap();
1765        let plan = simulator.compile_logical_count_plan();
1766
1767        for shots in [0, 1, 63, 64, 65, 129, 513] {
1768            for seed in [0, 7, 1234] {
1769                let mut generic_rng = SmallRng::new(seed);
1770                let generic = simulator.run_batch_with_rng(shots, &mut generic_rng, false);
1771                let mut compiled_rng = SmallRng::new(seed);
1772                let actual = plan.sample_logical_error_count_with_rng(shots, &mut compiled_rng);
1773                assert_eq!(actual, generic.loss_mask.bit_count());
1774                assert_eq!(compiled_rng.next_u64(), generic_rng.next_u64());
1775            }
1776        }
1777    }
1778
1779    #[test]
1780    fn compiled_sampling_preserves_validation_errors() {
1781        let simulator = DemHotspotEstimator::from_sampling_parts(
1782            vec![1],
1783            vec![2],
1784            vec![edge(0.5, vec![1], vec![2])],
1785        )
1786        .unwrap();
1787        let detector_error = simulator.compile_sampling_plan(&[9], &[2]).unwrap_err();
1788        assert_eq!(
1789            detector_error.message(),
1790            "packed DEM sampler requested detector id 9, but it is not declared by the DEM"
1791        );
1792        let observable_error = simulator.compile_sampling_plan(&[1], &[9]).unwrap_err();
1793        assert_eq!(
1794            observable_error.message(),
1795            "packed DEM sampler requested observable id 9, but it is not declared by the DEM"
1796        );
1797    }
1798
1799    #[test]
1800    fn compiled_sampling_rejects_duplicate_detector_layout() {
1801        let simulator = DemHotspotEstimator::from_sampling_parts(
1802            vec![1],
1803            vec![2],
1804            vec![edge(0.5, vec![1], vec![2])],
1805        )
1806        .unwrap();
1807
1808        let error = simulator.compile_sampling_plan(&[1, 1], &[2]).unwrap_err();
1809
1810        assert_eq!(
1811            error.message(),
1812            "decoder detector ids must be unique; duplicate detector id 1"
1813        );
1814    }
1815
1816    #[test]
1817    fn compiled_sampling_rejects_duplicate_detail_detector_layout() {
1818        let simulator = DemHotspotEstimator::from_sampling_parts(
1819            vec![1],
1820            vec![2],
1821            vec![edge(0.5, vec![1], vec![2])],
1822        )
1823        .unwrap();
1824
1825        let error = simulator
1826            .compile_decoder_sampling_plan(&[1], &[2], DetectorBatchFormat::Packed, &[1, 1], false)
1827            .unwrap_err();
1828
1829        assert_eq!(
1830            error.message(),
1831            "decoder detector ids must be unique; duplicate detector id 1"
1832        );
1833    }
1834
1835    #[test]
1836    fn compiled_sampling_rejects_duplicate_observable_layout() {
1837        let simulator = DemHotspotEstimator::from_sampling_parts(
1838            vec![1],
1839            vec![2],
1840            vec![edge(0.5, vec![1], vec![2])],
1841        )
1842        .unwrap();
1843
1844        let error = simulator.compile_sampling_plan(&[1], &[2, 2]).unwrap_err();
1845
1846        assert_eq!(
1847            error.message(),
1848            "decoder observable ids must be unique; duplicate observable id 2"
1849        );
1850    }
1851
1852    #[test]
1853    fn groups_edges_by_location() {
1854        let edges = vec![
1855            DetectorErrorEdge {
1856                probability: 0.1,
1857                detectors: vec![0],
1858                observables: Vec::new(),
1859                location_id: "a".to_string(),
1860                event: crate::DemEvent::Pauli("X".to_string()),
1861                tags: HashMap::new(),
1862            },
1863            DetectorErrorEdge {
1864                probability: 0.2,
1865                detectors: vec![1],
1866                observables: Vec::new(),
1867                location_id: "a".to_string(),
1868                event: crate::DemEvent::Pauli("Z".to_string()),
1869                tags: HashMap::new(),
1870            },
1871        ];
1872
1873        let groups = DemHotspotEstimator::from_parts(Vec::new(), Vec::new(), edges)
1874            .unwrap()
1875            .location_groups();
1876
1877        assert_eq!(groups.len(), 1);
1878        assert_eq!(groups[0].edge_indices, vec![0, 1]);
1879        assert_eq!(groups[0].total_probability, 0.30000000000000004);
1880    }
1881
1882    #[test]
1883    fn simulator_estimates_default_logical_loss() {
1884        let simulator = DemHotspotEstimator::from_parts(
1885            Vec::new(),
1886            vec![0],
1887            vec![DetectorErrorEdge {
1888                probability: 1.0,
1889                detectors: Vec::new(),
1890                observables: vec![0],
1891                location_id: "logical".to_string(),
1892                event: crate::DemEvent::Pauli("L".to_string()),
1893                tags: HashMap::new(),
1894            }],
1895        )
1896        .unwrap();
1897
1898        let estimate = simulator.estimate_default(64, Some(7), None, 1).unwrap();
1899
1900        assert_eq!(estimate.shots, 64);
1901        assert_eq!(estimate.mean_loss, 1.0);
1902        assert_eq!(estimate.top_edges, vec![0]);
1903        assert_eq!(estimate.top_locations, vec!["logical"]);
1904    }
1905
1906    #[test]
1907    fn simulator_hotspot_rejects_unrecorded_foreign_and_invalid_loss_batches() {
1908        let make_simulator = || {
1909            DemHotspotEstimator::from_parts(
1910                Vec::new(),
1911                vec![0],
1912                vec![edge(0.25, Vec::new(), vec![0])],
1913            )
1914            .unwrap()
1915        };
1916        let simulator = make_simulator();
1917
1918        let batch = simulator.run_batch(8, Some(1), false).unwrap();
1919        let err = simulator
1920            .estimate_from_loss(&batch, &batch.loss_mask, None, 1)
1921            .unwrap_err();
1922        assert!(err.to_string().contains("recorded event masks"));
1923
1924        let batch = simulator.run_batch(8, Some(1), true).unwrap();
1925        let foreign = make_simulator();
1926        let err = foreign
1927            .estimate_from_loss(&batch, &batch.loss_mask, None, 1)
1928            .unwrap_err();
1929        assert!(err.to_string().contains("layout does not match"));
1930        simulator
1931            .clone()
1932            .estimate_from_loss(&batch, &batch.loss_mask, None, 1)
1933            .unwrap();
1934
1935        let err = simulator
1936            .estimate_from_loss(&batch, &Mask::zero(2), None, 1)
1937            .unwrap_err();
1938        assert!(err.to_string().contains("loss_mask has 2 words"));
1939
1940        let mut rng = SmallRng::new(1);
1941        let zero_shot_batch = simulator.run_batch_with_rng(0, &mut rng, true);
1942        let err = simulator
1943            .estimate_from_loss(&zero_shot_batch, &zero_shot_batch.loss_mask, None, 1)
1944            .unwrap_err();
1945        assert!(err.to_string().contains("shots to be positive"));
1946    }
1947
1948    #[test]
1949    fn simulator_rejects_invalid_edge_probability() {
1950        let err = DemHotspotEstimator::from_parts(
1951            Vec::new(),
1952            Vec::new(),
1953            vec![DetectorErrorEdge {
1954                probability: 1.5,
1955                detectors: Vec::new(),
1956                observables: Vec::new(),
1957                location_id: "bad".to_string(),
1958                event: crate::DemEvent::Pauli("X".to_string()),
1959                tags: HashMap::new(),
1960            }],
1961        )
1962        .unwrap_err();
1963
1964        assert!(err
1965            .message()
1966            .contains("DEM edge probability must be in [0, 1]"));
1967    }
1968}