From aac3549a72663c523a456b2f5d7c3b77f509cdd6 Mon Sep 17 00:00:00 2001
From: Greg Brown <gmb60@cam.ac.uk>
Date: Thu, 14 Jan 2021 11:42:55 +0000
Subject: Add labelled expressions.

Restructure project (again).

Convert `Cat` and `Alt` from binary to n+2-ary.
---
 src/nibble/convert.rs | 233 ++++++++++++++++++++++++++++++++++++++++----------
 src/nibble/cst.rs     | 111 ++++++++++++++++++++----
 2 files changed, 282 insertions(+), 62 deletions(-)

(limited to 'src/nibble')

diff --git a/src/nibble/convert.rs b/src/nibble/convert.rs
index 422d100..5cbf5e2 100644
--- a/src/nibble/convert.rs
+++ b/src/nibble/convert.rs
@@ -1,10 +1,10 @@
-use std::collections::HashMap;
+use std::{collections::HashMap, fmt};
 
 use syn::punctuated::Pair;
 
-use crate::chomp::ast;
+use crate::chomp::ast::{self, NamedExpression};
 
-use super::cst::{Alt, Call, Cat, Fix, Ident, ParenExpression, Term};
+use super::cst::{Alt, Call, Cat, Fix, Ident, Labelled, ParenExpression, Term};
 
 #[derive(Clone, Copy, Debug)]
 pub enum Binding {
@@ -13,7 +13,7 @@ pub enum Binding {
     Global,
 }
 
-#[derive(Debug)]
+#[derive(Debug, Default)]
 pub struct Context {
     names: HashMap<String, Binding>,
     vars: usize,
@@ -62,55 +62,132 @@ impl Context {
     }
 }
 
+#[derive(Clone, Debug)]
+pub enum ConvertError {
+    UndeclaredName(Ident),
+}
+
+impl From<ConvertError> for syn::Error {
+    fn from(e: ConvertError) -> Self {
+        match e {
+            ConvertError::UndeclaredName(ident) => {
+                Self::new(ident.span(), "undeclared name")
+            }
+        }
+    }
+}
+
+impl fmt::Display for ConvertError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::UndeclaredName(i) => {
+                let start = i.span().start();
+                write!(
+                    f,
+                    "{}:{}: undeclared name `{}'",
+                    start.line, start.column, i
+                )
+            }
+        }
+    }
+}
+
+impl std::error::Error for ConvertError {}
+
 pub trait Convert {
-    fn convert(self, context: &mut Context) -> Option<ast::Expression>;
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError>;
 }
 
 impl Convert for Ident {
-    fn convert(self, context: &mut Context) -> Option<ast::Expression> {
-        let span = self.span();
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
+        let span = Some(self.span());
+        let binding = match context.lookup(&self) {
+            Some(b) => b,
+            None => return Err(ConvertError::UndeclaredName(self)),
+        };
+        let name = self.into();
 
-        match context.lookup(&self)? {
-            Binding::Variable(index) => Some(ast::Variable::new(self.into(), index).into()),
-            Binding::Parameter(index) => Some(ast::Parameter::new(self.into(), index).into()),
-            Binding::Global => Some(ast::Call::new(self.into(), Vec::new(), Some(span)).into()),
-        }
+        Ok(match binding {
+            Binding::Variable(index) => NamedExpression {
+                name: Some(name),
+                expr: ast::Variable { index }.into(),
+                span,
+            },
+            Binding::Parameter(index) => NamedExpression {
+                name: Some(name),
+                expr: ast::Parameter { index }.into(),
+                span,
+            },
+            Binding::Global => NamedExpression {
+                name: None,
+                expr: ast::Call {
+                    name,
+                    args: Vec::new(),
+                }
+                .into(),
+                span,
+            },
+        })
     }
 }
 
 impl Convert for Call {
-    fn convert(self, context: &mut Context) -> Option<ast::Expression> {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
         let span = self.span();
         let args = self
             .args
             .into_iter()
             .map(|arg| arg.convert(context))
-            .collect::<Option<_>>()?;
-        Some(ast::Call::new(self.name.into(), args, span).into())
+            .collect::<Result<_, _>>()?;
+        Ok(NamedExpression {
+            name: None,
+            expr: ast::Call {
+                name: self.name.into(),
+                args,
+            }
+            .into(),
+            span,
+        })
     }
 }
 
 impl Convert for Fix {
-    fn convert(self, context: &mut Context) -> Option<ast::Expression> {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
         let span = self.span();
         let expr = self.expr;
         let inner = context.with_variable(&self.arg, |context| expr.convert(context))?;
-        Some(ast::Fix::new(self.arg.into(), inner, span).into())
+        Ok(NamedExpression {
+            name: None,
+            expr: ast::Fix {
+                arg: Some(self.arg.into()),
+                inner: Box::new(inner),
+            }
+            .into(),
+            span,
+        })
     }
 }
 
 impl Convert for ParenExpression {
-    fn convert(self, context: &mut Context) -> Option<ast::Expression> {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
         self.expr.convert(context)
     }
 }
 
 impl Convert for Term {
-    fn convert(self, context: &mut Context) -> Option<ast::Expression> {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
         match self {
-            Self::Epsilon(e) => Some(Some(e).into()),
+            Self::Epsilon(e) => Ok(NamedExpression {
+                name: None,
+                expr: ast::Epsilon.into(),
+                span: Some(e.span),
+            }),
             Self::Ident(i) => i.convert(context),
-            Self::Literal(l) => Some(ast::Literal::from(l).into()),
+            Self::Literal(l) => Ok(NamedExpression {
+                name: None,
+                expr: l.value().into(),
+                span: Some(l.span()),
+            }),
             Self::Call(c) => c.convert(context),
             Self::Fix(f) => f.convert(context),
             Self::Parens(p) => p.convert(context),
@@ -119,47 +196,111 @@ impl Convert for Term {
 }
 
 impl Convert for Cat {
-    fn convert(self, context: &mut Context) -> Option<ast::Expression> {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
         let mut iter = self.0.into_pairs();
-        let mut out = match iter.next().unwrap() {
+
+        let (first, punct) = match iter.next().unwrap() {
             Pair::Punctuated(t, p) => (t.convert(context)?, Some(p)),
             Pair::End(t) => (t.convert(context)?, None),
         };
 
-        for pair in iter {
-            let (fst, punct) = out;
-            out = match pair {
-                Pair::Punctuated(t, p) => (
-                    ast::Cat::new(fst, punct, t.convert(context)?).into(),
-                    Some(p),
-                ),
-                Pair::End(t) => (ast::Cat::new(fst, punct, t.convert(context)?).into(), None),
-            };
+        let mut rest = Vec::new();
+        let (span, _) = iter.try_fold(
+            (
+                first.span.and_then(|s| punct.and_then(|p| s.join(p.span))),
+                punct,
+            ),
+            |(span, punct), pair| {
+                let (snd, p) = match pair {
+                    Pair::Punctuated(t, p) => (t.convert(context)?, Some(p)),
+                    Pair::End(t) => (t.convert(context)?, None),
+                };
+
+                let span = span
+                    .and_then(|s| snd.span.and_then(|t| s.join(t)))
+                    .and_then(|s| p.and_then(|p| s.join(p.span)));
+                rest.push((punct, snd));
+                Ok((span, p))
+            },
+        )?;
+
+        let mut iter = rest.into_iter();
+        if let Some((punct, second)) = iter.next() {
+            Ok(NamedExpression {
+                name: None,
+                expr: ast::Cat {
+                    first: Box::new(first),
+                    punct,
+                    second: Box::new(second),
+                    rest: iter.collect(),
+                }
+                .into(),
+                span,
+            })
+        } else {
+            Ok(first)
         }
+    }
+}
 
-        Some(out.0)
+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);
+
+        Ok(NamedExpression {
+            name,
+            expr: named.expr,
+            span,
+        })
     }
 }
 
 impl Convert for Alt {
-    fn convert(self, context: &mut Context) -> Option<ast::Expression> {
+    fn convert(self, context: &mut Context) -> Result<NamedExpression, ConvertError> {
         let mut iter = self.0.into_pairs();
-        let mut out = match iter.next().unwrap() {
+
+        let (first, punct) = match iter.next().unwrap() {
             Pair::Punctuated(t, p) => (t.convert(context)?, Some(p)),
             Pair::End(t) => (t.convert(context)?, None),
         };
 
-        for pair in iter {
-            let (fst, punct) = out;
-            out = match pair {
-                Pair::Punctuated(t, p) => (
-                    ast::Alt::new(fst, punct, t.convert(context)?).into(),
-                    Some(p),
-                ),
-                Pair::End(t) => (ast::Alt::new(fst, punct, t.convert(context)?).into(), None),
-            };
-        }
+        let mut rest = Vec::new();
+        let (span, _) = iter.try_fold(
+            (
+                first.span.and_then(|s| punct.and_then(|p| s.join(p.span))),
+                punct,
+            ),
+            |(span, punct), pair| {
+                let (snd, p) = match pair {
+                    Pair::Punctuated(t, p) => (t.convert(context)?, Some(p)),
+                    Pair::End(t) => (t.convert(context)?, None),
+                };
 
-        Some(out.0)
+                let span = span
+                    .and_then(|s| snd.span.and_then(|t| s.join(t)))
+                    .and_then(|s| p.and_then(|p| s.join(p.span)));
+                rest.push((punct, snd));
+                Ok((span, p))
+            },
+        )?;
+
+        let mut iter = rest.into_iter();
+        if let Some((punct, second)) = iter.next() {
+            Ok(NamedExpression {
+                name: None,
+                expr: ast::Alt {
+                    first: Box::new(first),
+                    punct,
+                    second: Box::new(second),
+                    rest: iter.collect(),
+                }
+                .into(),
+                span,
+            })
+        } else {
+            Ok(first)
+        }
     }
 }
diff --git a/src/nibble/cst.rs b/src/nibble/cst.rs
index 2b52678..f6fa51b 100644
--- a/src/nibble/cst.rs
+++ b/src/nibble/cst.rs
@@ -4,14 +4,14 @@ use syn::{
     ext::IdentExt,
     parenthesized,
     parse::{Parse, ParseStream},
-    punctuated::Punctuated,
+    punctuated::{Pair, Punctuated},
     token::{Bracket, Comma, Let, Match, Paren},
     LitStr, Token,
 };
 
-use crate::chomp::ast;
+use crate::chomp::{Name, ast};
 
-use super::convert::{Context, Convert};
+use super::convert::{Context, Convert, ConvertError};
 
 pub type Epsilon = Token![_];
 
@@ -134,6 +134,19 @@ pub enum Term {
     Parens(ParenExpression),
 }
 
+impl Term {
+    pub fn span(&self) -> Option<Span> {
+        match self {
+            Self::Epsilon(e) => Some(e.span),
+            Self::Ident(i) => Some(i.span()),
+            Self::Literal(l) => Some(l.span()),
+            Self::Call(c) => c.span(),
+            Self::Fix(f) => f.span(),
+            Self::Parens(p) => Some(p.paren_token.span),
+        }
+    }
+}
+
 impl Parse for Term {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
         let lookahead = input.lookahead1();
@@ -169,8 +182,74 @@ impl Parse for Cat {
     }
 }
 
+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)),
+        })
+    }
+}
+
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Label {
+    colon_tok: Token![:],
+    pub label: Ident,
+}
+
+impl Label {
+    pub fn span(&self) -> Option<Span> {
+        self.colon_tok.span.join(self.label.span())
+    }
+}
+
+impl Parse for Label {
+    fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
+        let colon_tok = input.parse()?;
+        let label = input.call(Ident::parse_any)?;
+        Ok(Self { colon_tok, label })
+    }
+}
+
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct Labelled {
+    pub cat: Cat,
+    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 Parse for Labelled {
+    fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
+        let cat = input.parse()?;
+        let label = if input.peek(Token![:]) {
+            Some(input.parse()?)
+        } else {
+            None
+        };
+        Ok(Self { cat, label })
+    }
+}
+
 #[derive(Clone, Debug, Eq, PartialEq)]
