Add `impl Trait` and `dyn Trait` types

 - refactor bounds handling in the AST a bit
 - add HIR for bounds
 - add `Ty::Dyn` and `Ty::Opaque` variants and lower `dyn Trait` / `impl Trait`
   syntax to them

1 files changed, 110 insertions, 10 deletions

diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 642dd02cb..4e5bdbae4 100644
--- a/crates/ra_hir/src/ty.rs
+++ b/crates/ra_hir/src/ty.rs
@@ -161,14 +161,28 @@ pub enum Ty {
         name: Name,
     },
 
-    /// A bound type variable. Only used during trait resolution to represent
-    /// Chalk variables.
+    /// A bound type variable. Used during trait resolution to represent Chalk
+    /// variables, and in `Dyn` and `Opaque` bounds to represent the `Self` type.
     Bound(u32),
 
     /// A type variable used during type checking. Not to be confused with a
     /// type parameter.
     Infer(InferTy),
 
+    /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
+    ///
+    /// The predicates are quantified over the `Self` type, i.e. `Ty::Bound(0)`
+    /// represents the `Self` type inside the bounds. This is currently
+    /// implicit; Chalk has the `Binders` struct to make it explicit, but it
+    /// didn't seem worth the overhead yet.
+    Dyn(Arc<[GenericPredicate]>),
+
+    /// An opaque type (`impl Trait`).
+    ///
+    /// The predicates are quantified over the `Self` type; see `Ty::Dyn` for
+    /// more.
+    Opaque(Arc<[GenericPredicate]>),
+
     /// A placeholder for a type which could not be computed; this is propagated
     /// to avoid useless error messages. Doubles as a placeholder where type
     /// variables are inserted before type checking, since we want to try to
@@ -194,6 +208,12 @@ impl Substs {
         Substs(self.0.iter().cloned().take(n).collect::<Vec<_>>().into())
     }
 
+    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        for t in self.0.iter() {
+            t.walk(f);
+        }
+    }
+
     pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
         // Without an Arc::make_mut_slice, we can't avoid the clone here:
         let mut v: Vec<_> = self.0.iter().cloned().collect();
@@ -270,6 +290,14 @@ impl TraitRef {
         });
         self
     }
+
+    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        self.substs.walk(f);
+    }
+
+    pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+        self.substs.walk_mut(f);
+    }
 }
 
 /// Like `generics::WherePredicate`, but with resolved types: A condition on the
@@ -299,6 +327,20 @@ impl GenericPredicate {
             GenericPredicate::Error => self,
         }
     }
+
+    pub fn walk(&self, f: &mut impl FnMut(&Ty)) {
+        match self {
+            GenericPredicate::Implemented(trait_ref) => trait_ref.walk(f),
+            GenericPredicate::Error => {}
+        }
+    }
+
+    pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
+        match self {
+            GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut(f),
+            GenericPredicate::Error => {}
+        }
+    }
 }
 
 /// Basically a claim (currently not validated / checked) that the contained
@@ -386,6 +428,11 @@ impl Ty {
                     t.walk(f);
                 }
             }
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                for p in predicates.iter() {
+                    p.walk(f);
+                }
+            }
             Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
         }
         f(self);
@@ -402,6 +449,13 @@ impl Ty {
             Ty::UnselectedProjection(p_ty) => {
                 p_ty.parameters.walk_mut(f);
             }
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                let mut v: Vec<_> = predicates.iter().cloned().collect();
+                for p in &mut v {
+                    p.walk_mut(f);
+                }
+                *predicates = v.into();
+            }
             Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
         }
         f(self);
@@ -669,6 +723,28 @@ impl HirDisplay for Ty {
             Ty::UnselectedProjection(p_ty) => p_ty.hir_fmt(f)?,
             Ty::Param { name, .. } => write!(f, "{}", name)?,
             Ty::Bound(idx) => write!(f, "?{}", idx)?,
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                match self {
+                    Ty::Dyn(_) => write!(f, "dyn ")?,
+                    Ty::Opaque(_) => write!(f, "impl ")?,
+                    _ => unreachable!(),
+                };
+                // looping by hand here just to format the bounds in a slightly nicer way
+                let mut first = true;
+                for p in predicates.iter() {
+                    if !first {
+                        write!(f, " + ")?;
+                    }
+                    first = false;
+                    match p {
+                        // don't show the $0 self type
+                        GenericPredicate::Implemented(trait_ref) => {
+                            trait_ref.hir_fmt_ext(f, false)?
+                        }
+                        GenericPredicate::Error => p.hir_fmt(f)?,
+                    }
+                }
+            }
             Ty::Unknown => write!(f, "{{unknown}}")?,
             Ty::Infer(..) => write!(f, "_")?,
         }
@@ -676,14 +752,16 @@ impl HirDisplay for Ty {
     }
 }
 
-impl HirDisplay for TraitRef {
-    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
-        write!(
-            f,
-            "{}: {}",
-            self.substs[0].display(f.db),
-            self.trait_.name(f.db).unwrap_or_else(Name::missing)
-        )?;
+impl TraitRef {
+    fn hir_fmt_ext(
+        &self,
+        f: &mut HirFormatter<impl HirDatabase>,
+        with_self_ty: bool,
+    ) -> fmt::Result {
+        if with_self_ty {
+            write!(f, "{}: ", self.substs[0].display(f.db),)?;
+        }
+        write!(f, "{}", self.trait_.name(f.db).unwrap_or_else(Name::missing))?;
         if self.substs.len() > 1 {
             write!(f, "<")?;
             f.write_joined(&self.substs[1..], ", ")?;
@@ -693,6 +771,28 @@ impl HirDisplay for TraitRef {
     }
 }
 
+impl HirDisplay for TraitRef {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        self.hir_fmt_ext(f, true)
+    }
+}
+
+impl HirDisplay for &GenericPredicate {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        HirDisplay::hir_fmt(*self, f)
+    }
+}
+
+impl HirDisplay for GenericPredicate {
+    fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
+        match self {
+            GenericPredicate::Implemented(trait_ref) => trait_ref.hir_fmt(f)?,
+            GenericPredicate::Error => write!(f, "{{error}}")?,
+        }
+        Ok(())
+    }
+}
+
 impl HirDisplay for Obligation {
     fn hir_fmt(&self, f: &mut HirFormatter<impl HirDatabase>) -> fmt::Result {
         match self {