crates/hir-ty/src/traits.rs

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