20 files changed, 633 insertions, 260 deletions

diff --git a/crates/ra_db/src/input.rs b/crates/ra_db/src/input.rs
index bf26048f2..e6af99035 100644
--- a/crates/ra_db/src/input.rs
+++ b/crates/ra_db/src/input.rs
@@ -254,12 +254,12 @@ impl CrateGraph {
             return false;
         }
 
+        if target == from {
+            return true;
+        }
+
         for dep in &self[from].dependencies {
             let crate_id = dep.crate_id;
-            if crate_id == target {
-                return true;
-            }
-
             if self.dfs_find(target, crate_id, visited) {
                 return true;
             }
@@ -369,7 +369,7 @@ mod tests {
     use super::{CfgOptions, CrateGraph, CrateName, Dependency, Edition::Edition2018, Env, FileId};
 
     #[test]
-    fn it_should_panic_because_of_cycle_dependencies() {
+    fn detect_cyclic_dependency_indirect() {
         let mut graph = CrateGraph::default();
         let crate1 = graph.add_crate_root(
             FileId(1u32),
@@ -404,6 +404,31 @@ mod tests {
     }
 
     #[test]
+    fn detect_cyclic_dependency_direct() {
+        let mut graph = CrateGraph::default();
+        let crate1 = graph.add_crate_root(
+            FileId(1u32),
+            Edition2018,
+            None,
+            CfgOptions::default(),
+            Env::default(),
+            Default::default(),
+            Default::default(),
+        );
+        let crate2 = graph.add_crate_root(
+            FileId(2u32),
+            Edition2018,
+            None,
+            CfgOptions::default(),
+            Env::default(),
+            Default::default(),
+            Default::default(),
+        );
+        assert!(graph.add_dep(crate1, CrateName::new("crate2").unwrap(), crate2).is_ok());
+        assert!(graph.add_dep(crate2, CrateName::new("crate2").unwrap(), crate2).is_err());
+    }
+
+    #[test]
     fn it_works() {
         let mut graph = CrateGraph::default();
         let crate1 = graph.add_crate_root(
diff --git a/crates/ra_hir/src/db.rs b/crates/ra_hir/src/db.rs
index b6b665de1..b25dac28e 100644
--- a/crates/ra_hir/src/db.rs
+++ b/crates/ra_hir/src/db.rs
@@ -16,7 +16,7 @@ pub use hir_expand::db::{
 pub use hir_ty::db::{
     AssociatedTyDataQuery, AssociatedTyValueQuery, CallableItemSignatureQuery, FieldTypesQuery,
     GenericDefaultsQuery, GenericPredicatesForParamQuery, GenericPredicatesQuery, HirDatabase,
-    HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsForTraitQuery,
+    HirDatabaseStorage, ImplDatumQuery, ImplSelfTyQuery, ImplTraitQuery, ImplsFromDepsQuery,
     ImplsInCrateQuery, InferQueryQuery, InternAssocTyValueQuery, InternChalkImplQuery,
     InternTypeCtorQuery, InternTypeParamIdQuery, ReturnTypeImplTraitsQuery, StructDatumQuery,
     TraitDatumQuery, TraitSolveQuery, TyQuery, ValueTyQuery,
diff --git a/crates/ra_hir_def/src/lib.rs b/crates/ra_hir_def/src/lib.rs
index edc59e5a8..af2a717c9 100644
--- a/crates/ra_hir_def/src/lib.rs
+++ b/crates/ra_hir_def/src/lib.rs
@@ -159,7 +159,7 @@ pub struct TypeAliasId(salsa::InternId);
 type TypeAliasLoc = AssocItemLoc<ast::TypeAliasDef>;
 impl_intern!(TypeAliasId, TypeAliasLoc, intern_type_alias, lookup_intern_type_alias);
 
-#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Ord, PartialOrd)]
 pub struct ImplId(salsa::InternId);
 type ImplLoc = ItemLoc<ast::ImplDef>;
 impl_intern!(ImplId, ImplLoc, intern_impl, lookup_intern_impl);
diff --git a/crates/ra_hir_def/src/nameres/collector.rs b/crates/ra_hir_def/src/nameres/collector.rs
index 77baa4c69..b8f6aac8f 100644
--- a/crates/ra_hir_def/src/nameres/collector.rs
+++ b/crates/ra_hir_def/src/nameres/collector.rs
@@ -36,8 +36,8 @@ pub(super) fn collect_defs(db: &dyn DefDatabase, mut def_map: CrateDefMap) -> Cr
 
     // populate external prelude
     for dep in &crate_graph[def_map.krate].dependencies {
-        let dep_def_map = db.crate_def_map(dep.crate_id);
         log::debug!("crate dep {:?} -> {:?}", dep.name, dep.crate_id);
+        let dep_def_map = db.crate_def_map(dep.crate_id);
         def_map.extern_prelude.insert(
             dep.as_name(),
             ModuleId { krate: dep.crate_id, local_id: dep_def_map.root }.into(),
diff --git a/crates/ra_hir_ty/src/db.rs b/crates/ra_hir_ty/src/db.rs
index bf71d38d6..7889b8d2c 100644
--- a/crates/ra_hir_ty/src/db.rs
+++ b/crates/ra_hir_ty/src/db.rs
@@ -3,15 +3,15 @@
 use std::sync::Arc;
 
 use hir_def::{
-    db::DefDatabase, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TraitId,
-    TypeParamId, VariantId,
+    db::DefDatabase, DefWithBodyId, FunctionId, GenericDefId, ImplId, LocalFieldId, TypeParamId,
+    VariantId,
 };
 use ra_arena::map::ArenaMap;
 use ra_db::{impl_intern_key, salsa, CrateId, Upcast};
 use ra_prof::profile;
 
 use crate::{
-    method_resolution::{CrateImplDefs, TyFingerprint},
+    method_resolution::CrateImplDefs,
     traits::{chalk, AssocTyValue, Impl},
     Binders, CallableDef, GenericPredicate, InferenceResult, OpaqueTyId, PolyFnSig,
     ReturnTypeImplTraits, Substs, TraitRef, Ty, TyDefId, TypeCtor, ValueTyDefId,
@@ -70,13 +70,8 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
     #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_in_crate_query)]
     fn impls_in_crate(&self, krate: CrateId) -> Arc<CrateImplDefs>;
 
-    #[salsa::invoke(crate::traits::impls_for_trait_query)]
-    fn impls_for_trait(
-        &self,
-        krate: CrateId,
-        trait_: TraitId,
-        self_ty_fp: Option<TyFingerprint>,
-    ) -> Arc<[ImplId]>;
+    #[salsa::invoke(crate::method_resolution::CrateImplDefs::impls_from_deps_query)]
+    fn impls_from_deps(&self, krate: CrateId) -> Arc<CrateImplDefs>;
 
     // Interned IDs for Chalk integration
     #[salsa::interned]
diff --git a/crates/ra_hir_ty/src/infer/expr.rs b/crates/ra_hir_ty/src/infer/expr.rs
index 9fd310f69..a9565a58d 100644
--- a/crates/ra_hir_ty/src/infer/expr.rs
+++ b/crates/ra_hir_ty/src/infer/expr.rs
@@ -10,12 +10,12 @@ use hir_def::{
     resolver::resolver_for_expr,
     AdtId, AssocContainerId, FieldId, Lookup,
 };
-use hir_expand::name::Name;
+use hir_expand::name::{name, Name};
 use ra_syntax::ast::RangeOp;
 
 use crate::{
     autoderef, method_resolution, op,
-    traits::InEnvironment,
+    traits::{FnTrait, InEnvironment},
     utils::{generics, variant_data, Generics},
     ApplicationTy, Binders, CallableDef, InferTy, IntTy, Mutability, Obligation, Rawness, Substs,
     TraitRef, Ty, TypeCtor,
@@ -63,6 +63,58 @@ impl<'a> InferenceContext<'a> {
         self.resolve_ty_as_possible(ty)
     }
 
+    fn callable_sig_from_fn_trait(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
+        let krate = self.resolver.krate()?;
+        let fn_once_trait = FnTrait::FnOnce.get_id(self.db, krate)?;
+        let output_assoc_type =
+            self.db.trait_data(fn_once_trait).associated_type_by_name(&name![Output])?;
+        let generic_params = generics(self.db.upcast(), fn_once_trait.into());
+        if generic_params.len() != 2 {
+            return None;
+        }
+
+        let mut param_builder = Substs::builder(num_args);
+        let mut arg_tys = vec![];
+        for _ in 0..num_args {
+            let arg = self.table.new_type_var();
+            param_builder = param_builder.push(arg.clone());
+            arg_tys.push(arg);
+        }
+        let parameters = param_builder.build();
+        let arg_ty = Ty::Apply(ApplicationTy {
+            ctor: TypeCtor::Tuple { cardinality: num_args as u16 },
+            parameters,
+        });
+        let substs = Substs::build_for_generics(&generic_params)
+            .push(ty.clone())
+            .push(arg_ty.clone())
+            .build();
+
+        let trait_env = Arc::clone(&self.trait_env);
+        let implements_fn_trait =
+            Obligation::Trait(TraitRef { trait_: fn_once_trait, substs: substs.clone() });
+        let goal = self.canonicalizer().canonicalize_obligation(InEnvironment {
+            value: implements_fn_trait.clone(),
+            environment: trait_env,
+        });
+        if self.db.trait_solve(krate, goal.value).is_some() {
+            self.obligations.push(implements_fn_trait);
+            let output_proj_ty =
+                crate::ProjectionTy { associated_ty: output_assoc_type, parameters: substs };
+            let return_ty = self.normalize_projection_ty(output_proj_ty);
+            Some((arg_tys, return_ty))
+        } else {
+            None
+        }
+    }
+
+    pub fn callable_sig(&mut self, ty: &Ty, num_args: usize) -> Option<(Vec<Ty>, Ty)> {
+        match ty.callable_sig(self.db) {
+            Some(sig) => Some((sig.params().to_vec(), sig.ret().clone())),
+            None => self.callable_sig_from_fn_trait(ty, num_args),
+        }
+    }
+
     fn infer_expr_inner(&mut self, tgt_expr: ExprId, expected: &Expectation) -> Ty {
         let body = Arc::clone(&self.body); // avoid borrow checker problem
         let ty = match &body[tgt_expr] {
@@ -198,14 +250,23 @@ impl<'a> InferenceContext<'a> {
             }
             Expr::Call { callee, args } => {
                 let callee_ty = self.infer_expr(*callee, &Expectation::none());
-                let (param_tys, ret_ty) = match callee_ty.callable_sig(self.db) {
-                    Some(sig) => (sig.params().to_vec(), sig.ret().clone()),
-                    None => {
-                        // Not callable
-                        // FIXME: report an error
-                        (Vec::new(), Ty::Unknown)
-                    }
-                };
+                let canonicalized = self.canonicalizer().canonicalize_ty(callee_ty.clone());
+                let mut derefs = autoderef(
+                    self.db,
+                    self.resolver.krate(),
+                    InEnvironment {
+                        value: canonicalized.value.clone(),
+                        environment: self.trait_env.clone(),
+                    },
+                );
+                let (param_tys, ret_ty): (Vec<Ty>, Ty) = derefs
+                    .find_map(|callee_deref_ty| {
+                        self.callable_sig(
+                            &canonicalized.decanonicalize_ty(callee_deref_ty.value),
+                            args.len(),
+                        )
+                    })
+                    .unwrap_or((Vec::new(), Ty::Unknown));
                 self.register_obligations_for_call(&callee_ty);
                 self.check_call_arguments(args, &param_tys);
                 self.normalize_associated_types_in(ret_ty)
diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs
index 7a7fcb0ab..d5154f436 100644
--- a/crates/ra_hir_ty/src/lower.rs
+++ b/crates/ra_hir_ty/src/lower.rs
@@ -467,6 +467,9 @@ impl Ty {
                             }
                             TypeParamLoweringMode::Variable => t.substs.clone(),
                         };
+                        // We need to shift in the bound vars, since
+                        // associated_type_shorthand_candidates does not do that
+                        let substs = substs.shift_bound_vars(ctx.in_binders);
                         // FIXME handle type parameters on the segment
                         return Some(Ty::Projection(ProjectionTy {
                             associated_ty,
diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs
index e83b39456..ed638c195 100644
--- a/crates/ra_hir_ty/src/method_resolution.rs
+++ b/crates/ra_hir_ty/src/method_resolution.rs
@@ -38,18 +38,53 @@ impl TyFingerprint {
     }
 }
 
+/// A queryable and mergeable collection of impls.
 #[derive(Debug, PartialEq, Eq)]
 pub struct CrateImplDefs {
-    impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
+    inherent_impls: FxHashMap<TyFingerprint, Vec<ImplId>>,
     impls_by_trait: FxHashMap<TraitId, FxHashMap<Option<TyFingerprint>, Vec<ImplId>>>,
 }
 
 impl CrateImplDefs {
     pub(crate) fn impls_in_crate_query(db: &dyn HirDatabase, krate: CrateId) -> Arc<CrateImplDefs> {
         let _p = profile("impls_in_crate_query");
-        let mut res =
-            CrateImplDefs { impls: FxHashMap::default(), impls_by_trait: FxHashMap::default() };
+        let mut res = CrateImplDefs {
+            inherent_impls: FxHashMap::default(),
+            impls_by_trait: FxHashMap::default(),
+        };
+        res.fill(db, krate);
+
+        Arc::new(res)
+    }
+
+    /// Collects all impls from transitive dependencies of `krate` that may be used by `krate`.
+    ///
+    /// The full set of impls that can be used by `krate` is the returned map plus all the impls
+    /// from `krate` itself.
+    pub(crate) fn impls_from_deps_query(
+        db: &dyn HirDatabase,
+        krate: CrateId,
+    ) -> Arc<CrateImplDefs> {
+        let _p = profile("impls_from_deps_query");
+        let crate_graph = db.crate_graph();
+        let mut res = CrateImplDefs {
+            inherent_impls: FxHashMap::default(),
+            impls_by_trait: FxHashMap::default(),
+        };
 
+        // For each dependency, calculate `impls_from_deps` recursively, then add its own
+        // `impls_in_crate`.
+        // As we might visit crates multiple times, `merge` has to deduplicate impls to avoid
+        // wasting memory.
+        for dep in &crate_graph[krate].dependencies {
+            res.merge(&db.impls_from_deps(dep.crate_id));
+            res.merge(&db.impls_in_crate(dep.crate_id));
+        }
+
+        Arc::new(res)
+    }
+
+    fn fill(&mut self, db: &dyn HirDatabase, krate: CrateId) {
         let crate_def_map = db.crate_def_map(krate);
         for (_module_id, module_data) in crate_def_map.modules.iter() {
             for impl_id in module_data.scope.impls() {
@@ -57,7 +92,7 @@ impl CrateImplDefs {
                     Some(tr) => {
                         let self_ty = db.impl_self_ty(impl_id);
                         let self_ty_fp = TyFingerprint::for_impl(&self_ty.value);
-                        res.impls_by_trait
+                        self.impls_by_trait
                             .entry(tr.value.trait_)
                             .or_default()
                             .entry(self_ty_fp)
@@ -67,18 +102,36 @@ impl CrateImplDefs {
                     None => {
                         let self_ty = db.impl_self_ty(impl_id);
                         if let Some(self_ty_fp) = TyFingerprint::for_impl(&self_ty.value) {
-                            res.impls.entry(self_ty_fp).or_default().push(impl_id);
+                            self.inherent_impls.entry(self_ty_fp).or_default().push(impl_id);
                         }
                     }
                 }
             }
         }
+    }
 
-        Arc::new(res)
+    fn merge(&mut self, other: &Self) {
+        for (fp, impls) in &other.inherent_impls {
+            let vec = self.inherent_impls.entry(*fp).or_default();
+            vec.extend(impls);
+            vec.sort();
+            vec.dedup();
+        }
+
+        for (trait_, other_map) in &other.impls_by_trait {
+            let map = self.impls_by_trait.entry(*trait_).or_default();
+            for (fp, impls) in other_map {
+                let vec = map.entry(*fp).or_default();
+                vec.extend(impls);
+                vec.sort();
+                vec.dedup();
+            }
+        }
     }
+
     pub fn lookup_impl_defs(&self, ty: &Ty) -> impl Iterator<Item = ImplId> + '_ {
         let fingerprint = TyFingerprint::for_impl(ty);
-        fingerprint.and_then(|f| self.impls.get(&f)).into_iter().flatten().copied()
+        fingerprint.and_then(|f| self.inherent_impls.get(&f)).into_iter().flatten().copied()
     }
 
     pub fn lookup_impl_defs_for_trait(&self, tr: TraitId) -> impl Iterator<Item = ImplId> + '_ {
@@ -110,7 +163,7 @@ impl CrateImplDefs {
     }
 
     pub fn all_impls<'a>(&'a self) -> impl Iterator<Item = ImplId> + 'a {
-        self.impls
+        self.inherent_impls
             .values()
             .chain(self.impls_by_trait.values().flat_map(|m| m.values()))
             .flatten()
diff --git a/crates/ra_hir_ty/src/tests/regression.rs b/crates/ra_hir_ty/src/tests/regression.rs
index 8dc5603b7..4da2e972b 100644
--- a/crates/ra_hir_ty/src/tests/regression.rs
+++ b/crates/ra_hir_ty/src/tests/regression.rs
@@ -693,3 +693,94 @@ fn check<T: PrimInt>(i: T) {
     "###
     );
 }
+
+#[test]
+fn issue_4885() {
+    assert_snapshot!(
+        infer(r#"
+#[lang = "coerce_unsized"]
+pub trait CoerceUnsized<T> {}
+
+trait Future {
+    type Output;
+}
+trait Foo<R> {
+    type Bar;
+}
+fn foo<R, K>(key: &K) -> impl Future<Output = K::Bar>
+where
+    K: Foo<R>,
+{
+    bar(key)
+}
+fn bar<R, K>(key: &K) -> impl Future<Output = K::Bar>
+where
+    K: Foo<R>,
+{
+}
+"#),
+        @r###"
+    137..140 'key': &K
+    199..215 '{     ...key) }': impl Future<Output = <K as Foo<R>>::Bar>
+    205..208 'bar': fn bar<R, K>(&K) -> impl Future<Output = <K as Foo<R>>::Bar>
+    205..213 'bar(key)': impl Future<Output = <K as Foo<R>>::Bar>
+    209..212 'key': &K
+    229..232 'key': &K
+    291..294 '{ }': ()
+    "###
+    );
+}
+
+#[test]
+fn issue_4800() {
+    assert_snapshot!(
+        infer(r#"
+trait Debug {}
+
+struct Foo<T>;
+
+type E1<T> = (T, T, T);
+type E2<T> = E1<E1<E1<(T, T, T)>>>;
+
+impl Debug for Foo<E2<()>> {}
+
+struct Request;
+
+pub trait Future {
+    type Output;
+}
+
+pub struct PeerSet<D>;
+
+impl<D> Service<Request> for PeerSet<D>
+where
+    D: Discover,
+    D::Key: Debug,
+{
+    type Error = ();
+    type Future = dyn Future<Output = Self::Error>;
+
+    fn call(&mut self) -> Self::Future {
+        loop {}
+    }
+}
+
+pub trait Discover {
+    type Key;
+}
+
+pub trait Service<Request> {
+    type Error;
+    type Future: Future<Output = Self::Error>;
+    fn call(&mut self) -> Self::Future;
+}
+"#),
+        @r###"
+    380..384 'self': &mut PeerSet<D>
+    402..425 '{     ...     }': dyn Future<Output = ()>
+    412..419 'loop {}': !
+    417..419 '{}': ()
+    576..580 'self': &mut Self
+    "###
+    );
+}
diff --git a/crates/ra_hir_ty/src/tests/traits.rs b/crates/ra_hir_ty/src/tests/traits.rs
index e81193a3c..961be4abd 100644
--- a/crates/ra_hir_ty/src/tests/traits.rs
+++ b/crates/ra_hir_ty/src/tests/traits.rs
@@ -2888,3 +2888,226 @@ impl<A: Step> iter::Iterator for ops::Range<A> {
     );
     assert_eq!(t, "i32");
 }
+
+#[test]
+fn infer_closure_arg() {
+    assert_snapshot!(
+        infer(
+            r#"
+            //- /lib.rs
+
+            enum Option<T> {
+                None,
+                Some(T)
+            }
+
+            fn foo() {
+                let s = Option::None;
+                let f = |x: Option<i32>| {};
+                (&f)(s)
+            }
+        "#
+        ),
+        @r###"
+    137..259 '{     ...     }': ()
+    159..160 's': Option<i32>
+    163..175 'Option::None': Option<i32>
+    197..198 'f': |Option<i32>| -> ()
+    201..220 '|x: Op...2>| {}': |Option<i32>| -> ()
+    202..203 'x': Option<i32>
+    218..220 '{}': ()
+    238..245 '(&f)(s)': ()
+    239..241 '&f': &|Option<i32>| -> ()
+    240..241 'f': |Option<i32>| -> ()
+    243..244 's': Option<i32>
+    "###
+    );
+}
+
+#[test]
+fn infer_fn_trait_arg() {
+    assert_snapshot!(
+        infer(
+            r#"
+            //- /lib.rs deps:std
+
+            #[lang = "fn_once"]
+            pub trait FnOnce<Args> {
+                type Output;
+
+                extern "rust-call" fn call_once(&self, args: Args) -> Self::Output;
+            }
+
+            #[lang = "fn"]
+            pub trait Fn<Args>:FnOnce<Args> {
+                extern "rust-call" fn call(&self, args: Args) -> Self::Output;
+            }
+
+            enum Option<T> {
+                None,
+                Some(T)
+            }
+
+            fn foo<F, T>(f: F) -> T
+            where
+                F: Fn(Option<i32>) -> T,
+            {
+                let s = None;
+                f(s)
+            }
+        "#
+        ),
+        @r###"
+    183..187 'self': &Self
+    189..193 'args': Args
+    350..354 'self': &Self
+    356..360 'args': Args
+    515..516 'f': F
+    597..663 '{     ...     }': T
+    619..620 's': Option<i32>
+    623..627 'None': Option<i32>
+    645..646 'f': F
+    645..649 'f(s)': T
+    647..648 's': Option<i32>
+    "###
+    );
+}
+
+#[test]
+fn infer_box_fn_arg() {
+    assert_snapshot!(
+        infer(
+            r#"
+            //- /lib.rs deps:std
+
+            #[lang = "fn_once"]
+            pub trait FnOnce<Args> {
+                type Output;
+
+                extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
+            }
+
+            #[lang = "deref"]
+            pub trait Deref {
+                type Target: ?Sized;
+
+                fn deref(&self) -> &Self::Target;
+            }
+
+            #[lang = "owned_box"]
+            pub struct Box<T: ?Sized> {
+                inner: *mut T,
+            }
+
+            impl<T: ?Sized> Deref for Box<T> {
+                type Target = T;
+
+                fn deref(&self) -> &T {
+                    &self.inner
+                }
+            }
+
+            enum Option<T> {
+                None,
+                Some(T)
+            }
+
+            fn foo() {
+                let s = Option::None;
+                let f: Box<dyn FnOnce(&Option<i32>)> = box (|ps| {});
+                f(&s)
+            }
+        "#
+        ),
+        @r###"
+    182..186 'self': Self
+    188..192 'args': Args
+    356..360 'self': &Self
+    622..626 'self': &Box<T>
+    634..685 '{     ...     }': &T
+    656..667 '&self.inner': &*mut T
+    657..661 'self': &Box<T>
+    657..667 'self.inner': *mut T
+    812..957 '{     ...     }': FnOnce::Output<dyn FnOnce<(&Option<i32>,)>, (&Option<i32>,)>
+    834..835 's': Option<i32>
+    838..850 'Option::None': Option<i32>
+    872..873 'f': Box<dyn FnOnce<(&Option<i32>,)>>
+    907..920 'box (|ps| {})': Box<|{unknown}| -> ()>
+    912..919 '|ps| {}': |{unknown}| -> ()
+    913..915 'ps': {unknown}
+    917..919 '{}': ()
+    938..939 'f': Box<dyn FnOnce<(&Option<i32>,)>>
+    938..943 'f(&s)': FnOnce::Output<dyn FnOnce<(&Option<i32>,)>, (&Option<i32>,)>
+    940..942 '&s': &Option<i32>
+    941..942 's': Option<i32>
+    "###
+    );
+}
+
+#[test]
+fn infer_dyn_fn_output() {
+    assert_snapshot!(
+        infer(
+            r#"
+            //- /lib.rs deps:std
+
+            #[lang = "fn_once"]
+            pub trait FnOnce<Args> {
+                type Output;
+
+                extern "rust-call" fn call_once(self, args: Args) -> Self::Output;
+            }
+
+            #[lang = "fn"]
+            pub trait Fn<Args>:FnOnce<Args> {
+                extern "rust-call" fn call(&self, args: Args) -> Self::Output;
+            }
+
+            #[lang = "deref"]
+            pub trait Deref {
+                type Target: ?Sized;
+
+                fn deref(&self) -> &Self::Target;
+            }
+
+            #[lang = "owned_box"]
+            pub struct Box<T: ?Sized> {
+                inner: *mut T,
+            }
+
+            impl<T: ?Sized> Deref for Box<T> {
+                type Target = T;
+
+                fn deref(&self) -> &T {
+                    &self.inner
+                }
+            }
+
+            fn foo() {
+                let f: Box<dyn Fn() -> i32> = box(|| 5);
+                let x = f();
+            }
+        "#
+        ),
+        @r###"
+    182..186 'self': Self
+    188..192 'args': Args
+    349..353 'self': &Self
+    355..359 'args': Args
+    523..527 'self': &Self
+    789..793 'self': &Box<T>
+    801..852 '{     ...     }': &T
+    823..834 '&self.inner': &*mut T
+    824..828 'self': &Box<T>
+    824..834 'self.inner': *mut T
+    889..990 '{     ...     }': ()
+    911..912 'f': Box<dyn Fn<(), Output = i32>>
+    937..946 'box(|| 5)': Box<|| -> i32>
+    941..945 '|| 5': || -> i32
+    944..945 '5': i32
+    968..969 'x': FnOnce::Output<dyn Fn<(), Output = i32>, ()>
+    972..973 'f': Box<dyn Fn<(), Output = i32>>
+    972..975 'f()': FnOnce::Output<dyn Fn<(), Output = i32>, ()>
+    "###
+    );
+}
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index 6bc6d474c..6f43c3a22 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -2,12 +2,13 @@
 use std::{panic, sync::Arc};
 
 use chalk_ir::cast::Cast;
-use hir_def::{expr::ExprId, DefWithBodyId, ImplId, TraitId, TypeAliasId};
+use hir_def::{
+    expr::ExprId, lang_item::LangItemTarget, DefWithBodyId, ImplId, TraitId, TypeAliasId,
+};
 use ra_db::{impl_intern_key, salsa, CrateId};
 use ra_prof::profile;
-use rustc_hash::FxHashSet;
 
-use crate::{db::HirDatabase, method_resolution::TyFingerprint, DebruijnIndex};
+use crate::{db::HirDatabase, DebruijnIndex};
 
 use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk};
 
@@ -36,34 +37,6 @@ fn create_chalk_solver() -> chalk_solve::Solver<Interner> {
     solver_choice.into_solver()
 }
 
-/// Collects impls for the given trait in the whole dependency tree of `krate`.
-pub(crate) fn impls_for_trait_query(
-    db: &dyn HirDatabase,
-    krate: CrateId,
-    trait_: TraitId,
-    self_ty_fp: Option<TyFingerprint>,
-) -> Arc<[ImplId]> {
-    // FIXME: We could be a lot smarter here - because of the orphan rules and
-    // the fact that the trait and the self type need to be in the dependency
-    // tree of a crate somewhere for an impl to exist, we could skip looking in
-    // a lot of crates completely
-    let mut impls = FxHashSet::default();
-    // We call the query recursively here. On the one hand, this means we can
-    // reuse results from queries for different crates; on the other hand, this
-    // will only ever get called for a few crates near the root of the tree (the
-    // ones the user is editing), so this may actually be a waste of memory. I'm
-    // doing it like this mainly for simplicity for now.
-    for dep in &db.crate_graph()[krate].dependencies {
-        impls.extend(db.impls_for_trait(dep.crate_id, trait_, self_ty_fp).iter());
-    }
-    let crate_impl_defs = db.impls_in_crate(krate);
-    match self_ty_fp {
-        Some(fp) => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp)),
-        None => impls.extend(crate_impl_defs.lookup_impl_defs_for_trait(trait_)),
-    }
-    impls.into_iter().collect()
-}
-
 /// A set of clauses that we assume to be true. E.g. if we are inside this function:
 /// ```rust
 /// fn foo<T: Default>(t: T) {}
@@ -298,6 +271,14 @@ impl FnTrait {
             FnTrait::Fn => "fn",
         }
     }
+
+    pub fn get_id(&self, db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId> {
+        let target = db.lang_item(krate, self.lang_item_name().into())?;
+        match target {
+            LangItemTarget::TraitId(t) => Some(t),
+            _ => None,
+        }
+    }
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs
index 88a422d2c..6d5f2d46a 100644
--- a/crates/ra_hir_ty/src/traits/builtin.rs
+++ b/crates/ra_hir_ty/src/traits/builtin.rs
@@ -40,7 +40,7 @@ pub(super) fn get_builtin_impls(
     if let Ty::Apply(ApplicationTy { ctor: TypeCtor::Closure { def, expr }, .. }) = ty {
         for &fn_trait in [super::FnTrait::FnOnce, super::FnTrait::FnMut, super::FnTrait::Fn].iter()
         {
-            if let Some(actual_trait) = get_fn_trait(db, krate, fn_trait) {
+            if let Some(actual_trait) = fn_trait.get_id(db, krate) {
                 if trait_ == actual_trait {
                     let impl_ = super::ClosureFnTraitImplData { def: *def, expr: *expr, fn_trait };
                     if check_closure_fn_trait_impl_prerequisites(db, krate, impl_) {
@@ -128,7 +128,7 @@ fn check_closure_fn_trait_impl_prerequisites(
     data: super::ClosureFnTraitImplData,
 ) -> bool {
     // the respective Fn/FnOnce/FnMut trait needs to exist
-    if get_fn_trait(db, krate, data.fn_trait).is_none() {
+    if data.fn_trait.get_id(db, krate).is_none() {
         return false;
     }
 
@@ -136,7 +136,7 @@ fn check_closure_fn_trait_impl_prerequisites(
     // the traits having no type params, FnOnce being a supertrait
 
     // the FnOnce trait needs to exist and have an assoc type named Output
-    let fn_once_trait = match get_fn_trait(db, krate, super::FnTrait::FnOnce) {
+    let fn_once_trait = match (super::FnTrait::FnOnce).get_id(db, krate) {
         Some(t) => t,
         None => return false,
     };
@@ -151,7 +151,9 @@ fn closure_fn_trait_impl_datum(
     // for some closure |X, Y| -> Z:
     // impl<T, U, V> Fn<(T, U)> for closure<fn(T, U) -> V> { Output = V }
 
-    let trait_ = get_fn_trait(db, krate, data.fn_trait) // get corresponding fn trait
+    let trait_ = data
+        .fn_trait
+        .get_id(db, krate) // get corresponding fn trait
         // the existence of the Fn trait has been checked before
         .expect("fn trait for closure impl missing");
 
@@ -211,7 +213,7 @@ fn closure_fn_trait_output_assoc_ty_value(
     let output_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, num_args.into()));
 
     let fn_once_trait =
-        get_fn_trait(db, krate, super::FnTrait::FnOnce).expect("assoc ty value should not exist");
+        (super::FnTrait::FnOnce).get_id(db, krate).expect("assoc ty value should not exist");
 
     let output_ty_id = db
         .trait_data(fn_once_trait)
@@ -360,14 +362,6 @@ fn super_trait_object_unsize_impl_datum(
     BuiltinImplData { num_vars, trait_ref, where_clauses: Vec::new(), assoc_ty_values: Vec::new() }
 }
 
-fn get_fn_trait(db: &dyn HirDatabase, krate: CrateId, fn_trait: super::FnTrait) -> Option<TraitId> {
-    let target = db.lang_item(krate, fn_trait.lang_item_name().into())?;
-    match target {
-        LangItemTarget::TraitId(t) => Some(t),
-        _ => None,
-    }
-}
-
 fn get_unsize_trait(db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId> {
     let target = db.lang_item(krate, "unsize".into())?;
     match target {
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index a72a82f5a..2f35d6d49 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -74,14 +74,26 @@ impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
         // Note: Since we're using impls_for_trait, only impls where the trait
         // can be resolved should ever reach Chalk. `impl_datum` relies on that
         // and will panic if the trait can't be resolved.
-        let mut result: Vec<_> = self
-            .db
-            .impls_for_trait(self.krate, trait_, self_ty_fp)
-            .iter()
-            .copied()
-            .map(Impl::ImplDef)
-            .map(|impl_| impl_.to_chalk(self.db))
-            .collect();
+        let in_deps = self.db.impls_from_deps(self.krate);
+        let in_self = self.db.impls_in_crate(self.krate);
+        let impl_maps = [in_deps, in_self];
+
+        let id_to_chalk = |id: hir_def::ImplId| Impl::ImplDef(id).to_chalk(self.db);
+
+        let mut result: Vec<_> = match self_ty_fp {
+            Some(fp) => impl_maps
+                .iter()
+                .flat_map(|crate_impl_defs| {
+                    crate_impl_defs.lookup_impl_defs_for_trait_and_ty(trait_, fp).map(id_to_chalk)
+                })
+                .collect(),
+            None => impl_maps
+                .iter()
+                .flat_map(|crate_impl_defs| {
+                    crate_impl_defs.lookup_impl_defs_for_trait(trait_).map(id_to_chalk)
+                })
+                .collect(),
+        };
 
         let arg: Option<Ty> =
             parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone()));
diff --git a/crates/ra_ide_db/src/change.rs b/crates/ra_ide_db/src/change.rs
index 78ee6a515..98993d571 100644
--- a/crates/ra_ide_db/src/change.rs
+++ b/crates/ra_ide_db/src/change.rs
@@ -283,7 +283,7 @@ impl RootDatabase {
             hir::db::GenericPredicatesQuery
             hir::db::GenericDefaultsQuery
             hir::db::ImplsInCrateQuery
-            hir::db::ImplsForTraitQuery
+            hir::db::ImplsFromDepsQuery
             hir::db::InternTypeCtorQuery
             hir::db::InternTypeParamIdQuery
             hir::db::InternChalkImplQuery
diff --git a/crates/rust-analyzer/Cargo.toml b/crates/rust-analyzer/Cargo.toml
index 458089e53..2b46e8905 100644
--- a/crates/rust-analyzer/Cargo.toml
+++ b/crates/rust-analyzer/Cargo.toml
@@ -32,7 +32,7 @@ threadpool = "1.7.1"
 
 stdx = { path = "../stdx" }
 
-lsp-server = "0.3.2"
+lsp-server = "0.3.3"
 ra_flycheck = { path = "../ra_flycheck" }
 ra_ide = { path = "../ra_ide" }
 ra_prof = { path = "../ra_prof" }
diff --git a/crates/rust-analyzer/src/global_state.rs b/crates/rust-analyzer/src/global_state.rs
index 1527c9947..d04ef4c61 100644
--- a/crates/rust-analyzer/src/global_state.rs
+++ b/crates/rust-analyzer/src/global_state.rs
@@ -20,7 +20,7 @@ use stdx::format_to;
 use crate::{
     config::{Config, FilesWatcher},
     diagnostics::{CheckFixes, DiagnosticCollection},
-    main_loop::pending_requests::{CompletedRequest, LatestRequests},
+    main_loop::request_metrics::{LatestRequests, RequestMetrics},
     to_proto::url_from_abs_path,
     vfs_glob::{Glob, RustPackageFilterBuilder},
     LspError, Result,
@@ -55,10 +55,10 @@ pub struct GlobalState {
     pub analysis_host: AnalysisHost,
     pub vfs: Arc<RwLock<Vfs>>,
     pub task_receiver: Receiver<VfsTask>,
-    pub latest_requests: Arc<RwLock<LatestRequests>>,
     pub flycheck: Option<Flycheck>,
     pub diagnostics: DiagnosticCollection,
     pub proc_macro_client: ProcMacroClient,
+    pub(crate) latest_requests: Arc<RwLock<LatestRequests>>,
 }
 
 /// An immutable snapshot of the world's state at a point in time.
@@ -66,8 +66,8 @@ pub struct GlobalStateSnapshot {
     pub config: Config,
     pub workspaces: Arc<Vec<ProjectWorkspace>>,
     pub analysis: Analysis,
-    pub latest_requests: Arc<RwLock<LatestRequests>>,
     pub check_fixes: CheckFixes,
+    pub(crate) latest_requests: Arc<RwLock<LatestRequests>>,
     vfs: Arc<RwLock<Vfs>>,
 }
 
@@ -236,7 +236,7 @@ impl GlobalState {
         self.analysis_host.collect_garbage()
     }
 
-    pub fn complete_request(&mut self, request: CompletedRequest) {
+    pub(crate) fn complete_request(&mut self, request: RequestMetrics) {
         self.latest_requests.write().record(request)
     }
 }
diff --git a/crates/rust-analyzer/src/lib.rs b/crates/rust-analyzer/src/lib.rs
index 609cb69d3..64e70955f 100644
--- a/crates/rust-analyzer/src/lib.rs
+++ b/crates/rust-analyzer/src/lib.rs
@@ -32,7 +32,7 @@ mod semantic_tokens;
 
 use serde::de::DeserializeOwned;
 
-pub type Result<T> = std::result::Result<T, Box<dyn std::error::Error + Send + Sync>>;
+pub type Result<T, E = Box<dyn std::error::Error + Send + Sync>> = std::result::Result<T, E>;
 pub use crate::{
     caps::server_capabilities,
     main_loop::LspError,
diff --git a/crates/rust-analyzer/src/main_loop.rs b/crates/rust-analyzer/src/main_loop.rs
index f0aaaa21e..674b1323b 100644
--- a/crates/rust-analyzer/src/main_loop.rs
+++ b/crates/rust-analyzer/src/main_loop.rs
@@ -3,7 +3,7 @@
 
 mod handlers;
 mod subscriptions;
-pub(crate) mod pending_requests;
+pub(crate) mod request_metrics;
 
 use std::{
     borrow::Cow,
@@ -17,18 +17,19 @@ use std::{
 };
 
 use crossbeam_channel::{never, select, unbounded, RecvError, Sender};
-use lsp_server::{Connection, ErrorCode, Message, Notification, Request, RequestId, Response};
+use lsp_server::{
+    Connection, ErrorCode, Message, Notification, ReqQueue, Request, RequestId, Response,
+};
 use lsp_types::{
-    DidChangeTextDocumentParams, NumberOrString, TextDocumentContentChangeEvent, WorkDoneProgress,
-    WorkDoneProgressBegin, WorkDoneProgressCreateParams, WorkDoneProgressEnd,
-    WorkDoneProgressReport,
+    request::Request as _, DidChangeTextDocumentParams, NumberOrString,
+    TextDocumentContentChangeEvent, WorkDoneProgress, WorkDoneProgressBegin,
+    WorkDoneProgressCreateParams, WorkDoneProgressEnd, WorkDoneProgressReport,
 };
 use ra_flycheck::{CheckTask, Status};
 use ra_ide::{Canceled, FileId, LineIndex};
 use ra_prof::profile;
 use ra_project_model::{PackageRoot, ProjectWorkspace};
 use ra_vfs::VfsTask;
-use rustc_hash::FxHashSet;
 use serde::{de::DeserializeOwned, Serialize};
 use threadpool::ThreadPool;
 
@@ -38,10 +39,7 @@ use crate::{
     from_proto,
     global_state::{file_id_to_url, GlobalState, GlobalStateSnapshot},
     lsp_ext,
-    main_loop::{
-        pending_requests::{PendingRequest, PendingRequests},
-        subscriptions::Subscriptions,
-    },
+    main_loop::{request_metrics::RequestMetrics, subscriptions::Subscriptions},
     Result,
 };
 
@@ -153,9 +151,10 @@ pub fn main_loop(config: Config, connection: Connection) -> Result<()> {
                 register_options: Some(serde_json::to_value(registration_options).unwrap()),
             };
             let params = lsp_types::RegistrationParams { registrations: vec![registration] };
-            let request = request_new::<lsp_types::request::RegisterCapability>(
-                loop_state.next_request_id(),
+            let request = loop_state.req_queue.outgoing.register(
+                lsp_types::request::RegisterCapability::METHOD.to_string(),
                 params,
+                DO_NOTHING,
             );
             connection.sender.send(request.into()).unwrap();
         }
@@ -199,7 +198,7 @@ pub fn main_loop(config: Config, connection: Connection) -> Result<()> {
     global_state.analysis_host.request_cancellation();
     log::info!("waiting for tasks to finish...");
     task_receiver.into_iter().for_each(|task| {
-        on_task(task, &connection.sender, &mut loop_state.pending_requests, &mut global_state)
+        on_task(task, &connection.sender, &mut loop_state.req_queue.incoming, &mut global_state)
     });
     log::info!("...tasks have finished");
     log::info!("joining threadpool...");
@@ -264,27 +263,18 @@ impl fmt::Debug for Event {
     }
 }
 
-#[derive(Debug, Default)]
+type ReqHandler = fn(&mut GlobalState, Response);
+const DO_NOTHING: ReqHandler = |_, _| ();
+type Incoming = lsp_server::Incoming<(&'static str, Instant)>;
+
+#[derive(Default)]
 struct LoopState {
-    next_request_id: u64,
-    pending_responses: FxHashSet<RequestId>,
-    pending_requests: PendingRequests,
+    req_queue: ReqQueue<(&'static str, Instant), ReqHandler>,
     subscriptions: Subscriptions,
     workspace_loaded: bool,
     roots_progress_reported: Option<usize>,
     roots_scanned: usize,
     roots_total: usize,
-    configuration_request_id: Option<RequestId>,
-}
-
-impl LoopState {
-    fn next_request_id(&mut self) -> RequestId {
-        self.next_request_id += 1;
-        let res: RequestId = self.next_request_id.into();
-        let inserted = self.pending_responses.insert(res.clone());
-        assert!(inserted);
-        res
-    }
 }
 
 fn loop_turn(
@@ -307,7 +297,7 @@ fn loop_turn(
 
     match event {
         Event::Task(task) => {
-            on_task(task, &connection.sender, &mut loop_state.pending_requests, global_state);
+            on_task(task, &connection.sender, &mut loop_state.req_queue.incoming, global_state);
             global_state.maybe_collect_garbage();
         }
         Event::Vfs(task) => {
@@ -317,7 +307,7 @@ fn loop_turn(
         Event::Msg(msg) => match msg {
             Message::Request(req) => on_request(
                 global_state,
-                &mut loop_state.pending_requests,
+                &mut loop_state.req_queue.incoming,
                 pool,
                 task_sender,
                 &connection.sender,
@@ -328,32 +318,8 @@ fn loop_turn(
                 on_notification(&connection.sender, global_state, loop_state, not)?;
             }
             Message::Response(resp) => {
-                let removed = loop_state.pending_responses.remove(&resp.id);
-                if !removed {
-                    log::error!("unexpected response: {:?}", resp)
-                }
-
-                if Some(&resp.id) == loop_state.configuration_request_id.as_ref() {
-                    loop_state.configuration_request_id = None;
-                    log::debug!("config update response: '{:?}", resp);
-                    let Response { error, result, .. } = resp;
-
-                    match (error, result) {
-                        (Some(err), _) => {
-                            log::error!("failed to fetch the server settings: {:?}", err)
-                        }
-                        (None, Some(configs)) => {
-                            if let Some(new_config) = configs.get(0) {
-                                let mut config = global_state.config.clone();
-                                config.update(&new_config);
-                                global_state.update_configuration(config);
-                            }
-                        }
-                        (None, None) => {
-                            log::error!("received empty server settings response from the client")
-                        }
-                    }
-                }
+                let handler = loop_state.req_queue.outgoing.complete(resp.id.clone());
+                handler(global_state, resp)
             }
         },
     };
@@ -407,14 +373,19 @@ fn loop_turn(
 fn on_task(
     task: Task,
     msg_sender: &Sender<Message>,
-    pending_requests: &mut PendingRequests,
+    incoming_requests: &mut Incoming,
     state: &mut GlobalState,
 ) {
     match task {
         Task::Respond(response) => {
-            if let Some(completed) = pending_requests.finish(&response.id) {
-                log::info!("handled req#{} in {:?}", completed.id, completed.duration);
-                state.complete_request(completed);
+            if let Some((method, start)) = incoming_requests.complete(response.id.clone()) {
+                let duration = start.elapsed();
+                log::info!("handled req#{} in {:?}", response.id, duration);
+                state.complete_request(RequestMetrics {
+                    id: response.id.clone(),
+                    method: method.to_string(),
+                    duration,
+                });
                 msg_sender.send(response.into()).unwrap();
             }
         }
@@ -427,7 +398,7 @@ fn on_task(
 
 fn on_request(
     global_state: &mut GlobalState,
-    pending_requests: &mut PendingRequests,
+    incoming_requests: &mut Incoming,
     pool: &ThreadPool,
     task_sender: &Sender<Task>,
     msg_sender: &Sender<Message>,
@@ -440,7 +411,7 @@ fn on_request(
         global_state,
         task_sender,
         msg_sender,
-        pending_requests,
+        incoming_requests,
         request_received,
     };
     pool_dispatcher
@@ -504,12 +475,7 @@ fn on_notification(
                 NumberOrString::Number(id) => id.into(),
                 NumberOrString::String(id) => id.into(),
             };
-            if loop_state.pending_requests.cancel(&id) {
-                let response = Response::new_err(
-                    id,
-                    ErrorCode::RequestCanceled as i32,
-                    "canceled by client".to_string(),
-                );
+            if let Some(response) = loop_state.req_queue.incoming.cancel(id) {
                 msg_sender.send(response.into()).unwrap()
             }
             return Ok(());
@@ -572,18 +538,36 @@ fn on_notification(
         Ok(_) => {
             // As stated in https://github.com/microsoft/language-server-protocol/issues/676,
             // this notification's parameters should be ignored and the actual config queried separately.
-            let request_id = loop_state.next_request_id();
-            let request = request_new::<lsp_types::request::WorkspaceConfiguration>(
-                request_id.clone(),
+            let request = loop_state.req_queue.outgoing.register(
+                lsp_types::request::WorkspaceConfiguration::METHOD.to_string(),
                 lsp_types::ConfigurationParams {
                     items: vec![lsp_types::ConfigurationItem {
                         scope_uri: None,
                         section: Some("rust-analyzer".to_string()),
                     }],
                 },
+                |global_state, resp| {
+                    log::debug!("config update response: '{:?}", resp);
+                    let Response { error, result, .. } = resp;
+
+                    match (error, result) {
+                        (Some(err), _) => {
+                            log::error!("failed to fetch the server settings: {:?}", err)
+                        }
+                        (None, Some(configs)) => {
+                            if let Some(new_config) = configs.get(0) {
+                                let mut config = global_state.config.clone();
+                                config.update(&new_config);
+                                global_state.update_configuration(config);
+                            }
+                        }
+                        (None, None) => {
+                            log::error!("received empty server settings response from the client")
+                        }
+                    }
+                },
             );
             msg_sender.send(request.into())?;
-            loop_state.configuration_request_id = Some(request_id);
 
             return Ok(());
         }
@@ -752,13 +736,14 @@ fn send_startup_progress(sender: &Sender<Message>, loop_state: &mut LoopState) {
 
     match (prev, loop_state.workspace_loaded) {
         (None, false) => {
-            let work_done_progress_create = request_new::<lsp_types::request::WorkDoneProgressCreate>(
-                loop_state.next_request_id(),
+            let request = loop_state.req_queue.outgoing.register(
+                lsp_types::request::WorkDoneProgressCreate::METHOD.to_string(),
                 WorkDoneProgressCreateParams {
                     token: lsp_types::ProgressToken::String("rustAnalyzer/startup".into()),
                 },
+                DO_NOTHING,
             );
-            sender.send(work_done_progress_create.into()).unwrap();
+            sender.send(request.into()).unwrap();
             send_startup_progress_notif(
                 sender,
                 WorkDoneProgress::Begin(WorkDoneProgressBegin {
@@ -800,7 +785,7 @@ struct PoolDispatcher<'a> {
     req: Option<Request>,
     pool: &'a ThreadPool,
     global_state: &'a mut GlobalState,
-    pending_requests: &'a mut PendingRequests,
+    incoming_requests: &'a mut Incoming,
     msg_sender: &'a Sender<Message>,
     task_sender: &'a Sender<Task>,
     request_received: Instant,
@@ -829,7 +814,7 @@ impl<'a> PoolDispatcher<'a> {
             result_to_task::<R>(id, result)
         })
         .map_err(|_| format!("sync task {:?} panicked", R::METHOD))?;
-        on_task(task, self.msg_sender, self.pending_requests, self.global_state);
+        on_task(task, self.msg_sender, self.incoming_requests, self.global_state);
         Ok(self)
     }
 
@@ -876,11 +861,7 @@ impl<'a> PoolDispatcher<'a> {
                 return None;
             }
         };
-        self.pending_requests.start(PendingRequest {
-            id: id.clone(),
-            method: R::METHOD.to_string(),
-            received: self.request_received,
-        });
+        self.incoming_requests.register(id.clone(), (R::METHOD, self.request_received));
         Some((id, params))
     }
 
@@ -993,14 +974,6 @@ where
     Notification::new(N::METHOD.to_string(), params)
 }
 
-fn request_new<R>(id: RequestId, params: R::Params) -> Request
-where
-    R: lsp_types::request::Request,
-    R::Params: Serialize,
-{
-    Request::new(id, R::METHOD.to_string(), params)
-}
-
 #[cfg(test)]
 mod tests {
     use std::borrow::Cow;
diff --git a/crates/rust-analyzer/src/main_loop/pending_requests.rs b/crates/rust-analyzer/src/main_loop/pending_requests.rs
deleted file mode 100644
index 73b33e419..000000000
--- a/crates/rust-analyzer/src/main_loop/pending_requests.rs
+++ /dev/null
@@ -1,75 +0,0 @@
-//! Data structures that keep track of inflight requests.
-
-use std::time::{Duration, Instant};
-
-use lsp_server::RequestId;
-use rustc_hash::FxHashMap;
-
-#[derive(Debug)]
-pub struct CompletedRequest {
-    pub id: RequestId,
-    pub method: String,
-    pub duration: Duration,
-}
-
-#[derive(Debug)]
-pub(crate) struct PendingRequest {
-    pub(crate) id: RequestId,
-    pub(crate) method: String,
-    pub(crate) received: Instant,
-}
-
-impl From<PendingRequest> for CompletedRequest {
-    fn from(pending: PendingRequest) -> CompletedRequest {
-        CompletedRequest {
-            id: pending.id,
-            method: pending.method,
-            duration: pending.received.elapsed(),
-        }
-    }
-}
-
-#[derive(Debug, Default)]
-pub(crate) struct PendingRequests {
-    map: FxHashMap<RequestId, PendingRequest>,
-}
-
-impl PendingRequests {
-    pub(crate) fn start(&mut self, request: PendingRequest) {
-        let id = request.id.clone();
-        let prev = self.map.insert(id.clone(), request);
-        assert!(prev.is_none(), "duplicate request with id {}", id);
-    }
-    pub(crate) fn cancel(&mut self, id: &RequestId) -> bool {
-        self.map.remove(id).is_some()
-    }
-    pub(crate) fn finish(&mut self, id: &RequestId) -> Option<CompletedRequest> {
-        self.map.remove(id).map(CompletedRequest::from)
-    }
-}
-
-const N_COMPLETED_REQUESTS: usize = 10;
-
-#[derive(Debug, Default)]
-pub struct LatestRequests {
-    // hand-rolling VecDeque here to print things in a nicer way
-    buf: [Option<CompletedRequest>; N_COMPLETED_REQUESTS],
-    idx: usize,
-}
-
-impl LatestRequests {
-    pub(crate) fn record(&mut self, request: CompletedRequest) {
-        // special case: don't track status request itself
-        if request.method == "rust-analyzer/analyzerStatus" {
-            return;
-        }
-        let idx = self.idx;
-        self.buf[idx] = Some(request);
-        self.idx = (idx + 1) % N_COMPLETED_REQUESTS;
-    }
-
-    pub(crate) fn iter(&self) -> impl Iterator<Item = (bool, &CompletedRequest)> {
-        let idx = self.idx;
-        self.buf.iter().enumerate().filter_map(move |(i, req)| Some((i == idx, req.as_ref()?)))
-    }
-}
diff --git a/crates/rust-analyzer/src/main_loop/request_metrics.rs b/crates/rust-analyzer/src/main_loop/request_metrics.rs
new file mode 100644
index 000000000..b1019e2d6
--- /dev/null
+++ b/crates/rust-analyzer/src/main_loop/request_metrics.rs
@@ -0,0 +1,37 @@
+//! Records stats about requests
+use std::time::Duration;
+
+use lsp_server::RequestId;
+
+#[derive(Debug)]
+pub(crate) struct RequestMetrics {
+    pub(crate) id: RequestId,
+    pub(crate) method: String,
+    pub(crate) duration: Duration,
+}
+
+const N_COMPLETED_REQUESTS: usize = 10;
+
+#[derive(Debug, Default)]
+pub(crate) struct LatestRequests {
+    // hand-rolling VecDeque here to print things in a nicer way
+    buf: [Option<RequestMetrics>; N_COMPLETED_REQUESTS],
+    idx: usize,
+}
+
+impl LatestRequests {
+    pub(crate) fn record(&mut self, request: RequestMetrics) {
+        // special case: don't track status request itself
+        if request.method == "rust-analyzer/analyzerStatus" {
+            return;
+        }
+        let idx = self.idx;
+        self.buf[idx] = Some(request);
+        self.idx = (idx + 1) % N_COMPLETED_REQUESTS;
+    }
+
+    pub(crate) fn iter(&self) -> impl Iterator<Item = (bool, &RequestMetrics)> {
+        let idx = self.idx;
+        self.buf.iter().enumerate().filter_map(move |(i, req)| Some((i == idx, req.as_ref()?)))
+    }
+}