hir_ty/
generics.rs

1//! Utilities for working with generics.
2//!
3//! The layout for generics as expected by chalk are as follows:
4//! - Parent parameters
5//! - Optional Self parameter
6//! - Lifetime parameters
7//! - Type or Const parameters
8//!
9//! where parent follows the same scheme.
10use std::ops;
11
12use chalk_ir::{BoundVar, DebruijnIndex, cast::Cast as _};
13use hir_def::{
14    ConstParamId, GenericDefId, GenericParamId, ItemContainerId, LifetimeParamId, Lookup,
15    TypeOrConstParamId, TypeParamId,
16    db::DefDatabase,
17    expr_store::ExpressionStore,
18    hir::generics::{
19        GenericParamDataRef, GenericParams, LifetimeParamData, LocalLifetimeParamId,
20        LocalTypeOrConstParamId, TypeOrConstParamData, TypeParamProvenance, WherePredicate,
21    },
22};
23use itertools::chain;
24use triomphe::Arc;
25
26use crate::{Interner, Substitution, db::HirDatabase, lt_to_placeholder_idx, to_placeholder_idx};
27
28pub fn generics(db: &dyn DefDatabase, def: GenericDefId) -> Generics {
29    let parent_generics = parent_generic_def(db, def).map(|def| Box::new(generics(db, def)));
30    let (params, store) = db.generic_params_and_store(def);
31    let has_trait_self_param = params.trait_self_param().is_some();
32    Generics { def, params, parent_generics, has_trait_self_param, store }
33}
34#[derive(Clone, Debug)]
35pub struct Generics {
36    def: GenericDefId,
37    params: Arc<GenericParams>,
38    store: Arc<ExpressionStore>,
39    parent_generics: Option<Box<Generics>>,
40    has_trait_self_param: bool,
41}
42
43impl<T> ops::Index<T> for Generics
44where
45    GenericParams: ops::Index<T>,
46{
47    type Output = <GenericParams as ops::Index<T>>::Output;
48    fn index(&self, index: T) -> &Self::Output {
49        &self.params[index]
50    }
51}
52
53impl Generics {
54    pub(crate) fn def(&self) -> GenericDefId {
55        self.def
56    }
57
58    pub(crate) fn store(&self) -> &ExpressionStore {
59        &self.store
60    }
61
62    pub(crate) fn where_predicates(&self) -> impl Iterator<Item = &WherePredicate> {
63        self.params.where_predicates().iter()
64    }
65
66    pub(crate) fn has_no_predicates(&self) -> bool {
67        self.params.has_no_predicates()
68            && self.parent_generics.as_ref().is_none_or(|g| g.params.has_no_predicates())
69    }
70
71    pub(crate) fn is_empty(&self) -> bool {
72        self.params.is_empty() && self.parent_generics.as_ref().is_none_or(|g| g.params.is_empty())
73    }
74
75    pub(crate) fn iter_id(&self) -> impl Iterator<Item = GenericParamId> + '_ {
76        self.iter_parent_id().chain(self.iter_self_id())
77    }
78
79    pub(crate) fn iter_self_id(&self) -> impl Iterator<Item = GenericParamId> + '_ {
80        self.iter_self().map(|(id, _)| id)
81    }
82
83    pub(crate) fn iter_parent_id(&self) -> impl Iterator<Item = GenericParamId> + '_ {
84        self.iter_parent().map(|(id, _)| id)
85    }
86
87    pub(crate) fn iter_self_type_or_consts(
88        &self,
89    ) -> impl DoubleEndedIterator<Item = (LocalTypeOrConstParamId, &TypeOrConstParamData)> + '_
90    {
91        let mut toc = self.params.iter_type_or_consts();
92        let trait_self_param = self.has_trait_self_param.then(|| toc.next()).flatten();
93        chain!(trait_self_param, toc)
94    }
95
96    /// Iterate over the parent params followed by self params.
97    pub(crate) fn iter(
98        &self,
99    ) -> impl DoubleEndedIterator<Item = (GenericParamId, GenericParamDataRef<'_>)> + '_ {
100        self.iter_parent().chain(self.iter_self())
101    }
102
103    pub(crate) fn iter_parents_with_store(
104        &self,
105    ) -> impl Iterator<Item = ((GenericParamId, GenericParamDataRef<'_>), &ExpressionStore)> + '_
106    {
107        self.iter_parent()
108            .zip(self.parent_generics().into_iter().flat_map(|it| std::iter::repeat(&*it.store)))
109    }
110
111    /// Iterate over the params without parent params.
112    pub(crate) fn iter_self(
113        &self,
114    ) -> impl DoubleEndedIterator<Item = (GenericParamId, GenericParamDataRef<'_>)> + '_ {
115        let mut toc = self.params.iter_type_or_consts().map(from_toc_id(self));
116        let trait_self_param = self.has_trait_self_param.then(|| toc.next()).flatten();
117        chain!(trait_self_param, self.params.iter_lt().map(from_lt_id(self)), toc)
118    }
119
120    /// Iterator over types and const params of parent.
121    pub(crate) fn iter_parent(
122        &self,
123    ) -> impl DoubleEndedIterator<Item = (GenericParamId, GenericParamDataRef<'_>)> + '_ {
124        self.parent_generics().into_iter().flat_map(|it| {
125            let mut toc = it.params.iter_type_or_consts().map(from_toc_id(it));
126            let trait_self_param = it.has_trait_self_param.then(|| toc.next()).flatten();
127            chain!(trait_self_param, it.params.iter_lt().map(from_lt_id(it)), toc)
128        })
129    }
130
131    /// Returns total number of generic parameters in scope, including those from parent.
132    pub(crate) fn len(&self) -> usize {
133        let parent = self.parent_generics().map_or(0, Generics::len);
134        let child = self.params.len();
135        parent + child
136    }
137
138    /// Returns numbers of generic parameters excluding those from parent.
139    pub(crate) fn len_self(&self) -> usize {
140        self.params.len()
141    }
142
143    pub(crate) fn len_lifetimes_self(&self) -> usize {
144        self.params.len_lifetimes()
145    }
146
147    /// (parent total, self param, type params, const params, impl trait list, lifetimes)
148    pub(crate) fn provenance_split(&self) -> (usize, bool, usize, usize, usize, usize) {
149        let mut self_param = false;
150        let mut type_params = 0;
151        let mut impl_trait_params = 0;
152        let mut const_params = 0;
153        self.params.iter_type_or_consts().for_each(|(_, data)| match data {
154            TypeOrConstParamData::TypeParamData(p) => match p.provenance {
155                TypeParamProvenance::TypeParamList => type_params += 1,
156                TypeParamProvenance::TraitSelf => self_param |= true,
157                TypeParamProvenance::ArgumentImplTrait => impl_trait_params += 1,
158            },
159            TypeOrConstParamData::ConstParamData(_) => const_params += 1,
160        });
161
162        let lifetime_params = self.params.len_lifetimes();
163
164        let parent_len = self.parent_generics().map_or(0, Generics::len);
165        (parent_len, self_param, type_params, const_params, impl_trait_params, lifetime_params)
166    }
167
168    pub(crate) fn type_or_const_param(
169        &self,
170        param: TypeOrConstParamId,
171    ) -> Option<(usize, TypeOrConstParamData)> {
172        let idx = self.find_type_or_const_param(param)?;
173        self.iter().nth(idx).and_then(|p| {
174            let data = match p.1 {
175                GenericParamDataRef::TypeParamData(p) => p.clone().into(),
176                GenericParamDataRef::ConstParamData(p) => p.clone().into(),
177                _ => return None,
178            };
179            Some((idx, data))
180        })
181    }
182
183    pub fn type_or_const_param_idx(&self, param: TypeOrConstParamId) -> Option<usize> {
184        self.find_type_or_const_param(param)
185    }
186
187    fn find_type_or_const_param(&self, param: TypeOrConstParamId) -> Option<usize> {
188        if param.parent == self.def {
189            let idx = param.local_id.into_raw().into_u32() as usize;
190            debug_assert!(
191                idx <= self.params.len_type_or_consts(),
192                "idx: {} len: {}",
193                idx,
194                self.params.len_type_or_consts()
195            );
196            if self.params.trait_self_param() == Some(param.local_id) {
197                return Some(idx);
198            }
199            Some(self.parent_generics().map_or(0, |g| g.len()) + self.params.len_lifetimes() + idx)
200        } else {
201            debug_assert_eq!(self.parent_generics().map(|it| it.def), Some(param.parent));
202            self.parent_generics().and_then(|g| g.find_type_or_const_param(param))
203        }
204    }
205
206    pub fn lifetime_idx(&self, lifetime: LifetimeParamId) -> Option<usize> {
207        self.find_lifetime(lifetime)
208    }
209
210    fn find_lifetime(&self, lifetime: LifetimeParamId) -> Option<usize> {
211        if lifetime.parent == self.def {
212            let idx = lifetime.local_id.into_raw().into_u32() as usize;
213            debug_assert!(idx <= self.params.len_lifetimes());
214            Some(
215                self.parent_generics().map_or(0, |g| g.len())
216                    + self.params.trait_self_param().is_some() as usize
217                    + idx,
218            )
219        } else {
220            debug_assert_eq!(self.parent_generics().map(|it| it.def), Some(lifetime.parent));
221            self.parent_generics().and_then(|g| g.find_lifetime(lifetime))
222        }
223    }
224
225    pub(crate) fn parent_generics(&self) -> Option<&Generics> {
226        self.parent_generics.as_deref()
227    }
228
229    pub(crate) fn parent_or_self(&self) -> &Generics {
230        self.parent_generics.as_deref().unwrap_or(self)
231    }
232
233    /// Returns a Substitution that replaces each parameter by a bound variable.
234    pub(crate) fn bound_vars_subst(
235        &self,
236        db: &dyn HirDatabase,
237        debruijn: DebruijnIndex,
238    ) -> Substitution {
239        Substitution::from_iter(
240            Interner,
241            self.iter_id().enumerate().map(|(idx, id)| match id {
242                GenericParamId::ConstParamId(id) => BoundVar::new(debruijn, idx)
243                    .to_const(Interner, db.const_param_ty(id))
244                    .cast(Interner),
245                GenericParamId::TypeParamId(_) => {
246                    BoundVar::new(debruijn, idx).to_ty(Interner).cast(Interner)
247                }
248                GenericParamId::LifetimeParamId(_) => {
249                    BoundVar::new(debruijn, idx).to_lifetime(Interner).cast(Interner)
250                }
251            }),
252        )
253    }
254
255    /// Returns a Substitution that replaces each parameter by itself (i.e. `Ty::Param`).
256    pub fn placeholder_subst(&self, db: &dyn HirDatabase) -> Substitution {
257        Substitution::from_iter(
258            Interner,
259            self.iter_id().enumerate().map(|(index, id)| match id {
260                GenericParamId::TypeParamId(id) => {
261                    to_placeholder_idx(db, id.into(), index as u32).to_ty(Interner).cast(Interner)
262                }
263                GenericParamId::ConstParamId(id) => to_placeholder_idx(db, id.into(), index as u32)
264                    .to_const(Interner, db.const_param_ty(id))
265                    .cast(Interner),
266                GenericParamId::LifetimeParamId(id) => {
267                    lt_to_placeholder_idx(db, id, index as u32).to_lifetime(Interner).cast(Interner)
268                }
269            }),
270        )
271    }
272}
273
274pub(crate) fn trait_self_param_idx(db: &dyn DefDatabase, def: GenericDefId) -> Option<usize> {
275    match def {
276        GenericDefId::TraitId(_) => {
277            let params = db.generic_params(def);
278            params.trait_self_param().map(|idx| idx.into_raw().into_u32() as usize)
279        }
280        GenericDefId::ImplId(_) => None,
281        _ => {
282            let parent_def = parent_generic_def(db, def)?;
283            let parent_params = db.generic_params(parent_def);
284            let parent_self_idx = parent_params.trait_self_param()?.into_raw().into_u32() as usize;
285            Some(parent_self_idx)
286        }
287    }
288}
289
290pub(crate) fn parent_generic_def(db: &dyn DefDatabase, def: GenericDefId) -> Option<GenericDefId> {
291    let container = match def {
292        GenericDefId::FunctionId(it) => it.lookup(db).container,
293        GenericDefId::TypeAliasId(it) => it.lookup(db).container,
294        GenericDefId::ConstId(it) => it.lookup(db).container,
295        GenericDefId::StaticId(_)
296        | GenericDefId::AdtId(_)
297        | GenericDefId::TraitId(_)
298        | GenericDefId::ImplId(_) => return None,
299    };
300
301    match container {
302        ItemContainerId::ImplId(it) => Some(it.into()),
303        ItemContainerId::TraitId(it) => Some(it.into()),
304        ItemContainerId::ModuleId(_) | ItemContainerId::ExternBlockId(_) => None,
305    }
306}
307
308fn from_toc_id<'a>(
309    it: &'a Generics,
310) -> impl Fn(
311    (LocalTypeOrConstParamId, &'a TypeOrConstParamData),
312) -> (GenericParamId, GenericParamDataRef<'a>) {
313    move |(local_id, p): (_, _)| {
314        let id = TypeOrConstParamId { parent: it.def, local_id };
315        match p {
316            TypeOrConstParamData::TypeParamData(p) => (
317                GenericParamId::TypeParamId(TypeParamId::from_unchecked(id)),
318                GenericParamDataRef::TypeParamData(p),
319            ),
320            TypeOrConstParamData::ConstParamData(p) => (
321                GenericParamId::ConstParamId(ConstParamId::from_unchecked(id)),
322                GenericParamDataRef::ConstParamData(p),
323            ),
324        }
325    }
326}
327
328fn from_lt_id<'a>(
329    it: &'a Generics,
330) -> impl Fn((LocalLifetimeParamId, &'a LifetimeParamData)) -> (GenericParamId, GenericParamDataRef<'a>)
331{
332    move |(local_id, p): (_, _)| {
333        (
334            GenericParamId::LifetimeParamId(LifetimeParamId { parent: it.def, local_id }),
335            GenericParamDataRef::LifetimeParamData(p),
336        )
337    }
338}
hir_ty/generics.rs

hir_ty/
generics.rs
