13 files changed, 501 insertions, 57 deletions

diff --git a/crates/ra_hir/src/generics.rs b/crates/ra_hir/src/generics.rs
index e75337cdf..d6728cc9f 100644
--- a/crates/ra_hir/src/generics.rs
+++ b/crates/ra_hir/src/generics.rs
@@ -11,7 +11,7 @@ use crate::{
     db::{AstDatabase, DefDatabase, HirDatabase},
     name::SELF_TYPE,
     path::Path,
-    type_ref::TypeRef,
+    type_ref::{TypeBound, TypeRef},
     AdtDef, AsName, Container, Enum, EnumVariant, Function, HasSource, ImplBlock, Name, Struct,
     Trait, TypeAlias, Union,
 };
@@ -35,10 +35,12 @@ pub struct GenericParams {
 
 /// A single predicate from a where clause, i.e. `where Type: Trait`. Combined
 /// where clauses like `where T: Foo + Bar` are turned into multiple of these.
+/// It might still result in multiple actual predicates though, because of
+/// associated type bindings like `Iterator<Item = u32>`.
 #[derive(Clone, PartialEq, Eq, Debug)]
 pub struct WherePredicate {
     pub(crate) type_ref: TypeRef,
-    pub(crate) trait_ref: Path,
+    pub(crate) bound: TypeBound,
 }
 
 // FIXME: consts can have type parameters from their parents (i.e. associated consts of traits)
@@ -143,18 +145,8 @@ impl GenericParams {
             // FIXME: remove this bound
             return;
         }
-        let path = bound
-            .type_ref()
-            .and_then(|tr| match tr {
-                ast::TypeRef::PathType(path) => path.path(),
-                _ => None,
-            })
-            .and_then(Path::from_ast);
-        let path = match path {
-            Some(p) => p,
-            None => return,
-        };
-        self.where_predicates.push(WherePredicate { type_ref, trait_ref: path });
+        let bound = TypeBound::from_ast(bound);
+        self.where_predicates.push(WherePredicate { type_ref, bound });
     }
 
     pub(crate) fn find_by_name(&self, name: &Name) -> Option<&GenericParam> {
diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs
index 642dd02cb..b54c80318 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);
@@ -529,6 +583,19 @@ impl Ty {
             ty => ty,
         })
     }
+
+    /// If this is an `impl Trait` or `dyn Trait`, returns that trait.
+    pub fn inherent_trait(&self) -> Option<Trait> {
+        match self {
+            Ty::Dyn(predicates) | Ty::Opaque(predicates) => {
+                predicates.iter().find_map(|pred| match pred {
+                    GenericPredicate::Implemented(tr) => Some(tr.trait_),
+                    _ => None,
+                })
+            }
+            _ => None,
+        }
+    }
 }
 
 impl HirDisplay for &Ty {
@@ -669,6 +736,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 +765,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 +784,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 {
diff --git a/crates/ra_hir/src/ty/lower.rs b/crates/ra_hir/src/ty/lower.rs
index debedcbb8..47d161277 100644
--- a/crates/ra_hir/src/ty/lower.rs
+++ b/crates/ra_hir/src/ty/lower.rs
@@ -17,7 +17,7 @@ use crate::{
     path::{GenericArg, PathSegment},
     resolve::{Resolution, Resolver},
     ty::AdtDef,
-    type_ref::TypeRef,
+    type_ref::{TypeBound, TypeRef},
     BuiltinType, Const, Enum, EnumVariant, Function, HirDatabase, ModuleDef, Path, Static, Struct,
     StructField, Trait, TypeAlias, Union,
 };
@@ -58,6 +58,22 @@ impl Ty {
                 let sig = Substs(inner_tys.into());
                 Ty::apply(TypeCtor::FnPtr { num_args: sig.len() as u16 - 1 }, sig)
             }
+            TypeRef::DynTrait(bounds) => {
+                let self_ty = Ty::Bound(0);
+                let predicates = bounds
+                    .iter()
+                    .map(|b| GenericPredicate::from_type_bound(db, resolver, b, self_ty.clone()))
+                    .collect::<Vec<_>>();
+                Ty::Dyn(predicates.into())
+            }
+            TypeRef::ImplTrait(bounds) => {
+                let self_ty = Ty::Bound(0);
+                let predicates = bounds
+                    .iter()
+                    .map(|b| GenericPredicate::from_type_bound(db, resolver, b, self_ty.clone()))
+                    .collect::<Vec<_>>();
+                Ty::Opaque(predicates.into())
+            }
             TypeRef::Error => Ty::Unknown,
         }
     }
