elly_core/
resolve.rs

1//! Name resolution: a static pass that converts [`Expr::Name`] into de Bruijn-indexed
2//! [`Expr::Local`] or [`Expr::ModItem`] and rejects free variables.
3//!
4//! Every binding comes from a [`crate::ast::Lambda`] head. Builtins are handled at parse.
5//! `resolve` rewrites the tree in place and returns [`ParseError::UnboundName`] on free names.
6//!
7//! ## de Bruijn indices
8//!
9//! A lambda activation's environment is a cons list of head bindings (innermost first)
10//! sitting on a captured **frame**. The resolver mirrors this with a stack of [`Level`]s,
11//! each containing its head's `locals` (bind order) and `captures` (frame-slot order).
12//!
13//! Reference resolution:
14//! 1. Local: If bound by current level, index is `locals.len() - 1 - pos`.
15//! 2. Captured: If already in this level's `captures`, index is `locals.len() + slot`.
16//! 3. Outer: Otherwise, resolve recursively in parent. If found, record as a new
17//!    capture slot for this level and use `locals.len() + slot`.
18//!
19//! This process fills [`Lambda::captures`]: the outer indices used to copy values into
20//! the closure's frame.
21//!
22//! Root level: names are either unbound, auto-bound ([`resolve_open`]), or found in
23//! the prelude ([`resolve_prelude`]).
24//!
25//! Walk order mirrors the evaluator's binding order (see `match_pattern` in `eval.rs`):
26//! list rests bind before elements; map keys resolve before values.
27//!
28//! ## Or-arms
29//!
30//! Arms of `(p | q)` must bind the same names in the same order to ensure a reference
31//! after the pattern reads a fixed index regardless of the matching arm.
32//! Captures are not rolled back between arms; only `locals` are checked for sequence match.
33
34use alloc::boxed::Box;
35use alloc::rc::Rc;
36use alloc::vec::Vec;
37
38use crate::ast::{Capture, Captures, Expr, Lambda, MapKey, Pattern, ProtoRef, Text};
39use crate::builtins::Builtin;
40use crate::module::ModuleData;
41use crate::parse::ParseError;
42
43/// Rebuild a call spine `[<module>, .member, rest…]` around the member's own
44/// builtin leaf. Arguments are moved from the old spine to avoid copying subtrees.
45fn fold_member(items: &mut [Expr], op: Builtin) -> Expr {
46    let rest = &mut items[2..];
47    if rest.is_empty() {
48        return Expr::Builtin(op);
49    }
50    let mut spine: Vec<Expr> = Vec::with_capacity(rest.len() + 1);
51    spine.push(Expr::Builtin(op));
52    for arg in rest {
53        spine.push(core::mem::replace(arg, Expr::Builtin(op)));
54    }
55    Expr::App(spine.into_boxed_slice())
56}
57
58/// Resolve a program against an empty scope; free names are rejected as [`ParseError::UnboundName`].
59/// Rewrites `expr` in place (names → de Bruijn locals).
60pub fn resolve(expr: &mut Expr) -> Result<(), ParseError> {
61    Resolver::new(Vec::new(), false, Vec::new()).walk(expr)
62}
63
64/// Resolve a module's bodies in place. Item names are sorted to provide a stable
65/// index space for order-independent mutual recursion.
66///
67/// Lookup order: enclosing binders $\to$ imports $\to$ module members (iotas $\to$ items $\to$ locals)
68/// $\to$ root frame $\to$ builtin aliases.
69///
70/// Iotas are searched before items to prefer the iota in re-exporting forms (`false = const`).
71/// Imports are searched before items to prefer the frame slot in re-exporting forms (`Foo = import "spec"`).
72pub fn resolve_module_bodies(
73    bindings: &mut [(Text, Expr)],
74    locals: &mut [(Text, Expr)],
75    main: Option<&mut Expr>,
76    imports: &[Text],
77    iotas: &[Text],
78    frame: &[Text],
79) -> Result<(), ParseError> {
80    bindings.sort_by(|(a, _), (b, _)| a.as_str().cmp(b.as_str()));
81    locals.sort_by(|(a, _), (b, _)| a.as_str().cmp(b.as_str()));
82    let members = Barrier::Module {
83        items: bindings.iter().map(|(n, _)| n.clone()).collect(),
84        locals: locals.iter().map(|(n, _)| n.clone()).collect(),
85        iotas: iotas.to_vec(),
86    };
87    let mut slots: Vec<Text> = imports.to_vec();
88    slots.extend_from_slice(frame);
89    let bodies = bindings
90        .iter_mut()
91        .chain(locals.iter_mut())
92        .map(|(_, body)| body)
93        .chain(main);
94    for body in bodies {
95        Resolver::new(slots.clone(), false, alloc::vec![members.clone()])
96            .with_imports(imports.len())
97            .walk(body)?;
98    }
99    Ok(())
100}
101
102/// Resolve an open term: free names are auto-bound below the whole scope.
103pub fn resolve_open(expr: &mut Expr) -> Result<(), ParseError> {
104    Resolver::new(Vec::new(), true, Vec::new()).walk(expr)
105}
106
107/// Resolve `expr` against a named outer `prelude`. References to `prelude[i]`
108/// become index `i` of the root frame.
109pub fn resolve_prelude(expr: &mut Expr, prelude: &[Text]) -> Result<(), ParseError> {
110    Resolver::new(prelude.to_vec(), false, Vec::new()).walk(expr)
111}
112
113/// A lambda activation's compile-time scope.
114struct Level {
115    /// Head bindings in cons order (most recent last).
116    locals: Vec<Text>,
117    /// Free names captured in frame-slot order (prelude/auto-bound for root level).
118    captures: Vec<Text>,
119    /// Enclosing activation indices for each capture; unused for root level.
120    outer: Vec<u32>,
121}
122
123impl Level {
124    fn new() -> Level {
125        Level {
126            locals: Vec::new(),
127            captures: Vec::new(),
128            outer: Vec::new(),
129        }
130    }
131}
132
133/// A terminal's member set: names reachable via [`Expr::ModItem`].
134/// Members are sorted by name; lookup is a series of binary searches.
135/// Iotas are searched first (see [`resolve_module_bodies`]).
136#[derive(Clone)]
137enum Barrier {
138    /// Recur group bindings (items only).
139    Group { items: Vec<Text> },
140    /// Module declarations: items, locals, and iotas.
141    Module {
142        items: Vec<Text>,
143        locals: Vec<Text>,
144        iotas: Vec<Text>,
145    },
146}
147
148impl Barrier {
149    /// Position of `name` in the member index space.
150    fn member(&self, name: &str) -> Option<u32> {
151        let (items, locals, iotas) = match self {
152            Barrier::Group { items } => return search(items, name),
153            Barrier::Module {
154                items,
155                locals,
156                iotas,
157            } => (items, locals, iotas),
158        };
159        if let Some(i) = search(iotas, name) {
160            return Some(i + (items.len() + locals.len()) as u32);
161        }
162        if let Some(i) = search(items, name) {
163            return Some(i);
164        }
165        search(locals, name).map(|i| i + items.len() as u32)
166    }
167
168    /// Returns a `ParseError` if `name` is declared here (used by [`check_shadow`](Resolver::check_shadow)).
169    fn shadow_error(&self, name: &Text) -> Option<ParseError> {
170        match self {
171            Barrier::Group { items } => {
172                search(items, name.as_str()).map(|_| ParseError::ShadowsItem(name.clone()))
173            }
174            Barrier::Module {
175                items,
176                locals,
177                iotas,
178            } => {
179                if search(iotas, name.as_str()).is_some() {
180                    return Some(ParseError::ShadowsIota(name.clone()));
181                }
182                if search(items, name.as_str()).is_some() {
183                    return Some(ParseError::ShadowsItem(name.clone()));
184                }
185                search(locals, name.as_str()).map(|_| ParseError::ShadowsLocal(name.clone()))
186            }
187        }
188    }
189}
190
191/// Binary search for `name` in a sorted slice.
192fn search(part: &[Text], name: &str) -> Option<u32> {
193    part.binary_search_by(|it| it.as_str().cmp(name))
194        .ok()
195        .map(|i| i as u32)
196}
197
198/// Lexical resolver: a stack of [`Level`]s, with `levels[0]` as root.
199struct Resolver {
200    levels: Vec<Level>,
201    auto_bind: bool,
202    /// Enclosing member sets (outermost first).- scanned innermost-first.
203    /// Depth to the answering set is the [`Expr::ModItem`] `depth`.
204    barriers: Vec<Barrier>,
205    /// Number of root frame slots treated as imports (searched before item sets).
206    imports: usize,
207}
208
209/// Result of name resolution.
210enum Ref {
211    Local(u32),
212    /// Item in an enclosing group: position in sorted table and terminal depth.
213    Item {
214        index: u32,
215        depth: u32,
216    },
217    /// Builtin module via bare alias.
218    Builtin(Builtin),
219}
220
221impl Resolver {
222    fn new(root: Vec<Text>, auto_bind: bool, barriers: Vec<Barrier>) -> Resolver {
223        Resolver {
224            levels: alloc::vec![Level {
225                locals: Vec::new(),
226                captures: root,
227                outer: Vec::new(),
228            }],
229            auto_bind,
230            barriers,
231            imports: 0,
232        }
233    }
234
235    fn with_imports(mut self, n: usize) -> Resolver {
236        self.imports = n;
237        self
238    }
239
240    fn depth(&self) -> usize {
241        self.levels.len() - 1
242    }
243
244    /// Binds `name` to the innermost activation; rejects declared names via [`check_shadow`](Self::check_shadow).
245    fn bind(&mut self, name: &Text) -> Result<(), ParseError> {
246        self.check_shadow(name)?;
247        let li = self.depth();
248        self.levels[li].locals.push(name.clone());
249        Ok(())
250    }
251
252    /// Ensures a binder does not shadow a declared name (import, iota, item, or local).
253    /// Frame names and builtin aliases remain shadowable.
254    fn check_shadow(&self, name: &Text) -> Result<(), ParseError> {
255        if self.levels[0].captures[..self.imports]
256            .iter()
257            .any(|n| n.as_str() == name.as_str())
258        {
259            return Err(ParseError::ShadowsImport(name.clone()));
260        }
261        for members in &self.barriers {
262            if let Some(err) = members.shadow_error(name) {
263                return Err(err);
264            }
265        }
266        Ok(())
267    }
268
269    /// Resolves a reference at level `li`. Root search order:
270    /// imports $\to$ member sets $\to$ root frame $\to$ builtin aliases.
271    ///
272    /// Item references are passed back without recording captures, as they resolve
273    /// via the environment's terminal rather than a frame slot.
274    fn reference(&mut self, name: &str, li: usize) -> Result<Ref, ParseError> {
275        let lvl = &self.levels[li];
276        if let Some(pos) = lvl.locals.iter().rposition(|n| n.as_str() == name) {
277            return Ok(Ref::Local((lvl.locals.len() - 1 - pos) as u32));
278        }
279        if li == 0 {
280            let root = &self.levels[0];
281            if let Some(slot) = root.captures[..self.imports]
282                .iter()
283                .position(|n| n.as_str() == name)
284            {
285                return Ok(Ref::Local((root.locals.len() + slot) as u32));
286            }
287            for (i, members) in self.barriers.iter().enumerate().rev() {
288                if let Some(index) = members.member(name) {
289                    return Ok(Ref::Item {
290                        index,
291                        depth: (self.barriers.len() - 1 - i) as u32,
292                    });
293                }
294            }
295            let root = &mut self.levels[0];
296            if let Some(slot) = root.captures.iter().position(|n| n.as_str() == name) {
297                return Ok(Ref::Local((root.locals.len() + slot) as u32));
298            }
299            if let Some(op) = Builtin::from_alias(name) {
300                return Ok(Ref::Builtin(op));
301            }
302            if !self.auto_bind {
303                return Err(ParseError::UnboundName(Text::from(name)));
304            }
305            let slot = root.captures.len();
306            root.captures.push(Text::from(name));
307            return Ok(Ref::Local((root.locals.len() + slot) as u32));
308        }
309        if let Some(slot) = lvl.captures.iter().position(|n| n.as_str() == name) {
310            return Ok(Ref::Local((lvl.locals.len() + slot) as u32));
311        }
312        let outer = match self.reference(name, li - 1)? {
313            leaf @ (Ref::Item { .. } | Ref::Builtin(_)) => return Ok(leaf),
314            Ref::Local(outer) => outer,
315        };
316        let lvl = &mut self.levels[li];
317        let slot = lvl.captures.len();
318        lvl.captures.push(Text::from(name));
319        lvl.outer.push(outer);
320        Ok(Ref::Local((lvl.locals.len() + slot) as u32))
321    }
322
323    fn walk(&mut self, expr: &mut Expr) -> Result<(), ParseError> {
324        match expr {
325            Expr::Unit | Expr::Int(_) | Expr::Symbol(_) | Expr::Str(_) | Expr::Builtin(_) => Ok(()),
326            Expr::Home { leaf, depth } => {
327                *depth = Self::home_depth(&self.barriers)
328                    .ok_or_else(|| ParseError::OutsideModule(Text::from(leaf.name())))?;
329                Ok(())
330            }
331            Expr::Local { .. } | Expr::ModItem { .. } => Ok(()),
332            Expr::Name(n) => {
333                let name = n.clone();
334                *expr = match self.reference(&name, self.depth())? {
335                    Ref::Local(index) => Expr::Local {
336                        name: Box::new(name),
337                        index,
338                    },
339                    Ref::Item { index, depth } => Expr::ModItem {
340                        name: Box::new(name),
341                        index,
342                        depth,
343                    },
344                    Ref::Builtin(op) => Expr::Builtin(op),
345                };
346                Ok(())
347            }
348            Expr::List(elems) => {
349                for e in elems.iter_mut() {
350                    self.walk(e)?;
351                }
352                Ok(())
353            }
354            Expr::Map(entries) => {
355                for (k, v) in entries.iter_mut() {
356                    self.walk(k)?;
357                    self.walk(v)?;
358                }
359                Ok(())
360            }
361            Expr::App(items) => {
362                let callee = &mut items[0];
363                match callee {
364                    Expr::Abs(code) => self.walk_abs(code, Captures::Chain)?,
365                    _ => self.walk(callee)?,
366                }
367                if let (Expr::Builtin(ns), Some(Expr::Symbol(m))) = (&items[0], items.get(1)) {
368                    if let Some(op) = ns.member(m) {
369                        *expr = fold_member(items, op);
370                        return self.walk(expr);
371                    }
372                }
373                let (callee, args) = items.split_first_mut().expect("a call spine has a callee");
374                let consumer = match callee {
375                    Expr::Builtin(op) => Some(*op),
376                    _ => None,
377                };
378                for (i, arg) in args.iter_mut().enumerate() {
379                    match (consumer, &mut *arg) {
380                        (Some(op), Expr::Abs(code)) if op.applies_arg(i) => {
381                            self.walk_abs(code, Captures::Chain)?
382                        }
383                        (Some(op), Expr::List(elems)) if op.applies_elements_of(i) => {
384                            for e in elems.iter_mut() {
385                                match e {
386                                    Expr::Abs(code) => self.walk_abs(code, Captures::Chain)?,
387                                    _ => self.walk(e)?,
388                                }
389                            }
390                        }
391                        _ => self.walk(arg)?,
392                    }
393                }
394                Ok(())
395            }
396            Expr::Block(clauses) => {
397                let li = self.depth();
398                let base = self.levels[li].locals.len();
399                for clause in clauses.iter_mut() {
400                    match clause {
401                        (Some(pat), value) => {
402                            self.walk(value)?;
403                            self.walk_pattern(pat)?;
404                        }
405                        (None, value) => self.walk(value)?,
406                    }
407                }
408                self.levels[li].locals.truncate(base);
409                Ok(())
410            }
411            Expr::Abs(code) => self.walk_abs(code, Captures::Frame(Box::new([]))),
412            Expr::Recur(r) => self.walk_recur(r),
413            Expr::Case { subject, cases } => {
414                let subject = Rc::get_mut(subject)
415                    .expect("the case subject is uniquely owned at resolve time");
416                self.walk(subject)?;
417                let li = self.depth();
418                for (pat, body) in cases.iter_mut() {
419                    let base = self.levels[li].locals.len();
420                    self.walk_pattern(pat)?;
421                    self.walk(body)?;
422                    self.levels[li].locals.truncate(base);
423                }
424                Ok(())
425            }
426        }
427    }
428
429    /// Returns the number of terminals to step over to reach the nearest module barrier.
430    fn home_depth(barriers: &[Barrier]) -> Option<u32> {
431        barriers
432            .iter()
433            .rev()
434            .position(|b| matches!(b, Barrier::Module { .. }))
435            .map(|d| d as u32)
436    }
437
438    /// Read-only check if `name` is in scope.
439    fn in_scope(&self, name: &str) -> bool {
440        let lexical = self.levels.iter().any(|lvl| {
441            lvl.locals.iter().any(|n| n.as_str() == name)
442                || lvl.captures.iter().any(|n| n.as_str() == name)
443        });
444        lexical || self.barriers.iter().any(|m| m.member(name).is_some())
445    }
446
447    /// Resolve a [`recur`](Expr::Recur). Group becomes a barrier; bodies resolve under it.
448    ///
449    /// Binding names may not shadow names already in scope to prevent ambiguous self-references
450    /// (rejected as [`ParseError::RecurShadowsOuter`]). Binders inside the group may also
451    /// not take a group's binding name (see [`check_shadow`](Self::check_shadow)).
452    fn walk_recur(&mut self, group: &mut Rc<ModuleData>) -> Result<(), ParseError> {
453        let names: Vec<Text> = group.items().iter().map(|(n, _)| n.clone()).collect();
454        for name in &names {
455            if self.in_scope(name) {
456                return Err(ParseError::RecurShadowsOuter(name.clone()));
457            }
458        }
459        self.barriers.push(Barrier::Group { items: names });
460        let data = Rc::get_mut(group).expect("the group is uniquely owned at resolve time");
461        for (_, body) in data.items_mut() {
462            self.walk(body)?;
463        }
464        let body = data.body_mut().expect("a recur group always has a body");
465        self.walk(body)?;
466        self.barriers.pop();
467        Ok(())
468    }
469
470    /// Resolve an abstraction. `how` selects the closure's environment.
471    ///
472    /// [`Captures::Frame`]: Opens a new level for parameters, then the body.
473    /// Popping the level generates the frame-building plan.
474    ///
475    /// [`Captures::Chain`]: Binders extend the enclosing activation; no new level
476    /// is opened and nothing is captured.
477    fn walk_abs(&mut self, code: &mut Rc<Lambda>, how: Captures) -> Result<(), ParseError> {
478        let lam = Rc::get_mut(code).expect("the lambda is uniquely owned at resolve time");
479        if let Captures::Chain = how {
480            let li = self.depth();
481            let base = self.levels[li].locals.len();
482            for pat in lam.head.iter_mut() {
483                self.walk_pattern(pat)?;
484            }
485            self.walk(&mut lam.body)?;
486            self.levels[li].locals.truncate(base);
487            lam.captures = Captures::Chain;
488            return Ok(());
489        }
490        self.levels.push(Level::new());
491        for pat in lam.head.iter_mut() {
492            self.walk_pattern(pat)?;
493        }
494        self.walk(&mut lam.body)?;
495        let level = self.levels.pop().expect("the level just pushed");
496        lam.captures = Captures::Frame(Self::capture_plan(&level.outer));
497        Ok(())
498    }
499
500    /// Converts a level's captures into a sorted frame-building plan.
501    /// Sorted by `outer` index to allow filling the frame in one ascending walk.
502    fn capture_plan(outer: &[u32]) -> Box<[Capture]> {
503        let mut plan: Vec<Capture> = outer
504            .iter()
505            .enumerate()
506            .map(|(slot, &outer)| Capture {
507                outer,
508                slot: slot as u32,
509            })
510            .collect();
511        plan.sort_unstable_by_key(|c| c.outer);
512        plan.into_boxed_slice()
513    }
514
515    /// Resolve a pattern: binds parameters and resolves embedded expressions
516    /// in the order the evaluator's matcher conses.
517    fn walk_pattern(&mut self, pat: &mut Pattern) -> Result<(), ParseError> {
518        match pat {
519            Pattern::Discard | Pattern::Unit => Ok(()),
520            Pattern::Bind(name) => self.bind(name),
521            Pattern::At(name, inner) => {
522                self.bind(name)?;
523                self.walk_pattern(inner)
524            }
525            Pattern::Equal(e) | Pattern::Less(e) | Pattern::Greater(e) => self.walk(e),
526            Pattern::Type(proto, inner) => {
527                if let ProtoRef::Ref(expr) = proto {
528                    self.walk(expr)?;
529                    if let Expr::Builtin(op) = expr {
530                        match op.proto_kind() {
531                            Some(kind) => *proto = ProtoRef::Kind(kind),
532                            None => return Err(ParseError::NotAPrototype(Text::from(op.name()))),
533                        }
534                    }
535                }
536                self.walk_pattern(inner)
537            }
538            Pattern::Unwrap { depth, inner } => {
539                *depth = Self::home_depth(&self.barriers)
540                    .ok_or_else(|| ParseError::OutsideModule(Text::from("Self")))?;
541                self.walk_pattern(inner)
542            }
543            Pattern::Or(left, right) => {
544                let li = self.depth();
545                let base = self.levels[li].locals.len();
546                self.walk_pattern(left)?;
547                let left_names: Vec<Text> = self.levels[li].locals[base..].to_vec();
548                self.levels[li].locals.truncate(base);
549                self.walk_pattern(right)?;
550                if self.levels[li].locals[base..] != left_names[..] {
551                    return Err(ParseError::OrBindersMismatch);
552                }
553                Ok(())
554            }
555            Pattern::List { elems, rest } => {
556                if let Some(rp) = rest {
557                    self.walk_pattern(rp)?;
558                }
559                for e in elems.iter_mut() {
560                    self.walk_pattern(e)?;
561                }
562                Ok(())
563            }
564            Pattern::Map { entries, rest } => {
565                for (key, _) in entries.iter_mut() {
566                    if let MapKey::Lookup(ke) = key {
567                        self.walk(ke)?;
568                    }
569                }
570                for (key, vpat) in entries.iter_mut() {
571                    if let MapKey::Lookup(_) = key {
572                        self.walk_pattern(vpat)?;
573                    }
574                }
575                for (key, vpat) in entries.iter_mut() {
576                    if let MapKey::Capture(kpat) = key {
577                        self.walk_pattern(kpat)?;
578                        self.walk_pattern(vpat)?;
579                    }
580                }
581                if let Some(rp) = rest {
582                    self.walk_pattern(rp)?;
583                }
584                Ok(())
585            }
586            Pattern::When { inner, when } => {
587                self.walk_pattern(inner)?;
588                let (guard, cond) = when;
589                self.walk(cond)?;
590                if let Some(gpat) = guard {
591                    self.walk_pattern(gpat)?;
592                }
593                Ok(())
594            }
595        }
596    }
597}
elly_core/resolve.rs

elly_core/
resolve.rs
