From 6a77ec7bbe6ddbf663dce9529d11d1bb56c5489a Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Thu, 13 Aug 2020 16:35:29 +0200 Subject: Rename ra_hir_ty -> hir_ty --- crates/ra_hir_ty/src/traits.rs | 272 ----------------------------------------- 1 file changed, 272 deletions(-) delete mode 100644 crates/ra_hir_ty/src/traits.rs (limited to 'crates/ra_hir_ty/src/traits.rs') diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs deleted file mode 100644 index 255323717..000000000 --- a/crates/ra_hir_ty/src/traits.rs +++ /dev/null @@ -1,272 +0,0 @@ -//! Trait solving using Chalk. -use std::sync::Arc; - -use base_db::CrateId; -use chalk_ir::cast::Cast; -use chalk_solve::Solver; -use hir_def::{lang_item::LangItemTarget, TraitId}; - -use crate::{db::HirDatabase, DebruijnIndex, Substs}; - -use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk}; - -use self::chalk::{from_chalk, Interner, ToChalk}; - -pub(crate) mod chalk; - -// This controls the maximum size of types Chalk considers. If we set this too -// high, we can run into slow edge cases; if we set it too low, Chalk won't -// find some solutions. -// FIXME this is currently hardcoded in the recursive solver -// const CHALK_SOLVER_MAX_SIZE: usize = 10; - -/// This controls how much 'time' we give the Chalk solver before giving up. -const CHALK_SOLVER_FUEL: i32 = 100; - -#[derive(Debug, Copy, Clone)] -struct ChalkContext<'a> { - db: &'a dyn HirDatabase, - krate: CrateId, -} - -fn create_chalk_solver() -> chalk_recursive::RecursiveSolver { - let overflow_depth = 100; - let caching_enabled = true; - chalk_recursive::RecursiveSolver::new(overflow_depth, caching_enabled) -} - -/// A set of clauses that we assume to be true. E.g. if we are inside this function: -/// ```rust -/// fn foo(t: T) {} -/// ``` -/// we assume that `T: Default`. -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub struct TraitEnvironment { - pub predicates: Vec, -} - -impl TraitEnvironment { - /// Returns trait refs with the given self type which are supposed to hold - /// in this trait env. E.g. if we are in `foo()`, this will - /// find that `T: SomeTrait` if we call it for `T`. - pub(crate) fn trait_predicates_for_self_ty<'a>( - &'a self, - ty: &'a Ty, - ) -> impl Iterator + 'a { - self.predicates.iter().filter_map(move |pred| match pred { - GenericPredicate::Implemented(tr) if tr.self_ty() == ty => Some(tr), - _ => None, - }) - } -} - -/// Something (usually a goal), along with an environment. -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub struct InEnvironment { - pub environment: Arc, - pub value: T, -} - -impl InEnvironment { - pub fn new(environment: Arc, value: T) -> InEnvironment { - InEnvironment { environment, value } - } -} - -/// Something that needs to be proven (by Chalk) during type checking, e.g. that -/// a certain type implements a certain trait. Proving the Obligation might -/// result in additional information about inference variables. -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub enum Obligation { - /// Prove that a certain type implements a trait (the type is the `Self` type - /// parameter to the `TraitRef`). - Trait(TraitRef), - Projection(ProjectionPredicate), -} - -impl Obligation { - pub fn from_predicate(predicate: GenericPredicate) -> Option { - match predicate { - GenericPredicate::Implemented(trait_ref) => Some(Obligation::Trait(trait_ref)), - GenericPredicate::Projection(projection_pred) => { - Some(Obligation::Projection(projection_pred)) - } - GenericPredicate::Error => None, - } - } -} - -#[derive(Clone, Debug, PartialEq, Eq, Hash)] -pub struct ProjectionPredicate { - pub projection_ty: ProjectionTy, - pub ty: Ty, -} - -impl TypeWalk for ProjectionPredicate { - fn walk(&self, f: &mut impl FnMut(&Ty)) { - self.projection_ty.walk(f); - self.ty.walk(f); - } - - fn walk_mut_binders( - &mut self, - f: &mut impl FnMut(&mut Ty, DebruijnIndex), - binders: DebruijnIndex, - ) { - self.projection_ty.walk_mut_binders(f, binders); - self.ty.walk_mut_binders(f, binders); - } -} - -/// Solve a trait goal using Chalk. -pub(crate) fn trait_solve_query( - db: &dyn HirDatabase, - krate: CrateId, - goal: Canonical>, -) -> Option { - let _p = profile::span("trait_solve_query").detail(|| match &goal.value.value { - Obligation::Trait(it) => db.trait_data(it.trait_).name.to_string(), - Obligation::Projection(_) => "projection".to_string(), - }); - log::info!("trait_solve_query({})", goal.value.value.display(db)); - - if let Obligation::Projection(pred) = &goal.value.value { - if let Ty::Bound(_) = &pred.projection_ty.parameters[0] { - // Hack: don't ask Chalk to normalize with an unknown self type, it'll say that's impossible - return Some(Solution::Ambig(Guidance::Unknown)); - } - } - - let canonical = goal.to_chalk(db).cast(&Interner); - - // We currently don't deal with universes (I think / hope they're not yet - // relevant for our use cases?) - let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 }; - let solution = solve(db, krate, &u_canonical); - solution.map(|solution| solution_from_chalk(db, solution)) -} - -fn solve( - db: &dyn HirDatabase, - krate: CrateId, - goal: &chalk_ir::UCanonical>>, -) -> Option> { - let context = ChalkContext { db, krate }; - log::debug!("solve goal: {:?}", goal); - let mut solver = create_chalk_solver(); - - let fuel = std::cell::Cell::new(CHALK_SOLVER_FUEL); - - let should_continue = || { - context.db.check_canceled(); - let remaining = fuel.get(); - fuel.set(remaining - 1); - if remaining == 0 { - log::debug!("fuel exhausted"); - } - remaining > 0 - }; - let mut solve = || { - let solution = solver.solve_limited(&context, goal, should_continue); - log::debug!("solve({:?}) => {:?}", goal, solution); - solution - }; - // don't set the TLS for Chalk unless Chalk debugging is active, to make - // extra sure we only use it for debugging - let solution = - if is_chalk_debug() { chalk::tls::set_current_program(db, solve) } else { solve() }; - - solution -} - -fn is_chalk_debug() -> bool { - std::env::var("CHALK_DEBUG").is_ok() -} - -fn solution_from_chalk( - db: &dyn HirDatabase, - solution: chalk_solve::Solution, -) -> Solution { - let convert_subst = |subst: chalk_ir::Canonical>| { - let result = from_chalk(db, subst); - SolutionVariables(result) - }; - match solution { - chalk_solve::Solution::Unique(constr_subst) => { - let subst = chalk_ir::Canonical { - value: constr_subst.value.subst, - binders: constr_subst.binders, - }; - Solution::Unique(convert_subst(subst)) - } - chalk_solve::Solution::Ambig(chalk_solve::Guidance::Definite(subst)) => { - Solution::Ambig(Guidance::Definite(convert_subst(subst))) - } - chalk_solve::Solution::Ambig(chalk_solve::Guidance::Suggested(subst)) => { - Solution::Ambig(Guidance::Suggested(convert_subst(subst))) - } - chalk_solve::Solution::Ambig(chalk_solve::Guidance::Unknown) => { - Solution::Ambig(Guidance::Unknown) - } - } -} - -#[derive(Clone, Debug, PartialEq, Eq)] -pub struct SolutionVariables(pub Canonical); - -#[derive(Clone, Debug, PartialEq, Eq)] -/// A (possible) solution for a proposed goal. -pub enum Solution { - /// The goal indeed holds, and there is a unique value for all existential - /// variables. - Unique(SolutionVariables), - - /// The goal may be provable in multiple ways, but regardless we may have some guidance - /// for type inference. In this case, we don't return any lifetime - /// constraints, since we have not "committed" to any particular solution - /// yet. - Ambig(Guidance), -} - -#[derive(Clone, Debug, PartialEq, Eq)] -/// When a goal holds ambiguously (e.g., because there are multiple possible -/// solutions), we issue a set of *guidance* back to type inference. -pub enum Guidance { - /// The existential variables *must* have the given values if the goal is - /// ever to hold, but that alone isn't enough to guarantee the goal will - /// actually hold. - Definite(SolutionVariables), - - /// There are multiple plausible values for the existentials, but the ones - /// here are suggested as the preferred choice heuristically. These should - /// be used for inference fallback only. - Suggested(SolutionVariables), - - /// There's no useful information to feed back to type inference - Unknown, -} - -#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] -pub enum FnTrait { - FnOnce, - FnMut, - Fn, -} - -impl FnTrait { - fn lang_item_name(self) -> &'static str { - match self { - FnTrait::FnOnce => "fn_once", - FnTrait::FnMut => "fn_mut", - FnTrait::Fn => "fn", - } - } - - pub fn get_id(&self, db: &dyn HirDatabase, krate: CrateId) -> Option { - let target = db.lang_item(krate, self.lang_item_name().into())?; - match target { - LangItemTarget::TraitId(t) => Some(t), - _ => None, - } - } -} -- cgit v1.2.3