Skip to main content

deq_runtime/misc/
validation.rs

1//! Validation of runtime protocol and coordinator payloads.
2
3use crate::bin::{GadgetType, ProbabilityModifier};
4use crate::coordinator::loss_handler::LossHandler;
5use crate::decoder::decoder_features::DecoderFeatures;
6use crate::util::BitVector;
7use tonic::Status;
8
9const REMOTE_REROUTE_INDEX_LIMIT: u64 = 65_536;
10
11/// Validate that a bit vector has exactly the bytes required by its declared
12/// number of bits.
13pub fn validate_data_len(bit_vector: &BitVector, name: &str) -> Result<(), String> {
14    let required = crate::misc::bit_vector::bit_vector_len(bit_vector.size);
15    if bit_vector.data.len() != required {
16        Err(format!(
17            "{name} data length ({}) does not match required length ({required}) for {} bits",
18            bit_vector.data.len(),
19            bit_vector.size
20        ))
21    } else {
22        Ok(())
23    }
24}
25
26pub fn validate_outcomes(outcomes: &BitVector, loss_mask: Option<&BitVector>, expected_size: u64) -> Result<(), String> {
27    validate_data_len(outcomes, "outcomes")?;
28    if outcomes.size != expected_size {
29        return Err(format!(
30            "outcomes size {} does not match gadget measurement count {expected_size}",
31            outcomes.size
32        ));
33    }
34    if let Some(loss_mask) = loss_mask {
35        validate_data_len(loss_mask, "loss_mask")?;
36        if outcomes.size != loss_mask.size {
37            return Err(format!(
38                "loss_mask size {} does not match outcomes size {}",
39                loss_mask.size, outcomes.size
40            ));
41        }
42    }
43    Ok(())
44}
45
46/// Validate the shape, indices, and values of a probability modifier for an
47/// error model with `error_count` errors.
48pub fn validate_probability_modifier(modifier: &ProbabilityModifier, error_count: usize) -> Result<(), String> {
49    if !modifier.probabilities.is_empty() && modifier.probabilities.len() != error_count {
50        return Err(format!(
51            "dense probability modifier has length {}, expected 0 or {error_count}",
52            modifier.probabilities.len()
53        ));
54    }
55    if modifier.sparse_indices.len() != modifier.sparse_probabilities.len() {
56        return Err(format!(
57            "sparse probability modifier has {} indices but {} probabilities",
58            modifier.sparse_indices.len(),
59            modifier.sparse_probabilities.len()
60        ));
61    }
62    for &index in &modifier.sparse_indices {
63        if index >= error_count as u64 {
64            return Err(format!(
65                "sparse probability modifier index {index} is outside [0, {error_count})"
66            ));
67        }
68    }
69    for &probability in modifier.probabilities.iter().chain(modifier.sparse_probabilities.iter()) {
70        if !probability.is_finite() || !(0.0..=1.0).contains(&probability) {
71            return Err(format!("probability modifier value must lie in [0, 1], got {probability}"));
72        }
73    }
74    Ok(())
75}
76
77fn remote_reroute_position(index: u64, kind: &str) -> Result<usize, String> {
78    if index >= REMOTE_REROUTE_INDEX_LIMIT {
79        return Err(format!(
80            "{kind} reroute index {index} must be less than {REMOTE_REROUTE_INDEX_LIMIT}"
81        ));
82    }
83    usize::try_from(index).map_err(|_| format!("{kind} reroute index does not fit usize"))
84}
85
86fn validate_remote_reroutes(indices: impl IntoIterator<Item = u64>, kind: &str) -> Result<(), String> {
87    for index in indices {
88        remote_reroute_position(index, kind)?;
89    }
90    Ok(())
91}
92
93pub(crate) fn validate_check_model_reroutes(
94    modifier: Option<&crate::bin::check_model::CheckModelModifier>,
95) -> Result<(), String> {
96    validate_remote_reroutes(
97        modifier
98            .into_iter()
99            .flat_map(|modifier| &modifier.reroute_remote_gadgets)
100            .map(|reroute| reroute.remote_gadget_index),
101        "remote gadget",
102    )
103}
104
105pub(crate) fn validate_error_model_reroutes(
106    modifier: Option<&crate::bin::error_model::ErrorModelModifier>,
107) -> Result<(), String> {
108    validate_remote_reroutes(
109        modifier
110            .into_iter()
111            .flat_map(|modifier| &modifier.reroute_remote_check_models)
112            .map(|reroute| reroute.remote_check_model_index),
113        "remote check model",
114    )
115}
116
117fn apply_remote_reroutes<T>(
118    base: &[T],
119    reroutes: impl IntoIterator<Item = (u64, Option<T>)>,
120    kind: &str,
121) -> Result<Vec<Option<T>>, String>
122where
123    T: Clone,
124{
125    let mut modified: Vec<_> = base.iter().cloned().map(Some).collect();
126    for (index, value) in reroutes {
127        let index = remote_reroute_position(index, kind)?;
128        if index >= modified.len() {
129            modified.resize_with(index + 1, || None);
130        }
131        modified[index] = value;
132    }
133    Ok(modified)
134}
135
136pub(crate) fn apply_check_model_reroutes(
137    base: &[crate::bin::check_model_type::RemoteGadget],
138    modifier: Option<&crate::bin::check_model::CheckModelModifier>,
139) -> Result<Vec<Option<crate::bin::check_model_type::RemoteGadget>>, String> {
140    apply_remote_reroutes(
141        base,
142        modifier
143            .into_iter()
144            .flat_map(|modifier| &modifier.reroute_remote_gadgets)
145            .map(|reroute| (reroute.remote_gadget_index, reroute.value.clone())),
146        "remote gadget",
147    )
148}
149
150pub(crate) fn apply_error_model_reroutes(
151    base: &[crate::bin::error_model_type::RemoteCheckModel],
152    modifier: Option<&crate::bin::error_model::ErrorModelModifier>,
153) -> Result<Vec<Option<crate::bin::error_model_type::RemoteCheckModel>>, String> {
154    apply_remote_reroutes(
155        base,
156        modifier
157            .into_iter()
158            .flat_map(|modifier| &modifier.reroute_remote_check_models)
159            .map(|reroute| (reroute.remote_check_model_index, reroute.value.clone())),
160        "remote check model",
161    )
162}
163
164impl LossHandler {
165    /// Validate that the decoder capabilities support this loss strategy for
166    /// the supplied gadget library.
167    pub fn validate_capability(self, gadget_types: &[GadgetType], features: DecoderFeatures) -> Result<(), Status> {
168        if self.hands_off_to_decoder()
169            && gadget_types.iter().any(|gadget_type| gadget_type.loss_model.is_some())
170            && !features.contains(DecoderFeatures::LOSS)
171        {
172            return Err(Status::failed_precondition(
173                "loss_strategy handoff requires a decoder with structured loss support for this library",
174            ));
175        }
176        Ok(())
177    }
178}
179
180use crate::decoder::blackbox_decoder::{DecodingHypergraph, LossInfo, ParityFactor};
181
182/// Validate that every edge returned by a decoder belongs to its hypergraph.
183pub fn validate_parity_factor(parity_factor: ParityFactor, edge_count: usize) -> Result<ParityFactor, String> {
184    if let Some(&edge) = parity_factor
185        .subgraph
186        .iter()
187        .find(|&&edge| usize::try_from(edge).map_or(true, |edge| edge >= edge_count))
188    {
189        return Err(format!(
190            "decoder returned edge {edge}, but the hypergraph has {edge_count} edges"
191        ));
192    }
193    Ok(parity_factor)
194}
195
196/// Validate hyperedge probabilities, vertex references, and observable indices.
197///
198/// # Errors
199/// Rejects invalid probabilities, out-of-range or duplicate vertices, and
200/// duplicate observable indices. Observable labels are otherwise unrestricted.
201pub fn validate_hypergraph(hypergraph: &DecodingHypergraph) -> Result<(), String> {
202    for (edge, hyperedge) in hypergraph.hyperedges.iter().enumerate() {
203        if let Some(flips) = &hyperedge.observable_flips {
204            let mut indices = hashbrown::HashSet::with_capacity(flips.indices.len());
205            if flips.indices.iter().any(|&index| !indices.insert(index)) {
206                return Err(format!("hyperedge {edge} observable indices must be unique"));
207            }
208        }
209        if !hyperedge.probability.is_finite() || !(0.0..=1.0).contains(&hyperedge.probability) {
210            return Err(format!(
211                "hyperedge {edge} probability must lie in [0, 1], got {}",
212                hyperedge.probability
213            ));
214        }
215        let mut vertices = hashbrown::HashSet::with_capacity(hyperedge.vertices.len());
216        for &vertex in &hyperedge.vertices {
217            if vertex >= hypergraph.vertex_num {
218                return Err(format!(
219                    "hyperedge {edge} contains vertex {vertex}, outside [0, {})",
220                    hypergraph.vertex_num
221                ));
222            }
223            if !vertices.insert(vertex) {
224                return Err(format!("hyperedge {edge} contains vertex {vertex} more than once"));
225            }
226        }
227    }
228    Ok(())
229}
230
231/// Validate a syndrome's storage and size against a hypergraph vertex count.
232pub fn validate_syndrome(syndrome: &BitVector, vertex_num: u64) -> Result<(), String> {
233    validate_data_len(syndrome, "syndrome")?;
234    if syndrome.size != vertex_num {
235        return Err(format!(
236            "syndrome size {} does not match hypergraph vertex count {vertex_num}",
237            syndrome.size
238        ));
239    }
240    Ok(())
241}
242
243/// Validate loaded-graph reweight indices, probabilities, and uniqueness.
244pub fn validate_reweights(reweights: &[(u64, f64)], edge_count: usize) -> Result<(), String> {
245    let mut seen = hashbrown::HashSet::with_capacity(reweights.len());
246    for &(edge, probability) in reweights {
247        if usize::try_from(edge).map_or(true, |edge| edge >= edge_count) {
248            return Err(format!(
249                "reweighted edge {edge} is outside loaded hypergraph with {edge_count} edges"
250            ));
251        }
252        if !probability.is_finite() || !(0.0..=1.0).contains(&probability) {
253            return Err(format!(
254                "reweighted edge {edge} probability must lie in [0, 1], got {probability}"
255            ));
256        }
257        if !seen.insert(edge) {
258            return Err(format!("reweighted edge {edge} is assigned more than once"));
259        }
260    }
261    Ok(())
262}
263
264/// Validate structured loss sites, references, uniqueness, and acyclicity.
265pub fn validate_loss(loss: Option<&LossInfo>, edge_count: usize) -> Result<(), String> {
266    let Some(loss) = loss else {
267        return Ok(());
268    };
269    let mut indegree = vec![0usize; loss.sites.len()];
270    let mut children = vec![Vec::new(); loss.sites.len()];
271    for (site_index, site) in loss.sites.iter().enumerate() {
272        if !site.probability.is_finite() || !(0.0..=1.0).contains(&site.probability) {
273            return Err(format!(
274                "loss site {site_index} probability must lie in [0, 1], got {}",
275                site.probability
276            ));
277        }
278        for (field, edges) in [
279            ("source_edges", &site.source_edges),
280            ("continuation_edges", &site.continuation_edges),
281        ] {
282            let mut seen = hashbrown::HashSet::with_capacity(edges.len());
283            for &edge in edges {
284                if usize::try_from(edge).map_or(true, |edge| edge >= edge_count) {
285                    return Err(format!(
286                        "loss site {site_index} {field} contains edge {edge}, outside [0, {edge_count})"
287                    ));
288                }
289                if !seen.insert(edge) {
290                    return Err(format!("loss site {site_index} {field} contains edge {edge} more than once"));
291                }
292            }
293        }
294        let mut seen_children = hashbrown::HashSet::with_capacity(site.children.len());
295        for &child in &site.children {
296            let Ok(child_index) = usize::try_from(child) else {
297                return Err(format!(
298                    "loss site {site_index} contains child {child}, outside [0, {})",
299                    loss.sites.len()
300                ));
301            };
302            let Some(degree) = indegree.get_mut(child_index) else {
303                return Err(format!(
304                    "loss site {site_index} contains child {child}, outside [0, {})",
305                    loss.sites.len()
306                ));
307            };
308            if !seen_children.insert(child_index) {
309                return Err(format!("loss site {site_index} contains child {child} more than once"));
310            }
311            *degree += 1;
312            children[site_index].push(child_index);
313        }
314        let mut seen_heralds = hashbrown::HashSet::with_capacity(site.heralds.len());
315        for &herald in &site.heralds {
316            if !seen_heralds.insert(herald) {
317                return Err(format!("loss site {site_index} contains herald {herald} more than once"));
318            }
319        }
320    }
321    let mut frontier: Vec<usize> = indegree
322        .iter()
323        .enumerate()
324        .filter_map(|(site, &degree)| (degree == 0).then_some(site))
325        .collect();
326    let mut visited = 0usize;
327    while let Some(site_index) = frontier.pop() {
328        visited += 1;
329        for &child_index in &children[site_index] {
330            indegree[child_index] -= 1;
331            if indegree[child_index] == 0 {
332                frontier.push(child_index);
333            }
334        }
335    }
336    if visited != loss.sites.len() {
337        return Err("loss site children graph contains a cycle".to_string());
338    }
339    Ok(())
340}
341
342#[cfg(test)]
343mod tests {
344    use super::*;
345
346    #[test]
347    fn observable_metadata_preserves_presence_and_sparse_labels_on_the_wire() {
348        use crate::decoder::blackbox_decoder::{Hyperedge, ObservableFlips};
349        use prost::Message;
350
351        let mut graphs = vec![];
352        for indices in [None, Some(vec![]), Some(vec![u64::MAX, 7, 0])] {
353            let graph = DecodingHypergraph {
354                vertex_num: 1,
355                hyperedges: vec![Hyperedge {
356                    vertices: vec![0],
357                    probability: 0.0,
358                    observable_flips: indices.clone().map(|indices| ObservableFlips { indices }),
359                }],
360            };
361            validate_hypergraph(&graph).unwrap();
362            let wire = graph.encode_to_vec();
363            let restored = DecodingHypergraph::decode(wire.as_slice()).unwrap();
364            assert_eq!(restored, graph);
365            assert_eq!(
366                restored.hyperedges[0].observable_flips.as_ref().map(|flips| &flips.indices),
367                indices.as_ref()
368            );
369            graphs.push(graph);
370        }
371        assert_ne!(graphs[0], graphs[1], "unknown effects must not equal known-empty effects");
372        assert_ne!(graphs[1], graphs[2]);
373    }
374
375    #[test]
376    fn observable_metadata_rejects_duplicate_labels() {
377        use crate::decoder::blackbox_decoder::{Hyperedge, ObservableFlips};
378
379        let graph = DecodingHypergraph {
380            vertex_num: 1,
381            hyperedges: vec![Hyperedge {
382                vertices: vec![0],
383                probability: 0.1,
384                observable_flips: Some(ObservableFlips { indices: vec![7, 1, 7] }),
385            }],
386        };
387        assert_eq!(
388            validate_hypergraph(&graph).unwrap_err(),
389            "hyperedge 0 observable indices must be unique"
390        );
391    }
392
393    #[test]
394    fn probability_modifier_validation_rejects_malformed_inputs() {
395        let dense_wrong_length = ProbabilityModifier {
396            probabilities: vec![0.1],
397            ..Default::default()
398        };
399        assert!(validate_probability_modifier(&dense_wrong_length, 2).is_err());
400
401        let sparse_length_mismatch = ProbabilityModifier {
402            sparse_indices: vec![0, 1],
403            sparse_probabilities: vec![0.2],
404            ..Default::default()
405        };
406        assert!(validate_probability_modifier(&sparse_length_mismatch, 2).is_err());
407
408        let sparse_out_of_range = ProbabilityModifier {
409            sparse_indices: vec![2],
410            sparse_probabilities: vec![0.2],
411            ..Default::default()
412        };
413        assert!(validate_probability_modifier(&sparse_out_of_range, 2).is_err());
414
415        let invalid_probability = ProbabilityModifier {
416            probabilities: vec![0.1, f64::NAN],
417            ..Default::default()
418        };
419        assert!(validate_probability_modifier(&invalid_probability, 2).is_err());
420    }
421
422    #[test]
423    fn remote_reroutes_extend_within_the_spec_bound() {
424        let modifier = crate::bin::check_model::CheckModelModifier {
425            reroute_remote_gadgets: vec![crate::bin::check_model::check_model_modifier::RerouteRemoteGadget {
426                remote_gadget_index: 5,
427                value: Some(crate::bin::check_model_type::RemoteGadget::default()),
428            }],
429        };
430
431        let modified = apply_check_model_reroutes(&[], Some(&modifier)).unwrap();
432
433        assert_eq!(modified.len(), 6);
434        assert!(modified[5].is_some());
435    }
436
437    #[test]
438    fn remote_reroutes_reject_indices_at_the_spec_bound() {
439        let check_modifier = crate::bin::check_model::CheckModelModifier {
440            reroute_remote_gadgets: vec![crate::bin::check_model::check_model_modifier::RerouteRemoteGadget {
441                remote_gadget_index: REMOTE_REROUTE_INDEX_LIMIT,
442                value: None,
443            }],
444        };
445        let error_modifier = crate::bin::error_model::ErrorModelModifier {
446            reroute_remote_check_models: vec![crate::bin::error_model::error_model_modifier::RerouteRemoteCheckModel {
447                remote_check_model_index: REMOTE_REROUTE_INDEX_LIMIT,
448                value: None,
449            }],
450            ..Default::default()
451        };
452
453        assert!(apply_check_model_reroutes(&[], Some(&check_modifier)).is_err());
454        assert!(apply_error_model_reroutes(&[], Some(&error_modifier)).is_err());
455    }
456
457    #[test]
458    fn handoff_requires_loss_support_only_for_loss_bearing_libraries() {
459        assert!(
460            LossHandler::Handoff
461                .validate_capability(&[GadgetType::default()], DecoderFeatures::empty())
462                .is_ok()
463        );
464        let loss_bearing = GadgetType {
465            loss_model: Some(crate::bin::gadget_type::LossModel::default()),
466            ..Default::default()
467        };
468
469        let error = LossHandler::Handoff
470            .validate_capability(std::slice::from_ref(&loss_bearing), DecoderFeatures::empty())
471            .unwrap_err();
472
473        assert_eq!(error.code(), tonic::Code::FailedPrecondition);
474        assert!(
475            LossHandler::Handoff
476                .validate_capability(&[loss_bearing], DecoderFeatures::LOSS)
477                .is_ok()
478        );
479    }
480}