bloq_graph/
action.rs

1//! Classical measurements, expressions, feedback, and branch actions.
2
3use bloq_utils::{Direction, PauliBasis};
4use glam::IVec3;
5use std::collections::BTreeSet;
6
7/// A binary operator in an action expression.
8#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
9pub enum BinaryOp {
10    /// Logical XOR.
11    Xor,
12    /// Logical AND.
13    And,
14    /// Logical OR.
15    Or,
16}
17
18impl BinaryOp {
19    /// Precedence level: higher number = tighter binding.
20    pub const fn precedence(&self) -> u8 {
21        match self {
22            BinaryOp::Or => 1,
23            BinaryOp::Xor => 2,
24            BinaryOp::And => 3,
25        }
26    }
27
28    fn symbol(&self) -> &'static str {
29        match self {
30            BinaryOp::Xor => "^",
31            BinaryOp::And => "&",
32            BinaryOp::Or => "|",
33        }
34    }
35}
36
37/// A boolean expression tree over measurement outcome variables.
38#[derive(Debug, Clone, PartialEq, Eq, Hash)]
39pub enum Expr {
40    /// A named variable reference (e.g., a measurement outcome name).
41    Var(String),
42    /// Logical NOT of a sub-expression.
43    Not(Box<Expr>),
44    /// A binary operation combining two sub-expressions.
45    Binary(BinaryOp, Box<Expr>, Box<Expr>),
46}
47
48impl Expr {
49    pub(crate) fn negated(self) -> Self {
50        match self {
51            Self::Not(inner) => *inner,
52            expr => Self::Not(Box::new(expr)),
53        }
54    }
55}
56
57impl std::fmt::Display for Expr {
58    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
59        match self {
60            Expr::Var(name) => write!(f, "{}", name),
61            Expr::Not(expr) => {
62                if matches!(expr.as_ref(), Expr::Binary(..)) {
63                    write!(f, "!({})", expr)
64                } else {
65                    write!(f, "!{}", expr)
66                }
67            }
68            Expr::Binary(op, lhs, rhs) => {
69                let prec = op.precedence();
70                // Parenthesize LHS if it has strictly lower precedence
71                if needs_parens(lhs, prec, true) {
72                    write!(f, "({})", lhs)?;
73                } else {
74                    write!(f, "{}", lhs)?;
75                }
76                write!(f, " {} ", op.symbol())?;
77                // Parenthesize RHS if lower-or-equal precedence (left-assoc)
78                if needs_parens(rhs, prec, false) {
79                    write!(f, "({})", rhs)
80                } else {
81                    write!(f, "{}", rhs)
82                }
83            }
84        }
85    }
86}
87
88/// Returns true if the child expression needs parentheses given the parent's precedence.
89/// `is_left` indicates whether the child is the left operand (left-assoc: left child
90/// only needs parens if strictly lower precedence; right child needs parens if
91/// lower-or-equal to preserve associativity).
92fn needs_parens(expr: &Expr, parent_prec: u8, is_left: bool) -> bool {
93    if let Expr::Binary(child_op, _, _) = expr {
94        let child_prec = child_op.precedence();
95        if is_left {
96            child_prec < parent_prec
97        } else {
98            child_prec <= parent_prec
99        }
100    } else {
101        false
102    }
103}
104
105/// A single Pauli correction site for an [`Action::Feedback`].
106#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
107pub struct FeedbackTarget {
108    /// Pauli basis of the correction to apply.
109    pub pauli: PauliBasis,
110    /// Block position the correction acts on.
111    pub target: IVec3,
112    /// A wire leaving `target`, in that endpoint's Pauli frame. `None` selects
113    /// the first outgoing temporal wire, then the last incoming temporal wire,
114    /// then a sole spatial wire, ordered by the neighboring source position.
115    pub direction: Option<Direction>,
116}
117
118/// The target of a measurement action — either a node or a specific edge.
119#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
120pub enum MeasureTarget {
121    /// Measurement on a node position.
122    Node(IVec3),
123    /// Measurement on an edge identified by source position and direction.
124    Edge {
125        /// Canonical source endpoint of the measured edge.
126        src: IVec3,
127        /// Direction from `src` to the other endpoint.
128        dir: Direction,
129    },
130}
131
132/// A classical-control action attached to a block graph program.
133///
134/// Actions encode classical control flow driven by measurement outcomes:
135/// variable definitions, conditional feedback, selective resolution,
136/// named structural branching, and post-selection via discard conditions.
137#[derive(Debug, Clone, PartialEq, Eq)]
138pub enum Action {
139    /// Define a named boolean variable from an expression.
140    Let {
141        /// Name bound by the action.
142        name: String,
143        /// Boolean expression assigned to `name`.
144        expr: Expr,
145    },
146    /// Bind a measurement outcome variable to a node or edge.
147    Measure {
148        /// Node or edge whose outcome is recorded.
149        target: MeasureTarget,
150        /// Name assigned to the measurement record.
151        name: String,
152    },
153    /// Discard the shot if the expression evaluates to true (post-selection).
154    DiscardIf(Expr),
155    /// Resolve a selective block at `target` using `condition`.
156    Resolve {
157        /// Selective block to resolve.
158        target: IVec3,
159        /// Boolean expression selecting the block basis.
160        condition: Expr,
161    },
162    /// Resolve the explicit branch region internally keyed by `target`.
163    /// [`BlockGraph::to_blog_text`](crate::BlockGraph::to_blog_text) writes its
164    /// public name because an action alone does not carry that name.
165    Branch {
166        /// Internal key position of the branch region.
167        target: IVec3,
168        /// Boolean expression selecting the branch choice.
169        condition: Expr,
170    },
171    /// Apply Pauli feedback to one or more targets, optionally gated on a condition.
172    Feedback {
173        /// Pauli correction sites affected by the action.
174        targets: Vec<FeedbackTarget>,
175        /// Optional Boolean guard; absence means unconditional feedback.
176        condition: Option<Expr>,
177    },
178}
179
180impl Action {
181    /// Boolean variable names consumed by this action, in sorted order.
182    pub fn referenced_names(&self) -> BTreeSet<&str> {
183        fn collect<'a>(expr: &'a Expr, names: &mut BTreeSet<&'a str>) {
184            match expr {
185                Expr::Var(name) => {
186                    names.insert(name);
187                }
188                Expr::Not(expr) => collect(expr, names),
189                Expr::Binary(_, left, right) => {
190                    collect(left, names);
191                    collect(right, names);
192                }
193            }
194        }
195        let mut names = BTreeSet::new();
196        let expression = match self {
197            Self::Let { expr, .. } | Self::DiscardIf(expr) => Some(expr),
198            Self::Resolve { condition, .. } | Self::Branch { condition, .. } => Some(condition),
199            Self::Feedback { condition, .. } => condition.as_ref(),
200            Self::Measure { .. } => None,
201        };
202        if let Some(expression) = expression {
203            collect(expression, &mut names);
204        }
205        names
206    }
207
208    pub(crate) fn try_with_orientation(
209        &self,
210        orientation: crate::ModuleOrientation,
211    ) -> Result<Self, crate::BlockGraphError> {
212        self.try_map_targets(
213            |position| orientation.try_rotate_position(position),
214            |direction| orientation.rotate_direction(direction),
215        )
216    }
217
218    /// Returns a copy of the action with every position translated by `offset`.
219    ///
220    /// # Panics
221    ///
222    /// Panics if a translated position exceeds the coordinate range. Use
223    /// [`try_with_shift`](Self::try_with_shift) for untrusted offsets.
224    pub fn with_shift(&self, offset: impl Into<IVec3>) -> Self {
225        self.try_with_shift(offset)
226            .expect("shifted action positions must fit in the i32 coordinate range")
227    }
228
229    /// Returns a copy of the action with every position translated by `offset`.
230    ///
231    /// # Errors
232    ///
233    /// Returns [`crate::BlockGraphError::CoordinateOverflow`] if a translated
234    /// position or measurement-edge endpoint exceeds the coordinate range.
235    pub fn try_with_shift(&self, offset: impl Into<IVec3>) -> Result<Self, crate::BlockGraphError> {
236        let offset = offset.into();
237        self.try_map_targets(
238            |position| crate::checked_add_position(position, offset),
239            |direction| direction,
240        )
241    }
242
243    fn try_map_targets(
244        &self,
245        position: impl Fn(IVec3) -> Result<IVec3, crate::BlockGraphError>,
246        direction: impl Fn(Direction) -> Direction,
247    ) -> Result<Self, crate::BlockGraphError> {
248        let mut action = self.clone();
249        match &mut action {
250            Action::Resolve { target, .. } | Action::Branch { target, .. } => {
251                *target = position(*target)?;
252            }
253            Action::Feedback { targets, .. } => {
254                for target in targets {
255                    target.target = position(target.target)?;
256                    target.direction = target.direction.map(&direction);
257                    if let Some(dir) = target.direction {
258                        crate::checked_add_position(target.target, dir.to_ivec3())?;
259                    }
260                }
261            }
262            Action::Measure { target, .. } => match target {
263                MeasureTarget::Node(target) => *target = position(*target)?,
264                MeasureTarget::Edge { src, dir } => {
265                    *src = position(*src)?;
266                    *dir = direction(*dir);
267                    crate::checked_add_position(*src, dir.to_ivec3())?;
268                }
269            },
270            Action::Let { .. } | Action::DiscardIf(..) => {}
271        }
272        Ok(action)
273    }
274
275    pub(crate) fn display_with_ids(&self, p2i: impl Fn(IVec3) -> Option<u32>) -> String {
276        let target_str = |target| {
277            if let Some(id) = p2i(target) {
278                return id.to_string();
279            }
280            target.to_string()
281        };
282        match self {
283            Action::Let { name, expr } => format!("{name} = {expr}"),
284            Action::Measure { target, name } => {
285                let target_str_val = match target {
286                    MeasureTarget::Node(pos) => target_str(*pos),
287                    MeasureTarget::Edge { src, dir } => {
288                        format!("{} -> {}", target_str(*src), dir)
289                    }
290                };
291                format!("{name} = measure {target_str_val}")
292            }
293            Action::DiscardIf(expr) => format!("discard if {expr}"),
294            Action::Resolve { target, condition } | Action::Branch { target, condition } => {
295                format!("resolve {} if {}", target_str(*target), condition)
296            }
297            Action::Feedback { targets, condition } => {
298                let ts = targets
299                    .iter()
300                    .map(|t| match t.direction {
301                        Some(dir) => format!("{} {} -> {}", t.pauli, target_str(t.target), dir),
302                        None => format!("{} {}", t.pauli, target_str(t.target)),
303                    })
304                    .collect::<Vec<_>>()
305                    .join(", ");
306                if let Some(cond) = condition {
307                    format!("feedback {} if {}", ts, cond)
308                } else {
309                    format!("feedback {}", ts)
310                }
311            }
312        }
313    }
314}
315
316impl std::fmt::Display for Action {
317    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
318        f.write_str(&self.display_with_ids(|_| None))
319    }
320}
321
322#[cfg(test)]
323mod tests {
324    use super::*;
325
326    #[test]
327    fn checked_shift_rejects_overflowing_measurement_edge() {
328        let action = Action::Measure {
329            target: MeasureTarget::Edge {
330                src: IVec3::new(i32::MAX - 1, 0, 0),
331                dir: Direction::XPLUS,
332            },
333            name: "m".into(),
334        };
335
336        assert!(matches!(
337            action.try_with_shift(IVec3::X),
338            Err(crate::BlockGraphError::CoordinateOverflow { .. })
339        ));
340    }
341
342    #[test]
343    fn expression_display_preserves_precedence_and_associativity() -> Result<(), crate::ParseError>
344    {
345        for (source, expected) in [
346            ("a | b & c", "a | b & c"),
347            ("(a | b) & c", "(a | b) & c"),
348            ("!(a | b)", "!(a | b)"),
349            ("!a", "!a"),
350            ("a ^ (b ^ c)", "a ^ (b ^ c)"),
351            ("(a ^ b) ^ c", "a ^ b ^ c"),
352        ] {
353            let actions = crate::parse_actions(&format!("result = {source}"), |_, _| None)?;
354            let [Action::Let { expr, .. }] = actions.as_slice() else {
355                unreachable!()
356            };
357            assert_eq!(expr.to_string(), expected, "{source}");
358        }
359        Ok::<_, crate::ParseError>(())
360    }
361
362    #[test]
363    fn branch_display_and_shift_preserve_condition() {
364        let action = Action::Branch {
365            target: IVec3::new(1, 2, 3),
366            condition: Expr::Var("m".into()),
367        };
368
369        assert_eq!(action.to_string(), "resolve [1, 2, 3] if m");
370        assert_eq!(
371            action.with_shift(IVec3::new(4, 5, 6)),
372            Action::Branch {
373                target: IVec3::new(5, 7, 9),
374                condition: Expr::Var("m".into()),
375            }
376        );
377    }
378}
bloq_graph/action.rs

bloq_graph/
action.rs
