Merge pull request #132 from Nadrieril/catchup-spec

Catchup spec

17 files changed, 110 insertions, 88 deletions

diff --git a/README.md b/README.md
index aa5cc61..2f90743 100644
--- a/README.md
+++ b/README.md
@@ -63,7 +63,7 @@ assert_eq!(deserialized_map, expected_map);
 ## Standard-compliance
 
 This implementation currently supports partially the [Dhall
-standard](https://github.com/dhall-lang/dhall-lang) version `12.0.0`.
+standard](https://github.com/dhall-lang/dhall-lang) version `14.0.0`.
 
 Only local imports are supported, but otherwise the main features are
 implemented. See
@@ -159,11 +159,25 @@ same name as the corresponding test.
 
 ## Changelog
 
-- 0.2.1: Improve documentation and deserialize many more types
+[???]
 
-- 0.2.0: Update to supporting dhall v12.0.0
+- Update to supporting dhall v14.0.0
+- Add support for dotted field syntax
+- Disallow Natural literals with leading zeros
+- Add support for duplicate record fields
+- Update to supporting dhall v13.0.0
 
-- 0.1.0: Initial release
+[0.2.1]
+
+- Improve documentation and deserialize many more types
+
+[0.2.0]
+
+- Update to supporting dhall v12.0.0
+
+[0.1.0]
+
+- Initial release
 
 ## License
 
diff --git a/dhall-lang b/dhall-lang
-Subproject e2d08ebf5fb5770b57d0681131bed4289d0bb62
+Subproject 68c8aa875801355a319261c87b547b9a017df3c
diff --git a/dhall/build.rs b/dhall/build.rs
index 7c62083..3ac2901 100644
--- a/dhall/build.rs
+++ b/dhall/build.rs
@@ -162,6 +162,7 @@ fn generate_tests() -> std::io::Result<()> {
                     || path == "unit/import/urls/emptyPath0"
                     || path == "unit/import/urls/emptyPath1"
                     || path == "unit/import/urls/emptyPathSegment"
+                    || path == "usingToMap"
             }),
             input_type: FileType::Text,
             output_type: Some(FileType::Binary),
@@ -186,6 +187,7 @@ fn generate_tests() -> std::io::Result<()> {
                     || path == "unit/import/urls/emptyPath0"
                     || path == "unit/import/urls/emptyPath1"
                     || path == "unit/import/urls/emptyPathSegment"
+                    || path == "usingToMap"
             }),
             input_type: FileType::Text,
             output_type: Some(FileType::Binary),
@@ -208,6 +210,7 @@ fn generate_tests() -> std::io::Result<()> {
                     || path == "unit/import/urls/emptyPath0"
                     || path == "unit/import/urls/emptyPath1"
                     || path == "unit/import/urls/emptyPathSegment"
+                    || path == "usingToMap"
             }),
             input_type: FileType::Text,
             output_type: Some(FileType::Binary),