-pub struct Alt(pub Punctuated<Cat, Token![|]>);
+pub struct Alt(pub Punctuated<Labelled, Token![|]>);
 
 impl Parse for Alt {
     fn parse(input: ParseStream<'_>) -> syn::Result<Self> {
@@ -248,28 +327,28 @@ pub struct File {
 }
 
 impl File {
-    pub fn convert(self) -> Option<(Vec<ast::Function>, ast::Expression)> {
+    pub fn convert(self) -> Result<(Vec<ast::Function>, ast::NamedExpression), ConvertError> {
         let mut names = Vec::new();
         let mut map = Vec::new();
         for stmt in self.lets {
-            let count = stmt.args.as_ref().map(ArgList::len).unwrap_or_default();
             let span = stmt.span();
-            let mut context = Context::new(
-                &names,
-                stmt.args.into_iter().flat_map(|args| args.into_iter()),
-            );
+            let params = stmt.args.into_iter().flat_map(|args| args.into_iter());
+            let mut context = Context::new(&names, params.clone());
             names.push(stmt.name.clone());
-            map.push(ast::Function::new(
-                stmt.name.into(),
-                count,
-                stmt.expr.convert(&mut context)?,
+            let mut expr = stmt.expr.convert(&mut context)?;
+            let name: Name = stmt.name.into();
+            expr.name = Some(name.clone());
+            map.push(ast::Function {
+                name,
+                params: params.map(|name| Some(name.into())).collect(),
+                expr,
                 span,
-            ));
+            });
         }
 
         let mut context = Context::new(&names, Vec::new());
         let goal = self.goal.expr.convert(&mut context)?;
-        Some((map, goal))
+        Ok((map, goal))
     }
 }
 
-- 
cgit v1.2.3