vendor/chalk-solve/src/logging_db/id_collector.rs

   1 use super::RecordedItemId;
   2 use crate::RustIrDatabase;
   3 use chalk_ir::{
   4     interner::Interner,
   5     visit::{ControlFlow, Visitor},
   6     visit::{SuperVisit, Visit},
   7     AliasTy, DebruijnIndex, TyKind, WhereClause,
   8 };
   9 use std::collections::BTreeSet;
  10
  11 /// Collects the identifiers needed to resolve all the names for a given
  12 /// set of identifers, excluding identifiers we already have.
  13 ///
  14 /// When recording identifiers to print, the `LoggingRustIrDatabase` only
  15 /// records identifiers the solver uses. But the solver assumes well-formedness,
  16 /// and thus skips over many names referenced in the definitions.
  17 ///
  18 /// For instance, if we have:
  19 ///
  20 /// ```rust,ignore
  21 /// struct S {}
  22 ///
  23 /// trait Parent {}
  24 /// trait Child where Self: Parent {}
  25 /// impl Parent for S {}
  26 /// impl Child for S {}
  27 /// ```
  28 ///
  29 /// And our goal is `S: Child`, we will only render `S`, `impl Child for S`, and
  30 /// `trait Child`. This will not parse because the `Child` trait's definition
  31 /// references parent. IdCollector solves this by collecting all of the directly
  32 /// related identifiers, allowing those to be rendered as well, ensuring name
  33 /// resolution is successful.
  34 pub fn collect_unrecorded_ids<'i, I: Interner, DB: RustIrDatabase<I>>(
  35     db: &'i DB,
  36     identifiers: &'_ BTreeSet<RecordedItemId<I>>,
  37 ) -> BTreeSet<RecordedItemId<I>> {
  38     let mut collector = IdCollector {
  39         db,
  40         found_identifiers: BTreeSet::new(),
  41     };
  42     for id in identifiers {
  43         match *id {
  44             RecordedItemId::Adt(adt_id) => {
  45                 collector
  46                     .db
  47                     .adt_datum(adt_id)
  48                     .visit_with(&mut collector, DebruijnIndex::INNERMOST);
  49             }
  50             RecordedItemId::FnDef(fn_def) => {
  51                 collector
  52                     .db
  53                     .fn_def_datum(fn_def)
  54                     .visit_with(&mut collector, DebruijnIndex::INNERMOST);
  55             }
  56             RecordedItemId::Generator(_generator_id) => unimplemented!(),
  57             RecordedItemId::Trait(trait_id) => {
  58                 let trait_datum = collector.db.trait_datum(trait_id);
  59
  60                 trait_datum.visit_with(&mut collector, DebruijnIndex::INNERMOST);
  61                 for assoc_ty_id in &trait_datum.associated_ty_ids {
  62                     let assoc_ty_datum = collector.db.associated_ty_data(*assoc_ty_id);
  63                     assoc_ty_datum
  64                         .bounds_on_self(collector.db.interner())
  65                         .visit_with(&mut collector, DebruijnIndex::INNERMOST);
  66                     assoc_ty_datum.visit_with(&mut collector, DebruijnIndex::INNERMOST);
  67                 }
  68             }
  69             RecordedItemId::OpaqueTy(opaque_id) => {
  70                 collector
  71                     .db
  72                     .opaque_ty_data(opaque_id)
  73                     .visit_with(&mut collector, DebruijnIndex::INNERMOST);
  74                 collector
  75                     .db
  76                     .hidden_opaque_type(opaque_id)
  77                     .visit_with(&mut collector, DebruijnIndex::INNERMOST);
  78             }
  79             RecordedItemId::Impl(impl_id) => {
  80                 let impl_datum = collector.db.impl_datum(impl_id);
  81                 for id in &impl_datum.associated_ty_value_ids {
  82                     let assoc_ty_value = collector.db.associated_ty_value(*id);
  83                     assoc_ty_value.visit_with(&mut collector, DebruijnIndex::INNERMOST);
  84                 }
  85                 impl_datum.visit_with(&mut collector, DebruijnIndex::INNERMOST);
  86             }
  87         }
  88     }
  89     collector
  90         .found_identifiers
  91         .difference(identifiers)
  92         .copied()
  93         .collect()
  94 }
  95
  96 struct IdCollector<'i, I: Interner, DB: RustIrDatabase<I>> {
  97     db: &'i DB,
  98     found_identifiers: BTreeSet<RecordedItemId<I>>,
  99 }
 100
 101 impl<'i, I: Interner, DB: RustIrDatabase<I>> IdCollector<'i, I, DB> {
 102     fn record(&mut self, id: impl Into<RecordedItemId<I>>) {
 103         self.found_identifiers.insert(id.into());
 104     }
 105 }
 106
 107 impl<'i, I: Interner, DB: RustIrDatabase<I>> Visitor<'i, I> for IdCollector<'i, I, DB>
 108 where
 109     I: 'i,
 110 {
 111     type BreakTy = ();
 112
 113     fn as_dyn(&mut self) -> &mut dyn Visitor<'i, I, BreakTy = Self::BreakTy> {
 114         self
 115     }
 116     fn interner(&self) -> &'i I {
 117         self.db.interner()
 118     }
 119
 120     fn visit_ty(
 121         &mut self,
 122         ty: &chalk_ir::Ty<I>,
 123         outer_binder: chalk_ir::DebruijnIndex,
 124     ) -> ControlFlow<()> {
 125         match ty.kind(self.db.interner()) {
 126             TyKind::Adt(adt, _) => self.record(*adt),
 127             TyKind::FnDef(fn_def, _) => self.record(*fn_def),
 128             TyKind::OpaqueType(opaque, _) => self.record(*opaque),
 129             TyKind::Alias(alias) => match alias {
 130                 AliasTy::Projection(projection_ty) => {
 131                     let assoc_ty_datum = self.db.associated_ty_data(projection_ty.associated_ty_id);
 132                     self.record(assoc_ty_datum.trait_id)
 133                 }
 134                 AliasTy::Opaque(opaque_ty) => {
 135                     self.record(opaque_ty.opaque_ty_id);
 136                 }
 137             },
 138             TyKind::BoundVar(..) => (),
 139             TyKind::Dyn(..) => (),
 140             TyKind::Function(..) => (),
 141             TyKind::InferenceVar(..) => (),
 142             TyKind::Placeholder(..) => (),
 143             _ => {}
 144         }
 145         ty.super_visit_with(self, outer_binder)
 146     }
 147
 148     fn visit_where_clause(
 149         &mut self,
 150         where_clause: &WhereClause<I>,
 151         outer_binder: DebruijnIndex,
 152     ) -> ControlFlow<()> {
 153         match where_clause {
 154             WhereClause::Implemented(trait_ref) => self.record(trait_ref.trait_id),
 155             WhereClause::AliasEq(alias_eq) => match &alias_eq.alias {
 156                 AliasTy::Projection(projection_ty) => {
 157                     let assoc_ty_datum = self.db.associated_ty_data(projection_ty.associated_ty_id);
 158                     self.record(assoc_ty_datum.trait_id)
 159                 }
 160                 AliasTy::Opaque(opaque_ty) => {
 161                     self.record(opaque_ty.opaque_ty_id);
 162                 }
 163             },
 164             WhereClause::LifetimeOutlives(_lifetime_outlives) => (),
 165             WhereClause::TypeOutlives(_type_outlives) => (),
 166         }
 167         where_clause.super_visit_with(self.as_dyn(), outer_binder)
 168     }
 169 }