diff options
author | bors[bot] <26634292+bors[bot]@users.noreply.github.com> | 2020-04-06 08:49:09 +0100 |
---|---|---|
committer | GitHub <[email protected]> | 2020-04-06 08:49:09 +0100 |
commit | a93a04fc9e48bdcc9132738c391de77bd25dca7e (patch) | |
tree | 70ad7c87e686111e3d2e150aea08612713b46079 /crates/ra_hir_ty/src/lib.rs | |
parent | 0625c76009d394bf73eb13c3de65304ce4283a1c (diff) | |
parent | 952714685a7c0e0a1c9970839ce307806adaa176 (diff) |
Merge #3744
3744: Upgrade Chalk r=matklad a=flodiebold
Co-authored-by: Florian Diebold <[email protected]>
Co-authored-by: Florian Diebold <[email protected]>
Diffstat (limited to 'crates/ra_hir_ty/src/lib.rs')
-rw-r--r-- | crates/ra_hir_ty/src/lib.rs | 103 |
1 files changed, 73 insertions, 30 deletions
diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs index 6c5469ecd..a9022dee7 100644 --- a/crates/ra_hir_ty/src/lib.rs +++ b/crates/ra_hir_ty/src/lib.rs | |||
@@ -64,6 +64,8 @@ pub use lower::{ | |||
64 | }; | 64 | }; |
65 | pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment}; | 65 | pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment}; |
66 | 66 | ||
67 | pub use chalk_ir::{BoundVar, DebruijnIndex}; | ||
68 | |||
67 | /// A type constructor or type name: this might be something like the primitive | 69 | /// A type constructor or type name: this might be something like the primitive |
68 | /// type `bool`, a struct like `Vec`, or things like function pointers or | 70 | /// type `bool`, a struct like `Vec`, or things like function pointers or |
69 | /// tuples. | 71 | /// tuples. |
@@ -265,7 +267,11 @@ impl TypeWalk for ProjectionTy { | |||
265 | self.parameters.walk(f); | 267 | self.parameters.walk(f); |
266 | } | 268 | } |
267 | 269 | ||
268 | fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { | 270 | fn walk_mut_binders( |
271 | &mut self, | ||
272 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
273 | binders: DebruijnIndex, | ||
274 | ) { | ||
269 | self.parameters.walk_mut_binders(f, binders); | 275 | self.parameters.walk_mut_binders(f, binders); |
270 | } | 276 | } |
271 | } | 277 | } |
@@ -299,7 +305,7 @@ pub enum Ty { | |||
299 | /// parameters get turned into variables; during trait resolution, inference | 305 | /// parameters get turned into variables; during trait resolution, inference |
300 | /// variables get turned into bound variables and back; and in `Dyn` the | 306 | /// variables get turned into bound variables and back; and in `Dyn` the |
301 | /// `Self` type is represented with a bound variable as well. | 307 | /// `Self` type is represented with a bound variable as well. |
302 | Bound(u32), | 308 | Bound(BoundVar), |
303 | 309 | ||
304 | /// A type variable used during type checking. | 310 | /// A type variable used during type checking. |
305 | Infer(InferTy), | 311 | Infer(InferTy), |
@@ -337,7 +343,11 @@ impl TypeWalk for Substs { | |||
337 | } | 343 | } |
338 | } | 344 | } |
339 | 345 | ||
340 | fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { | 346 | fn walk_mut_binders( |
347 | &mut self, | ||
348 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
349 | binders: DebruijnIndex, | ||
350 | ) { | ||
341 | for t in make_mut_slice(&mut self.0) { | 351 | for t in make_mut_slice(&mut self.0) { |
342 | t.walk_mut_binders(f, binders); | 352 | t.walk_mut_binders(f, binders); |
343 | } | 353 | } |
@@ -381,7 +391,13 @@ impl Substs { | |||
381 | 391 | ||
382 | /// Return Substs that replace each parameter by a bound variable. | 392 | /// Return Substs that replace each parameter by a bound variable. |
383 | pub(crate) fn bound_vars(generic_params: &Generics) -> Substs { | 393 | pub(crate) fn bound_vars(generic_params: &Generics) -> Substs { |
384 | Substs(generic_params.iter().enumerate().map(|(idx, _)| Ty::Bound(idx as u32)).collect()) | 394 | Substs( |
395 | generic_params | ||
396 | .iter() | ||
397 | .enumerate() | ||
398 | .map(|(idx, _)| Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx))) | ||
399 | .collect(), | ||
400 | ) | ||
385 | } | 401 | } |
386 | 402 | ||
387 | pub fn build_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder { | 403 | pub fn build_for_def(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> SubstsBuilder { |
@@ -425,8 +441,8 @@ impl SubstsBuilder { | |||
425 | self.param_count - self.vec.len() | 441 | self.param_count - self.vec.len() |
426 | } | 442 | } |
427 | 443 | ||
428 | pub fn fill_with_bound_vars(self, starting_from: u32) -> Self { | 444 | pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self { |
429 | self.fill((starting_from..).map(Ty::Bound)) | 445 | self.fill((starting_from..).map(|idx| Ty::Bound(BoundVar::new(debruijn, idx)))) |
430 | } | 446 | } |
431 | 447 | ||
432 | pub fn fill_with_unknown(self) -> Self { | 448 | pub fn fill_with_unknown(self) -> Self { |
@@ -507,7 +523,11 @@ impl TypeWalk for TraitRef { | |||
507 | self.substs.walk(f); | 523 | self.substs.walk(f); |
508 | } | 524 | } |
509 | 525 | ||
510 | fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { | 526 | fn walk_mut_binders( |
527 | &mut self, | ||
528 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
529 | binders: DebruijnIndex, | ||
530 | ) { | ||
511 | self.substs.walk_mut_binders(f, binders); | 531 | self.substs.walk_mut_binders(f, binders); |
512 | } | 532 | } |
513 | } | 533 | } |
@@ -558,7 +578,11 @@ impl TypeWalk for GenericPredicate { | |||
558 | } | 578 | } |
559 | } | 579 | } |
560 | 580 | ||
561 | fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { | 581 | fn walk_mut_binders( |
582 | &mut self, | ||
583 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
584 | binders: DebruijnIndex, | ||
585 | ) { | ||
562 | match self { | 586 | match self { |
563 | GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders), | 587 | GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders), |
564 | GenericPredicate::Projection(projection_pred) => { | 588 | GenericPredicate::Projection(projection_pred) => { |
@@ -616,7 +640,11 @@ impl TypeWalk for FnSig { | |||
616 | } | 640 | } |
617 | } | 641 | } |
618 | 642 | ||
619 | fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { | 643 | fn walk_mut_binders( |
644 | &mut self, | ||
645 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
646 | binders: DebruijnIndex, | ||
647 | ) { | ||
620 | for t in make_mut_slice(&mut self.params_and_return) { | 648 | for t in make_mut_slice(&mut self.params_and_return) { |
621 | t.walk_mut_binders(f, binders); | 649 | t.walk_mut_binders(f, binders); |
622 | } | 650 | } |
@@ -755,7 +783,7 @@ impl Ty { | |||
755 | pub trait TypeWalk { | 783 | pub trait TypeWalk { |
756 | fn walk(&self, f: &mut impl FnMut(&Ty)); | 784 | fn walk(&self, f: &mut impl FnMut(&Ty)); |
757 | fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { | 785 | fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { |
758 | self.walk_mut_binders(&mut |ty, _binders| f(ty), 0); | 786 | self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST); |
759 | } | 787 | } |
760 | /// Walk the type, counting entered binders. | 788 | /// Walk the type, counting entered binders. |
761 | /// | 789 | /// |
@@ -767,9 +795,17 @@ pub trait TypeWalk { | |||
767 | /// that. Currently, the only thing that introduces bound variables on our | 795 | /// that. Currently, the only thing that introduces bound variables on our |
768 | /// side are `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound | 796 | /// side are `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound |
769 | /// variable for the self type. | 797 | /// variable for the self type. |
770 | fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize); | 798 | fn walk_mut_binders( |
771 | 799 | &mut self, | |
772 | fn fold_binders(mut self, f: &mut impl FnMut(Ty, usize) -> Ty, binders: usize) -> Self | 800 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), |
801 | binders: DebruijnIndex, | ||
802 | ); | ||
803 | |||
804 | fn fold_binders( | ||
805 | mut self, | ||
806 | f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty, | ||
807 | binders: DebruijnIndex, | ||
808 | ) -> Self | ||
773 | where | 809 | where |
774 | Self: Sized, | 810 | Self: Sized, |
775 | { | 811 | { |
@@ -795,40 +831,43 @@ pub trait TypeWalk { | |||
795 | } | 831 | } |
796 | 832 | ||
797 | /// Substitutes `Ty::Bound` vars with the given substitution. | 833 | /// Substitutes `Ty::Bound` vars with the given substitution. |
798 | fn subst_bound_vars(mut self, substs: &Substs) -> Self | 834 | fn subst_bound_vars(self, substs: &Substs) -> Self |
835 | where | ||
836 | Self: Sized, | ||
837 | { | ||
838 | self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST) | ||
839 | } | ||
840 | |||
841 | /// Substitutes `Ty::Bound` vars with the given substitution. | ||
842 | fn subst_bound_vars_at_depth(mut self, substs: &Substs, depth: DebruijnIndex) -> Self | ||
799 | where | 843 | where |
800 | Self: Sized, | 844 | Self: Sized, |
801 | { | 845 | { |
802 | self.walk_mut_binders( | 846 | self.walk_mut_binders( |
803 | &mut |ty, binders| { | 847 | &mut |ty, binders| { |
804 | if let &mut Ty::Bound(idx) = ty { | 848 | if let &mut Ty::Bound(bound) = ty { |
805 | if idx as usize >= binders && (idx as usize - binders) < substs.len() { | 849 | if bound.debruijn >= binders { |
806 | *ty = substs.0[idx as usize - binders].clone(); | 850 | *ty = substs.0[bound.index].clone(); |
807 | } else if idx as usize >= binders + substs.len() { | ||
808 | // shift free binders | ||
809 | *ty = Ty::Bound(idx - substs.len() as u32); | ||
810 | } | 851 | } |
811 | } | 852 | } |
812 | }, | 853 | }, |
813 | 0, | 854 | depth, |
814 | ); | 855 | ); |
815 | self | 856 | self |
816 | } | 857 | } |
817 | 858 | // /// Shifts up debruijn indices of `Ty::Bound` vars by `n`. | |
818 | /// Shifts up `Ty::Bound` vars by `n`. | 859 | fn shift_bound_vars(self, n: DebruijnIndex) -> Self |
819 | fn shift_bound_vars(self, n: i32) -> Self | ||
820 | where | 860 | where |
821 | Self: Sized, | 861 | Self: Sized, |
822 | { | 862 | { |
823 | self.fold_binders( | 863 | self.fold_binders( |
824 | &mut |ty, binders| match ty { | 864 | &mut |ty, binders| match ty { |
825 | Ty::Bound(idx) if idx as usize >= binders => { | 865 | Ty::Bound(bound) if bound.debruijn >= binders => { |
826 | assert!(idx as i32 >= -n); | 866 | Ty::Bound(bound.shifted_in_from(n)) |
827 | Ty::Bound((idx as i32 + n) as u32) | ||
828 | } | 867 | } |
829 | ty => ty, | 868 | ty => ty, |
830 | }, | 869 | }, |
831 | 0, | 870 | DebruijnIndex::INNERMOST, |
832 | ) | 871 | ) |
833 | } | 872 | } |
834 | } | 873 | } |
@@ -856,7 +895,11 @@ impl TypeWalk for Ty { | |||
856 | f(self); | 895 | f(self); |
857 | } | 896 | } |
858 | 897 | ||
859 | fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { | 898 | fn walk_mut_binders( |
899 | &mut self, | ||
900 | f: &mut impl FnMut(&mut Ty, DebruijnIndex), | ||
901 | binders: DebruijnIndex, | ||
902 | ) { | ||
860 | match self { | 903 | match self { |
861 | Ty::Apply(a_ty) => { | 904 | Ty::Apply(a_ty) => { |
862 | a_ty.parameters.walk_mut_binders(f, binders); | 905 | a_ty.parameters.walk_mut_binders(f, binders); |
@@ -866,7 +909,7 @@ impl TypeWalk for Ty { | |||
866 | } | 909 | } |
867 | Ty::Dyn(predicates) | Ty::Opaque(predicates) => { | 910 | Ty::Dyn(predicates) | Ty::Opaque(predicates) => { |
868 | for p in make_mut_slice(predicates) { | 911 | for p in make_mut_slice(predicates) { |
869 | p.walk_mut_binders(f, binders + 1); | 912 | p.walk_mut_binders(f, binders.shifted_in()); |
870 | } | 913 | } |
871 | } | 914 | } |
872 | Ty::Placeholder { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {} | 915 | Ty::Placeholder { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {} |