diff options
author | Fintan Halpenny | 2019-09-02 23:09:26 +0100 |
---|---|---|
committer | Fintan Halpenny | 2019-09-02 23:09:26 +0100 |
commit | 8553b398a5f97eed240f5360282e911392cab6ff (patch) | |
tree | 076d554b7e066cf854aa50f350096ce55e3bd691 /dhall_syntax/src/core/expr.rs | |
parent | e73f822b6972e8fa2e72b56ff5378b91bea1a5e6 (diff) | |
parent | 737abd9be6d35bbce784d9cf249edf7ad14677d6 (diff) |
Merge remote-tracking branch 'origin/master' into fintan/canonicalize
Diffstat (limited to '')
-rw-r--r-- | dhall_syntax/src/core/expr.rs | 291 |
1 files changed, 117 insertions, 174 deletions
diff --git a/dhall_syntax/src/core/expr.rs b/dhall_syntax/src/core/expr.rs index 6522cb1..51b6c47 100644 --- a/dhall_syntax/src/core/expr.rs +++ b/dhall_syntax/src/core/expr.rs @@ -8,14 +8,34 @@ pub type Integer = isize; pub type Natural = usize; pub type Double = NaiveDouble; -/// An empty type -#[derive(Debug, Copy, Clone, PartialEq, Eq)] -pub enum X {} - -pub fn trivial_result<T>(x: Result<T, X>) -> T { +pub fn trivial_result<T>(x: Result<T, !>) -> T { match x { Ok(x) => x, - Err(e) => match e {}, + Err(e) => e, + } +} + +/// A location in the source text +#[derive(Debug, Clone)] +pub struct Span { + input: Rc<str>, + /// # Safety + /// + /// Must be a valid character boundary index into `input`. + start: usize, + /// # Safety + /// + /// Must be a valid character boundary index into `input`. + end: usize, +} + +impl Span { + pub(crate) fn make(input: Rc<str>, sp: pest::Span) -> Self { + Span { + input, + start: sp.start(), + end: sp.end(), + } } } @@ -31,6 +51,15 @@ impl PartialEq for NaiveDouble { impl Eq for NaiveDouble {} +impl std::hash::Hash for NaiveDouble { + fn hash<H>(&self, state: &mut H) + where + H: std::hash::Hasher, + { + self.0.to_bits().hash(state) + } +} + impl From<f64> for NaiveDouble { fn from(x: f64) -> Self { NaiveDouble(x) @@ -44,7 +73,7 @@ impl From<NaiveDouble> for f64 { } /// Constants for a pure type system -#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)] +#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] pub enum Const { Type, Kind, @@ -56,7 +85,7 @@ pub enum Const { /// The `Label` field is the variable's name (i.e. \"`x`\"). /// The `Int` field is a DeBruijn index. /// See dhall-lang/standard/semantics.md for details -#[derive(Debug, Clone, PartialEq, Eq)] +#[derive(Debug, Clone, PartialEq, Eq, Hash)] pub struct V<Label>(pub Label, pub usize); // This is only for the specific `Label` type, not generic @@ -73,7 +102,7 @@ impl<'a> From<&'a Label> for V<Label> { // Definition order must match precedence order for // pretty-printing to work correctly -#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)] +#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] pub enum BinOp { /// `x ? y` ImportAlt, @@ -104,7 +133,7 @@ pub enum BinOp { } /// Built-ins -#[derive(Debug, Copy, Clone, PartialEq, Eq)] +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] pub enum Builtin { Bool, Natural, @@ -137,29 +166,34 @@ pub enum Builtin { TextShow, } -pub type ParsedExpr = SubExpr<X, Import>; -pub type ResolvedExpr = SubExpr<X, X>; -pub type DhallExpr = ResolvedExpr; +// Each node carries an annotation. +#[derive(Debug, Clone)] +pub struct Expr<Embed>(Box<(RawExpr<Embed>, Option<Span>)>); -// Each node carries an annotation. In practice it's either X (no annotation) or a Span. -#[derive(Debug)] -pub struct SubExpr<Note, Embed>(Rc<(Expr<Note, Embed>, Option<Note>)>); +pub type RawExpr<Embed> = ExprF<Expr<Embed>, Embed>; -impl<Note, Embed: PartialEq> std::cmp::PartialEq for SubExpr<Note, Embed> { +impl<Embed: PartialEq> std::cmp::PartialEq for Expr<Embed> { fn eq(&self, other: &Self) -> bool { self.0.as_ref().0 == other.0.as_ref().0 } } -impl<Note, Embed: Eq> std::cmp::Eq for SubExpr<Note, Embed> {} +impl<Embed: Eq> std::cmp::Eq for Expr<Embed> {} -pub type Expr<Note, Embed> = ExprF<SubExpr<Note, Embed>, Embed>; +impl<Embed: std::hash::Hash> std::hash::Hash for Expr<Embed> { + fn hash<H>(&self, state: &mut H) + where + H: std::hash::Hasher, + { + (self.0).0.hash(state) + } +} /// Syntax tree for expressions // Having the recursion out of the enum definition enables writing // much more generic code and improves pattern-matching behind // smart pointers. -#[derive(Debug, Clone, PartialEq, Eq)] +#[derive(Debug, Clone, PartialEq, Eq, Hash)] pub enum ExprF<SubExpr, Embed> { Const(Const), /// `x` @@ -209,11 +243,15 @@ pub enum ExprF<SubExpr, Embed> { UnionType(DupTreeMap<Label, Option<SubExpr>>), /// `merge x y : t` Merge(SubExpr, SubExpr, Option<SubExpr>), + /// `toMap x : t` + ToMap(SubExpr, Option<SubExpr>), /// `e.x` Field(SubExpr, Label), /// `e.{ x, y, z }` Projection(SubExpr, DupTreeSet<Label>), - /// Embeds an import or the result of resolving the import + /// `./some/path` + Import(Import<SubExpr>), + /// Embeds the result of resolving an import Embed(Embed), } @@ -225,229 +263,134 @@ impl<SE, E> ExprF<SE, E> { v.visit(self) } - pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, E2, Err>( + pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>( &'a self, visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>, visit_under_binder: impl FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>, - visit_embed: impl FnOnce(&'a E) -> Result<E2, Err>, - ) -> Result<ExprF<SE2, E2>, Err> { + ) -> Result<ExprF<SE2, E>, Err> + where + E: Clone, + { self.visit(visitor::TraverseRefWithBindersVisitor { visit_subexpr, visit_under_binder, - visit_embed, }) } - fn traverse_ref<'a, SE2, E2, Err>( + fn traverse_ref<'a, SE2, Err>( &'a self, visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>, - visit_embed: impl FnOnce(&'a E) -> Result<E2, Err>, - ) -> Result<ExprF<SE2, E2>, Err> { - self.visit(visitor::TraverseRefVisitor { - visit_subexpr, - visit_embed, - }) + ) -> Result<ExprF<SE2, E>, Err> + where + E: Clone, + { + self.visit(visitor::TraverseRefVisitor { visit_subexpr }) } - pub fn map_ref_with_special_handling_of_binders<'a, SE2, E2>( + pub fn map_ref_with_special_handling_of_binders<'a, SE2>( &'a self, mut map_subexpr: impl FnMut(&'a SE) -> SE2, mut map_under_binder: impl FnMut(&'a Label, &'a SE) -> SE2, - map_embed: impl FnOnce(&'a E) -> E2, - ) -> ExprF<SE2, E2> { + ) -> ExprF<SE2, E> + where + E: Clone, + { trivial_result(self.traverse_ref_with_special_handling_of_binders( |x| Ok(map_subexpr(x)), |l, x| Ok(map_under_binder(l, x)), - |x| Ok(map_embed(x)), )) } - pub fn map_ref<'a, SE2, E2>( + pub fn map_ref<'a, SE2>( &'a self, mut map_subexpr: impl FnMut(&'a SE) -> SE2, - map_embed: impl FnOnce(&'a E) -> E2, - ) -> ExprF<SE2, E2> { - trivial_result( - self.traverse_ref(|x| Ok(map_subexpr(x)), |x| Ok(map_embed(x))), - ) - } - - pub fn traverse_ref_simple<'a, SE2, Err>( - &'a self, - visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>, - ) -> Result<ExprF<SE2, E>, Err> - where - E: Clone, - { - self.traverse_ref(visit_subexpr, |x| Ok(E::clone(x))) - } - - pub fn map_ref_simple<'a, SE2>( - &'a self, - map_subexpr: impl Fn(&'a SE) -> SE2, ) -> ExprF<SE2, E> where E: Clone, { - self.map_ref(map_subexpr, E::clone) + trivial_result(self.traverse_ref(|x| Ok(map_subexpr(x)))) } } -impl<N, E> Expr<N, E> { - fn traverse_embed<E2, Err>( - &self, - visit_embed: impl FnMut(&E) -> Result<E2, Err>, - ) -> Result<Expr<N, E2>, Err> - where - N: Clone, - { - self.visit(&mut visitor::TraverseEmbedVisitor(visit_embed)) - } - - fn map_embed<E2>(&self, mut map_embed: impl FnMut(&E) -> E2) -> Expr<N, E2> - where - N: Clone, - { - trivial_result(self.traverse_embed(|x| Ok(map_embed(x)))) - } - +impl<E> RawExpr<E> { pub fn traverse_resolve<E2, Err>( &self, - visit_embed: impl FnMut(&E) -> Result<E2, Err>, - ) -> Result<Expr<N, E2>, Err> - where - N: Clone, - { + visit_import: impl FnMut(&Import<Expr<E2>>) -> Result<E2, Err>, + ) -> Result<RawExpr<E2>, Err> { self.traverse_resolve_with_visitor(&mut visitor::ResolveVisitor( - visit_embed, + visit_import, )) } pub(crate) fn traverse_resolve_with_visitor<E2, Err, F1>( &self, visitor: &mut visitor::ResolveVisitor<F1>, - ) -> Result<Expr<N, E2>, Err> + ) -> Result<RawExpr<E2>, Err> where - N: Clone, - F1: FnMut(&E) -> Result<E2, Err>, + F1: FnMut(&Import<Expr<E2>>) -> Result<E2, Err>, { match self { ExprF::BinOp(BinOp::ImportAlt, l, r) => l .as_ref() .traverse_resolve_with_visitor(visitor) - .or(r.as_ref().traverse_resolve_with_visitor(visitor)), - _ => self.visit(visitor), + .or_else(|_| r.as_ref().traverse_resolve_with_visitor(visitor)), + _ => { + let e = self.visit(&mut *visitor)?; + Ok(match &e { + ExprF::Import(import) => ExprF::Embed((visitor.0)(import)?), + _ => e, + }) + } } } } -impl Expr<X, X> { - pub fn absurd<N, E>(&self) -> Expr<N, E> { - self.visit(&mut visitor::AbsurdVisitor) - } -} - -impl<E: Clone> Expr<X, E> { - pub fn note_absurd<N>(&self) -> Expr<N, E> { - self.visit(&mut visitor::NoteAbsurdVisitor) - } -} - -impl<N, E> SubExpr<N, E> { - pub fn as_ref(&self) -> &Expr<N, E> { +impl<E> Expr<E> { + pub fn as_ref(&self) -> &RawExpr<E> { &self.0.as_ref().0 } - pub fn new(x: Expr<N, E>, n: N) -> Self { - SubExpr(Rc::new((x, Some(n)))) + pub fn new(x: RawExpr<E>, n: Span) -> Self { + Expr(Box::new((x, Some(n)))) } - pub fn from_expr_no_note(x: Expr<N, E>) -> Self { - SubExpr(Rc::new((x, None))) + pub fn from_expr_no_span(x: RawExpr<E>) -> Self { + Expr(Box::new((x, None))) } pub fn from_builtin(b: Builtin) -> Self { - SubExpr::from_expr_no_note(ExprF::Builtin(b)) + Expr::from_expr_no_span(ExprF::Builtin(b)) } - pub fn rewrap<E2>(&self, x: Expr<N, E2>) -> SubExpr<N, E2> - where - N: Clone, - { - SubExpr(Rc::new((x, (self.0).1.clone()))) - } - - pub fn traverse_embed<E2, Err>( - &self, - visit_embed: impl FnMut(&E) -> Result<E2, Err>, - ) -> Result<SubExpr<N, E2>, Err> - where - N: Clone, - { - Ok(self.rewrap(self.as_ref().traverse_embed(visit_embed)?)) - } - - pub fn map_embed<E2>( - &self, - map_embed: impl FnMut(&E) -> E2, - ) -> SubExpr<N, E2> - where - N: Clone, - { - self.rewrap(self.as_ref().map_embed(map_embed)) - } - - pub fn map_subexprs_with_special_handling_of_binders<'a>( - &'a self, - map_expr: impl FnMut(&'a Self) -> Self, - map_under_binder: impl FnMut(&'a Label, &'a Self) -> Self, - ) -> Self - where - N: Clone, - { - match self.as_ref() { - ExprF::Embed(_) => SubExpr::clone(self), - // This calls ExprF::map_ref - e => self.rewrap(e.map_ref_with_special_handling_of_binders( - map_expr, - map_under_binder, - |_| unreachable!(), - )), - } + pub fn rewrap<E2>(&self, x: RawExpr<E2>) -> Expr<E2> { + Expr(Box::new((x, (self.0).1.clone()))) } +} +impl<E> Expr<E> { pub fn traverse_resolve<E2, Err>( &self, - visit_embed: impl FnMut(&E) -> Result<E2, Err>, - ) -> Result<SubExpr<N, E2>, Err> - where - N: Clone, - { - Ok(self.rewrap(self.as_ref().traverse_resolve(visit_embed)?)) - } -} - -impl SubExpr<X, X> { - pub fn absurd<N: Clone, T>(&self) -> SubExpr<N, T> { - SubExpr::from_expr_no_note(self.as_ref().absurd()) + visit_import: impl FnMut(&Import<Expr<E2>>) -> Result<E2, Err>, + ) -> Result<Expr<E2>, Err> { + Ok(self.rewrap(self.as_ref().traverse_resolve(visit_import)?)) } } -impl<E: Clone> SubExpr<X, E> { - pub fn note_absurd<N>(&self) -> SubExpr<N, E> { - SubExpr::from_expr_no_note(self.as_ref().note_absurd()) - } +// Should probably rename this +pub fn rc<E>(x: RawExpr<E>) -> Expr<E> { + Expr::from_expr_no_span(x) } -impl<N, E> Clone for SubExpr<N, E> { - fn clone(&self) -> Self { - SubExpr(Rc::clone(&self.0)) - } +pub(crate) fn spanned( + span: Span, + x: crate::parser::ParsedRawExpr, +) -> crate::parser::ParsedExpr { + Expr::new(x, span) } - -// Should probably rename this -pub fn rc<E>(x: Expr<X, E>) -> SubExpr<X, E> { - SubExpr::from_expr_no_note(x) +pub(crate) fn unspanned( + x: crate::parser::ParsedRawExpr, +) -> crate::parser::ParsedExpr { + Expr::from_expr_no_span(x) } /// Add an isize to an usize |