@@ -310,13 +326,46 @@ impl TraitRef {
         TraitRef { trait_, substs }
     }
 
-    pub(crate) fn for_where_predicate(
+    pub(crate) fn from_where_predicate(
         db: &impl HirDatabase,
         resolver: &Resolver,
         pred: &WherePredicate,
     ) -> Option<TraitRef> {
         let self_ty = Ty::from_hir(db, resolver, &pred.type_ref);
-        TraitRef::from_path(db, resolver, &pred.trait_ref, Some(self_ty))
+        TraitRef::from_type_bound(db, resolver, &pred.bound, self_ty)
+    }
+
+    pub(crate) fn from_type_bound(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        bound: &TypeBound,
+        self_ty: Ty,
+    ) -> Option<TraitRef> {
+        match bound {
+            TypeBound::Path(path) => TraitRef::from_path(db, resolver, path, Some(self_ty)),
+            TypeBound::Error => None,
+        }
+    }
+}
+
+impl GenericPredicate {
+    pub(crate) fn from_where_predicate(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        where_predicate: &WherePredicate,
+    ) -> GenericPredicate {
+        TraitRef::from_where_predicate(db, &resolver, where_predicate)
+            .map_or(GenericPredicate::Error, GenericPredicate::Implemented)
+    }
+
+    pub(crate) fn from_type_bound(
+        db: &impl HirDatabase,
+        resolver: &Resolver,
+        bound: &TypeBound,
+        self_ty: Ty,
+    ) -> GenericPredicate {
+        TraitRef::from_type_bound(db, &resolver, bound, self_ty)
+            .map_or(GenericPredicate::Error, GenericPredicate::Implemented)
     }
 }
 
