Skip to main content

deq_runtime/misc/
relative_program.rs

1use crate::bin::gadget::Connector;
2use hashbrown::HashMap;
3
4#[derive(Debug, Clone, Hash, PartialEq, Eq)]
5pub struct ExpandedGadget {
6    pub gid: u64,
7    pub gtype: u64,
8    pub inputs: Vec<Option<Connector>>,
9    pub outputs: Vec<Option<Connector>>,
10    /// binding check model
11    pub check_model: Option<ExpandedCheckModel>,
12    /// attached error models
13    pub error_models: Vec<ExpandedErrorModel>,
14}
15
16#[derive(Debug, Clone, Hash, PartialEq, Eq)]
17pub struct ExpandedCheckModel {
18    pub cid: u64,
19    pub ctype: u64,
20    pub remote_gadgets: Vec<Option<u64>>,
21    pub count_checks: usize,
22}
23
24#[derive(Debug, Clone, Hash, PartialEq, Eq)]
25pub struct ExpandedErrorModel {
26    pub eid: u64,
27    pub etype: u64,
28    pub remote_check_models: Vec<Option<u64>>,
29}
30
31/// a program that is agnostic to the global ids (gid, cid, eid): each gadget,
32/// check model and error model is assigned by the order they are instantiated
33/// and thus as long as the input program sequence is the same, the relative-id
34/// program is the same; this is useful to get a cached or prepared decoder
35/// instance
36#[derive(Debug, Clone, Hash, PartialEq, Eq)]
37pub struct RelativeProgram {
38    pub local_gadgets: Vec<ExpandedGadget>,
39    pub count_checks: usize,
40}
41
42#[derive(Clone, Debug, Default)]
43pub struct RelativeMapping {
44    // local ids starts from 0
45    pub local_gid_of: HashMap<u64, usize>,
46    pub global_gid_of: Vec<u64>,
47    pub local_cid_of: HashMap<u64, usize>,
48    pub global_cid_of: Vec<u64>,
49    pub local_eid_of: HashMap<u64, usize>,
50    pub global_eid_of: Vec<u64>,
51    pub local_gid_of_local_eid: Vec<usize>,
52    // the following fields are useful for calculating the syndrome
53    pub start_indices: Vec<usize>,
54    // from local_gid to the eid bias, useful to locate the error models attached to a gadget
55    pub local_eid_bias: Vec<usize>,
56}
57
58impl RelativeProgram {
59    pub fn new(expanded_gadgets: &[ExpandedGadget]) -> (RelativeProgram, RelativeMapping) {
60        let mut mapping: RelativeMapping = Default::default();
61        let mut local_gadgets = Vec::with_capacity(expanded_gadgets.len());
62        let mut count_checks = 0;
63        for gadget in expanded_gadgets.iter() {
64            let local_gid = mapping.global_gid_of.len();
65            let check_model = gadget.check_model.as_ref().map(|check_model| {
66                let local_cid = mapping.global_cid_of.len();
67                mapping.local_cid_of.insert(check_model.cid, local_cid);
68                mapping.global_cid_of.push(check_model.cid);
69                mapping.start_indices.push(count_checks);
70                count_checks += check_model.count_checks;
71                ExpandedCheckModel {
72                    cid: local_cid as u64,
73                    ctype: check_model.ctype,
74                    // translate to local index later
75                    remote_gadgets: check_model.remote_gadgets.clone(),
76                    count_checks: check_model.count_checks,
77                }
78            });
79            // Track eid bias per gadget (indexed by local_gid, not local_cid)
80            // so that error-only gadgets (no check_model) are also covered.
81            mapping.local_eid_bias.push(mapping.global_eid_of.len());
82            let error_models = gadget
83                .error_models
84                .iter()
85                .map(|error_model| {
86                    let local_eid = mapping.global_eid_of.len();
87                    mapping.local_eid_of.insert(error_model.eid, local_eid);
88                    mapping.global_eid_of.push(error_model.eid);
89                    mapping.local_gid_of_local_eid.push(local_gid);
90                    ExpandedErrorModel {
91                        eid: local_eid as u64,
92                        etype: error_model.etype,
93                        // translate to local index later
94                        remote_check_models: error_model.remote_check_models.clone(),
95                    }
96                })
97                .collect();
98            mapping.local_gid_of.insert(gadget.gid, local_gid);
99            mapping.global_gid_of.push(gadget.gid);
100            local_gadgets.push(ExpandedGadget {
101                gid: local_gid as u64,
102                gtype: gadget.gtype,
103                inputs: gadget.inputs.clone(),   // translate to local index later
104                outputs: gadget.outputs.clone(), //  translate to local index later
105                check_model,
106                error_models,
107            });
108        }
109        // now we have constructed all the local indices, we can update the indices
110        for local_gadget in local_gadgets.iter_mut() {
111            for connector in local_gadget.inputs.iter_mut().chain(local_gadget.outputs.iter_mut()) {
112                if let Some(&mut Connector { gid: global_gid, port }) = connector.as_mut() {
113                    if let Some(local_gid) = mapping.local_gid_of.get(&global_gid) {
114                        connector.replace(Connector {
115                            gid: *local_gid as u64,
116                            port,
117                        });
118                    } else {
119                        *connector = None; // drop unknown global index
120                    }
121                }
122            }
123            if let Some(check_model) = local_gadget.check_model.as_mut() {
124                for gid in check_model.remote_gadgets.iter_mut() {
125                    if let Some(global_gid) = gid.as_mut() {
126                        if let Some(local_gid) = mapping.local_gid_of.get(global_gid) {
127                            gid.replace(*local_gid as u64);
128                        } else {
129                            *gid = None; // drop unknown global index
130                        }
131                    }
132                }
133            }
134            for error_model in local_gadget.error_models.iter_mut() {
135                for cid in error_model.remote_check_models.iter_mut() {
136                    if let Some(global_cid) = cid.as_mut() {
137                        if let Some(local_cid) = mapping.local_cid_of.get(global_cid) {
138                            cid.replace(*local_cid as u64);
139                        } else {
140                            *cid = None;
141                        }
142                    }
143                }
144            }
145        }
146        let program = RelativeProgram {
147            local_gadgets,
148            count_checks,
149        };
150        (program, mapping)
151    }
152}