bloq_ir/
membership.rs

1//! Symbolic input domains for conditional component registration.
2use crate::{
3    Bloq, BloqNodeId, ClassicalExpr, ClassicalNode, FxMap, NodeTemplateInstanceMergeError as Error,
4    ObservableOutput, SubGraph, ValueRef,
5};
6use bloq_utils::boolean::{
7    BooleanDecisionDiagram, BooleanLimits, BooleanOp, DECISION_FALSE, DECISION_TRUE, DecisionId,
8};
9
10/// Cached Boolean queries over one immutable graph level.
11///
12/// Shared Compute ancestry preserves correlated guards. The graph must be
13/// acyclic and predicates must name existing bit producers. The borrow prevents
14/// graph edits from invalidating retained predicates and query results.
15#[derive(Debug)]
16pub struct PredicateAnalysis<'a> {
17    graph: &'a SubGraph,
18    diagram: BooleanDecisionDiagram,
19    memo: FxMap<ValueRef, DecisionId>,
20    variables: FxMap<ValueRef, usize>,
21    inputs: FxMap<BloqNodeId, FxMap<u32, ValueRef>>,
22    implications: FxMap<(Option<ValueRef>, ValueRef), bool>,
23    overlaps: FxMap<(Option<ValueRef>, Option<ValueRef>), bool>,
24}
25
26/// One exhaustive, mutually exclusive member choice and its known guard inputs.
27pub(crate) struct QuantumSelection {
28    pub input: u32,
29    pub values: FxMap<u32, bool>,
30}
31
32impl<'a> PredicateAnalysis<'a> {
33    /// Recognize a component whose member guards partition the input domain.
34    /// Side-table guards must be fixed by each choice; independent selections
35    /// still require pinning before timing or seam edits.
36    pub(crate) fn quantum_selections(
37        &mut self,
38        node: BloqNodeId,
39    ) -> Result<Option<Vec<QuantumSelection>>, Error> {
40        let quantum = self.graph[node].expect_quantum();
41        let mut choices = Vec::new();
42        let mut covered = DECISION_FALSE;
43        for guard in &quantum.guards {
44            if guard.instances.is_empty() {
45                continue;
46            }
47            let value = self.lower(Eval::Input(node, guard.input))?;
48            if value == DECISION_FALSE || choices.iter().any(|&(_, old)| old == value) {
49                continue;
50            }
51            if self.diagram.apply(BooleanOp::And, covered, value)? != DECISION_FALSE {
52                return Ok(None);
53            }
54            covered = self.diagram.apply(BooleanOp::Or, covered, value)?;
55            choices.push((guard.input, value));
56        }
57        if covered != DECISION_TRUE {
58            return Ok(None);
59        }
60        let mut selections = Vec::with_capacity(choices.len());
61        for (input, choice) in choices {
62            let mut values = FxMap::default();
63            for guard in &quantum.guards {
64                let value = self.lower(Eval::Input(node, guard.input))?;
65                let value = match self.diagram.constrain(value, choice)? {
66                    DECISION_FALSE => false,
67                    DECISION_TRUE => true,
68                    _ => return Ok(None),
69                };
70                values.insert(guard.input, value);
71            }
72            selections.push(QuantumSelection { input, values });
73        }
74        Ok(Some(selections))
75    }
76
77    /// Start a query cache borrowing this graph level, with finite defaults.
78    pub fn new(graph: &'a SubGraph) -> Self {
79        Self::with_limits(graph, BooleanLimits::default())
80    }
81
82    /// Start a query cache with explicit decision-node and cumulative-work limits.
83    pub fn with_limits(graph: &'a SubGraph, limits: BooleanLimits) -> Self {
84        Self {
85            graph,
86            diagram: BooleanDecisionDiagram::with_limits(limits),
87            memo: FxMap::default(),
88            variables: FxMap::default(),
89            inputs: FxMap::default(),
90            implications: FxMap::default(),
91            overlaps: FxMap::default(),
92        }
93    }
94
95    pub(crate) fn steps(&self) -> usize {
96        self.diagram.steps()
97    }
98
99    pub(crate) fn charge(&mut self, steps: usize) -> Result<(), Error> {
100        Ok(self.diagram.charge(steps)?)
101    }
102
103    /// Synchronize graph-local caches with the whole validation's work meter.
104    pub(crate) fn using_work<T>(
105        &mut self,
106        work: &mut BooleanDecisionDiagram,
107        query: impl FnOnce(&mut Self) -> Result<T, Error>,
108    ) -> Result<T, Error> {
109        self.charge(work.steps().saturating_sub(self.steps()))?;
110        let value = query(self)?;
111        work.charge(self.steps().saturating_sub(work.steps()))?;
112        Ok(value)
113    }
114
115    /// Whether two guards can both hold; an absent guard is unconditional.
116    ///
117    /// # Errors
118    ///
119    /// Returns [`crate::lowering::NodeTemplateInstanceMergeError`] for malformed predicate
120    /// dataflow or exhausted Boolean resources.
121    pub fn overlap(
122        &mut self,
123        left: Option<BloqNodeId>,
124        right: Option<BloqNodeId>,
125    ) -> Result<bool, Error> {
126        self.overlap_values(left.map(Into::into), right.map(Into::into))
127    }
128
129    /// Whether selected output guards overlap.
130    ///
131    /// # Errors
132    /// Returns an error for malformed predicates or exhausted Boolean resources.
133    pub fn overlap_values(
134        &mut self,
135        left: Option<ValueRef>,
136        right: Option<ValueRef>,
137    ) -> Result<bool, Error> {
138        self.charge(1)?;
139        let key = (left.min(right), left.max(right));
140        if let Some(&result) = self.overlaps.get(&key) {
141            return Ok(result);
142        }
143        let left = self.guard(left)?;
144        let right = self.guard(right)?;
145        let result = self.diagram.apply(BooleanOp::And, left, right)? != DECISION_FALSE;
146        self.overlaps.insert(key, result);
147        Ok(result)
148    }
149
150    fn guard(&mut self, node: Option<ValueRef>) -> Result<DecisionId, Error> {
151        node.map(|node| self.lower(Eval::Node(node)))
152            .transpose()
153            .map(|value| value.unwrap_or(DECISION_TRUE))
154    }
155
156    #[cfg(test)]
157    pub(crate) fn implies(
158        &mut self,
159        left: Option<BloqNodeId>,
160        right: BloqNodeId,
161    ) -> Result<bool, Error> {
162        self.implies_values(left.map(Into::into), right.into())
163    }
164
165    pub(crate) fn implies_values(
166        &mut self,
167        left: Option<ValueRef>,
168        right: ValueRef,
169    ) -> Result<bool, Error> {
170        self.charge(1)?;
171        if let Some(&result) = self.implications.get(&(left, right)) {
172            return Ok(result);
173        }
174        let source = self.guard(left)?;
175        let target = self.guard(Some(right))?;
176        let absent = self.diagram.negate(target)?;
177        let result = self.diagram.apply(BooleanOp::And, source, absent)? == DECISION_FALSE;
178        self.implications.insert((left, right), result);
179        Ok(result)
180    }
181
182    pub(crate) fn implies_all_values(
183        &mut self,
184        left: &[ValueRef],
185        right: ValueRef,
186    ) -> Result<bool, Error> {
187        if left.len() < 2 {
188            return self.implies_values(left.first().copied(), right);
189        }
190        self.charge(left.len())?;
191        let mut source = DECISION_TRUE;
192        for &node in left {
193            let value = self.guard(Some(node))?;
194            source = self.diagram.apply(BooleanOp::And, source, value)?;
195        }
196        let target = self.guard(Some(right))?;
197        let absent = self.diagram.negate(target)?;
198        Ok(self.diagram.apply(BooleanOp::And, source, absent)? == DECISION_FALSE)
199    }
200
201    fn input(&mut self, node: BloqNodeId, slot: u32) -> Result<ValueRef, Error> {
202        if !self.inputs.contains_key(&node) {
203            let mut inputs = FxMap::default();
204            for input in self.graph.value_inputs(node) {
205                self.diagram.charge(1)?;
206                inputs.insert(input.slot, input.value_ref().expect("runtime input"));
207            }
208            self.inputs.insert(node, inputs);
209        }
210        self.inputs[&node]
211            .get(&slot)
212            .copied()
213            .ok_or(Error::MissingMembershipInput(slot))
214    }
215
216    // Both expression nesting and shared Compute ancestry use one explicit
217    // stack. A long predicate chain cannot consume the native call stack.
218    fn lower(&mut self, first: Eval<'_>) -> Result<DecisionId, Error> {
219        self.charge(1)?;
220        let mut pending = vec![first];
221        let mut values = Vec::new();
222        let mut visiting = crate::FxSet::default();
223        while let Some(next) = pending.pop() {
224            self.charge(1)?;
225            match next {
226                Eval::Node(node) => {
227                    if let Some(&value) = self.memo.get(&node) {
228                        values.push(value);
229                        continue;
230                    }
231                    if !visiting.insert(node) {
232                        return Err(Error::InvalidMembership("cyclic predicate ancestry".into()));
233                    }
234                    let weight = self.graph.node(node.node).ok_or_else(|| {
235                        Error::InvalidMembership(format!("unknown predicate {node:?}"))
236                    })?;
237                    pending.push(Eval::Store(node));
238                    if let Some(slot) = weight.activation {
239                        pending.push(Eval::Apply(BooleanOp::And, 2, DECISION_TRUE));
240                        pending.push(Eval::Input(node.node, slot));
241                    }
242                    if node.output == ObservableOutput::Corrected
243                        && let Some(ClassicalNode::Compute { expr }) = weight.try_classical()
244                    {
245                        pending.push(Eval::Expr(node.node, expr));
246                    } else {
247                        // Keep related predicate inputs together. Registry node ids
248                        // follow physical emission and can separate correlated bits,
249                        // making a compact predicate exponential in that ordering.
250                        let next = self.variables.len();
251                        let variable = *self.variables.entry(node).or_insert(next);
252                        values.push(self.diagram.make_node(
253                            variable,
254                            DECISION_FALSE,
255                            DECISION_TRUE,
256                        )?);
257                    }
258                }
259                Eval::Store(node) => {
260                    let value = *values.last().expect("evaluated node");
261                    self.memo.insert(node, value);
262                    visiting.remove(&node);
263                }
264                Eval::Input(node, slot) => {
265                    let producer = self.input(node, slot)?;
266                    pending.push(Eval::Node(producer));
267                }
268                Eval::Expr(node, expr) => match expr {
269                    ClassicalExpr::Const(value) => {
270                        values.push(if *value {
271                            DECISION_TRUE
272                        } else {
273                            DECISION_FALSE
274                        });
275                    }
276                    ClassicalExpr::In(slot) => pending.push(Eval::Input(node, *slot)),
277                    ClassicalExpr::Not(inner) => {
278                        pending.push(Eval::Negate);
279                        pending.push(Eval::Expr(node, inner));
280                    }
281                    ClassicalExpr::Parity { inputs, constant } => {
282                        self.charge(inputs.len())?;
283                        pending.push(Eval::Apply(
284                            BooleanOp::Xor,
285                            inputs.len(),
286                            if *constant {
287                                DECISION_TRUE
288                            } else {
289                                DECISION_FALSE
290                            },
291                        ));
292                        pending.extend(inputs.iter().rev().map(|&slot| Eval::Input(node, slot)));
293                    }
294                    ClassicalExpr::Xor(operands)
295                    | ClassicalExpr::And(operands)
296                    | ClassicalExpr::Or(operands) => {
297                        self.charge(operands.len())?;
298                        let op = match expr {
299                            ClassicalExpr::Xor(..) => BooleanOp::Xor,
300                            ClassicalExpr::And(..) => BooleanOp::And,
301                            _ => BooleanOp::Or,
302                        };
303                        pending.push(Eval::Apply(
304                            op,
305                            operands.len(),
306                            if op == BooleanOp::And {
307                                DECISION_TRUE
308                            } else {
309                                DECISION_FALSE
310                            },
311                        ));
312                        pending.extend(operands.iter().rev().map(|expr| Eval::Expr(node, expr)));
313                    }
314                    ClassicalExpr::Select(operands) => {
315                        pending.push(Eval::Select);
316                        pending.extend(operands.iter().rev().map(|expr| Eval::Expr(node, expr)));
317                    }
318                },
319                Eval::Apply(op, count, mut value) => {
320                    for _ in 0..count {
321                        value = self
322                            .diagram
323                            .apply(op, value, values.pop().expect("operand"))?;
324                    }
325                    values.push(value);
326                }
327                Eval::Negate => {
328                    let value = values.pop().expect("negation operand");
329                    values.push(self.diagram.negate(value)?);
330                }
331                Eval::Select => {
332                    let high = values.pop().expect("true operand");
333                    let low = values.pop().expect("false operand");
334                    let condition = values.pop().expect("selection predicate");
335                    let absent = self.diagram.negate(condition)?;
336                    let low = self.diagram.apply(BooleanOp::And, absent, low)?;
337                    let high = self.diagram.apply(BooleanOp::And, condition, high)?;
338                    values.push(self.diagram.apply(BooleanOp::Or, low, high)?);
339                }
340            }
341        }
342        Ok(values.pop().expect("evaluated predicate"))
343    }
344}
345
346impl Bloq {
347    /// Terminal choices share fixed input seams, so their waits can be composed
348    /// before selection. Changing seams or continuing membership still needs a
349    /// pinned path. Activated quantum regions also retain that requirement.
350    pub(crate) fn timing_requires_pins(&self) -> Result<bool, Error> {
351        fn guarded(level: &SubGraph, under_activation: bool) -> Result<bool, Error> {
352            let mut predicates = PredicateAnalysis::new(level);
353            for (id, node) in level.nodes() {
354                if let Some(quantum) = node.try_quantum() {
355                    if under_activation {
356                        return Ok(true);
357                    }
358                    if !quantum.guards.is_empty()
359                        && (level
360                            .outgoing(id)
361                            .any(|edge| matches!(edge.edge, crate::BloqEdge::Quantum(_)))
362                            || predicates.quantum_selections(id)?.is_none())
363                    {
364                        return Ok(true);
365                    }
366                }
367                if let Some(region) = node.try_region() {
368                    for (_, body) in region.bodies() {
369                        if guarded(body, under_activation || node.activation.is_some())? {
370                            return Ok(true);
371                        }
372                    }
373                }
374            }
375            Ok(level.edges().any(|edge| {
376                matches!(edge.edge, crate::BloqEdge::Quantum(quantum) if quantum.guard.is_some())
377            }))
378        }
379        guarded(self.top(), false)
380    }
381}
382
383enum Eval<'a> {
384    Node(ValueRef),
385    Store(ValueRef),
386    Input(BloqNodeId, u32),
387    Expr(BloqNodeId, &'a ClassicalExpr),
388    Apply(BooleanOp, usize, DecisionId),
389    Negate,
390    Select,
391}
392
393/// SEM-MERGE legality is pairwise: aligned tick/repeat shapes, a unique partner
394/// for every reused body, and compatible operations on shared qubits. Checking
395/// every coexisting pair therefore certifies every selected set without listing
396/// its Boolean assignments. Record availability is checked separately by WF-7.
397pub(crate) fn validate_merge(
398    graph: &SubGraph,
399    id: BloqNodeId,
400    templates: &crate::BloqTemplatePool,
401    options: crate::lowering::InstantiationOptions<'_>,
402    predicates: &mut PredicateAnalysis<'_>,
403) -> Result<(), Error> {
404    let node = &graph[id];
405    let quantum = node.expect_quantum();
406    predicates.charge(
407        quantum
408            .instances
409            .len()
410            .saturating_add(quantum.guards.len())
411            .saturating_add(quantum.detector_bundles.len()),
412    )?;
413    for guard in &quantum.guards {
414        predicates.charge(
415            guard
416                .instances
417                .len()
418                .saturating_add(guard.detectors.len())
419                .saturating_add(guard.detector_bundles.len())
420                .saturating_add(guard.restarts.len())
421                .saturating_add(guard.detector_parities.len())
422                .saturating_add(guard.restart_parities.len()),
423        )?;
424    }
425    for parity in quantum.stored_parities() {
426        predicates.charge(parity.terms().len().saturating_add(1))?;
427    }
428    // Validate registration indices and uniqueness even for unreachable guards.
429    node.select_quantum_members(|_| Some(false))?;
430    let mut guards = FxMap::default();
431    for guard in &quantum.guards {
432        let producer = predicates.input(id, guard.input)?;
433        let value = predicates.guard(Some(producer))?;
434        for &instance in &guard.instances {
435            guards.insert(instance, value);
436        }
437    }
438    let mut pair = crate::BloqNode::from_members(Vec::new());
439    pair.provenance = node.provenance.clone();
440    let mut costs = FxMap::default();
441    let mut singleton = crate::FxSet::default();
442    let mut groups: FxMap<crate::TemplateId, (DecisionId, DecisionId)> = FxMap::default();
443    let mut shapes = crate::BloqTemplatePool::new();
444    let mut shape_ids = FxMap::default();
445    for instance in &quantum.instances {
446        let template = templates
447            .get(instance.template_id)
448            .ok_or(Error::UnknownTemplate(instance.template_id))?;
449        if let std::collections::hash_map::Entry::Vacant(entry) = costs.entry(instance.template_id)
450        {
451            let cost = crate::instantiation::circuit_work(&template.circuit);
452            predicates.charge(cost)?;
453            entry.insert(cost);
454            shape_ids.insert(
455                instance.template_id,
456                shapes.insert(crate::BloqTemplate::new(circuit_shape(&template.circuit))),
457            );
458        }
459        // Translation is the only instance-specific singleton check. Reuse the
460        // source footprint and materialize each template/provenance class once.
461        predicates.charge(template.qubits().len())?;
462        for &qubit in template.qubits() {
463            bloq_circuit::checked_translate_coordinate(qubit, instance.offset)?;
464        }
465        if singleton.insert((
466            instance.template_id,
467            instance.provenance.is_spatial_port_substitution(),
468        )) {
469            predicates.charge(costs[&instance.template_id])?;
470            pair.expect_quantum_mut().instances = vec![*instance];
471            pair.emission_plan_with_options(templates, options)?;
472        }
473        let value = guards.get(&instance.id).copied().unwrap_or(DECISION_TRUE);
474        // Keep the domains with at least one/two selected copies. The latter
475        // needs the pair merge's structural limits even at disjoint placements.
476        let (one, two) = groups
477            .entry(instance.template_id)
478            .or_insert((DECISION_FALSE, DECISION_FALSE));
479        let another = predicates.diagram.apply(BooleanOp::And, *one, value)?;
480        *two = predicates.diagram.apply(BooleanOp::Or, *two, another)?;
481        *one = predicates.diagram.apply(BooleanOp::Or, *one, value)?;
482    }
483    let groups: Vec<_> = groups
484        .into_iter()
485        .filter(|&(_, (guard, _))| guard != DECISION_FALSE)
486        .collect();
487    // Coexisting templates must align even when all their placements are
488    // disjoint. Strip coordinates, then use the same merge for shape legality.
489    for (index, &(left, (left_guard, multiple))) in groups.iter().enumerate() {
490        for &(right, (right_guard, _)) in groups.iter().take(index + 1) {
491            predicates.charge(1)?;
492            let coexisting = if left == right {
493                multiple
494            } else {
495                predicates
496                    .diagram
497                    .apply(BooleanOp::And, left_guard, right_guard)?
498            };
499            if coexisting == DECISION_FALSE {
500                continue;
501            }
502            predicates.charge(costs[&left].saturating_add(costs[&right]))?;
503            pair.expect_quantum_mut().instances = vec![
504                crate::TemplateInstance::new(
505                    crate::TemplateInstanceId(0),
506                    shape_ids[&left],
507                    glam::IVec2::ZERO,
508                ),
509                crate::TemplateInstance::new(
510                    crate::TemplateInstanceId(1),
511                    shape_ids[&right],
512                    glam::IVec2::ZERO,
513                ),
514            ];
515            pair.emission_plan(&shapes)?;
516        }
517    }
518
519    let mut occupants: FxMap<glam::IVec2, Vec<usize>> = FxMap::default();
520    let mut candidate_pairs = crate::FxSet::default();
521    let mut checked = crate::FxSet::default();
522    for (index, left) in quantum.instances.iter().enumerate() {
523        let left_guard = guards.get(&left.id).copied().unwrap_or(DECISION_TRUE);
524        if left_guard == DECISION_FALSE {
525            continue;
526        }
527        let footprint = templates[left.template_id].qubits();
528        predicates.charge(footprint.len())?;
529        for &qubit in footprint {
530            let qubit = bloq_circuit::checked_translate_coordinate(qubit, left.offset)?;
531            let others = occupants.entry(qubit).or_default();
532            for &other in others.iter() {
533                predicates.charge(1)?;
534                if !candidate_pairs.insert((index, other)) {
535                    continue;
536                }
537                let right = &quantum.instances[other];
538                let right_guard = guards.get(&right.id).copied().unwrap_or(DECISION_TRUE);
539                if predicates
540                    .diagram
541                    .apply(BooleanOp::And, left_guard, right_guard)?
542                    == DECISION_FALSE
543                {
544                    continue;
545                }
546                let offset = [
547                    i64::from(right.offset.x) - i64::from(left.offset.x),
548                    i64::from(right.offset.y) - i64::from(left.offset.y),
549                ];
550                if !checked.insert((
551                    left.template_id,
552                    right.template_id,
553                    offset,
554                    left.provenance.is_spatial_port_substitution(),
555                    right.provenance.is_spatial_port_substitution(),
556                )) {
557                    continue;
558                }
559                predicates
560                    .charge(costs[&left.template_id].saturating_add(costs[&right.template_id]))?;
561                pair.expect_quantum_mut().instances = vec![*left, *right];
562                pair.emission_plan_with_options(templates, options)?;
563            }
564            others.push(index);
565        }
566    }
567    Ok(())
568}
569
570/// Keep exactly the tick/repeat structure, including nonempty plain segments.
571/// The regular merge remains the sole authority for aligned-body legality.
572fn circuit_shape(source: &bloq_circuit::CoordCircuit) -> bloq_circuit::CoordCircuit {
573    use bloq_circuit::{BodyId, CircuitBody, CoordCircuit, GateType, Op};
574    let mut shape = CoordCircuit::new();
575    for index in 0..source.body_count() {
576        if index != 0 {
577            shape.add_body(CircuitBody::new());
578        }
579        let id = BodyId(index as u32);
580        let ops = shape.body_mut(id).expect("allocated shape body").ops_mut();
581        for op in source.body(id).expect("stored source body").ops() {
582            match op {
583                Op::Tick | Op::Repeat { .. } => ops.push(op.clone()),
584                _ if !matches!(ops.last(), Some(Op::Gate { .. })) => {
585                    ops.push(Op::Gate {
586                        gate: GateType::H,
587                        qubits: Vec::new(),
588                    });
589                }
590                _ => {}
591            }
592        }
593    }
594    shape
595        .set_entry_body(source.entry_body())
596        .expect("stored source entry");
597    shape
598}
599
600impl PredicateAnalysis<'_> {
601    /// Enumerate at most `limit` distinct, jointly reachable predicate tuples.
602    /// Shared Boolean ancestry preserves equal and complementary inputs without
603    /// enumerating all assignments to the underlying bit producers.
604    ///
605    /// # Errors
606    ///
607    /// Returns malformed predicate dataflow or exhausted Boolean resources.
608    pub fn values_up_to(
609        &mut self,
610        predicates: &[BloqNodeId],
611        limit: usize,
612    ) -> Result<Vec<Vec<bool>>, Error> {
613        self.charge(predicates.len())?;
614        let roots = predicates
615            .iter()
616            .map(|&node| self.guard(Some(node.into())))
617            .collect::<Result<Vec<_>, _>>()?;
618        Ok(self.diagram.values_up_to(&roots, limit)?)
619    }
620
621    /// Whether a joint assignment is consistent with the Boolean dataflow.
622    ///
623    /// # Errors
624    ///
625    /// Returns [`crate::lowering::NodeTemplateInstanceMergeError`] for malformed predicate
626    /// dataflow or exhausted Boolean resources.
627    pub fn assignment_reachable(
628        &mut self,
629        predicates: &[(BloqNodeId, bool)],
630    ) -> Result<bool, Error> {
631        Ok(self.assignment_root(predicates)? != DECISION_FALSE)
632    }
633
634    /// Additional predicate values fixed by one reachable assignment.
635    /// Unconditional Boolean constants remain for the caller's strict fold:
636    /// an unrelated `x ^ x` must still wait on `x` (SEM-EXPR).
637    pub(crate) fn values_fixed_by_assignment(
638        &mut self,
639        predicates: &[(ValueRef, bool)],
640        nodes: impl IntoIterator<Item = ValueRef>,
641    ) -> Result<Option<FxMap<ValueRef, bool>>, Error> {
642        let domain = self.assignment_value_root(predicates)?;
643        if domain == DECISION_FALSE {
644            return Ok(None);
645        }
646        let mut known = FxMap::default();
647        if domain == DECISION_TRUE {
648            return Ok(Some(known));
649        }
650        let mut fixed = FxMap::default();
651        for node in nodes {
652            let value = self.guard(Some(node))?;
653            if value == DECISION_FALSE || value == DECISION_TRUE {
654                continue;
655            }
656            let bit = if let Some(&bit) = fixed.get(&value) {
657                bit
658            } else {
659                let bit = match self.diagram.constrain(value, domain)? {
660                    DECISION_FALSE => Some(false),
661                    DECISION_TRUE => Some(true),
662                    _ => None,
663                };
664                fixed.insert(value, bit);
665                bit
666            };
667            if let Some(bit) = bit {
668                known.insert(node, bit);
669            }
670        }
671        Ok(Some(known))
672    }
673
674    fn assignment_root(&mut self, predicates: &[(BloqNodeId, bool)]) -> Result<DecisionId, Error> {
675        self.assignment_value_root(
676            &predicates
677                .iter()
678                .map(|&(node, value)| (node.into(), value))
679                .collect::<Vec<_>>(),
680        )
681    }
682
683    fn assignment_value_root(
684        &mut self,
685        predicates: &[(ValueRef, bool)],
686    ) -> Result<DecisionId, Error> {
687        self.charge(predicates.len().saturating_add(1))?;
688        let mut root = DECISION_TRUE;
689        for &(predicate, value) in predicates {
690            let mut condition = self.guard(Some(predicate))?;
691            if !value {
692                condition = self.diagram.negate(condition)?;
693            }
694            root = self.diagram.apply(BooleanOp::And, root, condition)?;
695            if root == DECISION_FALSE {
696                return Ok(root);
697            }
698        }
699        Ok(root)
700    }
701
702    /// Whether level-local bit predicates can all be true.
703    ///
704    /// Private because [`assignment_reachable`](Self::assignment_reachable) is
705    /// the public generalization (it takes a value per predicate); this is the
706    /// all-true special case, kept for its memoized one- and two-predicate
707    /// path through [`overlap`](Self::overlap).
708    fn can_coexist(&mut self, predicates: &[BloqNodeId]) -> Result<bool, Error> {
709        self.can_coexist_values(
710            &predicates
711                .iter()
712                .copied()
713                .map(Into::into)
714                .collect::<Vec<_>>(),
715        )
716    }
717
718    fn can_coexist_values(&mut self, predicates: &[ValueRef]) -> Result<bool, Error> {
719        if predicates.len() <= 2 {
720            return self.overlap_values(predicates.first().copied(), predicates.get(1).copied());
721        }
722        self.charge(predicates.len())?;
723        let mut root = DECISION_TRUE;
724        for &predicate in predicates {
725            let value = self.guard(Some(predicate))?;
726            root = self.diagram.apply(BooleanOp::And, root, value)?;
727            if root == DECISION_FALSE {
728                return Ok(false);
729            }
730        }
731        Ok(true)
732    }
733}
734
735impl SubGraph {
736    /// Whether selected level-local Boolean outputs can all be true. Shared Boolean
737    /// ancestry retains equal and complementary controls. The graph must be
738    /// acyclic, and every predicate must name an existing bit producer.
739    /// Use [`PredicateAnalysis::assignment_reachable`] to reuse derived
740    /// predicates across queries, or to ask for values other than all-true.
741    ///
742    /// # Errors
743    ///
744    /// Returns [`crate::lowering::NodeTemplateInstanceMergeError`] for malformed predicate
745    /// dataflow or exhausted Boolean resources.
746    pub fn predicates_can_coexist_values(&self, predicates: &[ValueRef]) -> Result<bool, Error> {
747        PredicateAnalysis::new(self).can_coexist_values(predicates)
748    }
749
750    /// Whether default corrected outputs can all be true.
751    ///
752    /// # Errors
753    /// Returns an error for malformed predicates or exhausted Boolean resources.
754    pub fn predicates_can_coexist(&self, predicates: &[BloqNodeId]) -> Result<bool, Error> {
755        PredicateAnalysis::new(self).can_coexist(predicates)
756    }
757}
758
759#[cfg(test)]
760mod tests {
761    use super::*;
762    use crate::{
763        BloqEdge, BloqNode, BloqTemplate, BloqValidationError, QuantumGuard, TemplateInstance,
764        TemplateInstanceId,
765    };
766    use bloq_circuit::{CoordCircuit, GateType};
767    use glam::ivec2;
768
769    #[test]
770    fn correlated_predicates_do_not_use_registry_allocation_order() {
771        let mut graph = SubGraph::new();
772        let groups: Vec<Vec<_>> = (0..2)
773            .map(|_| {
774                (0..20)
775                    .map(|_| {
776                        graph.add_node(BloqNode::classical(ClassicalNode::observable_fragment(
777                            Vec::new(),
778                            Vec::new(),
779                        )))
780                    })
781                    .collect()
782            })
783            .collect();
784        let equalities: Vec<_> = (0..20)
785            .map(|index| {
786                let node = graph.add_node(BloqNode::classical(ClassicalNode::Compute {
787                    expr: ClassicalExpr::parity([0, 1], true),
788                }));
789                graph.add_edge(groups[0][index], node, BloqEdge::value(0));
790                graph.add_edge(groups[1][index], node, BloqEdge::value(1));
791                node
792            })
793            .collect();
794        let all_equal = graph.add_node(BloqNode::classical(ClassicalNode::Compute {
795            expr: ClassicalExpr::And((0..20).map(ClassicalExpr::In).collect()),
796        }));
797        for (slot, &equal) in equalities.iter().enumerate() {
798            graph.add_edge(equal, all_equal, BloqEdge::value(slot as u32));
799        }
800        let mut analysis = PredicateAnalysis::with_limits(
801            &graph,
802            BooleanLimits {
803                max_nodes: 1_000,
804                max_steps: 100_000,
805            },
806        );
807        assert!(analysis.implies(Some(all_equal), equalities[0]).unwrap());
808        assert!(!analysis.implies(Some(equalities[0]), all_equal).unwrap());
809        assert!(
810            !analysis
811                .assignment_reachable(&[
812                    (all_equal, true),
813                    (groups[0][0], false),
814                    (groups[1][0], true),
815                ])
816                .unwrap()
817        );
818        assert!(
819            analysis
820                .assignment_reachable(&[
821                    (all_equal, true),
822                    (groups[0][0], true),
823                    (groups[1][0], true),
824                ])
825                .unwrap()
826        );
827    }
828
829    #[test]
830    fn deep_shared_predicates_keep_correlations_and_honor_limits() {
831        let mut graph = SubGraph::new();
832        let raw = graph.add_node(BloqNode::classical(ClassicalNode::observable_fragment(
833            Vec::new(),
834            Vec::new(),
835        )));
836        let mut tail = raw;
837        for _ in 0..12_000 {
838            let next = graph.add_node(BloqNode::classical(ClassicalNode::Compute {
839                expr: ClassicalExpr::In(0),
840            }));
841            graph.add_edge(tail, next, BloqEdge::value(0));
842            tail = next;
843        }
844        let different = graph.add_node(BloqNode::classical(ClassicalNode::Compute {
845            expr: ClassicalExpr::Xor(vec![ClassicalExpr::In(0), ClassicalExpr::In(1)].into()),
846        }));
847        graph.add_edge(raw, different, BloqEdge::value(0));
848        graph.add_edge(tail, different, BloqEdge::value(1));
849        let mut analysis = PredicateAnalysis::new(&graph);
850        assert!(analysis.overlap(Some(raw), Some(tail)).unwrap());
851        assert!(!analysis.overlap(None, Some(different)).unwrap());
852        assert_eq!(
853            analysis.values_up_to(&[raw, tail, different], 3).unwrap(),
854            [vec![false, false, false], vec![true, true, false]]
855        );
856        assert!(matches!(
857            PredicateAnalysis::with_limits(
858                &graph,
859                BooleanLimits {
860                    max_nodes: 4,
861                    max_steps: 100
862                }
863            )
864            .values_up_to(&[raw, tail], 3),
865            Err(Error::BooleanResource(_))
866        ));
867        assert!(matches!(
868            PredicateAnalysis::with_limits(
869                &graph,
870                BooleanLimits {
871                    max_nodes: 4,
872                    max_steps: 100
873                }
874            )
875            .overlap(None, Some(tail)),
876            Err(Error::BooleanResource(_))
877        ));
878        assert!(matches!(
879            PredicateAnalysis::with_limits(
880                &graph,
881                BooleanLimits {
882                    max_nodes: 4,
883                    max_steps: 100
884                }
885            )
886            .values_fixed_by_assignment(&[(raw.into(), true)], [tail.into()]),
887            Err(Error::BooleanResource(_))
888        ));
889        assert!(matches!(
890            PredicateAnalysis::with_limits(
891                &graph,
892                BooleanLimits {
893                    max_nodes: 0,
894                    max_steps: 100
895                }
896            )
897            .overlap(None, Some(raw)),
898            Err(Error::BooleanResource(_))
899        ));
900        let mut constants = PredicateAnalysis::with_limits(
901            &graph,
902            BooleanLimits {
903                max_nodes: 0,
904                max_steps: 2,
905            },
906        );
907        assert!(constants.overlap(None, None).unwrap());
908        assert!(constants.overlap(None, None).unwrap());
909        assert!(matches!(
910            constants.overlap(None, None),
911            Err(Error::BooleanResource(_))
912        ));
913    }
914
915    #[test]
916    fn disjoint_constant_members_scale_with_footprint_and_charge_work() {
917        let mut bloq = Bloq::new();
918        let mut circuit = CoordCircuit::new();
919        circuit.do_gate(GateType::H, [ivec2(0, 0)]).unwrap();
920        let template = bloq.add_template(BloqTemplate::new(circuit));
921        let guard = bloq.add_node(BloqNode::classical(ClassicalNode::Compute {
922            expr: ClassicalExpr::Const(true),
923        }));
924        let mut node = BloqNode::from_members(Vec::new());
925        node.expect_quantum_mut().instances = (0..1_000)
926            .map(|index| {
927                TemplateInstance::new(TemplateInstanceId(index), template, ivec2(index as i32, 0))
928            })
929            .collect();
930        node.expect_quantum_mut().guards.push(QuantumGuard {
931            input: 0,
932            instances: (0..1_000).map(TemplateInstanceId).collect(),
933            ..Default::default()
934        });
935        let node = bloq.add_node(node);
936        bloq.add_edge(guard, node, BloqEdge::value(0));
937        let options =
938            crate::lowering::InstantiationOptions::default().with_boolean_limits(BooleanLimits {
939                max_nodes: 0,
940                max_steps: 12_000,
941            });
942        bloq.validate_with_options(&options).unwrap();
943        let limited = options.with_boolean_limits(BooleanLimits {
944            max_nodes: 0,
945            max_steps: 100,
946        });
947        assert!(matches!(
948            bloq.validate_with_options(&limited),
949            Err(BloqValidationError::BooleanResource(_)
950                | BloqValidationError::InvalidInstanceMergeStructure {
951                    source: Error::BooleanResource(_),
952                    ..
953                },)
954        ));
955    }
956
957    #[test]
958    fn disjoint_templates_still_require_coexisting_tick_shapes() {
959        let mut bloq = Bloq::new();
960        let mut circuit = CoordCircuit::new();
961        circuit.do_gate(GateType::H, [ivec2(0, 0)]).unwrap();
962        let left = bloq.add_template(BloqTemplate::new(circuit.clone()));
963        circuit.tick();
964        let right = bloq.add_template(BloqTemplate::new(circuit));
965        let raw = bloq.add_node(BloqNode::classical(ClassicalNode::observable_fragment(
966            Vec::new(),
967            Vec::new(),
968        )));
969        let inverse = bloq.add_node(BloqNode::classical(ClassicalNode::Compute {
970            expr: ClassicalExpr::Not(Box::new(ClassicalExpr::In(0))),
971        }));
972        bloq.add_edge(raw, inverse, BloqEdge::value(0));
973        let mut node = BloqNode::from_members(Vec::new());
974        node.expect_quantum_mut().instances = vec![
975            TemplateInstance::new(TemplateInstanceId(0), left, ivec2(0, 0)),
976            TemplateInstance::new(TemplateInstanceId(1), right, ivec2(100, 0)),
977        ];
978        node.expect_quantum_mut().guards = vec![
979            QuantumGuard {
980                input: 0,
981                instances: vec![TemplateInstanceId(0)],
982                ..Default::default()
983            },
984            QuantumGuard {
985                input: 1,
986                instances: vec![TemplateInstanceId(1)],
987                ..Default::default()
988            },
989        ];
990        let node = bloq.add_node(node);
991        bloq.add_edge(raw, node, BloqEdge::value(0));
992        bloq.add_edge(inverse, node, BloqEdge::value(1));
993        bloq.validate().unwrap();
994        bloq.node_mut(inverse).unwrap().kind = crate::BloqNodeKind::Classical(
995            ClassicalNode::Compute {
996                expr: ClassicalExpr::In(0),
997            }
998            .into(),
999        );
1000        assert!(matches!(
1001            bloq.validate(),
1002            Err(BloqValidationError::InvalidInstanceMergeStructure {
1003                source: Error::TickSegmentCountMismatch,
1004                ..
1005            })
1006        ));
1007    }
1008
1009    #[test]
1010    fn deep_disjoint_copies_merge_when_they_coexist() {
1011        use bloq_circuit::{CircuitBody, Op};
1012        let mut bloq = Bloq::new();
1013        let mut circuit = CoordCircuit::new();
1014        circuit.do_gate(GateType::H, [ivec2(0, 0)]).unwrap();
1015        for _ in 0..257 {
1016            let child = circuit.entry_body();
1017            let parent = circuit.add_body(CircuitBody::new());
1018            circuit
1019                .body_mut(parent)
1020                .unwrap()
1021                .ops_mut()
1022                .push(Op::Repeat {
1023                    body: child,
1024                    repetitions: 1,
1025                });
1026            circuit.set_entry_body(parent).unwrap();
1027        }
1028        let template = bloq.add_template(BloqTemplate::new(circuit));
1029        let raw = bloq.add_node(BloqNode::classical(ClassicalNode::observable_fragment(
1030            Vec::new(),
1031            Vec::new(),
1032        )));
1033        let inverse = bloq.add_node(BloqNode::classical(ClassicalNode::Compute {
1034            expr: ClassicalExpr::Not(Box::new(ClassicalExpr::In(0))),
1035        }));
1036        bloq.add_edge(raw, inverse, BloqEdge::value(0));
1037        let mut node = BloqNode::from_members(Vec::new());
1038        for index in 0..2 {
1039            let instance = TemplateInstanceId(index);
1040            node.expect_quantum_mut()
1041                .instances
1042                .push(TemplateInstance::new(
1043                    instance,
1044                    template,
1045                    ivec2(index as i32, 0),
1046                ));
1047            node.expect_quantum_mut().guards.push(QuantumGuard {
1048                input: index,
1049                instances: vec![instance],
1050                ..Default::default()
1051            });
1052        }
1053        let node = bloq.add_node(node);
1054        bloq.add_edge(raw, node, BloqEdge::value(0));
1055        bloq.add_edge(inverse, node, BloqEdge::value(1));
1056        bloq.validate().unwrap();
1057        bloq.node_mut(inverse).unwrap().kind = crate::BloqNodeKind::Classical(
1058            ClassicalNode::Compute {
1059                expr: ClassicalExpr::In(0),
1060            }
1061            .into(),
1062        );
1063        bloq.validate().unwrap();
1064    }
1065}
bloq_ir/membership.rs

bloq_ir/
membership.rs