diff --git a/dhall/src/error/builder.rs b/dhall/src/error/builder.rs
index 39f8dfb..b4c5073 100644
--- a/dhall/src/error/builder.rs
+++ b/dhall/src/error/builder.rs
@@ -7,7 +7,7 @@ use annotate_snippets::{
 use crate::syntax::{ParsedSpan, Span};
 
 #[derive(Debug, Clone, Default)]
-pub struct ErrorBuilder {
+pub(crate) struct ErrorBuilder {
     title: FreeAnnotation,
     annotations: Vec<SpannedAnnotation>,
     footer: Vec<FreeAnnotation>,
diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs
index 972326b..319bb9d 100644
--- a/dhall/src/semantics/tck/typecheck.rs
+++ b/dhall/src/semantics/tck/typecheck.rs
@@ -53,11 +53,14 @@ fn function_check(a: Const, b: Const) -> Const {
     }
 }
 
-pub fn mkerr<T, S: ToString>(msg: S) -> Result<T, TypeError> {
+pub(crate) fn mkerr<T, S: ToString>(msg: S) -> Result<T, TypeError> {
     Err(TypeError::new(TypeMessage::Custom(msg.to_string())))
 }
 
-pub fn mk_span_err<T, S: ToString>(span: Span, msg: S) -> Result<T, TypeError> {
+pub(crate) fn mk_span_err<T, S: ToString>(
+    span: Span,
+    msg: S,
+) -> Result<T, TypeError> {
     mkerr(
         ErrorBuilder::new(msg.to_string())
             .span_err(span, msg.to_string())
diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index a479b53..ce0a3d2 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -1,3 +1,5 @@
+use std::collections::BTreeMap;
+
 use crate::semantics::Universe;
 use crate::syntax::map::{DupTreeMap, DupTreeSet};
 use crate::syntax::visitor;
@@ -165,7 +167,7 @@ pub enum ExprKind<SubExpr> {
     ///  `{ k1 : t1, k2 : t1 }`
     RecordType(DupTreeMap<Label, SubExpr>),
     ///  `{ k1 = v1, k2 = v2 }`
-    RecordLit(DupTreeMap<Label, SubExpr>),
+    RecordLit(BTreeMap<Label, SubExpr>),
     ///  `< k1 : t1, k2 >`
     UnionType(DupTreeMap<Label, Option<SubExpr>>),
     ///  `merge x y : t`
@@ -237,32 +239,19 @@ impl<SE> ExprKind<SE> {
 }
 
 impl Expr {
-    pub fn as_ref(&self) -> &UnspannedExpr {
+    pub(crate) fn as_ref(&self) -> &UnspannedExpr {
         &self.kind
     }
     pub fn kind(&self) -> &UnspannedExpr {
         &self.kind
     }
-    pub fn span(&self) -> Span {
+    pub(crate) fn span(&self) -> Span {
         self.span.clone()
     }
 
-    pub fn new(kind: UnspannedExpr, span: Span) -> Self {
-        Expr {
-            kind: Box::new(kind),
-            span,
-        }
-    }
-
-    pub fn rewrap(&self, kind: UnspannedExpr) -> Expr {
+    pub(crate) fn new(kind: UnspannedExpr, span: Span) -> Self {
         Expr {
             kind: Box::new(kind),
-            span: self.span.clone(),
-        }
-    }
-    pub fn with_span(self, span: Span) -> Self {
-        Expr {
-            kind: self.kind,
             span,
         }
     }
diff --git a/dhall/src/syntax/ast/mod.rs b/dhall/src/syntax/ast/mod.rs
index 1950154..5e20c5d 100644
--- a/dhall/src/syntax/ast/mod.rs
+++ b/dhall/src/syntax/ast/mod.rs
@@ -5,7 +5,7 @@ pub use import::*;
 mod label;
 pub use label::*;
 mod span;
-pub use span::*;
+pub(crate) use span::*;
 mod text;
 pub use text::*;
 pub mod map;
diff --git a/dhall/src/syntax/ast/span.rs b/dhall/src/syntax/ast/span.rs
index fba6a2d..7c004c5 100644
--- a/dhall/src/syntax/ast/span.rs
+++ b/dhall/src/syntax/ast/span.rs
@@ -2,7 +2,7 @@ use std::rc::Rc;
 
 /// A location in the source text
 #[derive(Debug, Clone)]
-pub struct ParsedSpan {
+pub(crate) struct ParsedSpan {
     input: Rc<str>,
     /// # Safety
     ///
@@ -15,9 +15,12 @@ pub struct ParsedSpan {
 }
 
 #[derive(Debug, Clone)]
-pub enum Span {
+pub(crate) enum Span {
     /// A location in the source text
     Parsed(ParsedSpan),
+    /// Desugarings
+    DuplicateRecordFieldsSugar,
+    DottedFieldSugar,
     /// For expressions obtained from decoding binary
     Decoded,
     /// For expressions constructed during normalization/typecheck
@@ -50,7 +53,7 @@ impl Span {
     /// Takes the union of the two spans, i.e. the range of input covered by the two spans plus any
     /// input between them. Assumes that the spans come from the same input. Fails if one of the
     /// spans does not point to an input location.
-    pub fn union(&self, other: &Span) -> Self {
+    pub(crate) fn union(&self, other: &Span) -> Self {
         use std::cmp::{max, min};
         use Span::*;
         match (self, other) {
@@ -67,31 +70,6 @@ impl Span {
             ),
         }
     }
-
-    /// Merges two spans assumed to point to a similar thing. If only one of them points to an
-    /// input location, use that one.
-    pub fn merge(&self, other: &Span) -> Self {
-        use Span::*;
-        match (self, other) {
-            (Parsed(x), _) | (_, Parsed(x)) => Parsed(x.clone()),
-            (Artificial, _) | (_, Artificial) => Artificial,
-            (Decoded, Decoded) => Decoded,
-        }
-    }
-
-    pub fn error(&self, message: impl Into<String>) -> String {
-        use pest::error::{Error, ErrorVariant};
-        use pest::Span;
-        let message: String = message.into();
-        let span = match self {
-            self::Span::Parsed(span) => span,
-            _ => return format!("[unknown location] {}", message),
-        };
-        let span = Span::new(&*span.input, span.start, span.end).unwrap();
-        let err: ErrorVariant<!> = ErrorVariant::CustomError { message };
-        let err = Error::new_from_span(err, span);
-        format!("{}", err)
-    }
 }
 
 /// Convert a byte idx into a string into a char idx for consumption by annotate_snippets.
diff --git a/dhall/src/syntax/binary/encode.rs b/dhall/src/syntax/binary/encode.rs
index 291ac4a..d2aa240 100644
--- a/dhall/src/syntax/binary/encode.rs
+++ b/dhall/src/syntax/binary/encode.rs
@@ -1,4 +1,5 @@
 use serde_cbor::value::value as cbor;
+use std::collections::BTreeMap;
 use std::vec;
 
 use crate::error::EncodeError;
@@ -17,7 +18,8 @@ pub(crate) fn encode(expr: &Expr) -> Result<Vec<u8>, EncodeError> {
 enum Serialize<'a> {
     Expr(&'a Expr),
     CBOR(cbor::Value),
-    RecordMap(&'a DupTreeMap<Label, Expr>),
+    RecordMap(&'a BTreeMap<Label, Expr>),
+    RecordDupMap(&'a DupTreeMap<Label, Expr>),
     UnionMap(&'a DupTreeMap<Label, Option<Expr>>),
 }
 
@@ -48,7 +50,7 @@ where
     use syntax::ExprKind::*;
     use syntax::LitKind::*;
 
-    use self::Serialize::{RecordMap, UnionMap};
+    use self::Serialize::{RecordDupMap, RecordMap, UnionMap};
     fn expr(x: &Expr) -> self::Serialize<'_> {
         self::Serialize::Expr(x)
     }
@@ -127,7 +129,7 @@ where
                 Text(x) => cbor(String(x.clone())),
             })))
         }
-        RecordType(map) => ser_seq!(ser; tag(7), RecordMap(map)),
+        RecordType(map) => ser_seq!(ser; tag(7), RecordDupMap(map)),
         RecordLit(map) => ser_seq!(ser; tag(8), RecordMap(map)),
         UnionType(map) => ser_seq!(ser; tag(11), UnionMap(map)),
         Field(x, l) => ser_seq!(ser; tag(9), expr(x), label(l)),
@@ -258,6 +260,11 @@ impl<'a> serde::ser::Serialize for Serialize<'a> {
         match self {
             Serialize::Expr(e) => serialize_subexpr(ser, e),
             Serialize::CBOR(v) => v.serialize(ser),
+            Serialize::RecordDupMap(map) => {
+                ser.collect_map(map.iter().map(|(k, v)| {
+                    (cbor::Value::String(k.into()), Serialize::Expr(v))
+                }))
+            }
             Serialize::RecordMap(map) => {
                 ser.collect_map(map.iter().map(|(k, v)| {
                     (cbor::Value::String(k.into()), Serialize::Expr(v))
diff --git a/dhall/src/syntax/text/parser.rs b/dhall/src/syntax/text/parser.rs
index f3ebd2b..ba64a75 100644
--- a/dhall/src/syntax/text/parser.rs
+++ b/dhall/src/syntax/text/parser.rs
@@ -1,6 +1,7 @@
 use itertools::Itertools;
 use pest::prec_climber as pcl;
 use pest::prec_climber::PrecClimber;
+use std::collections::BTreeMap;
 use std::rc::Rc;
 
 use pest_consume::{match_nodes, Parser};
@@ -124,6 +125,25 @@ fn trim_indent(lines: &mut Vec<ParsedText>) {
     }
 }
 
+/// Insert the expr into the map; in case of collision, create a RecursiveRecordMerge node.
+fn insert_recordlit_entry(map: &mut BTreeMap<Label, Expr>, l: Label, e: Expr) {
+    use crate::syntax::BinOp::RecursiveRecordMerge;
+    use std::collections::btree_map::Entry;
+    match map.entry(l) {
+        Entry::Vacant(entry) => {
+            entry.insert(e);
+        }
+        Entry::Occupied(mut entry) => {
+            let dummy = Expr::new(Lit(Bool(false)), Span::Artificial);
+            let other = entry.insert(dummy);
+            entry.insert(Expr::new(
+                BinOp(RecursiveRecordMerge, other, e),
+                Span::DuplicateRecordFieldsSugar,
+            ));
+        }
+    }
+}
+
 lazy_static::lazy_static! {
     static ref PRECCLIMBER: PrecClimber<Rule> = {
         use Rule::*;
@@ -860,26 +880,16 @@ impl DhallParser {
         input: ParseInput,
     ) -> ParseResult<UnspannedExpr> {
         Ok(match_nodes!(input.children();
-            [label(first_label), non_empty_record_type(rest)] => {
-                let (first_expr, mut map) = rest;
-                map.insert(first_label, first_expr);
-                RecordType(map)
-            },
-            [label(first_label), non_empty_record_literal(rest)] => {
-                let (first_expr, mut map) = rest;
-                map.insert(first_label, first_expr);
-                RecordLit(map)
-            },
+            [non_empty_record_type(map)] => RecordType(map),
+            [non_empty_record_literal(map)] => RecordLit(map),
         ))
     }
 
     fn non_empty_record_type(
         input: ParseInput,
-    ) -> ParseResult<(Expr, DupTreeMap<Label, Expr>)> {
+    ) -> ParseResult<DupTreeMap<Label, Expr>> {
         Ok(match_nodes!(input.into_children();
-            [expression(expr), record_type_entry(entries)..] => {
-                (expr, entries.collect())
-            }
+            [record_type_entry(entries)..] => entries.collect()
         ))
     }
 
@@ -891,17 +901,32 @@ impl DhallParser {
 
     fn non_empty_record_literal(
         input: ParseInput,
-    ) -> ParseResult<(Expr, DupTreeMap<Label, Expr>)> {
+    ) -> ParseResult<BTreeMap<Label, Expr>> {
         Ok(match_nodes!(input.into_children();
-            [expression(expr), record_literal_entry(entries)..] => {
-                (expr, entries.collect())
+            [record_literal_entry(entries)..] => {
+                let mut map = BTreeMap::new();
+                for (l, e) in entries {
+                    insert_recordlit_entry(&mut map, l, e);
+                }
+                map
             }
         ))
     }
 
     fn record_literal_entry(input: ParseInput) -> ParseResult<(Label, Expr)> {
         Ok(match_nodes!(input.into_children();
-            [label(name), expression(expr)] => (name, expr)
+            [label(name), expression(expr)] => (name, expr),
+            [label(first_name), label(names).., expression(expr)] => {
+                // Desugar dotted field syntax into nested records
+                let expr = names.rev().fold(expr, |e, l| {
+                    let map = Some((l, e)).into_iter().collect();
+                    Expr::new(
+                        RecordLit(map),
+                        Span::DottedFieldSugar,
+                    )
+                });
+                (first_name, expr)
+            },
         ))
     }
 
diff --git a/dhall/tests/parser/failure/spacing/RecordTypeNoSpace.txt b/dhall/tests/parser/failure/spacing/RecordTypeNoSpace.txt
index beca670..9c1eaef 100644
--- a/dhall/tests/parser/failure/spacing/RecordTypeNoSpace.txt
+++ b/dhall/tests/parser/failure/spacing/RecordTypeNoSpace.txt
@@ -1,6 +1,6 @@
- --> 1:5
+ --> 1:3
   |
 1 | { x :T }␊
-  |     ^---
+  |   ^---
   |
-  = expected non_empty_record_literal or non_empty_record_type
+  = expected empty_record_literal or non_empty_record_type_or_literal
diff --git a/dhall/tests/parser/failure/unit/NaturalLitLeadingZero.txt b/dhall/tests/parser/failure/unit/NaturalLitLeadingZero.txt
new file mode 100644
index 0000000..07d9b5c
--- /dev/null
+++ b/dhall/tests/parser/failure/unit/NaturalLitLeadingZero.txt
@@ -0,0 +1,6 @@
+ --> 1:2
+  |
+1 | 042␊
+  |  ^---
+  |
+  = expected EOI, import_alt, bool_or, natural_plus, text_append, list_append, bool_and, natural_times, bool_eq, bool_ne, combine, combine_types, equivalent, prefer, or arrow
diff --git a/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFields.txt b/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFields.txt
deleted file mode 100644
index 608c6a0..0000000
--- a/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFields.txt
+++ /dev/null
@@ -1,6 +0,0 @@
-Type error: error: RecordTypeDuplicateField
- --> <current file>:1:0
-  |
-1 | { x = 0, x = 0 }
-  | ^^^^^^^^^^^^^^^^ RecordTypeDuplicateField
-  |
diff --git a/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsAbstract.txt b/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsAbstract.txt
new file mode 100644
index 0000000..f74e839
--- /dev/null
+++ b/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsAbstract.txt
@@ -0,0 +1 @@
+Type error: error: RecordTypeMergeRequiresRecordType
diff --git a/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsCollidingRecords.txt b/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsCollidingRecords.txt
new file mode 100644
index 0000000..f74e839
--- /dev/null
+++ b/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsCollidingRecords.txt
@@ -0,0 +1 @@
+Type error: error: RecordTypeMergeRequiresRecordType
diff --git a/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsNotRecords.txt b/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsNotRecords.txt
new file mode 100644
index 0000000..f74e839
--- /dev/null
+++ b/dhall/tests/type-inference/failure/unit/RecordLitDuplicateFieldsNotRecords.txt
@@ -0,0 +1 @@
+Type error: error: RecordTypeMergeRequiresRecordType
diff --git a/serde_dhall/src/serde.rs b/serde_dhall/src/serde.rs
index 160392d..4fd7815 100644
--- a/serde_dhall/src/serde.rs
+++ b/serde_dhall/src/serde.rs
@@ -48,7 +48,7 @@ impl<'de: 'a, 'a> serde::Deserializer<'de> for Deserializer<'a> {
             )))
         };
 
-        match expr.as_ref() {
+        match expr.kind() {
             Lit(Bool(x)) => visitor.visit_bool(*x),
             Lit(Natural(x)) => {
                 if let Ok(x64) = (*x).try_into() {
@@ -81,11 +81,11 @@ impl<'de: 'a, 'a> serde::Deserializer<'de> for Deserializer<'a> {
                 xs.iter().map(|x| Deserializer(Cow::Borrowed(x))),
             )),
             SomeLit(x) => visitor.visit_some(Deserializer(Cow::Borrowed(x))),
-            App(f, x) => match f.as_ref() {
+            App(f, x) => match f.kind() {
                 Builtin(dhall::syntax::Builtin::OptionalNone) => {
                     visitor.visit_none()
                 }
-                Field(y, name) => match y.as_ref() {
+                Field(y, name) => match y.kind() {
                     UnionType(..) => {
                         let name: String = name.into();
                         visitor.visit_enum(MapAccessDeserializer::new(
@@ -103,7 +103,7 @@ impl<'de: 'a, 'a> serde::Deserializer<'de> for Deserializer<'a> {
                 .visit_map(MapDeserializer::new(m.iter().map(|(k, v)| {
                     (k.as_ref(), Deserializer(Cow::Borrowed(v)))
                 }))),
-            Field(y, name) => match y.as_ref() {
+            Field(y, name) => match y.kind() {
                 UnionType(..) => {
                     let name: String = name.into();
                     visitor.visit_enum(MapAccessDeserializer::new(
@@ -127,7 +127,7 @@ impl<'de: 'a, 'a> serde::Deserializer<'de> for Deserializer<'a> {
         use ExprKind::*;
         let expr = self.0.as_ref();
 
-        match expr.as_ref() {
+        match expr.kind() {
             // Blindly takes keys in sorted order.
             RecordLit(m) => visitor.visit_seq(SeqDeserializer::new(
                 m.iter().map(|(_, v)| Deserializer(Cow::Borrowed(v))),