celox_slt/
node.rs

1use std::{fmt, hash::Hash};
2
3use num_bigint::{BigInt, BigUint};
4use serde::{Deserialize, Deserializer, Serialize, de::Error as _};
5
6use super::node_facts::{SLTNodeFactsError, verify_append, verify_raw_nodes};
7
8use crate::HashMap;
9use celox_design::{BinaryOp, BitAccess, UnaryOp, VarAtomBase};
10
11#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
12pub struct NodeId(pub usize);
13
14/// Failure from a narrowly scoped mutation of a construction arena.
15#[derive(Debug, Clone, PartialEq, Eq)]
16pub enum SLTNodeArenaEditError {
17    RangeOutOfBounds {
18        start: usize,
19        end: usize,
20        node_count: usize,
21    },
22    SiteIdOverflow {
23        site_id: u32,
24        offset: u32,
25    },
26    StorageUnavailable {
27        effect_count: usize,
28    },
29    EffectCountOverflow,
30    EditPlanMismatch,
31}
32
33impl fmt::Display for SLTNodeArenaEditError {
34    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
35        match self {
36            Self::RangeOutOfBounds {
37                start,
38                end,
39                node_count,
40            } => write!(
41                formatter,
42                "SLT edit range {start}..{end} is outside arena length {node_count}"
43            ),
44            Self::SiteIdOverflow { site_id, offset } => write!(
45                formatter,
46                "ForFold runtime-event site {site_id} plus offset {offset} overflows u32"
47            ),
48            Self::StorageUnavailable { effect_count } => write!(
49                formatter,
50                "cannot reserve {effect_count} ForFold runtime-event edits"
51            ),
52            Self::EffectCountOverflow => {
53                write!(
54                    formatter,
55                    "ForFold runtime-event effect count overflows usize"
56                )
57            }
58            Self::EditPlanMismatch => {
59                write!(
60                    formatter,
61                    "ForFold runtime-event edit plan no longer matches the arena"
62                )
63            }
64        }
65    }
66}
67
68impl std::error::Error for SLTNodeArenaEditError {}
69
70#[derive(Debug, Clone, Serialize)]
71#[serde(bound(serialize = "A: Serialize + std::hash::Hash + Eq + Clone"))]
72pub struct SLTNodeArena<A: Hash + Eq + Clone> {
73    nodes: Vec<SLTNode<A>>,
74    #[serde(skip)]
75    cache: crate::HashMap<SLTNode<A>, NodeId>,
76    /// Locally derived construction widths in stable [`NodeId`] order.
77    /// Full verification recomputes these independently from `nodes`.
78    #[serde(skip)]
79    widths: Vec<usize>,
80}
81
82#[derive(Serialize, Deserialize)]
83#[serde(bound(
84    serialize = "A: Serialize + std::hash::Hash + Eq + Clone",
85    deserialize = "A: Deserialize<'de> + std::hash::Hash + Eq + Clone"
86))]
87struct SLTNodeArenaWire<A: Hash + Eq + Clone> {
88    nodes: Vec<SLTNode<A>>,
89}
90
91impl<'de, A> Deserialize<'de> for SLTNodeArena<A>
92where
93    A: Deserialize<'de> + Hash + Eq + Clone,
94{
95    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
96    where
97        D: Deserializer<'de>,
98    {
99        let wire = SLTNodeArenaWire::<A>::deserialize(deserializer)?;
100        Self::from_raw_nodes(wire.nodes).map_err(D::Error::custom)
101    }
102}
103
104impl<A: PartialEq + Hash + Eq + Clone> PartialEq for SLTNodeArena<A> {
105    fn eq(&self, other: &Self) -> bool {
106        self.nodes == other.nodes
107    }
108}
109
110impl<A: Eq + Hash + Clone> Eq for SLTNodeArena<A> {}
111
112impl<A: Hash + Eq + Clone> SLTNodeArena<A> {
113    pub fn new() -> Self {
114        Self {
115            nodes: Vec::new(),
116            cache: crate::HashMap::default(),
117            widths: Vec::new(),
118        }
119    }
120
121    pub fn alloc(&mut self, node: SLTNode<A>) -> Result<NodeId, SLTNodeFactsError>
122    where
123        A: Hash + Eq + Clone,
124    {
125        if let Some(id) = self.cache.get(&node) {
126            return Ok(*id);
127        }
128        let width = verify_append(&node, &self.widths)?;
129        let id = NodeId(self.nodes.len());
130        self.cache.insert(node.clone(), id);
131        self.nodes.push(node);
132        self.widths.push(width);
133        debug_assert_eq!(self.nodes.len(), self.widths.len());
134        Ok(id)
135    }
136
137    /// Return a construction-time width computed once when `id` was interned.
138    pub(crate) fn width(&self, id: NodeId) -> Option<usize> {
139        self.widths.get(id.0).copied()
140    }
141
142    pub(super) fn nodes(&self) -> &[SLTNode<A>] {
143        &self.nodes
144    }
145
146    pub(super) fn cached_widths(&self) -> &[usize] {
147        &self.widths
148    }
149
150    /// Return the number of nodes in stable [`NodeId`] order.
151    pub fn len(&self) -> usize {
152        self.nodes.len()
153    }
154
155    /// Return whether the arena contains no nodes.
156    pub fn is_empty(&self) -> bool {
157        self.nodes.is_empty()
158    }
159
160    /// Iterate over nodes in stable [`NodeId`] order.
161    pub fn iter(&self) -> std::slice::Iter<'_, SLTNode<A>> {
162        self.nodes.iter()
163    }
164
165    /// Look up a node without trusting that an externally supplied ID exists.
166    pub fn get_checked(&self, id: NodeId) -> Option<&SLTNode<A>> {
167        self.nodes.get(id.0)
168    }
169
170    /// Rewrite only the runtime-event identity carried by `ForFold` effects.
171    ///
172    /// The semantic interning cache is rebuilt internally whenever the rewrite
173    /// changes a node, so callers cannot leave node storage and cache identity
174    /// out of sync. `None` leaves an effect unchanged.
175    pub fn remap_for_fold_effect_sites(
176        &mut self,
177        range: std::ops::Range<usize>,
178        mut remap: impl FnMut(
179            u32,
180            Option<i64>,
181        ) -> Result<Option<(u32, Option<i64>)>, SLTNodeArenaEditError>,
182    ) -> Result<(), SLTNodeArenaEditError> {
183        let node_count = self.nodes.len();
184        let start = range.start;
185        let end = range.end;
186        let Some(nodes) = self.nodes.get(range.clone()) else {
187            return Err(SLTNodeArenaEditError::RangeOutOfBounds {
188                start,
189                end,
190                node_count,
191            });
192        };
193        let effect_count = nodes.iter().try_fold(0usize, |count, node| {
194            let effects = match node {
195                SLTNode::ForFold { effects, .. } => effects.len(),
196                _ => 0,
197            };
198            count.checked_add(effects)
199        });
200        let Some(effect_count) = effect_count else {
201            return Err(SLTNodeArenaEditError::EffectCountOverflow);
202        };
203        let mut edits = Vec::new();
204        edits
205            .try_reserve_exact(effect_count)
206            .map_err(|_| SLTNodeArenaEditError::StorageUnavailable { effect_count })?;
207        for (node_index, node) in nodes.iter().enumerate() {
208            let SLTNode::ForFold { effects, .. } = node else {
209                continue;
210            };
211            for (effect_index, effect) in effects.iter().enumerate() {
212                let SLTForEffect::Event {
213                    site_id,
214                    fatal_error_code,
215                    ..
216                } = effect
217                else {
218                    continue;
219                };
220                let Some((mapped_site_id, mapped_fatal_error_code)) =
221                    remap(*site_id, *fatal_error_code)?
222                else {
223                    continue;
224                };
225                if *site_id != mapped_site_id || *fatal_error_code != mapped_fatal_error_code {
226                    edits.push((
227                        node_index,
228                        effect_index,
229                        mapped_site_id,
230                        mapped_fatal_error_code,
231                    ));
232                }
233            }
234        }
235        if edits.is_empty() {
236            return Ok(());
237        }
238        let Some(nodes) = self.nodes.get_mut(range) else {
239            return Err(SLTNodeArenaEditError::RangeOutOfBounds {
240                start,
241                end,
242                node_count,
243            });
244        };
245        if edits.iter().any(|&(node_index, effect_index, _, _)| {
246            !matches!(
247                nodes.get(node_index),
248                Some(SLTNode::ForFold { effects, .. }) if effect_index < effects.len()
249            )
250        }) {
251            return Err(SLTNodeArenaEditError::EditPlanMismatch);
252        }
253        for (node_index, effect_index, site_id, fatal_error_code) in edits {
254            if let Some(SLTNode::ForFold { effects, .. }) = nodes.get_mut(node_index)
255                && let Some(effect) = effects.get_mut(effect_index)
256            {
257                let SLTForEffect::Event {
258                    site_id: current_site_id,
259                    fatal_error_code: current_fatal_error_code,
260                    ..
261                } = effect
262                else {
263                    return Err(SLTNodeArenaEditError::EditPlanMismatch);
264                };
265                *current_site_id = site_id;
266                *current_fatal_error_code = fatal_error_code;
267            }
268        }
269        self.rebuild_cache();
270        Ok(())
271    }
272
273    /// Rebuild the derived interning cache from the persistent node list.
274    ///
275    /// If the list already contains duplicate nodes, the smallest (and therefore
276    /// first) [`NodeId`] is retained as the canonical identity.
277    fn rebuild_cache(&mut self) {
278        self.cache.clear();
279        for (idx, node) in self.nodes.iter().cloned().enumerate() {
280            self.cache.entry(node).or_insert(NodeId(idx));
281        }
282        debug_assert_eq!(self.nodes.len(), self.widths.len());
283    }
284
285    pub fn get(&self, id: NodeId) -> &SLTNode<A> {
286        &self.nodes[id.0]
287    }
288
289    pub fn display(&self, id: NodeId) -> NodeDisplay<'_, A> {
290        NodeDisplay { arena: self, id }
291    }
292
293    fn from_raw_nodes(nodes: Vec<SLTNode<A>>) -> Result<Self, SLTNodeFactsError> {
294        let widths = verify_raw_nodes(&nodes)?;
295        let mut arena = Self {
296            nodes,
297            cache: crate::HashMap::default(),
298            widths,
299        };
300        arena.rebuild_cache();
301        Ok(arena)
302    }
303
304    /// Verify raw node storage for tests without exposing it to production
305    /// construction paths.
306    #[cfg(test)]
307    pub(crate) fn try_from_nodes(nodes: Vec<SLTNode<A>>) -> Result<Self, SLTNodeFactsError> {
308        Self::from_raw_nodes(nodes)
309    }
310}
311
312pub struct NodeDisplay<'a, A: Hash + Eq + Clone> {
313    arena: &'a SLTNodeArena<A>,
314    id: NodeId,
315}
316
317impl<'a, A: Hash + Eq + Clone + std::fmt::Display> std::fmt::Display for NodeDisplay<'a, A> {
318    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
319        write!(f, "n{}: ", self.id.0)?;
320        self.arena.get(self.id).fmt_expression(f, self.arena)
321    }
322}
323
324impl<A: Hash + Eq + Clone> SLTNode<A> {
325    pub fn fmt_expression(
326        &self,
327        f: &mut std::fmt::Formatter<'_>,
328        arena: &SLTNodeArena<A>,
329    ) -> std::fmt::Result
330    where
331        A: std::fmt::Display,
332    {
333        match self {
334            SLTNode::Input {
335                variable,
336                index,
337                access,
338                ..
339            } => {
340                write!(f, "{}", variable)?;
341                for idx in index {
342                    write!(f, "n{}", idx.node.0)?;
343                    write!(f, "[(idx)")?;
344                    arena.get(idx.node).fmt_expression(f, arena)?;
345                    if idx.stride > 1 {
346                        write!(f, " * {}", idx.stride)?;
347                    }
348                    write!(f, "]")?;
349                }
350                if index.is_empty() {
351                    write!(f, "{}", access)?;
352                } else {
353                    // For array access, the 'access' field represents the bit-slice within the element.
354                    // If it targets a multi-dimensional array, indices are processed recursively.
355                    if access.lsb != 0 || access.msb != 0 {
356                        // This depends on how SLTNode::Input is used for arrays.
357                        // If it's a bit-slice of an array element, we show it.
358                        // write!(f, "{}", access)?;
359                    }
360                }
361                Ok(())
362            }
363            SLTNode::Constant(val, _mask, _width, _signed) => {
364                write!(f, "{}", val)
365            }
366            SLTNode::Binary(lhs, op, rhs) => {
367                write!(f, "(")?;
368                write!(f, "n{}:", lhs.0)?;
369                arena.get(*lhs).fmt_expression(f, arena)?;
370                let op_str = match op {
371                    celox_design::BinaryOp::Add => "+",
372                    celox_design::BinaryOp::Sub => "-",
373                    celox_design::BinaryOp::Mul => "*",
374                    celox_design::BinaryOp::DivU | celox_design::BinaryOp::DivS => "/",
375                    celox_design::BinaryOp::RemU | celox_design::BinaryOp::RemS => "%",
376                    celox_design::BinaryOp::And => "&",
377                    celox_design::BinaryOp::Or => "|",
378                    celox_design::BinaryOp::Xor => "^",
379                    celox_design::BinaryOp::Shl => "<<",
380                    celox_design::BinaryOp::Shr => ">>",
381                    celox_design::BinaryOp::Sar => ">>>",
382                    celox_design::BinaryOp::Eq => "==",
383                    celox_design::BinaryOp::Ne => "!=",
384                    celox_design::BinaryOp::EqCase => "===",
385                    celox_design::BinaryOp::NeCase => "!==",
386                    celox_design::BinaryOp::LtU | celox_design::BinaryOp::LtS => "<",
387                    celox_design::BinaryOp::LeU | celox_design::BinaryOp::LeS => "<=",
388                    celox_design::BinaryOp::GtU | celox_design::BinaryOp::GtS => ">",
389                    celox_design::BinaryOp::GeU | celox_design::BinaryOp::GeS => ">=",
390                    celox_design::BinaryOp::LogicAnd => "&&",
391                    celox_design::BinaryOp::LogicOr => "||",
392                    celox_design::BinaryOp::EqWildcard => "==?",
393                    celox_design::BinaryOp::NeWildcard => "!=?",
394                };
395                write!(f, " {} ", op_str)?;
396                write!(f, "n{}:", rhs.0)?;
397                arena.get(*rhs).fmt_expression(f, arena)?;
398                write!(f, ")")
399            }
400            SLTNode::Unary(op, inner) => {
401                let op_str = match op {
402                    celox_design::UnaryOp::Ident => "",
403                    celox_design::UnaryOp::ToTwoState => "2state",
404                    celox_design::UnaryOp::Minus => "-",
405                    celox_design::UnaryOp::BitNot => "~",
406                    celox_design::UnaryOp::LogicNot => "!",
407                    celox_design::UnaryOp::And => "&", // reduction
408                    celox_design::UnaryOp::Or => "|",
409                    celox_design::UnaryOp::Xor => "^",
410                    celox_design::UnaryOp::PopCount => "popcount",
411                    celox_design::UnaryOp::CountLeadingZeros => "clz",
412                    celox_design::UnaryOp::CountTrailingZeros => "ctz",
413                };
414                write!(f, "{}(", op_str)?;
415                write!(f, "n{}:", inner.0)?;
416                arena.get(*inner).fmt_expression(f, arena)?;
417                write!(f, ")")
418            }
419            SLTNode::Capture { expr, key } => {
420                write!(f, "capture[{key}](n{}:", expr.0)?;
421                arena.get(*expr).fmt_expression(f, arena)?;
422                write!(f, ")")
423            }
424            SLTNode::Mux {
425                cond,
426                then_expr,
427                else_expr,
428            } => {
429                write!(f, "(")?;
430                write!(f, "n{}:", cond.0)?;
431                arena.get(*cond).fmt_expression(f, arena)?;
432                write!(f, " ? ")?;
433                write!(f, "n{}:", then_expr.0)?;
434                arena.get(*then_expr).fmt_expression(f, arena)?;
435                write!(f, " : ")?;
436                write!(f, "n{}:", else_expr.0)?;
437                arena.get(*else_expr).fmt_expression(f, arena)?;
438                write!(f, ")")
439            }
440            SLTNode::ForFold {
441                loop_var,
442                start,
443                end,
444                inclusive,
445                step,
446                step_op,
447                reverse,
448                result,
449                initials,
450                updates,
451                ..
452            } => {
453                let fmt_bound =
454                    |f: &mut std::fmt::Formatter<'_>, bound: &SLTLoopBound| -> std::fmt::Result {
455                        match bound {
456                            SLTLoopBound::Const(v) => write!(f, "{v}"),
457                            SLTLoopBound::Expr(node) => {
458                                write!(f, "n{}:", node.0)?;
459                                arena.get(*node).fmt_expression(f, arena)
460                            }
461                        }
462                    };
463                write!(f, "for {loop_var} in ")?;
464                if *reverse {
465                    write!(f, "rev ")?;
466                }
467                fmt_bound(f, start)?;
468                if *inclusive {
469                    write!(f, "..=")?;
470                } else {
471                    write!(f, "..")?;
472                }
473                fmt_bound(f, end)?;
474                if *step != 1 || *step_op != SLTStepOp::Add {
475                    write!(f, " step ")?;
476                    match step_op {
477                        SLTStepOp::Add => write!(f, "+=")?,
478                        SLTStepOp::Mul => write!(f, "*=")?,
479                        SLTStepOp::BitOr => write!(f, "|=")?,
480                        SLTStepOp::BitXor => write!(f, "^=")?,
481                        SLTStepOp::Shl => write!(f, "<<=")?,
482                    }
483                    write!(f, " {step}")?;
484                }
485                write!(f, " => {result} init[")?;
486                for (i, init) in initials.iter().enumerate() {
487                    if i > 0 {
488                        write!(f, "; ")?;
489                    }
490                    write!(f, "{} = n{}:", init.target, init.expr.0)?;
491                    arena.get(init.expr).fmt_expression(f, arena)?;
492                }
493                write!(f, "] {{ ")?;
494                for (i, update) in updates.iter().enumerate() {
495                    if i > 0 {
496                        write!(f, "; ")?;
497                    }
498                    write!(f, "{} = n{}:", update.target, update.expr.0)?;
499                    arena.get(update.expr).fmt_expression(f, arena)?;
500                }
501                write!(f, " }}")
502            }
503            SLTNode::ForFoldGroup {
504                loop_var,
505                loop_width,
506                loop_signed,
507                start,
508                step,
509                trip_count,
510                entry_guard,
511                states,
512            } => {
513                write!(
514                    f,
515                    "fold_group {loop_var}:{loop_width}{} = {start} step {step} count {trip_count} if n{}:",
516                    if *loop_signed { "s" } else { "u" },
517                    entry_guard.0,
518                )?;
519                arena.get(*entry_guard).fmt_expression(f, arena)?;
520                write!(f, " [")?;
521                for (index, state) in states.iter().enumerate() {
522                    if index > 0 {
523                        write!(f, "; ")?;
524                    }
525                    write!(f, "{} = n{}:", state.target, state.initial.0,)?;
526                    arena.get(state.initial).fmt_expression(f, arena)?;
527                    write!(f, " -> n{}:", state.update.0)?;
528                    arena.get(state.update).fmt_expression(f, arena)?;
529                }
530                write!(f, "]")
531            }
532            SLTNode::Concat(parts) => {
533                write!(f, "{{")?;
534                for (i, (part, w)) in parts.iter().enumerate() {
535                    if i > 0 {
536                        write!(f, ", ")?;
537                    }
538                    write!(f, "n{}@{w}:", part.0)?;
539                    arena.get(*part).fmt_expression(f, arena)?;
540                }
541                write!(f, "}}")
542            }
543            SLTNode::Slice { expr, access } => {
544                write!(f, "n{}:", expr.0)?;
545                arena.get(*expr).fmt_expression(f, arena)?;
546                write!(f, "{}", access)
547            }
548        }
549    }
550}
551
552impl<A: Hash + Eq + Clone> Default for SLTNodeArena<A> {
553    fn default() -> Self {
554        Self::new()
555    }
556}
557
558#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
559pub enum SLTIndexKind {
560    /// An unpacked-array dimension.  `element_width` is the packed width of
561    /// one complete array element.
562    Unpacked { element_width: usize },
563    /// A packed dimension or bit/part select.
564    Packed,
565}
566
567#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
568pub struct SLTIndex {
569    pub node: NodeId,
570    pub stride: usize,
571    pub kind: SLTIndexKind,
572}
573
574#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
575pub enum SLTLoopBound {
576    Const(usize),
577    Expr(NodeId),
578}
579
580#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
581pub enum SLTStepOp {
582    Add,
583    Mul,
584    Shl,
585    BitOr,
586    BitXor,
587}
588
589#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
590#[serde(bound(
591    serialize = "A: Serialize + std::hash::Hash + Eq + Clone",
592    deserialize = "A: Deserialize<'de> + std::hash::Hash + Eq + Clone"
593))]
594pub struct SLTForUpdate<A: Hash + Eq + Clone> {
595    pub target: VarAtomBase<A>,
596    pub expr: NodeId,
597}
598
599/// Selects the value returned by a legacy dynamic loop fold.
600///
601/// Most folds return one of their variable-backed states. Control-flow
602/// lowering can instead carry a transient value which has no semantic HDL
603/// variable and therefore must not be represented by a fabricated bit range.
604#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
605#[serde(bound(
606    serialize = "A: Serialize + std::hash::Hash + Eq + Clone",
607    deserialize = "A: Deserialize<'de> + std::hash::Hash + Eq + Clone"
608))]
609pub enum SLTForFoldResult<A: Hash + Eq + Clone> {
610    State(VarAtomBase<A>),
611    Transient { initial: NodeId, update: NodeId },
612}
613
614impl<A: fmt::Display + Hash + Eq + Clone> fmt::Display for SLTForFoldResult<A> {
615    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
616        match self {
617            Self::State(state) => state.fmt(f),
618            Self::Transient { initial, update } => {
619                write!(f, "transient(n{} -> n{})", initial.0, update.0)
620            }
621        }
622    }
623}
624
625/// One loop-carried state in a grouped fixed-trip-count fold.
626///
627/// `initial` is evaluated before entering the loop and `update` is evaluated
628/// once per iteration with all state targets bound to the previous iteration's
629/// values.  A [`SLTNode::ForFoldGroup`] packs the final values in `states`
630/// order, with the first state occupying the most-significant bits.
631#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
632#[serde(bound(
633    serialize = "A: Serialize + std::hash::Hash + Eq + Clone",
634    deserialize = "A: Deserialize<'de> + std::hash::Hash + Eq + Clone"
635))]
636pub struct SLTForFoldGroupState<A: Hash + Eq + Clone> {
637    pub target: VarAtomBase<A>,
638    pub initial: NodeId,
639    pub update: NodeId,
640}
641
642#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
643pub enum SLTForEffect {
644    /// Emit one runtime event for the current loop iteration.
645    Event {
646        site_id: u32,
647        guard: Option<NodeId>,
648        emit_on_true: bool,
649        args: Vec<NodeId>,
650        fatal_error_code: Option<i64>,
651    },
652    /// Evaluate a nested loop runner at this position in the effect sequence.
653    Runner(NodeId),
654}
655
656#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
657#[serde(
658    into = "SLTNodeSerde<A>",
659    from = "SLTNodeSerde<A>",
660    bound(
661        serialize = "A: Serialize + Clone",
662        deserialize = "A: Deserialize<'de>"
663    )
664)]
665pub enum SLTNode<A: Hash + Eq + Clone> {
666    Input {
667        variable: A,
668        signed: bool,
669        index: Vec<SLTIndex>,
670        access: BitAccess,
671    },
672    Constant(BigUint, BigUint, usize, bool),
673    Binary(NodeId, BinaryOp, NodeId),
674    Unary(UnaryOp, NodeId),
675    Mux {
676        cond: NodeId,
677        then_expr: NodeId,
678        else_expr: NodeId,
679    },
680    ForFold {
681        loop_var: A,
682        loop_width: usize,
683        loop_signed: bool,
684        start: SLTLoopBound,
685        end: SLTLoopBound,
686        inclusive: bool,
687        step: usize,
688        step_op: SLTStepOp,
689        reverse: bool,
690        result: SLTForFoldResult<A>,
691        initials: Vec<SLTForUpdate<A>>,
692        updates: Vec<SLTForUpdate<A>>,
693        effects: Vec<SLTForEffect>,
694        continue_cond: NodeId,
695    },
696    /// A fixed-trip-count fold carrying multiple state values and returning
697    /// their final values as one packed result.
698    ForFoldGroup {
699        loop_var: A,
700        loop_width: usize,
701        loop_signed: bool,
702        start: BigInt,
703        step: BigInt,
704        trip_count: usize,
705        entry_guard: NodeId,
706        states: Vec<SLTForFoldGroupState<A>>,
707    },
708    // Concat/Slice are primarily used for RHS expression evaluation.
709    // On the LHS (assignments), bit manipulation is handled implicitly by RangeStore atomization.
710    Concat(Vec<(NodeId, usize)>),
711    Slice {
712        expr: NodeId,
713        access: BitAccess,
714    },
715    /// A value materialized at a specific semantic evaluation position.
716    ///
717    /// `key` keeps captures from distinct runtime-event operands separate even
718    /// when their expressions are structurally identical.
719    Capture {
720        expr: NodeId,
721        key: u64,
722    },
723}
724
725/// Serde-friendly mirror of [`SLTNode`] that replaces [`BigUint`] with `Vec<u8>` (little-endian).
726#[derive(Serialize, Deserialize)]
727#[serde(bound(serialize = "A: Serialize", deserialize = "A: Deserialize<'de>"))]
728enum SLTNodeSerde<A: Hash + Eq + Clone> {
729    Input {
730        variable: A,
731        signed: bool,
732        index: Vec<SLTIndex>,
733        access: BitAccess,
734    },
735    Constant {
736        payload: Vec<u8>,
737        mask: Vec<u8>,
738        width: usize,
739        signed: bool,
740    },
741    Binary(NodeId, BinaryOp, NodeId),
742    Unary(UnaryOp, NodeId),
743    Mux {
744        cond: NodeId,
745        then_expr: NodeId,
746        else_expr: NodeId,
747    },
748    ForFold {
749        loop_var: A,
750        loop_width: usize,
751        loop_signed: bool,
752        start: SLTLoopBound,
753        end: SLTLoopBound,
754        inclusive: bool,
755        step: usize,
756        step_op: SLTStepOp,
757        reverse: bool,
758        result: SLTForFoldResult<A>,
759        initials: Vec<SLTForUpdate<A>>,
760        updates: Vec<SLTForUpdate<A>>,
761        effects: Vec<SLTForEffect>,
762        continue_cond: NodeId,
763    },
764    ForFoldGroup {
765        loop_var: A,
766        loop_width: usize,
767        loop_signed: bool,
768        /// Signed two's-complement, little-endian representation.
769        start: Vec<u8>,
770        /// Signed two's-complement, little-endian representation.
771        step: Vec<u8>,
772        trip_count: usize,
773        entry_guard: NodeId,
774        states: Vec<SLTForFoldGroupState<A>>,
775    },
776    Concat(Vec<(NodeId, usize)>),
777    Slice {
778        expr: NodeId,
779        access: BitAccess,
780    },
781    Capture {
782        expr: NodeId,
783        key: u64,
784    },
785}
786
787impl<A: Hash + Eq + Clone> From<SLTNode<A>> for SLTNodeSerde<A> {
788    fn from(node: SLTNode<A>) -> Self {
789        match node {
790            SLTNode::Input {
791                variable,
792                signed,
793                index,
794                access,
795            } => SLTNodeSerde::Input {
796                variable,
797                signed,
798                index,
799                access,
800            },
801            SLTNode::Constant(payload, mask, width, signed) => SLTNodeSerde::Constant {
802                payload: payload.to_bytes_le(),
803                mask: mask.to_bytes_le(),
804                width,
805                signed,
806            },
807            SLTNode::Binary(a, op, b) => SLTNodeSerde::Binary(a, op, b),
808            SLTNode::Unary(op, a) => SLTNodeSerde::Unary(op, a),
809            SLTNode::Capture { expr, key } => SLTNodeSerde::Capture { expr, key },
810            SLTNode::Mux {
811                cond,
812                then_expr,
813                else_expr,
814            } => SLTNodeSerde::Mux {
815                cond,
816                then_expr,
817                else_expr,
818            },
819            SLTNode::ForFold {
820                loop_var,
821                loop_width,
822                loop_signed,
823                start,
824                end,
825                inclusive,
826                step,
827                step_op,
828                reverse,
829                result,
830                initials,
831                updates,
832                effects,
833                continue_cond,
834            } => SLTNodeSerde::ForFold {
835                loop_var,
836                loop_width,
837                loop_signed,
838                start,
839                end,
840                inclusive,
841                step,
842                step_op,
843                reverse,
844                result,
845                initials,
846                updates,
847                effects,
848                continue_cond,
849            },
850            SLTNode::ForFoldGroup {
851                loop_var,
852                loop_width,
853                loop_signed,
854                start,
855                step,
856                trip_count,
857                entry_guard,
858                states,
859            } => SLTNodeSerde::ForFoldGroup {
860                loop_var,
861                loop_width,
862                loop_signed,
863                start: start.to_signed_bytes_le(),
864                step: step.to_signed_bytes_le(),
865                trip_count,
866                entry_guard,
867                states,
868            },
869            SLTNode::Concat(parts) => SLTNodeSerde::Concat(parts),
870            SLTNode::Slice { expr, access } => SLTNodeSerde::Slice { expr, access },
871        }
872    }
873}
874
875impl<A: Hash + Eq + Clone> From<SLTNodeSerde<A>> for SLTNode<A> {
876    fn from(node: SLTNodeSerde<A>) -> Self {
877        match node {
878            SLTNodeSerde::Input {
879                variable,
880                signed,
881                index,
882                access,
883            } => SLTNode::Input {
884                variable,
885                signed,
886                index,
887                access,
888            },
889            SLTNodeSerde::Constant {
890                payload,
891                mask,
892                width,
893                signed,
894            } => SLTNode::Constant(
895                BigUint::from_bytes_le(&payload),
896                BigUint::from_bytes_le(&mask),
897                width,
898                signed,
899            ),
900            SLTNodeSerde::Binary(a, op, b) => SLTNode::Binary(a, op, b),
901            SLTNodeSerde::Unary(op, a) => SLTNode::Unary(op, a),
902            SLTNodeSerde::Capture { expr, key } => SLTNode::Capture { expr, key },
903            SLTNodeSerde::Mux {
904                cond,
905                then_expr,
906                else_expr,
907            } => SLTNode::Mux {
908                cond,
909                then_expr,
910                else_expr,
911            },
912            SLTNodeSerde::ForFold {
913                loop_var,
914                loop_width,
915                loop_signed,
916                start,
917                end,
918                inclusive,
919                step,
920                step_op,
921                reverse,
922                result,
923                initials,
924                updates,
925                effects,
926                continue_cond,
927            } => SLTNode::ForFold {
928                loop_var,
929                loop_width,
930                loop_signed,
931                start,
932                end,
933                inclusive,
934                step,
935                step_op,
936                reverse,
937                result,
938                initials,
939                updates,
940                effects,
941                continue_cond,
942            },
943            SLTNodeSerde::ForFoldGroup {
944                loop_var,
945                loop_width,
946                loop_signed,
947                start,
948                step,
949                trip_count,
950                entry_guard,
951                states,
952            } => SLTNode::ForFoldGroup {
953                loop_var,
954                loop_width,
955                loop_signed,
956                start: BigInt::from_signed_bytes_le(&start),
957                step: BigInt::from_signed_bytes_le(&step),
958                trip_count,
959                entry_guard,
960                states,
961            },
962            SLTNodeSerde::Concat(parts) => SLTNode::Concat(parts),
963            SLTNodeSerde::Slice { expr, access } => SLTNode::Slice { expr, access },
964        }
965    }
966}
967impl<A: fmt::Debug + fmt::Display + Hash + Eq + Clone> SLTNode<A> {
968    /// Maps the address type A to B throughout the reachable graph.
969    ///
970    /// The traversal is explicitly postorder so deeply nested expressions do
971    /// not consume the host thread's call stack.
972    pub fn map_addr<B, F>(
973        &self,
974        id: NodeId,
975        arena: &SLTNodeArena<A>,
976        target_arena: &mut SLTNodeArena<B>,
977        cache: &mut HashMap<NodeId, NodeId>,
978        f: &F,
979    ) -> Result<NodeId, SLTNodeFactsError>
980    where
981        A: Hash + Eq + Clone,
982        B: Hash + Eq + Clone,
983        F: Fn(&A) -> B,
984    {
985        if let Some(mapped_id) = cache.get(&id) {
986            return Ok(*mapped_id);
987        }
988
989        let mut work = vec![(id, false)];
990        while let Some((current, expanded)) = work.pop() {
991            if cache.contains_key(&current) {
992                continue;
993            }
994
995            let node = arena.get(current);
996            if !expanded {
997                work.push((current, true));
998                let mut children = Vec::new();
999                match node {
1000                    SLTNode::Input { index, .. } => {
1001                        children.extend(index.iter().map(|index| index.node));
1002                    }
1003                    SLTNode::Constant(..) => {}
1004                    SLTNode::Binary(lhs, _, rhs) => children.extend([*lhs, *rhs]),
1005                    SLTNode::Unary(_, inner) => children.push(*inner),
1006                    SLTNode::Capture { expr, .. } => children.push(*expr),
1007                    SLTNode::Mux {
1008                        cond,
1009                        then_expr,
1010                        else_expr,
1011                    } => children.extend([*cond, *then_expr, *else_expr]),
1012                    SLTNode::ForFold {
1013                        start,
1014                        end,
1015                        result,
1016                        initials,
1017                        updates,
1018                        effects,
1019                        continue_cond,
1020                        ..
1021                    } => {
1022                        // Keep the same child order as the former recursive
1023                        // implementation so mapped NodeIds remain stable.
1024                        children.extend(initials.iter().map(|update| update.expr));
1025                        children.extend(updates.iter().map(|update| update.expr));
1026                        for effect in effects {
1027                            match effect {
1028                                SLTForEffect::Event { guard, args, .. } => {
1029                                    children.extend(*guard);
1030                                    children.extend(args.iter().copied());
1031                                }
1032                                SLTForEffect::Runner(runner) => children.push(*runner),
1033                            }
1034                        }
1035                        if let SLTForFoldResult::Transient { initial, update } = result {
1036                            children.extend([*initial, *update]);
1037                        }
1038                        if let SLTLoopBound::Expr(node) = start {
1039                            children.push(*node);
1040                        }
1041                        if let SLTLoopBound::Expr(node) = end {
1042                            children.push(*node);
1043                        }
1044                        children.push(*continue_cond);
1045                    }
1046                    SLTNode::ForFoldGroup {
1047                        entry_guard,
1048                        states,
1049                        ..
1050                    } => {
1051                        for state in states {
1052                            children.extend([state.initial, state.update]);
1053                        }
1054                        children.push(*entry_guard);
1055                    }
1056                    SLTNode::Concat(parts) => {
1057                        children.extend(parts.iter().map(|(node, _)| *node));
1058                    }
1059                    SLTNode::Slice { expr, .. } => children.push(*expr),
1060                }
1061                work.extend(children.into_iter().rev().map(|child| (child, false)));
1062                continue;
1063            }
1064
1065            let mapped = |child: NodeId| {
1066                *cache
1067                    .get(&child)
1068                    .expect("postorder address mapping must visit children before parents")
1069            };
1070            let new_node = match node {
1071                // Leaf: Transform address A to B
1072                SLTNode::Input {
1073                    variable: addr,
1074                    signed,
1075                    index,
1076                    access,
1077                } => {
1078                    let mapped_index = index
1079                        .iter()
1080                        .map(|idx| SLTIndex {
1081                            node: mapped(idx.node),
1082                            stride: idx.stride,
1083                            kind: idx.kind,
1084                        })
1085                        .collect();
1086                    SLTNode::Input {
1087                        variable: f(addr),
1088                        signed: *signed,
1089                        index: mapped_index,
1090                        access: *access,
1091                    }
1092                }
1093
1094                // Leaf: Constants remain unchanged
1095                SLTNode::Constant(val, mask, width, signed) => {
1096                    SLTNode::Constant(val.clone(), mask.clone(), *width, *signed)
1097                }
1098
1099                // Recursive cases
1100                SLTNode::Binary(lhs, op, rhs) => SLTNode::Binary(mapped(*lhs), *op, mapped(*rhs)),
1101
1102                SLTNode::Unary(op, inner) => SLTNode::Unary(*op, mapped(*inner)),
1103                SLTNode::Capture { expr, key } => SLTNode::Capture {
1104                    expr: mapped(*expr),
1105                    key: *key,
1106                },
1107
1108                SLTNode::Mux {
1109                    cond,
1110                    then_expr,
1111                    else_expr,
1112                } => SLTNode::Mux {
1113                    cond: mapped(*cond),
1114                    then_expr: mapped(*then_expr),
1115                    else_expr: mapped(*else_expr),
1116                },
1117
1118                SLTNode::ForFold {
1119                    loop_var,
1120                    loop_width,
1121                    loop_signed,
1122                    start,
1123                    end,
1124                    inclusive,
1125                    step,
1126                    step_op,
1127                    reverse,
1128                    result,
1129                    initials,
1130                    updates,
1131                    effects,
1132                    continue_cond,
1133                } => {
1134                    let map_bound = |bound: &SLTLoopBound| -> SLTLoopBound {
1135                        match bound {
1136                            SLTLoopBound::Const(v) => SLTLoopBound::Const(*v),
1137                            SLTLoopBound::Expr(node) => SLTLoopBound::Expr(mapped(*node)),
1138                        }
1139                    };
1140                    let mapped_initials = initials
1141                        .iter()
1142                        .map(|update| SLTForUpdate {
1143                            target: VarAtomBase::new(
1144                                f(&update.target.id),
1145                                update.target.access.lsb,
1146                                update.target.access.msb,
1147                            ),
1148                            expr: mapped(update.expr),
1149                        })
1150                        .collect();
1151                    let mapped_updates = updates
1152                        .iter()
1153                        .map(|update| SLTForUpdate {
1154                            target: VarAtomBase::new(
1155                                f(&update.target.id),
1156                                update.target.access.lsb,
1157                                update.target.access.msb,
1158                            ),
1159                            expr: mapped(update.expr),
1160                        })
1161                        .collect();
1162                    let mapped_effects = effects
1163                        .iter()
1164                        .map(|effect| match effect {
1165                            SLTForEffect::Event {
1166                                site_id,
1167                                guard,
1168                                emit_on_true,
1169                                args,
1170                                fatal_error_code,
1171                            } => SLTForEffect::Event {
1172                                site_id: *site_id,
1173                                guard: guard.map(mapped),
1174                                emit_on_true: *emit_on_true,
1175                                args: args.iter().map(|arg| mapped(*arg)).collect(),
1176                                fatal_error_code: *fatal_error_code,
1177                            },
1178                            SLTForEffect::Runner(runner) => SLTForEffect::Runner(mapped(*runner)),
1179                        })
1180                        .collect();
1181                    let mapped_result = match result {
1182                        SLTForFoldResult::State(result) => SLTForFoldResult::State(
1183                            VarAtomBase::new(f(&result.id), result.access.lsb, result.access.msb),
1184                        ),
1185                        SLTForFoldResult::Transient { initial, update } => {
1186                            SLTForFoldResult::Transient {
1187                                initial: mapped(*initial),
1188                                update: mapped(*update),
1189                            }
1190                        }
1191                    };
1192                    SLTNode::ForFold {
1193                        loop_var: f(loop_var),
1194                        loop_width: *loop_width,
1195                        loop_signed: *loop_signed,
1196                        start: map_bound(start),
1197                        end: map_bound(end),
1198                        inclusive: *inclusive,
1199                        step: *step,
1200                        step_op: *step_op,
1201                        reverse: *reverse,
1202                        result: mapped_result,
1203                        initials: mapped_initials,
1204                        updates: mapped_updates,
1205                        effects: mapped_effects,
1206                        continue_cond: mapped(*continue_cond),
1207                    }
1208                }
1209
1210                SLTNode::ForFoldGroup {
1211                    loop_var,
1212                    loop_width,
1213                    loop_signed,
1214                    start,
1215                    step,
1216                    trip_count,
1217                    entry_guard,
1218                    states,
1219                } => {
1220                    let mapped_states = states
1221                        .iter()
1222                        .map(|state| SLTForFoldGroupState {
1223                            target: VarAtomBase::new(
1224                                f(&state.target.id),
1225                                state.target.access.lsb,
1226                                state.target.access.msb,
1227                            ),
1228                            initial: mapped(state.initial),
1229                            update: mapped(state.update),
1230                        })
1231                        .collect();
1232                    SLTNode::ForFoldGroup {
1233                        loop_var: f(loop_var),
1234                        loop_width: *loop_width,
1235                        loop_signed: *loop_signed,
1236                        start: start.clone(),
1237                        step: step.clone(),
1238                        trip_count: *trip_count,
1239                        entry_guard: mapped(*entry_guard),
1240                        states: mapped_states,
1241                    }
1242                }
1243
1244                SLTNode::Concat(parts) => {
1245                    let mapped_parts = parts
1246                        .iter()
1247                        .map(|(node, width)| (mapped(*node), *width))
1248                        .collect();
1249                    SLTNode::Concat(mapped_parts)
1250                }
1251
1252                SLTNode::Slice { expr, access } => SLTNode::Slice {
1253                    expr: mapped(*expr),
1254                    access: *access,
1255                },
1256            };
1257            let new_id = target_arena.alloc(new_node)?;
1258            cache.insert(current, new_id);
1259        }
1260
1261        Ok(*cache
1262            .get(&id)
1263            .expect("root must be mapped after postorder traversal"))
1264    }
1265}
1266
1267/// Display implementation for SLTNode - provides human-readable tree structure
1268///
1269/// This implementation formats the Signal Logic Tree (SLT) as a hierarchical ASCII tree,
1270/// making it easy to visualize the expression structure. Each node type displays relevant
1271/// information:
1272///
1273/// - **Input**: Shows variable ID, dynamic indices (if any), and bit range `[lsb:msb]`
1274/// - **Constant**: Displays the value in hexadecimal and width in bits
1275/// - **Binary**: Shows the operation and recursively formats both operands with indentation
1276/// - **Unary**: Shows the operation and recursively formats the inner expression
1277/// - **Mux**: Displays condition, then-branch, and else-branch with clear labels
1278/// - **Concat**: Lists concatenated parts with their widths
1279/// - **Slice**: Shows the bit range extraction with the inner expression
1280///
1281/// # Example
1282///
1283/// A binary expression `a + b` would display as:
1284/// ```text
1285/// Binary(Add)
1286///   Const(0x1, 32bits)
1287///   Const(0x2, 32bits)
1288/// ```
1289///
1290/// A more complex expression `(a + b) * (c - d)` would show:
1291/// ```text
1292/// Binary(Mul)
1293///   Binary(Add)
1294///     Const(0x1, 32bits)
1295///     Const(0x2, 32bits)
1296///   Binary(Sub)
1297///     Const(0x3, 32bits)
1298///     Const(0x4, 32bits)
1299/// ```
1300impl<A: fmt::Debug + fmt::Display + Hash + Eq + Clone> SLTNode<A> {
1301    pub fn fmt_display(&self, f: &mut fmt::Formatter<'_>, arena: &SLTNodeArena<A>) -> fmt::Result {
1302        self.fmt_recursive(f, 0, arena)
1303    }
1304}
1305
1306impl<A: fmt::Debug + fmt::Display + Hash + Eq + Clone> SLTNode<A> {
1307    fn fmt_recursive(
1308        &self,
1309        f: &mut fmt::Formatter<'_>,
1310        depth: usize,
1311        arena: &SLTNodeArena<A>,
1312    ) -> fmt::Result {
1313        let indent = "  ".repeat(depth);
1314        let child_indent = "  ".repeat(depth + 1);
1315        match self {
1316            SLTNode::Input {
1317                variable,
1318                index,
1319                access,
1320                ..
1321            } => {
1322                write!(f, "{}Input({:?}", indent, variable)?;
1323                if !index.is_empty() {
1324                    write!(f, "[")?;
1325                    for (i, idx) in index.iter().enumerate() {
1326                        if i > 0 {
1327                            write!(f, ", ")?;
1328                        }
1329                        write!(f, "n{}:...", idx.node.0)?;
1330                        if idx.stride > 1 {
1331                            write!(f, "*{}", idx.stride)?;
1332                        }
1333                    }
1334                    write!(f, "]")?;
1335                }
1336                write!(f, "[{}:{}]", access.lsb, access.msb)?;
1337                write!(f, ")")
1338            }
1339            SLTNode::Constant(val, _mask, width, _signed) => {
1340                write!(f, "{}Const({:#x}, {}bits)", indent, val, width)
1341            }
1342            SLTNode::Binary(lhs, op, rhs) => {
1343                let op_str = format!("{:?}", op); // Just use Debug for simplicity
1344                writeln!(f, "{}Binary({})", indent, op_str)?;
1345                arena.get(*lhs).fmt_recursive(f, depth + 1, arena)?;
1346                writeln!(f)?; // Insert empty line between left and right expressions
1347                arena.get(*rhs).fmt_recursive(f, depth + 1, arena)
1348            }
1349            SLTNode::Unary(op, inner) => {
1350                writeln!(f, "{}Unary({:?})", indent, op)?;
1351                arena.get(*inner).fmt_recursive(f, depth + 1, arena)
1352            }
1353            SLTNode::Capture { expr, key } => {
1354                writeln!(f, "{}Capture({key})", indent)?;
1355                arena.get(*expr).fmt_recursive(f, depth + 1, arena)
1356            }
1357            SLTNode::Mux {
1358                cond,
1359                then_expr,
1360                else_expr,
1361            } => {
1362                writeln!(f, "{}Mux", indent)?;
1363                writeln!(f, "{}cond:", child_indent)?;
1364                arena.get(*cond).fmt_recursive(f, depth + 2, arena)?;
1365                writeln!(f, "\n{}then:", child_indent)?;
1366                arena.get(*then_expr).fmt_recursive(f, depth + 2, arena)?;
1367                writeln!(f, "\n{}else:", child_indent)?;
1368                arena.get(*else_expr).fmt_recursive(f, depth + 2, arena)
1369            }
1370            SLTNode::ForFold {
1371                loop_var,
1372                loop_width,
1373                loop_signed,
1374                start,
1375                end,
1376                inclusive,
1377                step,
1378                step_op,
1379                reverse,
1380                result,
1381                initials,
1382                updates,
1383                effects,
1384                continue_cond,
1385            } => {
1386                writeln!(
1387                    f,
1388                    "{}ForFold(loop_var={}, width={}, signed={}, inclusive={}, step={}, step_op={:?}, reverse={}, result={})",
1389                    indent,
1390                    loop_var,
1391                    loop_width,
1392                    loop_signed,
1393                    inclusive,
1394                    step,
1395                    step_op,
1396                    reverse,
1397                    result
1398                )?;
1399                writeln!(f, "{}start: {:?}", child_indent, start)?;
1400                writeln!(f, "{}end: {:?}", child_indent, end)?;
1401                for init in initials {
1402                    writeln!(f, "{}init {}:", child_indent, init.target)?;
1403                    arena.get(init.expr).fmt_recursive(f, depth + 2, arena)?;
1404                    writeln!(f)?;
1405                }
1406                for update in updates {
1407                    writeln!(f, "{}update {}:", child_indent, update.target)?;
1408                    arena.get(update.expr).fmt_recursive(f, depth + 2, arena)?;
1409                    writeln!(f)?;
1410                }
1411                for effect in effects {
1412                    match effect {
1413                        SLTForEffect::Event {
1414                            site_id,
1415                            guard,
1416                            args,
1417                            ..
1418                        } => {
1419                            writeln!(f, "{}effect site={}:", child_indent, site_id)?;
1420                            if let Some(guard) = guard {
1421                                writeln!(f, "{}guard:", child_indent)?;
1422                                arena.get(*guard).fmt_recursive(f, depth + 2, arena)?;
1423                                writeln!(f)?;
1424                            }
1425                            for arg in args {
1426                                writeln!(f, "{}arg:", child_indent)?;
1427                                arena.get(*arg).fmt_recursive(f, depth + 2, arena)?;
1428                                writeln!(f)?;
1429                            }
1430                        }
1431                        SLTForEffect::Runner(runner) => {
1432                            writeln!(f, "{}effect runner:", child_indent)?;
1433                            arena.get(*runner).fmt_recursive(f, depth + 2, arena)?;
1434                        }
1435                    }
1436                }
1437                writeln!(f, "{}continue:", child_indent)?;
1438                arena
1439                    .get(*continue_cond)
1440                    .fmt_recursive(f, depth + 2, arena)?;
1441                Ok(())
1442            }
1443            SLTNode::ForFoldGroup {
1444                loop_var,
1445                loop_width,
1446                loop_signed,
1447                start,
1448                step,
1449                trip_count,
1450                entry_guard,
1451                states,
1452            } => {
1453                writeln!(
1454                    f,
1455                    "{}ForFoldGroup(loop_var={}, width={}, signed={}, start={}, step={}, trip_count={})",
1456                    indent, loop_var, loop_width, loop_signed, start, step, trip_count,
1457                )?;
1458                writeln!(f, "{}entry guard:", child_indent)?;
1459                arena.get(*entry_guard).fmt_recursive(f, depth + 2, arena)?;
1460                writeln!(f)?;
1461                for state in states {
1462                    writeln!(f, "{}state {} initial:", child_indent, state.target)?;
1463                    arena
1464                        .get(state.initial)
1465                        .fmt_recursive(f, depth + 2, arena)?;
1466                    writeln!(f)?;
1467                    writeln!(f, "{}state {} update:", child_indent, state.target)?;
1468                    arena.get(state.update).fmt_recursive(f, depth + 2, arena)?;
1469                    writeln!(f)?;
1470                }
1471                Ok(())
1472            }
1473            SLTNode::Concat(parts) => {
1474                writeln!(f, "{}Concat", indent)?;
1475                for (i, (part, width)) in parts.iter().enumerate() {
1476                    if i > 0 {
1477                        writeln!(f)?;
1478                    }
1479                    writeln!(f, "{}[{}bits]:", child_indent, width)?;
1480                    arena.get(*part).fmt_recursive(f, depth + 2, arena)?;
1481                }
1482                Ok(())
1483            }
1484            SLTNode::Slice { expr, access } => {
1485                writeln!(f, "{}Slice[{}:{}]", indent, access.lsb, access.msb)?;
1486                arena.get(*expr).fmt_recursive(f, depth + 1, arena)
1487            }
1488        }
1489    }
1490}
1491
1492#[cfg(test)]
1493mod tests {
1494    use super::{
1495        NodeId, SLTForEffect, SLTForFoldGroupState, SLTForFoldResult, SLTIndex, SLTLoopBound,
1496        SLTNode, SLTNodeArena, SLTNodeArenaEditError, SLTNodeArenaWire, SLTStepOp,
1497    };
1498    use crate::{SLTNodeFacts, get_width};
1499    use celox_design::{BinaryOp, BitAccess, UnaryOp, VarAtomBase};
1500    use num_bigint::{BigInt, BigUint};
1501
1502    fn constant(value: u8) -> SLTNode<u32> {
1503        SLTNode::Constant(BigUint::from(value), BigUint::from(0u8), 8, false)
1504    }
1505
1506    #[test]
1507    fn rebuild_cache_uses_first_duplicate_node_id() {
1508        let duplicate = constant(7);
1509        let mut arena =
1510            SLTNodeArena::try_from_nodes(vec![constant(1), duplicate.clone(), duplicate.clone()])
1511                .unwrap();
1512        arena.cache.insert(duplicate.clone(), NodeId(2));
1513
1514        arena.rebuild_cache();
1515
1516        assert_eq!(arena.cache.get(&duplicate), Some(&NodeId(1)));
1517        let node_count = arena.len();
1518        assert_eq!(arena.alloc(duplicate).unwrap(), NodeId(1));
1519        assert_eq!(arena.len(), node_count);
1520    }
1521
1522    #[test]
1523    fn json_roundtrip_rebuilds_cache_with_minimum_node_id() {
1524        let duplicate = constant(9);
1525        let arena =
1526            SLTNodeArena::try_from_nodes(vec![constant(2), duplicate.clone(), duplicate.clone()])
1527                .unwrap();
1528
1529        let json = serde_json::to_string(&arena).unwrap();
1530        let mut decoded: SLTNodeArena<u32> = serde_json::from_str(&json).unwrap();
1531        let node_count = decoded.len();
1532
1533        assert_eq!(decoded.alloc(duplicate).unwrap(), NodeId(1));
1534        assert_eq!(decoded.len(), node_count);
1535        assert_eq!(decoded.width(NodeId(1)), Some(8));
1536        assert_eq!(decoded.widths.len(), decoded.nodes.len());
1537    }
1538
1539    fn arena_with_for_fold_group() -> (SLTNodeArena<u32>, NodeId) {
1540        let mut arena = SLTNodeArena::new();
1541        let entry_guard = arena
1542            .alloc(SLTNode::Constant(
1543                BigUint::from(1u8),
1544                BigUint::from(0u8),
1545                1,
1546                false,
1547            ))
1548            .unwrap();
1549        let initial_wide = arena.alloc(constant(3)).unwrap();
1550        let update_wide = arena.alloc(constant(4)).unwrap();
1551        let initial_narrow = arena
1552            .alloc(SLTNode::Constant(
1553                BigUint::from(1u8),
1554                BigUint::from(0u8),
1555                4,
1556                false,
1557            ))
1558            .unwrap();
1559        let update_narrow = arena
1560            .alloc(SLTNode::Constant(
1561                BigUint::from(2u8),
1562                BigUint::from(0u8),
1563                4,
1564                false,
1565            ))
1566            .unwrap();
1567        let group = arena
1568            .alloc(SLTNode::ForFoldGroup {
1569                loop_var: 7,
1570                loop_width: 8,
1571                loop_signed: true,
1572                start: BigInt::from(-4),
1573                step: BigInt::from(2),
1574                trip_count: 3,
1575                entry_guard,
1576                states: vec![
1577                    SLTForFoldGroupState {
1578                        target: VarAtomBase::new(8, 0, 7),
1579                        initial: initial_wide,
1580                        update: update_wide,
1581                    },
1582                    SLTForFoldGroupState {
1583                        target: VarAtomBase::new(9, 4, 7),
1584                        initial: initial_narrow,
1585                        update: update_narrow,
1586                    },
1587                ],
1588            })
1589            .unwrap();
1590        (arena, group)
1591    }
1592
1593    #[test]
1594    fn for_fold_group_json_roundtrip_preserves_signed_iteration_and_width() {
1595        let (arena, group) = arena_with_for_fold_group();
1596        let facts = SLTNodeFacts::verify(&arena).expect("valid ForFoldGroup must verify");
1597        assert_eq!(facts.width(group), Some(12));
1598
1599        let json = serde_json::to_string(&arena).unwrap();
1600        let decoded: SLTNodeArena<u32> = serde_json::from_str(&json).unwrap();
1601
1602        assert_eq!(decoded, arena);
1603        assert_eq!(decoded.width(group), Some(12));
1604        assert_eq!(
1605            SLTNodeFacts::verify(&decoded).unwrap().width(group),
1606            Some(12)
1607        );
1608    }
1609
1610    #[test]
1611    fn for_fold_group_map_addr_maps_loop_and_state_targets_and_children() {
1612        let (arena, group) = arena_with_for_fold_group();
1613        let mut mapped_arena = SLTNodeArena::<u64>::new();
1614        let mut cache = crate::HashMap::default();
1615
1616        let mapped_group = arena
1617            .get(group)
1618            .map_addr(group, &arena, &mut mapped_arena, &mut cache, &|address| {
1619                u64::from(*address) + 100
1620            })
1621            .unwrap();
1622
1623        let SLTNode::ForFoldGroup {
1624            loop_var,
1625            start,
1626            step,
1627            entry_guard,
1628            states,
1629            ..
1630        } = mapped_arena.get(mapped_group)
1631        else {
1632            panic!("mapped node must remain ForFoldGroup");
1633        };
1634        assert_eq!(*loop_var, 107);
1635        assert_eq!(*start, BigInt::from(-4));
1636        assert_eq!(*step, BigInt::from(2));
1637        assert_eq!(states[0].target, VarAtomBase::new(108, 0, 7));
1638        assert_eq!(states[1].target, VarAtomBase::new(109, 4, 7));
1639        assert!(entry_guard.0 < mapped_group.0);
1640        assert!(
1641            states.iter().all(|state| {
1642                state.initial.0 < mapped_group.0 && state.update.0 < mapped_group.0
1643            })
1644        );
1645        assert_eq!(
1646            SLTNodeFacts::verify(&mapped_arena)
1647                .unwrap()
1648                .width(mapped_group),
1649            Some(12)
1650        );
1651    }
1652
1653    #[test]
1654    fn map_addr_handles_deep_expression_without_using_the_call_stack() {
1655        const DEPTH: usize = 10_000;
1656
1657        let mut arena = SLTNodeArena::<u32>::new();
1658        let mut root = arena
1659            .alloc(SLTNode::Input {
1660                variable: 42,
1661                signed: false,
1662                index: Vec::new(),
1663                access: BitAccess::new(0, 0),
1664            })
1665            .unwrap();
1666        for _ in 0..DEPTH {
1667            root = arena.alloc(SLTNode::Unary(UnaryOp::Ident, root)).unwrap();
1668        }
1669
1670        let mut mapped_arena = SLTNodeArena::<u64>::new();
1671        let mut cache = crate::HashMap::default();
1672        let mut mapped = arena
1673            .get(root)
1674            .map_addr(root, &arena, &mut mapped_arena, &mut cache, &|address| {
1675                u64::from(*address) + 1
1676            })
1677            .unwrap();
1678
1679        assert_eq!(cache.len(), DEPTH + 1);
1680        for _ in 0..DEPTH {
1681            let SLTNode::Unary(UnaryOp::Ident, inner) = mapped_arena.get(mapped) else {
1682                panic!("mapped expression must preserve every unary node");
1683            };
1684            mapped = *inner;
1685        }
1686        let SLTNode::Input { variable, .. } = mapped_arena.get(mapped) else {
1687            panic!("mapped expression must end in its input");
1688        };
1689        assert_eq!(*variable, 43);
1690    }
1691
1692    #[test]
1693    fn default_allocation_and_clone_preserve_width_cache() {
1694        let mut arena = SLTNodeArena::<u32>::default();
1695        assert!(arena.is_empty());
1696        assert!(arena.widths.is_empty());
1697
1698        let narrow = arena
1699            .alloc(SLTNode::Constant(
1700                BigUint::from(3u8),
1701                BigUint::from(0u8),
1702                2,
1703                false,
1704            ))
1705            .unwrap();
1706        let wide = arena.alloc(constant(7)).unwrap();
1707        let sum = arena
1708            .alloc(SLTNode::Binary(narrow, BinaryOp::Add, wide))
1709            .unwrap();
1710        assert_eq!(get_width(sum, &arena), 8);
1711        assert_eq!(arena.widths.len(), arena.nodes.len());
1712
1713        let facts = SLTNodeFacts::verify(&arena).expect("allocated arena must verify");
1714        for index in 0..arena.len() {
1715            let id = NodeId(index);
1716            assert_eq!(arena.width(id), facts.width(id));
1717        }
1718
1719        let mut cloned = arena.clone();
1720        assert_eq!(cloned.widths, arena.widths);
1721        assert_eq!(get_width(sum, &cloned), 8);
1722        let node_count = cloned.len();
1723        assert_eq!(cloned.alloc(arena.get(sum).clone()).unwrap(), sum);
1724        assert_eq!(cloned.len(), node_count);
1725    }
1726
1727    #[test]
1728    fn get_width_does_not_rewalk_a_shared_mux_dag() {
1729        const DEPTH: usize = 64;
1730
1731        let mut arena = SLTNodeArena::<u32>::new();
1732        let cond = arena
1733            .alloc(SLTNode::Constant(
1734                BigUint::from(1u8),
1735                BigUint::from(0u8),
1736                1,
1737                false,
1738            ))
1739            .unwrap();
1740        let mut value = arena.alloc(constant(0)).unwrap();
1741        for _ in 0..DEPTH {
1742            let then_expr = arena.alloc(SLTNode::Unary(UnaryOp::Ident, value)).unwrap();
1743            let else_expr = arena.alloc(SLTNode::Unary(UnaryOp::BitNot, value)).unwrap();
1744            value = arena
1745                .alloc(SLTNode::Mux {
1746                    cond,
1747                    then_expr,
1748                    else_expr,
1749                })
1750                .unwrap();
1751        }
1752
1753        // Recursively walking both arms revisits the shared predecessor twice
1754        // per level. A construction-time fact lookup is independent of that
1755        // exponential number of graph paths.
1756        assert_eq!(get_width(value, &arena), 8);
1757        assert_eq!(arena.width(value), Some(8));
1758        assert_eq!(arena.widths.len(), arena.nodes.len());
1759    }
1760
1761    #[test]
1762    fn failed_append_does_not_mutate_arena_or_caches() {
1763        let mut arena = SLTNodeArena::<u32>::new();
1764        let valid = arena.alloc(constant(1)).unwrap();
1765        let nodes_before = arena.nodes.clone();
1766        let widths_before = arena.widths.clone();
1767        let cache_before = arena.cache.clone();
1768
1769        let error = arena
1770            .alloc(SLTNode::Binary(valid, BinaryOp::Add, NodeId(99)))
1771            .unwrap_err();
1772
1773        assert_eq!(error.invariant, "GRAPH.CHILD_EXISTS");
1774        assert_eq!(arena.nodes, nodes_before);
1775        assert_eq!(arena.widths, widths_before);
1776        assert_eq!(arena.cache, cache_before);
1777
1778        let error = arena
1779            .alloc(SLTNode::Concat(vec![(valid, usize::MAX), (valid, 1)]))
1780            .unwrap_err();
1781        assert_eq!(error.invariant, "WIDTH.CONCAT_REPRESENTABLE");
1782        assert_eq!(arena.nodes, nodes_before);
1783        assert_eq!(arena.widths, widths_before);
1784        assert_eq!(arena.cache, cache_before);
1785    }
1786
1787    #[test]
1788    fn append_derives_width_but_defers_semantic_rules_to_full_verifier() {
1789        let mut arena = SLTNodeArena::<u32>::new();
1790        let oversized = arena
1791            .alloc(SLTNode::Constant(
1792                BigUint::from(0x10u8),
1793                BigUint::from(0u8),
1794                4,
1795                false,
1796            ))
1797            .expect("declared width is locally derivable");
1798
1799        assert_eq!(arena.width(oversized), Some(4));
1800        assert_eq!(
1801            SLTNodeFacts::verify(&arena).unwrap_err().invariant,
1802            "CONSTANT.VALUE_FITS_WIDTH"
1803        );
1804    }
1805
1806    #[test]
1807    fn full_verifier_rejects_a_divergent_construction_width_cache() {
1808        let mut arena = SLTNodeArena::<u32>::new();
1809        arena.alloc(constant(1)).unwrap();
1810        arena.widths[0] = 7;
1811
1812        assert_eq!(
1813            SLTNodeFacts::verify(&arena).unwrap_err().invariant,
1814            "FACTS.CACHED_WIDTH_MATCHES"
1815        );
1816    }
1817
1818    #[test]
1819    fn json_deserialization_rejects_noncanonical_graphs() {
1820        let wire = SLTNodeArenaWire {
1821            nodes: vec![
1822                SLTNode::Binary(NodeId(1), BinaryOp::Add, NodeId(1)),
1823                constant(1),
1824            ],
1825        };
1826        let json = serde_json::to_string(&wire).unwrap();
1827
1828        let error = serde_json::from_str::<SLTNodeArena<u32>>(&json).unwrap_err();
1829
1830        assert!(error.to_string().contains("GRAPH.CHILD_PRECEDES_OWNER"));
1831    }
1832
1833    #[test]
1834    fn json_deserialization_checks_children_not_used_to_derive_width() {
1835        let cases = [
1836            vec![
1837                constant(1),
1838                SLTNode::Mux {
1839                    cond: NodeId(99),
1840                    then_expr: NodeId(0),
1841                    else_expr: NodeId(0),
1842                },
1843            ],
1844            vec![SLTNode::Input {
1845                variable: 1,
1846                signed: false,
1847                index: vec![SLTIndex {
1848                    node: NodeId(99),
1849                    stride: 1,
1850                    kind: super::SLTIndexKind::Packed,
1851                }],
1852                access: BitAccess::new(0, 0),
1853            }],
1854        ];
1855
1856        for nodes in cases {
1857            let json = serde_json::to_string(&SLTNodeArenaWire { nodes }).unwrap();
1858            let error = serde_json::from_str::<SLTNodeArena<u32>>(&json).unwrap_err();
1859            assert!(error.to_string().contains("GRAPH.CHILD_EXISTS"));
1860        }
1861    }
1862
1863    #[test]
1864    fn for_fold_effect_remap_updates_only_the_requested_range() {
1865        let mut arena = SLTNodeArena::new();
1866        let condition = arena.alloc(constant(1)).unwrap();
1867        let first_fold = arena
1868            .alloc(SLTNode::ForFold {
1869                loop_var: 1,
1870                loop_width: 8,
1871                loop_signed: false,
1872                start: SLTLoopBound::Const(0),
1873                end: SLTLoopBound::Const(1),
1874                inclusive: false,
1875                step: 1,
1876                step_op: SLTStepOp::Add,
1877                reverse: false,
1878                result: SLTForFoldResult::State(VarAtomBase::new(2, 0, 7)),
1879                initials: Vec::new(),
1880                updates: Vec::new(),
1881                effects: vec![SLTForEffect::Event {
1882                    site_id: 3,
1883                    guard: None,
1884                    emit_on_true: true,
1885                    args: Vec::new(),
1886                    fatal_error_code: Some(3),
1887                }],
1888                continue_cond: condition,
1889            })
1890            .unwrap();
1891        let second_fold = arena
1892            .alloc(SLTNode::ForFold {
1893                loop_var: 1,
1894                loop_width: 8,
1895                loop_signed: false,
1896                start: SLTLoopBound::Const(0),
1897                end: SLTLoopBound::Const(1),
1898                inclusive: false,
1899                step: 1,
1900                step_op: SLTStepOp::Add,
1901                reverse: false,
1902                result: SLTForFoldResult::State(VarAtomBase::new(2, 0, 7)),
1903                initials: Vec::new(),
1904                updates: Vec::new(),
1905                effects: vec![SLTForEffect::Event {
1906                    site_id: 4,
1907                    guard: None,
1908                    emit_on_true: true,
1909                    args: Vec::new(),
1910                    fatal_error_code: None,
1911                }],
1912                continue_cond: condition,
1913            })
1914            .unwrap();
1915
1916        arena
1917            .remap_for_fold_effect_sites(first_fold.0..second_fold.0, |site, fatal| {
1918                Ok(Some((site + 10, fatal.map(|_| 99))))
1919            })
1920            .expect("valid remap range must succeed");
1921
1922        let SLTNode::ForFold { effects, .. } = arena.get(first_fold) else {
1923            panic!("expected first ForFold");
1924        };
1925        let SLTForEffect::Event {
1926            site_id,
1927            fatal_error_code,
1928            ..
1929        } = effects[0]
1930        else {
1931            panic!("expected event effect");
1932        };
1933        assert_eq!(site_id, 13);
1934        assert_eq!(fatal_error_code, Some(99));
1935        let remapped_first = arena.get(first_fold).clone();
1936        assert_eq!(arena.alloc(remapped_first).unwrap(), first_fold);
1937        let SLTNode::ForFold { effects, .. } = arena.get(second_fold) else {
1938            panic!("expected second ForFold");
1939        };
1940        let SLTForEffect::Event {
1941            site_id,
1942            fatal_error_code,
1943            ..
1944        } = effects[0]
1945        else {
1946            panic!("expected event effect");
1947        };
1948        assert_eq!(site_id, 4);
1949        assert_eq!(fatal_error_code, None);
1950
1951        let error = arena
1952            .remap_for_fold_effect_sites(first_fold.0..second_fold.0 + 1, |site, fatal| {
1953                if site == 4 {
1954                    Err(SLTNodeArenaEditError::SiteIdOverflow {
1955                        site_id: site,
1956                        offset: u32::MAX,
1957                    })
1958                } else {
1959                    Ok(Some((site + 1, fatal)))
1960                }
1961            })
1962            .expect_err("failed remap must be reported");
1963        assert!(matches!(
1964            error,
1965            SLTNodeArenaEditError::SiteIdOverflow { .. }
1966        ));
1967        let SLTNode::ForFold { effects, .. } = arena.get(first_fold) else {
1968            panic!("expected first ForFold");
1969        };
1970        let SLTForEffect::Event { site_id, .. } = effects[0] else {
1971            panic!("expected event effect");
1972        };
1973        assert_eq!(site_id, 13, "failed remap must be atomic");
1974
1975        let error = arena
1976            .remap_for_fold_effect_sites(0..arena.len() + 1, |site, fatal| Ok(Some((site, fatal))))
1977            .expect_err("out-of-range remap must fail");
1978        assert!(matches!(
1979            error,
1980            SLTNodeArenaEditError::RangeOutOfBounds { .. }
1981        ));
1982    }
1983}
celox_slt/node.rs

celox_slt/
node.rs
