diff options
author | Florian Diebold <[email protected]> | 2019-03-31 19:02:16 +0100 |
---|---|---|
committer | Florian Diebold <[email protected]> | 2019-04-14 10:28:53 +0100 |
commit | a1ed53a4f183b5826162eb9e998207b92be9c57f (patch) | |
tree | 7c139a7dc38483188653c6d40583cddac9d23192 /crates/ra_hir/src/ty/traits.rs | |
parent | 413c87f155ab6b389b1cc122b5739716acccb476 (diff) |
More trait infrastructure
- make it possible to get parent trait from method
- add 'obligation' machinery for checking that a type implements a
trait (and inferring facts about type variables from that)
- handle type parameters of traits (to a certain degree)
- improve the hacky implements check to cover enough cases to exercise the
handling of traits with type parameters
- basic canonicalization (will probably also be done by Chalk)
Diffstat (limited to 'crates/ra_hir/src/ty/traits.rs')
-rw-r--r-- | crates/ra_hir/src/ty/traits.rs | 112 |
1 files changed, 112 insertions, 0 deletions
diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs new file mode 100644 index 000000000..f8c3958bd --- /dev/null +++ b/crates/ra_hir/src/ty/traits.rs | |||
@@ -0,0 +1,112 @@ | |||
1 | //! Stuff that will probably mostly replaced by Chalk. | ||
2 | use std::collections::HashMap; | ||
3 | |||
4 | use crate::db::HirDatabase; | ||
5 | use super::{ TraitRef, Substs, infer::{ TypeVarId, InferTy}, Ty}; | ||
6 | |||
7 | // Copied (and simplified) from Chalk | ||
8 | |||
9 | #[derive(Clone, Debug, PartialEq, Eq)] | ||
10 | /// A (possible) solution for a proposed goal. Usually packaged in a `Result`, | ||
11 | /// where `Err` represents definite *failure* to prove a goal. | ||
12 | pub enum Solution { | ||
13 | /// The goal indeed holds, and there is a unique value for all existential | ||
14 | /// variables. | ||
15 | Unique(Substs), | ||
16 | |||
17 | /// The goal may be provable in multiple ways, but regardless we may have some guidance | ||
18 | /// for type inference. | ||
19 | Ambig(Guidance), | ||
20 | } | ||
21 | |||
22 | #[derive(Clone, Debug, PartialEq, Eq)] | ||
23 | /// When a goal holds ambiguously (e.g., because there are multiple possible | ||
24 | /// solutions), we issue a set of *guidance* back to type inference. | ||
25 | pub enum Guidance { | ||
26 | /// The existential variables *must* have the given values if the goal is | ||
27 | /// ever to hold, but that alone isn't enough to guarantee the goal will | ||
28 | /// actually hold. | ||
29 | Definite(Substs), | ||
30 | |||
31 | /// There are multiple plausible values for the existentials, but the ones | ||
32 | /// here are suggested as the preferred choice heuristically. These should | ||
33 | /// be used for inference fallback only. | ||
34 | Suggested(Substs), | ||
35 | |||
36 | /// There's no useful information to feed back to type inference | ||
37 | Unknown, | ||
38 | } | ||
39 | |||
40 | /// Something that needs to be proven (by Chalk) during type checking, e.g. that | ||
41 | /// a certain type implements a certain trait. Proving the Obligation might | ||
42 | /// result in additional information about inference variables. | ||
43 | /// | ||
44 | /// This might be handled by Chalk when we integrate it? | ||
45 | #[derive(Clone, Debug, PartialEq, Eq)] | ||
46 | pub enum Obligation { | ||
47 | /// Prove that a certain type implements a trait (the type is the `Self` type | ||
48 | /// parameter to the `TraitRef`). | ||
49 | Trait(TraitRef), | ||
50 | } | ||
51 | |||
52 | /// Rudimentary check whether an impl exists for a given type and trait; this | ||
53 | /// will actually be done by chalk. | ||
54 | pub(crate) fn implements(db: &impl HirDatabase, trait_ref: TraitRef) -> Option<Solution> { | ||
55 | // FIXME use all trait impls in the whole crate graph | ||
56 | let krate = trait_ref.trait_.module(db).krate(db); | ||
57 | let krate = match krate { | ||
58 | Some(krate) => krate, | ||
59 | None => return None, | ||
60 | }; | ||
61 | let crate_impl_blocks = db.impls_in_crate(krate); | ||
62 | let mut impl_blocks = crate_impl_blocks.lookup_impl_blocks_for_trait(&trait_ref.trait_); | ||
63 | impl_blocks | ||
64 | .find_map(|impl_block| unify_trait_refs(&trait_ref, &impl_block.target_trait_ref(db)?)) | ||
65 | } | ||
66 | |||
67 | pub(super) fn canonicalize(trait_ref: TraitRef) -> (TraitRef, Vec<TypeVarId>) { | ||
68 | let mut canonical = HashMap::new(); // mapping uncanonical -> canonical | ||
69 | let mut uncanonical = Vec::new(); // mapping canonical -> uncanonical (which is dense) | ||
70 | let mut substs = trait_ref.substs.0.to_vec(); | ||
71 | for ty in &mut substs { | ||
72 | ty.walk_mut(&mut |ty| match ty { | ||
73 | Ty::Infer(InferTy::TypeVar(tv)) => { | ||
74 | let tv: &mut TypeVarId = tv; | ||
75 | *tv = *canonical.entry(*tv).or_insert_with(|| { | ||
76 | let i = uncanonical.len(); | ||
77 | uncanonical.push(*tv); | ||
78 | TypeVarId(i as u32) | ||
79 | }); | ||
80 | } | ||
81 | _ => {} | ||
82 | }); | ||
83 | } | ||
84 | (TraitRef { substs: substs.into(), ..trait_ref }, uncanonical) | ||
85 | } | ||
86 | |||
87 | fn unify_trait_refs(tr1: &TraitRef, tr2: &TraitRef) -> Option<Solution> { | ||
88 | if tr1.trait_ != tr2.trait_ { | ||
89 | return None; | ||
90 | } | ||
91 | let mut solution_substs = Vec::new(); | ||
92 | for (t1, t2) in tr1.substs.0.iter().zip(tr2.substs.0.iter()) { | ||
93 | // this is very bad / hacky 'unification' logic, just enough to make the simple tests pass | ||
94 | match (t1, t2) { | ||
95 | (_, Ty::Infer(InferTy::TypeVar(_))) | (_, Ty::Unknown) | (_, Ty::Param { .. }) => { | ||
96 | // type variable (or similar) in the impl, we just assume it works | ||
97 | } | ||
98 | (Ty::Infer(InferTy::TypeVar(v1)), _) => { | ||
99 | // type variable in the query and fixed type in the impl, record its value | ||
100 | solution_substs.resize_with(v1.0 as usize + 1, || Ty::Unknown); | ||
101 | solution_substs[v1.0 as usize] = t2.clone(); | ||
102 | } | ||
103 | _ => { | ||
104 | // check that they're equal (actually we'd have to recurse etc.) | ||
105 | if t1 != t2 { | ||
106 | return None; | ||
107 | } | ||
108 | } | ||
109 | } | ||
110 | } | ||
111 | Some(Solution::Unique(solution_substs.into())) | ||
112 | } | ||