1use std::fmt::Debug;
11use std::iter;
12
13use rustc_data_structures::captures::Captures;
14use rustc_index::{Idx, IndexVec};
15use rustc_middle::arena::ArenaAllocatable;
16use rustc_middle::mir::ConstraintCategory;
17use rustc_middle::ty::fold::TypeFoldable;
18use rustc_middle::ty::{self, BoundVar, GenericArg, GenericArgKind, Ty, TyCtxt};
19use rustc_middle::{bug, span_bug};
20use tracing::{debug, instrument};
21
22use crate::infer::canonical::instantiate::{CanonicalExt, instantiate_value};
23use crate::infer::canonical::{
24 Canonical, CanonicalQueryResponse, CanonicalVarValues, Certainty, OriginalQueryValues,
25 QueryOutlivesConstraint, QueryRegionConstraints, QueryResponse,
26};
27use crate::infer::region_constraints::{Constraint, RegionConstraintData};
28use crate::infer::{DefineOpaqueTypes, InferCtxt, InferOk, InferResult};
29use crate::traits::query::NoSolution;
30use crate::traits::{
31 Obligation, ObligationCause, PredicateObligation, PredicateObligations, ScrubbedTraitError,
32 TraitEngine,
33};
34
35impl<'tcx> InferCtxt<'tcx> {
36 #[instrument(skip(self, inference_vars, answer, fulfill_cx), level = "trace")]
56 pub fn make_canonicalized_query_response<T>(
57 &self,
58 inference_vars: CanonicalVarValues<'tcx>,
59 answer: T,
60 fulfill_cx: &mut dyn TraitEngine<'tcx, ScrubbedTraitError<'tcx>>,
61 ) -> Result<CanonicalQueryResponse<'tcx, T>, NoSolution>
62 where
63 T: Debug + TypeFoldable<TyCtxt<'tcx>>,
64 Canonical<'tcx, QueryResponse<'tcx, T>>: ArenaAllocatable<'tcx>,
65 {
66 let query_response = self.make_query_response(inference_vars, answer, fulfill_cx)?;
67 debug!("query_response = {:#?}", query_response);
68 let canonical_result = self.canonicalize_response(query_response);
69 debug!("canonical_result = {:#?}", canonical_result);
70
71 Ok(self.tcx.arena.alloc(canonical_result))
72 }
73
74 pub fn make_query_response_ignoring_pending_obligations<T>(
84 &self,
85 inference_vars: CanonicalVarValues<'tcx>,
86 answer: T,
87 ) -> Canonical<'tcx, QueryResponse<'tcx, T>>
88 where
89 T: Debug + TypeFoldable<TyCtxt<'tcx>>,
90 {
91 self.canonicalize_response(QueryResponse {
92 var_values: inference_vars,
93 region_constraints: QueryRegionConstraints::default(),
94 certainty: Certainty::Proven, opaque_types: vec![],
96 value: answer,
97 })
98 }
99
100 #[instrument(skip(self, fulfill_cx), level = "debug")]
103 fn make_query_response<T>(
104 &self,
105 inference_vars: CanonicalVarValues<'tcx>,
106 answer: T,
107 fulfill_cx: &mut dyn TraitEngine<'tcx, ScrubbedTraitError<'tcx>>,
108 ) -> Result<QueryResponse<'tcx, T>, NoSolution>
109 where
110 T: Debug + TypeFoldable<TyCtxt<'tcx>>,
111 {
112 let tcx = self.tcx;
113
114 let errors = fulfill_cx.select_all_or_error(self);
116
117 if errors.iter().any(|e| e.is_true_error()) {
119 return Err(NoSolution);
120 }
121
122 let region_obligations = self.take_registered_region_obligations();
123 debug!(?region_obligations);
124 let region_constraints = self.with_region_constraints(|region_constraints| {
125 make_query_region_constraints(
126 tcx,
127 region_obligations
128 .iter()
129 .map(|r_o| (r_o.sup_type, r_o.sub_region, r_o.origin.to_constraint_category())),
130 region_constraints,
131 )
132 });
133 debug!(?region_constraints);
134
135 let certainty = if errors.is_empty() { Certainty::Proven } else { Certainty::Ambiguous };
136
137 let opaque_types = self.take_opaque_types_for_query_response();
138
139 Ok(QueryResponse {
140 var_values: inference_vars,
141 region_constraints,
142 certainty,
143 value: answer,
144 opaque_types,
145 })
146 }
147
148 pub fn clone_opaque_types_for_query_response(
151 &self,
152 ) -> Vec<(ty::OpaqueTypeKey<'tcx>, Ty<'tcx>)> {
153 self.inner
154 .borrow()
155 .opaque_type_storage
156 .opaque_types
157 .iter()
158 .map(|(k, v)| (*k, v.ty))
159 .collect()
160 }
161
162 fn take_opaque_types_for_query_response(&self) -> Vec<(ty::OpaqueTypeKey<'tcx>, Ty<'tcx>)> {
163 self.take_opaque_types().into_iter().map(|(k, v)| (k, v.ty)).collect()
164 }
165
166 pub fn instantiate_query_response_and_region_obligations<R>(
177 &self,
178 cause: &ObligationCause<'tcx>,
179 param_env: ty::ParamEnv<'tcx>,
180 original_values: &OriginalQueryValues<'tcx>,
181 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
182 ) -> InferResult<'tcx, R>
183 where
184 R: Debug + TypeFoldable<TyCtxt<'tcx>>,
185 {
186 let InferOk { value: result_args, mut obligations } =
187 self.query_response_instantiation(cause, param_env, original_values, query_response)?;
188
189 obligations.extend(self.query_outlives_constraints_into_obligations(
190 cause,
191 param_env,
192 &query_response.value.region_constraints.outlives,
193 &result_args,
194 ));
195
196 let user_result: R =
197 query_response.instantiate_projected(self.tcx, &result_args, |q_r| q_r.value.clone());
198
199 Ok(InferOk { value: user_result, obligations })
200 }
201
202 pub fn instantiate_nll_query_response_and_region_obligations<R>(
238 &self,
239 cause: &ObligationCause<'tcx>,
240 param_env: ty::ParamEnv<'tcx>,
241 original_values: &OriginalQueryValues<'tcx>,
242 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
243 output_query_region_constraints: &mut QueryRegionConstraints<'tcx>,
244 ) -> InferResult<'tcx, R>
245 where
246 R: Debug + TypeFoldable<TyCtxt<'tcx>>,
247 {
248 let InferOk { value: result_args, mut obligations } = self
249 .query_response_instantiation_guess(
250 cause,
251 param_env,
252 original_values,
253 query_response,
254 )?;
255
256 let constraint_category = cause.to_constraint_category();
261
262 for (index, original_value) in original_values.var_values.iter().enumerate() {
263 let result_value = query_response.instantiate_projected(self.tcx, &result_args, |v| {
265 v.var_values[BoundVar::new(index)]
266 });
267 match (original_value.unpack(), result_value.unpack()) {
268 (GenericArgKind::Lifetime(re1), GenericArgKind::Lifetime(re2))
269 if re1.is_erased() && re2.is_erased() =>
270 {
271 }
273
274 (GenericArgKind::Lifetime(v_o), GenericArgKind::Lifetime(v_r)) => {
275 if v_o != v_r {
277 output_query_region_constraints
278 .outlives
279 .push((ty::OutlivesPredicate(v_o.into(), v_r), constraint_category));
280 output_query_region_constraints
281 .outlives
282 .push((ty::OutlivesPredicate(v_r.into(), v_o), constraint_category));
283 }
284 }
285
286 (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => {
287 obligations.extend(
288 self.at(&cause, param_env)
289 .eq(DefineOpaqueTypes::Yes, v1, v2)?
290 .into_obligations(),
291 );
292 }
293
294 (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => {
295 obligations.extend(
296 self.at(&cause, param_env)
297 .eq(DefineOpaqueTypes::Yes, v1, v2)?
298 .into_obligations(),
299 );
300 }
301
302 _ => {
303 bug!("kind mismatch, cannot unify {:?} and {:?}", original_value, result_value);
304 }
305 }
306 }
307
308 output_query_region_constraints.outlives.extend(
310 query_response.value.region_constraints.outlives.iter().filter_map(|&r_c| {
311 let r_c = instantiate_value(self.tcx, &result_args, r_c);
312
313 let ty::OutlivesPredicate(k1, r2) = r_c.0;
315 if k1 != r2.into() { Some(r_c) } else { None }
316 }),
317 );
318
319 let user_result: R =
320 query_response.instantiate_projected(self.tcx, &result_args, |q_r| q_r.value.clone());
321
322 Ok(InferOk { value: user_result, obligations })
323 }
324
325 fn query_response_instantiation<R>(
336 &self,
337 cause: &ObligationCause<'tcx>,
338 param_env: ty::ParamEnv<'tcx>,
339 original_values: &OriginalQueryValues<'tcx>,
340 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
341 ) -> InferResult<'tcx, CanonicalVarValues<'tcx>>
342 where
343 R: Debug + TypeFoldable<TyCtxt<'tcx>>,
344 {
345 debug!(
346 "query_response_instantiation(original_values={:#?}, query_response={:#?})",
347 original_values, query_response,
348 );
349
350 let mut value = self.query_response_instantiation_guess(
351 cause,
352 param_env,
353 original_values,
354 query_response,
355 )?;
356
357 value.obligations.extend(
358 self.unify_query_response_instantiation_guess(
359 cause,
360 param_env,
361 original_values,
362 &value.value,
363 query_response,
364 )?
365 .into_obligations(),
366 );
367
368 Ok(value)
369 }
370
371 #[instrument(level = "debug", skip(self, param_env))]
381 fn query_response_instantiation_guess<R>(
382 &self,
383 cause: &ObligationCause<'tcx>,
384 param_env: ty::ParamEnv<'tcx>,
385 original_values: &OriginalQueryValues<'tcx>,
386 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
387 ) -> InferResult<'tcx, CanonicalVarValues<'tcx>>
388 where
389 R: Debug + TypeFoldable<TyCtxt<'tcx>>,
390 {
391 let mut universe_map = original_values.universe_map.clone();
395 let num_universes_in_query = original_values.universe_map.len();
396 let num_universes_in_response = query_response.max_universe.as_usize() + 1;
397 for _ in num_universes_in_query..num_universes_in_response {
398 universe_map.push(self.create_next_universe());
399 }
400 assert!(!universe_map.is_empty()); assert_eq!(universe_map[ty::UniverseIndex::ROOT.as_usize()], ty::UniverseIndex::ROOT);
402
403 let result_values = &query_response.value.var_values;
408 assert_eq!(original_values.var_values.len(), result_values.len());
409
410 let mut opt_values: IndexVec<BoundVar, Option<GenericArg<'tcx>>> =
418 IndexVec::from_elem_n(None, query_response.variables.len());
419
420 for (original_value, result_value) in iter::zip(&original_values.var_values, result_values)
423 {
424 match result_value.unpack() {
425 GenericArgKind::Type(result_value) => {
426 if let ty::Bound(debruijn, b) = *result_value.kind() {
428 assert_eq!(debruijn, ty::INNERMOST);
432 opt_values[b.var] = Some(*original_value);
433 }
434 }
435 GenericArgKind::Lifetime(result_value) => {
436 if let ty::ReBound(debruijn, br) = *result_value {
438 assert_eq!(debruijn, ty::INNERMOST);
442 opt_values[br.var] = Some(*original_value);
443 }
444 }
445 GenericArgKind::Const(result_value) => {
446 if let ty::ConstKind::Bound(debruijn, b) = result_value.kind() {
447 assert_eq!(debruijn, ty::INNERMOST);
451 opt_values[b] = Some(*original_value);
452 }
453 }
454 }
455 }
456
457 let result_args = CanonicalVarValues {
461 var_values: self.tcx.mk_args_from_iter(
462 query_response.variables.iter().enumerate().map(|(index, info)| {
463 if info.universe() != ty::UniverseIndex::ROOT {
464 self.instantiate_canonical_var(cause.span, info, |u| {
467 universe_map[u.as_usize()]
468 })
469 } else if info.is_existential() {
470 match opt_values[BoundVar::new(index)] {
471 Some(k) => k,
472 None => self.instantiate_canonical_var(cause.span, info, |u| {
473 universe_map[u.as_usize()]
474 }),
475 }
476 } else {
477 opt_values[BoundVar::new(index)].expect(
480 "expected placeholder to be unified with itself during response",
481 )
482 }
483 }),
484 ),
485 };
486
487 let mut obligations = PredicateObligations::new();
488
489 for &(a, b) in &query_response.value.opaque_types {
491 let a = instantiate_value(self.tcx, &result_args, a);
492 let b = instantiate_value(self.tcx, &result_args, b);
493 debug!(?a, ?b, "constrain opaque type");
494 obligations.extend(
499 self.at(cause, param_env)
500 .eq(
501 DefineOpaqueTypes::Yes,
502 Ty::new_opaque(self.tcx, a.def_id.to_def_id(), a.args),
503 b,
504 )?
505 .obligations,
506 );
507 }
508
509 Ok(InferOk { value: result_args, obligations })
510 }
511
512 fn unify_query_response_instantiation_guess<R>(
519 &self,
520 cause: &ObligationCause<'tcx>,
521 param_env: ty::ParamEnv<'tcx>,
522 original_values: &OriginalQueryValues<'tcx>,
523 result_args: &CanonicalVarValues<'tcx>,
524 query_response: &Canonical<'tcx, QueryResponse<'tcx, R>>,
525 ) -> InferResult<'tcx, ()>
526 where
527 R: Debug + TypeFoldable<TyCtxt<'tcx>>,
528 {
529 let instantiated_query_response = |index: BoundVar| -> GenericArg<'tcx> {
534 query_response.instantiate_projected(self.tcx, result_args, |v| v.var_values[index])
535 };
536
537 self.unify_canonical_vars(cause, param_env, original_values, instantiated_query_response)
540 }
541
542 fn query_outlives_constraints_into_obligations<'a>(
545 &'a self,
546 cause: &'a ObligationCause<'tcx>,
547 param_env: ty::ParamEnv<'tcx>,
548 uninstantiated_region_constraints: &'a [QueryOutlivesConstraint<'tcx>],
549 result_args: &'a CanonicalVarValues<'tcx>,
550 ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a + Captures<'tcx> {
551 uninstantiated_region_constraints.iter().map(move |&constraint| {
552 let predicate = instantiate_value(self.tcx, result_args, constraint);
553 self.query_outlives_constraint_to_obligation(predicate, cause.clone(), param_env)
554 })
555 }
556
557 pub fn query_outlives_constraint_to_obligation(
558 &self,
559 (predicate, _): QueryOutlivesConstraint<'tcx>,
560 cause: ObligationCause<'tcx>,
561 param_env: ty::ParamEnv<'tcx>,
562 ) -> Obligation<'tcx, ty::Predicate<'tcx>> {
563 let ty::OutlivesPredicate(k1, r2) = predicate;
564
565 let atom = match k1.unpack() {
566 GenericArgKind::Lifetime(r1) => ty::PredicateKind::Clause(
567 ty::ClauseKind::RegionOutlives(ty::OutlivesPredicate(r1, r2)),
568 ),
569 GenericArgKind::Type(t1) => ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(
570 ty::OutlivesPredicate(t1, r2),
571 )),
572 GenericArgKind::Const(..) => {
573 span_bug!(cause.span, "unexpected const outlives {:?}", predicate);
576 }
577 };
578 let predicate = ty::Binder::dummy(atom);
579
580 Obligation::new(self.tcx, cause, param_env, predicate)
581 }
582
583 fn unify_canonical_vars(
586 &self,
587 cause: &ObligationCause<'tcx>,
588 param_env: ty::ParamEnv<'tcx>,
589 variables1: &OriginalQueryValues<'tcx>,
590 variables2: impl Fn(BoundVar) -> GenericArg<'tcx>,
591 ) -> InferResult<'tcx, ()> {
592 let mut obligations = PredicateObligations::new();
593 for (index, value1) in variables1.var_values.iter().enumerate() {
594 let value2 = variables2(BoundVar::new(index));
595
596 match (value1.unpack(), value2.unpack()) {
597 (GenericArgKind::Type(v1), GenericArgKind::Type(v2)) => {
598 obligations.extend(
599 self.at(cause, param_env)
600 .eq(DefineOpaqueTypes::Yes, v1, v2)?
601 .into_obligations(),
602 );
603 }
604 (GenericArgKind::Lifetime(re1), GenericArgKind::Lifetime(re2))
605 if re1.is_erased() && re2.is_erased() =>
606 {
607 }
609 (GenericArgKind::Lifetime(v1), GenericArgKind::Lifetime(v2)) => {
610 obligations.extend(
611 self.at(cause, param_env)
612 .eq(DefineOpaqueTypes::Yes, v1, v2)?
613 .into_obligations(),
614 );
615 }
616 (GenericArgKind::Const(v1), GenericArgKind::Const(v2)) => {
617 let ok = self.at(cause, param_env).eq(DefineOpaqueTypes::Yes, v1, v2)?;
618 obligations.extend(ok.into_obligations());
619 }
620 _ => {
621 bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,);
622 }
623 }
624 }
625 Ok(InferOk { value: (), obligations })
626 }
627}
628
629pub fn make_query_region_constraints<'tcx>(
632 tcx: TyCtxt<'tcx>,
633 outlives_obligations: impl Iterator<Item = (Ty<'tcx>, ty::Region<'tcx>, ConstraintCategory<'tcx>)>,
634 region_constraints: &RegionConstraintData<'tcx>,
635) -> QueryRegionConstraints<'tcx> {
636 let RegionConstraintData { constraints, verifys } = region_constraints;
637
638 assert!(verifys.is_empty());
639
640 debug!(?constraints);
641
642 let outlives: Vec<_> = constraints
643 .iter()
644 .map(|(k, origin)| {
645 let constraint = match *k {
646 Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate(
649 ty::Region::new_var(tcx, v2).into(),
650 ty::Region::new_var(tcx, v1),
651 ),
652 Constraint::VarSubReg(v1, r2) => {
653 ty::OutlivesPredicate(r2.into(), ty::Region::new_var(tcx, v1))
654 }
655 Constraint::RegSubVar(r1, v2) => {
656 ty::OutlivesPredicate(ty::Region::new_var(tcx, v2).into(), r1)
657 }
658 Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1),
659 };
660 (constraint, origin.to_constraint_category())
661 })
662 .chain(outlives_obligations.map(|(ty, r, constraint_category)| {
663 (ty::OutlivesPredicate(ty.into(), r), constraint_category)
664 }))
665 .collect();
666
667 QueryRegionConstraints { outlives }
668}