3 // Terms are structured as a straightforward tree. Rather than rely on
4 // GC, we allocate terms out of a bounded arena (the lifetime of this
5 // arena is the lifetime 'a that is threaded around).
7 // We assign a unique index to each type/region parameter whose variance
8 // is to be inferred. We refer to such variables as "inferreds". An
9 // `InferredIndex` is a newtype'd int representing the index of such
12 use arena
::TypedArena
;
14 use rustc_hir
::itemlikevisit
::ItemLikeVisitor
;
15 use rustc_hir
::HirIdMap
;
16 use rustc_middle
::ty
::{self, TyCtxt}
;
19 use self::VarianceTerm
::*;
21 pub type VarianceTermPtr
<'a
> = &'a VarianceTerm
<'a
>;
23 #[derive(Copy, Clone, Debug)]
24 pub struct InferredIndex(pub usize);
26 #[derive(Copy, Clone)]
27 pub enum VarianceTerm
<'a
> {
28 ConstantTerm(ty
::Variance
),
29 TransformTerm(VarianceTermPtr
<'a
>, VarianceTermPtr
<'a
>),
30 InferredTerm(InferredIndex
),
33 impl<'a
> fmt
::Debug
for VarianceTerm
<'a
> {
34 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
36 ConstantTerm(c1
) => write
!(f
, "{:?}", c1
),
37 TransformTerm(v1
, v2
) => write
!(f
, "({:?} \u{00D7} {:?})", v1
, v2
),
38 InferredTerm(id
) => write
!(f
, "[{}]", {
39 let InferredIndex(i
) = id
;
46 // The first pass over the crate simply builds up the set of inferreds.
48 pub struct TermsContext
<'a
, 'tcx
> {
49 pub tcx
: TyCtxt
<'tcx
>,
50 pub arena
: &'a TypedArena
<VarianceTerm
<'a
>>,
52 // For marker types, UnsafeCell, and other lang items where
53 // variance is hardcoded, records the item-id and the hardcoded
55 pub lang_items
: Vec
<(hir
::HirId
, Vec
<ty
::Variance
>)>,
57 // Maps from the node id of an item to the first inferred index
58 // used for its type & region parameters.
59 pub inferred_starts
: HirIdMap
<InferredIndex
>,
61 // Maps from an InferredIndex to the term for that variable.
62 pub inferred_terms
: Vec
<VarianceTermPtr
<'a
>>,
65 pub fn determine_parameters_to_be_inferred
<'a
, 'tcx
>(
67 arena
: &'a
mut TypedArena
<VarianceTerm
<'a
>>,
68 ) -> TermsContext
<'a
, 'tcx
> {
69 let mut terms_cx
= TermsContext
{
72 inferred_starts
: Default
::default(),
73 inferred_terms
: vec
![],
75 lang_items
: lang_items(tcx
),
78 // See the following for a discussion on dep-graph management.
80 // - https://rustc-dev-guide.rust-lang.org/query.html
81 // - https://rustc-dev-guide.rust-lang.org/variance.html
82 tcx
.hir().krate().visit_all_item_likes(&mut terms_cx
);
87 fn lang_items(tcx
: TyCtxt
<'_
>) -> Vec
<(hir
::HirId
, Vec
<ty
::Variance
>)> {
88 let lang_items
= tcx
.lang_items();
90 (lang_items
.phantom_data(), vec
![ty
::Covariant
]),
91 (lang_items
.unsafe_cell_type(), vec
![ty
::Invariant
]),
94 all
.into_iter() // iterating over (Option<DefId>, Variance)
95 .filter(|&(ref d
, _
)| d
.is_some())
96 .map(|(d
, v
)| (d
.unwrap(), v
)) // (DefId, Variance)
97 .filter_map(|(d
, v
)| tcx
.hir().as_local_hir_id(d
).map(|n
| (n
, v
))) // (HirId, Variance)
101 impl<'a
, 'tcx
> TermsContext
<'a
, 'tcx
> {
102 fn add_inferreds_for_item(&mut self, id
: hir
::HirId
) {
104 let def_id
= tcx
.hir().local_def_id(id
);
105 let count
= tcx
.generics_of(def_id
).count();
111 // Record the start of this item's inferreds.
112 let start
= self.inferred_terms
.len();
113 let newly_added
= self.inferred_starts
.insert(id
, InferredIndex(start
)).is_none();
114 assert
!(newly_added
);
116 // N.B., in the code below for writing the results back into the
117 // `CrateVariancesMap`, we rely on the fact that all inferreds
118 // for a particular item are assigned continuous indices.
120 let arena
= self.arena
;
121 self.inferred_terms
.extend(
122 (start
..(start
+ count
)).map(|i
| &*arena
.alloc(InferredTerm(InferredIndex(i
)))),
127 impl<'a
, 'tcx
, 'v
> ItemLikeVisitor
<'v
> for TermsContext
<'a
, 'tcx
> {
128 fn visit_item(&mut self, item
: &hir
::Item
<'_
>) {
129 debug
!("add_inferreds for item {}", self.tcx
.hir().node_to_string(item
.hir_id
));
132 hir
::ItemKind
::Struct(ref struct_def
, _
) | hir
::ItemKind
::Union(ref struct_def
, _
) => {
133 self.add_inferreds_for_item(item
.hir_id
);
135 if let hir
::VariantData
::Tuple(..) = *struct_def
{
136 self.add_inferreds_for_item(struct_def
.ctor_hir_id().unwrap());
140 hir
::ItemKind
::Enum(ref enum_def
, _
) => {
141 self.add_inferreds_for_item(item
.hir_id
);
143 for variant
in enum_def
.variants
{
144 if let hir
::VariantData
::Tuple(..) = variant
.data
{
145 self.add_inferreds_for_item(variant
.data
.ctor_hir_id().unwrap());
150 hir
::ItemKind
::Fn(..) => {
151 self.add_inferreds_for_item(item
.hir_id
);
154 hir
::ItemKind
::ForeignMod(ref foreign_mod
) => {
155 for foreign_item
in foreign_mod
.items
{
156 if let hir
::ForeignItemKind
::Fn(..) = foreign_item
.kind
{
157 self.add_inferreds_for_item(foreign_item
.hir_id
);
166 fn visit_trait_item(&mut self, trait_item
: &hir
::TraitItem
<'_
>) {
167 if let hir
::TraitItemKind
::Fn(..) = trait_item
.kind
{
168 self.add_inferreds_for_item(trait_item
.hir_id
);
172 fn visit_impl_item(&mut self, impl_item
: &hir
::ImplItem
<'_
>) {
173 if let hir
::ImplItemKind
::Fn(..) = impl_item
.kind
{
174 self.add_inferreds_for_item(impl_item
.hir_id
);