From 51dcf19eb6f8d2127f3dedfc1d7d5326d7a8017b Mon Sep 17 00:00:00 2001
From: Greg Brown <gmb60@cam.ac.uk>
Date: Tue, 27 Apr 2021 13:07:27 +0100
Subject: Start rewrite using query system.

---
 src/chomp/mod.rs | 188 ++++++++++++++++++++++++++++++-------------------------
 1 file changed, 101 insertions(+), 87 deletions(-)

(limited to 'src/chomp/mod.rs')

diff --git a/src/chomp/mod.rs b/src/chomp/mod.rs
index 79b4fac..c8c82ae 100644
--- a/src/chomp/mod.rs
+++ b/src/chomp/mod.rs
@@ -1,114 +1,128 @@
-use std::{fmt, hash};
+use std::{collections::HashMap, rc::Rc};
 
-use heck::{CamelCase, SnakeCase};
-use proc_macro2::{Ident, Span};
-use syn::ext::IdentExt;
+use intern::Intern;
 
-pub mod ast;
-pub mod set;
-pub mod typed;
-pub mod visit;
+use self::ast::Lambda;
 
-#[derive(Clone, Debug)]
-pub enum Name {
-    Spanned(Ident),
-    Spanless(String),
+mod ast;
+mod cst;
+mod intern;
+mod typed;
+
+type SubstTriple = (Intern<ast::Tree>, Intern<ast::Tree>, Intern<ast::Tree>);
+
+#[derive(Debug)]
+pub struct Context {
+    // Abstract tree interning
+    var_stack: Vec<Rc<ast::Tree>>,
+    pub tree_interner: intern::TreeInterner,
+    pub type_interner: intern::TypeInterner,
+
+    // Caches
+    as_tree: HashMap<Intern<cst::Shape>, Rc<ast::Tree>>,
+    substitute: HashMap<SubstTriple, Option<Rc<ast::Tree>>>,
+    translate: HashMap<Intern<ast::Tree>, Result<Option<Rc<ast::Tree>>, ast::TranslateError>>,
+    type_of: HashMap<
+        Intern<ast::Tree>,
+        Result<typed::ConstrainedType, typed::TypeError>,
+    >,
 }
 
-impl Name {
-    pub fn span(&self) -> Option<Span> {
-        match self {
-            Self::Spanned(i) => Some(i.span()),
-            Self::Spanless(_) => None,
+impl Context {
+    /// Converts a concrete syntax tree into an abstract one.
+    pub fn as_tree(&mut self, shape: &Rc<cst::Shape>) -> Rc<ast::Tree> {
+        if let Some(tree) = self.as_tree.get(&shape.clone().into()) {
+            return tree.clone();
         }
+        let tree = cst::as_tree(self, shape);
+        self.as_tree.insert(shape.clone().into(), tree.clone());
+        tree
     }
 
-    pub fn into_ident(self, span: Span) -> Ident {
-        match self {
-            Self::Spanned(i) => i,
-            Self::Spanless(s) => Ident::new(&s, span),
+    /// Creates a copy of `tree` that replaces variables pointing to `from` with `into`.
+    pub fn substitute(
+        &mut self,
+        tree: &Rc<ast::Tree>,
+        from: &Rc<ast::Tree>,
+        into: &Rc<ast::Tree>,
+    ) -> Option<Rc<ast::Tree>> {
+        if let Some(tree) = self.substitute.get(&(
+            tree.clone().into(),
+            from.clone().into(),
+            into.clone().into(),
+        )) {
+            return tree.clone();
         }
+        let out = ast::substitute(self, tree, from, into);
+        self.substitute.insert(
+            (
+                tree.clone().into(),
+                from.clone().into(),
+                into.clone().into(),
+            ),
+            out.clone(),
+        );
+        out
     }
-}
 
-impl CamelCase for Name {
-    fn to_camel_case(&self) -> Self::Owned {
-        match self {
-            Self::Spanned(ident) => {
-                let span = ident.span();
-                let name = ident.unraw().to_string();
-                Ident::new(&name.to_camel_case(), span).into()
-            }
-            Name::Spanless(name) => {
-                name.to_camel_case().into()
-            }
+    /// Expands let bindings and function calls until the top level construct is a base term.
+    pub fn translate(
+        &mut self,
+        tree: &Rc<ast::Tree>,
+    ) -> Result<Option<Rc<ast::Tree>>, ast::TranslateError> {
+        if let Some(tree) = self.translate.get(&tree.clone().into()) {
+            return tree.clone();
         }
+        let out = ast::translate(self, tree);
+        self.translate.insert(tree.clone().into(), out.clone());
+        out
     }
-}
 
-impl SnakeCase for Name {
-    fn to_snake_case(&self) -> Self::Owned {
-        match self {
-            Self::Spanned(ident) => {
-                let span = ident.span();
-                let name = ident.unraw().to_string();
-                Ident::new(&name.to_snake_case(), span).into()
-            }
-            Name::Spanless(name) => {
-                name.to_snake_case().into()
-            }
+    /// Computes set of unsolvable type constraints for a term. Returns an error
+    /// if a solvable constraint is unsatisfiable, or the constraints cannot be inferred.
+    pub fn type_of(
+        &mut self,
+        tree: &Rc<ast::Tree>,
+    ) -> Result<typed::ConstrainedType, typed::TypeError> {
+        if let Some(ty) = self.type_of.get(&tree.clone().into()) {
+            return ty.clone();
         }
+        let ty = typed::type_of(self, tree);
+        self.type_of.insert(tree.clone().into(), ty.clone());
+        ty
     }
-}
 
-impl PartialEq for Name {
-    fn eq(&self, other: &Self) -> bool {
-        match (self, other) {
-            (Self::Spanned(me), Self::Spanned(them)) => me == them,
-            (Self::Spanned(me), Self::Spanless(them)) => me.unraw() == them,
-            (Self::Spanless(me), Self::Spanned(them)) => them.unraw() == me,
-            (Self::Spanless(me), Self::Spanless(them)) => me == them,
-        }
+    fn lookup_tree_variable(&self, idx: usize) -> Rc<ast::Tree> {
+        self.var_stack[idx].clone()
     }
-}
 
-impl<T: AsRef<str>> PartialEq<T> for Name {
-    fn eq(&self, other: &T) -> bool {
-        match self {
-            Name::Spanned(me) => me.unraw() == other,
-            Name::Spanless(me) => me == other.as_ref(),
-        }
-    }
-}
+    fn new_lambda<F: FnOnce(&mut Self) -> Rc<ast::Tree>>(&mut self, f: F) -> Rc<ast::Tree> {
+        // Create variable node
+        let arg = Rc::new(ast::Tree::Variable);
 
-impl Eq for Name {}
+        // Apply inner with the variable
+        self.var_stack.push(arg.clone());
+        let inner = f(self);
+        self.var_stack.pop();
 
-impl hash::Hash for Name {
-    fn hash<H: hash::Hasher>(&self, state: &mut H) {
-        match self {
-            Self::Spanned(i) => i.unraw().to_string().hash(state),
-            Self::Spanless(s) => s.hash(state),
-        }
+        // Create the lambda
+        Rc::new(ast::Tree::Lambda(Lambda(arg, inner)))
     }
-}
 
-impl fmt::Display for Name {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match self {
-            Name::Spanned(i) => i.fmt(f),
-            Name::Spanless(s) => s.fmt(f),
-        }
-    }
-}
+    fn new_let<F: FnOnce(&mut Self) -> Rc<ast::Tree>>(
+        &mut self,
+        bind: Rc<ast::Tree>,
+        inner: F,
+    ) -> Rc<ast::Tree> {
+        // Create variable node
+        let arg = Rc::new(ast::Tree::Variable);
 
-impl From<Ident> for Name {
-    fn from(ident: Ident) -> Self {
-        Self::Spanned(ident)
-    }
-}
+        // Apply inner with the variable
+        self.var_stack.push(arg.clone());
+        let inner = inner(self);
+        self.var_stack.pop();
 
-impl From<String> for Name {
-    fn from(string: String) -> Self {
-        Self::Spanless(string)
+        // Create the let
+        Rc::new(ast::Tree::Let(bind, arg, inner))
     }
 }
-- 
cgit v1.2.3