]> git.lizzy.rs Git - rust.git/blob - src/librustc_typeck/check/closure.rs
cleanup `deduce_expectations_from_obligations`
[rust.git] / src / librustc_typeck / check / closure.rs
1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! Code for type-checking closure expressions.
12
13 use super::{check_fn, Expectation, FnCtxt, GeneratorTypes};
14
15 use astconv::AstConv;
16 use middle::region;
17 use rustc::hir::def_id::DefId;
18 use rustc::infer::{InferOk, InferResult};
19 use rustc::infer::LateBoundRegionConversionTime;
20 use rustc::infer::type_variable::TypeVariableOrigin;
21 use rustc::traits::Obligation;
22 use rustc::traits::error_reporting::ArgKind;
23 use rustc::ty::{self, Ty, GenericParamDefKind};
24 use rustc::ty::fold::TypeFoldable;
25 use rustc::ty::subst::Substs;
26 use std::cmp;
27 use std::iter;
28 use rustc_target::spec::abi::Abi;
29 use syntax::source_map::Span;
30 use rustc::hir;
31
32 /// What signature do we *expect* the closure to have from context?
33 #[derive(Debug)]
34 struct ExpectedSig<'tcx> {
35     /// Span that gave us this expectation, if we know that.
36     cause_span: Option<Span>,
37     sig: ty::FnSig<'tcx>,
38 }
39
40 struct ClosureSignatures<'tcx> {
41     bound_sig: ty::PolyFnSig<'tcx>,
42     liberated_sig: ty::FnSig<'tcx>,
43 }
44
45 impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
46     pub fn check_expr_closure(
47         &self,
48         expr: &hir::Expr,
49         _capture: hir::CaptureClause,
50         decl: &'gcx hir::FnDecl,
51         body_id: hir::BodyId,
52         gen: Option<hir::GeneratorMovability>,
53         expected: Expectation<'tcx>,
54     ) -> Ty<'tcx> {
55         debug!(
56             "check_expr_closure(expr={:?},expected={:?})",
57             expr, expected
58         );
59
60         // It's always helpful for inference if we know the kind of
61         // closure sooner rather than later, so first examine the expected
62         // type, and see if can glean a closure kind from there.
63         let (expected_sig, expected_kind) = match expected.to_option(self) {
64             Some(ty) => self.deduce_expectations_from_expected_type(ty),
65             None => (None, None),
66         };
67         let body = self.tcx.hir().body(body_id);
68         self.check_closure(expr, expected_kind, decl, body, gen, expected_sig)
69     }
70
71     fn check_closure(
72         &self,
73         expr: &hir::Expr,
74         opt_kind: Option<ty::ClosureKind>,
75         decl: &'gcx hir::FnDecl,
76         body: &'gcx hir::Body,
77         gen: Option<hir::GeneratorMovability>,
78         expected_sig: Option<ExpectedSig<'tcx>>,
79     ) -> Ty<'tcx> {
80         debug!(
81             "check_closure(opt_kind={:?}, expected_sig={:?})",
82             opt_kind, expected_sig
83         );
84
85         let expr_def_id = self.tcx.hir().local_def_id(expr.id);
86
87         let ClosureSignatures {
88             bound_sig,
89             liberated_sig,
90         } = self.sig_of_closure(expr_def_id, decl, body, expected_sig);
91
92         debug!("check_closure: ty_of_closure returns {:?}", liberated_sig);
93
94         let generator_types = check_fn(
95             self,
96             self.param_env,
97             liberated_sig,
98             decl,
99             expr.id,
100             body,
101             gen,
102         ).1;
103
104         // Create type variables (for now) to represent the transformed
105         // types of upvars. These will be unified during the upvar
106         // inference phase (`upvar.rs`).
107         let base_substs =
108             Substs::identity_for_item(self.tcx, self.tcx.closure_base_def_id(expr_def_id));
109         let substs = base_substs.extend_to(self.tcx,expr_def_id, |param, _| {
110             match param.kind {
111                 GenericParamDefKind::Lifetime => {
112                     span_bug!(expr.span, "closure has region param")
113                 }
114                 GenericParamDefKind::Type {..} => {
115                     self.infcx
116                         .next_ty_var(TypeVariableOrigin::ClosureSynthetic(expr.span)).into()
117                 }
118             }
119         });
120         if let Some(GeneratorTypes { yield_ty, interior, movability }) = generator_types {
121             let substs = ty::GeneratorSubsts { substs };
122             self.demand_eqtype(
123                 expr.span,
124                 yield_ty,
125                 substs.yield_ty(expr_def_id, self.tcx),
126             );
127             self.demand_eqtype(
128                 expr.span,
129                 liberated_sig.output(),
130                 substs.return_ty(expr_def_id, self.tcx),
131             );
132             self.demand_eqtype(
133                 expr.span,
134                 interior,
135                 substs.witness(expr_def_id, self.tcx),
136             );
137             return self.tcx.mk_generator(expr_def_id, substs, movability);
138         }
139
140         let substs = ty::ClosureSubsts { substs };
141         let closure_type = self.tcx.mk_closure(expr_def_id, substs);
142
143         debug!(
144             "check_closure: expr.id={:?} closure_type={:?}",
145             expr.id, closure_type
146         );
147
148         // Tuple up the arguments and insert the resulting function type into
149         // the `closures` table.
150         let sig = bound_sig.map_bound(|sig| {
151             self.tcx.mk_fn_sig(
152                 iter::once(self.tcx.intern_tup(sig.inputs())),
153                 sig.output(),
154                 sig.variadic,
155                 sig.unsafety,
156                 sig.abi,
157             )
158         });
159
160         debug!(
161             "check_closure: expr_def_id={:?}, sig={:?}, opt_kind={:?}",
162             expr_def_id, sig, opt_kind
163         );
164
165         let sig_fn_ptr_ty = self.tcx.mk_fn_ptr(sig);
166         self.demand_eqtype(
167             expr.span,
168             sig_fn_ptr_ty,
169             substs.closure_sig_ty(expr_def_id, self.tcx),
170         );
171
172         if let Some(kind) = opt_kind {
173             self.demand_eqtype(
174                 expr.span,
175                 kind.to_ty(self.tcx),
176                 substs.closure_kind_ty(expr_def_id, self.tcx),
177             );
178         }
179
180         closure_type
181     }
182
183     /// Given the expected type, figures out what it can about this closure we
184     /// are about to type check:
185     fn deduce_expectations_from_expected_type(
186         &self,
187         expected_ty: Ty<'tcx>,
188     ) -> (Option<ExpectedSig<'tcx>>, Option<ty::ClosureKind>) {
189         debug!(
190             "deduce_expectations_from_expected_type(expected_ty={:?})",
191             expected_ty
192         );
193
194         match expected_ty.sty {
195             ty::Dynamic(ref object_type, ..) => {
196                 let sig = object_type
197                     .projection_bounds()
198                     .filter_map(|pb| {
199                         let pb = pb.with_self_ty(self.tcx, self.tcx.types.err);
200                         self.deduce_sig_from_projection(None, &pb)
201                     })
202                     .next();
203                 let kind = self.tcx.lang_items().fn_trait_kind(object_type.principal().def_id());
204                 (sig, kind)
205             }
206             ty::Infer(ty::TyVar(vid)) => self.deduce_expectations_from_obligations(vid),
207             ty::FnPtr(sig) => {
208                 let expected_sig = ExpectedSig {
209                     cause_span: None,
210                     sig: sig.skip_binder().clone(),
211                 };
212                 (Some(expected_sig), Some(ty::ClosureKind::Fn))
213             }
214             _ => (None, None),
215         }
216     }
217
218     fn deduce_expectations_from_obligations(
219         &self,
220         expected_vid: ty::TyVid,
221     ) -> (Option<ExpectedSig<'tcx>>, Option<ty::ClosureKind>) {
222         let expected_sig = self.obligations_for_self_ty(expected_vid)
223             .find_map(|(_, obligation)| {
224                 debug!(
225                     "deduce_expectations_from_obligations: obligation.predicate={:?}",
226                     obligation.predicate
227                 );
228
229                 if let ty::Predicate::Projection(ref proj_predicate) = obligation.predicate {
230                     // Given a Projection predicate, we can potentially infer
231                     // the complete signature.
232                     self.deduce_sig_from_projection(
233                         Some(obligation.cause.span),
234                         proj_predicate
235                     )
236                 } else {
237                     None
238                 }
239             });
240
241         // Even if we can't infer the full signature, we may be able to
242         // infer the kind. This can occur if there is a trait-reference
243         // like `F : Fn<A>`. Note that due to subtyping we could encounter
244         // many viable options, so pick the most restrictive.
245         let expected_kind = self.obligations_for_self_ty(expected_vid)
246             .filter_map(|(tr, _)| self.tcx.lang_items().fn_trait_kind(tr.def_id()))
247             .fold(None, |best, cur| {
248                 Some(best.map_or(cur, |best| cmp::min(best, cur)))
249             });
250
251         (expected_sig, expected_kind)
252     }
253
254     /// Given a projection like "<F as Fn(X)>::Result == Y", we can deduce
255     /// everything we need to know about a closure.
256     ///
257     /// The `cause_span` should be the span that caused us to
258     /// have this expected signature, or `None` if we can't readily
259     /// know that.
260     fn deduce_sig_from_projection(
261         &self,
262         cause_span: Option<Span>,
263         projection: &ty::PolyProjectionPredicate<'tcx>,
264     ) -> Option<ExpectedSig<'tcx>> {
265         let tcx = self.tcx;
266
267         debug!("deduce_sig_from_projection({:?})", projection);
268
269         let trait_ref = projection.to_poly_trait_ref(tcx);
270
271         if tcx.lang_items().fn_trait_kind(trait_ref.def_id()).is_none() {
272             return None;
273         }
274
275         let arg_param_ty = trait_ref.skip_binder().substs.type_at(1);
276         let arg_param_ty = self.resolve_type_vars_if_possible(&arg_param_ty);
277         debug!(
278             "deduce_sig_from_projection: arg_param_ty {:?}",
279             arg_param_ty
280         );
281
282         let input_tys = match arg_param_ty.sty {
283             ty::Tuple(tys) => tys.into_iter(),
284             _ => return None
285         };
286
287         let ret_param_ty = projection.skip_binder().ty;
288         let ret_param_ty = self.resolve_type_vars_if_possible(&ret_param_ty);
289         debug!(
290             "deduce_sig_from_projection: ret_param_ty {:?}",
291             ret_param_ty
292         );
293
294         let sig = self.tcx.mk_fn_sig(
295             input_tys.cloned(),
296             ret_param_ty,
297             false,
298             hir::Unsafety::Normal,
299             Abi::Rust,
300         );
301         debug!("deduce_sig_from_projection: sig {:?}", sig);
302
303         Some(ExpectedSig { cause_span, sig })
304     }
305
306     fn sig_of_closure(
307         &self,
308         expr_def_id: DefId,
309         decl: &hir::FnDecl,
310         body: &hir::Body,
311         expected_sig: Option<ExpectedSig<'tcx>>,
312     ) -> ClosureSignatures<'tcx> {
313         if let Some(e) = expected_sig {
314             self.sig_of_closure_with_expectation(expr_def_id, decl, body, e)
315         } else {
316             self.sig_of_closure_no_expectation(expr_def_id, decl, body)
317         }
318     }
319
320     /// If there is no expected signature, then we will convert the
321     /// types that the user gave into a signature.
322     fn sig_of_closure_no_expectation(
323         &self,
324         expr_def_id: DefId,
325         decl: &hir::FnDecl,
326         body: &hir::Body,
327     ) -> ClosureSignatures<'tcx> {
328         debug!("sig_of_closure_no_expectation()");
329
330         let bound_sig = self.supplied_sig_of_closure(expr_def_id, decl);
331
332         self.closure_sigs(expr_def_id, body, bound_sig)
333     }
334
335     /// Invoked to compute the signature of a closure expression. This
336     /// combines any user-provided type annotations (e.g., `|x: u32|
337     /// -> u32 { .. }`) with the expected signature.
338     ///
339     /// The approach is as follows:
340     ///
341     /// - Let `S` be the (higher-ranked) signature that we derive from the user's annotations.
342     /// - Let `E` be the (higher-ranked) signature that we derive from the expectations, if any.
343     ///   - If we have no expectation `E`, then the signature of the closure is `S`.
344     ///   - Otherwise, the signature of the closure is E. Moreover:
345     ///     - Skolemize the late-bound regions in `E`, yielding `E'`.
346     ///     - Instantiate all the late-bound regions bound in the closure within `S`
347     ///       with fresh (existential) variables, yielding `S'`
348     ///     - Require that `E' = S'`
349     ///       - We could use some kind of subtyping relationship here,
350     ///         I imagine, but equality is easier and works fine for
351     ///         our purposes.
352     ///
353     /// The key intuition here is that the user's types must be valid
354     /// from "the inside" of the closure, but the expectation
355     /// ultimately drives the overall signature.
356     ///
357     /// # Examples
358     ///
359     /// ```
360     /// fn with_closure<F>(_: F)
361     ///   where F: Fn(&u32) -> &u32 { .. }
362     ///
363     /// with_closure(|x: &u32| { ... })
364     /// ```
365     ///
366     /// Here:
367     /// - E would be `fn(&u32) -> &u32`.
368     /// - S would be `fn(&u32) ->
369     /// - E' is `&'!0 u32 -> &'!0 u32`
370     /// - S' is `&'?0 u32 -> ?T`
371     ///
372     /// S' can be unified with E' with `['?0 = '!0, ?T = &'!10 u32]`.
373     ///
374     /// # Arguments
375     ///
376     /// - `expr_def_id`: the def-id of the closure expression
377     /// - `decl`: the HIR declaration of the closure
378     /// - `body`: the body of the closure
379     /// - `expected_sig`: the expected signature (if any). Note that
380     ///   this is missing a binder: that is, there may be late-bound
381     ///   regions with depth 1, which are bound then by the closure.
382     fn sig_of_closure_with_expectation(
383         &self,
384         expr_def_id: DefId,
385         decl: &hir::FnDecl,
386         body: &hir::Body,
387         expected_sig: ExpectedSig<'tcx>,
388     ) -> ClosureSignatures<'tcx> {
389         debug!(
390             "sig_of_closure_with_expectation(expected_sig={:?})",
391             expected_sig
392         );
393
394         // Watch out for some surprises and just ignore the
395         // expectation if things don't see to match up with what we
396         // expect.
397         if expected_sig.sig.variadic != decl.variadic {
398             return self.sig_of_closure_no_expectation(expr_def_id, decl, body);
399         } else if expected_sig.sig.inputs_and_output.len() != decl.inputs.len() + 1 {
400             return self.sig_of_closure_with_mismatched_number_of_arguments(
401                 expr_def_id,
402                 decl,
403                 body,
404                 expected_sig,
405             );
406         }
407
408         // Create a `PolyFnSig`. Note the oddity that late bound
409         // regions appearing free in `expected_sig` are now bound up
410         // in this binder we are creating.
411         assert!(!expected_sig.sig.has_vars_bound_above(ty::INNERMOST));
412         let bound_sig = ty::Binder::bind(self.tcx.mk_fn_sig(
413             expected_sig.sig.inputs().iter().cloned(),
414             expected_sig.sig.output(),
415             decl.variadic,
416             hir::Unsafety::Normal,
417             Abi::RustCall,
418         ));
419
420         // `deduce_expectations_from_expected_type` introduces
421         // late-bound lifetimes defined elsewhere, which we now
422         // anonymize away, so as not to confuse the user.
423         let bound_sig = self.tcx.anonymize_late_bound_regions(&bound_sig);
424
425         let closure_sigs = self.closure_sigs(expr_def_id, body, bound_sig);
426
427         // Up till this point, we have ignored the annotations that the user
428         // gave. This function will check that they unify successfully.
429         // Along the way, it also writes out entries for types that the user
430         // wrote into our tables, which are then later used by the privacy
431         // check.
432         match self.check_supplied_sig_against_expectation(expr_def_id, decl, body, &closure_sigs) {
433             Ok(infer_ok) => self.register_infer_ok_obligations(infer_ok),
434             Err(_) => return self.sig_of_closure_no_expectation(expr_def_id, decl, body),
435         }
436
437         closure_sigs
438     }
439
440     fn sig_of_closure_with_mismatched_number_of_arguments(
441         &self,
442         expr_def_id: DefId,
443         decl: &hir::FnDecl,
444         body: &hir::Body,
445         expected_sig: ExpectedSig<'tcx>,
446     ) -> ClosureSignatures<'tcx> {
447         let expr_map_node = self.tcx.hir().get_if_local(expr_def_id).unwrap();
448         let expected_args: Vec<_> = expected_sig
449             .sig
450             .inputs()
451             .iter()
452             .map(|ty| ArgKind::from_expected_ty(ty, None))
453             .collect();
454         let (closure_span, found_args) = self.get_fn_like_arguments(expr_map_node);
455         let expected_span = expected_sig.cause_span.unwrap_or(closure_span);
456         self.report_arg_count_mismatch(
457             expected_span,
458             Some(closure_span),
459             expected_args,
460             found_args,
461             true,
462         ).emit();
463
464         let error_sig = self.error_sig_of_closure(decl);
465
466         self.closure_sigs(expr_def_id, body, error_sig)
467     }
468
469     /// Enforce the user's types against the expectation.  See
470     /// `sig_of_closure_with_expectation` for details on the overall
471     /// strategy.
472     fn check_supplied_sig_against_expectation(
473         &self,
474         expr_def_id: DefId,
475         decl: &hir::FnDecl,
476         body: &hir::Body,
477         expected_sigs: &ClosureSignatures<'tcx>,
478     ) -> InferResult<'tcx, ()> {
479         // Get the signature S that the user gave.
480         //
481         // (See comment on `sig_of_closure_with_expectation` for the
482         // meaning of these letters.)
483         let supplied_sig = self.supplied_sig_of_closure(expr_def_id, decl);
484
485         debug!(
486             "check_supplied_sig_against_expectation: supplied_sig={:?}",
487             supplied_sig
488         );
489
490         // FIXME(#45727): As discussed in [this comment][c1], naively
491         // forcing equality here actually results in suboptimal error
492         // messages in some cases.  For now, if there would have been
493         // an obvious error, we fallback to declaring the type of the
494         // closure to be the one the user gave, which allows other
495         // error message code to trigger.
496         //
497         // However, I think [there is potential to do even better
498         // here][c2], since in *this* code we have the precise span of
499         // the type parameter in question in hand when we report the
500         // error.
501         //
502         // [c1]: https://github.com/rust-lang/rust/pull/45072#issuecomment-341089706
503         // [c2]: https://github.com/rust-lang/rust/pull/45072#issuecomment-341096796
504         self.infcx.commit_if_ok(|_| {
505             let mut all_obligations = vec![];
506
507             // The liberated version of this signature should be be a subtype
508             // of the liberated form of the expectation.
509             for ((hir_ty, &supplied_ty), expected_ty) in decl.inputs.iter()
510                .zip(*supplied_sig.inputs().skip_binder()) // binder moved to (*) below
511                .zip(expected_sigs.liberated_sig.inputs())
512             // `liberated_sig` is E'.
513             {
514                 // Instantiate (this part of..) S to S', i.e., with fresh variables.
515                 let (supplied_ty, _) = self.infcx.replace_bound_vars_with_fresh_vars(
516                     hir_ty.span,
517                     LateBoundRegionConversionTime::FnCall,
518                     &ty::Binder::bind(supplied_ty),
519                 ); // recreated from (*) above
520
521                 // Check that E' = S'.
522                 let cause = &self.misc(hir_ty.span);
523                 let InferOk {
524                     value: (),
525                     obligations,
526                 } = self.at(cause, self.param_env)
527                     .eq(*expected_ty, supplied_ty)?;
528                 all_obligations.extend(obligations);
529
530                 // Also, require that the supplied type must outlive
531                 // the closure body.
532                 let closure_body_region = self.tcx.mk_region(
533                     ty::ReScope(
534                         region::Scope {
535                             id: body.value.hir_id.local_id,
536                             data: region::ScopeData::Node,
537                         },
538                     ),
539                 );
540                 all_obligations.push(
541                     Obligation::new(
542                         cause.clone(),
543                         self.param_env,
544                         ty::Predicate::TypeOutlives(
545                             ty::Binder::dummy(
546                                 ty::OutlivesPredicate(
547                                     supplied_ty,
548                                     closure_body_region,
549                                 ),
550                             ),
551                         ),
552                     ),
553                 );
554             }
555
556             let (supplied_output_ty, _) = self.infcx.replace_bound_vars_with_fresh_vars(
557                 decl.output.span(),
558                 LateBoundRegionConversionTime::FnCall,
559                 &supplied_sig.output(),
560             );
561             let cause = &self.misc(decl.output.span());
562             let InferOk {
563                 value: (),
564                 obligations,
565             } = self.at(cause, self.param_env)
566                 .eq(expected_sigs.liberated_sig.output(), supplied_output_ty)?;
567             all_obligations.extend(obligations);
568
569             Ok(InferOk {
570                 value: (),
571                 obligations: all_obligations,
572             })
573         })
574     }
575
576     /// If there is no expected signature, then we will convert the
577     /// types that the user gave into a signature.
578     ///
579     /// Also, record this closure signature for later.
580     fn supplied_sig_of_closure(
581         &self,
582         expr_def_id: DefId,
583         decl: &hir::FnDecl,
584     ) -> ty::PolyFnSig<'tcx> {
585         let astconv: &dyn AstConv = self;
586
587         // First, convert the types that the user supplied (if any).
588         let supplied_arguments = decl.inputs.iter().map(|a| astconv.ast_ty_to_ty(a));
589         let supplied_return = match decl.output {
590             hir::Return(ref output) => astconv.ast_ty_to_ty(&output),
591             hir::DefaultReturn(_) => astconv.ty_infer(decl.output.span()),
592         };
593
594         let result = ty::Binder::bind(self.tcx.mk_fn_sig(
595             supplied_arguments,
596             supplied_return,
597             decl.variadic,
598             hir::Unsafety::Normal,
599             Abi::RustCall,
600         ));
601
602         debug!("supplied_sig_of_closure: result={:?}", result);
603
604         let c_result = self.inh.infcx.canonicalize_response(&result);
605         self.tables.borrow_mut().user_provided_sigs.insert(
606             expr_def_id,
607             c_result,
608         );
609
610         result
611     }
612
613     /// Converts the types that the user supplied, in case that doing
614     /// so should yield an error, but returns back a signature where
615     /// all parameters are of type `TyErr`.
616     fn error_sig_of_closure(&self, decl: &hir::FnDecl) -> ty::PolyFnSig<'tcx> {
617         let astconv: &dyn AstConv = self;
618
619         let supplied_arguments = decl.inputs.iter().map(|a| {
620             // Convert the types that the user supplied (if any), but ignore them.
621             astconv.ast_ty_to_ty(a);
622             self.tcx.types.err
623         });
624
625         if let hir::Return(ref output) = decl.output {
626             astconv.ast_ty_to_ty(&output);
627         }
628
629         let result = ty::Binder::bind(self.tcx.mk_fn_sig(
630             supplied_arguments,
631             self.tcx.types.err,
632             decl.variadic,
633             hir::Unsafety::Normal,
634             Abi::RustCall,
635         ));
636
637         debug!("supplied_sig_of_closure: result={:?}", result);
638
639         result
640     }
641
642     fn closure_sigs(
643         &self,
644         expr_def_id: DefId,
645         body: &hir::Body,
646         bound_sig: ty::PolyFnSig<'tcx>,
647     ) -> ClosureSignatures<'tcx> {
648         let liberated_sig = self.tcx()
649             .liberate_late_bound_regions(expr_def_id, &bound_sig);
650         let liberated_sig = self.inh.normalize_associated_types_in(
651             body.value.span,
652             body.value.id,
653             self.param_env,
654             &liberated_sig,
655         );
656         ClosureSignatures {
657             bound_sig,
658             liberated_sig,
659         }
660     }
661 }