scheme_rs/
env.rs

1//! Scheme lexical environments.
2
3use std::{
4    collections::{BTreeSet, HashMap, hash_map::Entry},
5    fmt,
6    hash::{Hash, Hasher},
7    path::{Path, PathBuf},
8    sync::{
9        LazyLock,
10        atomic::{AtomicUsize, Ordering},
11    },
12};
13
14use parking_lot::{MappedRwLockReadGuard, Mutex, RwLock, RwLockReadGuard};
15use scheme_rs_macros::{maybe_async, maybe_await};
16
17#[cfg(feature = "async")]
18use futures::future::BoxFuture;
19
20use crate::{
21    ast::{
22        DefinitionBody, ExportSet, ImportSet, LibraryName, LibrarySpec, ParseContext, Primitive,
23    },
24    cps::Compile,
25    exceptions::Exception,
26    gc::{Gc, Trace},
27    proc::{Application, DynamicState, Procedure},
28    runtime::Runtime,
29    symbols::Symbol,
30    syntax::{Identifier, Syntax},
31    value::{Cell, Value},
32};
33
34pub(crate) mod error {
35    use crate::exceptions::Message;
36
37    use super::*;
38
39    pub(crate) fn name_bound_multiple_times(name: Symbol) -> Exception {
40        Exception::from(Message::new(format!("`{name}` bound multiple times")))
41    }
42}
43
44#[derive(Clone)]
45pub(crate) enum TopLevelBinding {
46    Global(Global),
47    Keyword(Procedure),
48    Primitive(Primitive),
49}
50
51pub(crate) static TOP_LEVEL_BINDINGS: LazyLock<Mutex<HashMap<Binding, TopLevelBinding>>> =
52    LazyLock::new(|| Mutex::new(HashMap::new()));
53
54#[derive(Trace)]
55pub(crate) struct TopLevelEnvironmentInner {
56    pub(crate) rt: Runtime,
57    pub(crate) kind: TopLevelKind,
58    pub(crate) imports: HashMap<Binding, TopLevelEnvironment>,
59    pub(crate) exports: HashMap<Symbol, Export>,
60    pub(crate) state: LibraryState,
61    pub(crate) scope: Scope,
62}
63
64impl TopLevelEnvironmentInner {
65    pub(crate) fn new(
66        rt: &Runtime,
67        kind: TopLevelKind,
68        imports: HashMap<Binding, TopLevelEnvironment>,
69        exports: HashMap<Symbol, Symbol>,
70        scope: Scope,
71        body: Syntax,
72    ) -> Self {
73        let exports = exports
74            .into_iter()
75            .map(|(name, rename)| {
76                let binding = Identifier::from_symbol(name, scope).bind();
77                let origin = imports.get(&binding).cloned();
78                (rename, Export { binding, origin })
79            })
80            .collect();
81
82        Self {
83            rt: rt.clone(),
84            kind,
85            imports,
86            exports,
87            state: LibraryState::Unexpanded(body),
88            scope,
89        }
90    }
91}
92
93#[derive(Trace, Debug)]
94pub enum TopLevelKind {
95    /// A Repl is a library that does not have a name.
96    Repl,
97    /// A library has a name and an (optional) path.
98    Libary {
99        name: LibraryName,
100        path: Option<PathBuf>,
101    },
102    /// A program has a path
103    Program { path: PathBuf },
104}
105
106#[derive(Clone, Trace)]
107pub(crate) struct Import {
108    /// The original binding of the identifier before being renamed.
109    pub(crate) binding: Binding,
110    pub(crate) origin: TopLevelEnvironment,
111}
112
113#[derive(Trace, Clone)]
114pub(crate) struct Export {
115    pub(crate) binding: Binding,
116    pub(crate) origin: Option<TopLevelEnvironment>,
117}
118
119/// A top level environment such as a library, program, or REPL.
120#[derive(Trace, Clone)]
121pub struct TopLevelEnvironment(pub(crate) Gc<RwLock<TopLevelEnvironmentInner>>);
122
123impl PartialEq for TopLevelEnvironment {
124    fn eq(&self, rhs: &Self) -> bool {
125        Gc::ptr_eq(&self.0, &rhs.0)
126    }
127}
128
129impl TopLevelEnvironment {
130    pub fn new_repl(rt: &Runtime) -> Self {
131        let inner = TopLevelEnvironmentInner {
132            rt: rt.clone(),
133            kind: TopLevelKind::Repl,
134            exports: HashMap::new(),
135            imports: HashMap::new(),
136            state: LibraryState::Invoked,
137            scope: Scope::new(),
138        };
139        let repl = Self(Gc::new(RwLock::new(inner)));
140        // Repls are given the import keyword, free of charge.
141        repl.give_import_primitive();
142        repl
143    }
144
145    pub(crate) fn new_program(rt: &Runtime, path: &Path) -> Self {
146        let inner = TopLevelEnvironmentInner {
147            rt: rt.clone(),
148            kind: TopLevelKind::Program {
149                path: path.to_path_buf(),
150            },
151            exports: HashMap::new(),
152            imports: HashMap::new(),
153            state: LibraryState::Invoked,
154            scope: Scope::new(),
155        };
156        let program = Self(Gc::new(RwLock::new(inner)));
157        // Programs are given the import keyword, free of charge.
158        program.give_import_primitive();
159        program
160    }
161
162    fn give_import_primitive(&self) {
163        let kw = Symbol::intern("import");
164        let lib_name = [
165            Symbol::intern("rnrs"),
166            Symbol::intern("base"),
167            Symbol::intern("primitives"),
168        ];
169        let rnrs_base_prims = self
170            .0
171            .read()
172            .rt
173            .get_registry()
174            .0
175            .read()
176            .libs
177            .get(lib_name.as_slice())
178            .cloned()
179            .unwrap();
180        let import = rnrs_base_prims.0.read().exports.get(&kw).unwrap().clone();
181        let mut this = self.0.write();
182        this.imports.insert(import.binding, rnrs_base_prims.clone());
183        add_binding(Identifier::from_symbol(kw, this.scope), import.binding);
184    }
185
186    pub(crate) fn scope(&self) -> Scope {
187        self.0.read().scope
188    }
189
190    #[maybe_async]
191    pub fn from_spec(rt: &Runtime, spec: LibrarySpec, path: PathBuf) -> Result<Self, Exception> {
192        maybe_await!(Self::from_spec_with_scope(rt, spec, path, Scope::new()))
193    }
194
195    #[maybe_async]
196    pub(crate) fn from_spec_with_scope(
197        rt: &Runtime,
198        spec: LibrarySpec,
199        path: PathBuf,
200        library_scope: Scope,
201    ) -> Result<Self, Exception> {
202        let registry = rt.get_registry();
203
204        // Import libraries:
205        let mut bound_names = HashMap::<Symbol, Binding>::new();
206        let mut imports = HashMap::<Binding, TopLevelEnvironment>::new();
207
208        for lib_import in spec.imports.import_sets.into_iter() {
209            for (name, import) in maybe_await!(registry.import(rt, lib_import))? {
210                if let Some(prev_binding) = bound_names.get(&name)
211                    && prev_binding != &import.binding
212                {
213                    return Err(error::name_bound_multiple_times(name));
214                }
215                bound_names.insert(name, import.binding);
216                imports.insert(import.binding, import.origin);
217                // Bind the new identifier in the global symbol table:
218                add_binding(Identifier::from_symbol(name, library_scope), import.binding);
219            }
220        }
221
222        let mut exports = HashMap::new();
223        for export in spec.exports.export_sets.into_iter() {
224            match export {
225                ExportSet::Internal { rename, name } => {
226                    let rename = if let Some(rename) = rename {
227                        rename
228                    } else {
229                        name
230                    };
231                    exports.insert(name, rename);
232                }
233                ExportSet::External(lib_import) => {
234                    for lib_import in lib_import.import_sets.into_iter() {
235                        for (name, import) in maybe_await!(registry.import(rt, lib_import))? {
236                            if let Some(prev_binding) = bound_names.get(&name)
237                                && prev_binding != &import.binding
238                            {
239                                return Err(error::name_bound_multiple_times(name));
240                            }
241                            bound_names.insert(name, import.binding);
242                            imports.insert(import.binding, import.origin);
243                            // Bind the new identifier in the global symbol table:
244                            add_binding(
245                                Identifier::from_symbol(name, library_scope),
246                                import.binding,
247                            );
248                            exports.insert(name, name);
249                        }
250                    }
251                }
252            }
253        }
254
255        let mut body = spec.body;
256        body.add_scope(library_scope);
257
258        Ok(Self(Gc::new(RwLock::new(TopLevelEnvironmentInner::new(
259            rt,
260            TopLevelKind::Libary {
261                name: spec.name,
262                path: Some(path),
263            },
264            imports,
265            exports,
266            library_scope,
267            body,
268        )))))
269    }
270
271    pub(crate) fn get_kind(&self) -> MappedRwLockReadGuard<'_, TopLevelKind> {
272        RwLockReadGuard::map(self.0.read(), |inner| &inner.kind)
273    }
274
275    pub(crate) fn get_state(&self) -> MappedRwLockReadGuard<'_, LibraryState> {
276        RwLockReadGuard::map(self.0.read(), |inner| &inner.state)
277    }
278
279    /// Evaluate the scheme expression in the provided environment and return
280    /// the values. If `allow_imports` is false, import expressions are
281    /// disallowed and will cause an error.
282    #[maybe_async]
283    pub fn eval(&self, allow_imports: bool, code: &str) -> Result<Vec<Value>, Exception> {
284        let mut sexprs = Syntax::from_str(code, None)?;
285        sexprs.add_scope(self.0.read().scope);
286        let Some([body @ .., end]) = sexprs.as_list() else {
287            return Err(Exception::syntax(sexprs, None));
288        };
289        if !end.is_null() {
290            return Err(Exception::syntax(sexprs, None));
291        }
292        let rt = { self.0.read().rt.clone() };
293        let ctxt = ParseContext::new(&rt, allow_imports);
294        let body = maybe_await!(DefinitionBody::parse(
295            &ctxt,
296            body,
297            &Environment::Top(self.clone()),
298            &sexprs
299        ))?;
300        let compiled = maybe_await!(rt.compile_expr(body.compile_top_level()));
301        maybe_await!(Application::new(compiled, Vec::new()).eval(&mut DynamicState::new()))
302    }
303
304    #[maybe_async]
305    pub fn eval_sexpr(
306        &self,
307        allow_imports: bool,
308        mut sexpr: Syntax,
309    ) -> Result<Vec<Value>, Exception> {
310        let rt = { self.0.read().rt.clone() };
311        let ctxt = ParseContext::new(&rt, allow_imports);
312        sexpr.add_scope(self.0.read().scope);
313        let body = std::slice::from_ref(&sexpr);
314        let body = maybe_await!(DefinitionBody::parse(
315            &ctxt,
316            body,
317            &Environment::Top(self.clone()),
318            &sexpr
319        ))?;
320        let compiled = maybe_await!(rt.compile_expr(body.compile_top_level()));
321        maybe_await!(Application::new(compiled, Vec::new()).eval(&mut DynamicState::new()))
322    }
323
324    #[maybe_async]
325    pub fn import(&self, import_set: ImportSet) -> Result<(), Exception> {
326        let (rt, registry, scope) = {
327            let this = self.0.read();
328            (this.rt.clone(), this.rt.get_registry(), this.scope)
329        };
330        let imports = maybe_await!(registry.import(&rt, import_set))?;
331        let mut this = self.0.write();
332        for (sym, import) in imports {
333            match this.imports.entry(import.binding) {
334                Entry::Occupied(prev_imported) if *prev_imported.key() != import.binding => {
335                    return Err(error::name_bound_multiple_times(sym));
336                }
337                Entry::Vacant(slot) => {
338                    add_binding(Identifier::from_symbol(sym, scope), import.binding);
339                    slot.insert(import.origin);
340                }
341                _ => (),
342            }
343        }
344        Ok(())
345    }
346
347    #[maybe_async]
348    pub(crate) fn maybe_expand(&self) -> Result<(), Exception> {
349        let body = {
350            let mut this = self.0.write();
351            if let LibraryState::Unexpanded(body) = &mut this.state {
352                // std::mem::take(body)
353                body.clone()
354            } else {
355                return Ok(());
356            }
357        };
358        let rt = { self.0.read().rt.clone() };
359        let env = Environment::from(self.clone());
360        let expanded = maybe_await!(DefinitionBody::parse_lib_body(&rt, &body, &env))?;
361        self.0.write().state = LibraryState::Expanded(expanded);
362        Ok(())
363    }
364
365    #[maybe_async]
366    pub(crate) fn maybe_invoke(&self) -> Result<(), Exception> {
367        maybe_await!(self.maybe_expand())?;
368        let defn_body = {
369            let mut this = self.0.write();
370            match std::mem::replace(&mut this.state, LibraryState::Invalid) {
371                LibraryState::Expanded(defn_body) => defn_body,
372                x => {
373                    this.state = x;
374                    return Ok(());
375                }
376            }
377        };
378        let compiled = defn_body.compile_top_level();
379        let rt = { self.0.read().rt.clone() };
380        let proc = maybe_await!(rt.compile_expr(compiled));
381        let _ = maybe_await!(Application::new(proc, Vec::new()).eval(&mut DynamicState::new()))?;
382        self.0.write().state = LibraryState::Invoked;
383        Ok(())
384    }
385
386    pub fn is_repl(&self) -> bool {
387        matches!(self.0.read().kind, TopLevelKind::Repl)
388    }
389
390    pub fn def_var(&self, binding: Binding, name: Symbol, value: Value) -> Global {
391        let mutable = self
392            .0
393            .read()
394            .exports
395            .get(&name)
396            .map(|export| export.binding)
397            != Some(binding);
398        let mut top_level_binds = TOP_LEVEL_BINDINGS.lock();
399        match top_level_binds.entry(binding) {
400            Entry::Occupied(occup) => {
401                if let TopLevelBinding::Global(global) = occup.get().clone() {
402                    global
403                } else {
404                    unreachable!()
405                }
406            }
407            Entry::Vacant(vacant) => {
408                let global = Global::new(name, Cell::new(value), mutable, self.clone());
409                vacant.insert(TopLevelBinding::Global(global.clone()));
410                global
411            }
412        }
413    }
414
415    #[cfg(not(feature = "async"))]
416    pub fn lookup_var(&self, binding: Binding) -> Result<Option<Global>, Exception> {
417        self.lookup_var_inner(binding)
418    }
419
420    #[cfg(feature = "async")]
421    pub(crate) fn lookup_var(
422        &self,
423        binding: Binding,
424    ) -> BoxFuture<'_, Result<Option<Global>, Exception>> {
425        Box::pin(self.lookup_var_inner(binding))
426    }
427
428    #[maybe_async]
429    pub fn lookup_var_inner(&self, binding: Binding) -> Result<Option<Global>, Exception> {
430        if let Some(TopLevelBinding::Global(global)) =
431            { TOP_LEVEL_BINDINGS.lock().get(&binding).cloned() }
432        {
433            if *self != global.origin {
434                maybe_await!(global.origin.maybe_invoke())?;
435            }
436            Ok(Some(global.clone()))
437        } else {
438            Ok(None)
439        }
440    }
441
442    pub fn def_keyword(&self, binding: Binding, transformer: Procedure) {
443        TOP_LEVEL_BINDINGS
444            .lock()
445            .insert(binding, TopLevelBinding::Keyword(transformer));
446    }
447
448    #[cfg(not(feature = "async"))]
449    pub fn lookup_keyword(&self, binding: Binding) -> Result<Option<Procedure>, Exception> {
450        self.lookup_keyword_inner(binding)
451    }
452
453    #[cfg(feature = "async")]
454    pub(crate) fn lookup_keyword(
455        &self,
456        binding: Binding,
457    ) -> BoxFuture<'_, Result<Option<Procedure>, Exception>> {
458        Box::pin(self.lookup_keyword_inner(binding))
459    }
460
461    #[maybe_async]
462    pub fn lookup_keyword_inner(&self, binding: Binding) -> Result<Option<Procedure>, Exception> {
463        if let Some(origin) = { self.0.read().imports.get(&binding).cloned() } {
464            maybe_await!(origin.maybe_expand())?;
465            maybe_await!(origin.lookup_keyword(binding))
466        } else if let Some(TopLevelBinding::Keyword(kw)) = TOP_LEVEL_BINDINGS.lock().get(&binding) {
467            Ok(Some(kw.clone()))
468        } else {
469            Ok(None)
470        }
471    }
472
473    pub fn lookup_primitive(&self, binding: Binding) -> Option<Primitive> {
474        if let Some(TopLevelBinding::Primitive(primitive)) = TOP_LEVEL_BINDINGS.lock().get(&binding)
475        {
476            Some(*primitive)
477        } else {
478            None
479        }
480    }
481}
482
483impl fmt::Debug for TopLevelEnvironment {
484    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
485        write!(f, "%top")
486    }
487}
488
489// TODO: Use these states to detect circular dependencies when we do our DFS.
490// Or, alternatively, just handle circular dependencies like Guile does.
491#[derive(Trace, Debug)]
492pub(crate) enum LibraryState {
493    Invalid,
494    BridgesDefined,
495    Unexpanded(Syntax),
496    Expanded(DefinitionBody),
497    Invoked,
498}
499
500#[derive(Trace, PartialEq, Debug, Clone)]
501enum LocalBinding {
502    Var(Local),
503    Keyword(Procedure),
504    Pattern(Local, usize),
505    Imported(TopLevelEnvironment),
506}
507
508#[derive(Trace, Debug)]
509pub(crate) struct LexicalContour {
510    up: Environment,
511    bindings: Mutex<HashMap<Binding, LocalBinding>>,
512    scope: Scope,
513}
514
515impl LexicalContour {
516    fn def_var(&self, binding: Binding, name: Symbol) -> Local {
517        let local = Local::gensym_with_name(name);
518        self.bindings
519            .lock()
520            .insert(binding, LocalBinding::Var(local));
521        local
522    }
523
524    fn def_keyword(&self, binding: Binding, transformer: Procedure) {
525        self.bindings
526            .lock()
527            .insert(binding, LocalBinding::Keyword(transformer));
528    }
529
530    #[maybe_async]
531    fn lookup_keyword(&self, binding: Binding) -> Result<Option<Procedure>, Exception> {
532        if let Some(bound) = { self.bindings.lock().get(&binding).cloned() } {
533            match bound {
534                LocalBinding::Keyword(transformer) => Ok(Some(transformer.clone())),
535                LocalBinding::Imported(imported) => maybe_await!(imported.lookup_keyword(binding)),
536                _ => Ok(None),
537            }
538        } else {
539            maybe_await!(self.up.lookup_keyword(binding))
540        }
541    }
542
543    #[maybe_async]
544    fn lookup_var(&self, binding: Binding) -> Result<Option<Var>, Exception> {
545        if let Some(bound) = { self.bindings.lock().get(&binding).cloned() } {
546            match bound {
547                LocalBinding::Var(local) => Ok(Some(Var::Local(local))),
548                LocalBinding::Imported(imported) => {
549                    Ok(maybe_await!(imported.lookup_var(binding))?.map(Var::Global))
550                }
551                _ => Ok(None),
552            }
553        } else {
554            maybe_await!(self.up.lookup_var(binding))
555        }
556    }
557
558    fn lookup_primitive(&self, binding: Binding) -> Option<Primitive> {
559        if let Some(bound) = self.bindings.lock().get(&binding) {
560            match bound {
561                LocalBinding::Imported(imported) => imported.lookup_primitive(binding),
562                _ => None,
563            }
564        } else {
565            self.up.lookup_primitive(binding)
566        }
567    }
568
569    fn lookup_pattern_variable(&self, binding: Binding) -> Option<(Local, usize)> {
570        if let Some(bound) = self.bindings.lock().get(&binding) {
571            match bound {
572                LocalBinding::Pattern(local, depth) => Some((*local, *depth)),
573                _ => None,
574            }
575        } else {
576            self.up.lookup_pattern_variable(binding)
577        }
578    }
579
580    #[maybe_async]
581    pub fn import(&self, import_set: ImportSet) -> Result<(), Exception> {
582        let (rt, registry) = {
583            let top = self.fetch_top();
584            let top = top.0.read();
585            (top.rt.clone(), top.rt.get_registry())
586        };
587        let imports = maybe_await!(registry.import(&rt, import_set))?;
588        let mut bindings = self.bindings.lock();
589        for (sym, import) in imports {
590            let binding_type = LocalBinding::Imported(import.origin.clone());
591            match bindings.entry(import.binding) {
592                Entry::Occupied(prev_imported) if *prev_imported.key() != import.binding => {
593                    return Err(error::name_bound_multiple_times(sym));
594                }
595                Entry::Vacant(slot) => {
596                    add_binding(Identifier::from_symbol(sym, self.scope), import.binding);
597                    slot.insert(binding_type);
598                }
599                _ => (),
600            }
601        }
602        Ok(())
603    }
604
605    pub fn fetch_top(&self) -> TopLevelEnvironment {
606        self.up.fetch_top()
607    }
608}
609
610/// A lexical contour
611#[derive(Clone, Trace, Debug)]
612pub(crate) enum Environment {
613    Top(TopLevelEnvironment),
614    LexicalContour(Gc<LexicalContour>),
615}
616
617impl Environment {
618    pub fn new_lexical_contour(&self, scope: Scope) -> Self {
619        Self::LexicalContour(Gc::new(LexicalContour {
620            up: self.clone(),
621            bindings: Mutex::new(HashMap::new()),
622            scope,
623        }))
624    }
625
626    pub fn new_syntax_case_contour(
627        &self,
628        scope: Scope,
629        expansion: Local,
630        vars: HashMap<Binding, usize>,
631    ) -> Self {
632        Self::LexicalContour(Gc::new(LexicalContour {
633            up: self.clone(),
634            bindings: Mutex::new(
635                vars.into_iter()
636                    .map(|(binding, depth)| (binding, LocalBinding::Pattern(expansion, depth)))
637                    .collect(),
638            ),
639            scope,
640        }))
641    }
642
643    pub fn def_var(&self, binding: Binding, name: Symbol) -> Var {
644        match self {
645            Self::Top(top) => Var::Global(top.def_var(binding, name, Value::undefined())),
646            Self::LexicalContour(lc) => Var::Local(lc.def_var(binding, name)),
647        }
648    }
649
650    pub fn def_keyword(&self, binding: Binding, transformer: Procedure) {
651        match self {
652            Self::Top(top) => top.def_keyword(binding, transformer),
653            Self::LexicalContour(lc) => lc.def_keyword(binding, transformer),
654        }
655    }
656
657    #[cfg(not(feature = "async"))]
658    pub fn lookup_keyword(&self, binding: Binding) -> Result<Option<Procedure>, Exception> {
659        match self {
660            Self::Top(top) => top.lookup_keyword(binding),
661            Self::LexicalContour(lc) => lc.lookup_keyword(binding),
662        }
663    }
664
665    #[cfg(feature = "async")]
666    pub fn lookup_keyword(
667        &self,
668        binding: Binding,
669    ) -> BoxFuture<'_, Result<Option<Procedure>, Exception>> {
670        Box::pin(async move {
671            match self {
672                Self::Top(top) => top.lookup_keyword(binding).await,
673                Self::LexicalContour(lc) => lc.lookup_keyword(binding).await,
674            }
675        })
676    }
677
678    #[cfg(not(feature = "async"))]
679    pub fn lookup_var(&self, binding: Binding) -> Result<Option<Var>, Exception> {
680        match self {
681            Self::Top(top) => Ok(top.lookup_var(binding)?.map(Var::Global)),
682            Self::LexicalContour(lc) => lc.lookup_var(binding),
683        }
684    }
685
686    #[cfg(feature = "async")]
687    pub fn lookup_var(&self, binding: Binding) -> BoxFuture<'_, Result<Option<Var>, Exception>> {
688        Box::pin(async move {
689            match self {
690                Self::Top(top) => Ok(top.lookup_var(binding).await?.map(Var::Global)),
691                Self::LexicalContour(lc) => lc.lookup_var(binding).await,
692            }
693        })
694    }
695
696    pub fn get_scope_set(&self) -> BTreeSet<Scope> {
697        match self {
698            Self::Top(top) => BTreeSet::from([top.scope()]),
699            Self::LexicalContour(lc) => {
700                let mut up_scopes = lc.up.get_scope_set();
701                up_scopes.insert(lc.scope);
702                up_scopes
703            }
704        }
705    }
706
707    pub fn lookup_primitive(&self, binding: Binding) -> Option<Primitive> {
708        match self {
709            Self::Top(top) => top.lookup_primitive(binding),
710            Self::LexicalContour(lc) => lc.lookup_primitive(binding),
711        }
712    }
713
714    pub fn lookup_pattern_variable(&self, binding: Binding) -> Option<(Local, usize)> {
715        match self {
716            Self::Top(_) => None,
717            Self::LexicalContour(lc) => lc.lookup_pattern_variable(binding),
718        }
719    }
720
721    #[maybe_async]
722    pub fn import(&self, import_set: ImportSet) -> Result<(), Exception> {
723        match self {
724            Self::Top(top) => maybe_await!(top.import(import_set)),
725            Self::LexicalContour(lc) => maybe_await!(lc.import(import_set)),
726        }
727    }
728
729    pub fn fetch_top(&self) -> TopLevelEnvironment {
730        match self {
731            Self::Top(top) => top.clone(),
732            Self::LexicalContour(lc) => lc.fetch_top(),
733        }
734    }
735}
736
737impl From<TopLevelEnvironment> for Environment {
738    fn from(env: TopLevelEnvironment) -> Self {
739        Self::Top(env)
740    }
741}
742
743/// A local variable.
744#[derive(Copy, Clone, Trace)]
745pub struct Local {
746    pub(crate) id: usize,
747    pub(crate) name: Option<Symbol>,
748}
749
750impl Hash for Local {
751    fn hash<H>(&self, state: &mut H)
752    where
753        H: Hasher,
754    {
755        self.id.hash(state);
756    }
757}
758
759impl PartialEq for Local {
760    fn eq(&self, rhs: &Self) -> bool {
761        self.id == rhs.id
762    }
763}
764
765impl Eq for Local {}
766
767impl Local {
768    /// Create a new temporary value.
769    pub(crate) fn gensym() -> Self {
770        static NEXT_SYM: AtomicUsize = AtomicUsize::new(0);
771        Self {
772            id: NEXT_SYM.fetch_add(1, Ordering::Relaxed),
773            name: None,
774        }
775    }
776
777    pub(crate) fn gensym_with_name(name: Symbol) -> Self {
778        let mut sym = Self::gensym();
779        sym.name = Some(name);
780        sym
781    }
782
783    pub(crate) fn get_func_name(&self) -> String {
784        if let Some(name) = self.name {
785            format!("{name}")
786        } else {
787            format!("f{}", self.id)
788        }
789    }
790}
791
792impl fmt::Display for Local {
793    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
794        if let Some(name) = self.name {
795            write!(f, "{name}:${}", self.id)
796        } else {
797            write!(f, "%{}", self.id)
798        }
799    }
800}
801
802impl fmt::Debug for Local {
803    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
804        if let Some(name) = self.name {
805            write!(f, "{name}:${}", self.id)
806        } else {
807            write!(f, "%{}", self.id)
808        }
809    }
810}
811
812// TODO: Do we need to make this pointer eq?
813/// A global variable, i.e. a variable that is present in a top level
814/// environment.
815#[derive(Clone, Trace)]
816pub struct Global {
817    pub(crate) name: Symbol,
818    pub(crate) val: Cell,
819    pub(crate) mutable: bool,
820    pub(crate) origin: TopLevelEnvironment,
821}
822
823impl Global {
824    pub(crate) fn new(name: Symbol, val: Cell, mutable: bool, origin: TopLevelEnvironment) -> Self {
825        Global {
826            name,
827            val,
828            mutable,
829            origin,
830        }
831    }
832
833    pub fn is_mutable(&self) -> bool {
834        self.mutable
835    }
836
837    pub fn read(&self) -> Value {
838        self.val.0.read().clone()
839    }
840
841    pub fn set(&self, new: Value) -> Result<(), Exception> {
842        if !self.mutable {
843            return Err(Exception::error("cannot modify immutable variable"));
844        }
845        *self.val.0.write() = new;
846        Ok(())
847    }
848}
849
850impl fmt::Debug for Global {
851    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
852        write!(f, "${}", self.name)
853    }
854}
855
856impl PartialEq for Global {
857    fn eq(&self, rhs: &Self) -> bool {
858        Gc::ptr_eq(&self.val.0, &rhs.val.0)
859        /* self.name == rhs.name && */
860    }
861}
862
863impl Eq for Global {}
864
865impl Hash for Global {
866    fn hash<H>(&self, state: &mut H)
867    where
868        H: Hasher,
869    {
870        self.name.hash(state);
871        Gc::as_ptr(&self.val.0).hash(state);
872    }
873}
874
875#[derive(Clone, Trace, Hash, PartialEq, Eq)]
876pub(crate) enum Var {
877    Global(Global),
878    Local(Local),
879}
880
881impl Var {
882    pub fn symbol(&self) -> Option<Symbol> {
883        match self {
884            Var::Global(global) => Some(global.name),
885            Var::Local(local) => local.name,
886        }
887    }
888
889    pub fn as_local(&self) -> Option<Local> {
890        match self {
891            Self::Global(_) => None,
892            Self::Local(local) => Some(*local),
893        }
894    }
895}
896
897impl fmt::Debug for Var {
898    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
899        match self {
900            Self::Global(global) => global.fmt(f),
901            Self::Local(local) => local.fmt(f),
902        }
903    }
904}
905
906/// A scope uniquely identifies a lexical contour and is used for binding
907/// resolution.
908#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Trace)]
909pub struct Scope(usize);
910
911impl fmt::Debug for Scope {
912    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
913        write!(f, "%{}", self.0)
914    }
915}
916
917impl Scope {
918    /// Generates a new unique scope.
919    pub fn new() -> Self {
920        static NEXT_SCOPE: AtomicUsize = AtomicUsize::new(0);
921
922        Self(NEXT_SCOPE.fetch_add(1, Ordering::Relaxed))
923    }
924}
925
926impl Default for Scope {
927    fn default() -> Self {
928        Self::new()
929    }
930}
931
932#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Trace)]
933pub struct Binding(usize);
934
935impl Binding {
936    pub fn new() -> Self {
937        static NEXT_LOC: AtomicUsize = AtomicUsize::new(0);
938
939        Self(NEXT_LOC.fetch_add(1, Ordering::Relaxed))
940    }
941}
942
943impl Default for Binding {
944    fn default() -> Self {
945        Self::new()
946    }
947}
948
949impl fmt::Debug for Binding {
950    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
951        write!(f, "!{}", self.0)
952    }
953}
954
955type Bindings = Vec<(BTreeSet<Scope>, Binding)>;
956
957// We can probably design this much more intelligently
958pub(crate) static GLOBAL_BINDING_TABLE: LazyLock<Mutex<HashMap<Symbol, Bindings>>> =
959    LazyLock::new(|| Mutex::new(HashMap::new()));
960
961pub(crate) fn add_binding(id: Identifier, binding: Binding) {
962    GLOBAL_BINDING_TABLE
963        .lock()
964        .entry(id.sym)
965        .or_default()
966        .push((id.scopes, binding));
967}
968
969pub(crate) fn resolve(id: &Identifier) -> Option<Binding> {
970    let candidate_ids = find_all_matching_bindings(id);
971    let max_id = candidate_ids
972        .iter()
973        .max_by(|a, b| a.0.len().cmp(&b.0.len()))?;
974    if is_ambiguous(&max_id.0, &candidate_ids) {
975        return None;
976    }
977    Some(max_id.1)
978}
979
980fn is_ambiguous(max_id: &BTreeSet<Scope>, candidates: &[(BTreeSet<Scope>, Binding)]) -> bool {
981    for candidate in candidates {
982        if !candidate.0.is_subset(max_id) {
983            return true;
984        }
985    }
986    false
987}
988
989fn find_all_matching_bindings(id: &Identifier) -> Vec<(BTreeSet<Scope>, Binding)> {
990    GLOBAL_BINDING_TABLE
991        .lock()
992        .get(&id.sym)
993        .map_or_else(Vec::new, |vec| {
994            vec.iter()
995                .filter(|(scopes, _)| scopes.is_subset(&id.scopes))
996                .cloned()
997                .collect()
998        })
999}
scheme_rs/env.rs

scheme_rs/
env.rs
