bloq_ir/ir/
detector.rs

1use std::sync::{Arc, OnceLock};
2
3use bloq_circuit::{DetectorCoords, DetectorParity, DetectorTerm};
4use glam::IVec2;
5
6use super::{
7    Bloq, DetectorBundleId, InstanceMeasurement, NodeDetector, NodeDetectorParity, QuantumNode,
8    TemplateId, TemplateInstanceId,
9};
10
11/// A measurement in one bundle-local owner slot.
12#[derive(
13    Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, serde::Serialize, serde::Deserialize,
14)]
15pub struct BundleMeasurement {
16    /// Index into [`DetectorBundle::owner_templates`].
17    pub owner: u32,
18    /// Measurement id local to that owner's template.
19    pub measurement: u32,
20}
21
22/// One row stored in a reusable detector bundle.
23#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
24pub struct BundleDetector {
25    /// Parity over bundle-local owner slots.
26    pub parity: DetectorParity<BundleMeasurement>,
27    /// Local decoder coordinates.
28    pub coords: Option<DetectorCoords>,
29}
30
31/// Shared detector rows with an ordered template signature.
32#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
33pub struct DetectorBundle {
34    owner_templates: Vec<TemplateId>,
35    detectors: Vec<BundleDetector>,
36    #[serde(skip)]
37    used_owners: OnceLock<Result<Vec<u32>, DetectorBundleError>>,
38}
39
40impl DetectorBundle {
41    /// Build a bundle. Its local owner slots are checked when read or used.
42    pub fn new(owner_templates: Vec<TemplateId>, detectors: Vec<BundleDetector>) -> Self {
43        Self {
44            owner_templates,
45            detectors,
46            used_owners: OnceLock::new(),
47        }
48    }
49
50    /// Ordered template signature for the bundle's owner slots.
51    pub fn owner_templates(&self) -> &[TemplateId] {
52        &self.owner_templates
53    }
54
55    /// Detector rows in bundle-local order.
56    pub fn detectors(&self) -> &[BundleDetector] {
57        &self.detectors
58    }
59
60    /// Distinct owner slots referenced by measurement terms, in slot order.
61    ///
62    /// # Errors
63    ///
64    /// Returns [`DetectorBundleError::InvalidLocalOwner`] for an out-of-range slot,
65    /// or [`DetectorBundleError::CountOverflow`] when owner slots exceed `u32`.
66    pub fn used_owners(&self) -> Result<&[u32], DetectorBundleError> {
67        self.used_owners
68            .get_or_init(|| {
69                if self.owner_templates.len() > u32::MAX as usize {
70                    return Err(DetectorBundleError::CountOverflow);
71                }
72                let mut used = vec![false; self.owner_templates.len()];
73                for detector in &self.detectors {
74                    for term in detector.parity.terms() {
75                        if let DetectorTerm::Measurement(measurement) = term {
76                            if measurement.owner as usize >= self.owner_templates.len() {
77                                return Err(DetectorBundleError::InvalidLocalOwner {
78                                    owner: measurement.owner,
79                                    owners: self.owner_templates.len(),
80                                });
81                            }
82                            used[measurement.owner as usize] = true;
83                        }
84                    }
85                }
86                Ok(used
87                    .into_iter()
88                    .enumerate()
89                    .filter_map(|(index, present)| present.then_some(index as u32))
90                    .collect())
91            })
92            .as_ref()
93            .map(Vec::as_slice)
94            .map_err(Clone::clone)
95    }
96}
97
98/// One node-local binding of a reusable detector bundle.
99#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
100pub struct DetectorBundleUse {
101    /// Shared bundle id.
102    pub bundle: DetectorBundleId,
103    /// Instance bound to each ordered owner slot.
104    pub instances: Vec<TemplateInstanceId>,
105    /// Translation of the first two detector coordinates.
106    pub offset: IVec2,
107}
108
109/// Append-only, clone-cheap bundle storage.
110#[derive(Debug, Clone, Default, serde::Serialize, serde::Deserialize)]
111pub struct DetectorBundlePool {
112    #[serde(deserialize_with = "super::id::deserialize_pool")]
113    bundles: Vec<Arc<DetectorBundle>>,
114}
115
116fn check_table_count(count: usize) -> Result<(), DetectorBundleError> {
117    u32::try_from(count)
118        .map(|_| ())
119        .map_err(|_| DetectorBundleError::CountOverflow)
120}
121
122impl QuantumNode {
123    pub(crate) fn check_side_table_counts(&self) -> Result<(), DetectorBundleError> {
124        for count in [
125            self.detectors.len(),
126            self.detector_bundles.len(),
127            self.restarts.len(),
128        ] {
129            check_table_count(count)?;
130        }
131        Ok(())
132    }
133}
134
135impl DetectorBundlePool {
136    /// Create an empty pool.
137    pub fn new() -> Self {
138        Self::default()
139    }
140
141    /// Insert an owned bundle and return its append-only id.
142    ///
143    /// # Panics
144    ///
145    /// Panics before insertion if the next id exceeds `u32`.
146    pub fn insert(&mut self, bundle: DetectorBundle) -> DetectorBundleId {
147        self.insert_shared(Arc::new(bundle))
148    }
149
150    /// Insert an immutable shared bundle, preserving its cached analysis.
151    ///
152    /// # Panics
153    ///
154    /// Panics before insertion if the next id exceeds `u32`.
155    pub fn insert_shared(&mut self, bundle: Arc<DetectorBundle>) -> DetectorBundleId {
156        let id = DetectorBundleId(super::id::pool_index(self.bundles.len()));
157        self.bundles.push(bundle);
158        id
159    }
160
161    /// Look up a bundle by id.
162    pub fn get(&self, id: DetectorBundleId) -> Option<&DetectorBundle> {
163        self.bundles.get(id.0 as usize).map(Arc::as_ref)
164    }
165
166    /// Iterate over bundles in id order.
167    pub fn iter(&self) -> impl Iterator<Item = (DetectorBundleId, &DetectorBundle)> {
168        self.iter_shared().map(|(id, bundle)| (id, bundle.as_ref()))
169    }
170
171    /// Borrow shared handles in id order.
172    pub fn iter_shared(&self) -> impl Iterator<Item = (DetectorBundleId, &Arc<DetectorBundle>)> {
173        self.bundles
174            .iter()
175            .enumerate()
176            .map(|(index, bundle)| (DetectorBundleId(super::id::pool_index(index)), bundle))
177    }
178
179    /// Number of bundles.
180    pub fn len(&self) -> usize {
181        self.bundles.len()
182    }
183
184    /// Whether the pool has no bundles.
185    pub fn is_empty(&self) -> bool {
186        self.bundles.is_empty()
187    }
188}
189
190/// Local structure errors found before any detector rows are expanded.
191#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
192#[non_exhaustive]
193pub enum DetectorBundleError {
194    /// A node use refers to a bundle absent from the program pool.
195    #[error("unknown detector bundle {0:?}")]
196    UnknownBundle(DetectorBundleId),
197    /// A node use binds a different number of instances than the bundle signature.
198    #[error("detector bundle {bundle:?} binds {actual} instances; expected {expected}")]
199    BindingArity {
200        /// Referenced bundle.
201        bundle: DetectorBundleId,
202        /// Number of owner slots.
203        expected: usize,
204        /// Number of bound instances.
205        actual: usize,
206    },
207    /// A bundle row references a local owner slot outside its signature.
208    #[error("detector bundle owner slot {owner} exceeds {owners} owners")]
209    InvalidLocalOwner {
210        /// Referenced owner slot.
211        owner: u32,
212        /// Number of declared owner slots.
213        owners: usize,
214    },
215    /// A bound instance id has no known template placement.
216    #[error("detector bundle {bundle:?} owner {owner} binds unknown instance {instance:?}")]
217    UnknownBoundInstance {
218        /// Referenced bundle.
219        bundle: DetectorBundleId,
220        /// Bundle-local owner slot.
221        owner: u32,
222        /// Unknown instance id.
223        instance: TemplateInstanceId,
224    },
225    /// A bound instance uses a different template than its owner slot declares.
226    #[error(
227        "detector bundle {bundle:?} owner {owner} expects {expected:?}, but {instance:?} uses {actual:?}"
228    )]
229    OwnerTemplateMismatch {
230        /// Referenced bundle.
231        bundle: DetectorBundleId,
232        /// Bundle-local owner slot.
233        owner: u32,
234        /// Bound instance id.
235        instance: TemplateInstanceId,
236        /// Template declared by the bundle.
237        expected: TemplateId,
238        /// Actual instance template.
239        actual: TemplateId,
240    },
241    /// A count or address exceeds its integer representation.
242    #[error("detector count or address overflows")]
243    CountOverflow,
244}
245
246/// Stable address of a node detector row.
247#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
248pub enum NodeDetectorAddress {
249    /// Index into the node's inline detector table.
250    Inline(u32),
251    /// Index of a bundle use and a row within its definition.
252    Bundle {
253        /// Index into `QuantumNode::detector_bundles`.
254        use_index: u32,
255        /// Index into `DetectorBundle::detectors`.
256        row: u32,
257    },
258}
259
260/// A borrowed detector row, mapped into instance space on demand.
261#[derive(Debug, Clone, Copy)]
262pub struct NodeDetectorView<'a> {
263    address: NodeDetectorAddress,
264    source: NodeDetectorSource<'a>,
265    offset: IVec2,
266}
267
268#[derive(Debug, Clone, Copy)]
269enum NodeDetectorSource<'a> {
270    Inline(&'a NodeDetector),
271    Bundle(&'a BundleDetector, &'a [TemplateInstanceId]),
272}
273
274impl NodeDetectorView<'_> {
275    /// Stable address of this row within the node.
276    pub fn address(&self) -> NodeDetectorAddress {
277        self.address
278    }
279
280    /// Terms mapped to bound instances, in source term order.
281    pub fn terms(&self) -> impl Iterator<Item = DetectorTerm<InstanceMeasurement>> + '_ {
282        let (inline, bundle) = match self.source {
283            NodeDetectorSource::Inline(detector) => (Some(detector), None),
284            NodeDetectorSource::Bundle(detector, instances) => (None, Some((detector, instances))),
285        };
286        inline
287            .map(|detector| detector.parity.terms().iter().copied())
288            .into_iter()
289            .flatten()
290            .chain(
291                bundle
292                    .map(|(detector, instances)| {
293                        detector.parity.terms().iter().map(move |term| match *term {
294                            DetectorTerm::Measurement(measurement) => {
295                                DetectorTerm::Measurement(InstanceMeasurement {
296                                    instance: instances[measurement.owner as usize],
297                                    measurement: measurement.measurement,
298                                })
299                            }
300                            DetectorTerm::LoopState(state) => DetectorTerm::LoopState(state),
301                        })
302                    })
303                    .into_iter()
304                    .flatten(),
305            )
306    }
307
308    /// Measurement terms only, in source term order.
309    pub fn measurements(&self) -> impl Iterator<Item = InstanceMeasurement> + '_ {
310        self.terms().filter_map(|term| match term {
311            DetectorTerm::Measurement(measurement) => Some(measurement),
312            DetectorTerm::LoopState(_) => None,
313        })
314    }
315
316    /// Constant XOR term.
317    pub fn sign(&self) -> bool {
318        match self.source {
319            NodeDetectorSource::Inline(detector) => detector.parity.sign(),
320            NodeDetectorSource::Bundle(detector, _) => detector.parity.sign(),
321        }
322    }
323
324    /// Coordinates translated by the bundle use's spatial offset.
325    pub fn coords(&self) -> Option<impl Iterator<Item = f64> + '_> {
326        let coords = match self.source {
327            NodeDetectorSource::Inline(detector) => detector.coords.as_ref(),
328            NodeDetectorSource::Bundle(detector, _) => detector.coords.as_ref(),
329        }?;
330        Some(coords.iter().enumerate().map(move |(index, &coord)| {
331            if matches!(self.source, NodeDetectorSource::Inline(_)) {
332                return coord;
333            }
334            match index {
335                0 => coord + self.offset.x as f64,
336                1 => coord + self.offset.y as f64,
337                _ => coord,
338            }
339        }))
340    }
341
342    /// Materialize and canonicalize the bound parity, including alias cancellation.
343    pub fn parity(&self) -> NodeDetectorParity {
344        NodeDetectorParity::from_terms(self.terms()).with_sign(self.sign())
345    }
346
347    /// Materialize the bound detector and its translated coordinates.
348    pub fn to_owned(&self) -> NodeDetector {
349        NodeDetector {
350            parity: self.parity(),
351            coords: self.coords().map(Iterator::collect),
352        }
353    }
354}
355
356/// Inline rows followed by bundle uses in node order, then row order.
357#[derive(Debug)]
358pub struct NodeDetectors<'a> {
359    node: &'a QuantumNode,
360    pool: &'a DetectorBundlePool,
361    inline_index: usize,
362    use_index: usize,
363    row_index: usize,
364}
365
366impl<'a> Iterator for NodeDetectors<'a> {
367    type Item = NodeDetectorView<'a>;
368
369    fn next(&mut self) -> Option<Self::Item> {
370        if let Some(detector) = self.node.detectors.get(self.inline_index) {
371            let address = NodeDetectorAddress::Inline(self.inline_index as u32);
372            self.inline_index += 1;
373            return Some(NodeDetectorView {
374                address,
375                source: NodeDetectorSource::Inline(detector),
376                offset: IVec2::ZERO,
377            });
378        }
379        loop {
380            let bundle_use = self.node.detector_bundles.get(self.use_index)?;
381            let bundle = self
382                .pool
383                .get(bundle_use.bundle)
384                .expect("preflight checked bundle");
385            if let Some(detector) = bundle.detectors.get(self.row_index) {
386                let address = NodeDetectorAddress::Bundle {
387                    use_index: self.use_index as u32,
388                    row: self.row_index as u32,
389                };
390                self.row_index += 1;
391                return Some(NodeDetectorView {
392                    address,
393                    source: NodeDetectorSource::Bundle(detector, &bundle_use.instances),
394                    offset: bundle_use.offset,
395                });
396            }
397            self.use_index += 1;
398            self.row_index = 0;
399        }
400    }
401}
402
403impl Bloq {
404    /// Count inline and bound detector rows after checking local bundle structure.
405    ///
406    /// # Errors
407    ///
408    /// Returns a [`DetectorBundleError`] for a missing bundle, invalid binding,
409    /// invalid local owner slot, or a count/address overflow.
410    pub fn node_detector_count(&self, node: &QuantumNode) -> Result<usize, DetectorBundleError> {
411        node.check_side_table_counts()?;
412        let mut count = node.detectors.len();
413        for bundle_use in &node.detector_bundles {
414            let bundle = self
415                .detector_bundles()
416                .get(bundle_use.bundle)
417                .ok_or(DetectorBundleError::UnknownBundle(bundle_use.bundle))?;
418            let expected = bundle.owner_templates.len();
419            let actual = bundle_use.instances.len();
420            if actual != expected {
421                return Err(DetectorBundleError::BindingArity {
422                    bundle: bundle_use.bundle,
423                    expected,
424                    actual,
425                });
426            }
427            bundle.used_owners()?;
428            if bundle.detectors.len() > u32::MAX as usize {
429                return Err(DetectorBundleError::CountOverflow);
430            }
431            count = count
432                .checked_add(bundle.detectors.len())
433                .ok_or(DetectorBundleError::CountOverflow)?;
434        }
435        if self.detector_bundles().len() > u32::MAX as usize {
436            return Err(DetectorBundleError::CountOverflow);
437        }
438        Ok(count)
439    }
440
441    /// Check every bundle owner binding against a caller's instance registry.
442    ///
443    /// # Errors
444    ///
445    /// Returns local structure errors from [`Self::node_detector_count`], or
446    /// [`DetectorBundleError::UnknownBoundInstance`] / [`DetectorBundleError::OwnerTemplateMismatch`]
447    /// when the supplied registry does not match a bundle's owner signature.
448    pub fn check_detector_bundle_bindings(
449        &self,
450        node: &QuantumNode,
451        mut lookup: impl FnMut(TemplateInstanceId) -> Option<TemplateId>,
452    ) -> Result<(), DetectorBundleError> {
453        self.node_detector_count(node)?;
454        for bundle_use in &node.detector_bundles {
455            let bundle = self
456                .detector_bundles()
457                .get(bundle_use.bundle)
458                .ok_or(DetectorBundleError::UnknownBundle(bundle_use.bundle))?;
459            for (owner, (&instance, &expected)) in bundle_use
460                .instances
461                .iter()
462                .zip(bundle.owner_templates.iter())
463                .enumerate()
464            {
465                let actual = lookup(instance).ok_or(DetectorBundleError::UnknownBoundInstance {
466                    bundle: bundle_use.bundle,
467                    owner: owner as u32,
468                    instance,
469                })?;
470                if actual != expected {
471                    return Err(DetectorBundleError::OwnerTemplateMismatch {
472                        bundle: bundle_use.bundle,
473                        owner: owner as u32,
474                        instance,
475                        expected,
476                        actual,
477                    });
478                }
479            }
480        }
481        Ok(())
482    }
483
484    /// Borrow node detectors in inline, bundle-use, and bundle-row order.
485    ///
486    /// # Errors
487    ///
488    /// Returns the same structural errors as [`Self::node_detector_count`].
489    pub fn node_detectors<'a>(
490        &'a self,
491        node: &'a QuantumNode,
492    ) -> Result<NodeDetectors<'a>, DetectorBundleError> {
493        self.node_detector_count(node)?;
494        Ok(NodeDetectors {
495            node,
496            pool: self.detector_bundles(),
497            inline_index: 0,
498            use_index: 0,
499            row_index: 0,
500        })
501    }
502}
503
504#[cfg(test)]
505mod tests {
506    use bloq_circuit::LoopStateId;
507
508    use super::*;
509
510    #[test]
511    fn side_table_counts_fit_guard_index_counters() {
512        assert_eq!(check_table_count(u32::MAX as usize), Ok(()));
513        if let Some(exhausted) = (u32::MAX as usize).checked_add(1) {
514            assert_eq!(
515                check_table_count(exhausted),
516                Err(DetectorBundleError::CountOverflow)
517            );
518        }
519    }
520
521    #[test]
522    fn bound_rows_translate_and_cancel_aliased_measurements() {
523        let mut bloq = Bloq::new();
524        let bundle = bloq.add_detector_bundle(DetectorBundle::new(
525            vec![TemplateId(0), TemplateId(0)],
526            vec![BundleDetector {
527                parity: DetectorParity::from_terms([
528                    DetectorTerm::Measurement(BundleMeasurement {
529                        owner: 0,
530                        measurement: 7,
531                    }),
532                    DetectorTerm::Measurement(BundleMeasurement {
533                        owner: 1,
534                        measurement: 7,
535                    }),
536                    DetectorTerm::LoopState(LoopStateId(2)),
537                ])
538                .with_sign(true),
539                coords: Some(DetectorCoords::from_slice(&[1.0, 2.0, 3.0])),
540            }],
541        ));
542        let node = QuantumNode {
543            detector_bundles: vec![DetectorBundleUse {
544                bundle,
545                instances: vec![TemplateInstanceId(4), TemplateInstanceId(4)],
546                offset: IVec2::new(10, -2),
547            }],
548            ..QuantumNode::default()
549        };
550        assert_eq!(bloq.node_detector_count(&node), Ok(1));
551        let row = bloq.node_detectors(&node).unwrap().next().unwrap();
552        assert_eq!(
553            row.address(),
554            NodeDetectorAddress::Bundle {
555                use_index: 0,
556                row: 0
557            }
558        );
559        assert_eq!(row.measurements().count(), 2);
560        assert_eq!(
561            row.parity().terms(),
562            &[DetectorTerm::LoopState(LoopStateId(2))]
563        );
564        assert_eq!(row.coords().unwrap().collect::<Vec<_>>(), [11.0, 0.0, 3.0]);
565    }
566
567    #[test]
568    fn preflight_rejects_bad_binding_and_local_slot() {
569        let mut bloq = Bloq::new();
570        let bundle = bloq.add_detector_bundle(DetectorBundle::new(
571            vec![TemplateId(0)],
572            vec![BundleDetector {
573                parity: DetectorParity::from_measurements([BundleMeasurement {
574                    owner: 1,
575                    measurement: 0,
576                }]),
577                coords: None,
578            }],
579        ));
580        let mut node = QuantumNode {
581            detector_bundles: vec![DetectorBundleUse {
582                bundle,
583                instances: vec![],
584                offset: IVec2::ZERO,
585            }],
586            ..QuantumNode::default()
587        };
588        assert_eq!(
589            bloq.node_detector_count(&node),
590            Err(DetectorBundleError::BindingArity {
591                bundle,
592                expected: 1,
593                actual: 0
594            })
595        );
596        node.detector_bundles[0]
597            .instances
598            .push(TemplateInstanceId(0));
599        assert_eq!(
600            bloq.node_detector_count(&node),
601            Err(DetectorBundleError::InvalidLocalOwner {
602                owner: 1,
603                owners: 1
604            })
605        );
606    }
607
608    #[test]
609    fn binding_checker_checks_even_unused_owner_slots() {
610        let mut bloq = Bloq::new();
611        let bundle = bloq.add_detector_bundle(DetectorBundle::new(vec![TemplateId(2)], vec![]));
612        let instance = TemplateInstanceId(4);
613        let node = QuantumNode {
614            detector_bundles: vec![DetectorBundleUse {
615                bundle,
616                instances: vec![instance],
617                offset: IVec2::ZERO,
618            }],
619            ..QuantumNode::default()
620        };
621        assert_eq!(
622            bloq.check_detector_bundle_bindings(&node, |_| None),
623            Err(DetectorBundleError::UnknownBoundInstance {
624                bundle,
625                owner: 0,
626                instance,
627            })
628        );
629        assert_eq!(
630            bloq.check_detector_bundle_bindings(&node, |_| Some(TemplateId(1))),
631            Err(DetectorBundleError::OwnerTemplateMismatch {
632                bundle,
633                owner: 0,
634                instance,
635                expected: TemplateId(2),
636                actual: TemplateId(1),
637            })
638        );
639        assert_eq!(
640            bloq.check_detector_bundle_bindings(&node, |_| Some(TemplateId(2))),
641            Ok(())
642        );
643    }
644}
bloq_ir/ir/detector.rs

bloq_ir/ir/
detector.rs
