vyre_libs/parsing/rust/sema/
mod.rs

1//! Rust semantic analysis: name resolution, type checking, borrow checking.
2//!
3//! Reusable substrate (Tier 3), mirroring `vyre-libs::parsing::c::sema`. The
4//! algorithms live here so any consumer can run typed Rust analysis without
5//! depending on the `vyre-frontend-rust` driver crate. The driver orchestrates.
6//!
7//! Analyses are side tables over the borrowed AST: a pass is
8//! `pass(&Module, &Resolution) -> Result<...>` and never clones the AST. This
9//! keeps the pipeline allocation-lean and extends cleanly as the compiler grows
10//! (new passes add new side tables, not new copies of the program).
11//!
12//! `resolve` and `typeck` are implemented for the nano-subset. `borrow_check`
13//! implements the mutability rule (E0596) and reports the conflicting-borrow
14//! rules (E0499/E0502) as not-yet-wired rather than faking a complete pass.
15
16use std::collections::HashMap;
17
18use thiserror::Error;
19
20use super::lex::tokens::{ANDAND, EQ, GE, GT, LE, LT, MINUS, NE, OROR, PERCENT, PLUS, SLASH, STAR};
21use super::parse::{Expr, Module, Stmt, Type};
22
23/// Stable id for a resolved binding (index into [`Resolution::bindings`]).
24pub type BindingId = usize;
25
26/// A resolved binding: a function parameter or a `let` declaration.
27#[derive(Debug, Clone, PartialEq)]
28pub struct Binding {
29    /// Recovered identifier text.
30    pub name: String,
31    /// Whether the binding was declared `mut`.
32    pub mutable: bool,
33    /// Declared type.
34    pub ty: Type,
35    /// Source byte offset of the defining identifier.
36    pub def_offset: u32,
37    /// Index of the enclosing function in `Module::functions`.
38    pub function: usize,
39}
40
41/// Name-resolution result: a binding table plus a use -> binding map over the
42/// AST. Holds no copy of the AST; analyses borrow the `Module` alongside it.
43#[derive(Debug, Clone, Default)]
44pub struct Resolution {
45    /// Every parameter and `let` binding, in declaration order.
46    pub bindings: Vec<Binding>,
47    /// Map from each variable-use source offset to its resolved binding.
48    pub uses: HashMap<u32, BindingId>,
49    /// Map from each call's name source offset to the callee function index.
50    pub calls: HashMap<u32, usize>,
51}
52
53/// Errors from the Rust semantic-analysis stages.
54#[derive(Debug, Clone, Error)]
55pub enum RustSemaError {
56    /// A variable use did not resolve to any in-scope binding (rustc E0425).
57    #[error("cannot find value `{name}` in this scope (byte {offset})")]
58    UnresolvedName {
59        /// The unresolved identifier text.
60        name: String,
61        /// Source byte offset of the use.
62        offset: u32,
63    },
64    /// A call referenced a function that is not defined (rustc E0425).
65    #[error("cannot find function `{name}` in this scope (byte {offset})")]
66    UnknownFunction {
67        /// The unresolved function name.
68        name: String,
69        /// Source byte offset of the call.
70        offset: u32,
71    },
72    /// A `&mut` borrow targeted an immutable place (rustc E0596).
73    #[error("cannot borrow `{name}` as mutable, as it is not declared as mutable (byte {offset})")]
74    CannotBorrowImmutableAsMutable {
75        /// The immutable binding being borrowed mutably.
76        name: String,
77        /// Source byte offset of the borrowed place.
78        offset: u32,
79    },
80    /// A function returned a reference to a call-local value (rustc E0597).
81    #[error(
82        "cannot return a reference to a local value; it does not live long enough (byte {offset})"
83    )]
84    ReturnsReferenceToLocal {
85        /// Source byte offset of the offending place.
86        offset: u32,
87    },
88    /// Two mutable borrows of the same place are live simultaneously (rustc E0499).
89    #[error("cannot borrow as mutable more than once at a time (byte {offset})")]
90    MultipleMutableBorrows {
91        /// Source byte offset of the conflicting borrow.
92        offset: u32,
93    },
94    /// A mutable and a shared borrow of the same place are live at once (rustc E0502).
95    #[error("cannot borrow as mutable because it is also borrowed as immutable (byte {offset})")]
96    MutableAndSharedBorrow {
97        /// Source byte offset of the conflicting borrow.
98        offset: u32,
99    },
100    /// An expression's type did not match the expected type (rustc E0308).
101    #[error("mismatched types in {context}: expected `{expected}`, found `{found}`")]
102    TypeMismatch {
103        /// Where the mismatch occurred (let binding, return, operand, argument).
104        context: String,
105        /// The expected type.
106        expected: String,
107        /// The type actually found.
108        found: String,
109    },
110    /// A dereference was applied to a non-reference type (rustc E0614).
111    #[error("type `{found}` cannot be dereferenced; only references can")]
112    CannotDeref {
113        /// The non-reference type.
114        found: String,
115    },
116    /// An `if` condition was not `bool` (rustc E0308).
117    #[error("`if` condition must be `bool`, found `{found}`")]
118    NonBooleanCondition {
119        /// The non-boolean condition type.
120        found: String,
121    },
122    /// A call passed the wrong number of arguments (rustc E0061).
123    #[error("function `{function}` expects {expected} argument(s), found {found}")]
124    ArgCountMismatch {
125        /// The called function name.
126        function: String,
127        /// The declared parameter count.
128        expected: usize,
129        /// The supplied argument count.
130        found: usize,
131    },
132    /// A non-unit function body does not return on all paths (rustc E0308).
133    #[error("function `{function}` must return `{expected}` on all paths")]
134    MissingReturn {
135        /// The function name.
136        function: String,
137        /// The declared return type.
138        expected: String,
139    },
140    /// Assignment to a binding not declared `mut` (rustc E0384).
141    #[error("cannot assign twice to immutable variable `{name}`")]
142    AssignToImmutable {
143        /// The immutable binding being assigned.
144        name: String,
145    },
146    /// Internal pass invariant failed.
147    #[error("internal Rust semantic invariant failed: {message}")]
148    InternalInvariant {
149        /// Actionable invariant diagnostic.
150        message: String,
151    },
152}
153
154/// Recover the identifier text that begins at `offset` in `source`.
155///
156/// The AST stores only the start offset of each identifier, so resolution and
157/// type checking re-scan the contiguous identifier bytes (`[A-Za-z0-9_]`).
158fn ident_at(source: &[u8], offset: u32) -> String {
159    let start = (offset as usize).min(source.len());
160    let mut end = start;
161    while end < source.len() && (source[end].is_ascii_alphanumeric() || source[end] == b'_') {
162        end += 1;
163    }
164    String::from_utf8_lossy(&source[start..end]).into_owned()
165}
166
167/// Whether a value of type `found` is accepted where `expected` is required,
168/// allowing rustc's `&mut T -> &T` reference coercion (top-level only; the
169/// pointee type must match exactly, as references are invariant in it). A shared
170/// `&T` never coerces to `&mut T`.
171fn coerces(found: &Type, expected: &Type) -> bool {
172    match (found, expected) {
173        (
174            Type::Ref {
175                mutable: fm,
176                inner: fi,
177            },
178            Type::Ref {
179                mutable: em,
180                inner: ei,
181            },
182        ) => (fm == em || (*fm && !*em)) && fi == ei,
183        _ => found == expected,
184    }
185}
186
187/// Render a type for diagnostics, matching Rust surface syntax.
188fn type_str(ty: &Type) -> String {
189    match ty {
190        Type::I32 => "i32".to_string(),
191        Type::Bool => "bool".to_string(),
192        Type::Unit => "()".to_string(),
193        Type::Ref { mutable, inner } => {
194            format!("&{}{}", if *mutable { "mut " } else { "" }, type_str(inner))
195        }
196    }
197}
198
199// ----------------------------------------------------------------------------
200// Name resolution
201// ----------------------------------------------------------------------------
202
203struct Resolver<'a> {
204    source: &'a [u8],
205    fn_index: &'a HashMap<String, usize>,
206    bindings: Vec<Binding>,
207    uses: HashMap<u32, BindingId>,
208    calls: HashMap<u32, usize>,
209    scopes: Vec<HashMap<String, BindingId>>,
210    function: usize,
211}
212
213impl Resolver<'_> {
214    fn declare(
215        &mut self,
216        name: String,
217        mutable: bool,
218        ty: Type,
219        def_offset: u32,
220    ) -> Result<(), RustSemaError> {
221        let id = self.bindings.len();
222        self.bindings.push(Binding {
223            name: name.clone(),
224            mutable,
225            ty,
226            def_offset,
227            function: self.function,
228        });
229        let scope = self
230            .scopes
231            .last_mut()
232            .ok_or_else(|| RustSemaError::InternalInvariant {
233                message:
234                    "resolver scope stack was empty while declaring a binding; seed the function scope before resolution"
235                        .to_string(),
236            })?;
237        scope.insert(name, id);
238        Ok(())
239    }
240
241    fn lookup(&self, name: &str) -> Option<BindingId> {
242        self.scopes
243            .iter()
244            .rev()
245            .find_map(|frame| frame.get(name).copied())
246    }
247
248    fn resolve_expr(&mut self, expr: &Expr) -> Result<(), RustSemaError> {
249        match expr {
250            Expr::LiteralInt(..) | Expr::LiteralBool(..) => Ok(()),
251            Expr::Var(offset) => {
252                let name = ident_at(self.source, *offset);
253                match self.lookup(&name) {
254                    Some(id) => {
255                        self.uses.insert(*offset, id);
256                        Ok(())
257                    }
258                    None => Err(RustSemaError::UnresolvedName {
259                        name,
260                        offset: *offset,
261                    }),
262                }
263            }
264            Expr::Binary { lhs, rhs, .. } => {
265                self.resolve_expr(lhs)?;
266                self.resolve_expr(rhs)
267            }
268            Expr::Borrow { expr, .. } => self.resolve_expr(expr),
269            Expr::Deref(inner) => self.resolve_expr(inner),
270            Expr::Not(inner) => self.resolve_expr(inner),
271            Expr::Neg(inner) => self.resolve_expr(inner),
272            Expr::Call { name, args } => {
273                let fname = ident_at(self.source, *name);
274                match self.fn_index.get(&fname) {
275                    Some(&idx) => {
276                        self.calls.insert(*name, idx);
277                    }
278                    None => {
279                        return Err(RustSemaError::UnknownFunction {
280                            name: fname,
281                            offset: *name,
282                        })
283                    }
284                }
285                for arg in args {
286                    self.resolve_expr(arg)?;
287                }
288                Ok(())
289            }
290            Expr::Block(stmts) => {
291                self.scopes.push(HashMap::new());
292                let result = self.resolve_block(stmts);
293                self.scopes.pop();
294                result
295            }
296            Expr::If {
297                cond,
298                then_block,
299                else_block,
300            } => {
301                self.resolve_expr(cond)?;
302                self.resolve_expr(then_block)?;
303                if let Some(else_block) = else_block {
304                    self.resolve_expr(else_block)?;
305                }
306                Ok(())
307            }
308        }
309    }
310
311    fn resolve_block(&mut self, stmts: &[Stmt]) -> Result<(), RustSemaError> {
312        for stmt in stmts {
313            match stmt {
314                Stmt::Let {
315                    mutable,
316                    name,
317                    ty,
318                    init,
319                } => {
320                    self.resolve_expr(init)?;
321                    let recovered = ident_at(self.source, *name);
322                    self.declare(recovered, *mutable, ty.clone(), *name)?;
323                }
324                Stmt::Expr(expr) => self.resolve_expr(expr)?,
325                Stmt::Assign { name, value } => {
326                    self.resolve_expr(value)?;
327                    let n = ident_at(self.source, *name);
328                    match self.lookup(&n) {
329                        Some(id) => {
330                            self.uses.insert(*name, id);
331                        }
332                        None => {
333                            return Err(RustSemaError::UnresolvedName {
334                                name: n,
335                                offset: *name,
336                            })
337                        }
338                    }
339                }
340                Stmt::Return(Some(expr)) => self.resolve_expr(expr)?,
341                Stmt::Return(None) => {}
342                Stmt::While { cond, body } => {
343                    self.resolve_expr(cond)?;
344                    self.scopes.push(HashMap::new());
345                    let r = self.resolve_block(body);
346                    self.scopes.pop();
347                    r?;
348                }
349                Stmt::For {
350                    name,
351                    start,
352                    end,
353                    body,
354                } => {
355                    self.resolve_expr(start)?;
356                    self.resolve_expr(end)?;
357                    self.scopes.push(HashMap::new());
358                    let recovered = ident_at(self.source, *name);
359                    self.declare(recovered, false, Type::I32, *name)?;
360                    let r = self.resolve_block(body);
361                    self.scopes.pop();
362                    r?;
363                }
364            }
365        }
366        Ok(())
367    }
368}
369
370/// Resolve names in a parsed module against its `source`.
371///
372/// Recovers identifier text from source offsets, tracks lexical scope
373/// (parameters plus block-nested `let`, with shadowing), maps every variable
374/// use to its binding, and rejects uses of names not in scope (rustc E0425).
375///
376/// # Errors
377/// Returns [`RustSemaError::UnresolvedName`] or [`RustSemaError::UnknownFunction`]
378/// for a use with no in-scope definition.
379pub fn resolve(module: &Module, source: &[u8]) -> Result<Resolution, RustSemaError> {
380    let fn_index: HashMap<String, usize> = module
381        .functions
382        .iter()
383        .enumerate()
384        .map(|(i, f)| (ident_at(source, f.name), i))
385        .collect();
386
387    let mut resolver = Resolver {
388        source,
389        fn_index: &fn_index,
390        bindings: Vec::new(),
391        uses: HashMap::new(),
392        calls: HashMap::new(),
393        scopes: Vec::new(),
394        function: 0,
395    };
396
397    for (index, func) in module.functions.iter().enumerate() {
398        resolver.function = index;
399        resolver.scopes = vec![HashMap::new()];
400        for (offset, ty) in &func.params {
401            let name = ident_at(source, *offset);
402            resolver.declare(name, false, ty.clone(), *offset)?;
403        }
404        resolver.resolve_block(&func.body)?;
405    }
406
407    Ok(Resolution {
408        bindings: resolver.bindings,
409        uses: resolver.uses,
410        calls: resolver.calls,
411    })
412}
413
414// ----------------------------------------------------------------------------
415// Type checking
416// ----------------------------------------------------------------------------
417
418struct FnSig {
419    params: Vec<Type>,
420    ret: Type,
421}
422
423struct TypeCk<'a> {
424    source: &'a [u8],
425    resolution: &'a Resolution,
426    sigs: &'a HashMap<String, FnSig>,
427    ret: &'a Type,
428}
429
430impl TypeCk<'_> {
431    fn type_of(&self, expr: &Expr) -> Result<Type, RustSemaError> {
432        match expr {
433            Expr::LiteralInt(..) => Ok(Type::I32),
434            Expr::LiteralBool(..) => Ok(Type::Bool),
435            Expr::Var(offset) => {
436                let id = *self.resolution.uses.get(offset).ok_or_else(|| {
437                    RustSemaError::InternalInvariant {
438                        message: format!(
439                            "resolve did not record variable use at byte {offset} before typeck"
440                        ),
441                    }
442                })?;
443                Ok(self.resolution.bindings[id].ty.clone())
444            }
445            Expr::Binary { op, lhs, rhs } => {
446                let lt = self.type_of(lhs)?;
447                let rt = self.type_of(rhs)?;
448                match *op {
449                    PLUS | MINUS | STAR | SLASH | PERCENT => {
450                        self.require(&lt, &Type::I32, "arithmetic operand")?;
451                        self.require(&rt, &Type::I32, "arithmetic operand")?;
452                        Ok(Type::I32)
453                    }
454                    LT | GT | LE | GE => {
455                        self.require(&lt, &Type::I32, "comparison operand")?;
456                        self.require(&rt, &Type::I32, "comparison operand")?;
457                        Ok(Type::Bool)
458                    }
459                    EQ | NE => {
460                        if lt != rt {
461                            return Err(RustSemaError::TypeMismatch {
462                                context: "equality operands".to_string(),
463                                expected: type_str(&lt),
464                                found: type_str(&rt),
465                            });
466                        }
467                        Ok(Type::Bool)
468                    }
469                    ANDAND | OROR => {
470                        self.require(&lt, &Type::Bool, "logical operand")?;
471                        self.require(&rt, &Type::Bool, "logical operand")?;
472                        Ok(Type::Bool)
473                    }
474                    _ => Ok(Type::I32),
475                }
476            }
477            Expr::Borrow { mutable, expr } => {
478                let inner = self.type_of(expr)?;
479                Ok(Type::Ref {
480                    mutable: *mutable,
481                    inner: Box::new(inner),
482                })
483            }
484            Expr::Deref(inner) => match self.type_of(inner)? {
485                Type::Ref { inner, .. } => Ok(*inner),
486                other => Err(RustSemaError::CannotDeref {
487                    found: type_str(&other),
488                }),
489            },
490            Expr::Not(inner) => {
491                let it = self.type_of(inner)?;
492                self.require(&it, &Type::Bool, "logical-not operand")?;
493                Ok(Type::Bool)
494            }
495            Expr::Neg(inner) => {
496                let it = self.type_of(inner)?;
497                self.require(&it, &Type::I32, "arithmetic-negation operand")?;
498                Ok(Type::I32)
499            }
500            Expr::Call { name, args } => {
501                let fname = ident_at(self.source, *name);
502                let sig = self
503                    .sigs
504                    .get(&fname)
505                    .ok_or(RustSemaError::UnknownFunction {
506                        name: fname.clone(),
507                        offset: *name,
508                    })?;
509                if args.len() != sig.params.len() {
510                    return Err(RustSemaError::ArgCountMismatch {
511                        function: fname,
512                        expected: sig.params.len(),
513                        found: args.len(),
514                    });
515                }
516                for (arg, param_ty) in args.iter().zip(&sig.params) {
517                    let at = self.type_of(arg)?;
518                    self.require(&at, param_ty, "function argument")?;
519                }
520                Ok(sig.ret.clone())
521            }
522            Expr::Block(stmts) => {
523                self.check_block(stmts)?;
524                Ok(Type::Unit)
525            }
526            Expr::If {
527                cond,
528                then_block,
529                else_block,
530            } => {
531                let ct = self.type_of(cond)?;
532                if ct != Type::Bool {
533                    return Err(RustSemaError::NonBooleanCondition {
534                        found: type_str(&ct),
535                    });
536                }
537                let tt = self.type_of(then_block)?;
538                let et = match else_block {
539                    Some(else_block) => self.type_of(else_block)?,
540                    None => Type::Unit,
541                };
542                if tt != et {
543                    return Err(RustSemaError::TypeMismatch {
544                        context: "if/else branches".to_string(),
545                        expected: type_str(&tt),
546                        found: type_str(&et),
547                    });
548                }
549                Ok(tt)
550            }
551        }
552    }
553
554    fn require(&self, found: &Type, expected: &Type, context: &str) -> Result<(), RustSemaError> {
555        if coerces(found, expected) {
556            Ok(())
557        } else {
558            Err(RustSemaError::TypeMismatch {
559                context: context.to_string(),
560                expected: type_str(expected),
561                found: type_str(found),
562            })
563        }
564    }
565
566    fn check_block(&self, stmts: &[Stmt]) -> Result<(), RustSemaError> {
567        for stmt in stmts {
568            match stmt {
569                Stmt::Let { ty, init, .. } => {
570                    let it = self.type_of(init)?;
571                    self.require(&it, ty, "let binding")?;
572                }
573                Stmt::Expr(expr) => {
574                    self.type_of(expr)?;
575                }
576                Stmt::Assign { name, value } => {
577                    let id = self.resolution.uses[name];
578                    let (mutable, target_ty, bname) = {
579                        let b = &self.resolution.bindings[id];
580                        (b.mutable, b.ty.clone(), b.name.clone())
581                    };
582                    if !mutable {
583                        return Err(RustSemaError::AssignToImmutable { name: bname });
584                    }
585                    let vt = self.type_of(value)?;
586                    self.require(&vt, &target_ty, "assignment")?;
587                }
588                Stmt::Return(Some(expr)) => {
589                    let rt = self.type_of(expr)?;
590                    self.require(&rt, self.ret, "return value")?;
591                }
592                Stmt::Return(None) => {
593                    self.require(&Type::Unit, self.ret, "return value")?;
594                }
595                Stmt::While { cond, body } => {
596                    let ct = self.type_of(cond)?;
597                    if ct != Type::Bool {
598                        return Err(RustSemaError::NonBooleanCondition {
599                            found: type_str(&ct),
600                        });
601                    }
602                    self.check_block(body)?;
603                }
604                Stmt::For {
605                    start, end, body, ..
606                } => {
607                    let st = self.type_of(start)?;
608                    self.require(&st, &Type::I32, "for range start")?;
609                    let et = self.type_of(end)?;
610                    self.require(&et, &Type::I32, "for range end")?;
611                    self.check_block(body)?;
612                }
613            }
614        }
615        Ok(())
616    }
617}
618
619/// Type-check a resolved module against its `source` (rustc E0308 / E0061 / E0614).
620///
621/// Checks `let` initializer types, return-value types, binary-operator operand
622/// types, dereference of references only, boolean `if` conditions, call arity
623/// and argument types, and that a non-unit function returns on all paths.
624///
625/// # Errors
626/// Returns the matching [`RustSemaError`] variant on a type error.
627pub fn typeck(
628    module: &Module,
629    source: &[u8],
630    resolution: &Resolution,
631) -> Result<(), RustSemaError> {
632    let sigs: HashMap<String, FnSig> = module
633        .functions
634        .iter()
635        .map(|f| {
636            (
637                ident_at(source, f.name),
638                FnSig {
639                    params: f.params.iter().map(|(_, t)| t.clone()).collect(),
640                    ret: f.ret.clone(),
641                },
642            )
643        })
644        .collect();
645
646    for func in &module.functions {
647        let ck = TypeCk {
648            source,
649            resolution,
650            sigs: &sigs,
651            ret: &func.ret,
652        };
653        ck.check_block(&func.body)?;
654        if func.ret != Type::Unit && !block_diverges(&func.body) {
655            return Err(RustSemaError::MissingReturn {
656                function: ident_at(source, func.name),
657                expected: type_str(&func.ret),
658            });
659        }
660    }
661    Ok(())
662}
663
664/// Whether a statement sequence is guaranteed to return on all paths.
665fn block_diverges(stmts: &[Stmt]) -> bool {
666    stmts.iter().any(stmt_diverges)
667}
668
669fn stmt_diverges(stmt: &Stmt) -> bool {
670    match stmt {
671        Stmt::Return(_) => true,
672        Stmt::Expr(expr) => expr_diverges(expr),
673        Stmt::Assign { .. } => false,
674        Stmt::While { .. } => false,
675        Stmt::For { .. } => false,
676        Stmt::Let { init, .. } => expr_diverges(init),
677    }
678}
679
680fn expr_diverges(expr: &Expr) -> bool {
681    match expr {
682        Expr::Block(stmts) => block_diverges(stmts),
683        Expr::If {
684            then_block,
685            else_block: Some(else_block),
686            ..
687        } => expr_diverges(then_block) && expr_diverges(else_block),
688        _ => false,
689    }
690}
691
692// ----------------------------------------------------------------------------
693// Borrow checking
694// ----------------------------------------------------------------------------
695
696/// Borrow-check a resolved module: the nano-subset verdict.
697///
698/// Runs mutability (E0596) via [`check_mutability`], dangling-reference / escape
699/// (E0597) via [`check_escape`], and conflicting borrows (E0499/E0502) via
700/// [`check_conflicts`], which lowers each function to a CFG and runs the NLL
701/// loan-liveness engine (branches and through-deref reborrows included). On the
702/// nano-subset this verdict is accept/reject-identical to rustc; the
703/// `rust_sema_borrow_oracle` differential gates that agreement against a real
704/// rustc over generated straight-line, branch, and reborrow programs.
705///
706/// # Errors
707/// Returns the matching [`RustSemaError`] for an E0596/E0597/E0499/E0502 violation.
708pub fn borrow_check(module: &Module, resolution: &Resolution) -> Result<(), RustSemaError> {
709    check_mutability(module, resolution)?;
710    check_escape(module, resolution)?;
711    check_conflicts(module, resolution)?;
712    Ok(())
713}
714
715/// Check the mutability borrow rule (rustc E0596) over a resolved module.
716///
717/// A `&mut` borrow is rejected when the borrowed place is an immutable binding
718/// or a dereference of a shared (`&T`) reference. Borrowing a temporary is
719/// allowed.
720///
721/// # Errors
722/// Returns [`RustSemaError::CannotBorrowImmutableAsMutable`] on a violation.
723pub fn check_mutability(module: &Module, resolution: &Resolution) -> Result<(), RustSemaError> {
724    for func in &module.functions {
725        check_mut_stmts(&func.body, resolution)?;
726    }
727    Ok(())
728}
729
730fn check_mut_stmts(stmts: &[Stmt], resolution: &Resolution) -> Result<(), RustSemaError> {
731    for stmt in stmts {
732        match stmt {
733            Stmt::Let { init, .. } => check_mut_expr(init, resolution)?,
734            Stmt::Expr(expr) => check_mut_expr(expr, resolution)?,
735            Stmt::Assign { value, .. } => check_mut_expr(value, resolution)?,
736            Stmt::While { cond, body } => {
737                check_mut_expr(cond, resolution)?;
738                check_mut_stmts(body, resolution)?;
739            }
740            Stmt::For {
741                start, end, body, ..
742            } => {
743                check_mut_expr(start, resolution)?;
744                check_mut_expr(end, resolution)?;
745                check_mut_stmts(body, resolution)?;
746            }
747            Stmt::Return(Some(expr)) => check_mut_expr(expr, resolution)?,
748            Stmt::Return(None) => {}
749        }
750    }
751    Ok(())
752}
753
754fn check_mut_expr(expr: &Expr, resolution: &Resolution) -> Result<(), RustSemaError> {
755    match expr {
756        Expr::Borrow { mutable, expr } => {
757            if *mutable {
758                check_mutable_place(expr, resolution)?;
759            }
760            check_mut_expr(expr, resolution)
761        }
762        Expr::Binary { lhs, rhs, .. } => {
763            check_mut_expr(lhs, resolution)?;
764            check_mut_expr(rhs, resolution)
765        }
766        Expr::Deref(inner) => check_mut_expr(inner, resolution),
767        Expr::Not(inner) => check_mut_expr(inner, resolution),
768        Expr::Neg(inner) => check_mut_expr(inner, resolution),
769        Expr::Call { args, .. } => {
770            for arg in args {
771                check_mut_expr(arg, resolution)?;
772            }
773            Ok(())
774        }
775        Expr::Block(stmts) => check_mut_stmts(stmts, resolution),
776        Expr::If {
777            cond,
778            then_block,
779            else_block,
780        } => {
781            check_mut_expr(cond, resolution)?;
782            check_mut_expr(then_block, resolution)?;
783            if let Some(else_block) = else_block {
784                check_mut_expr(else_block, resolution)?;
785            }
786            Ok(())
787        }
788        Expr::LiteralInt(..) | Expr::LiteralBool(..) | Expr::Var(..) => Ok(()),
789    }
790}
791
792/// Verify that `place` denotes a mutable place for a `&mut` borrow.
793fn check_mutable_place(place: &Expr, resolution: &Resolution) -> Result<(), RustSemaError> {
794    match place {
795        Expr::Var(offset) => {
796            if let Some(&id) = resolution.uses.get(offset) {
797                let binding = &resolution.bindings[id];
798                if !binding.mutable {
799                    return Err(RustSemaError::CannotBorrowImmutableAsMutable {
800                        name: binding.name.clone(),
801                        offset: *offset,
802                    });
803                }
804            }
805            Ok(())
806        }
807        Expr::Deref(inner) => {
808            if let Expr::Var(offset) = inner.as_ref() {
809                if let Some(&id) = resolution.uses.get(offset) {
810                    let binding = &resolution.bindings[id];
811                    if let Type::Ref { mutable: false, .. } = binding.ty {
812                        return Err(RustSemaError::CannotBorrowImmutableAsMutable {
813                            name: binding.name.clone(),
814                            offset: *offset,
815                        });
816                    }
817                }
818            }
819            Ok(())
820        }
821        _ => Ok(()),
822    }
823}
824
825/// Check that no function returns a reference to a call-local value (rustc E0597).
826///
827/// A reference escapes only if it borrows a binding's storage (`&x`, for any
828/// local binding) or transitively points at such a borrow. A reference derived
829/// from a `&T` parameter's pointee (`return r`, `&*r`) is allowed. The check
830/// never rejects a reference whose provenance it cannot prove local, so it never
831/// diverges from rustc on acceptance.
832///
833/// # Errors
834/// Returns [`RustSemaError::ReturnsReferenceToLocal`] when a returned reference
835/// provably borrows a local value.
836pub fn check_escape(module: &Module, resolution: &Resolution) -> Result<(), RustSemaError> {
837    let def_to_id: HashMap<u32, BindingId> = resolution
838        .bindings
839        .iter()
840        .enumerate()
841        .map(|(id, b)| (b.def_offset, id))
842        .collect();
843
844    for func in &module.functions {
845        let returns_ref = matches!(func.ret, Type::Ref { .. });
846        // A reference's borrows-local provenance: true if the reference value
847        // ultimately points at a call-local binding's storage. Parameters point
848        // outside the call, so they start false.
849        let mut borrows_local: HashMap<BindingId, bool> = HashMap::new();
850        for (offset, _ty) in &func.params {
851            if let Some(&id) = def_to_id.get(offset) {
852                borrows_local.insert(id, false);
853            }
854        }
855        walk_escape(
856            &func.body,
857            returns_ref,
858            &def_to_id,
859            resolution,
860            &mut borrows_local,
861        )?;
862    }
863    Ok(())
864}
865
866fn walk_escape(
867    stmts: &[Stmt],
868    returns_ref: bool,
869    def_to_id: &HashMap<u32, BindingId>,
870    resolution: &Resolution,
871    borrows_local: &mut HashMap<BindingId, bool>,
872) -> Result<(), RustSemaError> {
873    for stmt in stmts {
874        match stmt {
875            Stmt::Let { name, ty, init, .. } => {
876                if let Some(&id) = def_to_id.get(name) {
877                    let escapes = matches!(ty, Type::Ref { .. })
878                        && escapes_offset(init, resolution, borrows_local).is_some();
879                    borrows_local.insert(id, escapes);
880                }
881                descend_escape(init, returns_ref, def_to_id, resolution, borrows_local)?;
882            }
883            Stmt::Expr(expr) => {
884                descend_escape(expr, returns_ref, def_to_id, resolution, borrows_local)?;
885            }
886            Stmt::Assign { value, .. } => {
887                descend_escape(value, returns_ref, def_to_id, resolution, borrows_local)?;
888            }
889            Stmt::While { cond, body } => {
890                descend_escape(cond, returns_ref, def_to_id, resolution, borrows_local)?;
891                walk_escape(body, returns_ref, def_to_id, resolution, borrows_local)?;
892            }
893            Stmt::For {
894                start, end, body, ..
895            } => {
896                descend_escape(start, returns_ref, def_to_id, resolution, borrows_local)?;
897                descend_escape(end, returns_ref, def_to_id, resolution, borrows_local)?;
898                walk_escape(body, returns_ref, def_to_id, resolution, borrows_local)?;
899            }
900            Stmt::Return(Some(expr)) => {
901                if returns_ref {
902                    if let Some(offset) = escapes_offset(expr, resolution, borrows_local) {
903                        return Err(RustSemaError::ReturnsReferenceToLocal { offset });
904                    }
905                }
906                descend_escape(expr, returns_ref, def_to_id, resolution, borrows_local)?;
907            }
908            Stmt::Return(None) => {}
909        }
910    }
911    Ok(())
912}
913
914fn descend_escape(
915    expr: &Expr,
916    returns_ref: bool,
917    def_to_id: &HashMap<u32, BindingId>,
918    resolution: &Resolution,
919    borrows_local: &mut HashMap<BindingId, bool>,
920) -> Result<(), RustSemaError> {
921    match expr {
922        Expr::Block(stmts) => walk_escape(stmts, returns_ref, def_to_id, resolution, borrows_local),
923        Expr::If {
924            cond,
925            then_block,
926            else_block,
927        } => {
928            descend_escape(cond, returns_ref, def_to_id, resolution, borrows_local)?;
929            descend_escape(
930                then_block,
931                returns_ref,
932                def_to_id,
933                resolution,
934                borrows_local,
935            )?;
936            if let Some(else_block) = else_block {
937                descend_escape(
938                    else_block,
939                    returns_ref,
940                    def_to_id,
941                    resolution,
942                    borrows_local,
943                )?;
944            }
945            Ok(())
946        }
947        Expr::Binary { lhs, rhs, .. } => {
948            descend_escape(lhs, returns_ref, def_to_id, resolution, borrows_local)?;
949            descend_escape(rhs, returns_ref, def_to_id, resolution, borrows_local)
950        }
951        Expr::Borrow { expr, .. } => {
952            descend_escape(expr, returns_ref, def_to_id, resolution, borrows_local)
953        }
954        Expr::Deref(inner) => {
955            descend_escape(inner, returns_ref, def_to_id, resolution, borrows_local)
956        }
957        Expr::Not(inner) => {
958            descend_escape(inner, returns_ref, def_to_id, resolution, borrows_local)
959        }
960        Expr::Neg(inner) => {
961            descend_escape(inner, returns_ref, def_to_id, resolution, borrows_local)
962        }
963        Expr::Call { args, .. } => {
964            for arg in args {
965                descend_escape(arg, returns_ref, def_to_id, resolution, borrows_local)?;
966            }
967            Ok(())
968        }
969        Expr::Var(..) | Expr::LiteralInt(..) | Expr::LiteralBool(..) => Ok(()),
970    }
971}
972
973/// If the reference value `expr` provably borrows a call-local binding, return
974/// the source offset of the offending place; otherwise `None`.
975fn escapes_offset(
976    expr: &Expr,
977    resolution: &Resolution,
978    borrows_local: &HashMap<BindingId, bool>,
979) -> Option<u32> {
980    match expr {
981        Expr::Borrow { expr, .. } => match expr.as_ref() {
982            // `&x` borrows the storage of a call-local binding; it escapes.
983            Expr::Var(offset) => Some(*offset),
984            // `&*r` points at r's pointee; it escapes iff that pointee is local.
985            Expr::Deref(inner) => {
986                if let Expr::Var(offset) = inner.as_ref() {
987                    let id = resolution.uses.get(offset)?;
988                    if *borrows_local.get(id).unwrap_or(&false) {
989                        Some(*offset)
990                    } else {
991                        None
992                    }
993                } else {
994                    None
995                }
996            }
997            _ => None,
998        },
999        // Returning a reference binding escapes iff it holds a local borrow.
1000        Expr::Var(offset) => {
1001            let id = resolution.uses.get(offset)?;
1002            if *borrows_local.get(id).unwrap_or(&false) {
1003                Some(*offset)
1004            } else {
1005                None
1006            }
1007        }
1008        _ => None,
1009    }
1010}
1011
1012// ----------------------------------------------------------------------------
1013// Conflicting borrows (E0499 / E0502)
1014// ----------------------------------------------------------------------------
1015
1016/// Conflicting-borrow rules (rustc E0499 / E0502).
1017///
1018/// Lowers each function to neutral [`crate::borrowck::BorrowFacts`] (a CFG with
1019/// loan issue/use points, branches included) and runs the front-end-agnostic
1020/// engine, which computes NLL loan liveness as a CFG dataflow. Correct across
1021/// control flow: borrows live across a branch point conflict; borrows confined
1022/// to mutually exclusive branches do not. Only direct `&[mut] x` borrows are
1023/// tracked as loans today; through-deref and nested-block borrows are a sound
1024/// gap (never false-rejects).
1025///
1026/// # Errors
1027/// Returns [`RustSemaError::MultipleMutableBorrows`] (E0499) or
1028/// [`RustSemaError::MutableAndSharedBorrow`] (E0502) on a detected conflict.
1029pub fn check_conflicts(module: &Module, resolution: &Resolution) -> Result<(), RustSemaError> {
1030    use crate::{analyze_borrow_facts as analyze, ConflictKind};
1031
1032    let def_to_id: HashMap<u32, BindingId> = resolution
1033        .bindings
1034        .iter()
1035        .enumerate()
1036        .map(|(id, b)| (b.def_offset, id))
1037        .collect();
1038
1039    for func in &module.functions {
1040        let facts = build_borrow_facts(func, resolution, &def_to_id);
1041        if let Some(conflict) = analyze(&facts).into_iter().next() {
1042            return Err(match conflict.kind {
1043                ConflictKind::TwoMutable => RustSemaError::MultipleMutableBorrows {
1044                    offset: conflict.offset,
1045                },
1046                ConflictKind::MutableAndShared => RustSemaError::MutableAndSharedBorrow {
1047                    offset: conflict.offset,
1048                },
1049            });
1050        }
1051    }
1052    Ok(())
1053}
1054
1055/// Lower one function body to neutral borrow facts: a CFG over program points,
1056/// the `&[mut] x` loans, and each loan's use points.
1057fn build_borrow_facts(
1058    func: &super::parse::Function,
1059    resolution: &Resolution,
1060    def_to_id: &HashMap<u32, BindingId>,
1061) -> crate::borrowck::BorrowFacts {
1062    let mut builder = FactBuilder {
1063        resolution,
1064        def_to_id,
1065        facts: crate::borrowck::BorrowFacts::default(),
1066        binding_to_loan: HashMap::new(),
1067    };
1068    builder.build_block(&func.body, &[]);
1069    builder.facts
1070}
1071
1072struct FactBuilder<'a> {
1073    resolution: &'a Resolution,
1074    def_to_id: &'a HashMap<u32, BindingId>,
1075    facts: crate::borrowck::BorrowFacts,
1076    binding_to_loan: HashMap<BindingId, crate::borrowck::Loan>,
1077}
1078
1079impl FactBuilder<'_> {
1080    fn alloc_point(&mut self) -> u32 {
1081        let point = self.facts.point_count;
1082        self.facts.point_count += 1;
1083        point
1084    }
1085
1086    /// Build the CFG for `stmts`; `preds` are the points flowing in. Returns the
1087    /// points flowing out (empty if every path returns).
1088    fn build_block(&mut self, stmts: &[Stmt], preds: &[u32]) -> Vec<u32> {
1089        let mut cur: Vec<u32> = preds.to_vec();
1090        for stmt in stmts {
1091            let point = self.alloc_point();
1092            for &pred in &cur {
1093                self.facts.cfg_edges.push((pred, point));
1094            }
1095            match stmt {
1096                Stmt::Let { name, ty, init, .. } => {
1097                    self.record_uses(init, point);
1098                    self.record_loan(name, ty, init, point);
1099                    cur = vec![point];
1100                }
1101                Stmt::Return(value) => {
1102                    if let Some(expr) = value {
1103                        self.record_uses(expr, point);
1104                    }
1105                    cur = Vec::new();
1106                }
1107                Stmt::Assign { value, .. } => {
1108                    self.record_uses(value, point);
1109                    cur = vec![point];
1110                }
1111                Stmt::While { cond, body } => {
1112                    self.record_uses(cond, point);
1113                    let out = self.build_block(body, &[point]);
1114                    for &b in &out {
1115                        self.facts.cfg_edges.push((b, point));
1116                    }
1117                    cur = vec![point];
1118                }
1119                Stmt::For {
1120                    start, end, body, ..
1121                } => {
1122                    self.record_uses(start, point);
1123                    self.record_uses(end, point);
1124                    let out = self.build_block(body, &[point]);
1125                    for &b in &out {
1126                        self.facts.cfg_edges.push((b, point));
1127                    }
1128                    cur = vec![point];
1129                }
1130                Stmt::Expr(Expr::If {
1131                    cond,
1132                    then_block,
1133                    else_block,
1134                }) => {
1135                    self.record_uses(cond, point);
1136                    let mut out = self.build_block(block_stmts(then_block), &[point]);
1137                    match else_block {
1138                        Some(else_block) => {
1139                            out.extend(self.build_block(block_stmts(else_block), &[point]))
1140                        }
1141                        None => out.push(point),
1142                    }
1143                    cur = out;
1144                }
1145                Stmt::Expr(expr) => {
1146                    self.record_uses(expr, point);
1147                    cur = vec![point];
1148                }
1149            }
1150        }
1151        cur
1152    }
1153
1154    /// Record a loan for a borrow-introducing `let`:
1155    /// - `let a = &[mut] x;` borrows place `x`;
1156    /// - `let a = &[mut] *r;` reborrows through `r` (place `r`);
1157    /// - `let a: &[mut] T = r;` is a reborrow coercion (the grammar requires the
1158    ///   annotation, so it is never a move): it reborrows `*r` with the let
1159    ///   type's mutability, place `r`.
1160    ///
1161    /// In the nano-subset a reborrow conflicts exactly when another borrow of
1162    /// the same `r` is live, matching rustc.
1163    fn record_loan(&mut self, name: &u32, ty: &Type, init: &Expr, point: u32) {
1164        let (place_off, mutable) = match init {
1165            Expr::Borrow { mutable, expr } => {
1166                let off = match expr.as_ref() {
1167                    Expr::Var(off) => Some(*off),
1168                    Expr::Deref(inner) => match inner.as_ref() {
1169                        Expr::Var(off) => Some(*off),
1170                        _ => None,
1171                    },
1172                    _ => None,
1173                };
1174                match off {
1175                    Some(off) => (off, *mutable),
1176                    None => return,
1177                }
1178            }
1179            Expr::Var(off) => match ty {
1180                Type::Ref { mutable, .. } => (*off, *mutable),
1181                _ => return,
1182            },
1183            _ => return,
1184        };
1185        if let (Some(&place), Some(&binding)) = (
1186            self.resolution.uses.get(&place_off),
1187            self.def_to_id.get(name),
1188        ) {
1189            let loan = self.facts.loan_place.len() as crate::borrowck::Loan;
1190            self.facts.loan_place.push(place as crate::borrowck::Place);
1191            self.facts.loan_kind.push(if mutable {
1192                crate::borrowck::LoanKind::Mut
1193            } else {
1194                crate::borrowck::LoanKind::Shared
1195            });
1196            self.facts.loan_issued_at.push(point);
1197            self.facts.loan_offset.push(*name);
1198            self.binding_to_loan.insert(binding, loan);
1199        }
1200    }
1201
1202    /// Record uses of loan bindings in `expr` at `point` (not descending into
1203    /// nested `if`/block bodies, which carry their own points).
1204    fn record_uses(&mut self, expr: &Expr, point: u32) {
1205        let mut used = Vec::new();
1206        collect_expr_uses(expr, self.resolution, &mut used);
1207        for binding in used {
1208            if let Some(&loan) = self.binding_to_loan.get(&binding) {
1209                self.facts.loan_used_at.push((loan, point));
1210            }
1211        }
1212    }
1213}
1214
1215/// Statement list of a block expression (empty for anything else).
1216fn block_stmts(expr: &Expr) -> &[Stmt] {
1217    match expr {
1218        Expr::Block(stmts) => stmts,
1219        _ => &[],
1220    }
1221}
1222
1223fn collect_expr_uses(expr: &Expr, resolution: &Resolution, into: &mut Vec<BindingId>) {
1224    match expr {
1225        Expr::Var(off) => {
1226            if let Some(&id) = resolution.uses.get(off) {
1227                into.push(id);
1228            }
1229        }
1230        Expr::Binary { lhs, rhs, .. } => {
1231            collect_expr_uses(lhs, resolution, into);
1232            collect_expr_uses(rhs, resolution, into);
1233        }
1234        Expr::Borrow { expr, .. } => collect_expr_uses(expr, resolution, into),
1235        Expr::Deref(inner) => collect_expr_uses(inner, resolution, into),
1236        Expr::Not(inner) => collect_expr_uses(inner, resolution, into),
1237        Expr::Neg(inner) => collect_expr_uses(inner, resolution, into),
1238        Expr::Call { args, .. } => {
1239            for arg in args {
1240                collect_expr_uses(arg, resolution, into);
1241            }
1242        }
1243        // Do not descend into branch bodies: uses inside `if` blocks are not
1244        // counted, keeping the straight-line check sound (never false-rejects).
1245        Expr::Block(..) | Expr::If { .. } | Expr::LiteralInt(..) | Expr::LiteralBool(..) => {}
1246    }
1247}
vyre_libs/parsing/rust/sema/mod.rs

vyre_libs/parsing/rust/sema/
mod.rs
