Add support for duplicate record fields

13 files changed, 78 insertions, 35 deletions

diff --git a/README.md b/README.md
index 664b167..a46859e 100644
--- a/README.md
+++ b/README.md
@@ -161,19 +161,20 @@ same name as the corresponding test.
 
 [???]
 
-Update to supporting dhall v13.0.0
+- Add support for duplicate record fields
+- Update to supporting dhall v13.0.0
 
 [0.2.1]
 
-Improve documentation and deserialize many more types
+- Improve documentation and deserialize many more types
 
 [0.2.0]
 
-Update to supporting dhall v12.0.0
+- Update to supporting dhall v12.0.0
 
 [0.1.0]
 
-Initial release
+- Initial release
 
 ## License
 
diff --git a/dhall-lang b/dhall-lang
-Subproject 48db9e1ff1f8881fa4310085834fbc19e313ebf
+Subproject 3301f2e2a408d9e3953185c51c1a07c668db47b
diff --git a/dhall/build.rs b/dhall/build.rs
index 7c62083..88a2145 100644
--- a/dhall/build.rs
+++ b/dhall/build.rs
@@ -375,6 +375,26 @@ fn convert_abnf_to_pest() -> std::io::Result<()> {
     rules.remove("url_path");
     writeln!(&mut file, "url_path = _{{ path }}")?;
 
+    // TODO: workaround to simplify record parsing
+    rules.remove("non_empty_record_type_or_literal");
+    rules.remove("non_empty_record_literal");
+    rules.remove("non_empty_record_type");
+    writeln!(
+        &mut file,
+        "non_empty_record_type_or_literal = {{ non_empty_record_literal | \
+         non_empty_record_type }}"
+    )?;
+    writeln!(
+        &mut file,
+        "non_empty_record_literal = {{ record_literal_entry ~ (whsp ~ ^\",\" \
+         ~ whsp ~ record_literal_entry)*}}"
+    )?;
+    writeln!(
+        &mut file,
+        "non_empty_record_type = {{ record_type_entry ~ (whsp ~ ^\",\" ~ whsp \
+         ~ record_type_entry)* }}"
+    )?;
+
     // Work around some greediness issue in the grammar.
     rules.remove("missing");
     writeln!(
diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 089c178..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`
diff --git a/dhall/src/syntax/ast/span.rs b/dhall/src/syntax/ast/span.rs
index e75ea53..6d017f6 100644
--- a/dhall/src/syntax/ast/span.rs
+++ b/dhall/src/syntax/ast/span.rs
@@ -18,6 +18,8 @@ pub(crate) struct ParsedSpan {
 pub(crate) enum Span {
     /// A location in the source text
     Parsed(ParsedSpan),
+    /// Desugaring of duplicate fields
+    DuplicateRecordFieldsSugar,
     /// For expressions obtained from decoding binary
     Decoded,
     /// For expressions constructed during normalization/typecheck
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..f74794b 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,10 +901,14 @@ 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
             }
         ))
     }
diff --git a/dhall/tests/parser/failure/spacing/MergeNoSpace2.txt b/dhall/tests/parser/failure/spacing/MergeNoSpace2.txt
index 96d937b..77314e0 100644
--- a/dhall/tests/parser/failure/spacing/MergeNoSpace2.txt
+++ b/dhall/tests/parser/failure/spacing/MergeNoSpace2.txt
@@ -3,4 +3,4 @@
 1 | merge x(y)␊
   |       ^---
   |
-  = expected missing, double_quote_literal, single_quote_literal, if_, merge, non_empty_list_literal, NaN, Some_, toMap, assert, forall, numeric_double_literal, minus_infinity_literal, plus_infinity_literal, natural_literal, integer_literal, or import_hashed
+  = expected missing, non_empty_list_literal, double_quote_literal, single_quote_literal, if_, merge, NaN, Some_, toMap, assert, forall, numeric_double_literal, minus_infinity_literal, plus_infinity_literal, natural_literal, integer_literal, or import_hashed
diff --git a/dhall/tests/parser/failure/spacing/RecordTypeNoSpace.txt b/dhall/tests/parser/failure/spacing/RecordTypeNoSpace.txt
index beca670..f6427a4 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 non_empty_record_type_or_literal or empty_record_literal
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