src/tools/rust-analyzer/crates/hir-ty/src/traits.rs

   1 //! Trait solving using Chalk.
   2
   3 use std::{env::var, sync::Arc};
   4
   5 use chalk_ir::GoalData;
   6 use chalk_recursive::Cache;
   7 use chalk_solve::{logging_db::LoggingRustIrDatabase, Solver};
   8
   9 use base_db::CrateId;
  10 use hir_def::{lang_item::LangItemTarget, TraitId};
  11 use stdx::panic_context;
  12 use syntax::SmolStr;
  13
  14 use crate::{
  15     db::HirDatabase, infer::unify::InferenceTable, AliasEq, AliasTy, Canonical, DomainGoal, Goal,
  16     Guidance, InEnvironment, Interner, ProjectionTy, ProjectionTyExt, Solution, TraitRefExt, Ty,
  17     TyKind, WhereClause,
  18 };
  19
  20 /// This controls how much 'time' we give the Chalk solver before giving up.
  21 const CHALK_SOLVER_FUEL: i32 = 1000;
  22
  23 #[derive(Debug, Copy, Clone)]
  24 pub(crate) struct ChalkContext<'a> {
  25     pub(crate) db: &'a dyn HirDatabase,
  26     pub(crate) krate: CrateId,
  27 }
  28
  29 fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> {
  30     let overflow_depth =
  31         var("CHALK_OVERFLOW_DEPTH").ok().and_then(|s| s.parse().ok()).unwrap_or(500);
  32     let max_size = var("CHALK_SOLVER_MAX_SIZE").ok().and_then(|s| s.parse().ok()).unwrap_or(150);
  33     chalk_recursive::RecursiveSolver::new(overflow_depth, max_size, Some(Cache::new()))
  34 }
  35
  36 /// A set of clauses that we assume to be true. E.g. if we are inside this function:
  37 /// ```rust
  38 /// fn foo<T: Default>(t: T) {}
  39 /// ```
  40 /// we assume that `T: Default`.
  41 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  42 pub struct TraitEnvironment {
  43     pub krate: CrateId,
  44     // FIXME make this a BTreeMap
  45     pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>,
  46     pub env: chalk_ir::Environment<Interner>,
  47 }
  48
  49 impl TraitEnvironment {
  50     pub fn empty(krate: CrateId) -> Self {
  51         TraitEnvironment {
  52             krate,
  53             traits_from_clauses: Vec::new(),
  54             env: chalk_ir::Environment::new(Interner),
  55         }
  56     }
  57
  58     pub fn traits_in_scope_from_clauses(&self, ty: Ty) -> impl Iterator<Item = TraitId> + '_ {
  59         self.traits_from_clauses
  60             .iter()
  61             .filter_map(move |(self_ty, trait_id)| (*self_ty == ty).then_some(*trait_id))
  62     }
  63 }
  64
  65 pub(crate) fn normalize_projection_query(
  66     db: &dyn HirDatabase,
  67     projection: ProjectionTy,
  68     env: Arc<TraitEnvironment>,
  69 ) -> Ty {
  70     let mut table = InferenceTable::new(db, env);
  71     let ty = table.normalize_projection_ty(projection);
  72     table.resolve_completely(ty)
  73 }
  74
  75 /// Solve a trait goal using Chalk.
  76 pub(crate) fn trait_solve_query(
  77     db: &dyn HirDatabase,
  78     krate: CrateId,
  79     goal: Canonical<InEnvironment<Goal>>,
  80 ) -> Option<Solution> {
  81     let _p = profile::span("trait_solve_query").detail(|| match &goal.value.goal.data(Interner) {
  82         GoalData::DomainGoal(DomainGoal::Holds(WhereClause::Implemented(it))) => {
  83             db.trait_data(it.hir_trait_id()).name.to_string()
  84         }
  85         GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(_))) => "alias_eq".to_string(),
  86         _ => "??".to_string(),
  87     });
  88     tracing::info!("trait_solve_query({:?})", goal.value.goal);
  89
  90     if let GoalData::DomainGoal(DomainGoal::Holds(WhereClause::AliasEq(AliasEq {
  91         alias: AliasTy::Projection(projection_ty),
  92         ..
  93     }))) = &goal.value.goal.data(Interner)
  94     {
  95         if let TyKind::BoundVar(_) = projection_ty.self_type_parameter(db).kind(Interner) {
  96             // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible
  97             return Some(Solution::Ambig(Guidance::Unknown));
  98         }
  99     }
 100
 101     // We currently don't deal with universes (I think / hope they're not yet
 102     // relevant for our use cases?)
 103     let u_canonical = chalk_ir::UCanonical { canonical: goal, universes: 1 };
 104     solve(db, krate, &u_canonical)
 105 }
 106
 107 fn solve(
 108     db: &dyn HirDatabase,
 109     krate: CrateId,
 110     goal: &chalk_ir::UCanonical<chalk_ir::InEnvironment<chalk_ir::Goal<Interner>>>,
 111 ) -> Option<chalk_solve::Solution<Interner>> {
 112     let context = ChalkContext { db, krate };
 113     tracing::debug!("solve goal: {:?}", goal);
 114     let mut solver = create_chalk_solver();
 115
 116     let fuel = std::cell::Cell::new(CHALK_SOLVER_FUEL);
 117
 118     let should_continue = || {
 119         db.unwind_if_cancelled();
 120         let remaining = fuel.get();
 121         fuel.set(remaining - 1);
 122         if remaining == 0 {
 123             tracing::debug!("fuel exhausted");
 124         }
 125         remaining > 0
 126     };
 127
 128     let mut solve = || {
 129         let _ctx = if is_chalk_debug() || is_chalk_print() {
 130             Some(panic_context::enter(format!("solving {goal:?}")))
 131         } else {
 132             None
 133         };
 134         let solution = if is_chalk_print() {
 135             let logging_db =
 136                 LoggingRustIrDatabaseLoggingOnDrop(LoggingRustIrDatabase::new(context));
 137             solver.solve_limited(&logging_db.0, goal, &should_continue)
 138         } else {
 139             solver.solve_limited(&context, goal, &should_continue)
 140         };
 141
 142         tracing::debug!("solve({:?}) => {:?}", goal, solution);
 143
 144         solution
 145     };
 146
 147     // don't set the TLS for Chalk unless Chalk debugging is active, to make
 148     // extra sure we only use it for debugging
 149     if is_chalk_debug() {
 150         crate::tls::set_current_program(db, solve)
 151     } else {
 152         solve()
 153     }
 154 }
 155
 156 struct LoggingRustIrDatabaseLoggingOnDrop<'a>(LoggingRustIrDatabase<Interner, ChalkContext<'a>>);
 157
 158 impl<'a> Drop for LoggingRustIrDatabaseLoggingOnDrop<'a> {
 159     fn drop(&mut self) {
 160         eprintln!("chalk program:\n{}", self.0);
 161     }
 162 }
 163
 164 fn is_chalk_debug() -> bool {
 165     std::env::var("CHALK_DEBUG").is_ok()
 166 }
 167
 168 fn is_chalk_print() -> bool {
 169     std::env::var("CHALK_PRINT").is_ok()
 170 }
 171
 172 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
 173 pub enum FnTrait {
 174     FnOnce,
 175     FnMut,
 176     Fn,
 177 }
 178
 179 impl FnTrait {
 180     const fn lang_item_name(self) -> &'static str {
 181         match self {
 182             FnTrait::FnOnce => "fn_once",
 183             FnTrait::FnMut => "fn_mut",
 184             FnTrait::Fn => "fn",
 185         }
 186     }
 187
 188     pub fn get_id(&self, db: &dyn HirDatabase, krate: CrateId) -> Option<TraitId> {
 189         let target = db.lang_item(krate, SmolStr::new_inline(self.lang_item_name()))?;
 190         match target {
 191             LangItemTarget::TraitId(t) => Some(t),
 192             _ => None,
 193         }
 194     }
 195 }