perl_parser_core/hir/
body.rs

1//! HIR body graph: arena-based expression/statement/block representation.
2//!
3//! This module provides the first vertical slice of HIR body infrastructure,
4//! implementing the arena-based graph described in ADR #2564. It introduces:
5//!
6//! - Typed arena indices: [`HirBodyId`], [`HirExprId`], [`HirStmtId`], [`HirBlockId`]
7//! - Per-body arenas and a source map: [`HirBody`], [`BodySourceMap`]
8//! - Body owners (program root + subroutine): [`BodyOwnerKind`]
9//! - Expression/statement/block node taxonomy: [`HirExpr`], [`HirStmt`], [`HirBlock`]
10//! - A lowering entry point for one Perl source string: [`lower_body`]
11//!
12//! # Specimen
13//!
14//! The first vertical slice lowers exactly one specimen end-to-end:
15//!
16//! ```text
17//! my $x = $a + $b;
18//! ```
19//!
20//! This produces a [`HirBody`] with:
21//! - One [`HirStmt::Let`] binding `$x`
22//! - One [`HirExpr::Binary`] `+` node with children reading `$a` and `$b`
23//! - One [`HirExpr::Assign`] connecting the decl place to the binary value
24//! - All nodes carry exact byte-offset source ranges in [`BodySourceMap`]
25
26use crate::SourceLocation;
27
28// ──────────────────────────────────────────────────────────────────────────────
29// Typed arena indices
30// ──────────────────────────────────────────────────────────────────────────────
31
32/// Stable index into the workspace body registry (one per body owner).
33///
34/// Currently unused at runtime — reserved so that cross-body references can be
35/// introduced later without changing existing index types.
36#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
37pub struct HirBodyId(pub u32);
38
39/// Typed index into a [`HirBody`]'s expression arena.
40#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
41pub struct HirExprId(pub u32);
42
43/// Typed index into a [`HirBody`]'s statement arena.
44#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
45pub struct HirStmtId(pub u32);
46
47/// Typed index into a [`HirBody`]'s block arena.
48#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
49pub struct HirBlockId(pub u32);
50
51// ──────────────────────────────────────────────────────────────────────────────
52// Arena
53// ──────────────────────────────────────────────────────────────────────────────
54
55/// Typed append-only arena indexed by a strongly-typed ID.
56///
57/// The ID type must implement a constructor from `u32`; see the `impl` blocks
58/// below for each concrete instantiation.
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct Arena<T> {
61    items: Vec<T>,
62}
63
64impl<T> Default for Arena<T> {
65    fn default() -> Self {
66        Self { items: Vec::new() }
67    }
68}
69
70impl<T> Arena<T> {
71    /// Push a value and return its index.
72    pub fn alloc(&mut self, value: T) -> u32 {
73        let id = self.items.len() as u32;
74        self.items.push(value);
75        id
76    }
77
78    /// Return a reference to the value at `index`.
79    ///
80    /// Returns `None` if the index is out of bounds.
81    pub fn get(&self, index: u32) -> Option<&T> {
82        self.items.get(index as usize)
83    }
84
85    /// Return the number of allocated items.
86    pub fn len(&self) -> usize {
87        self.items.len()
88    }
89
90    /// Return true when no items have been allocated.
91    pub fn is_empty(&self) -> bool {
92        self.items.is_empty()
93    }
94
95    /// Iterate over all allocated items in allocation order.
96    pub fn iter(&self) -> impl Iterator<Item = &T> {
97        self.items.iter()
98    }
99}
100
101// ──────────────────────────────────────────────────────────────────────────────
102// Source map
103// ──────────────────────────────────────────────────────────────────────────────
104
105/// Source map for one [`HirBody`].
106///
107/// Each arena entry in [`HirBody`] has a corresponding `SourceLocation` here,
108/// indexed by the same raw `u32` that the typed ID wraps.
109#[derive(Debug, Clone, PartialEq, Eq, Default)]
110pub struct BodySourceMap {
111    /// Source range for each expression, indexed by [`HirExprId`] value.
112    pub expr_ranges: Vec<SourceLocation>,
113    /// Source range for each statement, indexed by [`HirStmtId`] value.
114    pub stmt_ranges: Vec<SourceLocation>,
115    /// Source range for each block, indexed by [`HirBlockId`] value.
116    pub block_ranges: Vec<SourceLocation>,
117}
118
119impl BodySourceMap {
120    /// Look up the source range for an expression.
121    pub fn expr_range(&self, id: HirExprId) -> Option<SourceLocation> {
122        self.expr_ranges.get(id.0 as usize).copied()
123    }
124
125    /// Look up the source range for a statement.
126    pub fn stmt_range(&self, id: HirStmtId) -> Option<SourceLocation> {
127        self.stmt_ranges.get(id.0 as usize).copied()
128    }
129
130    /// Look up the source range for a block.
131    pub fn block_range(&self, id: HirBlockId) -> Option<SourceLocation> {
132        self.block_ranges.get(id.0 as usize).copied()
133    }
134}
135
136// ──────────────────────────────────────────────────────────────────────────────
137// Body owner
138// ──────────────────────────────────────────────────────────────────────────────
139
140/// What syntactic construct owns this body.
141#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
142pub enum BodyOwnerKind {
143    /// Top-level program root (file-level statement sequence).
144    ProgramRoot,
145    /// Named subroutine body (`sub foo { ... }`).
146    Subroutine {
147        /// Subroutine name, or `None` for anonymous subs.
148        name: Option<String>,
149    },
150    /// Method body (`method foo { ... }`).
151    Method {
152        /// Method name.
153        name: String,
154    },
155}
156
157/// Stable key for a body in the per-file body registry.
158///
159/// The ordinal disambiguates multiple anonymous subroutines or method bodies
160/// with the same name in one file.
161#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
162pub struct BodyOwner {
163    /// What owns this body.
164    pub kind: BodyOwnerKind,
165    /// Zero-based ordinal for disambiguation within one file.
166    pub ordinal: u32,
167}
168
169impl BodyOwner {
170    /// Create a `BodyOwner` key.
171    pub fn new(kind: BodyOwnerKind, ordinal: u32) -> Self {
172        Self { kind, ordinal }
173    }
174}
175
176// ──────────────────────────────────────────────────────────────────────────────
177// Expression nodes
178// ──────────────────────────────────────────────────────────────────────────────
179
180/// Sigil for a variable reference.
181#[derive(Debug, Clone, PartialEq, Eq)]
182pub enum Sigil {
183    /// `$` — scalar.
184    Scalar,
185    /// `@` — array.
186    Array,
187    /// `%` — hash.
188    Hash,
189    /// `&` — code ref / sub.
190    Code,
191    /// `*` — typeglob.
192    Glob,
193}
194
195impl Sigil {
196    /// Parse from a sigil character string as produced by the AST.
197    fn from_str(s: &str) -> Self {
198        match s {
199            "$" => Sigil::Scalar,
200            "@" => Sigil::Array,
201            "%" => Sigil::Hash,
202            "&" => Sigil::Code,
203            "*" => Sigil::Glob,
204            _ => Sigil::Scalar, // graceful fallback; should not occur
205        }
206    }
207}
208
209/// How a variable is accessed.
210#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
211pub enum AccessMode {
212    /// Value is being read.
213    Read,
214    /// Variable is the target of an assignment (lexical place / lvalue).
215    Write,
216    /// Variable is both read and written — compound assignment or `++`/`--`.
217    ReadModifyWrite,
218}
219
220/// Variable origin classification.
221#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
222pub enum VariableKind {
223    /// `my`-declared lexical in scope.
224    Lexical,
225    /// Package / stash variable.
226    Package,
227}
228
229/// A variable reference node.
230#[derive(Debug, Clone, PartialEq, Eq)]
231pub struct HirVariable {
232    /// Variable sigil.
233    pub sigil: Sigil,
234    /// Variable name without sigil.
235    pub name: String,
236    /// Lexical or package origin.
237    pub kind: VariableKind,
238    /// How this node uses the variable.
239    pub access: AccessMode,
240}
241
242/// How an assignment is performed.
243#[derive(Debug, Clone, PartialEq, Eq)]
244pub enum AssignMode {
245    /// Simple `=` assignment.
246    Simple,
247    /// Compound assignment: `+=`, `-=`, `*=`, etc.
248    ///
249    /// The LHS is both read (to compute the new value) and written (to store
250    /// the result).  The LHS variable node carries [`AccessMode::ReadModifyWrite`].
251    ReadModifyWrite,
252}
253
254/// How a unary operator accesses its operand.
255#[derive(Debug, Clone, PartialEq, Eq)]
256pub enum UnaryMode {
257    /// Pure read (e.g. unary minus, `!`).
258    Read,
259    /// Read-modify-write (e.g. `++`, `--`).
260    ReadModifyWrite,
261}
262
263/// Binary operator.
264#[derive(Debug, Clone, PartialEq, Eq)]
265pub enum BinaryOp {
266    /// Numeric addition `+`.
267    Add,
268    /// Numeric subtraction `-`.
269    Sub,
270    /// Numeric multiplication `*`.
271    Mul,
272    /// Numeric division `/`.
273    Div,
274    /// String concatenation `.`.
275    Concat,
276    /// Other/unknown operator — preserves the original text.
277    Other(String),
278}
279
280impl BinaryOp {
281    fn from_str(s: &str) -> Self {
282        match s {
283            "+" => BinaryOp::Add,
284            "-" => BinaryOp::Sub,
285            "*" => BinaryOp::Mul,
286            "/" => BinaryOp::Div,
287            "." => BinaryOp::Concat,
288            other => BinaryOp::Other(other.to_string()),
289        }
290    }
291}
292
293/// One expression node in the HIR body graph.
294///
295/// Every variant that has child expressions carries explicit [`HirExprId`]
296/// references — there are no flat shells.
297#[derive(Debug, Clone, PartialEq, Eq)]
298pub enum HirExpr {
299    /// Variable read or write-place reference.
300    Variable(HirVariable),
301
302    /// Binary expression: `lhs OP rhs`, both children are explicit IDs.
303    Binary {
304        /// Left-hand operand.
305        lhs: HirExprId,
306        /// Operator.
307        op: BinaryOp,
308        /// Right-hand operand.
309        rhs: HirExprId,
310    },
311
312    /// Assignment expression: `lhs = rhs`, both sides are explicit IDs.
313    ///
314    /// For `my $x = …`, the `lhs` is a `Variable` node with `access: Write`
315    /// representing the declared place, and `rhs` is the initializer.
316    Assign {
317        /// Assignment target (place / lvalue).
318        lhs: HirExprId,
319        /// Value being assigned.
320        rhs: HirExprId,
321        /// Assignment mode.
322        mode: AssignMode,
323    },
324
325    /// Unary expression: `OP operand`.
326    Unary {
327        /// Operand.
328        operand: HirExprId,
329        /// How the operator accesses the operand.
330        mode: UnaryMode,
331        /// Operator text, for diagnostics.
332        op: String,
333    },
334
335    /// Function/method call expression (first-pass model).
336    ///
337    /// Arguments that are individually lowerable carry explicit IDs; everything
338    /// else is `Opaque`.
339    Call {
340        /// Argument expressions in source order.
341        args: Vec<HirExprId>,
342        /// The AST node kind name, for diagnostics.
343        ast_kind: String,
344    },
345
346    /// Opaque expression — used when the AST shape is not yet modeled.
347    Opaque {
348        /// The AST node kind name for diagnostics.
349        ast_kind: String,
350    },
351}
352
353// ──────────────────────────────────────────────────────────────────────────────
354// Statement nodes
355// ──────────────────────────────────────────────────────────────────────────────
356
357/// Storage class for a variable declaration.
358#[derive(Debug, Clone, PartialEq, Eq)]
359pub enum DeclStorageClass {
360    /// `my` — lexical.
361    My,
362    /// `our` — package alias.
363    Our,
364    /// `local` — dynamic.
365    Local,
366    /// `state` — persistent lexical.
367    State,
368}
369
370impl DeclStorageClass {
371    fn from_str(s: &str) -> Self {
372        match s {
373            "my" => DeclStorageClass::My,
374            "our" => DeclStorageClass::Our,
375            "local" => DeclStorageClass::Local,
376            "state" => DeclStorageClass::State,
377            _ => DeclStorageClass::My,
378        }
379    }
380}
381
382/// One statement node in the HIR body graph.
383#[derive(Debug, Clone, PartialEq, Eq)]
384pub enum HirStmt {
385    /// Expression statement: evaluate the expression for its side effects.
386    Expr(HirExprId),
387
388    /// Variable declaration: `my $x = …`
389    ///
390    /// The `init` expression, when present, is the full initializer (which may
391    /// itself be an [`HirExpr::Assign`] that links the declared place to its
392    /// value).
393    Let {
394        /// Variable name without sigil.
395        name: String,
396        /// Sigil of the declared variable.
397        sigil: Sigil,
398        /// Storage class: `my`, `our`, `local`, `state`.
399        storage: DeclStorageClass,
400        /// Optional initializer expression ID.
401        init: Option<HirExprId>,
402    },
403}
404
405// ──────────────────────────────────────────────────────────────────────────────
406// Block node
407// ──────────────────────────────────────────────────────────────────────────────
408
409/// A sequenced list of statements — the building block of every body.
410#[derive(Debug, Clone, PartialEq, Eq, Default)]
411pub struct HirBlock {
412    /// Ordered statement IDs in source order.
413    pub stmts: Vec<HirStmtId>,
414}
415
416// ──────────────────────────────────────────────────────────────────────────────
417// HirBody
418// ──────────────────────────────────────────────────────────────────────────────
419
420/// Arena-based expression/statement/block graph for one body owner.
421///
422/// This is the unit of lowering produced by [`lower_body`]. It is separate
423/// from [`crate::hir::HirFile`]'s flat item list — flat items remain for
424/// compile-time fact extraction; bodies are the new representation for data-flow
425/// analysis, context propagation, and PIR-A lowering.
426#[derive(Debug, Clone, PartialEq, Eq)]
427pub struct HirBody {
428    /// All expression nodes, indexed by [`HirExprId`].
429    pub exprs: Arena<HirExpr>,
430    /// All statement nodes, indexed by [`HirStmtId`].
431    pub stmts: Arena<HirStmt>,
432    /// All block nodes (ordered statement sequences), indexed by [`HirBlockId`].
433    pub blocks: Arena<HirBlock>,
434    /// Source map: maps each expr/stmt/block index to its [`SourceLocation`].
435    pub source_map: BodySourceMap,
436    /// Root block — the entry point for the body.
437    pub root_block: HirBlockId,
438    /// What syntactic construct owns this body.
439    pub owner: BodyOwnerKind,
440}
441
442impl HirBody {
443    /// Look up an expression node by ID.
444    pub fn expr(&self, id: HirExprId) -> Option<&HirExpr> {
445        self.exprs.get(id.0)
446    }
447
448    /// Look up a statement node by ID.
449    pub fn stmt(&self, id: HirStmtId) -> Option<&HirStmt> {
450        self.stmts.get(id.0)
451    }
452
453    /// Look up a block node by ID.
454    pub fn block(&self, id: HirBlockId) -> Option<&HirBlock> {
455        self.blocks.get(id.0)
456    }
457}
458
459// ──────────────────────────────────────────────────────────────────────────────
460// Body builder (internal)
461// ──────────────────────────────────────────────────────────────────────────────
462
463struct BodyBuilder {
464    exprs: Arena<HirExpr>,
465    stmts: Arena<HirStmt>,
466    blocks: Arena<HirBlock>,
467    source_map: BodySourceMap,
468}
469
470impl BodyBuilder {
471    fn new() -> Self {
472        Self {
473            exprs: Arena::default(),
474            stmts: Arena::default(),
475            blocks: Arena::default(),
476            source_map: BodySourceMap::default(),
477        }
478    }
479
480    fn alloc_expr(&mut self, expr: HirExpr, range: SourceLocation) -> HirExprId {
481        let idx = self.exprs.alloc(expr);
482        self.source_map.expr_ranges.push(range);
483        HirExprId(idx)
484    }
485
486    fn alloc_stmt(&mut self, stmt: HirStmt, range: SourceLocation) -> HirStmtId {
487        let idx = self.stmts.alloc(stmt);
488        self.source_map.stmt_ranges.push(range);
489        HirStmtId(idx)
490    }
491
492    fn alloc_block(&mut self, block: HirBlock, range: SourceLocation) -> HirBlockId {
493        let idx = self.blocks.alloc(block);
494        self.source_map.block_ranges.push(range);
495        HirBlockId(idx)
496    }
497
498    fn finish(self, root_block: HirBlockId, owner: BodyOwnerKind) -> HirBody {
499        HirBody {
500            exprs: self.exprs,
501            stmts: self.stmts,
502            blocks: self.blocks,
503            source_map: self.source_map,
504            root_block,
505            owner,
506        }
507    }
508}
509
510// ──────────────────────────────────────────────────────────────────────────────
511// Lowering
512// ──────────────────────────────────────────────────────────────────────────────
513
514use crate::{Node, NodeKind};
515
516/// Lower the top-level program-root body from a parsed AST node.
517///
518/// This is the entry point for the first vertical slice. It lowers the
519/// statements inside a `Program` node into an arena-based [`HirBody`].
520///
521/// Currently handled constructs:
522/// - `my $x = EXPR;` — [`HirStmt::Let`] with an [`HirExpr::Assign`] initializer
523/// - `$a + $b` — [`HirExpr::Binary`] with explicit child IDs
524/// - Variable references — [`HirExpr::Variable`]
525/// - Everything else — [`HirExpr::Opaque`] / [`HirStmt::Expr`] fallback
526pub fn lower_body(ast: &Node) -> HirBody {
527    let mut builder = BodyBuilder::new();
528
529    let stmts = match &ast.kind {
530        NodeKind::Program { statements } => statements.as_slice(),
531        _ => std::slice::from_ref(ast),
532    };
533
534    let root_range = ast.location;
535    let mut root_block = HirBlock::default();
536
537    for stmt_node in stmts {
538        let stmt_id = lower_statement(&mut builder, stmt_node);
539        root_block.stmts.push(stmt_id);
540    }
541
542    let root_id = builder.alloc_block(root_block, root_range);
543    builder.finish(root_id, BodyOwnerKind::ProgramRoot)
544}
545
546fn lower_statement(builder: &mut BodyBuilder, node: &Node) -> HirStmtId {
547    let range = node.location;
548
549    match &node.kind {
550        NodeKind::VariableDeclaration { declarator, variable, initializer, .. } => {
551            // Extract variable name and sigil from the inner Variable node.
552            let (sigil_str, var_name) = match &variable.kind {
553                NodeKind::Variable { sigil, name } => (sigil.as_str(), name.clone()),
554                _ => ("$", String::from("<unknown>")),
555            };
556            let sigil = Sigil::from_str(sigil_str);
557            let storage = DeclStorageClass::from_str(declarator);
558
559            let init_expr_id = initializer.as_ref().map(|init_node| {
560                // The initializer is the full RHS expression.
561                // For `my $x = $a + $b`, the AST may represent this as:
562                //   VariableDeclaration { variable: $x, initializer: Binary(+, $a, $b) }
563                // We model the assignment as:
564                //   Assign { lhs: Variable($x, Write), rhs: lower_expr(initializer) }
565
566                // Allocate the write-place for $x
567                let place_expr = HirExpr::Variable(HirVariable {
568                    sigil: Sigil::from_str(sigil_str),
569                    name: var_name.clone(),
570                    kind: VariableKind::Lexical,
571                    access: AccessMode::Write,
572                });
573                let place_id = builder.alloc_expr(place_expr, variable.location);
574
575                // Lower the RHS value expression
576                let rhs_id = lower_expr(builder, init_node);
577
578                // Wrap in an Assign node spanning the full declaration range
579                let assign_range =
580                    SourceLocation { start: variable.location.start, end: init_node.location.end };
581                let assign_expr =
582                    HirExpr::Assign { lhs: place_id, rhs: rhs_id, mode: AssignMode::Simple };
583                builder.alloc_expr(assign_expr, assign_range)
584            });
585
586            builder.alloc_stmt(
587                HirStmt::Let { name: var_name, sigil, storage, init: init_expr_id },
588                range,
589            )
590        }
591
592        // Expression statement fallback
593        _ => {
594            let expr_id = lower_expr(builder, node);
595            builder.alloc_stmt(HirStmt::Expr(expr_id), range)
596        }
597    }
598}
599
600fn lower_expr(builder: &mut BodyBuilder, node: &Node) -> HirExprId {
601    let range = node.location;
602
603    match &node.kind {
604        NodeKind::Variable { sigil, name } => {
605            let var = HirVariable {
606                sigil: Sigil::from_str(sigil),
607                name: name.clone(),
608                kind: VariableKind::Lexical,
609                access: AccessMode::Read,
610            };
611            builder.alloc_expr(HirExpr::Variable(var), range)
612        }
613
614        NodeKind::Binary { op, left, right } => {
615            let lhs_id = lower_expr(builder, left);
616            let rhs_id = lower_expr(builder, right);
617            let binary_op = BinaryOp::from_str(op);
618            builder.alloc_expr(HirExpr::Binary { lhs: lhs_id, op: binary_op, rhs: rhs_id }, range)
619        }
620
621        NodeKind::Assignment { lhs, rhs, .. } => {
622            let lhs_id = lower_expr(builder, lhs);
623            let rhs_id = lower_expr(builder, rhs);
624            builder.alloc_expr(
625                HirExpr::Assign { lhs: lhs_id, rhs: rhs_id, mode: AssignMode::Simple },
626                range,
627            )
628        }
629
630        _ => {
631            let kind_name = node.kind.kind_name().to_string();
632            builder.alloc_expr(HirExpr::Opaque { ast_kind: kind_name }, range)
633        }
634    }
635}
perl_parser_core/hir/body.rs

perl_parser_core/hir/
body.rs
