bloq_compile/
signature.rs

1use std::fmt;
2
3use bloq_graph::{
4    Basis, Block, BlockGraph, BlockKind, Direction, UDirection, checked_add_position,
5};
6
7use crate::CompileError;
8use glam::IVec3;
9
10pub(crate) type BlockSignatureMap = crate::FxMap<IVec3, BlockSignature>;
11
12/// Connected faces reported by [`CompileError::InvalidConnectivity`].
13///
14/// Inspect which faces have pipes and Hadamard walls. Author connections using
15/// [`BlockGraph`] and [`bloq_graph::Pipe`]; the compiler derives this diagnostic.
16// Each face uses two bits in Direction::index() order: pipe, then Hadamard.
17// A Hadamard wall always implies a pipe.
18#[derive(Clone, Copy, Default, PartialEq, Eq, Hash)]
19pub struct Connectivity(u16);
20
21impl Connectivity {
22    /// No connections on any face.
23    pub(crate) const ISOLATED: Self = Self(0);
24
25    /// Whether the given face has a pipe.
26    pub const fn has_pipe(self, dir: Direction) -> bool {
27        self.0 & (1 << (dir.index() * 2)) != 0
28    }
29
30    /// Whether the given face has a hadamard pipe.
31    /// Only meaningful when [`has_pipe(dir)`](Self::has_pipe) is true.
32    pub const fn has_hadamard(self, dir: Direction) -> bool {
33        self.0 & (2 << (dir.index() * 2)) != 0
34    }
35
36    /// Set a pipe on the given face.
37    pub(crate) const fn with_pipe(self, dir: Direction) -> Self {
38        Self(self.0 | (1 << (dir.index() * 2)))
39    }
40
41    /// Set a plain pipe and clear any Hadamard bit on the face.
42    pub(crate) const fn with_plain_pipe(self, dir: Direction) -> Self {
43        let shift = dir.index() * 2;
44        Self((self.0 & !(0b11 << shift)) | (1 << shift))
45    }
46
47    /// Which spatial axes carry a Hadamard wall, as `(x, y)`. A wall on both
48    /// axes has no layer schedule that serves it (LIM-017), so callers reject
49    /// or skip that combination rather than pick one.
50    pub(crate) fn hadamard_wall_axes(self) -> (bool, bool) {
51        let on = |axis: [Direction; 2]| axis.into_iter().any(|dir| self.has_hadamard(dir));
52        (
53            on([Direction::XPLUS, Direction::XMINUS]),
54            on([Direction::YPLUS, Direction::YMINUS]),
55        )
56    }
57
58    /// Set a hadamard pipe on the given face (implies pipe).
59    pub(crate) const fn with_hadamard(self, dir: Direction) -> Self {
60        Self(self.0 | (0b11 << (dir.index() * 2)))
61    }
62
63    /// Iterate over spatial directions that have a pipe connection.
64    pub fn spatial_pipes(self) -> impl Iterator<Item = Direction> {
65        Direction::iter().filter(move |d| d.is_spatial() && self.has_pipe(*d))
66    }
67
68    /// Iterate over all directions that have a pipe connection.
69    pub fn pipe_dirs(self) -> impl Iterator<Item = Direction> {
70        Direction::iter().filter(move |d| self.has_pipe(*d))
71    }
72
73    /// Whether this block has no connections on any face.
74    pub const fn is_isolated(self) -> bool {
75        self.0 == 0
76    }
77
78    /// Whether the given face continues the block's own lattice.
79    ///
80    /// A spatial Hadamard *cedes* its face to the wall pipe, which owns the
81    /// seam-facing cell column outright, so the cube must treat that face as
82    /// closed everywhere a plain pipe would open it.
83    pub(crate) const fn has_open_edge(self, dir: Direction) -> bool {
84        self.has_pipe(dir) && !self.has_hadamard(dir)
85    }
86}
87
88impl fmt::Debug for Connectivity {
89    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
90        if *self == Self::ISOLATED {
91            return write!(f, "Connectivity(ISOLATED)");
92        }
93        write!(f, "Connectivity(")?;
94        let mut first = true;
95        for dir in Direction::iter() {
96            if self.has_pipe(dir) {
97                if !first {
98                    write!(f, " ")?;
99                }
100                first = false;
101                if self.has_hadamard(dir) {
102                    write!(f, "{dir}H")?;
103                } else {
104                    write!(f, "{dir}")?;
105                }
106            }
107        }
108        write!(f, ")")
109    }
110}
111
112/// The CX-slot depth shared by every cube in one z-layer spatial component.
113///
114/// Depth is a *component-wide* property: merged patches drive shared data
115/// qubits, so their syndrome rounds have to line up moment for moment. A
116/// component therefore takes the deepest schedule any of its members demands.
117#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
118pub(crate) enum LayerSchedule {
119    /// 4 slots — the compact schedule, for components of regular cubes only.
120    #[default]
121    Compact,
122    /// 5 slots — the padded schedule a spatial cube's quadrant hooks need.
123    Padded,
124    /// 6 slots — room for the GHZ bracket of a spatial Hadamard wall's extended
125    /// stabilizers on the X axis. Ordinary tiles idle through the bracket
126    /// slots.
127    Extended,
128    /// 6 slots — the diagonal transpose of [`Extended`](Self::Extended), for a
129    /// Y-axis spatial Hadamard wall.
130    ExtendedY,
131}
132
133impl LayerSchedule {
134    pub(crate) const fn is_extended(self) -> bool {
135        matches!(self, Self::Extended | Self::ExtendedY)
136    }
137}
138
139/// A block's kind plus its face connectivity, forming a unique compilation signature.
140///
141/// Two blocks with the same `BlockSignature` produce identical compiled output,
142/// enabling caching.
143#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
144pub(crate) struct BlockSignature {
145    pub kind: BlockKind,
146    /// For cube blocks: the syndrome-extraction rounds the cube's
147    /// [`CubeHeight`](bloq_graph::CubeHeight) resolves to at this compilation's
148    /// distance. `None` for every other kind.
149    ///
150    /// The *resolved* count, not the symbolic height: two heights resolving
151    /// alike at one distance compile to one template. The footprint half
152    /// (`cells`) is deliberately absent — a cube's template is one patch
153    /// replayed in time, and which faces are open is already in `connectivity`.
154    /// `cube_templates_may_share_rounds_across_different_footprints` pins that.
155    pub rounds: Option<u32>,
156    pub connectivity: Connectivity,
157    /// For Y, Measurement, Port, Selective, and T blocks: the top boundary basis
158    /// of the neighboring cube's surface code patch. Determined by the adjacent
159    /// cube's y-face basis. `None` for block kinds that do not attach to a
160    /// temporal cube seam.
161    pub boundary_basis: Option<Basis>,
162    /// For cube blocks: the CX-slot depth of the same-layer spatial component
163    /// this cube belongs to. `None` for every other kind.
164    pub layer_schedule: Option<LayerSchedule>,
165    /// For T blocks: the spatial side whose neighbor cell is reserved for the
166    /// Steane cultivation spill — picked deterministically from graph
167    /// occupancy by `t_surgery_sides`, so it is part of the signature (and thus
168    /// the template cache key: the surgery geometry is a rigid transform per
169    /// side). `None` for every other kind.
170    pub surgery_side: Option<Direction>,
171}
172
173impl BlockSignature {
174    /// Patch boundary basis for a Y, Measurement, Port, Selective, or T block,
175    /// inherited from its single temporal cube neighbour's top-boundary basis
176    /// (`kind.y()`), flipped across a Hadamard pipe.
177    pub(crate) fn temporal_neighbor_boundary_basis(
178        block: &Block,
179        graph: &BlockGraph,
180    ) -> Option<Basis> {
181        let block_pos = block.pos();
182        for dir in [Direction::ZPLUS, Direction::ZMINUS] {
183            let Ok(neighbor_endpoint) = checked_add_position(block_pos, dir.to_ivec3()) else {
184                continue;
185            };
186            let pipe = graph.get_pipe(block_pos, neighbor_endpoint);
187            if let Some(neighbor) = graph.get_endpoint_block(neighbor_endpoint)
188                && let BlockKind::Cube(kind) = neighbor.kind()
189                && let Some(pipe) = pipe
190            {
191                let basis = kind.y();
192                return Some(if pipe.is_hadamard() {
193                    basis.flip()
194                } else {
195                    basis
196                });
197            }
198            if let Some(pipe) = pipe {
199                return graph.infer_pipe_basis_from_endpoint(pipe, block_pos)[1];
200            }
201        }
202        None
203    }
204
205    pub(crate) fn template_connectivity(block: &Block, graph: &BlockGraph) -> Connectivity {
206        Self::connectivity(block, graph, false)
207    }
208
209    pub(crate) fn graph_connectivity(block: &Block, graph: &BlockGraph) -> Connectivity {
210        Self::connectivity(block, graph, true)
211    }
212
213    fn connectivity(block: &Block, graph: &BlockGraph, preserve_hadamard: bool) -> Connectivity {
214        if let BlockKind::Walking(kind) = block.kind() {
215            return Self::two_layer_endpoint_connectivity(
216                block.pos(),
217                kind.end_position(block.pos()),
218                graph,
219                preserve_hadamard,
220            );
221        }
222        if let BlockKind::PatchRotation(kind) = block.kind() {
223            return Self::two_layer_endpoint_connectivity(
224                block.pos(),
225                kind.end_position(block.pos()),
226                graph,
227                preserve_hadamard,
228            );
229        }
230
231        let mut connectivity = Connectivity::ISOLATED;
232        for dir in Direction::iter() {
233            let endpoint = block.endpoint_for_direction(dir);
234            let Ok(neighbor_pos) = checked_add_position(endpoint, dir.to_ivec3()) else {
235                continue;
236            };
237            if let Some(pipe) = graph.get_pipe(endpoint, neighbor_pos) {
238                // Template signatures strip *temporal* Hadamard flags — the
239                // realignment pipe node owns that flip, so H-adjacent blocks
240                // compile (and cache) as plain. A spatial Hadamard changes its
241                // endpoint cube: the cube cedes its seam column to the wall, so
242                // that flag must survive in the block signature.
243                connectivity = if pipe.is_hadamard() && (preserve_hadamard || dir.is_spatial()) {
244                    connectivity.with_hadamard(dir)
245                } else {
246                    connectivity.with_pipe(dir)
247                };
248            }
249        }
250        connectivity
251    }
252
253    fn two_layer_endpoint_connectivity(
254        start: IVec3,
255        end: IVec3,
256        graph: &BlockGraph,
257        preserve_hadamard: bool,
258    ) -> Connectivity {
259        let mut connectivity = Connectivity::ISOLATED;
260        for (endpoint, dir) in [(start, Direction::ZMINUS), (end, Direction::ZPLUS)] {
261            let Ok(neighbor_pos) = checked_add_position(endpoint, dir.to_ivec3()) else {
262                continue;
263            };
264            if let Some(pipe) = graph.get_pipe(endpoint, neighbor_pos) {
265                connectivity = if preserve_hadamard && pipe.is_hadamard() {
266                    connectivity.with_hadamard(dir)
267                } else {
268                    connectivity.with_pipe(dir)
269                };
270            }
271        }
272        connectivity
273    }
274}
275
276/// The syndrome rounds a cube compiles to at `distance`, rejecting a height that
277/// cannot produce a usable cube.
278///
279/// A cube's template is an initialization stage, a bulk loop and a measurement
280/// stage, so it needs at least two rounds before the loop is even empty; the
281/// bulk repetition count is `rounds - 2`. A height like `height=d/2` at `d = 3`
282/// clears that, but `height=d-3` at `d = 3` does not.
283pub(crate) fn cube_rounds(block: &Block, distance: u32) -> Result<u32, CompileError> {
284    let height = block.height();
285    let rounds = height.rounds(distance);
286    match u32::try_from(rounds) {
287        Ok(rounds) if rounds >= 2 => Ok(rounds),
288        _ => Err(CompileError::CubeHeightTooShort {
289            pos: block.pos(),
290            height,
291            distance,
292            rounds,
293        }),
294    }
295}
296
297pub(crate) fn derive_block_signature(
298    graph: &BlockGraph,
299    block: &Block,
300    distance: u32,
301    layer_schedule: LayerSchedule,
302    surgery_side: Option<Direction>,
303) -> Result<BlockSignature, CompileError> {
304    let kind = block.kind();
305    let is_cube = matches!(kind, BlockKind::Cube(_));
306    let boundary_basis = matches!(
307        kind,
308        BlockKind::Y
309            | BlockKind::Measurement(_)
310            | BlockKind::Port
311            | BlockKind::Selective(_)
312            | BlockKind::T
313    )
314    .then(|| BlockSignature::temporal_neighbor_boundary_basis(block, graph))
315    .flatten();
316    Ok(BlockSignature {
317        kind,
318        rounds: is_cube.then(|| cube_rounds(block, distance)).transpose()?,
319        connectivity: BlockSignature::template_connectivity(block, graph),
320        boundary_basis,
321        layer_schedule: is_cube.then_some(layer_schedule),
322        surgery_side,
323    })
324}
325
326pub(crate) fn block_signatures(
327    graph: &BlockGraph,
328    layer_schedules: &LayerScheduleMap,
329    distance: u32,
330) -> Result<BlockSignatureMap, CompileError> {
331    let t_surgery_sides = t_surgery_sides(graph)?;
332
333    graph
334        .blocks()
335        .map(|block| {
336            let signature = derive_block_signature(
337                graph,
338                block,
339                distance,
340                layer_schedule_at(layer_schedules, block.pos()),
341                t_surgery_sides.get(&block.pos()).copied(),
342            )?;
343            Ok((block.pos(), signature))
344        })
345        .collect()
346}
347
348/// Per-site signatures used to build relocatable definition objects before global
349/// component schedules and T-spill allocation are known. The module compiler
350/// expands these local seeds into every finite public-context variant; the
351/// linker later selects an exact signature with [`block_signatures`].
352pub(crate) fn relocatable_block_signatures(
353    graph: &BlockGraph,
354    positions: &crate::FxSet<IVec3>,
355    distance: u32,
356) -> Result<BlockSignatureMap, CompileError> {
357    graph
358        .blocks()
359        .filter(|block| positions.contains(&block.pos()))
360        .map(|block| {
361            let kind = block.kind();
362            let mut signature = derive_block_signature(
363                graph,
364                block,
365                distance,
366                LayerSchedule::default(),
367                (kind == BlockKind::T)
368                    .then_some(crate::block::fixed_bulk::t::SurgeryLayout::SIDE_PRIORITY[0]),
369            )?;
370            signature.layer_schedule = match kind {
371                BlockKind::Cube(cube) => Some(match signature.connectivity.hadamard_wall_axes() {
372                    (true, _) => LayerSchedule::Extended,
373                    (false, true) => LayerSchedule::ExtendedY,
374                    (false, false) if cube.is_spatial() => LayerSchedule::Padded,
375                    (false, false) => LayerSchedule::Compact,
376                }),
377                _ => None,
378            };
379            Ok((block.pos(), signature))
380        })
381        .collect()
382}
383
384/// Pick each T block's Steane-spill side: a side in
385/// [`SurgeryLayout::SIDE_PRIORITY`] whose neighbor cell is neither occupied by a
386/// block nor claimed as another T block's spill. The whole neighbor cell is
387/// reserved — conservative (the spill is only a margin strip), but it keeps two
388/// adjacent T blocks from silently sharing spill space.
389///
390/// Assignment is deterministic bipartite matching. An augmenting path may move
391/// an earlier T off its first choice when a later T needs that cell; unlike
392/// backtracking, work stays polynomial in the linked layout size.
393fn t_surgery_sides(graph: &BlockGraph) -> Result<crate::FxMap<IVec3, Direction>, CompileError> {
394    let t_positions: Vec<IVec3> = graph
395        .blocks()
396        .filter(|block| block.kind() == BlockKind::T)
397        .map(Block::pos)
398        .collect();
399    assign_linked_t_surgery_sides(t_positions, occupied_branch_positions(graph)?)
400}
401
402/// Shared templates must leave room for every authored branch arm.
403pub(crate) fn occupied_branch_positions(
404    graph: &BlockGraph,
405) -> Result<crate::FxSet<IVec3>, CompileError> {
406    let mut occupied = graph.occupied_positions().collect::<crate::FxSet<_>>();
407    for region in graph.branch_regions()? {
408        for block in region.on_false().blocks().chain(region.on_true().blocks()) {
409            occupied.extend(
410                block
411                    .reserved_offsets()
412                    .into_iter()
413                    .map(|offset| block.pos() + offset),
414            );
415        }
416    }
417    Ok(occupied)
418}
419
420pub(crate) fn assign_linked_t_surgery_sides(
421    mut t_positions: Vec<IVec3>,
422    reserved: crate::FxSet<IVec3>,
423) -> Result<crate::FxMap<IVec3, Direction>, CompileError> {
424    if t_positions.is_empty() {
425        return Ok(crate::FxMap::default());
426    }
427    t_positions.sort_by_key(|pos| (pos.z, pos.x, pos.y));
428
429    let candidates = t_positions
430        .iter()
431        .map(|&position| {
432            crate::block::fixed_bulk::t::SurgeryLayout::SIDE_PRIORITY
433                .into_iter()
434                .filter_map(|side| {
435                    let cell = checked_add_position(position, side.to_ivec3()).ok()?;
436                    (!reserved.contains(&cell)).then_some((cell, side))
437                })
438                .collect::<Vec<_>>()
439        })
440        .collect::<Vec<_>>();
441    let mut owner = crate::FxMap::<IVec3, usize>::default();
442    for (index, &position) in t_positions.iter().enumerate() {
443        if !augment_surgery_matching(index, &candidates, &mut crate::FxSet::default(), &mut owner) {
444            return Err(CompileError::TBlockNeedsFreeNeighbor { pos: position });
445        }
446    }
447    Ok(owner
448        .into_iter()
449        .map(|(cell, index)| {
450            let side = candidates[index]
451                .iter()
452                .find_map(|&(candidate, side)| (candidate == cell).then_some(side))
453                .expect("matched spill cell belongs to its T candidate set");
454            (t_positions[index], side)
455        })
456        .collect())
457}
458
459fn augment_surgery_matching(
460    index: usize,
461    candidates: &[Vec<(IVec3, Direction)>],
462    visited: &mut crate::FxSet<IVec3>,
463    owner: &mut crate::FxMap<IVec3, usize>,
464) -> bool {
465    for &(cell, _) in &candidates[index] {
466        if !visited.insert(cell) {
467            continue;
468        }
469        let previous = owner.get(&cell).copied();
470        if previous
471            .is_some_and(|previous| !augment_surgery_matching(previous, candidates, visited, owner))
472        {
473            continue;
474        }
475        owner.insert(cell, index);
476        return true;
477    }
478    false
479}
480
481pub(crate) type LayerScheduleMap = crate::FxMap<IVec3, LayerSchedule>;
482
483/// The schedule of the cube at `pos`; cubes outside the map are compact.
484pub(crate) fn layer_schedule_at(schedules: &LayerScheduleMap, pos: IVec3) -> LayerSchedule {
485    schedules.get(&pos).copied().unwrap_or_default()
486}
487
488/// Per-cube CX-slot depth, derived per z-layer spatial component.
489///
490/// Only the components that demand more than [`LayerSchedule::Compact`] are
491/// recorded, so the map stays empty for the common case. A component carrying
492/// walls on both spatial axes has no schedule at all (LIM-017), so it is
493/// rejected here rather than represented.
494pub(crate) fn join_component_layer_schedules(
495    graph: &BlockGraph,
496) -> Result<LayerScheduleMap, CompileError> {
497    // Without a spatial cube or Hadamard wall, every component is compact.
498    if !graph
499        .blocks()
500        .any(|block| matches!(block.kind(), BlockKind::Cube(kind) if kind.is_spatial()))
501        && !graph
502            .pipes()
503            .any(|pipe| pipe.is_hadamard() && pipe.dir().is_spatial())
504    {
505        return Ok(LayerScheduleMap::default());
506    }
507    let mut schedules = LayerScheduleMap::default();
508    let mut mixed = Vec::new();
509
510    // The z-layer spatial partition is `bloq_graph`'s, shared with the cube
511    // height propagation that runs at lowering time: both answer "which cubes
512    // drive the same data qubits, and therefore share a schedule". A component
513    // is named by its lowest member, which is also the position we blame.
514    for (layer, components) in graph.cube_layer_components() {
515        let root: crate::FxMap<IVec3, IVec3> = components
516            .iter()
517            .flat_map(|members| members.iter().map(|&pos| (pos, members[0])))
518            .collect();
519
520        // A spatial Hadamard wall outranks a spatial cube: its extended
521        // stabilizers need the GHZ bracket the padded depth lacks.
522        let mut demanded = crate::FxMap::<IVec3, LayerSchedule>::default();
523        let mut demand = |component: IVec3, schedule: LayerSchedule| {
524            let slot = demanded.entry(component).or_default();
525            *slot = (*slot).max(schedule);
526        };
527        for (&pos, &component) in &root {
528            if matches!(
529                graph.get_block(pos).map(Block::kind),
530                Some(BlockKind::Cube(kind)) if kind.is_spatial()
531            ) {
532                demand(component, LayerSchedule::Padded);
533            }
534        }
535
536        let mut wall_axes = crate::FxMap::<IVec3, (bool, bool)>::default();
537        for pipe in graph.layer(layer).spacelike_pipes() {
538            if !pipe.is_hadamard() {
539                continue;
540            }
541            let (src, dst) = pipe.endpoints();
542            let (Some(src), Some(dst)) =
543                (graph.get_endpoint_block(src), graph.get_endpoint_block(dst))
544            else {
545                continue;
546            };
547            let (Some(&component), Some(_)) = (root.get(&src.pos()), root.get(&dst.pos())) else {
548                continue;
549            };
550            let axes = wall_axes.entry(component).or_default();
551            match pipe.dir().as_udirection() {
552                UDirection::X => axes.0 = true,
553                UDirection::Y => axes.1 = true,
554                UDirection::Z => unreachable!("spatial Hadamard walls are not temporal"),
555            }
556        }
557        for (component, (has_x, has_y)) in wall_axes {
558            match (has_x, has_y) {
559                (true, true) => mixed.push(component),
560                (true, false) => demand(component, LayerSchedule::Extended),
561                (false, true) => demand(component, LayerSchedule::ExtendedY),
562                (false, false) => unreachable!("wall axis map is non-empty"),
563            }
564        }
565
566        for (&pos, component) in &root {
567            if let Some(&schedule) = demanded.get(component) {
568                schedules.insert(pos, schedule);
569            }
570        }
571    }
572
573    match mixed.into_iter().min_by_key(glam::IVec3::to_array) {
574        Some(pos) => Err(CompileError::MixedSpatialHadamardUnsupported { pos }),
575        None => Ok(schedules),
576    }
577}
578
579#[cfg(test)]
580mod tests {
581    use super::*;
582    use bloq_graph::{Pipe, WalkingBoundaryKind, WalkingKind};
583    use rstest::rstest;
584
585    use crate::{CompileConfig, CompileContext};
586
587    /// A hub whose spatial Hadamard walls run on *both* in-plane axes has no
588    /// single [`LayerSchedule`], so the compiler must reject it — blaming the
589    /// component's lowest coordinate — rather than silently picking one axis.
590    /// Compilation with and without the explicit audit must agree.
591    #[test]
592    fn quarter_turn_spatial_hadamard_is_rejected() {
593        let graph = BlockGraph::from_blog_text(
594            "BLOG 1.0\n\n\
595             0: ZZX [0, 0, 0]\n\
596             1: XZZ [0, 1, 0]\n\
597             2: ZXZ [1, 0, 0]\n\
598             3: Port [0, 1, 1]\n\
599             4: Port [1, 0, 1]\n\
600             [0, 0, 0] -H> +Y\n\
601             [0, 0, 0] -H> +X\n\
602             [0, 1, 0] -> +Z\n\
603             [1, 0, 0] -> +Z\n",
604        )
605        .expect("quarter-turn graph parses");
606        let ctx = CompileContext::new(CompileConfig::new(3));
607
608        assert!(matches!(
609            ctx.compile_and_validate(&graph),
610            Err(CompileError::MixedSpatialHadamardUnsupported { pos }) if pos == IVec3::ZERO
611        ));
612        assert!(matches!(
613            ctx.compile(&graph),
614            Err(CompileError::MixedSpatialHadamardUnsupported { pos }) if pos == IVec3::ZERO
615        ));
616    }
617
618    #[test]
619    fn spatial_cube_pads_its_whole_component() {
620        let mut graph = BlockGraph::new();
621        graph.add_block(Block::new(
622            IVec3::new(0, 0, 0),
623            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
624        ));
625        graph.add_block(Block::new(
626            IVec3::new(1, 0, 0),
627            BlockKind::Cube(bloq_graph::CubeKind::ZZX),
628        ));
629        graph.add_block(Block::new(IVec3::new(2, 0, 0), BlockKind::Y));
630        graph.add_block(Block::new(
631            IVec3::new(1, 1, 0),
632            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
633        ));
634        graph.add_pipe(Pipe::new(IVec3::new(1, 0, 0), Direction::YPLUS));
635
636        let regular = IVec3::new(0, 0, 0);
637        let spatial = IVec3::new(1, 0, 0);
638        let connected_regular = IVec3::new(1, 1, 0);
639        let y = IVec3::new(2, 0, 0);
640
641        // Exercise the production signature path rather than a per-block helper,
642        // so the test covers the same spatial-component set the compiler uses.
643        let signatures = block_signatures(
644            &graph,
645            &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
646            3,
647        )
648        .expect("valid graph");
649
650        assert_eq!(
651            signatures
652                .get(&regular)
653                .expect("regular cube signature")
654                .layer_schedule,
655            Some(LayerSchedule::Compact)
656        );
657        assert_eq!(
658            signatures
659                .get(&spatial)
660                .expect("spatial cube signature")
661                .layer_schedule,
662            Some(LayerSchedule::Padded)
663        );
664        assert_eq!(
665            signatures
666                .get(&connected_regular)
667                .expect("spatial-connected regular cube signature")
668                .layer_schedule,
669            Some(LayerSchedule::Padded)
670        );
671        assert_eq!(
672            signatures
673                .get(&y)
674                .expect("Y block signature")
675                .layer_schedule,
676            None
677        );
678    }
679
680    /// A cube at `pos` in the z = 0 layer.
681    fn cube(pos: IVec3, kind: bloq_graph::CubeKind) -> Block {
682        Block::new(pos, BlockKind::Cube(kind))
683    }
684
685    #[test]
686    fn spatial_hadamard_extends_its_whole_component() {
687        use bloq_graph::CubeKind::{XZX, ZXZ};
688
689        let mut graph = BlockGraph::new();
690        // A wall between two regular cubes, one of which merges on further.
691        graph.add_block(cube(IVec3::ZERO, XZX));
692        graph.add_block(cube(IVec3::new(1, 0, 0), XZX));
693        graph.add_block(cube(IVec3::new(1, 1, 0), ZXZ));
694        // A second component in the same layer, out of the wall's reach.
695        graph.add_block(cube(IVec3::new(5, 0, 0), ZXZ));
696        graph.add_pipe(Pipe::new(IVec3::new(1, 0, 0), Direction::YPLUS));
697        assert!(join_component_layer_schedules(&graph).unwrap().is_empty());
698        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::XPLUS).with_hadamard());
699
700        let schedules =
701            join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls");
702        for pos in [IVec3::ZERO, IVec3::new(1, 0, 0), IVec3::new(1, 1, 0)] {
703            assert_eq!(
704                layer_schedule_at(&schedules, pos),
705                LayerSchedule::Extended,
706                "{pos} shares the wall's component"
707            );
708        }
709        assert_eq!(
710            layer_schedule_at(&schedules, IVec3::new(5, 0, 0)),
711            LayerSchedule::Compact
712        );
713    }
714
715    #[test]
716    fn spatial_hadamard_outranks_a_spatial_cube_in_the_same_component() {
717        use bloq_graph::CubeKind::{XXZ, XZX};
718
719        let mut graph = BlockGraph::new();
720        graph.add_block(cube(IVec3::ZERO, XZX));
721        graph.add_block(cube(IVec3::new(1, 0, 0), XXZ));
722        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::XPLUS).with_hadamard());
723
724        let schedules =
725            join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls");
726        assert_eq!(
727            layer_schedule_at(&schedules, IVec3::new(1, 0, 0)),
728            LayerSchedule::Extended,
729            "the spatial cube's padded demand must not win over the wall's"
730        );
731        assert_eq!(
732            layer_schedule_at(&schedules, IVec3::ZERO),
733            LayerSchedule::Extended
734        );
735    }
736
737    /// Rounds resolve as `ceil(k*d) + n` on integers, and a cube that lands
738    /// below two rounds is rejected by name rather than compiled into a
739    /// template with no measurement stage.
740    #[rstest]
741    #[case("d/2", 3, 2)]
742    #[case("d/2", 7, 4)]
743    #[case("3d/2", 7, 11)]
744    #[case("3d+2", 7, 23)]
745    #[case("d-1", 7, 6)]
746    fn cube_rounds_resolve_the_height_at_the_code_distance(
747        #[case] height: &str,
748        #[case] distance: u32,
749        #[case] expected: u32,
750    ) {
751        let cube = Block::new(IVec3::ZERO, BlockKind::Cube(bloq_graph::CubeKind::ZXZ))
752            .with_height(height.parse().expect("valid height"))
753            .expect("cube accepts a height");
754
755        assert_eq!(
756            cube_rounds(&cube, distance).expect("height resolves"),
757            expected
758        );
759    }
760
761    #[rstest]
762    #[case("d-2", 3)]
763    #[case("d/2-1", 3)]
764    #[case("d-9", 7)]
765    fn cube_rounds_reject_a_height_below_two_rounds(#[case] height: &str, #[case] distance: u32) {
766        let cube = Block::new(
767            IVec3::new(1, 2, 3),
768            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
769        )
770        .with_height(height.parse().expect("valid height"))
771        .expect("cube accepts a height");
772
773        let error = cube_rounds(&cube, distance).expect_err("too short to compile");
774        let CompileError::CubeHeightTooShort { pos, rounds, .. } = error else {
775            panic!("expected a too-short height error, got {error}");
776        };
777        assert_eq!(pos, IVec3::new(1, 2, 3));
778        assert!(rounds < 2, "{rounds}");
779    }
780
781    #[test]
782    fn tall_cube_signature_checks_top_temporal_endpoint() {
783        let mut graph = BlockGraph::new();
784        graph.add_block(
785            Block::new(
786                IVec3::new(0, 0, 0),
787                BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
788            )
789            .with_height("2d".parse().expect("valid height"))
790            .unwrap(),
791        );
792        graph.add_block(Block::new(IVec3::new(0, 0, 2), BlockKind::Port));
793        graph.add_pipe(Pipe::new(IVec3::new(0, 0, 1), Direction::ZPLUS));
794
795        let signature = block_signatures(
796            &graph,
797            &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
798            3,
799        )
800        .expect("valid graph")[&IVec3::ZERO];
801
802        assert_eq!(signature.rounds, Some(6));
803        assert!(signature.connectivity.has_pipe(Direction::ZPLUS));
804    }
805
806    #[test]
807    fn tall_spatial_cube_does_not_mark_unconnected_overlapping_layer_cube() {
808        let mut graph = BlockGraph::new();
809        graph.add_block(Block::new(
810            IVec3::new(0, 0, 1),
811            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
812        ));
813        graph.add_block(
814            Block::new(
815                IVec3::new(1, 0, 0),
816                BlockKind::Cube(bloq_graph::CubeKind::ZZX),
817            )
818            .with_height("2d".parse().expect("valid height"))
819            .unwrap(),
820        );
821
822        let signatures = block_signatures(
823            &graph,
824            &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
825            3,
826        )
827        .expect("valid graph");
828
829        assert_eq!(
830            signatures[&IVec3::new(0, 0, 1)].layer_schedule,
831            Some(LayerSchedule::Compact)
832        );
833        assert_eq!(
834            signatures[&IVec3::new(1, 0, 0)].layer_schedule,
835            Some(LayerSchedule::Padded)
836        );
837    }
838
839    #[test]
840    fn y_boundary_basis_flips_across_hadamard_edge() {
841        let mut graph = BlockGraph::new();
842        graph.add_block(Block::new(IVec3::new(0, 0, 0), BlockKind::Y));
843        graph.add_block(Block::new(
844            IVec3::new(0, 0, 1),
845            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
846        ));
847        graph.add_pipe(Pipe::new(IVec3::new(0, 0, 0), Direction::ZPLUS).with_hadamard());
848
849        assert_eq!(
850            block_signatures(
851                &graph,
852                &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
853                3
854            )
855            .expect("valid graph")[&IVec3::new(0, 0, 0)]
856                .boundary_basis,
857            Some(Basis::Z)
858        );
859    }
860
861    #[test]
862    fn measurement_signature_inherits_boundary_basis_across_hadamard_edge() {
863        let mut graph = BlockGraph::new();
864        graph.add_block(Block::new(
865            IVec3::ZERO,
866            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
867        ));
868        graph.add_block(Block::new(IVec3::Z, BlockKind::Measurement(Basis::X)));
869        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::ZPLUS).with_hadamard());
870
871        let signatures = block_signatures(
872            &graph,
873            &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
874            3,
875        )
876        .expect("valid graph");
877        assert_eq!(signatures[&IVec3::Z].boundary_basis, Some(Basis::Z));
878        assert!(
879            signatures[&IVec3::Z]
880                .connectivity
881                .has_pipe(Direction::ZMINUS)
882        );
883    }
884
885    #[test]
886    fn y_boundary_basis_resolves_tall_cube_top_endpoint() {
887        let mut graph = BlockGraph::new();
888        graph.add_block(
889            Block::new(
890                IVec3::new(0, 0, 0),
891                BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
892            )
893            .with_height("2d".parse().expect("valid height"))
894            .unwrap(),
895        );
896        graph.add_block(Block::new(IVec3::new(0, 0, 2), BlockKind::Y));
897        graph.add_pipe(Pipe::new(IVec3::new(0, 0, 1), Direction::ZPLUS));
898
899        assert_eq!(
900            block_signatures(
901                &graph,
902                &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
903                3
904            )
905            .expect("valid graph")[&IVec3::new(0, 0, 2)]
906                .boundary_basis,
907            Some(Basis::X)
908        );
909    }
910
911    #[test]
912    fn y_boundary_basis_ignores_adjacent_unpiped_cube() {
913        let mut graph = BlockGraph::new();
914        graph.add_block(Block::new(IVec3::ZERO, BlockKind::Y));
915        graph.add_block(Block::new(
916            IVec3::Z,
917            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
918        ));
919
920        assert_eq!(
921            block_signatures(
922                &graph,
923                &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
924                3
925            )
926            .expect("valid graph")[&IVec3::ZERO]
927                .boundary_basis,
928            None
929        );
930    }
931
932    #[test]
933    fn y_boundary_basis_falls_back_to_graph_pipe_inference() {
934        let mut graph = BlockGraph::new();
935        graph.add_block(Block::new(IVec3::ZERO, BlockKind::Y));
936        graph.add_block(Block::new(IVec3::Z, BlockKind::Y));
937        graph.add_pipe(Pipe::new(IVec3::ZERO, Direction::ZPLUS));
938
939        assert_eq!(
940            graph.infer_pipe_basis(graph.pipes().next().unwrap())[1],
941            Some(Basis::Z)
942        );
943        assert_eq!(
944            block_signatures(
945                &graph,
946                &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
947                3
948            )
949            .expect("valid graph")[&IVec3::ZERO]
950                .boundary_basis,
951            Some(Basis::Z)
952        );
953    }
954
955    #[test]
956    fn walking_connectivity_checks_virtual_end_endpoint() {
957        let mut graph = BlockGraph::new();
958        let walking = WalkingKind::new(WalkingBoundaryKind::ZXZ, glam::ivec2(1, 1)).unwrap();
959        graph.add_block(Block::new(IVec3::ZERO, BlockKind::Walking(walking)));
960        graph.add_block(Block::new(IVec3::new(1, 1, 2), BlockKind::Port));
961        graph.add_pipe(Pipe::new(
962            walking.end_position(IVec3::ZERO),
963            Direction::ZPLUS,
964        ));
965
966        let signature = block_signatures(
967            &graph,
968            &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"),
969            3,
970        )
971        .expect("valid graph")[&IVec3::ZERO];
972
973        assert!(signature.connectivity.has_pipe(Direction::ZPLUS));
974        assert!(!signature.connectivity.has_pipe(Direction::ZMINUS));
975    }
976
977    /// A T block at `pos` under a ZXZ cube, optionally with same-layer neighbor
978    /// cubes boxing it in.
979    fn t_graph(pos: IVec3, neighbors: &[IVec3]) -> BlockGraph {
980        let mut graph = BlockGraph::new();
981        graph.add_block(Block::new(pos, BlockKind::T));
982        graph.add_block(Block::new(
983            pos + IVec3::Z,
984            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
985        ));
986        graph.add_pipe(Pipe::new(pos, Direction::ZPLUS));
987        for &neighbor in neighbors {
988            graph.add_block(Block::new(
989                neighbor,
990                BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
991            ));
992        }
993        graph
994    }
995
996    fn t_side(graph: &BlockGraph, pos: IVec3) -> Option<Direction> {
997        block_signatures(
998            graph,
999            &join_component_layer_schedules(graph).expect("no mixed spatial Hadamard walls"),
1000            3,
1001        )
1002        .expect("valid graph")[&pos]
1003            .surgery_side
1004    }
1005
1006    #[test]
1007    fn t_surgery_side_picks_first_free_in_priority_order() {
1008        let pos = IVec3::ZERO;
1009        // All four sides free: -y wins.
1010        assert_eq!(t_side(&t_graph(pos, &[]), pos), Some(Direction::YMINUS));
1011        // -y occupied: falls through to +x.
1012        assert_eq!(
1013            t_side(&t_graph(pos, &[IVec3::new(0, -1, 0)]), pos),
1014            Some(Direction::XPLUS)
1015        );
1016        // -y and +x occupied: +y.
1017        assert_eq!(
1018            t_side(
1019                &t_graph(pos, &[IVec3::new(0, -1, 0), IVec3::new(1, 0, 0)]),
1020                pos
1021            ),
1022            Some(Direction::YPLUS)
1023        );
1024    }
1025
1026    #[test]
1027    fn signature_neighbor_steps_do_not_wrap_at_coordinate_limits() {
1028        let pos = IVec3::new(i32::MAX, i32::MIN, 0);
1029        let graph = t_graph(pos, &[]);
1030
1031        assert_eq!(
1032            t_side(&graph, pos),
1033            Some(Direction::YPLUS),
1034            "-Y and +X overflow, so +Y is the first available spill side"
1035        );
1036
1037        let isolated = Block::new(IVec3::new(i32::MAX, 0, 0), BlockKind::Port);
1038        assert!(BlockSignature::template_connectivity(&isolated, &BlockGraph::new()).is_isolated());
1039    }
1040
1041    #[test]
1042    fn t_surgery_side_reservation_is_exclusive_between_t_blocks() {
1043        // Two T blocks whose only mutually free side is the single cell between
1044        // them: the left T (first in sorted (z, x, y) order) reserves it as its
1045        // +x spill, so the right T finds every side occupied or reserved.
1046        let mut graph = t_graph(IVec3::ZERO, &[IVec3::new(0, -1, 0), IVec3::new(2, -1, 0)]);
1047        graph.add_block(Block::new(IVec3::new(2, 0, 0), BlockKind::T));
1048        graph.add_block(Block::new(
1049            IVec3::new(2, 0, 1),
1050            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
1051        ));
1052        graph.add_pipe(Pipe::new(IVec3::new(2, 0, 0), Direction::ZPLUS));
1053        // Box the left T's remaining sides except +x, and the right T's +x/+y,
1054        // so the shared cell (1, 0, 0) is the decisive one.
1055        for boxed in [
1056            IVec3::new(0, 1, 0),
1057            IVec3::new(-1, 0, 0),
1058            IVec3::new(3, 0, 0),
1059            IVec3::new(2, 1, 0),
1060        ] {
1061            graph.add_block(Block::new(
1062                boxed,
1063                BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
1064            ));
1065        }
1066
1067        assert!(matches!(
1068            block_signatures(&graph, &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"), 3).unwrap_err(),
1069            CompileError::TBlockNeedsFreeNeighbor { pos } if pos == IVec3::new(2, 0, 0)
1070        ));
1071    }
1072
1073    #[test]
1074    fn t_surgery_matching_reassigns_for_a_later_blocks_only_option() {
1075        // The left T has two free sides (+x, +y); the right T's only free side
1076        // is the shared middle cell (1, 0, 0) — the left T's +x. A greedy
1077        // first-fit would grab it for the left T (priority: -y blocked, then
1078        // +x) and reject the graph; an augmenting path moves the left T to +y
1079        // and satisfies both.
1080        let mut graph = t_graph(IVec3::ZERO, &[IVec3::new(0, -1, 0)]);
1081        graph.add_block(Block::new(IVec3::new(2, 0, 0), BlockKind::T));
1082        graph.add_block(Block::new(
1083            IVec3::new(2, 0, 1),
1084            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
1085        ));
1086        graph.add_pipe(Pipe::new(IVec3::new(2, 0, 0), Direction::ZPLUS));
1087        for boxed in [
1088            IVec3::new(2, -1, 0),
1089            IVec3::new(3, 0, 0),
1090            IVec3::new(2, 1, 0),
1091        ] {
1092            graph.add_block(Block::new(
1093                boxed,
1094                BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
1095            ));
1096        }
1097
1098        assert_eq!(t_side(&graph, IVec3::ZERO), Some(Direction::YPLUS));
1099        assert_eq!(t_side(&graph, IVec3::new(2, 0, 0)), Some(Direction::XMINUS));
1100    }
1101
1102    #[test]
1103    fn t_block_boxed_on_all_sides_needs_free_neighbor() {
1104        let pos = IVec3::ZERO;
1105        let graph = t_graph(
1106            pos,
1107            &[
1108                IVec3::new(0, -1, 0),
1109                IVec3::new(1, 0, 0),
1110                IVec3::new(0, 1, 0),
1111                IVec3::new(-1, 0, 0),
1112            ],
1113        );
1114        assert!(matches!(
1115            block_signatures(&graph, &join_component_layer_schedules(&graph).expect("no mixed spatial Hadamard walls"), 3).unwrap_err(),
1116            CompileError::TBlockNeedsFreeNeighbor { pos: p } if p == pos
1117        ));
1118    }
1119
1120    #[test]
1121    fn t_boundary_basis_inherits_and_flips_across_hadamard_edge() {
1122        let plain = t_graph(IVec3::ZERO, &[]);
1123        assert_eq!(
1124            block_signatures(
1125                &plain,
1126                &join_component_layer_schedules(&plain).expect("no mixed spatial Hadamard walls"),
1127                3
1128            )
1129            .expect("valid graph")[&IVec3::ZERO]
1130                .boundary_basis,
1131            Some(Basis::X) // ZXZ cube's y-face basis
1132        );
1133
1134        let mut hadamard = BlockGraph::new();
1135        hadamard.add_block(Block::new(IVec3::ZERO, BlockKind::T));
1136        hadamard.add_block(Block::new(
1137            IVec3::Z,
1138            BlockKind::Cube(bloq_graph::CubeKind::ZXZ),
1139        ));
1140        hadamard.add_pipe(Pipe::new(IVec3::ZERO, Direction::ZPLUS).with_hadamard());
1141        assert_eq!(
1142            block_signatures(
1143                &hadamard,
1144                &join_component_layer_schedules(&hadamard)
1145                    .expect("no mixed spatial Hadamard walls"),
1146                3
1147            )
1148            .expect("valid graph")[&IVec3::ZERO]
1149                .boundary_basis,
1150            Some(Basis::Z)
1151        );
1152    }
1153}
bloq_compile/signature.rs

bloq_compile/
signature.rs
