1#![cfg_attr(feature = "in-rust-tree", feature(rustc_private))]
5#![allow(rustdoc::private_intra_doc_links)]
7
8extern crate ra_ap_rustc_index as rustc_index;
15
16extern crate ra_ap_rustc_abi as rustc_abi;
17
18extern crate ra_ap_rustc_pattern_analysis as rustc_pattern_analysis;
19
20extern crate ra_ap_rustc_ast_ir as rustc_ast_ir;
21
22extern crate ra_ap_rustc_type_ir as rustc_type_ir;
23
24extern crate ra_ap_rustc_next_trait_solver as rustc_next_trait_solver;
25
26extern crate self as hir_ty;
27
28pub mod builtin_derive;
29mod generics;
30mod infer;
31mod inhabitedness;
32mod lower;
33pub mod next_solver;
34mod opaques;
35mod representability;
36mod specialization;
37mod target_feature;
38mod utils;
39mod variance;
40
41pub mod autoderef;
42pub mod consteval;
43pub mod db;
44pub mod diagnostics;
45pub mod display;
46pub mod drop;
47pub mod dyn_compatibility;
48pub mod lang_items;
49pub mod layout;
50pub mod method_resolution;
51pub mod mir;
52pub mod primitive;
53pub mod solver_errors;
54pub mod traits;
55pub mod upvars;
56
57#[cfg(test)]
58mod test_db;
59#[cfg(test)]
60mod tests;
61
62use std::{hash::Hash, ops::ControlFlow};
63
64use base_db::SourceDatabase;
65use hir_def::{
66 CallableDefId, ConstId, DefWithBodyId, EnumVariantId, ExpressionStoreOwnerId, FunctionId,
67 GenericDefId, HasModule, LifetimeParamId, ModuleId, StaticId, TypeAliasId, TypeOrConstParamId,
68 TypeParamId,
69 expr_store::{Body, ExpressionStore},
70 hir::{BindingId, ExprId, ExprOrPatId, ExprOrPatIdPacked, PatId},
71 resolver::{HasResolver, Resolver, TypeNs},
72 type_ref::{Rawness, TypeRefId},
73};
74use hir_expand::name::Name;
75use indexmap::{IndexMap, map::Entry};
76use macros::GenericTypeVisitable;
77use mir::{MirEvalError, VTableMap};
78use rustc_abi::ExternAbi;
79use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet};
80use rustc_type_ir::{
81 BoundVarIndexKind, TypeSuperVisitable, TypeVisitableExt,
82 inherent::{IntoKind, Ty as _},
83};
84use salsa::Update;
85use stdx::impl_from;
86use syntax::ast::{ConstArg, make};
87use traits::FnTrait;
88
89use crate::{
90 db::{AnonConstId, HirDatabase},
91 display::HirDisplay,
92 lower::SupertraitsInfo,
93 next_solver::{
94 AliasTy, Binder, BoundConst, BoundRegion, BoundRegionKind, BoundTy, BoundTyKind, Canonical,
95 CanonicalVarKind, CanonicalVarKinds, ClauseKind, Const, ConstKind, DbInterner, GenericArgs,
96 PolyFnSig, Region, RegionKind, TraitRef, Ty, TyKind, TypingMode,
97 abi::Safety,
98 infer::{
99 DbInternerInferExt,
100 traits::{Obligation, ObligationCause},
101 },
102 obligation_ctxt::ObligationCtxt,
103 },
104};
105
106pub use autoderef::autoderef;
107pub use infer::{
108 Adjust, Adjustment, AutoBorrow, BindingMode, ByRef, ExplicitDropMethodUseKind,
109 InferenceDiagnostic, InferenceResult, InferenceTyDiagnosticSource, OverloadedDeref,
110 PointerCast, ReturnKind, cast::CastError, could_coerce, could_unify, could_unify_deeply,
111 infer_query_with_inspect,
112};
113pub use lower::{
114 FieldType, GenericDefaults, GenericDefaultsRef, GenericPredicates, ImplTraits,
115 LifetimeElisionKind, LifetimeLoweringMode, LoweringMode, TyDefId, TyLoweringContext,
116 TyLoweringInferVarsCtx, TyLoweringResult, ValueTyDefId, diagnostics::*,
117};
118pub use next_solver::interner::{attach_db, attach_db_allow_change, with_attached_db};
119pub use target_feature::TargetFeatures;
120pub use traits::{ParamEnvAndCrate, check_orphan_rules};
121pub use utils::{
122 TargetFeatureIsSafeInTarget, Unsafety, all_super_traits, direct_super_traits,
123 is_fn_unsafe_to_call, target_feature_is_safe_in_target,
124};
125
126pub mod closure_analysis {
127 pub use crate::infer::{
128 CaptureInfo, CaptureSourceStack, CapturedPlace, ClosureData, UpvarCapture,
129 closure::analysis::{
130 BorrowKind,
131 expr_use_visitor::{FakeReadCause, Place, PlaceBase, Projection, ProjectionKind},
132 },
133 };
134}
135
136#[derive(Debug, Default, Clone, PartialEq, Eq, GenericTypeVisitable)]
140pub enum MemoryMap<'db> {
141 #[default]
142 Empty,
143 Simple(Box<[u8]>),
144 Complex(Box<ComplexMemoryMap<'db>>),
145}
146
147#[derive(Debug, Default, Clone, PartialEq, Eq, GenericTypeVisitable)]
148pub struct ComplexMemoryMap<'db> {
149 memory: IndexMap<usize, Box<[u8]>, FxBuildHasher>,
150 vtable: VTableMap<'db>,
151}
152
153impl ComplexMemoryMap<'_> {
154 fn insert(&mut self, addr: usize, val: Box<[u8]>) {
155 match self.memory.entry(addr) {
156 Entry::Occupied(mut e) => {
157 if e.get().len() < val.len() {
158 e.insert(val);
159 }
160 }
161 Entry::Vacant(e) => {
162 e.insert(val);
163 }
164 }
165 }
166}
167
168impl<'db> MemoryMap<'db> {
169 pub fn vtable_ty(&self, id: usize) -> Result<Ty<'db>, MirEvalError<'db>> {
170 match self {
171 MemoryMap::Empty | MemoryMap::Simple(_) => Err(MirEvalError::InvalidVTableId(id)),
172 MemoryMap::Complex(cm) => cm.vtable.ty(id),
173 }
174 }
175
176 fn simple(v: Box<[u8]>) -> Self {
177 MemoryMap::Simple(v)
178 }
179
180 fn transform_addresses(
184 &self,
185 mut f: impl FnMut(&[u8], usize) -> Result<usize, MirEvalError<'db>>,
186 ) -> Result<FxHashMap<usize, usize>, MirEvalError<'db>> {
187 let mut transform = |(addr, val): (&usize, &[u8])| {
188 let addr = *addr;
189 let align = if addr == 0 { 64 } else { (addr - (addr & (addr - 1))).min(64) };
190 f(val, align).map(|it| (addr, it))
191 };
192 match self {
193 MemoryMap::Empty => Ok(Default::default()),
194 MemoryMap::Simple(m) => transform((&0, m)).map(|(addr, val)| {
195 let mut map = FxHashMap::with_capacity_and_hasher(1, rustc_hash::FxBuildHasher);
196 map.insert(addr, val);
197 map
198 }),
199 MemoryMap::Complex(cm) => {
200 cm.memory.iter().map(|(addr, val)| transform((addr, val))).collect()
201 }
202 }
203 }
204
205 fn get(&self, addr: usize, size: usize) -> Option<&[u8]> {
206 if size == 0 {
207 Some(&[])
208 } else {
209 match self {
210 MemoryMap::Empty => Some(&[]),
211 MemoryMap::Simple(m) if addr == 0 => m.get(0..size),
212 MemoryMap::Simple(_) => None,
213 MemoryMap::Complex(cm) => cm.memory.get(&addr)?.get(0..size),
214 }
215 }
216 }
217}
218
219pub fn type_or_const_param_idx(db: &dyn HirDatabase, id: TypeOrConstParamId) -> u32 {
221 generics::generics(db, id.parent).type_or_const_param_idx(id)
222}
223
224pub fn lifetime_param_idx(db: &dyn HirDatabase, id: LifetimeParamId) -> u32 {
225 generics::generics(db, id.parent).lifetime_param_idx(id, false).0
226}
227
228#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
229pub enum ImplTraitId {
230 ReturnTypeImplTrait(hir_def::FunctionId, next_solver::ImplTraitIdx),
231 TypeAliasImplTrait(hir_def::TypeAliasId, next_solver::ImplTraitIdx),
232}
233
234pub fn replace_errors_with_variables<'db, T>(interner: DbInterner<'db>, t: &T) -> Canonical<'db, T>
238where
239 T: rustc_type_ir::TypeFoldable<DbInterner<'db>> + Clone,
240{
241 use rustc_type_ir::{FallibleTypeFolder, TypeSuperFoldable};
242 struct ErrorReplacer<'db> {
243 interner: DbInterner<'db>,
244 vars: Vec<CanonicalVarKind<'db>>,
245 binder: rustc_type_ir::DebruijnIndex,
246 }
247 impl<'db> FallibleTypeFolder<DbInterner<'db>> for ErrorReplacer<'db> {
248 #[cfg(debug_assertions)]
249 type Error = ();
250 #[cfg(not(debug_assertions))]
251 type Error = std::convert::Infallible;
252
253 fn cx(&self) -> DbInterner<'db> {
254 self.interner
255 }
256
257 fn try_fold_binder<T>(&mut self, t: Binder<'db, T>) -> Result<Binder<'db, T>, Self::Error>
258 where
259 T: rustc_type_ir::TypeFoldable<DbInterner<'db>>,
260 {
261 self.binder.shift_in(1);
262 let result = t.try_super_fold_with(self);
263 self.binder.shift_out(1);
264 result
265 }
266
267 fn try_fold_ty(&mut self, t: Ty<'db>) -> Result<Ty<'db>, Self::Error> {
268 if !t.has_type_flags(
269 rustc_type_ir::TypeFlags::HAS_ERROR
270 | rustc_type_ir::TypeFlags::HAS_TY_INFER
271 | rustc_type_ir::TypeFlags::HAS_CT_INFER
272 | rustc_type_ir::TypeFlags::HAS_RE_INFER,
273 ) {
274 return Ok(t);
275 }
276
277 #[cfg(debug_assertions)]
278 let error = || Err(());
279 #[cfg(not(debug_assertions))]
280 let error = || Ok(Ty::new_error(self.interner, crate::next_solver::ErrorGuaranteed));
281
282 match t.kind() {
283 TyKind::Error(_) => {
284 let var = rustc_type_ir::BoundVar::from_usize(self.vars.len());
285 self.vars.push(CanonicalVarKind::Ty {
286 ui: rustc_type_ir::UniverseIndex::ZERO,
287 sub_root: var,
288 });
289 Ok(Ty::new_bound(
290 self.interner,
291 self.binder,
292 BoundTy { var, kind: BoundTyKind::Anon },
293 ))
294 }
295 TyKind::Infer(_) => error(),
296 TyKind::Bound(BoundVarIndexKind::Bound(index), _) if index > self.binder => error(),
297 _ => t.try_super_fold_with(self),
298 }
299 }
300
301 fn try_fold_const(&mut self, ct: Const<'db>) -> Result<Const<'db>, Self::Error> {
302 if !ct.has_type_flags(
303 rustc_type_ir::TypeFlags::HAS_ERROR
304 | rustc_type_ir::TypeFlags::HAS_TY_INFER
305 | rustc_type_ir::TypeFlags::HAS_CT_INFER
306 | rustc_type_ir::TypeFlags::HAS_RE_INFER,
307 ) {
308 return Ok(ct);
309 }
310
311 #[cfg(debug_assertions)]
312 let error = || Err(());
313 #[cfg(not(debug_assertions))]
314 let error = || Ok(Const::error(self.interner));
315
316 match ct.kind() {
317 ConstKind::Error(_) => {
318 let var = rustc_type_ir::BoundVar::from_usize(self.vars.len());
319 self.vars.push(CanonicalVarKind::Const(rustc_type_ir::UniverseIndex::ZERO));
320 Ok(Const::new_bound(self.interner, self.binder, BoundConst::new(var)))
321 }
322 ConstKind::Infer(_) => error(),
323 ConstKind::Bound(BoundVarIndexKind::Bound(index), _) if index > self.binder => {
324 error()
325 }
326 _ => ct.try_super_fold_with(self),
327 }
328 }
329
330 fn try_fold_region(&mut self, region: Region<'db>) -> Result<Region<'db>, Self::Error> {
331 #[cfg(debug_assertions)]
332 let error = || Err(());
333 #[cfg(not(debug_assertions))]
334 let error = || Ok(Region::error(self.interner));
335
336 match region.kind() {
337 RegionKind::ReError(_) => {
338 let var = rustc_type_ir::BoundVar::from_usize(self.vars.len());
339 self.vars.push(CanonicalVarKind::Region(rustc_type_ir::UniverseIndex::ZERO));
340 Ok(Region::new_bound(
341 self.interner,
342 self.binder,
343 BoundRegion { var, kind: BoundRegionKind::Anon },
344 ))
345 }
346 RegionKind::ReVar(_) => error(),
347 RegionKind::ReBound(BoundVarIndexKind::Bound(index), _) if index > self.binder => {
348 error()
349 }
350 _ => Ok(region),
351 }
352 }
353 }
354
355 let mut error_replacer =
356 ErrorReplacer { vars: Vec::new(), binder: rustc_type_ir::DebruijnIndex::ZERO, interner };
357 let value = match t.clone().try_fold_with(&mut error_replacer) {
358 Ok(t) => t,
359 Err(_) => panic!("Encountered unbound or inference vars in {t:?}"),
360 };
361 Canonical {
362 value,
363 max_universe: rustc_type_ir::UniverseIndex::ZERO,
364 var_kinds: CanonicalVarKinds::new_from_slice(&error_replacer.vars),
365 }
366}
367
368pub fn associated_type_shorthand_candidates(
370 db: &dyn HirDatabase,
371 def: GenericDefId,
372 res: TypeNs,
373 mut cb: impl FnMut(&Name, TypeAliasId) -> bool,
374) -> Option<TypeAliasId> {
375 let interner = DbInterner::new_no_crate(db);
376 let (def, param) = match res {
377 TypeNs::GenericParam(param) => (def, param),
378 TypeNs::SelfType(impl_) => {
379 let impl_trait = db.impl_trait(impl_)?.skip_binder().def_id.0;
380 let param = TypeParamId::trait_self(impl_trait);
381 (impl_trait.into(), param)
382 }
383 _ => return None,
384 };
385
386 let mut dedup_map = FxHashSet::default();
387 let param_ty = Ty::new_param(interner, param, type_or_const_param_idx(db, param.into()));
388 let param_env = db.trait_environment(def);
390 for clause in param_env.clauses {
391 let ClauseKind::Trait(trait_clause) = clause.kind().skip_binder() else { continue };
392 if trait_clause.self_ty() != param_ty {
393 continue;
394 }
395 let trait_id = trait_clause.def_id().0;
396 dedup_map.extend(
397 SupertraitsInfo::query(db, trait_id)
398 .defined_assoc_types
399 .iter()
400 .map(|(name, id)| (name, *id)),
401 );
402 }
403
404 dedup_map
405 .into_iter()
406 .try_for_each(
407 |(name, id)| {
408 if cb(name, id) { ControlFlow::Break(id) } else { ControlFlow::Continue(()) }
409 },
410 )
411 .break_value()
412}
413
414pub fn callable_sig_from_fn_trait<'db>(
416 self_ty: Ty<'db>,
417 param_env: ParamEnvAndCrate<'db>,
418 db: &'db dyn HirDatabase,
419) -> Option<(FnTrait, PolyFnSig<'db>)> {
420 let ParamEnvAndCrate { param_env, krate } = param_env;
421 let interner = DbInterner::new_with(db, krate);
422 let infcx = interner.infer_ctxt().build(TypingMode::PostAnalysis);
423 let lang_items = interner.lang_items();
424 let cause = ObligationCause::dummy();
425
426 let impls_trait = |trait_: FnTrait| {
427 let mut ocx = ObligationCtxt::new(&infcx);
428 let tupled_args = infcx.next_ty_var(Span::Dummy);
429 let args = GenericArgs::new_from_slice(&[self_ty.into(), tupled_args.into()]);
430 let trait_id = trait_.get_id(lang_items)?;
431 let trait_ref = TraitRef::new_from_args(interner, trait_id.into(), args);
432 let obligation = Obligation::new(interner, cause, param_env, trait_ref);
433 ocx.register_obligation(obligation);
434 if !ocx.try_evaluate_obligations().is_empty() {
435 return None;
436 }
437 let tupled_args =
438 infcx.resolve_vars_if_possible(tupled_args).replace_infer_with_error(interner);
439 if tupled_args.is_tuple() { Some(tupled_args) } else { None }
440 };
441
442 let (trait_, args) = 'find_trait: {
443 for trait_ in [FnTrait::Fn, FnTrait::FnMut, FnTrait::FnOnce] {
444 if let Some(args) = impls_trait(trait_) {
445 break 'find_trait (trait_, args);
446 }
447 }
448 return None;
449 };
450
451 let output_assoc_type = lang_items.FnOnceOutput?;
452 let output_projection = Ty::new_alias(
453 interner,
454 AliasTy::new(
455 interner,
456 rustc_type_ir::Projection { def_id: output_assoc_type.into() },
457 [self_ty, args],
458 ),
459 );
460 let mut ocx = ObligationCtxt::new(&infcx);
461 let ret = ocx.structurally_normalize_ty(&cause, param_env, output_projection).ok()?;
462 let ret = ret.replace_infer_with_error(interner);
463
464 let sig = Binder::dummy(interner.mk_fn_sig(
465 args.tuple_fields(),
466 ret,
467 false,
468 Safety::Safe,
470 ExternAbi::Rust,
471 ));
472 Some((trait_, sig))
473}
474
475struct ParamCollector {
476 params: FxHashSet<TypeOrConstParamId>,
477}
478
479impl<'db> rustc_type_ir::TypeVisitor<DbInterner<'db>> for ParamCollector {
480 type Result = ();
481
482 fn visit_ty(&mut self, ty: Ty<'db>) -> Self::Result {
483 if let TyKind::Param(param) = ty.kind() {
484 self.params.insert(param.id.into());
485 }
486
487 ty.super_visit_with(self);
488 }
489
490 fn visit_const(&mut self, konst: Const<'db>) -> Self::Result {
491 if let ConstKind::Param(param) = konst.kind() {
492 self.params.insert(param.id.into());
493 }
494
495 konst.super_visit_with(self);
496 }
497}
498
499pub fn collect_params<'db, T>(value: &T) -> Vec<TypeOrConstParamId>
501where
502 T: ?Sized + rustc_type_ir::TypeVisitable<DbInterner<'db>>,
503{
504 let mut collector = ParamCollector { params: FxHashSet::default() };
505 value.visit_with(&mut collector);
506 Vec::from_iter(collector.params)
507}
508
509pub fn known_const_to_ast<'db>(
510 konst: Const<'db>,
511 db: &'db dyn HirDatabase,
512 target_module: ModuleId,
513) -> Option<ConstArg> {
514 Some(make::expr_const_value(
515 &konst.display_source_code(db, target_module, true).unwrap_or_else(|_| "_".to_owned()),
516 ))
517}
518
519#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
525pub enum Span {
526 ExprId(ExprId),
527 PatId(PatId),
528 BindingId(BindingId),
529 TypeRefId(TypeRefId),
530 Dummy,
532}
533impl_from!(ExprId, PatId, BindingId, TypeRefId for Span);
534
535impl From<ExprOrPatIdPacked> for Span {
536 fn from(value: ExprOrPatIdPacked) -> Self {
537 match value.unpack() {
538 ExprOrPatId::ExprId(idx) => idx.into(),
539 ExprOrPatId::PatId(idx) => idx.into(),
540 }
541 }
542}
543
544impl Span {
545 pub(crate) fn pick_best(a: Span, b: Span) -> Span {
546 if b.is_dummy() { b } else { a }
548 }
549
550 #[inline]
551 pub fn is_dummy(&self) -> bool {
552 matches!(self, Self::Dummy)
553 }
554}
555
556#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, salsa::Supertype, Update)]
558pub enum InferBodyId<'db> {
559 DefWithBodyId(DefWithBodyId),
560 AnonConstId(AnonConstId<'db>),
561}
562impl_from!(
563 impl<'db>
564 DefWithBodyId(FunctionId, ConstId, StaticId),
565 AnonConstId<'db>
566 for InferBodyId<'db>
567);
568impl<'db> From<EnumVariantId> for InferBodyId<'db> {
569 fn from(id: EnumVariantId) -> Self {
570 InferBodyId::DefWithBodyId(DefWithBodyId::VariantId(id))
571 }
572}
573
574impl HasModule for InferBodyId<'_> {
575 fn module(&self, db: &dyn SourceDatabase) -> ModuleId {
576 match self {
577 InferBodyId::DefWithBodyId(id) => id.module(db),
578 InferBodyId::AnonConstId(id) => id.module(db),
579 }
580 }
581}
582
583impl HasResolver for InferBodyId<'_> {
584 fn resolver(self, db: &dyn SourceDatabase) -> Resolver<'_> {
585 match self {
586 InferBodyId::DefWithBodyId(id) => id.resolver(db),
587 InferBodyId::AnonConstId(id) => id.resolver(db),
588 }
589 }
590}
591
592impl InferBodyId<'_> {
593 pub fn expression_store_owner(self, db: &dyn HirDatabase) -> ExpressionStoreOwnerId {
594 match self {
595 InferBodyId::DefWithBodyId(id) => id.into(),
596 InferBodyId::AnonConstId(id) => id.loc(db).owner,
597 }
598 }
599
600 pub fn generic_def(self, db: &dyn HirDatabase) -> GenericDefId {
601 match self {
602 InferBodyId::DefWithBodyId(id) => id.generic_def(db),
603 InferBodyId::AnonConstId(id) => id.loc(db).owner.generic_def(db),
604 }
605 }
606
607 #[inline]
608 pub fn as_function(self) -> Option<FunctionId> {
609 match self {
610 InferBodyId::DefWithBodyId(DefWithBodyId::FunctionId(it)) => Some(it),
611 _ => None,
612 }
613 }
614
615 #[inline]
616 pub fn as_variant(self) -> Option<EnumVariantId> {
617 match self {
618 InferBodyId::DefWithBodyId(DefWithBodyId::VariantId(it)) => Some(it),
619 _ => None,
620 }
621 }
622
623 pub fn store_and_root_expr(self, db: &dyn HirDatabase) -> (&ExpressionStore, ExprId) {
624 match self {
625 InferBodyId::DefWithBodyId(id) => {
626 let body = Body::of(db, id);
627 (body, body.root_expr())
628 }
629 InferBodyId::AnonConstId(id) => {
630 let loc = id.loc(db);
631 let store = ExpressionStore::of(db, loc.owner);
632 (store, loc.expr)
633 }
634 }
635 }
636}
637
638pub fn setup_tracing() -> Option<tracing::subscriber::DefaultGuard> {
639 use std::env;
640 use tracing_subscriber::{Registry, layer::SubscriberExt};
641 use tracing_tree::HierarchicalLayer;
642
643 let filter: tracing_subscriber::filter::Targets =
644 env::var("SOLVER_DEBUG").ok().and_then(|it| it.parse().ok()).unwrap_or_default();
645 let layer = HierarchicalLayer::default()
646 .with_indent_lines(true)
647 .with_ansi(false)
648 .with_indent_amount(2)
649 .with_writer(std::io::stderr);
650 let subscriber = Registry::default().with(filter).with(layer);
651 Some(tracing::subscriber::set_default(subscriber))
652}