plotnik_lib/ir/
transition.rs

1//! Transition struct - the fundamental unit of the query IR.
2//!
3//! Each transition is 64 bytes and cache-line aligned to ensure no transition
4//! straddles cache lines. Transitions carry all semantics: matching, effects,
5//! and successors. States are implicit junction points.
6
7use super::{EffectOp, Matcher, Nav, RefTransition, Slice, TransitionId};
8
9/// Maximum number of inline successors before spilling to external segment.
10pub const MAX_INLINE_SUCCESSORS: usize = 8;
11
12/// A single transition in the query graph.
13///
14/// Transitions use SSO (small-size optimization) for successors:
15/// - 0-8 successors: stored inline in `successor_data`
16/// - 9+ successors: `successor_data[0]` is index into successors segment
17///
18/// Layout (64 bytes total, 64-byte aligned):
19/// ```text
20/// offset 0:  matcher (16 bytes)
21/// offset 16: ref_marker (4 bytes)
22/// offset 20: nav (2 bytes)
23/// offset 22: effects_len (2 bytes)
24/// offset 24: successor_count (4 bytes)
25/// offset 28: effects_start (4 bytes)
26/// offset 32: successor_data (32 bytes)
27/// ```
28#[repr(C, align(64))]
29#[derive(Clone, Copy)]
30pub struct Transition {
31    // --- 32 bytes metadata ---
32    /// What this transition matches (node kind, wildcard, epsilon).
33    pub matcher: Matcher, // 16 bytes, offset 0
34
35    /// Reference call/return marker for recursive definitions.
36    pub ref_marker: RefTransition, // 4 bytes, offset 16
37
38    /// Navigation instruction (descend/ascend/sibling traversal).
39    pub nav: Nav, // 2 bytes, offset 20
40
41    /// Number of effect operations (inlined from Slice for alignment).
42    effects_len: u16, // 2 bytes, offset 22
43
44    /// Number of successor transitions.
45    pub successor_count: u32, // 4 bytes, offset 24
46
47    /// Start index into effects segment (inlined from Slice for alignment).
48    effects_start: u32, // 4 bytes, offset 28
49
50    // --- 32 bytes control flow ---
51    /// Successor storage (inline or spilled index).
52    ///
53    /// - If `successor_count <= 8`: contains `TransitionId` values directly
54    /// - If `successor_count > 8`: `successor_data[0]` is index into successors segment
55    pub successor_data: [u32; MAX_INLINE_SUCCESSORS], // 32 bytes, offset 32
56}
57
58impl Transition {
59    /// Creates a new transition with all fields.
60    #[inline]
61    pub fn new(
62        matcher: Matcher,
63        ref_marker: RefTransition,
64        nav: Nav,
65        effects: Slice<EffectOp>,
66        successor_count: u32,
67        successor_data: [u32; MAX_INLINE_SUCCESSORS],
68    ) -> Self {
69        Self {
70            matcher,
71            ref_marker,
72            nav,
73            effects_len: effects.len(),
74            successor_count,
75            effects_start: effects.start_index(),
76            successor_data,
77        }
78    }
79
80    /// Returns the effects slice.
81    #[inline]
82    pub fn effects(&self) -> Slice<EffectOp> {
83        Slice::new(self.effects_start, self.effects_len)
84    }
85
86    /// Sets the effects slice.
87    #[inline]
88    pub fn set_effects(&mut self, effects: Slice<EffectOp>) {
89        self.effects_start = effects.start_index();
90        self.effects_len = effects.len();
91    }
92
93    /// Returns `true` if successors are stored inline.
94    #[inline]
95    pub fn has_inline_successors(&self) -> bool {
96        self.successor_count as usize <= MAX_INLINE_SUCCESSORS
97    }
98
99    /// Returns inline successors if they fit, `None` if spilled.
100    #[inline]
101    pub fn inline_successors(&self) -> Option<&[TransitionId]> {
102        if self.has_inline_successors() {
103            Some(&self.successor_data[..self.successor_count as usize])
104        } else {
105            None
106        }
107    }
108
109    /// Returns the spilled successor segment index and count.
110    /// Panics if successors are inline.
111    #[inline]
112    pub fn spilled_successors_index(&self) -> u32 {
113        debug_assert!(
114            !self.has_inline_successors(),
115            "successors are inline, not spilled"
116        );
117        self.successor_data[0]
118    }
119}
120
121// Compile-time size/alignment verification
122const _: () = {
123    assert!(core::mem::size_of::<Transition>() == 64);
124    assert!(core::mem::align_of::<Transition>() == 64);
125};
plotnik_lib/ir/transition.rs

plotnik_lib/ir/
transition.rs
