bloq_graph/
validate.rs

1//! Structural and classical-semantic validation for block graphs.
2
3use crate::MeasureTarget;
4use crate::{
5    ActionDag, Basis, Block, BlockGraph, BlockGraphError, BlockKind, Direction, PatchRotationKind,
6    Pipe, UDirection,
7};
8use glam::IVec3;
9use std::collections::{HashMap, HashSet};
10use thiserror::Error;
11
12/// A structural well-formedness violation found while validating a
13/// [`BlockGraph`](crate::BlockGraph)'s blocks, pipes, and lattice-surgery
14/// geometry.
15#[derive(Error, Debug, Clone)]
16#[non_exhaustive]
17pub enum InvalidBlockGraphError {
18    /// A block kind requiring one pipe has a different degree.
19    #[error("expected exactly one pipe connected to the block at {0}")]
20    NotExactlySinglePipe(IVec3),
21    /// A block kind that accepts only temporal pipes has a spatial pipe.
22    #[error("spatial pipe connected to the block at {0}")]
23    SpatialPipeNotAllowed(IVec3),
24    /// A spatial port lacks an explicit input, output, or multiplex role.
25    #[error("spatial Port at {0} must declare role=input, role=output, or role=multiplex")]
26    SpatialPortRoleRequired(IVec3),
27    /// A temporal port's declared role disagrees with its pipe direction.
28    #[error("temporal Port at {pos} declares role {declared}, but its pipe makes it {inferred}")]
29    TemporalPortRoleMismatch {
30        /// Port position.
31        pos: IVec3,
32        /// Explicitly declared role.
33        declared: crate::PortRole,
34        /// Role inferred from the temporal pipe.
35        inferred: crate::PortRole,
36    },
37    /// A block accepts only a pipe extending into its past.
38    #[error("only time-like pipe connected to past is allowed for block at {0}")]
39    FuturePipeNotAllowed(IVec3),
40    /// A block accepts only a pipe extending into its future.
41    #[error("only time-like pipe connected to future is allowed for block at {0}")]
42    PastPipeNotAllowed(IVec3),
43    /// Adjacent block faces imply incompatible lattice-surgery orientations.
44    #[error(
45        "cannot resolve the lattice surgery orientation for pipe between blocks at {0} and {1}"
46    )]
47    OrientationContradiction(IVec3, IVec3),
48    /// A multi-pipe junction does not lie in one plane.
49    #[error("block at {0} is not a planar junction")]
50    JunctionNotPlanar(IVec3),
51    /// A pipe face has the same basis on both perpendicular axes.
52    #[error(
53        "degenerate pipe face: block at {0} has the same basis on both axes perpendicular to pipe toward {1}"
54    )]
55    DegeneratePipeFace(IVec3, IVec3),
56    /// Spatially connected cubes have different symbolic heights.
57    #[error(
58        "spatially connected cubes at {pos} and {neighbor} have different heights (height={height} vs height={neighbor_height})"
59    )]
60    CubeHeightSpatialMismatch {
61        /// First cube position.
62        pos: IVec3,
63        /// Neighboring cube position.
64        neighbor: IVec3,
65        /// First cube height.
66        height: crate::CubeHeight,
67        /// Neighboring cube height.
68        neighbor_height: crate::CubeHeight,
69    },
70    /// A pipe attaches to an invalid cell of a multi-cell cube.
71    #[error(
72        "multi-cell cube at {pos} has an invalid pipe endpoint {endpoint}; spatial pipes attach at the anchor, temporal pipes attach at bottom or top"
73    )]
74    CubeInvalidPipeEndpoint {
75        /// Cube anchor position.
76        pos: IVec3,
77        /// Invalid pipe endpoint.
78        endpoint: IVec3,
79    },
80    /// Two block footprints reserve the same lattice cell.
81    #[error("block footprints overlap at occupied position {pos}")]
82    BlockFootprintOverlap {
83        /// Multiply occupied lattice cell.
84        pos: IVec3,
85    },
86    /// A walking block endpoint has a spatial pipe.
87    #[error("Walking block at {pos} has a non-temporal pipe attached at endpoint {endpoint}")]
88    WalkingPipeNotTemporal {
89        /// Walking-block anchor position.
90        pos: IVec3,
91        /// Endpoint with the invalid pipe.
92        endpoint: IVec3,
93    },
94    /// A walking block's start endpoint has a non-past pipe.
95    #[error("Walking block at {pos} start endpoint only allows past temporal pipes")]
96    WalkingStartPipeNotPast {
97        /// Walking-block anchor position.
98        pos: IVec3,
99    },
100    /// A walking block's end endpoint has a non-future pipe.
101    #[error("Walking block at {pos} end endpoint only allows future temporal pipes")]
102    WalkingEndPipeNotFuture {
103        /// Walking-block anchor position.
104        pos: IVec3,
105    },
106    /// A patch-rotation endpoint does not have exactly one temporal pipe.
107    #[error(
108        "Patch rotation block at {pos} endpoint {endpoint} requires exactly one temporal pipe, got {count}"
109    )]
110    PatchRotationEndpointPipeCount {
111        /// Patch-rotation anchor position.
112        pos: IVec3,
113        /// Endpoint being checked.
114        endpoint: IVec3,
115        /// Number of attached temporal pipes.
116        count: usize,
117    },
118    /// A patch-rotation endpoint has a spatial pipe.
119    #[error(
120        "Patch rotation block at {pos} has a non-temporal pipe attached at endpoint {endpoint}"
121    )]
122    PatchRotationPipeNotTemporal {
123        /// Patch-rotation anchor position.
124        pos: IVec3,
125        /// Endpoint with the invalid pipe.
126        endpoint: IVec3,
127    },
128    /// A patch rotation has a Hadamard pipe at its start endpoint.
129    #[error("Patch rotation block at {pos} does not allow a Hadamard pipe at its start endpoint")]
130    PatchRotationStartPipeHadamard {
131        /// Patch-rotation anchor position.
132        pos: IVec3,
133    },
134    /// A patch-rotation endpoint has the wrong boundary orientation.
135    #[error(
136        "Patch rotation block at {pos} endpoint {endpoint} has boundary orientation {actual:?}, expected {expected:?}"
137    )]
138    PatchRotationBoundaryMismatch {
139        /// Patch-rotation anchor position.
140        pos: IVec3,
141        /// Endpoint being checked.
142        endpoint: IVec3,
143        /// Boundary basis required by the rotation.
144        expected: Basis,
145        /// Basis inferred from the attached pipe, if any.
146        actual: Option<Basis>,
147    },
148}
149
150/// A semantic or graph-constraint violation found while validating a graph's
151/// [`Action`](crate::Action)s.
152#[derive(Error, Debug, Clone)]
153#[non_exhaustive]
154pub enum InvalidActionError {
155    /// An edge measurement targets a temporal pipe.
156    #[error("measurement target edge at {0} along {1} is time-like")]
157    TimeLikeMeasurementEdge(IVec3, Direction),
158    /// A node measurement targets an unsupported block kind.
159    #[error("measurement target node at {0} is invalid")]
160    InvalidMeasurementNode(IVec3),
161    /// More than one measurement action targets the same node or edge.
162    #[error("measurement target {0:?} is duplicated")]
163    DuplicateMeasurementTarget(MeasureTarget),
164    /// An action name is not a valid BLOG identifier.
165    #[error("action name '{0}' is not a valid BLOG identifier")]
166    InvalidActionName(String),
167    /// A classical variable is defined more than once.
168    #[error("variable '{0}' defined multiple times")]
169    VariableRedefinition(String),
170    /// An expression refers to an unavailable variable.
171    #[error("undefined variable '{0}' used")]
172    UndefinedVariable(String),
173    /// A resolve action targets a non-selective block.
174    #[error("resolve target {0} is not a selective block")]
175    InvalidResolveTarget(IVec3),
176    /// More than one resolve action targets the same selective block.
177    #[error("resolve target {0} is duplicated")]
178    DuplicateResolveTarget(IVec3),
179    /// A branch action targets no explicit branch region.
180    #[error("branch target {0} is not a branch region")]
181    InvalidBranchTarget(IVec3),
182    /// More than one branch action targets the same region.
183    #[error("branch target {0} is duplicated")]
184    DuplicateBranchTarget(IVec3),
185    /// More than one explicit branch region uses the same name.
186    #[error("branch region '{0}' is duplicated")]
187    DuplicateBranchName(String),
188    /// An explicit branch region has no selector action.
189    #[error("branch region '{0}' has no resolve action")]
190    MissingResolveForBranch(String),
191    /// A branch action names no explicit branch region.
192    #[error("resolve names unknown branch region '{0}'")]
193    UnknownBranchName(String),
194    /// The two arms of a branch expose incompatible boundary cuts.
195    #[error("branch region '{name}' has invalid arm interface: {reason}")]
196    InvalidBranchInterface {
197        /// Branch region name.
198        name: String,
199        /// Interface mismatch diagnostic.
200        reason: String,
201    },
202    /// Static stabilizer analysis was requested for continuing branches.
203    #[error(
204        "continuing branches require GuardedSurfaceSpace; select a projection for a static stabilizer table"
205    )]
206    GuardedAnalysisRequired,
207    /// A branch selector depends on a measurement inside that branch.
208    #[error("branch target {target} is controlled by measurement {controller:?} inside its region")]
209    BranchControllerInside {
210        /// Stable branch anchor.
211        target: IVec3,
212        /// Measurement target used by the selector.
213        controller: MeasureTarget,
214    },
215    /// A physical action target lies inside conditional branch geometry.
216    #[error("branch target {target} contains physical target of action ordinal {ordinal}")]
217    BranchContainsActionTarget {
218        /// Stable branch anchor.
219        target: IVec3,
220        /// Source ordinal of the conflicting action.
221        ordinal: usize,
222    },
223    /// Two explicit branch regions own the same block.
224    #[error("branch regions at {first} and {second} overlap at block {block}")]
225    OverlappingBranchRegions {
226        /// First branch anchor.
227        first: IVec3,
228        /// Second branch anchor.
229        second: IVec3,
230        /// Overlapping block position.
231        block: IVec3,
232    },
233    /// A requested branch projection omits a branch value.
234    #[error("branch target {0} has no projection value")]
235    MissingBranchValue(IVec3),
236    /// A requested branch projection names an unknown branch.
237    #[error("projection value names unknown branch target {0}")]
238    UnknownBranchValue(IVec3),
239    /// A requested branch projection assigns one branch more than once.
240    #[error("branch target {0} has more than one projection value")]
241    DuplicateBranchValue(IVec3),
242    /// A named measurement has different stabilizer support across branch arms.
243    #[error("measurement {name:?} has branch-dependent stabilizer support")]
244    BranchDependentMeasurementSurface {
245        /// Measurement record name.
246        name: String,
247    },
248    /// A selective block has no resolve action.
249    #[error("Selective block at {target} is missing its resolve action")]
250    MissingResolveForSelective {
251        /// Unresolved selective-block position.
252        target: IVec3,
253    },
254    /// Classical and implicit action dependencies form a cycle.
255    #[error("action dependency cycle detected at ordinal {ordinal}")]
256    DependencyCycle {
257        /// Source action ordinal at which the cycle was detected.
258        ordinal: usize,
259    },
260    /// A feedback action contains no correction targets.
261    #[error("feedback requires at least one target")]
262    EmptyFeedbackTargets,
263    /// A feedback correction targets no block.
264    #[error("feedback target {0} is not a block")]
265    InvalidFeedbackTarget(IVec3),
266}
267
268/// Validates graph structure and action semantics, then — once the cached DAG
269/// is stale — the stabilizer-derived measurement surfaces and dependency edges.
270pub(crate) fn validate(graph: &BlockGraph) -> Result<(), BlockGraphError> {
271    validate_with_limits(graph, crate::ModuleCertificationLimits::DEFAULT)
272}
273
274pub(crate) fn validate_with_limits(
275    graph: &BlockGraph,
276    limits: crate::ModuleCertificationLimits,
277) -> Result<(), BlockGraphError> {
278    let mut dag = validate_source(graph)?;
279    let regions = graph.branch_regions()?;
280    if graph.has_continuing_branches() {
281        return graph.validate_guarded_actions_with_limits(limits);
282    }
283    if (!regions.is_empty() || graph.has_actions()) && !graph.action_graph().is_analyzed() {
284        let stabilizers = if regions.is_empty() {
285            graph.stabilizers_with_limits(limits)?
286        } else {
287            graph.stabilizers_for_action_analysis_with_limits(limits)?
288        };
289        stabilizers.validate_selective_decoupling()?;
290        dag.attach_readout_dependencies(&stabilizers.generators, Some(&stabilizers.zx_graph))?;
291    }
292    Ok(())
293}
294
295/// Structure and action semantics only, returning the DAG built along the way.
296///
297/// This is the precondition for building a [`ZXGraph`](crate::ZXGraph), so it
298/// deliberately stops short of the physical analysis in [`validate`]: that
299/// analysis needs a ZX graph to derive the rows it would check.
300pub(crate) fn validate_source(graph: &BlockGraph) -> Result<ActionDag, BlockGraphError> {
301    validate_structure(graph)?;
302    let mut dag = graph.build_action_graph(&graph.actions())?;
303    if !graph.has_actions() {
304        // `build_action_graph` short-circuits on an empty list, so its
305        // graph-constraint pass — every selective block needs a `resolve` —
306        // has not run yet.
307        dag.validate(Some(graph))?;
308    }
309    Ok(dag)
310}
311
312pub(crate) fn validate_structure(graph: &BlockGraph) -> Result<(), BlockGraphError> {
313    structural_errors(graph)
314        .into_iter()
315        .next()
316        .map_or(Ok(()), Err)
317}
318
319/// Collects every structural violation instead of stopping at the first.
320///
321/// Editing tools diff this set across a candidate edit so they can reject only
322/// what the edit introduces and leave defects the graph already carried alone;
323/// a fail-fast check cannot tell those apart.
324///
325/// The phases stay ordered and gated exactly as the fail-fast path had them: a
326/// later phase runs only once the earlier ones are clean, because its geometry
327/// inference assumes resolvable pipe endpoints and non-overlapping footprints.
328/// Errors are therefore complete *within* a phase, not across phases.
329pub(crate) fn structural_errors(graph: &BlockGraph) -> Vec<BlockGraphError> {
330    let mut errors = Vec::new();
331
332    collect_block_footprint_errors(graph, &mut errors);
333    if !errors.is_empty() {
334        return errors;
335    }
336    errors.extend(graph.pipes().filter_map(|pipe| pipe.try_endpoints().err()));
337    if !errors.is_empty() {
338        return errors;
339    }
340    for pipe in graph.pipes() {
341        for endpoint in [pipe.src(), pipe.dst()] {
342            if graph.get_endpoint_block(endpoint).is_none() {
343                errors.push(BlockGraphError::BlockNotFound(endpoint));
344            }
345        }
346    }
347    if !errors.is_empty() {
348        return errors;
349    }
350    collect_lattice_surgery_errors(graph, &mut errors);
351    if !errors.is_empty() {
352        return errors;
353    }
354    collect_block_constraint_errors(graph, &mut errors);
355    errors
356}
357
358fn collect_block_footprint_errors(graph: &BlockGraph, errors: &mut Vec<BlockGraphError>) {
359    let mut occupied = HashMap::<IVec3, Vec<(IVec3, BlockKind)>>::new();
360    for block in graph.blocks() {
361        let reserved = match block.checked_reserved_positions() {
362            Ok(reserved) => reserved,
363            Err(err) => {
364                errors.push(err);
365                continue;
366            }
367        };
368        for pos in reserved {
369            for (other_pos, other_kind) in occupied.get(&pos).into_iter().flatten() {
370                if !block
371                    .kind
372                    .allows_reserved_overlap(block.pos(), *other_kind, *other_pos, pos)
373                {
374                    errors.push(InvalidBlockGraphError::BlockFootprintOverlap { pos }.into());
375                }
376            }
377            occupied
378                .entry(pos)
379                .or_default()
380                .push((block.pos(), block.kind));
381        }
382    }
383}
384
385fn collect_lattice_surgery_errors(graph: &BlockGraph, errors: &mut Vec<BlockGraphError>) {
386    for (u_pos, v_pos, _, _, pipe) in graph.pipe_endpoints_with_blocks() {
387        debug_assert_eq!(pipe.src(), u_pos);
388        let u_bases = graph.infer_pipe_endpoint_face_bases(pipe, u_pos);
389        let v_bases = graph.infer_pipe_endpoint_face_bases(pipe, v_pos);
390        let delta = u_pos - v_pos;
391        for ((d, u_basis), v_basis) in delta.to_array().into_iter().zip(u_bases).zip(v_bases) {
392            if d == 0
393                && let (Some(u_basis), Some(v_basis)) = (u_basis, v_basis)
394                && (u_basis != v_basis) ^ pipe.hadamard
395            {
396                errors.push(InvalidBlockGraphError::OrientationContradiction(u_pos, v_pos).into());
397                break;
398            }
399        }
400    }
401}
402
403/// One pipe's physical endpoints and owner blocks, as yielded by
404/// [`BlockGraph::pipe_endpoints_with_blocks`].
405type PipeIncidence<'a> = (IVec3, IVec3, &'a Block, &'a Block, &'a Pipe);
406
407fn collect_block_constraint_errors(graph: &BlockGraph, errors: &mut Vec<BlockGraphError>) {
408    // Index pipes by owner block once, keeping validation O(V+E) and preserving
409    // pipe order within each block.
410    let mut incidence: HashMap<IVec3, Vec<PipeIncidence>> = HashMap::new();
411    for tuple in graph.pipe_endpoints_with_blocks() {
412        let (_, _, u, v, _) = tuple;
413        incidence.entry(u.pos()).or_default().push(tuple);
414        if v.pos() != u.pos() {
415            incidence.entry(v.pos()).or_default().push(tuple);
416        }
417    }
418
419    // A failing block stops its own checks and the scan moves on to the next
420    // block, rather than abandoning the rest of the graph.
421    for block in graph.blocks() {
422        let neighbors = graph.neighbor_positions(block.pos());
423        let incident: &[PipeIncidence] = match incidence.get(&block.pos()) {
424            Some(pipes) => pipes,
425            None => &[],
426        };
427        match block.kind {
428            BlockKind::Port
429            | BlockKind::Y
430            | BlockKind::Measurement(_)
431            | BlockKind::T
432            | BlockKind::Selective(_) => {
433                if neighbors.len() != 1 {
434                    errors.push(InvalidBlockGraphError::NotExactlySinglePipe(block.pos()).into());
435                    continue;
436                }
437                let has_spatial_pipe = neighbors
438                    .iter()
439                    .any(|&pos| (pos - block.pos()).abs() != IVec3::Z);
440                if block.kind == BlockKind::Port {
441                    let role = block.port_role().expect("Port blocks expose a role");
442                    if has_spatial_pipe && role == crate::PortRole::Auto {
443                        errors.push(
444                            InvalidBlockGraphError::SpatialPortRoleRequired(block.pos()).into(),
445                        );
446                    }
447                    if !has_spatial_pipe && role != crate::PortRole::Auto {
448                        let inferred = if neighbors[0].z > block.pos().z {
449                            crate::PortRole::Input
450                        } else {
451                            crate::PortRole::Output
452                        };
453                        if role != inferred {
454                            errors.push(
455                                InvalidBlockGraphError::TemporalPortRoleMismatch {
456                                    pos: block.pos(),
457                                    declared: role,
458                                    inferred,
459                                }
460                                .into(),
461                            );
462                            continue;
463                        }
464                    }
465                }
466                let spatial_allowed = block.kind == BlockKind::Port;
467                if has_spatial_pipe && !spatial_allowed {
468                    errors.push(InvalidBlockGraphError::SpatialPipeNotAllowed(block.pos()).into());
469                    continue;
470                }
471                if matches!(block.kind, BlockKind::T)
472                    && neighbors.iter().any(|&pos| pos - block.pos() != IVec3::Z)
473                {
474                    // A T block injects into the future, so its single pipe must
475                    // point at +Z; a past-facing pipe is the violation here.
476                    errors.push(InvalidBlockGraphError::PastPipeNotAllowed(block.pos()).into());
477                    continue;
478                }
479                if matches!(
480                    block.kind,
481                    BlockKind::Measurement(_) | BlockKind::Selective(_)
482                ) && neighbors
483                    .iter()
484                    .any(|&pos| pos - block.pos() != IVec3::NEG_Z)
485                {
486                    errors.push(InvalidBlockGraphError::FuturePipeNotAllowed(block.pos()).into());
487                    continue;
488                }
489            }
490            BlockKind::Cube(ck) => {
491                let height_errors = errors.len();
492                collect_cube_height_errors(block, incident, errors);
493                if errors.len() > height_errors {
494                    continue;
495                }
496                let cube_neighbors = cube_endpoint_neighbors(block, incident);
497                // A pipe face is defined by the two axes perpendicular to the pipe
498                // direction. If both perpendicular axes have the same basis, the
499                // lattice surgery orientation is degenerate (e.g. XZZ cube with a
500                // pipe along +X has Z on both Y and Z faces).
501                for (endpoint, delta) in &cube_neighbors {
502                    let diff = (*delta).abs();
503                    let pipe_axis = diff
504                        .to_array()
505                        .iter()
506                        .position(|&d| d != 0)
507                        .expect("neighbor differs on at least one axis");
508                    let perp: [usize; 2] = match pipe_axis {
509                        0 => [1, 2],
510                        1 => [0, 2],
511                        _ => [0, 1],
512                    };
513                    // Each face is independent, so report them all: a cube that
514                    // already has one broken face must still report a second one
515                    // an edit adds, or a before/after diff would not see it.
516                    if ck.bases()[perp[0]] == ck.bases()[perp[1]] {
517                        errors.push(
518                            InvalidBlockGraphError::DegeneratePipeFace(
519                                block.pos(),
520                                *endpoint + *delta,
521                            )
522                            .into(),
523                        );
524                    }
525                }
526
527                if cube_neighbors
528                    .into_iter()
529                    .map(|(_, delta)| delta.abs())
530                    .collect::<HashSet<_>>()
531                    .len()
532                    == 3
533                {
534                    errors.push(InvalidBlockGraphError::JunctionNotPlanar(block.pos()).into());
535                }
536            }
537            BlockKind::Walking(kind) => {
538                let start = block.pos();
539                let end = kind.end_position(start);
540                for &(u_pos, v_pos, u, v, _) in incident {
541                    let (endpoint, other_pos) = if u.pos() == block.pos() {
542                        (u_pos, v_pos)
543                    } else if v.pos() == block.pos() {
544                        (v_pos, u_pos)
545                    } else {
546                        continue;
547                    };
548                    // One violation per incident pipe, then on to the next pipe:
549                    // an existing bad pipe must not mask a newly added one.
550                    let delta = other_pos - endpoint;
551                    if delta.abs() != IVec3::Z {
552                        errors.push(
553                            InvalidBlockGraphError::WalkingPipeNotTemporal {
554                                pos: start,
555                                endpoint,
556                            }
557                            .into(),
558                        );
559                        continue;
560                    }
561                    if endpoint == start && delta != IVec3::NEG_Z {
562                        errors.push(
563                            InvalidBlockGraphError::WalkingStartPipeNotPast { pos: start }.into(),
564                        );
565                        continue;
566                    }
567                    if endpoint == end && delta != IVec3::Z {
568                        errors.push(
569                            InvalidBlockGraphError::WalkingEndPipeNotFuture { pos: start }.into(),
570                        );
571                        continue;
572                    }
573                    if endpoint != start && endpoint != end {
574                        errors.push(
575                            InvalidBlockGraphError::WalkingPipeNotTemporal {
576                                pos: start,
577                                endpoint,
578                            }
579                            .into(),
580                        );
581                        continue;
582                    }
583                }
584            }
585            BlockKind::PatchRotation(kind) => {
586                collect_patch_rotation_errors(graph, block.pos(), kind, incident, errors);
587            }
588        }
589    }
590}
591
592fn cube_endpoint_neighbors(block: &Block, incident: &[PipeIncidence]) -> Vec<(IVec3, IVec3)> {
593    incident
594        .iter()
595        .filter_map(|&(u_pos, v_pos, u, v, _)| {
596            if u.pos() == block.pos() {
597                Some((u_pos, v_pos - u_pos))
598            } else if v.pos() == block.pos() {
599                Some((v_pos, u_pos - v_pos))
600            } else {
601                None
602            }
603        })
604        .collect()
605}
606
607/// Reports each endpoint of the rotation independently, so a half-wired block
608/// names both of its missing pipes rather than only the first: an editor adding
609/// them one at a time needs the untouched endpoint to keep reporting the same
610/// violation it already had.
611fn collect_patch_rotation_errors(
612    graph: &BlockGraph,
613    start: IVec3,
614    kind: PatchRotationKind,
615    incident: &[PipeIncidence],
616    errors: &mut Vec<BlockGraphError>,
617) {
618    let end = kind.end_position(start);
619    for endpoint in [start, end] {
620        let pipes = pipes_at_endpoint(incident, start, endpoint);
621        if pipes.len() != 1 {
622            errors.push(
623                InvalidBlockGraphError::PatchRotationEndpointPipeCount {
624                    pos: start,
625                    endpoint,
626                    count: pipes.len(),
627                }
628                .into(),
629            );
630            continue;
631        }
632        let pipe = pipes[0];
633        let neighbor = pipe_neighbor_at(pipe, endpoint)
634            .expect("pipe selected for endpoint must include that endpoint");
635        if (neighbor - endpoint).abs() != IVec3::Z {
636            errors.push(
637                InvalidBlockGraphError::PatchRotationPipeNotTemporal {
638                    pos: start,
639                    endpoint,
640                }
641                .into(),
642            );
643            continue;
644        }
645        if endpoint == start && pipe.is_hadamard() {
646            errors
647                .push(InvalidBlockGraphError::PatchRotationStartPipeHadamard { pos: start }.into());
648            continue;
649        }
650        let expected_basis = kind
651            .pipe_face_bases_at_endpoint(start, endpoint)
652            .expect("patch rotation endpoint was checked above")[UDirection::X.index()];
653        let actual_basis = pipe_neighbor_basis_at_endpoint(graph, pipe, endpoint);
654        if actual_basis.is_some_and(|actual| (actual != expected_basis) ^ pipe.is_hadamard()) {
655            errors.push(
656                InvalidBlockGraphError::PatchRotationBoundaryMismatch {
657                    pos: start,
658                    endpoint,
659                    expected: expected_basis,
660                    actual: actual_basis,
661                }
662                .into(),
663            );
664        }
665    }
666}
667
668fn pipe_neighbor_basis_at_endpoint(
669    graph: &BlockGraph,
670    pipe: &Pipe,
671    endpoint: IVec3,
672) -> Option<Basis> {
673    let neighbor_pos = pipe_neighbor_at(pipe, endpoint)?;
674    graph.infer_pipe_endpoint_face_bases(pipe, neighbor_pos)[UDirection::X.index()]
675}
676
677/// Collects the two rules a cube's height imposes on its pipes.
678///
679/// Height agreement is checked pairwise across spacelike pipes, which is
680/// equivalent to the component-wide statement `parser::lower` propagates:
681/// spatial components are exactly the transitive closure of spacelike pipes, so
682/// pairwise equality along every edge is component-wide equality. Per-edge is
683/// also what lets the message name the offending *pair*.
684fn collect_cube_height_errors(
685    block: &Block,
686    incident: &[PipeIncidence],
687    errors: &mut Vec<BlockGraphError>,
688) {
689    let height = block.height();
690    let cells = block.height_cells();
691    let top = block.pos() + IVec3::new(0, 0, cells as i32 - 1);
692
693    for &(u_pos, v_pos, u, v, _) in incident {
694        let (endpoint, other_endpoint, other_block) = if u.pos() == block.pos() {
695            (u_pos, v_pos, v)
696        } else if v.pos() == block.pos() {
697            (v_pos, u_pos, u)
698        } else {
699            continue;
700        };
701        let delta = other_endpoint - endpoint;
702
703        if delta.z == 0 {
704            if cells > 1 && endpoint != block.pos() {
705                errors.push(
706                    InvalidBlockGraphError::CubeInvalidPipeEndpoint {
707                        pos: block.pos(),
708                        endpoint,
709                    }
710                    .into(),
711                );
712                continue;
713            }
714            if other_block.kind.is_cube() && other_block.height() != height {
715                errors.push(
716                    InvalidBlockGraphError::CubeHeightSpatialMismatch {
717                        pos: block.pos(),
718                        neighbor: other_block.pos(),
719                        height,
720                        neighbor_height: other_block.height(),
721                    }
722                    .into(),
723                );
724                continue;
725            }
726        } else if cells > 1 {
727            let valid_temporal_endpoint = (endpoint == block.pos() && delta == IVec3::NEG_Z)
728                || (endpoint == top && delta == IVec3::Z);
729            if !valid_temporal_endpoint {
730                errors.push(
731                    InvalidBlockGraphError::CubeInvalidPipeEndpoint {
732                        pos: block.pos(),
733                        endpoint,
734                    }
735                    .into(),
736                );
737            }
738        }
739    }
740}
741
742fn pipes_at_endpoint<'a>(
743    incident: &[PipeIncidence<'a>],
744    owner_pos: IVec3,
745    endpoint: IVec3,
746) -> Vec<&'a Pipe> {
747    incident
748        .iter()
749        .filter_map(|&(u_pos, v_pos, u, v, pipe)| {
750            let touches_endpoint = (u.pos() == owner_pos && u_pos == endpoint)
751                || (v.pos() == owner_pos && v_pos == endpoint);
752            touches_endpoint.then_some(pipe)
753        })
754        .collect()
755}
756
757fn pipe_neighbor_at(pipe: &Pipe, endpoint: IVec3) -> Option<IVec3> {
758    if pipe.src() == endpoint {
759        Some(pipe.dst())
760    } else if pipe.dst() == endpoint {
761        Some(pipe.src())
762    } else {
763        None
764    }
765}
766
767#[cfg(test)]
768mod tests {
769    use super::*;
770    use crate::{Action, FeedbackTarget, PauliBasis};
771    use crate::{CubeKind, Expr, SelectiveKind, WalkingBoundaryKind, WalkingKind};
772    use glam::IVec2;
773
774    #[test]
775    fn structural_errors_lists_every_offending_block() {
776        let mut graph = BlockGraph::new();
777        // Two independent lone ports, each missing its single pipe.
778        graph.add_block(Block::new(IVec3::ZERO, BlockKind::Port));
779        graph.add_block(Block::new(IVec3::new(4, 0, 0), BlockKind::Port));
780
781        let errors = structural_errors(&graph);
782
783        assert_eq!(errors.len(), 2, "{errors:?}");
784        assert_eq!(
785            validate_structure(&graph)
786                .expect_err("graph is invalid")
787                .to_string(),
788            errors[0].to_string(),
789            "fail-fast validation reports the first collected error"
790        );
791    }
792
793    /// Helper to create a `Measure` action with a dummy block target.
794    fn measurement(name: &str) -> Action {
795        Action::Measure {
796            target: MeasureTarget::Node(IVec3::ZERO),
797            name: name.to_string(),
798        }
799    }
800
801    #[test]
802    fn resolve_must_target_selective_block() {
803        // Resolve targeting a cube block → rejected during graph validation.
804        let mut g = BlockGraph::new();
805        g.add_block(Block::new(
806            IVec3::new(0, 0, 0),
807            BlockKind::Cube(CubeKind::ZXZ),
808        ));
809        g.add_block(Block::new(
810            IVec3::new(1, 0, 0),
811            BlockKind::Cube(CubeKind::ZXZ),
812        ));
813        g.set_actions_unchecked(vec![
814            Action::Measure {
815                target: MeasureTarget::Node(IVec3::new(1, 0, 0)),
816                name: "m".to_string(),
817            },
818            Action::Resolve {
819                target: IVec3::new(0, 0, 0),
820                condition: Expr::Var("m".to_string()),
821            },
822        ]);
823        let err = validate(&g).unwrap_err();
824        assert!(
825            matches!(
826                err,
827                BlockGraphError::InvalidAction(InvalidActionError::InvalidResolveTarget(..))
828            ),
829            "expected InvalidResolveTarget, got: {err:?}",
830        );
831    }
832
833    #[test]
834    fn validate_rechecks_dag_actions_after_graph_mutation() {
835        let mut graph = BlockGraph::new();
836        graph.add_block(Block::new(
837            glam::ivec3(0, 0, 0),
838            BlockKind::Cube(CubeKind::ZXZ),
839        ));
840        graph.add_block(Block::new(
841            glam::ivec3(0, 0, 1),
842            BlockKind::Cube(CubeKind::ZXZ),
843        ));
844        graph.add_block(Block::new(
845            glam::ivec3(2, 0, 0),
846            BlockKind::Selective(SelectiveKind::XY),
847        ));
848        graph.add_block(Block::new(
849            glam::ivec3(2, 0, -1),
850            BlockKind::Cube(CubeKind::ZXZ),
851        ));
852        graph.add_pipe(Pipe::new(glam::ivec3(0, 0, 0), Direction::ZPLUS));
853        graph.add_pipe(Pipe::new(glam::ivec3(2, 0, -1), Direction::ZPLUS));
854        graph.set_actions_unchecked(vec![
855            Action::Measure {
856                target: MeasureTarget::Node(glam::ivec3(0, 0, 1)),
857                name: "m".to_string(),
858            },
859            Action::Resolve {
860                target: glam::ivec3(2, 0, 0),
861                condition: Expr::Var("m".to_string()),
862            },
863        ]);
864        let err = validate(&graph);
865        assert!(err.is_ok(), "{err:?}");
866
867        graph.add_block(Block::new(
868            glam::ivec3(4, 0, -1),
869            BlockKind::Cube(CubeKind::ZXZ),
870        ));
871        graph.add_block(Block::new(
872            glam::ivec3(4, 0, 0),
873            BlockKind::Selective(SelectiveKind::XY),
874        ));
875        graph.add_pipe(Pipe::new(glam::ivec3(4, 0, -1), Direction::ZPLUS));
876
877        let err = graph.validate().unwrap_err();
878        assert!(matches!(
879            err,
880            BlockGraphError::InvalidAction(InvalidActionError::MissingResolveForSelective {
881                target
882            }) if target == glam::ivec3(4, 0, 0)
883        ));
884    }
885
886    #[test]
887    fn validate_rejects_dependency_cycles_from_action_dag() {
888        let mut graph = BlockGraph::new();
889        graph.add_block(Block::new(
890            glam::ivec3(0, 0, -1),
891            BlockKind::Cube(CubeKind::ZXZ),
892        ));
893        graph.add_block(Block::new(
894            glam::ivec3(0, 0, 0),
895            BlockKind::Selective(SelectiveKind::XY),
896        ));
897        graph.add_pipe(Pipe::new(glam::ivec3(0, 0, -1), Direction::ZPLUS));
898        graph.set_actions_unchecked(vec![
899            Action::Measure {
900                target: MeasureTarget::Node(glam::ivec3(0, 0, 0)),
901                name: "m".into(),
902            },
903            Action::Resolve {
904                target: glam::ivec3(0, 0, 0),
905                condition: Expr::Var("m".into()),
906            },
907        ]);
908        let err = validate(&graph).unwrap_err();
909        assert!(
910            matches!(
911                err,
912                BlockGraphError::InvalidAction(InvalidActionError::DependencyCycle { .. })
913            ),
914            "expected DependencyCycle, got: {err:?}",
915        );
916    }
917
918    #[test]
919    fn boundary_nodes_require_exactly_one_pipe() {
920        for kind in [
921            BlockKind::Port,
922            BlockKind::Y,
923            BlockKind::Measurement(Basis::X),
924            BlockKind::T,
925            BlockKind::Selective(SelectiveKind::XY),
926        ] {
927            let mut g = BlockGraph::new();
928            g.add_block(Block::new(IVec3::new(0, 0, 0), kind));
929
930            let err = validate(&g).unwrap_err();
931            assert!(
932                matches!(
933                    err,
934                    BlockGraphError::Invalid(InvalidBlockGraphError::NotExactlySinglePipe(_))
935                ),
936                "expected NotExactlySinglePipe for {kind:?}, got: {err:?}",
937            );
938        }
939    }
940
941    #[test]
942    fn spatial_ports_require_roles_and_temporal_roles_must_match_time() {
943        let mut spatial = BlockGraph::new();
944        spatial.add_block(Block::new(IVec3::ZERO, BlockKind::Port));
945        spatial.add_block(Block::new(IVec3::X, BlockKind::Cube(CubeKind::ZXZ)));
946        spatial.add_pipe(Pipe::new(IVec3::ZERO, Direction::XPLUS));
947        assert!(matches!(
948            validate(&spatial),
949            Err(BlockGraphError::Invalid(
950                InvalidBlockGraphError::SpatialPortRoleRequired(IVec3::ZERO)
951            ))
952        ));
953        spatial
954            .set_port_role(IVec3::ZERO, crate::PortRole::Input)
955            .unwrap();
956        validate(&spatial).expect("directed spatial Port validates");
957        spatial
958            .set_port_role(IVec3::ZERO, crate::PortRole::Multiplex)
959            .unwrap();
960        validate(&spatial).expect("Multiplex spatial Port validates");
961
962        let mut temporal = BlockGraph::new();
963        temporal.add_block(
964            Block::new(IVec3::ZERO, BlockKind::Port)
965                .with_port_role(crate::PortRole::Output)
966                .unwrap(),
967        );
968        temporal.add_block(Block::new(IVec3::Z, BlockKind::Cube(CubeKind::ZXZ)));
969        temporal.add_pipe(Pipe::new(IVec3::ZERO, Direction::ZPLUS));
970        assert!(matches!(
971            validate(&temporal),
972            Err(BlockGraphError::Invalid(
973                InvalidBlockGraphError::TemporalPortRoleMismatch { .. }
974            ))
975        ));
976        temporal
977            .set_port_role(IVec3::ZERO, crate::PortRole::Multiplex)
978            .unwrap();
979        assert!(matches!(
980            validate(&temporal),
981            Err(BlockGraphError::Invalid(
982                InvalidBlockGraphError::TemporalPortRoleMismatch { .. }
983            ))
984        ));
985    }
986
987    #[test]
988    fn walking_blocks_may_be_unconnected() {
989        let mut graph = BlockGraph::new();
990        graph.add_block(Block::new(
991            IVec3::ZERO,
992            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::X).unwrap()),
993        ));
994
995        validate(&graph).unwrap();
996    }
997
998    #[test]
999    fn walking_soft_corridor_allows_same_start_layer_ports() {
1000        let mut graph = BlockGraph::new();
1001        graph.add_block(Block::new(
1002            IVec3::ZERO,
1003            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::ONE).unwrap()),
1004        ));
1005
1006        graph
1007            .try_add_block(
1008                Block::new(IVec3::new(1, 0, 0), BlockKind::Port)
1009                    .with_port_role(crate::PortRole::Input)
1010                    .unwrap(),
1011            )
1012            .expect("same-start-layer port may share walking soft corridor");
1013        graph.add_block(Block::new(
1014            IVec3::new(2, 0, 0),
1015            BlockKind::Cube(CubeKind::ZXZ),
1016        ));
1017        graph.add_pipe(Pipe::new(IVec3::new(1, 0, 0), Direction::XPLUS));
1018
1019        validate(&graph).unwrap();
1020    }
1021
1022    #[test]
1023    fn walking_soft_corridor_rejects_upper_layer_ports() {
1024        let mut graph = BlockGraph::new();
1025        graph.add_block(Block::new(
1026            IVec3::ZERO,
1027            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::ONE).unwrap()),
1028        ));
1029
1030        let err = graph
1031            .try_add_block(Block::new(IVec3::new(1, 0, 1), BlockKind::Port))
1032            .expect_err("upper-layer port cannot share walking soft corridor");
1033
1034        assert!(matches!(
1035            err,
1036            BlockGraphError::BlockPositionOccupied(pos) if pos == IVec3::new(1, 0, 1)
1037        ));
1038    }
1039
1040    #[test]
1041    fn walking_soft_corridor_allows_parallel_same_layer_walking() {
1042        let mut graph = BlockGraph::new();
1043        graph.add_block(Block::new(
1044            IVec3::ZERO,
1045            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::ONE).unwrap()),
1046        ));
1047
1048        graph
1049            .try_add_block(Block::new(
1050                IVec3::Y,
1051                BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::XZX, IVec2::ONE).unwrap()),
1052            ))
1053            .expect("parallel same-layer walking blocks may share soft corridors");
1054
1055        validate(&graph).unwrap();
1056    }
1057
1058    #[test]
1059    fn walking_soft_corridor_rejects_nonparallel_walking() {
1060        let mut graph = BlockGraph::new();
1061        graph.add_block(Block::new(
1062            IVec3::ZERO,
1063            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::ONE).unwrap()),
1064        ));
1065
1066        let err = graph
1067            .try_add_block(Block::new(
1068                IVec3::X,
1069                BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::Y).unwrap()),
1070            ))
1071            .expect_err("nonparallel walking blocks cannot share soft corridors");
1072
1073        assert!(matches!(
1074            err,
1075            BlockGraphError::BlockPositionOccupied(pos) if pos == IVec3::new(1, 0, 0)
1076        ));
1077    }
1078
1079    #[test]
1080    fn walking_soft_corridor_rejects_different_start_layer_walking() {
1081        let mut graph = BlockGraph::new();
1082        graph.add_block(Block::new(
1083            IVec3::ZERO,
1084            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::ONE).unwrap()),
1085        ));
1086
1087        let err = graph
1088            .try_add_block(Block::new(
1089                IVec3::new(1, 0, 1),
1090                BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::ONE).unwrap()),
1091            ))
1092            .expect_err("different-start-layer walking blocks cannot share soft corridors");
1093
1094        assert!(matches!(
1095            err,
1096            BlockGraphError::BlockPositionOccupied(pos) if pos == IVec3::new(1, 0, 1)
1097        ));
1098    }
1099
1100    #[test]
1101    fn walking_start_accepts_past_temporal_pipe() {
1102        let mut graph = BlockGraph::new();
1103        graph.add_block(Block::new(IVec3::NEG_Z, BlockKind::Port));
1104        graph.add_block(Block::new(
1105            IVec3::ZERO,
1106            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::X).unwrap()),
1107        ));
1108        graph.add_pipe(Pipe::new(IVec3::NEG_Z, Direction::ZPLUS));
1109
1110        validate(&graph).unwrap();
1111    }
1112
1113    #[test]
1114    fn walking_end_accepts_future_temporal_pipe() {
1115        let mut graph = BlockGraph::new();
1116        let walking = WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::X).expect("valid movement");
1117        graph.add_block(Block::new(IVec3::ZERO, BlockKind::Walking(walking)));
1118        graph.add_block(Block::new(IVec3::new(1, 0, 2), BlockKind::Port));
1119        graph.add_pipe(Pipe::new(
1120            walking.end_position(IVec3::ZERO),
1121            Direction::ZPLUS,
1122        ));
1123
1124        validate(&graph).unwrap();
1125    }
1126
1127    #[test]
1128    fn walking_rejects_spatial_pipe_at_endpoint() {
1129        let mut graph = BlockGraph::new();
1130        graph.add_block(Block::new(
1131            IVec3::ZERO,
1132            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::ZXZ, IVec2::X).unwrap()),
1133        ));
1134        graph.add_block(Block::new(IVec3::NEG_X, BlockKind::Port));
1135        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::XMINUS));
1136
1137        let err = validate(&graph).unwrap_err();
1138
1139        assert!(matches!(
1140            err,
1141            BlockGraphError::Invalid(InvalidBlockGraphError::WalkingPipeNotTemporal {
1142                pos,
1143                endpoint
1144            }) if pos == IVec3::ZERO && endpoint == IVec3::ZERO
1145        ));
1146    }
1147
1148    #[test]
1149    fn walking_participates_in_lattice_surgery_orientation_checks() {
1150        let mut graph = BlockGraph::new();
1151        graph.add_block(Block::new(
1152            IVec3::ZERO,
1153            BlockKind::Walking(WalkingKind::new(WalkingBoundaryKind::XZZ, IVec2::X).unwrap()),
1154        ));
1155        graph.add_block(Block::new(
1156            IVec3::new(1, 0, 2),
1157            BlockKind::Cube(CubeKind::ZXX),
1158        ));
1159        graph.add_pipe(Pipe::new(IVec3::new(1, 0, 1), Direction::ZPLUS));
1160
1161        let err = validate(&graph).unwrap_err();
1162
1163        assert!(matches!(
1164            err,
1165            BlockGraphError::Invalid(InvalidBlockGraphError::OrientationContradiction(a, b))
1166                if a == IVec3::new(1, 0, 1) && b == IVec3::new(1, 0, 2)
1167        ));
1168    }
1169
1170    #[test]
1171    fn patch_rotation_requires_temporal_pipes_at_start_and_end() {
1172        let mut graph = BlockGraph::new();
1173        let kind = PatchRotationKind::new(Basis::X, IVec2::X).unwrap();
1174        graph.add_block(Block::new(IVec3::ZERO, BlockKind::PatchRotation(kind)));
1175
1176        let err = validate(&graph).unwrap_err();
1177
1178        assert!(matches!(
1179            err,
1180            BlockGraphError::Invalid(InvalidBlockGraphError::PatchRotationEndpointPipeCount {
1181                pos,
1182                endpoint,
1183                count: 0
1184            }) if pos == IVec3::ZERO && endpoint == IVec3::ZERO
1185        ));
1186    }
1187
1188    #[test]
1189    fn patch_rotation_allows_hadamard_only_at_end() {
1190        let mut graph = BlockGraph::new();
1191        let kind = PatchRotationKind::new(Basis::X, IVec2::X).unwrap();
1192        graph.add_block(Block::new(IVec3::ZERO, BlockKind::PatchRotation(kind)));
1193        graph.add_block(Block::new(IVec3::NEG_Z, BlockKind::Port));
1194        graph.add_block(Block::new(IVec3::new(1, 0, 2), BlockKind::Port));
1195        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::ZMINUS));
1196        graph.add_pipe(Pipe::new(kind.end_position(IVec3::ZERO), Direction::ZPLUS).with_hadamard());
1197
1198        validate(&graph).unwrap();
1199
1200        graph
1201            .set_pipe_hadamard(IVec3::ZERO, IVec3::NEG_Z, true)
1202            .unwrap();
1203        assert!(matches!(
1204            validate(&graph),
1205            Err(BlockGraphError::Invalid(
1206                InvalidBlockGraphError::PatchRotationStartPipeHadamard { pos }
1207            )) if pos == IVec3::ZERO
1208        ));
1209    }
1210
1211    #[test]
1212    fn patch_rotation_rejects_spatial_pipe_at_endpoint() {
1213        let mut graph = BlockGraph::new();
1214        let kind = PatchRotationKind::new(Basis::X, IVec2::X).unwrap();
1215        graph.add_block(Block::new(IVec3::ZERO, BlockKind::PatchRotation(kind)));
1216        graph.add_block(Block::new(IVec3::NEG_Z, BlockKind::Port));
1217        graph.add_block(Block::new(IVec3::new(1, 0, 2), BlockKind::Port));
1218        graph.add_block(Block::new(IVec3::NEG_X, BlockKind::Port));
1219        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::ZMINUS));
1220        graph.add_pipe(Pipe::new(kind.end_position(IVec3::ZERO), Direction::ZPLUS));
1221        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::XMINUS));
1222
1223        let err = validate(&graph).unwrap_err();
1224
1225        assert!(matches!(
1226            err,
1227            BlockGraphError::Invalid(InvalidBlockGraphError::PatchRotationEndpointPipeCount {
1228                pos,
1229                endpoint,
1230                count: 2
1231            }) if pos == IVec3::ZERO && endpoint == IVec3::ZERO
1232        ));
1233    }
1234
1235    #[test]
1236    fn patch_rotation_rejects_mismatched_start_boundary_orientation() {
1237        let mut graph = BlockGraph::new();
1238        let kind = PatchRotationKind::new(Basis::X, IVec2::X).unwrap();
1239        graph.add_block(Block::new(IVec3::ZERO, BlockKind::PatchRotation(kind)));
1240        graph.add_block(Block::new(IVec3::NEG_Z, BlockKind::Cube(CubeKind::XXZ)));
1241        graph.add_block(Block::new(IVec3::new(1, 0, 2), BlockKind::Port));
1242        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::ZMINUS));
1243        graph.add_pipe(Pipe::new(kind.end_position(IVec3::ZERO), Direction::ZPLUS));
1244
1245        let err = validate(&graph).unwrap_err();
1246
1247        assert!(matches!(
1248            err,
1249            BlockGraphError::Invalid(InvalidBlockGraphError::OrientationContradiction(a, b))
1250                if a == IVec3::ZERO && b == IVec3::NEG_Z
1251        ));
1252    }
1253
1254    #[test]
1255    fn spatially_connected_cubes_must_have_matching_height() {
1256        let mut graph = BlockGraph::new();
1257        graph.add_block(
1258            Block::new(IVec3::ZERO, BlockKind::Cube(CubeKind::ZXZ))
1259                .with_height("2d".parse().expect("valid height"))
1260                .unwrap(),
1261        );
1262        graph.add_block(
1263            Block::new(IVec3::X, BlockKind::Cube(CubeKind::ZXZ))
1264                .with_height("3d".parse().expect("valid height"))
1265                .unwrap(),
1266        );
1267        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::XPLUS));
1268
1269        assert!(matches!(
1270            graph.validate_structure(),
1271            Err(BlockGraphError::Invalid(
1272                InvalidBlockGraphError::CubeHeightSpatialMismatch { .. }
1273            ))
1274        ));
1275    }
1276
1277    #[test]
1278    fn multi_cell_cube_spatial_pipe_must_attach_at_anchor() {
1279        let mut graph = BlockGraph::new();
1280        graph.add_block(
1281            Block::new(IVec3::ZERO, BlockKind::Cube(CubeKind::ZXZ))
1282                .with_height("2d".parse().expect("valid height"))
1283                .unwrap(),
1284        );
1285        graph.add_block(
1286            Block::new(IVec3::new(1, 0, 1), BlockKind::Cube(CubeKind::ZXZ))
1287                .with_height("2d".parse().expect("valid height"))
1288                .unwrap(),
1289        );
1290        graph.add_pipe(Pipe::new(IVec3::new(0, 0, 1), Direction::XPLUS));
1291
1292        assert!(matches!(
1293            graph.validate_structure(),
1294            Err(BlockGraphError::Invalid(
1295                InvalidBlockGraphError::CubeInvalidPipeEndpoint { .. }
1296            ))
1297        ));
1298    }
1299
1300    #[test]
1301    fn multi_cell_cube_allows_bottom_past_and_top_future_temporal_pipes() {
1302        let mut graph = BlockGraph::new();
1303        graph.add_block(Block::new(IVec3::NEG_Z, BlockKind::Cube(CubeKind::ZXZ)));
1304        graph.add_block(
1305            Block::new(IVec3::ZERO, BlockKind::Cube(CubeKind::ZXZ))
1306                .with_height("3d".parse().expect("valid height"))
1307                .unwrap(),
1308        );
1309        graph.add_block(Block::new(
1310            IVec3::new(0, 0, 3),
1311            BlockKind::Cube(CubeKind::ZXZ),
1312        ));
1313        graph.add_pipe(Pipe::new(IVec3::NEG_Z, Direction::ZPLUS));
1314        graph.add_pipe(Pipe::new(IVec3::new(0, 0, 2), Direction::ZPLUS));
1315
1316        graph
1317            .validate_structure()
1318            .expect("scaled cube temporal endpoints should validate");
1319    }
1320
1321    #[test]
1322    fn resolve_alias_defined_later_than_raw_measurement_is_accepted() {
1323        let mut g = BlockGraph::new();
1324        g.add_block(Block::new(
1325            IVec3::new(0, 0, 2),
1326            BlockKind::Selective(SelectiveKind::XY),
1327        ));
1328        g.add_block(Block::new(
1329            IVec3::new(0, 0, 1),
1330            BlockKind::Cube(CubeKind::ZXZ),
1331        ));
1332        g.add_block(Block::new(
1333            IVec3::new(0, 0, 0),
1334            BlockKind::Cube(CubeKind::ZXZ),
1335        ));
1336        g.add_pipe(Pipe::new(IVec3::new(0, 0, 2), Direction::ZMINUS));
1337        g.set_actions_unchecked(vec![
1338            measurement("m"),
1339            Action::Let {
1340                name: "alias".to_string(),
1341                expr: Expr::Var("m".to_string()),
1342            },
1343            Action::Resolve {
1344                target: IVec3::new(0, 0, 2),
1345                condition: Expr::Var("alias".to_string()),
1346            },
1347        ]);
1348
1349        validate(&g).unwrap();
1350    }
1351
1352    #[test]
1353    fn empty_feedback_is_rejected_atomically_by_every_source_install() {
1354        for install in [
1355            BlockGraph::set_actions,
1356            BlockGraph::set_actions_deferred,
1357            BlockGraph::set_actions_lenient,
1358        ] {
1359            let mut graph =
1360                BlockGraph::from_blog_text("BLOG 1.0\n0: ZXZ [0,0,0]\nm = measure 0\n").unwrap();
1361            let previous = graph.actions();
1362            let error = install(
1363                &mut graph,
1364                vec![Action::Feedback {
1365                    targets: vec![],
1366                    condition: None,
1367                }],
1368            )
1369            .unwrap_err();
1370            assert!(matches!(
1371                error,
1372                BlockGraphError::InvalidAction(InvalidActionError::EmptyFeedbackTargets)
1373            ));
1374            assert_eq!(graph.actions(), previous);
1375        }
1376    }
1377
1378    #[test]
1379    fn feedback_accepts_a_future_measurement_binding() {
1380        let mut g = BlockGraph::new();
1381        g.add_block(Block::new(
1382            IVec3::new(0, 0, 0),
1383            BlockKind::Cube(CubeKind::ZXZ),
1384        ));
1385        g.add_block(Block::new(IVec3::Z, BlockKind::Cube(CubeKind::ZXZ)));
1386        g.add_pipe(crate::Pipe::new(IVec3::ZERO, crate::Direction::ZPLUS));
1387        g.set_actions_unchecked(vec![
1388            Action::Feedback {
1389                targets: vec![FeedbackTarget {
1390                    pauli: PauliBasis::Z,
1391                    target: IVec3::ZERO,
1392                    direction: None,
1393                }],
1394                condition: Some(Expr::Var("m".to_string())),
1395            },
1396            measurement("m"),
1397        ]);
1398
1399        validate(&g).unwrap();
1400        assert_eq!(
1401            BlockGraph::from_blog_text(&g.to_blog_text())
1402                .unwrap()
1403                .actions(),
1404            g.actions()
1405        );
1406        g.set_actions(vec![Action::Feedback {
1407            targets: vec![FeedbackTarget {
1408                pauli: PauliBasis::Z,
1409                target: IVec3::ZERO,
1410                direction: None,
1411            }],
1412            condition: None,
1413        }])
1414        .unwrap();
1415        assert_eq!(
1416            BlockGraph::from_blog_text(&g.to_blog_text())
1417                .unwrap()
1418                .actions(),
1419            g.actions()
1420        );
1421    }
1422
1423    #[test]
1424    fn discard_if_accepts_a_measurement_binding() {
1425        let mut g = BlockGraph::new();
1426        g.add_block(Block::new(
1427            IVec3::new(0, 0, 0),
1428            BlockKind::Cube(CubeKind::ZXZ),
1429        ));
1430        g.add_action(measurement("m")).unwrap();
1431        g.add_action(Action::DiscardIf(Expr::Var("m".to_string())))
1432            .unwrap();
1433
1434        validate(&g).unwrap();
1435    }
1436
1437    #[test]
1438    fn feedback_rejects_undefined_variables() {
1439        let mut g = BlockGraph::new();
1440        g.add_block(Block::new(
1441            IVec3::new(0, 0, 0),
1442            BlockKind::Cube(CubeKind::ZXZ),
1443        ));
1444        g.set_actions_unchecked(vec![Action::Feedback {
1445            targets: vec![FeedbackTarget {
1446                pauli: PauliBasis::Z,
1447                target: IVec3::ZERO,
1448                direction: None,
1449            }],
1450            condition: Some(Expr::Var("missing".to_string())),
1451        }]);
1452        let err = validate(&g).unwrap_err();
1453        assert!(
1454            matches!(
1455                err,
1456                BlockGraphError::InvalidAction(InvalidActionError::UndefinedVariable(_))
1457            ),
1458            "expected UndefinedVariable, got: {err:?}",
1459        );
1460    }
1461
1462    #[test]
1463    fn duplicate_measure_pipe_from_both_directions_is_rejected() {
1464        let mut g = BlockGraph::new();
1465        g.add_block(Block::new(
1466            IVec3::new(0, 0, 0),
1467            BlockKind::Cube(CubeKind::ZXZ),
1468        ));
1469        g.add_block(Block::new(
1470            IVec3::new(1, 0, 0),
1471            BlockKind::Cube(CubeKind::ZXZ),
1472        ));
1473        g.add_pipe(Pipe::new(IVec3::new(0, 0, 0), Direction::XPLUS));
1474        g.set_actions_unchecked(vec![
1475            Action::Measure {
1476                target: MeasureTarget::Edge {
1477                    src: IVec3::new(0, 0, 0),
1478                    dir: Direction::XPLUS,
1479                },
1480                name: "m0".into(),
1481            },
1482            Action::Measure {
1483                target: MeasureTarget::Edge {
1484                    src: IVec3::new(1, 0, 0),
1485                    dir: Direction::XMINUS,
1486                },
1487                name: "m1".into(),
1488            },
1489        ]);
1490
1491        let err = validate(&g).unwrap_err();
1492        assert!(
1493            matches!(
1494                err,
1495                BlockGraphError::InvalidAction(InvalidActionError::DuplicateMeasurementTarget(..))
1496            ),
1497            "expected DuplicateMeasurementTarget, got: {err:?}",
1498        );
1499    }
1500
1501    #[test]
1502    fn terminal_measurements_with_future_pipes_are_rejected() {
1503        for kind in [
1504            BlockKind::Measurement(Basis::X),
1505            BlockKind::Selective(SelectiveKind::XY),
1506        ] {
1507            let mut graph = BlockGraph::new();
1508            graph.add_block(Block::new(IVec3::ZERO, kind));
1509            graph.add_block(Block::new(IVec3::Z, BlockKind::Cube(CubeKind::ZXZ)));
1510            graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::ZPLUS));
1511
1512            let err = validate(&graph).unwrap_err();
1513            assert!(matches!(
1514                err,
1515                BlockGraphError::Invalid(InvalidBlockGraphError::FuturePipeNotAllowed(pos))
1516                    if pos == IVec3::ZERO
1517            ));
1518        }
1519    }
1520
1521    #[test]
1522    fn fixed_measurement_accepts_one_past_pipe() {
1523        let mut graph = BlockGraph::new();
1524        graph.add_block(Block::new(IVec3::NEG_Z, BlockKind::Cube(CubeKind::ZXZ)));
1525        graph.add_block(Block::new(IVec3::ZERO, BlockKind::Measurement(Basis::X)));
1526        graph.add_pipe(Pipe::new(IVec3::NEG_Z, Direction::ZPLUS));
1527
1528        validate(&graph).unwrap();
1529    }
1530
1531    #[test]
1532    fn feedback_rejects_missing_targets() {
1533        let mut g = BlockGraph::new();
1534        g.add_block(Block::new(
1535            IVec3::new(0, 0, 0),
1536            BlockKind::Cube(CubeKind::ZXZ),
1537        ));
1538        g.set_actions_unchecked(vec![Action::Feedback {
1539            targets: vec![crate::FeedbackTarget {
1540                pauli: crate::PauliBasis::Z,
1541                target: IVec3::new(1, 0, 0),
1542                direction: None,
1543            }],
1544            condition: None,
1545        }]);
1546
1547        let err = validate(&g).unwrap_err();
1548        assert!(
1549            matches!(
1550                err,
1551                BlockGraphError::InvalidAction(InvalidActionError::InvalidFeedbackTarget(..))
1552            ),
1553            "expected InvalidFeedbackTarget, got: {err:?}",
1554        );
1555    }
1556
1557    #[test]
1558    fn feedback_accepts_output_port_targets() {
1559        let mut g = BlockGraph::new();
1560        g.add_block(Block::new(
1561            IVec3::new(0, 0, 0),
1562            BlockKind::Cube(CubeKind::ZXZ),
1563        ));
1564        g.add_block(Block::new(IVec3::new(0, 0, 1), BlockKind::Port));
1565        g.add_pipe(Pipe::new(IVec3::new(0, 0, 0), Direction::ZPLUS));
1566        g.add_action(Action::Feedback {
1567            targets: vec![crate::FeedbackTarget {
1568                pauli: crate::PauliBasis::Z,
1569                target: IVec3::new(0, 0, 1),
1570                direction: None,
1571            }],
1572            condition: None,
1573        })
1574        .unwrap();
1575
1576        validate(&g).unwrap();
1577    }
1578
1579    #[test]
1580    fn feedback_accepts_existing_non_output_targets() {
1581        let mut g = BlockGraph::new();
1582        g.add_block(Block::new(
1583            IVec3::new(0, 0, 0),
1584            BlockKind::Cube(CubeKind::ZXZ),
1585        ));
1586        g.add_block(Block::new(IVec3::new(0, 0, 1), BlockKind::Port));
1587        g.add_pipe(Pipe::new(IVec3::new(0, 0, 0), Direction::ZPLUS));
1588        g.set_actions_unchecked(vec![Action::Feedback {
1589            targets: vec![crate::FeedbackTarget {
1590                pauli: crate::PauliBasis::Z,
1591                target: IVec3::new(0, 0, 0),
1592                direction: None,
1593            }],
1594            condition: None,
1595        }]);
1596
1597        validate(&g).unwrap();
1598    }
1599
1600    #[test]
1601    fn set_actions_rejects_measure_name_outside_identifier_grammar() {
1602        // A space cannot appear in a BLOG identifier, so the writer would emit a
1603        // name that fails to reparse — set_actions must reject it up front.
1604        let mut g = BlockGraph::new();
1605        g.add_block(Block::new(IVec3::ZERO, BlockKind::Cube(CubeKind::ZXZ)));
1606        let err = g
1607            .set_actions(vec![Action::Measure {
1608                target: MeasureTarget::Node(IVec3::ZERO),
1609                name: "bad name".to_string(),
1610            }])
1611            .expect_err("a name with a space cannot round-trip through to_blog_text");
1612        assert!(
1613            matches!(
1614                err,
1615                BlockGraphError::InvalidAction(InvalidActionError::InvalidActionName(_))
1616            ),
1617            "expected InvalidActionName, got: {err:?}",
1618        );
1619    }
1620
1621    #[test]
1622    fn set_actions_rejects_reserved_keyword_name() {
1623        // A reserved keyword re-emitted verbatim would be reparsed as a
1624        // keyword, not a name.
1625        let mut g = BlockGraph::new();
1626        g.add_block(Block::new(IVec3::ZERO, BlockKind::Cube(CubeKind::ZXZ)));
1627        let err = g
1628            .set_actions(vec![Action::Let {
1629                name: "measure".to_string(),
1630                expr: Expr::Var("m".to_string()),
1631            }])
1632            .expect_err("a reserved keyword name would not reparse");
1633        assert!(
1634            matches!(
1635                err,
1636                BlockGraphError::InvalidAction(InvalidActionError::InvalidActionName(_))
1637            ),
1638            "expected InvalidActionName, got: {err:?}",
1639        );
1640    }
1641
1642    #[test]
1643    fn set_actions_accepts_valid_name_and_round_trips() {
1644        let graph =
1645            crate::parse_blog_to_graph("BLOG 1.0\n\n  0: ZXZ [0, 0, 0]\n\n  m0 = measure 0\n")
1646                .expect("valid name parses");
1647        let text = graph.to_blog_text();
1648        let reparsed = crate::parse_blog_to_graph(&text).expect("round-trip reparses");
1649        assert_eq!(reparsed.to_blog_text(), text);
1650    }
1651}
bloq_graph/validate.rs

bloq_graph/
validate.rs
