summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Cargo.lock5
-rw-r--r--dhall/Cargo.toml1
-rw-r--r--dhall/src/binary.rs14
-rw-r--r--dhall/src/expr.rs3
-rw-r--r--dhall/src/lib.rs1
-rw-r--r--dhall/src/normalize.rs1093
-rw-r--r--dhall/src/typecheck.rs90
-rw-r--r--dhall_core/Cargo.toml2
-rw-r--r--dhall_core/src/context.rs28
-rw-r--r--dhall_core/src/core.rs70
-rw-r--r--dhall_core/src/parser.rs8
-rw-r--r--dhall_core/src/printer.rs34
-rw-r--r--dhall_core/src/text.rs59
-rw-r--r--dhall_core/src/visitor.rs10
-rw-r--r--dhall_generator/src/quote.rs8
-rw-r--r--improved_slice_patterns/Cargo.toml2
-rw-r--r--improved_slice_patterns/README.md7
-rw-r--r--improved_slice_patterns/src/lib.rs30
18 files changed, 973 insertions, 492 deletions
diff --git a/Cargo.lock b/Cargo.lock
index 097dd89..fc30d65 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -71,6 +71,7 @@ dependencies = [
"bytecount 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
"dhall_core 0.1.0",
"dhall_generator 0.1.0",
+ "improved_slice_patterns 2.0.0",
"itertools 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
"pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
"serde 1.0.90 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -84,7 +85,7 @@ name = "dhall_core"
version = "0.1.0"
dependencies = [
"dhall_generated_parser 0.1.0",
- "improved_slice_patterns 1.0.1",
+ "improved_slice_patterns 2.0.0",
"itertools 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
"pest 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
]
@@ -148,7 +149,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
[[package]]
name = "improved_slice_patterns"
-version = "1.0.1"
+version = "2.0.0"
[[package]]
name = "indexmap"
diff --git a/dhall/Cargo.toml b/dhall/Cargo.toml
index 905f074..d1c921f 100644
--- a/dhall/Cargo.toml
+++ b/dhall/Cargo.toml
@@ -15,6 +15,7 @@ itertools = "0.8.0"
term-painter = "0.2.3"
serde = { version = "1.0", features = ["derive"] }
serde_cbor = "0.9.0"
+improved_slice_patterns = { version = "2.0.0", path = "../improved_slice_patterns" }
dhall_core = { path = "../dhall_core" }
dhall_generator = { path = "../dhall_generator" }
diff --git a/dhall/src/binary.rs b/dhall/src/binary.rs
index c12aa2a..7ded3a5 100644
--- a/dhall/src/binary.rs
+++ b/dhall/src/binary.rs
@@ -42,12 +42,12 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<ParsedExpr, DecodeError> {
Var(V(l, *n as usize))
}
[U64(0), f, args..] => {
- let f = cbor_value_to_dhall(&f)?;
- let args = args
- .iter()
- .map(cbor_value_to_dhall)
- .collect::<Result<Vec<_>, _>>()?;
- App(f, args)
+ let mut f = cbor_value_to_dhall(&f)?;
+ for a in args {
+ let a = cbor_value_to_dhall(&a)?;
+ f = rc(App(f, a))
+ }
+ return Ok(f);
}
[U64(1), x, y] => {
let x = cbor_value_to_dhall(&x)?;
@@ -111,7 +111,7 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result<ParsedExpr, DecodeError> {
}
[U64(5), Null, x] => {
let x = cbor_value_to_dhall(&x)?;
- NEOptionalLit(x)
+ SomeLit(x)
}
[U64(5), t, x] => {
let x = cbor_value_to_dhall(&x)?;
diff --git a/dhall/src/expr.rs b/dhall/src/expr.rs
index 5885359..bb1a4e4 100644
--- a/dhall/src/expr.rs
+++ b/dhall/src/expr.rs
@@ -107,9 +107,6 @@ impl<'a> Typed<'a> {
pub(crate) fn as_expr(&self) -> &SubExpr<X, Normalized<'a>> {
&self.0
}
- pub(crate) fn into_expr(self) -> SubExpr<X, Normalized<'a>> {
- self.0
- }
}
#[doc(hidden)]
diff --git a/dhall/src/lib.rs b/dhall/src/lib.rs
index 544df6e..c85b962 100644
--- a/dhall/src/lib.rs
+++ b/dhall/src/lib.rs
@@ -3,6 +3,7 @@
#![feature(slice_patterns)]
#![feature(label_break_value)]
#![feature(non_exhaustive)]
+#![feature(bind_by_move_pattern_guards)]
#![cfg_attr(test, feature(custom_inner_attributes))]
#![allow(
clippy::type_complexity,
diff --git a/dhall/src/normalize.rs b/dhall/src/normalize.rs
index 1561f01..f092c4d 100644
--- a/dhall/src/normalize.rs
+++ b/dhall/src/normalize.rs
@@ -1,8 +1,18 @@
#![allow(non_snake_case)]
-use crate::expr::*;
-use dhall_core::*;
+use std::collections::BTreeMap;
+use std::rc::Rc;
+
+use dhall_core::context::Context;
+use dhall_core::{
+ rc, shift, shift0, Builtin, ExprF, Integer, InterpolatedText,
+ InterpolatedTextContents, Label, Natural, SubExpr, V, X,
+};
use dhall_generator as dhall;
-use std::fmt;
+
+use crate::expr::{Normalized, Typed};
+
+type InputSubExpr = SubExpr<X, Normalized<'static>>;
+type OutputSubExpr = SubExpr<X, X>;
impl<'a> Typed<'a> {
pub fn normalize(self) -> Normalized<'a> {
@@ -19,323 +29,762 @@ impl<'a> Typed<'a> {
}
}
-fn apply_builtin<N, E>(b: Builtin, args: &[Expr<N, E>]) -> WhatNext<N, E>
-where
- N: fmt::Debug + Clone,
- E: fmt::Debug + Clone,
-{
+fn shift0_mut<N, E>(delta: isize, label: &Label, in_expr: &mut SubExpr<N, E>) {
+ let new_expr = shift0(delta, label, &in_expr);
+ std::mem::replace(in_expr, new_expr);
+}
+
+fn shift_mut<N, E>(delta: isize, var: &V<Label>, in_expr: &mut SubExpr<N, E>) {
+ let new_expr = shift(delta, var, &in_expr);
+ std::mem::replace(in_expr, new_expr);
+}
+
+fn apply_builtin(b: Builtin, args: Vec<WHNF>) -> WHNF {
use dhall_core::Builtin::*;
- use dhall_core::ExprF::*;
- use WhatNext::*;
- let (ret, rest) = match (b, args) {
- (OptionalNone, [t, rest..]) => (rc(EmptyOptionalLit(t.roll())), rest),
- (NaturalIsZero, [NaturalLit(n), rest..]) => {
- (rc(BoolLit(*n == 0)), rest)
- }
- (NaturalEven, [NaturalLit(n), rest..]) => {
- (rc(BoolLit(*n % 2 == 0)), rest)
- }
- (NaturalOdd, [NaturalLit(n), rest..]) => {
- (rc(BoolLit(*n % 2 != 0)), rest)
- }
- (NaturalToInteger, [NaturalLit(n), rest..]) => {
- (rc(IntegerLit(*n as isize)), rest)
- }
- (NaturalShow, [NaturalLit(n), rest..]) => {
- (rc(TextLit(n.to_string().into())), rest)
- }
- (ListLength, [_, EmptyListLit(_), rest..]) => (rc(NaturalLit(0)), rest),
- (ListLength, [_, NEListLit(ys), rest..]) => {
- (rc(NaturalLit(ys.len())), rest)
- }
- (ListHead, [_, EmptyListLit(t), rest..]) => {
- (rc(EmptyOptionalLit(t.clone())), rest)
- }
- (ListHead, [_, NEListLit(ys), rest..]) => {
- (rc(NEOptionalLit(ys.first().unwrap().clone())), rest)
- }
- (ListLast, [_, EmptyListLit(t), rest..]) => {
- (rc(EmptyOptionalLit(t.clone())), rest)
- }
- (ListLast, [_, NEListLit(ys), rest..]) => {
- (rc(NEOptionalLit(ys.last().unwrap().clone())), rest)
- }
- (ListReverse, [_, EmptyListLit(t), rest..]) => {
- (rc(EmptyListLit(t.clone())), rest)
- }
- (ListReverse, [_, NEListLit(ys), rest..]) => {
- let ys = ys.iter().rev().cloned().collect();
- (rc(NEListLit(ys)), rest)
- }
- (ListIndexed, [_, EmptyListLit(t), rest..]) => (
- dhall::subexpr!([] : List ({ index : Natural, value : t })),
- rest,
+ use WHNF::*;
+
+ let ret = match b {
+ OptionalNone => improved_slice_patterns::match_vec!(args;
+ [t] => EmptyOptionalLit(Now::from_whnf(t)),
),
- (ListIndexed, [_, NEListLit(xs), rest..]) => {
- let xs = xs
- .iter()
- .cloned()
- .enumerate()
- .map(|(i, e)| {
- let i = rc(NaturalLit(i));
- dhall::subexpr!({ index = i, value = e })
- })
- .collect();
- (rc(NEListLit(xs)), rest)
- }
- (ListBuild, [a0, g, rest..]) => {
- 'ret: {
- if let App(f2, args2) = g {
- if let (Builtin(ListFold), [_, x, rest_inner..]) =
- (f2.as_ref(), args2.as_slice())
- {
- // fold/build fusion
- break 'ret (
- rc(App(x.clone(), rest_inner.to_vec())),
- rest,
- );
- }
- };
- let a0 = a0.roll();
- let a1 = shift(1, &V("x".into(), 0), &a0);
- let g = g.roll();
- break 'ret (
- dhall::subexpr!(
- g
- (List a0)
- (λ(x : a0) -> λ(xs : List a1) -> [ x ] # xs)
- ([] : List a0)
+ NaturalIsZero => improved_slice_patterns::match_vec!(args;
+ [NaturalLit(n)] => BoolLit(n == 0),
+ ),
+ NaturalEven => improved_slice_patterns::match_vec!(args;
+ [NaturalLit(n)] => BoolLit(n % 2 == 0),
+ ),
+ NaturalOdd => improved_slice_patterns::match_vec!(args;
+ [NaturalLit(n)] => BoolLit(n % 2 != 0),
+ ),
+ NaturalToInteger => improved_slice_patterns::match_vec!(args;
+ [NaturalLit(n)] => IntegerLit(n as isize),
+ ),
+ NaturalShow => improved_slice_patterns::match_vec!(args;
+ [NaturalLit(n)] => {
+ TextLit(vec![InterpolatedTextContents::Text(n.to_string())])
+ }
+ ),
+ ListLength => improved_slice_patterns::match_vec!(args;
+ [_, EmptyListLit(_)] => NaturalLit(0),
+ [_, NEListLit(xs)] => NaturalLit(xs.len()),
+ ),
+ ListHead => improved_slice_patterns::match_vec!(args;
+ [_, EmptyListLit(n)] => EmptyOptionalLit(n),
+ [_, NEListLit(xs)] => {
+ NEOptionalLit(xs.into_iter().next().unwrap())
+ }
+ ),
+ ListLast => improved_slice_patterns::match_vec!(args;
+ [_, EmptyListLit(n)] => EmptyOptionalLit(n),
+ [_, NEListLit(xs)] => {
+ NEOptionalLit(xs.into_iter().rev().next().unwrap())
+ }
+ ),
+ ListReverse => improved_slice_patterns::match_vec!(args;
+ [_, EmptyListLit(n)] => EmptyListLit(n),
+ [_, NEListLit(xs)] => {
+ let mut xs = xs;
+ xs.reverse();
+ NEListLit(xs)
+ }
+ ),
+ ListIndexed => improved_slice_patterns::match_vec!(args;
+ [_, EmptyListLit(t)] => {
+ let mut kts = BTreeMap::new();
+ kts.insert(
+ "index".into(),
+ Now::from_whnf(
+ WHNF::from_builtin(Natural)
),
- rest,
);
+ kts.insert("value".into(), t);
+ EmptyListLit(Now::from_whnf(RecordType(kts)))
+ },
+ [_, NEListLit(xs)] => {
+ let xs = xs
+ .into_iter()
+ .enumerate()
+ .map(|(i, e)| {
+ let i = NaturalLit(i);
+ let mut kvs = BTreeMap::new();
+ kvs.insert("index".into(), Now::from_whnf(i));
+ kvs.insert("value".into(), e);
+ Now::from_whnf(RecordLit(kvs))
+ })
+ .collect();
+ NEListLit(xs)
}
- }
- (OptionalBuild, [a0, g, rest..]) => {
- 'ret: {
- if let App(f2, args2) = g {
- if let (Builtin(OptionalFold), [_, x, rest_inner..]) =
- (f2.as_ref(), args2.as_slice())
- {
- // fold/build fusion
- break 'ret (
- rc(App(x.clone(), rest_inner.to_vec())),
- rest,
- );
+ ),
+ ListBuild => improved_slice_patterns::match_vec!(args;
+ // fold/build fusion
+ [_, WHNF::AppliedBuiltin(ListFold, args)] => {
+ let mut args = args;
+ if args.len() >= 2 {
+ args.remove(1)
+ } else {
+ // Do we really need to handle this case ?
+ unimplemented!()
+ }
+ },
+ [t, g] => g
+ .app(WHNF::from_builtin(List).app(t.clone()))
+ .app(ListConsClosure(Now::from_whnf(t.clone()), None))
+ .app(EmptyListLit(Now::from_whnf(t))),
+ ),
+ ListFold => improved_slice_patterns::match_vec!(args;
+ // fold/build fusion
+ [_, WHNF::AppliedBuiltin(ListBuild, args)] => {
+ let mut args = args;
+ if args.len() >= 2 {
+ args.remove(1)
+ } else {
+ unimplemented!()
+ }
+ },
+ [_, EmptyListLit(_), _, _, nil] => nil,
+ [_, NEListLit(xs), _, cons, nil] => {
+ let mut v = nil;
+ for x in xs.into_iter().rev() {
+ v = cons.clone().app(x.normalize()).app(v);
+ }
+ v
+ }
+ ),
+ OptionalBuild => improved_slice_patterns::match_vec!(args;
+ // fold/build fusion
+ [_, WHNF::AppliedBuiltin(OptionalFold, args)] => {
+ let mut args = args;
+ if args.len() >= 2 {
+ args.remove(1)
+ } else {
+ unimplemented!()
+ }
+ },
+ [t, g] => g
+ .app(WHNF::from_builtin(Optional).app(t.clone()))
+ .app(OptionalSomeClosure(Now::from_whnf(t.clone())))
+ .app(EmptyOptionalLit(Now::from_whnf(t))),
+ ),
+ OptionalFold => improved_slice_patterns::match_vec!(args;
+ // fold/build fusion
+ [_, WHNF::AppliedBuiltin(OptionalBuild, args)] => {
+ let mut args = args;
+ if args.len() >= 2 {
+ args.remove(1)
+ } else {
+ unimplemented!()
+ }
+ },
+ [_, EmptyOptionalLit(_), _, _, nothing] => {
+ nothing
+ },
+ [_, NEOptionalLit(x), _, just, _] => {
+ just.app(x.normalize())
+ }
+ ),
+ NaturalBuild => improved_slice_patterns::match_vec!(args;
+ // fold/build fusion
+ [WHNF::AppliedBuiltin(NaturalFold, args)] => {
+ let mut args = args;
+ if args.len() >= 1 {
+ args.remove(0)
+ } else {
+ unimplemented!()
+ }
+ },
+ [g] => g
+ .app(WHNF::from_builtin(Natural))
+ .app(NaturalSuccClosure)
+ .app(NaturalLit(0)),
+ ),
+ NaturalFold => improved_slice_patterns::match_vec!(args;
+ // fold/build fusion
+ [WHNF::AppliedBuiltin(NaturalBuild, args)] => {
+ let mut args = args;
+ if args.len() >= 1 {
+ args.remove(0)
+ } else {
+ unimplemented!()
+ }
+ },
+ [NaturalLit(0), _, _, zero] => zero,
+ [NaturalLit(n), t, succ, zero] => {
+ let fold = WHNF::from_builtin(NaturalFold)
+ .app(NaturalLit(n - 1))
+ .app(t)
+ .app(succ.clone())
+ .app(zero);
+ succ.app(fold)
+ },
+ ),
+ _ => Err(args),
+ };
+
+ match ret {
+ Ok(x) => x,
+ Err(args) => AppliedBuiltin(b, args),
+ }
+}
+
+#[derive(Debug, Clone)]
+enum EnvItem {
+ Expr(WHNF),
+ Skip(usize),
+}
+
+#[derive(Debug, Clone)]
+struct NormalizationContext(Rc<Context<Label, EnvItem>>);
+
+impl NormalizationContext {
+ fn new() -> Self {
+ NormalizationContext(Rc::new(Context::new()))
+ }
+ fn insert(&self, x: &Label, e: WHNF) -> Self {
+ NormalizationContext(Rc::new(
+ self.0.insert(x.clone(), EnvItem::Expr(e)),
+ ))
+ }
+ fn skip(&self, x: &Label) -> Self {
+ NormalizationContext(Rc::new(
+ self.0
+ .map(|l, e| {
+ use EnvItem::*;
+ match e {
+ Expr(e) => {
+ let mut e = e.clone();
+ e.shift0(1, x);
+ Expr(e)
+ }
+ Skip(n) if l == x => Skip(*n + 1),
+ Skip(n) => Skip(*n),
}
- };
- let a0 = a0.roll();
- let g = g.roll();
- break 'ret (
- dhall::subexpr!(
- g
- (Optional a0)
- (λ(x: a0) -> Some x)
- (None a0)
- ),
- rest,
- );
+ })
+ .insert(x.clone(), EnvItem::Skip(0)),
+ ))
+ }
+ fn lookup(&self, var: &V<Label>) -> WHNF {
+ let V(x, n) = var;
+ match self.0.lookup(x, *n) {
+ Some(EnvItem::Expr(e)) => e.clone(),
+ Some(EnvItem::Skip(m)) => {
+ WHNF::Expr(rc(ExprF::Var(V(x.clone(), *m))))
}
+ None => WHNF::Expr(rc(ExprF::Var(V(x.clone(), *n)))),
}
- (ListFold, [_, EmptyListLit(_), _, _, nil, rest..]) => {
- (nil.roll(), rest)
- }
- (ListFold, [_, NEListLit(xs), _, cons, nil, rest..]) => (
- xs.iter().rev().fold(nil.roll(), |acc, x| {
- let x = x.clone();
- let acc = acc.clone();
- let cons = cons.roll();
- dhall::subexpr!(cons x acc)
- }),
- rest,
- ),
- // // fold/build fusion
- // (ListFold, [_, App(box Builtin(ListBuild), [_, x, rest..]), rest..]) => {
- // normalize_ref(&App(bx(x.clone()), rest.to_vec()))
- // }
- (OptionalFold, [_, NEOptionalLit(x), _, just, _, rest..]) => {
- let x = x.clone();
- let just = just.roll();
- (dhall::subexpr!(just x), rest)
+ }
+}
+
+/// A semantic value. This is partially redundant with `dhall_core::Expr`, on purpose. `Expr` should
+/// be limited to syntactic expressions: either written by the user or meant to be printed.
+/// The rule is the following: we must _not_ construct values of type `Expr` while normalizing,
+/// but only construct `WHNF`s.
+///
+/// WHNFs store subexpressions unnormalized, to enable lazy normalization. They approximate
+/// what's called Weak Head Normal-Form (WHNF). This means that the expression is normalized as
+/// little as possible, but just enough to know the first constructor of the normal form. This is
+/// identical to full normalization for simple types like integers, but for e.g. a record literal
+/// this means knowing just the field names.
+///
+/// Each variant captures the relevant contexts when it is constructed. Conceptually each
+/// subexpression has its own context, but in practice some contexts can be shared when sensible, to
+/// avoid unnecessary allocations.
+#[derive(Debug, Clone)]
+enum WHNF {
+ /// Closures
+ Lam(Label, Now, (NormalizationContext, InputSubExpr)),
+ AppliedBuiltin(Builtin, Vec<WHNF>),
+ /// `λ(x: a) -> Some x`
+ OptionalSomeClosure(Now),
+ /// `λ(x : a) -> λ(xs : List a) -> [ x ] # xs`
+ /// `λ(xs : List a) -> [ x ] # xs`
+ ListConsClosure(Now, Option<Now>),
+ /// `λ(x : Natural) -> x + 1`
+ NaturalSuccClosure,
+
+ BoolLit(bool),
+ NaturalLit(Natural),
+ IntegerLit(Integer),
+ EmptyOptionalLit(Now),
+ NEOptionalLit(Now),
+ EmptyListLit(Now),
+ NEListLit(Vec<Now>),
+ RecordLit(BTreeMap<Label, Now>),
+ RecordType(BTreeMap<Label, Now>),
+ UnionType(NormalizationContext, BTreeMap<Label, Option<InputSubExpr>>),
+ UnionConstructor(
+ NormalizationContext,
+ Label,
+ BTreeMap<Label, Option<InputSubExpr>>,
+ ),
+ UnionLit(
+ Label,
+ Now,
+ (NormalizationContext, BTreeMap<Label, Option<InputSubExpr>>),
+ ),
+ TextLit(Vec<InterpolatedTextContents<Now>>),
+ Expr(OutputSubExpr),
+}
+
+impl WHNF {
+ /// Convert the value back to a (normalized) syntactic expression
+ fn normalize_to_expr(self) -> OutputSubExpr {
+ match self {
+ WHNF::Lam(x, t, (ctx, e)) => {
+ let ctx2 = ctx.skip(&x);
+ rc(ExprF::Lam(
+ x.clone(),
+ t.normalize().normalize_to_expr(),
+ normalize_whnf(ctx2, e).normalize_to_expr(),
+ ))
+ }
+ WHNF::AppliedBuiltin(b, args) => {
+ let mut e = WHNF::Expr(rc(ExprF::Builtin(b)));
+ for v in args {
+ e = e.app(v);
+ }
+ e.normalize_to_expr()
+ }
+ WHNF::OptionalSomeClosure(n) => {
+ let a = n.normalize().normalize_to_expr();
+ dhall::subexpr!(λ(x: a) -> Some x)
+ }
+ WHNF::ListConsClosure(n, None) => {
+ let a = n.normalize().normalize_to_expr();
+ // Avoid accidental capture of the new `x` variable
+ let a1 = shift0(1, &"x".into(), &a);
+ dhall::subexpr!(λ(x : a) -> λ(xs : List a1) -> [ x ] # xs)
+ }
+ WHNF::ListConsClosure(n, Some(v)) => {
+ let v = v.normalize().normalize_to_expr();
+ let a = n.normalize().normalize_to_expr();
+ dhall::subexpr!(λ(xs : List a) -> [ v ] # xs)
+ }
+ WHNF::NaturalSuccClosure => {
+ dhall::subexpr!(λ(x : Natural) -> x + 1)
+ }
+ WHNF::BoolLit(b) => rc(ExprF::BoolLit(b)),
+ WHNF::NaturalLit(n) => rc(ExprF::NaturalLit(n)),
+ WHNF::IntegerLit(n) => rc(ExprF::IntegerLit(n)),
+ WHNF::EmptyOptionalLit(n) => {
+ WHNF::Expr(rc(ExprF::Builtin(Builtin::OptionalNone)))
+ .app(n.normalize())
+ .normalize_to_expr()
+ }
+ WHNF::NEOptionalLit(n) => {
+ rc(ExprF::SomeLit(n.normalize().normalize_to_expr()))
+ }
+ WHNF::EmptyListLit(n) => {
+ rc(ExprF::EmptyListLit(n.normalize().normalize_to_expr()))
+ }
+ WHNF::NEListLit(elts) => rc(ExprF::NEListLit(
+ elts.into_iter()
+ .map(|n| n.normalize().normalize_to_expr())
+ .collect(),
+ )),
+ WHNF::RecordLit(kvs) => rc(ExprF::RecordLit(
+ kvs.into_iter()
+ .map(|(k, v)| (k, v.normalize().normalize_to_expr()))
+ .collect(),
+ )),
+ WHNF::RecordType(kts) => rc(ExprF::RecordType(
+ kts.into_iter()
+ .map(|(k, v)| (k, v.normalize().normalize_to_expr()))
+ .collect(),
+ )),
+ WHNF::UnionType(ctx, kts) => rc(ExprF::UnionType(
+ kts.into_iter()
+ .map(|(k, v)| {
+ (
+ k,
+ v.map(|v| {
+ normalize_whnf(ctx.clone(), v)
+ .normalize_to_expr()
+ }),
+ )
+ })
+ .collect(),
+ )),
+ WHNF::UnionConstructor(ctx, l, kts) => {
+ let kts = kts
+ .into_iter()
+ .map(|(k, v)| {
+ (
+ k,
+ v.map(|v| {
+ normalize_whnf(ctx.clone(), v)
+ .normalize_to_expr()
+ }),
+ )
+ })
+ .collect();
+ rc(ExprF::Field(rc(ExprF::UnionType(kts)), l))
+ }
+ WHNF::UnionLit(l, v, (kts_ctx, kts)) => rc(ExprF::UnionLit(
+ l,
+ v.normalize().normalize_to_expr(),
+ kts.into_iter()
+ .map(|(k, v)| {
+ (
+ k,
+ v.map(|v| {
+ normalize_whnf(kts_ctx.clone(), v)
+ .normalize_to_expr()
+ }),
+ )
+ })
+ .collect(),
+ )),
+ WHNF::TextLit(elts) => {
+ fn normalize_textlit(
+ elts: Vec<InterpolatedTextContents<Now>>,
+ ) -> InterpolatedText<OutputSubExpr> {
+ elts.into_iter()
+ .flat_map(|contents| {
+ use InterpolatedTextContents::{Expr, Text};
+ let new_interpolated = match contents {
+ Expr(n) => match n.normalize() {
+ WHNF::TextLit(elts2) => {
+ normalize_textlit(elts2)
+ }
+ e => InterpolatedText::from((
+ String::new(),
+ vec![(
+ e.normalize_to_expr(),
+ String::new(),
+ )],
+ )),
+ },
+ Text(s) => InterpolatedText::from(s),
+ };
+ new_interpolated.into_iter()
+ })
+ .collect()
+ }
+
+ rc(ExprF::TextLit(normalize_textlit(elts)))
+ }
+ WHNF::Expr(e) => e,
}
- (OptionalFold, [_, EmptyOptionalLit(_), _, _, nothing, rest..]) => {
- (nothing.roll(), rest)
+ }
+
+ /// Apply to a value
+ fn app(self, val: WHNF) -> WHNF {
+ match (self, val) {
+ (WHNF::Lam(x, _, (ctx, e)), val) => {
+ let ctx2 = ctx.insert(&x, val);
+ normalize_whnf(ctx2, e)
+ }
+ (WHNF::AppliedBuiltin(b, mut args), val) => {
+ args.push(val);
+ apply_builtin(b, args)
+ }
+ (WHNF::OptionalSomeClosure(_), val) => {
+ WHNF::NEOptionalLit(Now::from_whnf(val))
+ }
+ (WHNF::ListConsClosure(t, None), val) => {
+ WHNF::ListConsClosure(t, Some(Now::from_whnf(val)))
+ }
+ (WHNF::ListConsClosure(_, Some(x)), WHNF::EmptyListLit(_)) => {
+ WHNF::NEListLit(vec![x])
+ }
+ (WHNF::ListConsClosure(_, Some(x)), WHNF::NEListLit(mut xs)) => {
+ xs.insert(0, x);
+ WHNF::NEListLit(xs)
+ }
+ (WHNF::NaturalSuccClosure, WHNF::NaturalLit(n)) => {
+ WHNF::NaturalLit(n + 1)
+ }
+ (WHNF::UnionConstructor(ctx, l, kts), val) => {
+ WHNF::UnionLit(l, Now::from_whnf(val), (ctx, kts))
+ }
+ // Can't do anything useful, convert to expr
+ (f, a) => WHNF::Expr(rc(ExprF::App(
+ f.normalize_to_expr(),
+ a.normalize_to_expr(),
+ ))),
}
- // // fold/build fusion
- // (OptionalFold, [_, App(box Builtin(OptionalBuild), [_, x, rest..]), rest..]) => {
- // normalize_ref(&App(bx(x.clone()), rest.to_vec()))
- // }
- (NaturalBuild, [g, rest..]) => {
- 'ret: {
- if let App(f2, args2) = g {
- if let (Builtin(NaturalFold), [x, rest_inner..]) =
- (f2.as_ref(), args2.as_slice())
- {
- // fold/build fusion
- break 'ret (
- rc(App(x.clone(), rest_inner.to_vec())),
- rest,
- );
+ }
+
+ fn from_builtin(b: Builtin) -> WHNF {
+ WHNF::AppliedBuiltin(b, vec![])
+ }
+
+ fn shift0(&mut self, delta: isize, label: &Label) {
+ match self {
+ WHNF::NaturalSuccClosure
+ | WHNF::BoolLit(_)
+ | WHNF::NaturalLit(_)
+ | WHNF::IntegerLit(_) => {}
+ WHNF::EmptyOptionalLit(n)
+ | WHNF::NEOptionalLit(n)
+ | WHNF::OptionalSomeClosure(n)
+ | WHNF::EmptyListLit(n) => {
+ n.shift0(delta, label);
+ }
+ WHNF::Lam(_, t, (_, e)) => {
+ t.shift0(delta, label);
+ shift_mut(delta, &V(label.clone(), 1), e);
+ }
+ WHNF::AppliedBuiltin(_, args) => {
+ for x in args.iter_mut() {
+ x.shift0(delta, label);
+ }
+ }
+ WHNF::ListConsClosure(t, v) => {
+ t.shift0(delta, label);
+ for x in v.iter_mut() {
+ x.shift0(delta, label);
+ }
+ }
+ WHNF::NEListLit(elts) => {
+ for x in elts.iter_mut() {
+ x.shift0(delta, label);
+ }
+ }
+ WHNF::RecordLit(kvs) | WHNF::RecordType(kvs) => {
+ for x in kvs.values_mut() {
+ x.shift0(delta, label);
+ }
+ }
+ WHNF::UnionType(_, kts) | WHNF::UnionConstructor(_, _, kts) => {
+ for x in kts.values_mut().flat_map(|opt| opt) {
+ shift0_mut(delta, label, x);
+ }
+ }
+ WHNF::UnionLit(_, v, (_, kts)) => {
+ v.shift0(delta, label);
+ for x in kts.values_mut().flat_map(|opt| opt) {
+ shift0_mut(delta, label, x);
+ }
+ }
+ WHNF::TextLit(elts) => {
+ for x in elts.iter_mut() {
+ use InterpolatedTextContents::{Expr, Text};
+ match x {
+ Expr(n) => n.shift0(delta, label),
+ Text(_) => {}
}
- };
- let g = g.roll();
- break 'ret (
- dhall::subexpr!(g Natural (λ(x : Natural) -> x + 1) 0),
- rest,
- );
+ }
}
+ WHNF::Expr(e) => shift0_mut(delta, label, e),
}
- (NaturalFold, [NaturalLit(0), _, _, zero, rest..]) => {
- (zero.roll(), rest)
- }
- (NaturalFold, [NaturalLit(n), t, succ, zero, rest..]) => {
- let fold = rc(Builtin(NaturalFold));
- let n = rc(NaturalLit(n - 1));
- let t = t.roll();
- let succ = succ.roll();
- let zero = zero.roll();
- (dhall::subexpr!(succ (fold n t succ zero)), rest)
- }
- // (NaturalFold, Some(App(f2, args2)), _) => {
- // match (f2.as_ref(), args2.as_slice()) {
- // // fold/build fusion
- // (Builtin(NaturalBuild), [x, rest..]) => {
- // rc(App(x.clone(), rest.to_vec()))
- // }
- // _ => return rc(App(f, args)),
- // }
- // }
- _ => return DoneAsIs,
- };
- // Put the remaining arguments back and eval again. In most cases
- // ret will not be of a form that can be applied, so this won't go very deep.
- // In lots of cases, there are no remaining args so this cann will just return ret.
- let rest: Vec<SubExpr<N, E>> = rest.iter().map(ExprF::roll).collect();
- Continue(ExprF::App(ret, rest))
+ }
}
-// Small enum to help with being DRY
-enum WhatNext<'a, N, E> {
- // Recurse on this expression
- Continue(Expr<N, E>),
- ContinueSub(SubExpr<N, E>),
- // The following expression is the normal form
- Done(Expr<N, E>),
- DoneRef(&'a Expr<N, E>),
- DoneRefSub(&'a SubExpr<N, E>),
- // The current expression is already in normal form
- DoneAsIs,
+/// Normalize-on-write smart container. Contains either a (partially) normalized value or a
+/// non-normalized value alongside a normalization context.
+/// The name is a pun on std::borrow::Cow.
+#[derive(Debug, Clone)]
+enum Now {
+ Normalized(Box<WHNF>),
+ Unnormalized(NormalizationContext, InputSubExpr),
}
-fn normalize_ref(expr: &Expr<X, Normalized<'static>>) -> Expr<X, X> {
- use dhall_core::BinOp::*;
- use dhall_core::ExprF::*;
- // Recursively normalize all subexpressions
- let expr: ExprF<Expr<X, X>, Label, X, Normalized<'static>> =
- expr.map_ref_simple(|e| normalize_ref(e.as_ref()));
-
- use WhatNext::*;
- // TODO: match by move
- let what_next = match &expr {
- Let(f, _, r, b) => {
- let vf0 = &V(f.clone(), 0);
- // TODO: use a context
- ContinueSub(subst_shift(vf0, &r.roll(), &b.roll()))
+impl Now {
+ fn new(ctx: NormalizationContext, e: InputSubExpr) -> Now {
+ Now::Unnormalized(ctx, e)
+ }
+
+ fn from_whnf(v: WHNF) -> Now {
+ Now::Normalized(Box::new(v))
+ }
+
+ fn normalize(self) -> WHNF {
+ match self {
+ Now::Normalized(v) => *v,
+ Now::Unnormalized(ctx, e) => normalize_whnf(ctx, e),
+ }
+ }
+
+ fn shift0(&mut self, delta: isize, label: &Label) {
+ match self {
+ Now::Normalized(v) => v.shift0(delta, label),
+ Now::Unnormalized(_, e) => shift0_mut(delta, label, e),
+ }
+ }
+}
+
+/// Reduces the imput expression to WHNF. See doc on `WHNF` for details.
+fn normalize_whnf(ctx: NormalizationContext, expr: InputSubExpr) -> WHNF {
+ match expr.as_ref() {
+ ExprF::Var(v) => ctx.lookup(&v),
+ ExprF::Annot(x, _) => normalize_whnf(ctx, x.clone()),
+ ExprF::Note(_, e) => normalize_whnf(ctx, e.clone()),
+ // TODO: wasteful to retraverse everything
+ ExprF::Embed(e) => normalize_whnf(ctx, e.0.embed_absurd()),
+ ExprF::Let(x, _, r, b) => {
+ let r = normalize_whnf(ctx.clone(), r.clone());
+ normalize_whnf(ctx.insert(x, r), b.clone())
+ }
+ ExprF::Lam(x, t, e) => WHNF::Lam(
+ x.clone(),
+ Now::new(ctx.clone(), t.clone()),
+ (ctx, e.clone()),
+ ),
+ ExprF::Builtin(b) => WHNF::AppliedBuiltin(*b, vec![]),
+ ExprF::BoolLit(b) => WHNF::BoolLit(*b),
+ ExprF::NaturalLit(n) => WHNF::NaturalLit(*n),
+ ExprF::OldOptionalLit(None, e) => {
+ WHNF::EmptyOptionalLit(Now::new(ctx, e.clone()))
}
- Annot(x, _) => DoneRef(x),
- Note(_, e) => DoneRef(e),
- App(f, args) if args.is_empty() => DoneRef(f),
- App(App(f, args1), args2) => Continue(App(
- f.clone(),
- args1
- .iter()
- .cloned()
- .chain(args2.iter().map(ExprF::roll))
+ ExprF::OldOptionalLit(Some(e), _) => {
+ WHNF::NEOptionalLit(Now::new(ctx, e.clone()))
+ }
+ ExprF::SomeLit(e) => WHNF::NEOptionalLit(Now::new(ctx, e.clone())),
+ ExprF::EmptyListLit(e) => WHNF::EmptyListLit(Now::new(ctx, e.clone())),
+ ExprF::NEListLit(elts) => WHNF::NEListLit(
+ elts.iter()
+ .map(|e| Now::new(ctx.clone(), e.clone()))
.collect(),
- )),
- App(Builtin(b), args) => apply_builtin(*b, args),
- App(Lam(x, _, b), args) => {
- let mut iter = args.iter();
- // We know args is nonempty
- let a = iter.next().unwrap();
- // Beta reduce
- let vx0 = &V(x.clone(), 0);
- let b2 = subst_shift(vx0, &a.roll(), &b);
- Continue(App(b2, iter.map(ExprF::roll).collect()))
+ ),
+ ExprF::RecordLit(kvs) => WHNF::RecordLit(
+ kvs.iter()
+ .map(|(k, e)| (k.clone(), Now::new(ctx.clone(), e.clone())))
+ .collect(),
+ ),
+ ExprF::UnionType(kvs) => WHNF::UnionType(ctx, kvs.clone()),
+ ExprF::UnionLit(l, x, kts) => WHNF::UnionLit(
+ l.clone(),
+ Now::new(ctx.clone(), x.clone()),
+ (ctx, kts.clone()),
+ ),
+ ExprF::TextLit(elts) => WHNF::TextLit(
+ elts.iter()
+ .map(|contents| {
+ use InterpolatedTextContents::{Expr, Text};
+ match contents {
+ Expr(n) => Expr(Now::new(ctx.clone(), n.clone())),
+ Text(s) => Text(s.clone()),
+ }
+ })
+ .collect(),
+ ),
+ ExprF::BoolIf(b, e1, e2) => {
+ let b = normalize_whnf(ctx.clone(), b.clone());
+ match b {
+ WHNF::BoolLit(true) => normalize_whnf(ctx, e1.clone()),
+ WHNF::BoolLit(false) => normalize_whnf(ctx, e2.clone()),
+ b => {
+ let e1 = normalize_whnf(ctx.clone(), e1.clone());
+ let e2 = normalize_whnf(ctx, e2.clone());
+ match (e1, e2) {
+ (WHNF::BoolLit(true), WHNF::BoolLit(false)) => b,
+ (e1, e2) => {
+ normalize_last_layer(ExprF::BoolIf(b, e1, e2))
+ }
+ }
+ }
+ }
}
- App(UnionConstructor(l, kts), args) => {
- let mut iter = args.iter();
- // We know args is nonempty
- let a = iter.next().unwrap();
- let e = rc(UnionLit(l.clone(), rc(a.clone()), kts.clone()));
- Continue(App(e, iter.map(ExprF::roll).collect()))
+ expr => {
+ // Recursively normalize subexpressions
+ let expr: ExprF<WHNF, Label, X, X> = expr
+ .map_ref_with_special_handling_of_binders(
+ |e| normalize_whnf(ctx.clone(), e.clone()),
+ |x, e| normalize_whnf(ctx.skip(x), e.clone()),
+ X::clone,
+ |_| unreachable!(),
+ Label::clone,
+ );
+
+ normalize_last_layer(expr)
}
- BoolIf(BoolLit(true), t, _) => DoneRef(t),
- BoolIf(BoolLit(false), _, f) => DoneRef(f),
- // TODO: interpolation
- // TextLit(t) =>
- OldOptionalLit(None, t) => Done(EmptyOptionalLit(t.roll())),
- OldOptionalLit(Some(x), _) => Done(NEOptionalLit(x.roll())),
- BinOp(BoolAnd, BoolLit(x), BoolLit(y)) => Done(BoolLit(*x && *y)),
- BinOp(BoolOr, BoolLit(x), BoolLit(y)) => Done(BoolLit(*x || *y)),
- BinOp(BoolEQ, BoolLit(x), BoolLit(y)) => Done(BoolLit(x == y)),
- BinOp(BoolNE, BoolLit(x), BoolLit(y)) => Done(BoolLit(x != y)),
- BinOp(NaturalPlus, NaturalLit(x), NaturalLit(y)) => {
- Done(NaturalLit(x + y))
+ }
+}
+
+/// When all sub-expressions have been (partially) normalized, eval the remaining toplevel layer.
+fn normalize_last_layer(expr: ExprF<WHNF, Label, X, X>) -> WHNF {
+ use dhall_core::BinOp::*;
+ use WHNF::*;
+
+ match expr {
+ ExprF::App(v, a) => v.app(a),
+
+ ExprF::BinOp(BoolAnd, BoolLit(true), y) => y,
+ ExprF::BinOp(BoolAnd, x, BoolLit(true)) => x,
+ ExprF::BinOp(BoolAnd, BoolLit(false), _) => BoolLit(false),
+ ExprF::BinOp(BoolAnd, _, BoolLit(false)) => BoolLit(false),
+ ExprF::BinOp(BoolOr, BoolLit(true), _) => BoolLit(true),
+ ExprF::BinOp(BoolOr, _, BoolLit(true)) => BoolLit(true),
+ ExprF::BinOp(BoolOr, BoolLit(false), y) => y,
+ ExprF::BinOp(BoolOr, x, BoolLit(false)) => x,
+ ExprF::BinOp(BoolEQ, BoolLit(true), y) => y,
+ ExprF::BinOp(BoolEQ, x, BoolLit(true)) => x,
+ ExprF::BinOp(BoolNE, BoolLit(false), y) => y,
+ ExprF::BinOp(BoolNE, x, BoolLit(false)) => x,
+ ExprF::BinOp(BoolEQ, BoolLit(x), BoolLit(y)) => BoolLit(x == y),
+ ExprF::BinOp(BoolNE, BoolLit(x), BoolLit(y)) => BoolLit(x != y),
+
+ ExprF::BinOp(NaturalPlus, NaturalLit(0), y) => y,
+ ExprF::BinOp(NaturalPlus, x, NaturalLit(0)) => x,
+ ExprF::BinOp(NaturalTimes, NaturalLit(0), _) => NaturalLit(0),
+ ExprF::BinOp(NaturalTimes, _, NaturalLit(0)) => NaturalLit(0),
+ ExprF::BinOp(NaturalTimes, NaturalLit(1), y) => y,
+ ExprF::BinOp(NaturalTimes, x, NaturalLit(1)) => x,
+ ExprF::BinOp(NaturalPlus, NaturalLit(x), NaturalLit(y)) => {
+ NaturalLit(x + y)
}
- BinOp(NaturalTimes, NaturalLit(x), NaturalLit(y)) => {
- Done(NaturalLit(x * y))
+ ExprF::BinOp(NaturalTimes, NaturalLit(x), NaturalLit(y)) => {
+ NaturalLit(x * y)
}
- BinOp(TextAppend, TextLit(x), TextLit(y)) => Done(TextLit(x + y)),
- BinOp(ListAppend, EmptyListLit(_), y) => DoneRef(y),
- BinOp(ListAppend, x, EmptyListLit(_)) => DoneRef(x),
- BinOp(ListAppend, NEListLit(xs), NEListLit(ys)) => {
- let xs = xs.iter().cloned();
- let ys = ys.iter().cloned();
- Done(NEListLit(xs.chain(ys).collect()))
+
+ ExprF::BinOp(ListAppend, EmptyListLit(_), y) => y,
+ ExprF::BinOp(ListAppend, x, EmptyListLit(_)) => x,
+ ExprF::BinOp(ListAppend, NEListLit(mut xs), NEListLit(mut ys)) => {
+ xs.append(&mut ys);
+ NEListLit(xs)
}
- Merge(RecordLit(handlers), UnionLit(l, v, _), _) => {
- match handlers.get(&l) {
- Some(h) => Continue(App(h.clone(), vec![v.clone()])),
- None => DoneAsIs,
- }
+ ExprF::BinOp(TextAppend, TextLit(mut x), TextLit(mut y)) => {
+ x.append(&mut y);
+ TextLit(x)
}
- Merge(RecordLit(handlers), UnionConstructor(l, _), _) => {
- match handlers.get(&l) {
- Some(h) => DoneRefSub(h),
- None => DoneAsIs,
+ ExprF::BinOp(TextAppend, TextLit(x), y) if x.is_empty() => y,
+ ExprF::BinOp(TextAppend, x, TextLit(y)) if y.is_empty() => x,
+
+ ExprF::Field(UnionType(ctx, kts), l) => UnionConstructor(ctx, l, kts),
+ ExprF::Field(RecordLit(mut kvs), l) => match kvs.remove(&l) {
+ Some(r) => r.normalize(),
+ None => {
+ // Couldn't do anything useful, so just normalize subexpressions
+ Expr(rc(ExprF::Field(RecordLit(kvs).normalize_to_expr(), l)))
}
- }
- Field(RecordLit(kvs), l) => match kvs.get(&l) {
- Some(r) => DoneRefSub(r),
- None => DoneAsIs,
},
- Field(UnionType(kts), l) => {
- Done(UnionConstructor(l.clone(), kts.clone()))
+ ExprF::Projection(_, ls) if ls.is_empty() => {
+ RecordLit(std::collections::BTreeMap::new())
}
- Projection(_, ls) if ls.is_empty() => {
- Done(RecordLit(std::collections::BTreeMap::new()))
- }
- Projection(RecordLit(kvs), ls) => Done(RecordLit(
- ls.iter()
- .filter_map(|l| kvs.get(l).map(|x| (l.clone(), x.clone())))
+ ExprF::Projection(RecordLit(mut kvs), ls) => RecordLit(
+ ls.into_iter()
+ .filter_map(|l| kvs.remove(&l).map(|x| (l, x)))
.collect(),
- )),
- Embed(e) => DoneRefSub(&e.0),
- _ => DoneAsIs,
- };
-
- match what_next {
- Continue(e) => normalize_ref(&e.embed_absurd()),
- ContinueSub(e) => normalize_ref(e.embed_absurd().as_ref()),
- Done(e) => e,
- DoneRef(e) => e.clone(),
- DoneRefSub(e) => e.unroll(),
- DoneAsIs => expr.map_ref_simple(ExprF::roll).map_ref(
- SubExpr::clone,
- X::clone,
- |_| unreachable!(),
- Label::clone,
),
+ ExprF::Merge(RecordLit(mut handlers), e, t) => {
+ let e = match e {
+ UnionConstructor(ctor_ctx, l, kts) => match handlers.remove(&l)
+ {
+ Some(h) => return h.normalize(),
+ None => UnionConstructor(ctor_ctx, l, kts),
+ },
+ UnionLit(l, v, (kts_ctx, kts)) => match handlers.remove(&l) {
+ Some(h) => {
+ let h = h.normalize();
+ let v = v.normalize();
+ return h.app(v);
+ }
+ None => UnionLit(l, v, (kts_ctx, kts)),
+ },
+ e => e,
+ };
+ // Couldn't do anything useful, so just normalize subexpressions
+ Expr(rc(ExprF::Merge(
+ RecordLit(handlers).normalize_to_expr(),
+ e.normalize_to_expr(),
+ t.map(WHNF::normalize_to_expr),
+ )))
+ }
+ // Couldn't do anything useful, so just normalize subexpressions
+ expr => {
+ Expr(rc(expr.map_ref_simple(|e| e.clone().normalize_to_expr())))
+ }
}
}
@@ -348,8 +797,8 @@ fn normalize_ref(expr: &Expr<X, Normalized<'static>>) -> Expr<X, X> {
/// However, `normalize` will not fail if the expression is ill-typed and will
/// leave ill-typed sub-expressions unevaluated.
///
-fn normalize(e: SubExpr<X, Normalized<'static>>) -> SubExpr<X, X> {
- normalize_ref(e.as_ref()).roll()
+fn normalize(e: InputSubExpr) -> OutputSubExpr {
+ normalize_whnf(NormalizationContext::new(), e).normalize_to_expr()
}
#[cfg(test)]
@@ -489,7 +938,7 @@ mod spec_tests {
norm!(success_prelude_Optional_unzip_1, "prelude/Optional/unzip/1");
norm!(success_prelude_Text_concat_0, "prelude/Text/concat/0");
norm!(success_prelude_Text_concat_1, "prelude/Text/concat/1");
- // norm!(success_prelude_Text_concatMap_0, "prelude/Text/concatMap/0");
+ norm!(success_prelude_Text_concatMap_0, "prelude/Text/concatMap/0");
norm!(success_prelude_Text_concatMap_1, "prelude/Text/concatMap/1");
// norm!(success_prelude_Text_concatMapSep_0, "prelude/Text/concatMapSep/0");
// norm!(success_prelude_Text_concatMapSep_1, "prelude/Text/concatMapSep/1");
@@ -536,7 +985,7 @@ mod spec_tests {
// norm!(success_unit_IfAlternativesIdentical, "unit/IfAlternativesIdentical");
norm!(success_unit_IfFalse, "unit/IfFalse");
norm!(success_unit_IfNormalizePredicateAndBranches, "unit/IfNormalizePredicateAndBranches");
- // norm!(success_unit_IfTrivial, "unit/IfTrivial");
+ norm!(success_unit_IfTrivial, "unit/IfTrivial");
norm!(success_unit_IfTrue, "unit/IfTrue");
norm!(success_unit_Integer, "unit/Integer");
norm!(success_unit_IntegerNegative, "unit/IntegerNegative");
@@ -603,42 +1052,42 @@ mod spec_tests {
norm!(success_unit_None, "unit/None");
norm!(success_unit_NoneNatural, "unit/NoneNatural");
// norm!(success_unit_OperatorAndEquivalentArguments, "unit/OperatorAndEquivalentArguments");
- // norm!(success_unit_OperatorAndLhsFalse, "unit/OperatorAndLhsFalse");
- // norm!(success_unit_OperatorAndLhsTrue, "unit/OperatorAndLhsTrue");
- // norm!(success_unit_OperatorAndNormalizeArguments, "unit/OperatorAndNormalizeArguments");
- // norm!(success_unit_OperatorAndRhsFalse, "unit/OperatorAndRhsFalse");
- // norm!(success_unit_OperatorAndRhsTrue, "unit/OperatorAndRhsTrue");
+ norm!(success_unit_OperatorAndLhsFalse, "unit/OperatorAndLhsFalse");
+ norm!(success_unit_OperatorAndLhsTrue, "unit/OperatorAndLhsTrue");
+ norm!(success_unit_OperatorAndNormalizeArguments, "unit/OperatorAndNormalizeArguments");
+ norm!(success_unit_OperatorAndRhsFalse, "unit/OperatorAndRhsFalse");
+ norm!(success_unit_OperatorAndRhsTrue, "unit/OperatorAndRhsTrue");
// norm!(success_unit_OperatorEqualEquivalentArguments, "unit/OperatorEqualEquivalentArguments");
- // norm!(success_unit_OperatorEqualLhsTrue, "unit/OperatorEqualLhsTrue");
- // norm!(success_unit_OperatorEqualNormalizeArguments, "unit/OperatorEqualNormalizeArguments");
- // norm!(success_unit_OperatorEqualRhsTrue, "unit/OperatorEqualRhsTrue");
+ norm!(success_unit_OperatorEqualLhsTrue, "unit/OperatorEqualLhsTrue");
+ norm!(success_unit_OperatorEqualNormalizeArguments, "unit/OperatorEqualNormalizeArguments");
+ norm!(success_unit_OperatorEqualRhsTrue, "unit/OperatorEqualRhsTrue");
norm!(success_unit_OperatorListConcatenateLhsEmpty, "unit/OperatorListConcatenateLhsEmpty");
norm!(success_unit_OperatorListConcatenateListList, "unit/OperatorListConcatenateListList");
norm!(success_unit_OperatorListConcatenateNormalizeArguments, "unit/OperatorListConcatenateNormalizeArguments");
norm!(success_unit_OperatorListConcatenateRhsEmpty, "unit/OperatorListConcatenateRhsEmpty");
// norm!(success_unit_OperatorNotEqualEquivalentArguments, "unit/OperatorNotEqualEquivalentArguments");
- // norm!(success_unit_OperatorNotEqualLhsFalse, "unit/OperatorNotEqualLhsFalse");
- // norm!(success_unit_OperatorNotEqualNormalizeArguments, "unit/OperatorNotEqualNormalizeArguments");
- // norm!(success_unit_OperatorNotEqualRhsFalse, "unit/OperatorNotEqualRhsFalse");
+ norm!(success_unit_OperatorNotEqualLhsFalse, "unit/OperatorNotEqualLhsFalse");
+ norm!(success_unit_OperatorNotEqualNormalizeArguments, "unit/OperatorNotEqualNormalizeArguments");
+ norm!(success_unit_OperatorNotEqualRhsFalse, "unit/OperatorNotEqualRhsFalse");
// norm!(success_unit_OperatorOrEquivalentArguments, "unit/OperatorOrEquivalentArguments");
- // norm!(success_unit_OperatorOrLhsFalse, "unit/OperatorOrLhsFalse");
- // norm!(success_unit_OperatorOrLhsTrue, "unit/OperatorOrLhsTrue");
- // norm!(success_unit_OperatorOrNormalizeArguments, "unit/OperatorOrNormalizeArguments");
- // norm!(success_unit_OperatorOrRhsFalse, "unit/OperatorOrRhsFalse");
- // norm!(success_unit_OperatorOrRhsTrue, "unit/OperatorOrRhsTrue");
- // norm!(success_unit_OperatorPlusLhsZero, "unit/OperatorPlusLhsZero");
- // norm!(success_unit_OperatorPlusNormalizeArguments, "unit/OperatorPlusNormalizeArguments");
+ norm!(success_unit_OperatorOrLhsFalse, "unit/OperatorOrLhsFalse");
+ norm!(success_unit_OperatorOrLhsTrue, "unit/OperatorOrLhsTrue");
+ norm!(success_unit_OperatorOrNormalizeArguments, "unit/OperatorOrNormalizeArguments");
+ norm!(success_unit_OperatorOrRhsFalse, "unit/OperatorOrRhsFalse");
+ norm!(success_unit_OperatorOrRhsTrue, "unit/OperatorOrRhsTrue");
+ norm!(success_unit_OperatorPlusLhsZero, "unit/OperatorPlusLhsZero");
+ norm!(success_unit_OperatorPlusNormalizeArguments, "unit/OperatorPlusNormalizeArguments");
norm!(success_unit_OperatorPlusOneAndOne, "unit/OperatorPlusOneAndOne");
- // norm!(success_unit_OperatorPlusRhsZero, "unit/OperatorPlusRhsZero");
- // norm!(success_unit_OperatorTextConcatenateLhsEmpty, "unit/OperatorTextConcatenateLhsEmpty");
- // norm!(success_unit_OperatorTextConcatenateNormalizeArguments, "unit/OperatorTextConcatenateNormalizeArguments");
- // norm!(success_unit_OperatorTextConcatenateRhsEmpty, "unit/OperatorTextConcatenateRhsEmpty");
+ norm!(success_unit_OperatorPlusRhsZero, "unit/OperatorPlusRhsZero");
+ norm!(success_unit_OperatorTextConcatenateLhsEmpty, "unit/OperatorTextConcatenateLhsEmpty");
+ norm!(success_unit_OperatorTextConcatenateNormalizeArguments, "unit/OperatorTextConcatenateNormalizeArguments");
+ norm!(success_unit_OperatorTextConcatenateRhsEmpty, "unit/OperatorTextConcatenateRhsEmpty");
norm!(success_unit_OperatorTextConcatenateTextText, "unit/OperatorTextConcatenateTextText");
- // norm!(success_unit_OperatorTimesLhsOne, "unit/OperatorTimesLhsOne");
- // norm!(success_unit_OperatorTimesLhsZero, "unit/OperatorTimesLhsZero");
- // norm!(success_unit_OperatorTimesNormalizeArguments, "unit/OperatorTimesNormalizeArguments");
- // norm!(success_unit_OperatorTimesRhsOne, "unit/OperatorTimesRhsOne");
- // norm!(success_unit_OperatorTimesRhsZero, "unit/OperatorTimesRhsZero");
+ norm!(success_unit_OperatorTimesLhsOne, "unit/OperatorTimesLhsOne");
+ norm!(success_unit_OperatorTimesLhsZero, "unit/OperatorTimesLhsZero");
+ norm!(success_unit_OperatorTimesNormalizeArguments, "unit/OperatorTimesNormalizeArguments");
+ norm!(success_unit_OperatorTimesRhsOne, "unit/OperatorTimesRhsOne");
+ norm!(success_unit_OperatorTimesRhsZero, "unit/OperatorTimesRhsZero");
norm!(success_unit_OperatorTimesTwoAndTwo, "unit/OperatorTimesTwoAndTwo");
norm!(success_unit_Optional, "unit/Optional");
norm!(success_unit_OptionalBuild, "unit/OptionalBuild");
@@ -675,7 +1124,7 @@ mod spec_tests {
norm!(success_unit_SomeNormalizeArguments, "unit/SomeNormalizeArguments");
norm!(success_unit_Sort, "unit/Sort");
norm!(success_unit_Text, "unit/Text");
- // norm!(success_unit_TextInterpolate, "unit/TextInterpolate");
+ norm!(success_unit_TextInterpolate, "unit/TextInterpolate");
norm!(success_unit_TextLiteral, "unit/TextLiteral");
norm!(success_unit_TextNormalizeInterpolations, "unit/TextNormalizeInterpolations");
norm!(success_unit_TextShow, "unit/TextShow");
diff --git a/dhall/src/typecheck.rs b/dhall/src/typecheck.rs
index 5aaeb08..b26f845 100644
--- a/dhall/src/typecheck.rs
+++ b/dhall/src/typecheck.rs
@@ -44,9 +44,9 @@ impl<'a> Normalized<'a> {
fn unroll_ref(&self) -> &Expr<X, X> {
self.as_expr().as_ref()
}
- fn shift(&self, delta: isize, var: &V<Label>) -> Self {
+ fn shift0(&self, delta: isize, label: &Label) -> Self {
// shift the type too ?
- Normalized(shift(delta, var, &self.0), self.1.clone(), self.2)
+ Normalized(shift0(delta, label, &self.0), self.1.clone(), self.2)
}
}
impl Normalized<'static> {
@@ -86,10 +86,10 @@ impl<'a> Type<'a> {
Cow::Owned(e) => Ok(Cow::Owned(e.into_expr().unroll())),
}
}
- fn shift(&self, delta: isize, var: &V<Label>) -> Self {
+ fn shift0(&self, delta: isize, label: &Label) -> Self {
use TypeInternal::*;
Type(match &self.0 {
- Expr(e) => Expr(Box::new(e.shift(delta, var))),
+ Expr(e) => Expr(Box::new(e.shift0(delta, label))),
Const(c) => Const(*c),
SuperType => SuperType,
})
@@ -168,11 +168,7 @@ where
eq2
}
}
- (App(fL, aL), App(fR, aR)) => {
- go(ctx, fL, fR)
- && aL.len() == aR.len()
- && aL.iter().zip(aR.iter()).all(|(aL, aR)| go(ctx, aL, aR))
- }
+ (App(fL, aL), App(fR, aR)) => go(ctx, fL, fR) && go(ctx, aL, aR),
(RecordType(ktsL0), RecordType(ktsR0)) => {
ktsL0.len() == ktsR0.len()
&& ktsL0
@@ -378,9 +374,8 @@ fn type_with(
let ret = match e.as_ref() {
Lam(x, t, b) => {
let t = mktype(ctx, t.clone())?;
- let ctx2 = ctx
- .insert(x.clone(), t.clone())
- .map(|e| e.shift(1, &V(x.clone(), 0)));
+ let ctx2 =
+ ctx.insert(x.clone(), t.clone()).map(|_, e| e.shift0(1, x));
let b = type_with(&ctx2, b.clone())?;
Ok(RetExpr(Pi(
x.clone(),
@@ -395,9 +390,8 @@ fn type_with(
mkerr(InvalidInputType(ta.into_normalized()?)),
);
- let ctx2 = ctx
- .insert(x.clone(), ta.clone())
- .map(|e| e.shift(1, &V(x.clone(), 0)));
+ let ctx2 =
+ ctx.insert(x.clone(), ta.clone()).map(|_, e| e.shift0(1, x));
let tb = type_with(&ctx2, tb.clone())?;
let kB = ensure_is_const!(
&tb.get_type()?,
@@ -476,46 +470,22 @@ fn type_last_layer(
Some(e) => Ok(RetType(e.clone())),
None => Err(mkerr(UnboundVariable)),
},
- App(f, args) => {
- let mut tf = f.get_type()?.into_owned();
- // Reconstruct the application `f a0 a1 ...`
- // for error reporting
- let mkf = |args: Vec<_>, i| {
- rc(App(
- f.into_expr(),
- args.into_iter().take(i).map(Typed::into_expr).collect(),
- ))
- };
-
- for (i, a) in args.iter().enumerate() {
- let (x, tx, tb) = ensure_matches!(tf,
- Pi(x, tx, tb) => (x, tx, tb),
- mkerr(NotAFunction(Typed(
- mkf(args, i),
- Some(tf),
- PhantomData
- )))
- );
- let tx = mktype(ctx, tx.embed_absurd())?;
- ensure_equal!(&tx, a.get_type()?, {
- let a = a.clone();
- mkerr(TypeMismatch(
- Typed(mkf(args, i + 1), Some(tf), PhantomData),
- tx.into_normalized()?,
- a,
- ))
- });
- tf = mktype(
- ctx,
- rc(Let(
- x.clone(),
- None,
- a.clone().normalize().embed(),
- tb.embed_absurd(),
- )),
- )?;
- }
- Ok(RetType(tf))
+ App(f, a) => {
+ let tf = f.get_type()?;
+ let (x, tx, tb) = ensure_matches!(tf,
+ Pi(x, tx, tb) => (x, tx, tb),
+ mkerr(NotAFunction(f))
+ );
+ let tx = mktype(ctx, tx.embed_absurd())?;
+ ensure_equal!(a.get_type()?, &tx, {
+ mkerr(TypeMismatch(f, tx.into_normalized()?, a))
+ });
+ Ok(RetExpr(Let(
+ x.clone(),
+ None,
+ a.normalize().embed(),
+ tb.embed_absurd(),
+ )))
}
Annot(x, t) => {
let t = t.normalize().into_type();
@@ -593,13 +563,7 @@ fn type_last_layer(
let e = dhall::subexpr!(Some x : Optional t);
Ok(RetType(type_with(ctx, e)?.get_type()?.into_owned()))
}
- EmptyOptionalLit(t) => {
- let t = t.normalize();
- ensure_simple_type!(t, mkerr(InvalidOptionalType(t)));
- let t = t.embed();
- Ok(RetExpr(dhall::expr!(Optional t)))
- }
- NEOptionalLit(x) => {
+ SomeLit(x) => {
let tx = x.get_type_move()?;
ensure_simple_type!(
tx,
@@ -706,7 +670,7 @@ fn type_last_layer(
TextLit(_) => Ok(RetType(simple_type_from_builtin(Text))),
BinOp(o @ ListAppend, l, r) => {
match l.get_type()?.unroll_ref()?.as_ref() {
- App(f, args) if args.len() == 1 => match f.as_ref() {
+ App(f, _) => match f.as_ref() {
Builtin(List) => {}
_ => return Err(mkerr(BinOpTypeMismatch(o, l))),
},
diff --git a/dhall_core/Cargo.toml b/dhall_core/Cargo.toml
index a2aced0..80cf721 100644
--- a/dhall_core/Cargo.toml
+++ b/dhall_core/Cargo.toml
@@ -12,4 +12,4 @@ doctest = false
itertools = "0.8.0"
pest = "2.1"
dhall_generated_parser = { path = "../dhall_generated_parser" }
-improved_slice_patterns = { version = "1.0.1", path = "../improved_slice_patterns" }
+improved_slice_patterns = { version = "2.0.0", path = "../improved_slice_patterns" }
diff --git a/dhall_core/src/context.rs b/dhall_core/src/context.rs
index 877843d..55bfff5 100644
--- a/dhall_core/src/context.rs
+++ b/dhall_core/src/context.rs
@@ -32,17 +32,39 @@ impl<K: Hash + Eq + Clone, T> Context<K, T> {
/// lookup k n (insert j v c) = lookup k n c -- k /= j
/// ```
pub fn lookup<'a>(&'a self, k: &K, n: usize) -> Option<&'a T> {
- self.0.get(k).and_then(|v| v.get(v.len() - 1 - n))
+ self.0.get(k).and_then(|v| {
+ if n < v.len() {
+ v.get(v.len() - 1 - n)
+ } else {
+ None
+ }
+ })
}
- pub fn map<U, F: Fn(&T) -> U>(&self, f: F) -> Context<K, U> {
+ pub fn map<U, F: Fn(&K, &T) -> U>(&self, f: F) -> Context<K, U> {
Context(
self.0
.iter()
- .map(|(k, v)| ((*k).clone(), v.iter().map(&f).collect()))
+ .map(|(k, vs)| {
+ ((*k).clone(), vs.iter().map(|v| f(k, v)).collect())
+ })
.collect(),
)
}
+
+ pub fn lookup_all<'a>(&'a self, k: &K) -> impl Iterator<Item = &T> {
+ self.0.get(k).into_iter().flat_map(|v| v.iter())
+ }
+
+ pub fn iter<'a>(&'a self) -> impl Iterator<Item = (&K, &T)> {
+ self.0
+ .iter()
+ .flat_map(|(k, vs)| vs.iter().map(move |v| (k, v)))
+ }
+
+ pub fn iter_keys<'a>(&'a self) -> impl Iterator<Item = (&K, &Vec<T>)> {
+ self.0.iter()
+ }
}
impl<K: Hash + Eq + Clone, T: Clone> Context<K, T> {
diff --git a/dhall_core/src/core.rs b/dhall_core/src/core.rs
index aeb6f23..fa6fca4 100644
--- a/dhall_core/src/core.rs
+++ b/dhall_core/src/core.rs
@@ -1,7 +1,9 @@
#![allow(non_snake_case)]
use std::collections::BTreeMap;
+use std::collections::HashMap;
use std::rc::Rc;
+use crate::context::Context;
use crate::visitor;
use crate::*;
@@ -148,7 +150,7 @@ pub enum ExprF<SubExpr, Label, Note, Embed> {
/// `∀(x : A) -> B`
Pi(Label, SubExpr, SubExpr),
/// `f a`
- App(SubExpr, Vec<SubExpr>),
+ App(SubExpr, SubExpr),
/// `let x = r in e`
/// `let x : t = r in e`
Let(Label, Option<SubExpr>, SubExpr, SubExpr),
@@ -178,10 +180,8 @@ pub enum ExprF<SubExpr, Label, Note, Embed> {
/// `[] : Optional a`
/// `[x] : Optional a`
OldOptionalLit(Option<SubExpr>, SubExpr),
- /// `None t`
- EmptyOptionalLit(SubExpr),
/// `Some e`
- NEOptionalLit(SubExpr),
+ SomeLit(SubExpr),
/// `{ k1 : t1, k2 : t1 }`
RecordType(BTreeMap<Label, SubExpr>),
/// `{ k1 = v1, k2 = v2 }`
@@ -190,8 +190,6 @@ pub enum ExprF<SubExpr, Label, Note, Embed> {
UnionType(BTreeMap<Label, Option<SubExpr>>),
/// `< k1 = t1, k2 : t2, k3 >`
UnionLit(Label, SubExpr, BTreeMap<Label, Option<SubExpr>>),
- /// `< k1 : t1, k2 >.k1`
- UnionConstructor(Label, BTreeMap<Label, Option<SubExpr>>),
/// `merge x y : t`
Merge(SubExpr, SubExpr, Option<SubExpr>),
/// `e.x`
@@ -486,6 +484,7 @@ fn shift_var(delta: isize, var: &V<Label>, in_expr: &V<Label>) -> V<Label> {
/// capture by shifting variable indices
/// See https://github.com/dhall-lang/dhall-lang/blob/master/standard/semantics.md#shift
/// for details
+///
pub fn shift<N, E>(
delta: isize,
var: &V<Label>,
@@ -505,6 +504,41 @@ pub fn shift<N, E>(
}
}
+pub fn shift0<N, E>(
+ delta: isize,
+ label: &Label,
+ in_expr: &SubExpr<N, E>,
+) -> SubExpr<N, E> {
+ shift(delta, &V(label.clone(), 0), in_expr)
+}
+
+fn shift0_multiple<N, E>(
+ deltas: &HashMap<Label, isize>,
+ in_expr: &SubExpr<N, E>,
+) -> SubExpr<N, E> {
+ shift0_multiple_inner(&Context::new(), deltas, in_expr)
+}
+
+fn shift0_multiple_inner<N, E>(
+ ctx: &Context<Label, ()>,
+ deltas: &HashMap<Label, isize>,
+ in_expr: &SubExpr<N, E>,
+) -> SubExpr<N, E> {
+ use crate::ExprF::*;
+ match in_expr.as_ref() {
+ Var(V(y, m)) if ctx.lookup(y, *m).is_none() => {
+ let delta = deltas.get(y).unwrap_or(&0);
+ rc(Var(V(y.clone(), add_ui(*m, *delta))))
+ }
+ _ => in_expr.map_subexprs_with_special_handling_of_binders(
+ |e| shift0_multiple_inner(ctx, deltas, e),
+ |l: &Label, e| {
+ shift0_multiple_inner(&ctx.insert(l.clone(), ()), deltas, e)
+ },
+ ),
+ }
+}
+
/// Substitute all occurrences of a variable with an expression, and
/// removes the variable from the environment by shifting the indices
/// of other variables appropriately.
@@ -518,15 +552,29 @@ pub fn subst_shift<N, E>(
value: &SubExpr<N, E>,
in_expr: &SubExpr<N, E>,
) -> SubExpr<N, E> {
+ subst_shift_inner(&HashMap::new(), var, value, in_expr)
+}
+
+fn subst_shift_inner<N, E>(
+ ctx: &HashMap<Label, isize>,
+ var: &V<Label>,
+ value: &SubExpr<N, E>,
+ in_expr: &SubExpr<N, E>,
+) -> SubExpr<N, E> {
use crate::ExprF::*;
+ let V(x, n) = var;
+ let dn = ctx.get(x).unwrap_or(&0);
+ let actual_var = V(x.clone(), add_ui(*n, *dn));
match in_expr.as_ref() {
- Var(v) if v == var => SubExpr::clone(value),
- Var(v) => rc(Var(shift_var(-1, var, v))),
+ Var(v) if v == &actual_var => shift0_multiple(ctx, value),
+ Var(v) => rc(Var(shift_var(-1, &actual_var, v))),
_ => in_expr.map_subexprs_with_special_handling_of_binders(
- |e| subst_shift(var, &value, e),
+ |e| subst_shift_inner(ctx, var, value, e),
|l: &Label, e| {
- let vl = V(l.clone(), 0);
- subst_shift(&shift_var(1, &vl, var), &shift(1, &vl, value), e)
+ let mut ctx = ctx.clone();
+ let count = ctx.entry(l.clone()).or_insert(0);
+ *count += 1;
+ subst_shift_inner(&ctx, var, value, e)
},
),
}
diff --git a/dhall_core/src/parser.rs b/dhall_core/src/parser.rs
index 2a30b2b..ba15bae 100644
--- a/dhall_core/src/parser.rs
+++ b/dhall_core/src/parser.rs
@@ -176,7 +176,7 @@ macro_rules! make_parser {
[x..] => Err(
format!("Unexpected children: {:?}", x.collect::<Vec<_>>())
)?,
- ).ok_or_else(|| -> String { unreachable!() })?;
+ ).map_err(|_| -> String { unreachable!() })?;
Ok(ParsedValue::$group(res))
});
(@body,
@@ -743,10 +743,10 @@ make_parser! {
token_rule!(Some_<()>);
- rule!(application_expression<ParsedExpr<'a>> as expression; span; children!(
+ rule!(application_expression<ParsedExpr<'a>> as expression; children!(
[expression(e)] => e,
[expression(first), expression(rest)..] => {
- spanned(span, App(rc(first), rest.map(rc).collect()))
+ rest.fold(first, |acc, e| App(rc(acc), rc(e)))
},
));
@@ -754,7 +754,7 @@ make_parser! {
children!(
[expression(e)] => e,
[Some_(()), expression(e)] => {
- spanned(span, NEOptionalLit(rc(e)))
+ spanned(span, SomeLit(rc(e)))
},
[merge(()), expression(x), expression(y)] => {
spanned(span, Merge(rc(x), rc(y), None))
diff --git a/dhall_core/src/printer.rs b/dhall_core/src/printer.rs
index 4d1ae2d..c4bad71 100644
--- a/dhall_core/src/printer.rs
+++ b/dhall_core/src/printer.rs
@@ -38,10 +38,7 @@ impl<SE: Display + Clone, N, E: Display> Display for ExprF<SE, Label, N, E> {
OldOptionalLit(Some(x), t) => {
write!(f, "[{}] : Optional {}", x, t)?;
}
- EmptyOptionalLit(t) => {
- write!(f, "None {}", t)?;
- }
- NEOptionalLit(e) => {
+ SomeLit(e) => {
write!(f, "Some {}", e)?;
}
Merge(a, b, c) => {
@@ -56,12 +53,8 @@ impl<SE: Display + Clone, N, E: Display> Display for ExprF<SE, Label, N, E> {
ExprF::BinOp(op, a, b) => {
write!(f, "{} {} {}", a, op, b)?;
}
- ExprF::App(a, args) => {
- a.fmt(f)?;
- for x in args {
- f.write_str(" ")?;
- x.fmt(f)?;
- }
+ ExprF::App(a, b) => {
+ write!(f, "{} {}", a, b)?;
}
Field(a, b) => {
write!(f, "{}.{}", a, b)?;
@@ -108,16 +101,6 @@ impl<SE: Display + Clone, N, E: Display> Display for ExprF<SE, Label, N, E> {
}
f.write_str(" >")?
}
- UnionConstructor(x, map) => {
- fmt_list("< ", " | ", " >", map, f, |(k, v), f| {
- write!(f, "{}", k)?;
- if let Some(v) = v {
- write!(f, ": {}", v)?;
- }
- Ok(())
- })?;
- write!(f, ".{}", x)?
- }
Embed(a) => a.fmt(f)?,
Note(_, b) => b.fmt(f)?,
}
@@ -173,8 +156,7 @@ impl<S: Clone, A: Display + Clone> Expr<S, A> {
| EmptyListLit(_)
| NEListLit(_)
| OldOptionalLit(_, _)
- | EmptyOptionalLit(_)
- | NEOptionalLit(_)
+ | SomeLit(_)
| Merge(_, _, _)
| Annot(_, _)
if phase > Base =>
@@ -214,12 +196,8 @@ impl<S: Clone, A: Display + Clone> Expr<S, A> {
),
EmptyListLit(t) => EmptyListLit(t.phase(Import)),
OldOptionalLit(x, t) => OldOptionalLit(x, t.phase(Import)),
- EmptyOptionalLit(t) => EmptyOptionalLit(t.phase(Import)),
- NEOptionalLit(e) => NEOptionalLit(e.phase(Import)),
- ExprF::App(a, args) => ExprF::App(
- a.phase(Import),
- args.into_iter().map(|x| x.phase(Import)).collect(),
- ),
+ SomeLit(e) => SomeLit(e.phase(Import)),
+ ExprF::App(f, a) => ExprF::App(f.phase(Import), a.phase(Import)),
Field(a, b) => Field(a.phase(Primitive), b),
Projection(e, ls) => Projection(e.phase(Primitive), ls),
Note(n, b) => Note(n, b.phase(phase)),
diff --git a/dhall_core/src/text.rs b/dhall_core/src/text.rs
index 0cfbd7b..83643d9 100644
--- a/dhall_core/src/text.rs
+++ b/dhall_core/src/text.rs
@@ -1,5 +1,4 @@
use std::iter::FromIterator;
-use std::ops::Add;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct InterpolatedText<SubExpr> {
@@ -33,6 +32,16 @@ pub enum InterpolatedTextContents<SubExpr> {
Expr(SubExpr),
}
+impl<SubExpr> InterpolatedTextContents<SubExpr> {
+ pub fn is_empty(&self) -> bool {
+ use InterpolatedTextContents::{Expr, Text};
+ match self {
+ Expr(_) => false,
+ Text(s) => s.is_empty(),
+ }
+ }
+}
+
impl<SubExpr> InterpolatedText<SubExpr> {
pub fn traverse_ref<'a, SubExpr2, E, F>(
&'a self,
@@ -51,13 +60,6 @@ impl<SubExpr> InterpolatedText<SubExpr> {
})
}
- pub fn as_ref(&self) -> InterpolatedText<&SubExpr> {
- InterpolatedText {
- head: self.head.clone(),
- tail: self.tail.iter().map(|(e, s)| (e, s.clone())).collect(),
- }
- }
-
pub fn iter<'a>(
&'a self,
) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> + 'a
@@ -65,16 +67,30 @@ impl<SubExpr> InterpolatedText<SubExpr> {
SubExpr: Clone,
{
use std::iter::once;
- once(InterpolatedTextContents::Text(self.head.clone())).chain(
- self.tail.iter().flat_map(|(e, s)| {
- once(InterpolatedTextContents::Expr(SubExpr::clone(e)))
- .chain(once(InterpolatedTextContents::Text(s.clone())))
- }),
- )
+ use InterpolatedTextContents::{Expr, Text};
+ once(Text(self.head.clone()))
+ .chain(self.tail.iter().flat_map(|(e, s)| {
+ once(Expr(SubExpr::clone(e))).chain(once(Text(s.clone())))
+ }))
+ .filter(|c| !c.is_empty())
+ }
+
+ pub fn into_iter(
+ self,
+ ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> {
+ use std::iter::once;
+ use InterpolatedTextContents::{Expr, Text};
+ once(Text(self.head))
+ .chain(
+ self.tail
+ .into_iter()
+ .flat_map(|(e, s)| once(Expr(e)).chain(once(Text(s)))),
+ )
+ .filter(|c| !c.is_empty())
}
}
-impl<'a, SubExpr: Clone + 'a> FromIterator<InterpolatedTextContents<SubExpr>>
+impl<SubExpr> FromIterator<InterpolatedTextContents<SubExpr>>
for InterpolatedText<SubExpr>
{
fn from_iter<T>(iter: T) -> Self
@@ -82,15 +98,15 @@ impl<'a, SubExpr: Clone + 'a> FromIterator<InterpolatedTextContents<SubExpr>>
T: IntoIterator<Item = InterpolatedTextContents<SubExpr>>,
{
let mut res = InterpolatedText {
- head: "".to_owned(),
- tail: vec![],
+ head: String::new(),
+ tail: Vec::new(),
};
let mut crnt_str = &mut res.head;
for x in iter.into_iter() {
match x {
InterpolatedTextContents::Text(s) => crnt_str.push_str(&s),
InterpolatedTextContents::Expr(e) => {
- res.tail.push((e.clone(), "".to_owned()));
+ res.tail.push((e, String::new()));
crnt_str = &mut res.tail.last_mut().unwrap().1;
}
}
@@ -98,10 +114,3 @@ impl<'a, SubExpr: Clone + 'a> FromIterator<InterpolatedTextContents<SubExpr>>
res
}
}
-
-impl<SubExpr: Clone> Add for &InterpolatedText<SubExpr> {
- type Output = InterpolatedText<SubExpr>;
- fn add(self, rhs: &InterpolatedText<SubExpr>) -> Self::Output {
- self.iter().chain(rhs.iter()).collect()
- }
-}
diff --git a/dhall_core/src/visitor.rs b/dhall_core/src/visitor.rs
index 16ad418..caaefce 100644
--- a/dhall_core/src/visitor.rs
+++ b/dhall_core/src/visitor.rs
@@ -130,9 +130,7 @@ where
let (l, e) = v.visit_binder(l, e)?;
Let(l, t, a, e)
}
- App(f, args) => {
- App(v.visit_subexpr(f)?, vec(args, |e| v.visit_subexpr(e))?)
- }
+ App(f, a) => App(v.visit_subexpr(f)?, v.visit_subexpr(a)?),
Annot(x, t) => Annot(v.visit_subexpr(x)?, v.visit_subexpr(t)?),
Const(k) => Const(*k),
Builtin(v) => Builtin(*v),
@@ -155,8 +153,7 @@ where
opt(x, |e| v.visit_subexpr(e))?,
v.visit_subexpr(t)?,
),
- EmptyOptionalLit(t) => EmptyOptionalLit(v.visit_subexpr(t)?),
- NEOptionalLit(e) => NEOptionalLit(v.visit_subexpr(e)?),
+ SomeLit(e) => SomeLit(v.visit_subexpr(e)?),
RecordType(kts) => RecordType(btmap(kts, v)?),
RecordLit(kvs) => RecordLit(btmap(kvs, v)?),
UnionType(kts) => UnionType(btoptmap(kts, v)?),
@@ -165,9 +162,6 @@ where
v.visit_subexpr(x)?,
btoptmap(kts, v)?,
),
- UnionConstructor(x, kts) => {
- UnionConstructor(v.visit_label(x)?, btoptmap(kts, v)?)
- }
Merge(x, y, t) => Merge(
v.visit_subexpr(x)?,
v.visit_subexpr(y)?,
diff --git a/dhall_generator/src/quote.rs b/dhall_generator/src/quote.rs
index 400c12c..c588eda 100644
--- a/dhall_generator/src/quote.rs
+++ b/dhall_generator/src/quote.rs
@@ -43,7 +43,6 @@ where
quote! { dhall_core::ExprF::Lam(#x, #t, #b) }
}
App(f, a) => {
- let a = quote_vec(a);
quote! { dhall_core::ExprF::App(#f, #a) }
}
Annot(x, t) => {
@@ -67,11 +66,8 @@ where
BoolLit(b) => {
quote! { dhall_core::ExprF::BoolLit(#b) }
}
- EmptyOptionalLit(x) => {
- quote! { dhall_core::ExprF::EmptyOptionalLit(#x) }
- }
- NEOptionalLit(x) => {
- quote! { dhall_core::ExprF::NEOptionalLit(#x) }
+ SomeLit(x) => {
+ quote! { dhall_core::ExprF::SomeLit(#x) }
}
EmptyListLit(t) => {
quote! { dhall_core::ExprF::EmptyListLit(#t) }
diff --git a/improved_slice_patterns/Cargo.toml b/improved_slice_patterns/Cargo.toml
index 9c99e0d..a5815e8 100644
--- a/improved_slice_patterns/Cargo.toml
+++ b/improved_slice_patterns/Cargo.toml
@@ -1,6 +1,6 @@
[package]
name = "improved_slice_patterns"
-version = "1.0.1" # remember to update html_root_url
+version = "2.0.0" # remember to update html_root_url
authors = ["Nadrieril <nadrieril@users.noreply.github.com>"]
license = "MIT OR Apache-2.0"
edition = "2018"
diff --git a/improved_slice_patterns/README.md b/improved_slice_patterns/README.md
index ab8fd7e..7f07530 100644
--- a/improved_slice_patterns/README.md
+++ b/improved_slice_patterns/README.md
@@ -5,6 +5,13 @@ on `Vec`s and iterators using the syntax of [`slice_patterns`][slice_patterns]
[slice_patterns]: https://doc.rust-lang.org/nightly/unstable-book/language-features/slice-patterns.html
+## Changelog
+
+### V2.0
+
+- `match_vec` now returns a `Result` instead of an `Option`. The `Err` variant
+is used to return ownership of the passed vec if there was no match.
+
## License
Licensed under either of
diff --git a/improved_slice_patterns/src/lib.rs b/improved_slice_patterns/src/lib.rs
index 3e459bb..5478c1b 100644
--- a/improved_slice_patterns/src/lib.rs
+++ b/improved_slice_patterns/src/lib.rs
@@ -1,5 +1,5 @@
#![feature(slice_patterns)]
-#![doc(html_root_url = "https://docs.rs/improved_slice_patterns/1.0.1")]
+#![doc(html_root_url = "https://docs.rs/improved_slice_patterns/2.0.0")]
//! A tiny crate that provides two macros to help matching
//! on `Vec`s and iterators using the syntax of
@@ -127,8 +127,8 @@ macro_rules! destructure_iter {
/// Pattern-match on a vec using the syntax of slice_patterns.
///
-/// Wraps the match body in `Some` if there was a match; returns
-/// `None` otherwise.
+/// Wraps the match body in `Ok` if there was a match; returns
+/// an `Err` containing the ownership of the vec otherwise.
///
/// Contrary to slice_patterns, this allows moving out
/// of the `Vec`.
@@ -152,7 +152,7 @@ macro_rules! destructure_iter {
/// [..] => vec![]
/// );
///
-/// assert_eq!(res, Some(vec![Some(2), Some(3)]));
+/// assert_eq!(res, Ok(vec![Some(2), Some(3)]));
///
///
/// let vec = vec![Some(1), Some(2), Some(3), None];
@@ -166,7 +166,7 @@ macro_rules! destructure_iter {
/// },
/// );
///
-/// assert_eq!(res, None); // there was no match
+/// assert!(res.is_err()); // there was no match
///
/// # Ok::<(), ()>(())
/// ```
@@ -259,10 +259,17 @@ macro_rules! match_vec {
// Actually consume the values
#[allow(unused_mut)]
let mut iter = vec.into_iter();
- $crate::destructure_iter!(iter; [$($args)*] => $body)
+ let ret =
+ $crate::destructure_iter!(iter;
+ [$($args)*] => $body
+ );
+ match ret {
+ Some(x) => Ok(x),
+ None => unreachable!(), // Hopefully
+ }
}
)*
- _ => std::option::Option::None,
+ _ => std::result::Result::Err(vec),
}
}
};
@@ -294,9 +301,16 @@ fn test() {
assert_eq!(test(vec![Some(0), None, Some(1)]), -1);
// Test move out of pattern
+ #[derive(Debug)]
struct Foo;
- let _: (Foo, Foo) = match_vec!(vec![Some(Foo), Some(Foo)].into_iter();
+ let _: (Foo, Foo) = match_vec!(vec![Some(Foo), Some(Foo)];
[Some(f1), Some(f2)] => (f1, f2),
)
.unwrap();
+
+ // Test return ownership if no match
+ let _: Vec<Foo> = match_vec!(vec![Foo];
+ [] => "Error".to_string(),
+ )
+ .unwrap_err();
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-27 18:27:11 +0000