From dfc08ff2c6580bbeb3951b223e0332546ba3b0d9 Mon Sep 17 00:00:00 2001
From: Greg Brown <gmb60@cam.ac.uk>
Date: Thu, 6 May 2021 19:40:59 +0100
Subject: Introduce lambda expressions.

---
 src/nibble/convert.rs | 133 ++++++++++++++++++-------
 src/nibble/mod.rs     | 269 +++++++++++++++++++++-----------------------------
 2 files changed, 207 insertions(+), 195 deletions(-)

(limited to 'src/nibble')

diff --git a/src/nibble/convert.rs b/src/nibble/convert.rs
index e5e8c5d..ca6c95a 100644
--- a/src/nibble/convert.rs
+++ b/src/nibble/convert.rs
@@ -1,18 +1,18 @@
 use std::{fmt, mem};
 
 use proc_macro2::Span;
-use syn::{punctuated::Pair, Token};
+use syn::{punctuated::Pair, spanned::Spanned, Token};
 
-use crate::chomp::{
-    ast::{self, NamedExpression},
-    Name,
-};
+use crate::chomp::{ast::{self, NamedExpression}, name::{Content, Name}};
 
-use super::{Alt, Call, Cat, Expression, Fix, Ident, Labelled, Lambda, ParenExpression, Term};
+use super::{
+    Alt, Call, Cat, Expression, Fix, GoalStatement, Ident, Labelled, Lambda, LetStatement,
+    ParenExpression, Statement, Term,
+};
 
 #[derive(Debug, Default)]
 pub struct Context {
-    bindings: Vec<Name>,
+    bindings: Vec<Content>,
 }
 
 impl Context {
@@ -20,20 +20,24 @@ impl Context {
         Self::default()
     }
 
+    /// Get the De Bruijn index of `name`, if it is defined.
     pub fn lookup(&self, name: &Name) -> Option<usize> {
         self.bindings
             .iter()
+            .rev()
             .enumerate()
-            .rfind(|(_, n)| *n == name)
+            .find(|(_, n)| *n == &name.content)
             .map(|(idx, _)| idx)
     }
 
+    /// Permanently add the variable `name` to the top of the stack.
     pub fn push_variable(&mut self, name: Name) {
-        self.bindings.push(name);
+        self.bindings.push(name.content);
     }
 
+    /// Call `f` with the variable `name` pushed to the top of the stack.
     pub fn with_variable<F: FnOnce(&mut Self) -> R, R>(&mut self, name: Name, f: F) -> R {
-        self.bindings.push(name);
+        self.bindings.push(name.content);
         let res = f(self);
         self.bindings.pop();
         res
@@ -45,7 +49,7 @@ impl Context {
         f: F,
     ) -> R {
         let len = self.bindings.len();
-        self.bindings.extend(names);
+        self.bindings.extend(names.into_iter().map(|n| n.content));
         let res = f(self);
         self.bindings.resize_with(len, || unreachable!());
         res
@@ -55,10 +59,9 @@ impl Context {
 #[derive(Clone, Debug)]
 pub enum ConvertError {
     UndeclaredName(Box<Name>),
-    EmptyCat(Option<Span>),
-    EmptyAlt(Option<Span>),
-    EmptyCall(Option<Span>),
-    MissingArgs(Option<Span>),
+    EmptyCat(Span),
+    EmptyAlt(Span),
+    EmptyCall(Span),
 }
 
 impl From<ConvertError> for syn::Error {
@@ -68,11 +71,10 @@ impl From<ConvertError> for syn::Error {
             ConvertError::UndeclaredName(name) => name.span(),
             ConvertError::EmptyCat(span)
             | ConvertError::EmptyAlt(span)
-            | ConvertError::EmptyCall(span)
-            | ConvertError::MissingArgs(span) => span,
+            | ConvertError::EmptyCall(span) => span,
         };
 
-        Self::new(span.unwrap_or_else(Span::call_site), msg)
+        Self::new(span, msg)
     }
 }
 
@@ -91,9 +93,6 @@ impl fmt::Display for ConvertError {
             Self::EmptyCall(_) => {
                 write!(f, "call has no function")
             }
-            Self::MissingArgs(_) => {
-                write!(f, "call has no arguments")
-            }
         }
     }
 }
@@ -106,8 +105,8 @@ pub trait Convert {
 
 impl Convert for Ident {
     fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
-        let span = Some(self.span());
-        let name = self.into();
+        let span = self.span();
+        let name = Name::new_variable(self);
 
         let index = context
             .lookup(&name)
@@ -148,13 +147,13 @@ impl Convert for Term {
             Self::Epsilon(e) => Ok(NamedExpression {
                 name: None,
                 expr: ast::Epsilon.into(),
-                span: Some(e.span),
+                span: e.span,
             }),
             Self::Ident(i) => i.convert(context),
             Self::Literal(l) => Ok(NamedExpression {
                 name: None,
                 expr: l.value().into(),
-                span: Some(l.span()),
+                span: l.span(),
             }),
             Self::Fix(f) => f.convert(context),
             Self::Parens(p) => p.convert(context),
@@ -168,13 +167,13 @@ impl Convert for Call {
         let mut iter = self.0.into_iter();
         let on = iter
             .next()
-            .ok_or_else(|| ConvertError::EmptyCall(span))?
+            .ok_or(ConvertError::EmptyCall(span))?
             .convert(context)?;
         let args = iter
             .map(|arg| arg.convert(context))
             .collect::<Result<Vec<_>, _>>()?;
         if args.is_empty() {
-            Err(ConvertError::MissingArgs(span))
+            Ok(on)
         } else {
             Ok(NamedExpression {
                 name: None,
@@ -194,10 +193,10 @@ impl Convert for Cat {
         fn convert_pair(
             pair: Pair<Call, Token![.]>,
             context: &mut Context,
-        ) -> Result<(NamedExpression, Option<Span>), ConvertError> {
+        ) -> Result<(NamedExpression, Span), ConvertError> {
             match pair {
-                Pair::Punctuated(t, p) => t.convert(context).map(|expr| (expr, Some(p.span))),
-                Pair::End(t) => t.convert(context).map(|expr| (expr, None)),
+                Pair::Punctuated(t, p) => t.convert(context).map(|expr| (expr, p.span)),
+                Pair::End(t) => t.convert(context).map(|expr| (expr, Span::call_site())),
             }
         }
 
@@ -215,7 +214,7 @@ impl Convert for Cat {
             })
             .peekable();
 
-        if let Some(_) = rest.peek() {
+        if rest.peek().is_some() {
             Ok(NamedExpression {
                 name: None,
                 expr: ast::Cat {
@@ -235,7 +234,8 @@ impl Convert for Labelled {
     fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
         let span = self.span();
         let named = self.cat.convert(context)?;
-        let name = self.label.map(|l| l.label.into()).or(named.name);
+        let label = self.label.map(|l| Name::new_label(l.label));
+        let name = Name::merge(label, named.name);
 
         Ok(NamedExpression {
             name,
@@ -250,10 +250,10 @@ impl Convert for Alt {
         fn convert_pair(
             pair: Pair<Labelled, Token![|]>,
             context: &mut Context,
-        ) -> Result<(NamedExpression, Option<Span>), ConvertError> {
+        ) -> Result<(NamedExpression, Span), ConvertError> {
             match pair {
-                Pair::Punctuated(t, p) => t.convert(context).map(|expr| (expr, Some(p.span))),
-                Pair::End(t) => t.convert(context).map(|expr| (expr, None)),
+                Pair::Punctuated(t, p) => t.convert(context).map(|expr| (expr, p.span)),
+                Pair::End(t) => t.convert(context).map(|expr| (expr, Span::call_site())),
             }
         }
 
@@ -271,7 +271,7 @@ impl Convert for Alt {
             })
             .peekable();
 
-        if let Some(_) = rest.peek() {
+        if rest.peek().is_some() {
             Ok(NamedExpression {
                 name: None,
                 expr: ast::Alt {
@@ -290,7 +290,7 @@ impl Convert for Alt {
 impl Convert for Lambda {
     fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
         let span = self.span();
-        let mut args: Vec<_> = self.args.into_iter().map(Name::from).collect();
+        let args: Vec<_> = self.args.into_iter().map(Name::new_variable).collect();
         let expr = self.expr;
         let inner = context.with_variables(args.clone(), |ctx| expr.convert(ctx))?;
         Ok(NamedExpression {
@@ -313,3 +313,62 @@ impl Convert for Expression {
         }
     }
 }
+
+impl Convert for GoalStatement {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
+        let span = self.span();
+        let inner = self.expr.convert(context)?;
+        Ok(NamedExpression {
+            name: Name::merge(inner.name, Some(Name::new_variable("Ast".to_owned()))),
+            expr: inner.expr,
+            span,
+        })
+    }
+}
+
+impl Convert for LetStatement {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
+        let span = self.span();
+        let bound = if self.args.is_empty() {
+            self.expr.convert(context)?
+        } else {
+            let args: Vec<_> = self.args.into_iter().map(Name::new_variable).collect();
+            let expr = self.expr;
+            let inner = context.with_variables(args.clone(), |ctx| expr.convert(ctx))?;
+            NamedExpression {
+                name: None,
+                expr: ast::Lambda {
+                    args,
+                    inner: Box::new(inner),
+                }
+                .into(),
+                span,
+            }
+        };
+        let name = Name::new_let(self.name);
+        context.push_variable(name.clone());
+        let body = self.next.convert(context)?;
+        Ok(NamedExpression {
+            name: None,
+            expr: ast::Let {
+                name: name.clone(),
+                bound: Box::new(NamedExpression {
+                    name: Some(name),
+                    ..bound
+                }),
+                body: Box::new(body),
+            }
+            .into(),
+            span,
+        })
+    }
+}
+
+impl Convert for Statement {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
+        match self {
+            Self::Goal(g) => g.convert(context),
+            Self::Let(l) => l.convert(context),
+        }
+    }
+}
diff --git a/src/nibble/mod.rs b/src/nibble/mod.rs
index dbb05b0..f5417db 100644
--- a/src/nibble/mod.rs
+++ b/src/nibble/mod.rs
@@ -2,82 +2,33 @@ pub mod convert;
 
 use std::fmt;
 
-use proc_macro2::Span;
+use proc_macro2::TokenStream;
+use quote::{ToTokens, TokenStreamExt};
 use syn::{
-    bracketed,
     ext::IdentExt,
     parenthesized,
     parse::{Parse, ParseStream},
-    punctuated::{Pair, Punctuated},
-    token::{Bracket, Comma, Let, Match, Paren},
+    punctuated::Punctuated,
+    token::{Let, Match, Paren},
     LitStr, Token,
 };
 
-use crate::chomp::{Name, ast::{self, TopLevel}};
-
-use convert::{Context, Convert, ConvertError};
-
 pub type Epsilon = Token![_];
 
 pub type Ident = syn::Ident;
 
 pub type Literal = LitStr;
 
-#[derive(Clone)]
-pub struct ArgList<T> {
-    paren_token: Paren,
-    args: Punctuated<T, Comma>,
-}
-
-impl<T> ArgList<T> {
-    pub fn span(&self) -> Span {
-        self.paren_token.span
-    }
-
-    pub fn len(&self) -> usize {
-        self.args.len()
-    }
-
-    pub fn is_empty(&self) -> bool {
-        self.args.is_empty()
-    }
-}
-
-impl<T> IntoIterator for ArgList<T> {
-    type Item = T;
-
-    type IntoIter = <Punctuated<T, Comma> as IntoIterator>::IntoIter;
-
-    fn into_iter(self) -> Self::IntoIter {
-        self.args.into_iter()
-    }
-}
-
-impl<T: Parse> Parse for ArgList<T> {
-    fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
-        let args;
-        let paren_token = parenthesized!(args in input);
-        let args = args.call(Punctuated::parse_terminated)?;
-        Ok(Self { paren_token, args })
-    }
-}
-
-impl<T: fmt::Debug> fmt::Debug for ArgList<T> {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "ArgList")?;
-        f.debug_list().entries(self.args.iter()).finish()
-    }
-}
-
 #[derive(Clone)]
 pub struct Fix {
     bang_token: Token![!],
     pub expr: Box<Term>,
 }
 
-impl Fix {
-    pub fn span(&self) -> Option<Span> {
-        self.bang_token.span.join(self.expr.span()?)
+impl ToTokens for Fix {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.bang_token.to_tokens(tokens);
+        self.expr.to_tokens(tokens);
     }
 }
 
@@ -101,6 +52,12 @@ pub struct ParenExpression {
     pub expr: Expression,
 }
 
+impl ToTokens for ParenExpression {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.paren_token.surround(tokens, |tokens| self.expr.to_tokens(tokens))
+    }
+}
+
 impl Parse for ParenExpression {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
         let expr;
@@ -127,14 +84,14 @@ pub enum Term {
     Parens(ParenExpression),
 }
 
-impl Term {
-    pub fn span(&self) -> Option<Span> {
+impl ToTokens for Term {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
         match self {
-            Self::Epsilon(e) => Some(e.span),
-            Self::Ident(i) => Some(i.span()),
-            Self::Literal(l) => Some(l.span()),
-            Self::Fix(f) => f.span(),
-            Self::Parens(p) => Some(p.paren_token.span),
+            Self::Epsilon(e) => e.to_tokens(tokens),
+            Self::Ident(i) => i.to_tokens(tokens),
+            Self::Literal(l) => l.to_tokens(tokens),
+            Self::Fix(f) => f.to_tokens(tokens),
+            Self::Parens(p) => p.to_tokens(tokens),
         }
     }
 }
@@ -174,18 +131,15 @@ impl fmt::Debug for Term {
 #[derive(Clone, Debug)]
 pub struct Call(pub Vec<Term>);
 
-impl Call {
-    pub fn span(&self) -> Option<Span> {
-        let mut iter = self.0.iter();
-        let first = iter.next()?.span()?;
-        iter.try_fold(first, |span, t| t.span().and_then(|s| span.join(s)))
+impl ToTokens for Call {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        tokens.append_all(&self.0)
     }
 }
 
 impl Parse for Call {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
-        let mut out = Vec::new();
-        out.push(input.parse()?);
+        let mut out = vec![input.parse()?];
         loop {
             let lookahead = input.lookahead1();
             if lookahead.peek(Token![_])
@@ -207,34 +161,22 @@ impl Parse for Call {
 #[derive(Clone)]
 pub struct Cat(pub Punctuated<Call, Token![.]>);
 
-impl Parse for Cat {
-    fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
-        input.call(Punctuated::parse_separated_nonempty).map(Self)
+impl ToTokens for Cat {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.0.to_tokens(tokens)
     }
 }
 
-impl Cat {
-    pub fn span(&self) -> Option<Span> {
-        let mut iter = self.0.pairs();
-        let span = match iter.next()? {
-            Pair::Punctuated(t, p) => t.span().and_then(|s| s.join(p.span)),
-            Pair::End(t) => t.span(),
-        }?;
-
-        iter.try_fold(span, |span, pair| match pair {
-            Pair::Punctuated(t, p) => t
-                .span()
-                .and_then(|s| span.join(s))
-                .and_then(|s| s.join(p.span)),
-            Pair::End(t) => t.span().and_then(|s| span.join(s)),
-        })
+impl Parse for Cat {
+    fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
+        input.call(Punctuated::parse_separated_nonempty).map(Self)
     }
 }
 
 impl fmt::Debug for Cat {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "Cat")?;
-        f.debug_list().entries(self.0.iter()).finish()
+        f.debug_list().entries(&self.0).finish()
     }
 }
 
@@ -244,9 +186,10 @@ pub struct Label {
     pub label: Ident,
 }
 
-impl Label {
-    pub fn span(&self) -> Option<Span> {
-        self.colon_tok.span.join(self.label.span())
+impl ToTokens for Label {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.colon_tok.to_tokens(tokens);
+        self.label.to_tokens(tokens);
     }
 }
 
@@ -270,13 +213,12 @@ pub struct Labelled {
     pub label: Option<Label>,
 }
 
-impl Labelled {
-    pub fn span(&self) -> Option<Span> {
-        self.cat.span().and_then(|s| {
-            self.label
-                .as_ref()
-                .and_then(|l| l.span().and_then(|t| s.join(t)))
-        })
+impl ToTokens for Labelled {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.cat.to_tokens(tokens);
+        if let Some(label) = &self.label {
+            label.to_tokens(tokens);
+        }
     }
 }
 
@@ -295,21 +237,9 @@ impl Parse for Labelled {
 #[derive(Clone)]
 pub struct Alt(pub Punctuated<Labelled, Token![|]>);
 
-impl Alt {
-    pub fn span(&self) -> Option<Span> {
-        let mut iter = self.0.pairs();
-        let span = match iter.next()? {
-            Pair::Punctuated(t, p) => t.span().and_then(|s| s.join(p.span)),
-            Pair::End(t) => t.span(),
-        }?;
-
-        iter.try_fold(span, |span, pair| match pair {
-            Pair::Punctuated(t, p) => t
-                .span()
-                .and_then(|s| span.join(s))
-                .and_then(|s| s.join(p.span)),
-            Pair::End(t) => t.span().and_then(|s| span.join(s)),
-        })
+impl ToTokens for Alt {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.0.to_tokens(tokens)
     }
 }
 
@@ -322,27 +252,40 @@ impl Parse for Alt {
 impl fmt::Debug for Alt {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "Alt")?;
-        f.debug_list().entries(self.0.iter()).finish()
+        f.debug_list().entries(&self.0).finish()
     }
 }
 #[derive(Clone)]
 pub struct Lambda {
     slash_tok_left: Token![/],
-    pub args: ArgList<Ident>,
+    pub args: Vec<Ident>,
     slash_tok_right: Token![/],
     pub expr: Alt,
 }
 
-impl Lambda {
-    pub fn span(&self) -> Option<Span> {
-        self.slash_tok_left.span.join(self.expr.span()?)
+impl ToTokens for Lambda {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.slash_tok_left.to_tokens(tokens);
+        tokens.append_all(&self.args);
+        self.slash_tok_right.to_tokens(tokens);
+        self.expr.to_tokens(tokens);
     }
 }
 
 impl Parse for Lambda {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
         let slash_tok_left = input.parse()?;
-        let args = input.parse()?;
+        let mut args = Vec::new();
+        loop {
+            args.push(input.parse()?);
+            let lookahead = input.lookahead1();
+
+            if lookahead.peek(Token![/]) {
+                break;
+            } else if !lookahead.peek(Ident::peek_any) {
+                return Err(lookahead.error());
+            }
+        }
         let slash_tok_right = input.parse()?;
         let expr = input.parse()?;
         Ok(Self {
@@ -369,6 +312,15 @@ pub enum Expression {
     Lambda(Lambda),
 }
 
+impl ToTokens for Expression {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        match self {
+            Self::Alt(a) => a.to_tokens(tokens),
+            Self::Lambda(l) => l.to_tokens(tokens),
+        }
+    }
+}
+
 impl Parse for Expression {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
         if input.peek(Token![/]) {
@@ -386,6 +338,14 @@ pub struct GoalStatement {
     semi_token: Token![;],
 }
 
+impl ToTokens for GoalStatement {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.match_token.to_tokens(tokens);
+        self.expr.to_tokens(tokens);
+        self.semi_token.to_tokens(tokens);
+    }
+}
+
 impl Parse for GoalStatement {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
         let match_token = input.parse()?;
@@ -412,22 +372,40 @@ impl fmt::Debug for GoalStatement {
 pub struct LetStatement {
     let_token: Token![let],
     name: Ident,
-    args: Option<ArgList<Ident>>,
+    args: Vec<Ident>,
     eq_token: Token![=],
     expr: Expression,
     semi_token: Token![;],
     next: Box<Statement>,
 }
 
+impl ToTokens for LetStatement {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        self.let_token.to_tokens(tokens);
+        self.name.to_tokens(tokens);
+        tokens.append_all(&self.args);
+        self.eq_token.to_tokens(tokens);
+        self.expr.to_tokens(tokens);
+        self.semi_token.to_tokens(tokens);
+        self.next.to_tokens(tokens);
+    }
+}
+
 impl Parse for LetStatement {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
         let let_token = input.parse()?;
         let name = input.call(Ident::parse_any)?;
-        let args = if input.peek(Paren) {
-            Some(input.parse()?)
-        } else {
-            None
-        };
+        let mut args = Vec::new();
+        loop {
+            let lookahead = input.lookahead1();
+            if lookahead.peek(Token![=]) {
+                break;
+            } else if lookahead.peek(Ident::peek_any) {
+                args.push(input.parse()?);
+            } else {
+                return Err(lookahead.error());
+            }
+        }
         let eq_token = input.parse()?;
         let expr = input.parse()?;
         let semi_token = input.parse()?;
@@ -462,43 +440,18 @@ pub enum Statement {
     Let(LetStatement),
 }
 
-impl Statement {
-    pub fn convert(self) -> Result<TopLevel, ConvertError> {
-        let mut stmt = self;
-        let mut context = Context::new();
-        let mut name_val = Vec::new();
-        while let Self::Let(let_stmt) = stmt {
-            let mut val = match let_stmt.args {
-                Some(args) => {
-                    todo!()
-                }
-                None => let_stmt.expr.convert(&mut context),
-            }?;
-            let name: Name = let_stmt.name.into();
-            val.name = val.name.or_else(|| Some(name.clone()));
-            context.push_variable(name.clone());
-            name_val.push((name, val));
-            stmt = *let_stmt.next;
+impl ToTokens for Statement {
+    fn to_tokens(&self, tokens: &mut TokenStream) {
+        match self {
+            Self::Goal(g) => g.to_tokens(tokens),
+            Self::Let(l) => l.to_tokens(tokens),
         }
-
-        let goal = match stmt {
-            Statement::Goal(goal) => TopLevel::Goal(goal.expr.convert(&mut context)?),
-            Statement::Let(_) => unreachable!(),
-        };
-
-        Ok(name_val.into_iter().rfold(goal, |inner, (name, val)| {
-            TopLevel::Let(ast::Let {
-                name,
-                val,
-                inner: Box::new(inner),
-            })
-        }))
     }
 }
 
 impl Parse for Statement {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
-        let mut lookahead = input.lookahead1();
+        let lookahead = input.lookahead1();
 
         if lookahead.peek(Let) {
             input.parse().map(Self::Let)
-- 
cgit v1.2.3