summaryrefslogtreecommitdiff
path: root/dhall/src
diff options
context:
space:
mode:
Diffstat (limited to 'dhall/src')
-rw-r--r--dhall/src/builtins.rs8
-rw-r--r--dhall/src/operations.rs13
-rw-r--r--dhall/src/semantics/resolve/resolve.rs4
-rw-r--r--dhall/src/semantics/tck/typecheck.rs61
-rw-r--r--dhall/src/syntax/ast/expr.rs5
-rw-r--r--dhall/src/syntax/ast/map.rs282
-rw-r--r--dhall/src/syntax/ast/mod.rs1
-rw-r--r--dhall/src/syntax/binary/encode.rs13
-rw-r--r--dhall/src/syntax/text/parser.rs64
9 files changed, 90 insertions, 361 deletions
diff --git a/dhall/src/builtins.rs b/dhall/src/builtins.rs
index bb8173c..67929a0 100644
--- a/dhall/src/builtins.rs
+++ b/dhall/src/builtins.rs
@@ -1,15 +1,15 @@
+use std::collections::{BTreeMap, HashMap};
+use std::convert::TryInto;
+
use crate::operations::{BinOp, OpKind};
use crate::semantics::{
skip_resolve_expr, typecheck, Hir, HirKind, Nir, NirKind, NzEnv, VarEnv,
};
-use crate::syntax::map::DupTreeMap;
use crate::syntax::Const::Type;
use crate::syntax::{
Const, Expr, ExprKind, InterpolatedText, InterpolatedTextContents, Label,
NaiveDouble, NumKind, Span, UnspannedExpr, V,
};
-use std::collections::HashMap;
-use std::convert::TryInto;
/// Built-ins
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -147,7 +147,7 @@ macro_rules! make_type {
)))
};
({ $($label:ident : $ty:ident),* }) => {{
- let mut kts = DupTreeMap::new();
+ let mut kts = BTreeMap::new();
$(
kts.insert(
Label::from(stringify!($label)),
diff --git a/dhall/src/operations.rs b/dhall/src/operations.rs
index 1ebf288..8b5fa10 100644
--- a/dhall/src/operations.rs
+++ b/dhall/src/operations.rs
@@ -1,7 +1,7 @@
use itertools::Itertools;
use std::borrow::Cow;
use std::cmp::max;
-use std::collections::HashMap;
+use std::collections::{BTreeSet, HashMap};
use crate::builtins::Builtin;
use crate::error::{ErrorBuilder, TypeError};
@@ -9,7 +9,6 @@ use crate::semantics::{
merge_maps, mk_span_err, mkerr, ret_kind, ret_op, ret_ref, Binder, Closure,
Hir, HirKind, Nir, NirKind, Ret, TextLit, Tir, TyEnv, Type,
};
-use crate::syntax::map::DupTreeSet;
use crate::syntax::{trivial_result, Const, ExprKind, Label, NumKind, Span};
// Definition order must match precedence order for
@@ -60,7 +59,7 @@ pub enum OpKind<SubExpr> {
/// `e.x`
Field(SubExpr, Label),
/// `e.{ x, y, z }`
- Projection(SubExpr, DupTreeSet<Label>),
+ Projection(SubExpr, BTreeSet<Label>),
/// `e.(t)`
ProjectionByExpr(SubExpr, SubExpr),
/// `x::y`
@@ -565,13 +564,7 @@ pub fn typecheck_operation(
match kts.get(l) {
None => return span_err("ProjectionMissingEntry"),
Some(t) => {
- use std::collections::hash_map::Entry;
- match new_kts.entry(l.clone()) {
- Entry::Occupied(_) => {
- return span_err("ProjectionDuplicateField")
- }
- Entry::Vacant(e) => e.insert(t.clone()),
- }
+ new_kts.insert(l.clone(), t.clone());
}
};
}
diff --git a/dhall/src/semantics/resolve/resolve.rs b/dhall/src/semantics/resolve/resolve.rs
index cd5232a..e96f16b 100644
--- a/dhall/src/semantics/resolve/resolve.rs
+++ b/dhall/src/semantics/resolve/resolve.rs
@@ -1,5 +1,6 @@
use itertools::Itertools;
use std::borrow::Cow;
+use std::collections::BTreeMap;
use std::env;
use std::path::PathBuf;
use url::Url;
@@ -10,7 +11,6 @@ use crate::error::{Error, ImportError};
use crate::operations::{BinOp, OpKind};
use crate::semantics::{mkerr, Hir, HirKind, ImportEnv, NameEnv, Type};
use crate::syntax;
-use crate::syntax::map::DupTreeMap;
use crate::syntax::{
Expr, ExprKind, FilePath, FilePrefix, Hash, ImportMode, ImportTarget, Span,
UnspannedExpr, URL,
@@ -199,7 +199,7 @@ fn mkexpr(kind: UnspannedExpr) -> Expr {
fn make_aslocation_uniontype() -> Expr {
let text_type = mkexpr(ExprKind::Builtin(Builtin::Text));
- let mut union = DupTreeMap::default();
+ let mut union = BTreeMap::default();
union.insert("Local".into(), Some(text_type.clone()));
union.insert("Remote".into(), Some(text_type.clone()));
union.insert("Environment".into(), Some(text_type));
diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs
index c6300d9..45a3055 100644
--- a/dhall/src/semantics/tck/typecheck.rs
+++ b/dhall/src/semantics/tck/typecheck.rs
@@ -1,5 +1,4 @@
use std::cmp::max;
-use std::collections::HashMap;
use crate::builtins::{type_of_builtin, Builtin};
use crate::error::{ErrorBuilder, TypeError, TypeMessage};
@@ -107,71 +106,55 @@ fn type_one_layer(
Nir::from_builtin(Builtin::List).app(t).to_type(Const::Type)
}
ExprKind::RecordLit(kvs) => {
- use std::collections::hash_map::Entry;
- let mut kts = HashMap::new();
// An empty record type has type Type
let mut k = Const::Type;
- for (x, v) in kvs {
- // Check for duplicated entries
- match kts.entry(x.clone()) {
- Entry::Occupied(_) => {
- return span_err("RecordTypeDuplicateField")
- }
- Entry::Vacant(e) => e.insert(v.ty().to_nir()),
- };
-
+ for (_, v) in kvs {
// Check that the fields have a valid kind
match v.ty().ty().as_const() {
Some(c) => k = max(k, c),
- None => return span_err("InvalidFieldType"),
+ None => return mk_span_err(v.span(), "InvalidFieldType"),
}
}
+ let kts = kvs
+ .iter()
+ .map(|(x, v)| (x.clone(), v.ty().to_nir()))
+ .collect();
+
Nir::from_kind(NirKind::RecordType(kts)).to_type(k)
}
ExprKind::RecordType(kts) => {
- use std::collections::hash_map::Entry;
- let mut seen_fields = HashMap::new();
// An empty record type has type Type
let mut k = Const::Type;
-
- for (x, t) in kts {
- // Check for duplicated entries
- match seen_fields.entry(x.clone()) {
- Entry::Occupied(_) => {
- return span_err("RecordTypeDuplicateField")
- }
- Entry::Vacant(e) => e.insert(()),
- };
-
+ for (_, t) in kts {
// Check the type is a Const and compute final type
match t.ty().as_const() {
Some(c) => k = max(k, c),
- None => return span_err("InvalidFieldType"),
+ None => return mk_span_err(t.span(), "InvalidFieldType"),
}
}
Type::from_const(k)
}
ExprKind::UnionType(kts) => {
- use std::collections::hash_map::Entry;
- let mut seen_fields = HashMap::new();
// Check that all types are the same const
let mut k = None;
- for (x, t) in kts {
+ for (_, t) in kts {
if let Some(t) = t {
- match (k, t.ty().as_const()) {
- (None, Some(k2)) => k = Some(k2),
- (Some(k1), Some(k2)) if k1 == k2 => {}
- _ => return span_err("InvalidFieldType"),
+ let c = match t.ty().as_const() {
+ Some(c) => c,
+ None => {
+ return mk_span_err(t.span(), "InvalidVariantType")
+ }
+ };
+ match k {
+ None => k = Some(c),
+ Some(k) if k == c => {}
+ _ => {
+ return mk_span_err(t.span(), "InvalidVariantType")
+ }
}
}
- match seen_fields.entry(x) {
- Entry::Occupied(_) => {
- return span_err("UnionTypeDuplicateField")
- }
- Entry::Vacant(e) => e.insert(()),
- };
}
// An empty union type has type Type;
diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 8f55540..9d216a7 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -4,7 +4,6 @@ use crate::builtins::Builtin;
use crate::error::Error;
use crate::operations::OpKind;
use crate::semantics::Universe;
-use crate::syntax::map::DupTreeMap;
use crate::syntax::visitor;
use crate::syntax::*;
@@ -81,11 +80,11 @@ pub enum ExprKind<SubExpr> {
/// `[x, y, z]`
NEListLit(Vec<SubExpr>),
/// `{ k1 : t1, k2 : t1 }`
- RecordType(DupTreeMap<Label, SubExpr>),
+ RecordType(BTreeMap<Label, SubExpr>),
/// `{ k1 = v1, k2 = v2 }`
RecordLit(BTreeMap<Label, SubExpr>),
/// `< k1 : t1, k2 >`
- UnionType(DupTreeMap<Label, Option<SubExpr>>),
+ UnionType(BTreeMap<Label, Option<SubExpr>>),
/// `x`, `x@n`
Var(V),
diff --git a/dhall/src/syntax/ast/map.rs b/dhall/src/syntax/ast/map.rs
deleted file mode 100644
index 7a88204..0000000
--- a/dhall/src/syntax/ast/map.rs
+++ /dev/null
@@ -1,282 +0,0 @@
-/// A sorted map that allows multiple values for each key.
-pub use dup_tree_map::DupTreeMap;
-pub use dup_tree_set::DupTreeSet;
-
-mod known_size_iter {
- pub struct KnownSizeIterator<I> {
- pub iter: I,
- pub size: usize,
- }
-
- impl<I: Iterator> Iterator for KnownSizeIterator<I> {
- type Item = I::Item;
-
- fn next(&mut self) -> Option<Self::Item> {
- let next = self.iter.next();
- if next.is_some() {
- self.size -= 1;
- }
- next
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- (self.size, Some(self.size))
- }
- }
-
- // unsafe impl<I: Iterator> iter::TrustedLen for KnownSizeIterator<I> {}
-}
-
-mod tuple {
- mod sealed {
- pub trait Sealed {}
- }
- pub trait Tuple: sealed::Sealed {
- type First;
- type Second;
- }
- impl<A, B> sealed::Sealed for (A, B) {}
- impl<A, B> Tuple for (A, B) {
- type First = A;
- type Second = B;
- }
-}
-
-mod dup_tree_map {
- use super::known_size_iter::KnownSizeIterator;
- use super::tuple::Tuple;
- use smallvec::SmallVec;
- use std::collections::BTreeMap;
- use std::iter;
-
- type OneOrMore<V> = SmallVec<[V; 1]>;
- type DupTreeMapInternal<K, V> = BTreeMap<K, OneOrMore<V>>;
-
- #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
- pub struct DupTreeMap<K, V> {
- map: DupTreeMapInternal<K, V>,
- size: usize,
- }
-
- // Generic types and functions to construct the iterators for this struct.
- type ZipRepeatIter<T> = iter::Zip<
- iter::Repeat<<T as Tuple>::First>,
- <<T as Tuple>::Second as IntoIterator>::IntoIter,
- >;
- type DupTreeMapIter<M> = KnownSizeIterator<
- iter::FlatMap<
- <M as IntoIterator>::IntoIter,
- ZipRepeatIter<<M as IntoIterator>::Item>,
- fn(
- <M as IntoIterator>::Item,
- ) -> ZipRepeatIter<<M as IntoIterator>::Item>,
- >,
- >;
-
- fn zip_repeat<K, I>((k, iter): (K, I)) -> ZipRepeatIter<(K, I)>
- where
- K: Clone,
- I: IntoIterator,
- {
- iter::repeat(k).zip(iter.into_iter())
- }
-
- fn make_map_iter<M, K, I>(map: M, size: usize) -> DupTreeMapIter<M>
- where
- M: IntoIterator<Item = (K, I)>,
- K: Clone,
- I: IntoIterator,
- {
- KnownSizeIterator {
- iter: map.into_iter().flat_map(zip_repeat),
- size,
- }
- }
-
- pub type IterMut<'a, K, V> =
- DupTreeMapIter<&'a mut DupTreeMapInternal<K, V>>;
- pub type Iter<'a, K, V> = DupTreeMapIter<&'a DupTreeMapInternal<K, V>>;
- pub type IntoIter<K, V> = DupTreeMapIter<DupTreeMapInternal<K, V>>;
-
- impl<K: Ord, V> DupTreeMap<K, V> {
- pub fn new() -> Self {
- DupTreeMap {
- map: BTreeMap::new(),
- size: 0,
- }
- }
-
- pub fn insert(&mut self, key: K, value: V) {
- self.map.entry(key).or_default().push(value);
- self.size += 1;
- }
-
- pub fn len(&self) -> usize {
- self.size
- }
- pub fn is_empty(&self) -> bool {
- self.size == 0
- }
-
- pub fn iter(&self) -> Iter<'_, K, V> {
- make_map_iter(&self.map, self.size)
- }
-
- pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
- make_map_iter(&mut self.map, self.size)
- }
- }
-
- impl<K, V> Default for DupTreeMap<K, V>
- where
- K: Ord,
- {
- fn default() -> Self {
- Self::new()
- }
- }
-
- impl<K, V> IntoIterator for DupTreeMap<K, V>
- where
- K: Ord + Clone,
- {
- type Item = (K, V);
- type IntoIter = IntoIter<K, V>;
-
- fn into_iter(self) -> Self::IntoIter {
- make_map_iter(self.map, self.size)
- }
- }
-
- impl<'a, K, V> IntoIterator for &'a DupTreeMap<K, V>
- where
- K: Ord + 'a,
- V: 'a,
- {
- type Item = (&'a K, &'a V);
- type IntoIter = Iter<'a, K, V>;
-
- fn into_iter(self) -> Self::IntoIter {
- self.iter()
- }
- }
-
- impl<'a, K, V> IntoIterator for &'a mut DupTreeMap<K, V>
- where
- K: Ord + 'a,
- V: 'a,
- {
- type Item = (&'a K, &'a mut V);
- type IntoIter = IterMut<'a, K, V>;
-
- fn into_iter(self) -> Self::IntoIter {
- self.iter_mut()
- }
- }
-
- impl<K, V> iter::FromIterator<(K, V)> for DupTreeMap<K, V>
- where
- K: Ord,
- {
- fn from_iter<T>(iter: T) -> Self
- where
- T: IntoIterator<Item = (K, V)>,
- {
- let mut map = DupTreeMap::new();
- for (k, v) in iter {
- map.insert(k, v);
- }
- map
- }
- }
-}
-
-mod dup_tree_set {
- use super::tuple::Tuple;
- use super::DupTreeMap;
- use std::iter;
-
- #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
- pub struct DupTreeSet<K> {
- map: DupTreeMap<K, ()>,
- }
-
- type DupTreeSetIter<M> = iter::Map<
- <M as IntoIterator>::IntoIter,
- fn(
- <M as IntoIterator>::Item,
- ) -> <<M as IntoIterator>::Item as Tuple>::First,
- >;
-
- pub type Iter<'a, K> = DupTreeSetIter<&'a DupTreeMap<K, ()>>;
- pub type IntoIter<K> = DupTreeSetIter<DupTreeMap<K, ()>>;
-
- fn drop_second<A, B>((a, _): (A, B)) -> A {
- a
- }
-
- impl<K: Ord> DupTreeSet<K> {
- pub fn new() -> Self {
- DupTreeSet {
- map: DupTreeMap::new(),
- }
- }
-
- pub fn len(&self) -> usize {
- self.map.len()
- }
- pub fn is_empty(&self) -> bool {
- self.map.is_empty()
- }
-
- pub fn iter(&self) -> Iter<'_, K> {
- self.map.iter().map(drop_second)
- }
- }
-
- impl<K> Default for DupTreeSet<K>
- where
- K: Ord,
- {
- fn default() -> Self {
- Self::new()
- }
- }
-
- impl<K> IntoIterator for DupTreeSet<K>
- where
- K: Ord + Clone,
- {
- type Item = K;
- type IntoIter = IntoIter<K>;
-
- fn into_iter(self) -> Self::IntoIter {
- self.map.into_iter().map(drop_second)
- }
- }
-
- impl<'a, K> IntoIterator for &'a DupTreeSet<K>
- where
- K: Ord + 'a,
- {
- type Item = &'a K;
- type IntoIter = Iter<'a, K>;
-
- fn into_iter(self) -> Self::IntoIter {
- self.iter()
- }
- }
-
- impl<K> iter::FromIterator<K> for DupTreeSet<K>
- where
- K: Ord,
- {
- fn from_iter<T>(iter: T) -> Self
- where
- T: IntoIterator<Item = K>,
- {
- let map = iter.into_iter().map(|k| (k, ())).collect();
- DupTreeSet { map }
- }
- }
-}
diff --git a/dhall/src/syntax/ast/mod.rs b/dhall/src/syntax/ast/mod.rs
index 1950154..c341af7 100644
--- a/dhall/src/syntax/ast/mod.rs
+++ b/dhall/src/syntax/ast/mod.rs
@@ -8,5 +8,4 @@ mod span;
pub use span::*;
mod text;
pub use text::*;
-pub mod map;
pub mod visitor;
diff --git a/dhall/src/syntax/binary/encode.rs b/dhall/src/syntax/binary/encode.rs
index 913dd67..b6bbabe 100644
--- a/dhall/src/syntax/binary/encode.rs
+++ b/dhall/src/syntax/binary/encode.rs
@@ -6,7 +6,6 @@ use crate::builtins::Builtin;
use crate::error::EncodeError;
use crate::operations::{BinOp, OpKind};
use crate::syntax;
-use crate::syntax::map::DupTreeMap;
use crate::syntax::{
Expr, ExprKind, FilePrefix, Hash, Import, ImportMode, ImportTarget, Label,
Scheme, V,
@@ -21,8 +20,7 @@ enum Serialize<'a> {
Expr(&'a Expr),
CBOR(cbor::Value),
RecordMap(&'a BTreeMap<Label, Expr>),
- RecordDupMap(&'a DupTreeMap<Label, Expr>),
- UnionMap(&'a DupTreeMap<Label, Option<Expr>>),
+ UnionMap(&'a BTreeMap<Label, Option<Expr>>),
}
macro_rules! count {
@@ -52,7 +50,7 @@ where
use syntax::NumKind::*;
use OpKind::*;
- use self::Serialize::{RecordDupMap, RecordMap, UnionMap};
+ use self::Serialize::{RecordMap, UnionMap};
fn expr(x: &Expr) -> self::Serialize<'_> {
self::Serialize::Expr(x)
}
@@ -133,7 +131,7 @@ where
Text(x) => cbor(String(x)),
})))
}
- RecordType(map) => ser_seq!(ser; tag(7), RecordDupMap(map)),
+ RecordType(map) => ser_seq!(ser; tag(7), RecordMap(map)),
RecordLit(map) => ser_seq!(ser; tag(8), RecordMap(map)),
UnionType(map) => ser_seq!(ser; tag(11), UnionMap(map)),
Op(Field(x, l)) => ser_seq!(ser; tag(9), expr(x), label(l)),
@@ -266,11 +264,6 @@ 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 dbf5c75..dcaf5e4 100644
--- a/dhall/src/syntax/text/parser.rs
+++ b/dhall/src/syntax/text/parser.rs
@@ -1,14 +1,13 @@
use itertools::Itertools;
use pest::prec_climber as pcl;
use pest::prec_climber::PrecClimber;
-use std::collections::BTreeMap;
+use std::collections::{BTreeMap, BTreeSet};
use std::iter::once;
use std::rc::Rc;
use pest_consume::{match_nodes, Parser};
use crate::operations::OpKind::*;
-use crate::syntax::map::{DupTreeMap, DupTreeSet};
use crate::syntax::ExprKind::*;
use crate::syntax::NumKind::*;
use crate::syntax::{
@@ -32,7 +31,7 @@ pub type ParseResult<T> = Result<T, ParseError>;
#[derive(Debug)]
enum Selector {
Field(Label),
- Projection(DupTreeSet<Label>),
+ Projection(BTreeSet<Label>),
ProjectionByExpr(Expr),
}
@@ -879,9 +878,20 @@ impl DhallParser {
Ok((stor, input_to_span(input)))
}
- fn labels(input: ParseInput) -> ParseResult<DupTreeSet<Label>> {
- Ok(match_nodes!(input.into_children();
- [label(ls)..] => ls.collect(),
+ fn labels(input: ParseInput) -> ParseResult<BTreeSet<Label>> {
+ Ok(match_nodes!(input.children();
+ [label(ls)..] => {
+ let mut set = BTreeSet::default();
+ for l in ls {
+ if set.contains(&l) {
+ return Err(
+ input.error(format!("Duplicate field in projection"))
+ )
+ }
+ set.insert(l);
+ }
+ set
+ },
))
}
@@ -921,9 +931,26 @@ impl DhallParser {
fn non_empty_record_type(
input: ParseInput,
- ) -> ParseResult<DupTreeMap<Label, Expr>> {
- Ok(match_nodes!(input.into_children();
- [record_type_entry(entries)..] => entries.collect()
+ ) -> ParseResult<BTreeMap<Label, Expr>> {
+ Ok(match_nodes!(input.children();
+ [record_type_entry(entries)..] => {
+ let mut map = BTreeMap::default();
+ for (l, t) in entries {
+ use std::collections::btree_map::Entry;
+ match map.entry(l) {
+ Entry::Occupied(_) => {
+ return Err(input.error(
+ "Duplicate field in record type"
+ .to_string(),
+ ));
+ }
+ Entry::Vacant(e) => {
+ e.insert(t);
+ }
+ }
+ }
+ map
+ },
))
}
@@ -972,7 +999,24 @@ impl DhallParser {
fn union_type(input: ParseInput) -> ParseResult<UnspannedExpr> {
let map = match_nodes!(input.children();
[empty_union_type(_)] => Default::default(),
- [union_type_entry(entries)..] => entries.collect(),
+ [union_type_entry(entries)..] => {
+ let mut map = BTreeMap::default();
+ for (l, t) in entries {
+ use std::collections::btree_map::Entry;
+ match map.entry(l) {
+ Entry::Occupied(_) => {
+ return Err(input.error(
+ "Duplicate variant in union type"
+ .to_string(),
+ ));
+ }
+ Entry::Vacant(e) => {
+ e.insert(t);
+ }
+ }
+ }
+ map
+ },
);
Ok(UnionType(map))
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-23 03:48:38 +0000