crates/hir_ty/src/traits.rs

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