@@ -376,10 +425,7 @@ pub(crate) fn trait_env(
 ) -> Arc<super::TraitEnvironment> {
     let predicates = resolver
         .where_predicates_in_scope()
-        .map(|pred| {
-            TraitRef::for_where_predicate(db, &resolver, pred)
-                .map_or(GenericPredicate::Error, GenericPredicate::Implemented)
-        })
+        .map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
         .collect::<Vec<_>>();
 
     Arc::new(super::TraitEnvironment { predicates })
@@ -393,10 +439,7 @@ pub(crate) fn generic_predicates_query(
     let resolver = def.resolver(db);
     let predicates = resolver
         .where_predicates_in_scope()
-        .map(|pred| {
-            TraitRef::for_where_predicate(db, &resolver, pred)
-                .map_or(GenericPredicate::Error, GenericPredicate::Implemented)
-        })
+        .map(|pred| GenericPredicate::from_where_predicate(db, &resolver, pred))
         .collect::<Vec<_>>();
     predicates.into()
 }
diff --git a/crates/ra_hir/src/ty/method_resolution.rs b/crates/ra_hir/src/ty/method_resolution.rs
index 3f4c43aee..9873a0440 100644
--- a/crates/ra_hir/src/ty/method_resolution.rs
+++ b/crates/ra_hir/src/ty/method_resolution.rs
@@ -211,12 +211,19 @@ fn iterate_trait_method_candidates<T>(
     let krate = resolver.krate()?;
     // FIXME: maybe put the trait_env behind a query (need to figure out good input parameters for that)
     let env = lower::trait_env(db, resolver);
-    'traits: for t in resolver.traits_in_scope(db) {
+    // if ty is `impl Trait` or `dyn Trait`, the trait doesn't need to be in scope
+    let traits = ty.value.inherent_trait().into_iter().chain(resolver.traits_in_scope(db));
+    'traits: for t in traits {
         let data = t.trait_data(db);
+
+        // FIXME this is a bit of a hack, since Chalk should say the same thing
+        // anyway, but currently Chalk doesn't implement `dyn/impl Trait` yet
+        let inherently_implemented = ty.value.inherent_trait() == Some(t);
+
         // we'll be lazy about checking whether the type implements the
         // trait, but if we find out it doesn't, we'll skip the rest of the
         // iteration
-        let mut known_implemented = false;
+        let mut known_implemented = inherently_implemented;
         for item in data.items() {
             if let TraitItem::Function(m) = *item {
                 let data = m.data(db);
@@ -271,6 +278,11 @@ pub(crate) fn implements_trait(
     krate: Crate,
     trait_: Trait,
 ) -> bool {
+    if ty.value.inherent_trait() == Some(trait_) {
+        // FIXME this is a bit of a hack, since Chalk should say the same thing
+        // anyway, but currently Chalk doesn't implement `dyn/impl Trait` yet
+        return true;
+    }
     let env = lower::trait_env(db, resolver);
     let goal = generic_implements_goal(db, env.clone(), trait_, ty.clone());
     let solution = db.trait_solve(krate, goal);
diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs
index 57fd5492d..c5818b738 100644
--- a/crates/ra_hir/src/ty/tests.rs
+++ b/crates/ra_hir/src/ty/tests.rs
@@ -3273,6 +3273,181 @@ fn test<T: ApplyL>(t: T) {
     assert_eq!(t, "{unknown}");
 }
 
+#[test]
+fn impl_trait() {
+    assert_snapshot_matches!(
+        infer(r#"
+trait Trait<T> {
+    fn foo(&self) -> T;
+    fn foo2(&self) -> i64;
+}
+fn bar() -> impl Trait<u64> {}
+
+fn test(x: impl Trait<u64>, y: &impl Trait<u64>) {
+    x;
+    y;
+    let z = bar();
+    x.foo();
+    y.foo();
+    z.foo();
+    x.foo2();
+    y.foo2();
+    z.foo2();
+}
+"#),
+        @r###"
+   ⋮
+   ⋮[30; 34) 'self': &Self
+   ⋮[55; 59) 'self': &Self
+   ⋮[99; 101) '{}': ()
+   ⋮[111; 112) 'x': impl Trait<u64>
+   ⋮[131; 132) 'y': &impl Trait<u64>
+   ⋮[152; 269) '{     ...2(); }': ()
+   ⋮[158; 159) 'x': impl Trait<u64>
+   ⋮[165; 166) 'y': &impl Trait<u64>
+   ⋮[176; 177) 'z': impl Trait<u64>
+   ⋮[180; 183) 'bar': fn bar() -> impl Trait<u64>
+   ⋮[180; 185) 'bar()': impl Trait<u64>
+   ⋮[191; 192) 'x': impl Trait<u64>
+   ⋮[191; 198) 'x.foo()': {unknown}
+   ⋮[204; 205) 'y': &impl Trait<u64>
+   ⋮[204; 211) 'y.foo()': {unknown}
+   ⋮[217; 218) 'z': impl Trait<u64>
+   ⋮[217; 224) 'z.foo()': {unknown}
+   ⋮[230; 231) 'x': impl Trait<u64>
+   ⋮[230; 238) 'x.foo2()': i64
+   ⋮[244; 245) 'y': &impl Trait<u64>
+   ⋮[244; 252) 'y.foo2()': i64
+   ⋮[258; 259) 'z': impl Trait<u64>
+   ⋮[258; 266) 'z.foo2()': i64
+    "###
+    );
+}
+
+#[test]
+fn dyn_trait() {
+    assert_snapshot_matches!(
+        infer(r#"
+trait Trait<T> {
+    fn foo(&self) -> T;
+    fn foo2(&self) -> i64;
+}
+fn bar() -> dyn Trait<u64> {}
+
+fn test(x: dyn Trait<u64>, y: &dyn Trait<u64>) {
+    x;
+    y;
+    let z = bar();
+    x.foo();
+    y.foo();
+    z.foo();
+    x.foo2();
+    y.foo2();
+    z.foo2();
+}
+"#),
+        @r###"
+   ⋮
+   ⋮[30; 34) 'self': &Self
+   ⋮[55; 59) 'self': &Self
+   ⋮[98; 100) '{}': ()
+   ⋮[110; 111) 'x': dyn Trait<u64>
+   ⋮[129; 130) 'y': &dyn Trait<u64>
+   ⋮[149; 266) '{     ...2(); }': ()
+   ⋮[155; 156) 'x': dyn Trait<u64>
+   ⋮[162; 163) 'y': &dyn Trait<u64>
+   ⋮[173; 174) 'z': dyn Trait<u64>
+   ⋮[177; 180) 'bar': fn bar() -> dyn Trait<u64>
+   ⋮[177; 182) 'bar()': dyn Trait<u64>
+   ⋮[188; 189) 'x': dyn Trait<u64>
+   ⋮[188; 195) 'x.foo()': {unknown}
+   ⋮[201; 202) 'y': &dyn Trait<u64>
+   ⋮[201; 208) 'y.foo()': {unknown}
+   ⋮[214; 215) 'z': dyn Trait<u64>
+   ⋮[214; 221) 'z.foo()': {unknown}
+   ⋮[227; 228) 'x': dyn Trait<u64>
+   ⋮[227; 235) 'x.foo2()': i64
+   ⋮[241; 242) 'y': &dyn Trait<u64>
+   ⋮[241; 249) 'y.foo2()': i64
+   ⋮[255; 256) 'z': dyn Trait<u64>
+   ⋮[255; 263) 'z.foo2()': i64
+    "###
+    );
+}
+
+#[test]
+fn dyn_trait_bare() {
+    assert_snapshot_matches!(
+        infer(r#"
+trait Trait {
+    fn foo(&self) -> u64;
+}
+fn bar() -> Trait {}
+
+fn test(x: Trait, y: &Trait) -> u64 {
+    x;
+    y;
+    let z = bar();
+    x.foo();
+    y.foo();
+    z.foo();
+}
+"#),
+        @r###"
+   ⋮
+   ⋮[27; 31) 'self': &Self
+   ⋮[61; 63) '{}': ()
+   ⋮[73; 74) 'x': {unknown}
+   ⋮[83; 84) 'y': &{unknown}
+   ⋮[101; 176) '{     ...o(); }': ()
+   ⋮[107; 108) 'x': {unknown}
+   ⋮[114; 115) 'y': &{unknown}
+   ⋮[125; 126) 'z': {unknown}
+   ⋮[129; 132) 'bar': fn bar() -> {unknown}
+   ⋮[129; 134) 'bar()': {unknown}
+   ⋮[140; 141) 'x': {unknown}
+   ⋮[140; 147) 'x.foo()': {unknown}
+   ⋮[153; 154) 'y': &{unknown}
+   ⋮[153; 160) 'y.foo()': {unknown}
+   ⋮[166; 167) 'z': {unknown}
+   ⋮[166; 173) 'z.foo()': {unknown}
+    "###
+    );
+}
+
+#[test]
+fn weird_bounds() {
+    assert_snapshot_matches!(
+        infer(r#"
+trait Trait {}
+fn test() {
+    let a: impl Trait + 'lifetime = foo;
+    let b: impl 'lifetime = foo;
+    let b: impl (Trait) = foo;
+    let b: impl ('lifetime) = foo;
+    let d: impl ?Sized = foo;
+    let e: impl Trait + ?Sized = foo;
+}
+"#),
+        @r###"
+   ⋮
+   ⋮[26; 237) '{     ...foo; }': ()
+   ⋮[36; 37) 'a': impl Trait + {error}
+   ⋮[64; 67) 'foo': impl Trait + {error}
+   ⋮[77; 78) 'b': impl {error}
+   ⋮[97; 100) 'foo': impl {error}
+   ⋮[110; 111) 'b': impl Trait
+   ⋮[128; 131) 'foo': impl Trait
+   ⋮[141; 142) 'b': impl {error}
+   ⋮[163; 166) 'foo': impl {error}
+   ⋮[176; 177) 'd': impl {error}
+   ⋮[193; 196) 'foo': impl {error}
+   ⋮[206; 207) 'e': impl Trait + {error}
+   ⋮[231; 234) 'foo': impl Trait + {error}
+    "###
+    );
+}
+
 fn type_at_pos(db: &MockDatabase, pos: FilePosition) -> String {
     let file = db.parse(pos.file_id).ok().unwrap();
     let expr = algo::find_node_at_offset::<ast::Expr>(file.syntax(), pos.offset).unwrap();
diff --git a/crates/ra_hir/src/ty/traits/chalk.rs b/crates/ra_hir/src/ty/traits/chalk.rs
index 6df7094c5..2ebc06135 100644
--- a/crates/ra_hir/src/ty/traits/chalk.rs
+++ b/crates/ra_hir/src/ty/traits/chalk.rs
@@ -80,7 +80,9 @@ impl ToChalk for Ty {
             // FIXME this is clearly incorrect, but probably not too incorrect
             // and I'm not sure what to actually do with Ty::Unknown
             // maybe an alternative would be `for<T> T`? (meaningless in rust, but expressible in chalk's Ty)
-            Ty::Unknown => {
+            //
+            // FIXME also dyn and impl Trait are currently handled like Unknown because Chalk doesn't have them yet
+            Ty::Unknown | Ty::Dyn(_) | Ty::Opaque(_) => {
                 PlaceholderIndex { ui: UniverseIndex::ROOT, idx: usize::max_value() }.to_ty()
             }
         }
diff --git a/crates/ra_hir/src/type_ref.rs b/crates/ra_hir/src/type_ref.rs
index b92a0b55a..fa91bfb22 100644
--- a/crates/ra_hir/src/type_ref.rs
+++ b/crates/ra_hir/src/type_ref.rs
@@ -1,7 +1,7 @@
 //! HIR for references to types. Paths in these are not yet resolved. They can
 //! be directly created from an ast::TypeRef, without further queries.
 
-use ra_syntax::ast::{self, TypeAscriptionOwner};
+use ra_syntax::ast::{self, TypeAscriptionOwner, TypeBoundsOwner};
 
 use crate::Path;
 
@@ -49,8 +49,16 @@ pub enum TypeRef {
     /// A fn pointer. Last element of the vector is the return type.
     Fn(Vec<TypeRef>),
     // For
-    // ImplTrait,
-    // DynTrait,
+    ImplTrait(Vec<TypeBound>),
+    DynTrait(Vec<TypeBound>),
+    Error,
+}
+
+#[derive(Clone, PartialEq, Eq, Hash, Debug)]
+pub enum TypeBound {
+    Path(Path),
+    // also for<> bounds
+    // also Lifetimes
     Error,
 }
 
@@ -95,8 +103,12 @@ impl TypeRef {
             }
             // for types are close enough for our purposes to the inner type for now...
             ast::TypeRef::ForType(inner) => TypeRef::from_ast_opt(inner.type_ref()),
-            ast::TypeRef::ImplTraitType(_inner) => TypeRef::Error,
-            ast::TypeRef::DynTraitType(_inner) => TypeRef::Error,
+            ast::TypeRef::ImplTraitType(inner) => {
+                TypeRef::ImplTrait(type_bounds_from_ast(inner.type_bound_list()))
+            }
+            ast::TypeRef::DynTraitType(inner) => {
+                TypeRef::DynTrait(type_bounds_from_ast(inner.type_bound_list()))
+            }
         }
     }
 
@@ -112,3 +124,30 @@ impl TypeRef {
         TypeRef::Tuple(Vec::new())
     }
 }
+
+pub(crate) fn type_bounds_from_ast(type_bounds_opt: Option<ast::TypeBoundList>) -> Vec<TypeBound> {
+    if let Some(type_bounds) = type_bounds_opt {
+        type_bounds.bounds().map(TypeBound::from_ast).collect()
+    } else {
+        vec![]
+    }
+}
+
+impl TypeBound {
+    pub(crate) fn from_ast(node: ast::TypeBound) -> Self {
+        match node.kind() {
+            ast::TypeBoundKind::PathType(path_type) => {
+                let path = match path_type.path() {
+                    Some(p) => p,
+                    None => return TypeBound::Error,
+                };
+                let path = match Path::from_ast(path) {
+                    Some(p) => p,
+                    None => return TypeBound::Error,
+                };
+                TypeBound::Path(path)
+            }
+            ast::TypeBoundKind::ForType(_) | ast::TypeBoundKind::Lifetime(_) => TypeBound::Error,
+        }
+    }
+}
diff --git a/crates/ra_parser/src/grammar/expressions/atom.rs b/crates/ra_parser/src/grammar/expressions/atom.rs
index bc942ae01..ab8fb9f6e 100644
--- a/crates/ra_parser/src/grammar/expressions/atom.rs
+++ b/crates/ra_parser/src/grammar/expressions/atom.rs
@@ -414,6 +414,8 @@ pub(crate) fn match_arm_list(p: &mut Parser) {
 //         X | Y if Z => (),
 //         | X | Y if Z => (),
 //         | X => (),
+//         box X => (),
+//         Some(box X) => (),
 //     };
 // }
 fn match_arm(p: &mut Parser) -> BlockLike {
diff --git a/crates/ra_parser/src/grammar/patterns.rs b/crates/ra_parser/src/grammar/patterns.rs
index df6000707..1f6a6fd48 100644
--- a/crates/ra_parser/src/grammar/patterns.rs
+++ b/crates/ra_parser/src/grammar/patterns.rs
@@ -2,7 +2,7 @@ use super::*;
 
 pub(super) const PATTERN_FIRST: TokenSet = expressions::LITERAL_FIRST
     .union(paths::PATH_FIRST)
-    .union(token_set![REF_KW, MUT_KW, L_PAREN, L_BRACK, AMP, UNDERSCORE, MINUS]);
+    .union(token_set![BOX_KW, REF_KW, MUT_KW, L_PAREN, L_BRACK, AMP, UNDERSCORE, MINUS]);
 
 pub(super) fn pattern(p: &mut Parser) {
     pattern_r(p, PAT_RECOVERY_SET);
diff --git a/crates/ra_syntax/src/ast.rs b/crates/ra_syntax/src/ast.rs
index 6f0489617..afdfca66e 100644
--- a/crates/ra_syntax/src/ast.rs
+++ b/crates/ra_syntax/src/ast.rs
@@ -15,7 +15,7 @@ use crate::{
 
 pub use self::{
     expr_extensions::{ArrayExprKind, BinOp, ElseBranch, LiteralKind, PrefixOp},
-    extensions::{FieldKind, PathSegmentKind, SelfParamKind, StructKind},
+    extensions::{FieldKind, PathSegmentKind, SelfParamKind, StructKind, TypeBoundKind},
     generated::*,
     tokens::*,
     traits::*,
diff --git a/crates/ra_syntax/src/ast/extensions.rs b/crates/ra_syntax/src/ast/extensions.rs
index efe261fc2..e0ea3e5ab 100644
--- a/crates/ra_syntax/src/ast/extensions.rs
+++ b/crates/ra_syntax/src/ast/extensions.rs
@@ -382,7 +382,36 @@ impl ast::WherePred {
     }
 }
 
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub enum TypeBoundKind {
+    /// Trait
+    PathType(ast::PathType),
+    /// for<'a> ...
+    ForType(ast::ForType),
+    /// 'a
+    Lifetime(ast::SyntaxToken),
+}
+
 impl ast::TypeBound {
+    pub fn kind(&self) -> TypeBoundKind {
+        if let Some(path_type) = children(self).next() {
+            TypeBoundKind::PathType(path_type)
+        } else if let Some(for_type) = children(self).next() {
+            TypeBoundKind::ForType(for_type)
+        } else if let Some(lifetime) = self.lifetime() {
+            TypeBoundKind::Lifetime(lifetime)
+        } else {
+            unreachable!()
+        }
+    }
+
+    fn lifetime(&self) -> Option<SyntaxToken> {
+        self.syntax()
+            .children_with_tokens()
+            .filter_map(|it| it.into_token())
+            .find(|it| it.kind() == LIFETIME)
+    }
+
     pub fn question_mark_token(&self) -> Option<SyntaxToken> {
         self.syntax()
             .children_with_tokens()
diff --git a/crates/ra_syntax/test_data/parser/inline/ok/0066_match_arm.rs b/crates/ra_syntax/test_data/parser/inline/ok/0066_match_arm.rs
index 9e009e24f..2d476278d 100644
--- a/crates/ra_syntax/test_data/parser/inline/ok/0066_match_arm.rs
+++ b/crates/ra_syntax/test_data/parser/inline/ok/0066_match_arm.rs
@@ -5,5 +5,7 @@ fn foo() {
         X | Y if Z => (),
         | X | Y if Z => (),
         | X => (),
+        box X => (),
+        Some(box X) => (),
     };
 }
diff --git a/crates/ra_syntax/test_data/parser/inline/ok/0066_match_arm.txt b/crates/ra_syntax/test_data/parser/inline/ok/0066_match_arm.txt
index 041e7179e..28d501459 100644
--- a/crates/ra_syntax/test_data/parser/inline/ok/0066_match_arm.txt
+++ b/crates/ra_syntax/test_data/parser/inline/ok/0066_match_arm.txt
@@ -1,5 +1,5 @@
-SOURCE_FILE@[0; 167)
-  FN_DEF@[0; 166)
+SOURCE_FILE@[0; 215)
+  FN_DEF@[0; 214)
     FN_KW@[0; 2) "fn"
     WHITESPACE@[2; 3) " "
     NAME@[3; 6)
@@ -8,18 +8,18 @@ SOURCE_FILE@[0; 167)
       L_PAREN@[6; 7) "("
       R_PAREN@[7; 8) ")"
     WHITESPACE@[8; 9) " "
-    BLOCK@[9; 166)
+    BLOCK@[9; 214)
       L_CURLY@[9; 10) "{"
       WHITESPACE@[10; 15) "\n    "
-      EXPR_STMT@[15; 164)
-        MATCH_EXPR@[15; 163)
+      EXPR_STMT@[15; 212)
+        MATCH_EXPR@[15; 211)
           MATCH_KW@[15; 20) "match"
           WHITESPACE@[20; 21) " "
           TUPLE_EXPR@[21; 23)
             L_PAREN@[21; 22) "("
             R_PAREN@[22; 23) ")"
           WHITESPACE@[23; 24) " "
-          MATCH_ARM_LIST@[24; 163)
+          MATCH_ARM_LIST@[24; 211)
             L_CURLY@[24; 25) "{"
             WHITESPACE@[25; 34) "\n        "
             MATCH_ARM@[34; 41)
@@ -141,9 +141,44 @@ SOURCE_FILE@[0; 167)
                 L_PAREN@[154; 155) "("
                 R_PAREN@[155; 156) ")"
             COMMA@[156; 157) ","
-            WHITESPACE@[157; 162) "\n    "
-            R_CURLY@[162; 163) "}"
-        SEMI@[163; 164) ";"
-      WHITESPACE@[164; 165) "\n"
-      R_CURLY@[165; 166) "}"
-  WHITESPACE@[166; 167) "\n"
+            WHITESPACE@[157; 166) "\n        "
+            MATCH_ARM@[166; 177)
+              BIND_PAT@[166; 171)
+                BOX_KW@[166; 169) "box"
+                WHITESPACE@[169; 170) " "
+                NAME@[170; 171)
+                  IDENT@[170; 171) "X"
+              WHITESPACE@[171; 172) " "
+              FAT_ARROW@[172; 174) "=>"
+              WHITESPACE@[174; 175) " "
+              TUPLE_EXPR@[175; 177)
+                L_PAREN@[175; 176) "("
+                R_PAREN@[176; 177) ")"
+            COMMA@[177; 178) ","
+            WHITESPACE@[178; 187) "\n        "
+            MATCH_ARM@[187; 204)
+              TUPLE_STRUCT_PAT@[187; 198)
+                PATH@[187; 191)
+                  PATH_SEGMENT@[187; 191)
+                    NAME_REF@[187; 191)
+                      IDENT@[187; 191) "Some"
+                L_PAREN@[191; 192) "("
+                BIND_PAT@[192; 197)
+                  BOX_KW@[192; 195) "box"
+                  WHITESPACE@[195; 196) " "
+                  NAME@[196; 197)
+                    IDENT@[196; 197) "X"
+                R_PAREN@[197; 198) ")"
+              WHITESPACE@[198; 199) " "
+              FAT_ARROW@[199; 201) "=>"
+              WHITESPACE@[201; 202) " "
+              TUPLE_EXPR@[202; 204)
+                L_PAREN@[202; 203) "("
+                R_PAREN@[203; 204) ")"
+            COMMA@[204; 205) ","
+            WHITESPACE@[205; 210) "\n    "
+            R_CURLY@[210; 211) "}"
+        SEMI@[211; 212) ";"
+      WHITESPACE@[212; 213) "\n"
+      R_CURLY@[213; 214) "}"
+  WHITESPACE@[214; 215) "\n"