aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFlorian Diebold <[email protected]>2021-04-29 19:18:41 +0100
committerFlorian Diebold <[email protected]>2021-04-29 19:18:41 +0100
commit2d20ab7eaf928dfaf3e1823707a3b6b84e918d07 (patch)
tree472c16ab18b9abe63306524a59b26715d3d9ef2f
parentb384cfcb81ae0db541cfe02213e9d95041b77362 (diff)
Rewrite all_super_trait_refs as an iterator
Doesn't fix the bug I was trying to fix, but now that I did it anyway it seems fine to keep.
-rw-r--r--crates/hir_ty/src/utils.rs52
1 files changed, 34 insertions, 18 deletions
diff --git a/crates/hir_ty/src/utils.rs b/crates/hir_ty/src/utils.rs
index 2f04ee57a..2f490fb92 100644
--- a/crates/hir_ty/src/utils.rs
+++ b/crates/hir_ty/src/utils.rs
@@ -1,6 +1,8 @@
1//! Helper functions for working with def, which don't need to be a separate 1//! Helper functions for working with def, which don't need to be a separate
2//! query, but can't be computed directly from `*Data` (ie, which need a `db`). 2//! query, but can't be computed directly from `*Data` (ie, which need a `db`).
3 3
4use std::iter;
5
4use chalk_ir::{fold::Shift, BoundVar, DebruijnIndex}; 6use chalk_ir::{fold::Shift, BoundVar, DebruijnIndex};
5use hir_def::{ 7use hir_def::{
6 db::DefDatabase, 8 db::DefDatabase,
@@ -14,8 +16,12 @@ use hir_def::{
14 AssocContainerId, GenericDefId, Lookup, TraitId, TypeAliasId, TypeParamId, 16 AssocContainerId, GenericDefId, Lookup, TraitId, TypeAliasId, TypeParamId,
15}; 17};
16use hir_expand::name::{name, Name}; 18use hir_expand::name::{name, Name};
19use rustc_hash::FxHashSet;
17 20
18use crate::{db::HirDatabase, Interner, Substitution, TraitRef, TraitRefExt, TyKind, WhereClause}; 21use crate::{
22 db::HirDatabase, ChalkTraitId, Interner, Substitution, TraitRef, TraitRefExt, TyKind,
23 WhereClause,
24};
19 25
20fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> { 26fn direct_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
21 let resolver = trait_.resolver(db); 27 let resolver = trait_.resolver(db);
@@ -102,25 +108,35 @@ pub fn all_super_traits(db: &dyn DefDatabase, trait_: TraitId) -> Vec<TraitId> {
102/// `all_super_traits` is that we keep track of type parameters; for example if 108/// `all_super_traits` is that we keep track of type parameters; for example if
103/// we have `Self: Trait<u32, i32>` and `Trait<T, U>: OtherTrait<U>` we'll get 109/// we have `Self: Trait<u32, i32>` and `Trait<T, U>: OtherTrait<U>` we'll get
104/// `Self: OtherTrait<i32>`. 110/// `Self: OtherTrait<i32>`.
105pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) -> Vec<TraitRef> { 111pub(super) fn all_super_trait_refs(db: &dyn HirDatabase, trait_ref: TraitRef) -> SuperTraits {
106 // FIXME: replace by Chalk's `super_traits`, maybe make this a query 112 SuperTraits { db, seen: iter::once(trait_ref.trait_id).collect(), stack: vec![trait_ref] }
113}
107 114
108 // we need to take care a bit here to avoid infinite loops in case of cycles 115pub(super) struct SuperTraits<'a> {
109 // (i.e. if we have `trait A: B; trait B: A;`) 116 db: &'a dyn HirDatabase,
110 let mut result = vec![trait_ref]; 117 stack: Vec<TraitRef>,
111 let mut i = 0; 118 seen: FxHashSet<ChalkTraitId>,
112 while i < result.len() { 119}
113 let t = &result[i]; 120
114 // yeah this is quadratic, but trait hierarchies should be flat 121impl<'a> SuperTraits<'a> {
115 // enough that this doesn't matter 122 fn elaborate(&mut self, trait_ref: &TraitRef) {
116 for tt in direct_super_trait_refs(db, t) { 123 let mut trait_refs = direct_super_trait_refs(self.db, trait_ref);
117 if !result.iter().any(|tr| tr.trait_id == tt.trait_id) { 124 trait_refs.retain(|tr| !self.seen.contains(&tr.trait_id));
118 result.push(tt); 125 self.stack.extend(trait_refs);
119 } 126 }
127}
128
129impl<'a> Iterator for SuperTraits<'a> {
130 type Item = TraitRef;
131
132 fn next(&mut self) -> Option<Self::Item> {
133 if let Some(next) = self.stack.pop() {
134 self.elaborate(&next);
135 Some(next)
136 } else {
137 None
120 } 138 }
121 i += 1;
122 } 139 }
123 result
124} 140}
125 141
126pub(super) fn associated_type_by_name_including_super_traits( 142pub(super) fn associated_type_by_name_including_super_traits(
@@ -128,7 +144,7 @@ pub(super) fn associated_type_by_name_including_super_traits(
128 trait_ref: TraitRef, 144 trait_ref: TraitRef,
129 name: &Name, 145 name: &Name,
130) -> Option<(TraitRef, TypeAliasId)> { 146) -> Option<(TraitRef, TypeAliasId)> {
131 all_super_trait_refs(db, trait_ref).into_iter().find_map(|t| { 147 all_super_trait_refs(db, trait_ref).find_map(|t| {
132 let assoc_type = db.trait_data(t.hir_trait_id()).associated_type_by_name(name)?; 148 let assoc_type = db.trait_data(t.hir_trait_id()).associated_type_by_name(name)?;
133 Some((t, assoc_type)) 149 Some((t, assoc_type))
134 }) 150 })