compiler/rustc_middle/src/ty/closure.rs

   1 use crate::hir::place::{
   2     Place as HirPlace, PlaceBase as HirPlaceBase, ProjectionKind as HirProjectionKind,
   3 };
   4 use crate::{mir, ty};
   5
   6 use std::fmt::Write;
   7
   8 use rustc_data_structures::fx::{FxHashMap, FxIndexMap};
   9 use rustc_hir as hir;
  10 use rustc_hir::def_id::{DefId, LocalDefId};
  11 use rustc_span::{Span, Symbol};
  12
  13 use super::{Ty, TyCtxt};
  14
  15 use self::BorrowKind::*;
  16
  17 // Captures are represented using fields inside a structure.
  18 // This represents accessing self in the closure structure
  19 pub const CAPTURE_STRUCT_LOCAL: mir::Local = mir::Local::from_u32(1);
  20
  21 #[derive(
  22     Clone,
  23     Copy,
  24     Debug,
  25     PartialEq,
  26     Eq,
  27     Hash,
  28     TyEncodable,
  29     TyDecodable,
  30     TypeFoldable,
  31     HashStable
  32 )]
  33 pub struct UpvarPath {
  34     pub hir_id: hir::HirId,
  35 }
  36
  37 /// Upvars do not get their own `NodeId`. Instead, we use the pair of
  38 /// the original var ID (that is, the root variable that is referenced
  39 /// by the upvar) and the ID of the closure expression.
  40 #[derive(Clone, Copy, PartialEq, Eq, Hash, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
  41 pub struct UpvarId {
  42     pub var_path: UpvarPath,
  43     pub closure_expr_id: LocalDefId,
  44 }
  45
  46 impl UpvarId {
  47     pub fn new(var_hir_id: hir::HirId, closure_def_id: LocalDefId) -> UpvarId {
  48         UpvarId { var_path: UpvarPath { hir_id: var_hir_id }, closure_expr_id: closure_def_id }
  49     }
  50 }
  51
  52 /// Information describing the capture of an upvar. This is computed
  53 /// during `typeck`, specifically by `regionck`.
  54 #[derive(PartialEq, Clone, Debug, Copy, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
  55 pub enum UpvarCapture {
  56     /// Upvar is captured by value. This is always true when the
  57     /// closure is labeled `move`, but can also be true in other cases
  58     /// depending on inference.
  59     ByValue,
  60
  61     /// Upvar is captured by reference.
  62     ByRef(BorrowKind),
  63 }
  64
  65 pub type UpvarListMap = FxHashMap<DefId, FxIndexMap<hir::HirId, UpvarId>>;
  66 pub type UpvarCaptureMap = FxHashMap<UpvarId, UpvarCapture>;
  67
  68 /// Given the closure DefId this map provides a map of root variables to minimum
  69 /// set of `CapturedPlace`s that need to be tracked to support all captures of that closure.
  70 pub type MinCaptureInformationMap<'tcx> = FxHashMap<DefId, RootVariableMinCaptureList<'tcx>>;
  71
  72 /// Part of `MinCaptureInformationMap`; Maps a root variable to the list of `CapturedPlace`.
  73 /// Used to track the minimum set of `Place`s that need to be captured to support all
  74 /// Places captured by the closure starting at a given root variable.
  75 ///
  76 /// This provides a convenient and quick way of checking if a variable being used within
  77 /// a closure is a capture of a local variable.
  78 pub type RootVariableMinCaptureList<'tcx> = FxIndexMap<hir::HirId, MinCaptureList<'tcx>>;
  79
  80 /// Part of `MinCaptureInformationMap`; List of `CapturePlace`s.
  81 pub type MinCaptureList<'tcx> = Vec<CapturedPlace<'tcx>>;
  82
  83 /// Represents the various closure traits in the language. This
  84 /// will determine the type of the environment (`self`, in the
  85 /// desugaring) argument that the closure expects.
  86 ///
  87 /// You can get the environment type of a closure using
  88 /// `tcx.closure_env_ty()`.
  89 #[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash, Debug, TyEncodable, TyDecodable)]
  90 #[derive(HashStable)]
  91 pub enum ClosureKind {
  92     // Warning: Ordering is significant here! The ordering is chosen
  93     // because the trait Fn is a subtrait of FnMut and so in turn, and
  94     // hence we order it so that Fn < FnMut < FnOnce.
  95     Fn,
  96     FnMut,
  97     FnOnce,
  98 }
  99
 100 impl<'tcx> ClosureKind {
 101     // This is the initial value used when doing upvar inference.
 102     pub const LATTICE_BOTTOM: ClosureKind = ClosureKind::Fn;
 103
 104     /// Returns `true` if a type that impls this closure kind
 105     /// must also implement `other`.
 106     pub fn extends(self, other: ty::ClosureKind) -> bool {
 107         matches!(
 108             (self, other),
 109             (ClosureKind::Fn, ClosureKind::Fn)
 110                 | (ClosureKind::Fn, ClosureKind::FnMut)
 111                 | (ClosureKind::Fn, ClosureKind::FnOnce)
 112                 | (ClosureKind::FnMut, ClosureKind::FnMut)
 113                 | (ClosureKind::FnMut, ClosureKind::FnOnce)
 114                 | (ClosureKind::FnOnce, ClosureKind::FnOnce)
 115         )
 116     }
 117
 118     /// Returns the representative scalar type for this closure kind.
 119     /// See `TyS::to_opt_closure_kind` for more details.
 120     pub fn to_ty(self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
 121         match self {
 122             ty::ClosureKind::Fn => tcx.types.i8,
 123             ty::ClosureKind::FnMut => tcx.types.i16,
 124             ty::ClosureKind::FnOnce => tcx.types.i32,
 125         }
 126     }
 127 }
 128
 129 /// A composite describing a `Place` that is captured by a closure.
 130 #[derive(PartialEq, Clone, Debug, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
 131 pub struct CapturedPlace<'tcx> {
 132     /// The `Place` that is captured.
 133     pub place: HirPlace<'tcx>,
 134
 135     /// `CaptureKind` and expression(s) that resulted in such capture of `place`.
 136     pub info: CaptureInfo,
 137
 138     /// Represents if `place` can be mutated or not.
 139     pub mutability: hir::Mutability,
 140
 141     /// Region of the resulting reference if the upvar is captured by ref.
 142     pub region: Option<ty::Region<'tcx>>,
 143 }
 144
 145 impl<'tcx> CapturedPlace<'tcx> {
 146     pub fn to_string(&self, tcx: TyCtxt<'tcx>) -> String {
 147         place_to_string_for_capture(tcx, &self.place)
 148     }
 149
 150     /// Returns a symbol of the captured upvar, which looks like `name__field1__field2`.
 151     fn to_symbol(&self, tcx: TyCtxt<'tcx>) -> Symbol {
 152         let hir_id = match self.place.base {
 153             HirPlaceBase::Upvar(upvar_id) => upvar_id.var_path.hir_id,
 154             base => bug!("Expected an upvar, found {:?}", base),
 155         };
 156         let mut symbol = tcx.hir().name(hir_id).as_str().to_string();
 157
 158         let mut ty = self.place.base_ty;
 159         for proj in self.place.projections.iter() {
 160             match proj.kind {
 161                 HirProjectionKind::Field(idx, variant) => match ty.kind() {
 162                     ty::Tuple(_) => write!(&mut symbol, "__{}", idx).unwrap(),
 163                     ty::Adt(def, ..) => {
 164                         write!(
 165                             &mut symbol,
 166                             "__{}",
 167                             def.variants[variant].fields[idx as usize].name.as_str(),
 168                         )
 169                         .unwrap();
 170                     }
 171                     ty => {
 172                         bug!("Unexpected type {:?} for `Field` projection", ty)
 173                     }
 174                 },
 175
 176                 // Ignore derefs for now, as they are likely caused by
 177                 // autoderefs that don't appear in the original code.
 178                 HirProjectionKind::Deref => {}
 179                 proj => bug!("Unexpected projection {:?} in captured place", proj),
 180             }
 181             ty = proj.ty;
 182         }
 183
 184         Symbol::intern(&symbol)
 185     }
 186
 187     /// Returns the hir-id of the root variable for the captured place.
 188     /// e.g., if `a.b.c` was captured, would return the hir-id for `a`.
 189     pub fn get_root_variable(&self) -> hir::HirId {
 190         match self.place.base {
 191             HirPlaceBase::Upvar(upvar_id) => upvar_id.var_path.hir_id,
 192             base => bug!("Expected upvar, found={:?}", base),
 193         }
 194     }
 195
 196     /// Returns the `LocalDefId` of the closure that captured this Place
 197     pub fn get_closure_local_def_id(&self) -> LocalDefId {
 198         match self.place.base {
 199             HirPlaceBase::Upvar(upvar_id) => upvar_id.closure_expr_id,
 200             base => bug!("expected upvar, found={:?}", base),
 201         }
 202     }
 203
 204     /// Return span pointing to use that resulted in selecting the captured path
 205     pub fn get_path_span(&self, tcx: TyCtxt<'tcx>) -> Span {
 206         if let Some(path_expr_id) = self.info.path_expr_id {
 207             tcx.hir().span(path_expr_id)
 208         } else if let Some(capture_kind_expr_id) = self.info.capture_kind_expr_id {
 209             tcx.hir().span(capture_kind_expr_id)
 210         } else {
 211             // Fallback on upvars mentioned if neither path or capture expr id is captured
 212
 213             // Safe to unwrap since we know this place is captured by the closure, therefore the closure must have upvars.
 214             tcx.upvars_mentioned(self.get_closure_local_def_id()).unwrap()
 215                 [&self.get_root_variable()]
 216                 .span
 217         }
 218     }
 219
 220     /// Return span pointing to use that resulted in selecting the current capture kind
 221     pub fn get_capture_kind_span(&self, tcx: TyCtxt<'tcx>) -> Span {
 222         if let Some(capture_kind_expr_id) = self.info.capture_kind_expr_id {
 223             tcx.hir().span(capture_kind_expr_id)
 224         } else if let Some(path_expr_id) = self.info.path_expr_id {
 225             tcx.hir().span(path_expr_id)
 226         } else {
 227             // Fallback on upvars mentioned if neither path or capture expr id is captured
 228
 229             // Safe to unwrap since we know this place is captured by the closure, therefore the closure must have upvars.
 230             tcx.upvars_mentioned(self.get_closure_local_def_id()).unwrap()
 231                 [&self.get_root_variable()]
 232                 .span
 233         }
 234     }
 235 }
 236
 237 fn symbols_for_closure_captures<'tcx>(
 238     tcx: TyCtxt<'tcx>,
 239     def_id: (LocalDefId, DefId),
 240 ) -> Vec<Symbol> {
 241     let typeck_results = tcx.typeck(def_id.0);
 242     let captures = typeck_results.closure_min_captures_flattened(def_id.1);
 243     captures.into_iter().map(|captured_place| captured_place.to_symbol(tcx)).collect()
 244 }
 245
 246 /// Return true if the `proj_possible_ancestor` represents an ancestor path
 247 /// to `proj_capture` or `proj_possible_ancestor` is same as `proj_capture`,
 248 /// assuming they both start off of the same root variable.
 249 ///
 250 /// **Note:** It's the caller's responsibility to ensure that both lists of projections
 251 ///           start off of the same root variable.
 252 ///
 253 /// Eg: 1. `foo.x` which is represented using `projections=[Field(x)]` is an ancestor of
 254 ///        `foo.x.y` which is represented using `projections=[Field(x), Field(y)]`.
 255 ///        Note both `foo.x` and `foo.x.y` start off of the same root variable `foo`.
 256 ///     2. Since we only look at the projections here function will return `bar.x` as an a valid
 257 ///        ancestor of `foo.x.y`. It's the caller's responsibility to ensure that both projections
 258 ///        list are being applied to the same root variable.
 259 pub fn is_ancestor_or_same_capture(
 260     proj_possible_ancestor: &[HirProjectionKind],
 261     proj_capture: &[HirProjectionKind],
 262 ) -> bool {
 263     // We want to make sure `is_ancestor_or_same_capture("x.0.0", "x.0")` to return false.
 264     // Therefore we can't just check if all projections are same in the zipped iterator below.
 265     if proj_possible_ancestor.len() > proj_capture.len() {
 266         return false;
 267     }
 268
 269     proj_possible_ancestor.iter().zip(proj_capture).all(|(a, b)| a == b)
 270 }
 271
 272 /// Part of `MinCaptureInformationMap`; describes the capture kind (&, &mut, move)
 273 /// for a particular capture as well as identifying the part of the source code
 274 /// that triggered this capture to occur.
 275 #[derive(PartialEq, Clone, Debug, Copy, TyEncodable, TyDecodable, TypeFoldable, HashStable)]
 276 pub struct CaptureInfo {
 277     /// Expr Id pointing to use that resulted in selecting the current capture kind
 278     ///
 279     /// Eg:
 280     /// ```rust,no_run
 281     /// let mut t = (0,1);
 282     ///
 283     /// let c = || {
 284     ///     println!("{}",t); // L1
 285     ///     t.1 = 4; // L2
 286     /// };
 287     /// ```
 288     /// `capture_kind_expr_id` will point to the use on L2 and `path_expr_id` will point to the
 289     /// use on L1.
 290     ///
 291     /// If the user doesn't enable feature `capture_disjoint_fields` (RFC 2229) then, it is
 292     /// possible that we don't see the use of a particular place resulting in capture_kind_expr_id being
 293     /// None. In such case we fallback on uvpars_mentioned for span.
 294     ///
 295     /// Eg:
 296     /// ```rust,no_run
 297     /// let x = 5;
 298     ///
 299     /// let c = || {
 300     ///     let _ = x
 301     /// };
 302     /// ```
 303     ///
 304     /// In this example, if `capture_disjoint_fields` is **not** set, then x will be captured,
 305     /// but we won't see it being used during capture analysis, since it's essentially a discard.
 306     pub capture_kind_expr_id: Option<hir::HirId>,
 307     /// Expr Id pointing to use that resulted the corresponding place being captured
 308     ///
 309     /// See `capture_kind_expr_id` for example.
 310     ///
 311     pub path_expr_id: Option<hir::HirId>,
 312
 313     /// Capture mode that was selected
 314     pub capture_kind: UpvarCapture,
 315 }
 316
 317 pub fn place_to_string_for_capture<'tcx>(tcx: TyCtxt<'tcx>, place: &HirPlace<'tcx>) -> String {
 318     let mut curr_string: String = match place.base {
 319         HirPlaceBase::Upvar(upvar_id) => tcx.hir().name(upvar_id.var_path.hir_id).to_string(),
 320         _ => bug!("Capture_information should only contain upvars"),
 321     };
 322
 323     for (i, proj) in place.projections.iter().enumerate() {
 324         match proj.kind {
 325             HirProjectionKind::Deref => {
 326                 curr_string = format!("*{}", curr_string);
 327             }
 328             HirProjectionKind::Field(idx, variant) => match place.ty_before_projection(i).kind() {
 329                 ty::Adt(def, ..) => {
 330                     curr_string = format!(
 331                         "{}.{}",
 332                         curr_string,
 333                         def.variants[variant].fields[idx as usize].name.as_str()
 334                     );
 335                 }
 336                 ty::Tuple(_) => {
 337                     curr_string = format!("{}.{}", curr_string, idx);
 338                 }
 339                 _ => {
 340                     bug!(
 341                         "Field projection applied to a type other than Adt or Tuple: {:?}.",
 342                         place.ty_before_projection(i).kind()
 343                     )
 344                 }
 345             },
 346             proj => bug!("{:?} unexpected because it isn't captured", proj),
 347         }
 348     }
 349
 350     curr_string
 351 }
 352
 353 #[derive(Clone, PartialEq, Debug, TyEncodable, TyDecodable, TypeFoldable, Copy, HashStable)]
 354 pub enum BorrowKind {
 355     /// Data must be immutable and is aliasable.
 356     ImmBorrow,
 357
 358     /// Data must be immutable but not aliasable. This kind of borrow
 359     /// cannot currently be expressed by the user and is used only in
 360     /// implicit closure bindings. It is needed when the closure
 361     /// is borrowing or mutating a mutable referent, e.g.:
 362     ///
 363     /// ```
 364     /// let x: &mut isize = ...;
 365     /// let y = || *x += 5;
 366     /// ```
 367     ///
 368     /// If we were to try to translate this closure into a more explicit
 369     /// form, we'd encounter an error with the code as written:
 370     ///
 371     /// ```
 372     /// struct Env { x: & &mut isize }
 373     /// let x: &mut isize = ...;
 374     /// let y = (&mut Env { &x }, fn_ptr);  // Closure is pair of env and fn
 375     /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
 376     /// ```
 377     ///
 378     /// This is then illegal because you cannot mutate a `&mut` found
 379     /// in an aliasable location. To solve, you'd have to translate with
 380     /// an `&mut` borrow:
 381     ///
 382     /// ```
 383     /// struct Env { x: &mut &mut isize }
 384     /// let x: &mut isize = ...;
 385     /// let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
 386     /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
 387     /// ```
 388     ///
 389     /// Now the assignment to `**env.x` is legal, but creating a
 390     /// mutable pointer to `x` is not because `x` is not mutable. We
 391     /// could fix this by declaring `x` as `let mut x`. This is ok in
 392     /// user code, if awkward, but extra weird for closures, since the
 393     /// borrow is hidden.
 394     ///
 395     /// So we introduce a "unique imm" borrow -- the referent is
 396     /// immutable, but not aliasable. This solves the problem. For
 397     /// simplicity, we don't give users the way to express this
 398     /// borrow, it's just used when translating closures.
 399     UniqueImmBorrow,
 400
 401     /// Data is mutable and not aliasable.
 402     MutBorrow,
 403 }
 404
 405 impl BorrowKind {
 406     pub fn from_mutbl(m: hir::Mutability) -> BorrowKind {
 407         match m {
 408             hir::Mutability::Mut => MutBorrow,
 409             hir::Mutability::Not => ImmBorrow,
 410         }
 411     }
 412
 413     /// Returns a mutability `m` such that an `&m T` pointer could be used to obtain this borrow
 414     /// kind. Because borrow kinds are richer than mutabilities, we sometimes have to pick a
 415     /// mutability that is stronger than necessary so that it at least *would permit* the borrow in
 416     /// question.
 417     pub fn to_mutbl_lossy(self) -> hir::Mutability {
 418         match self {
 419             MutBorrow => hir::Mutability::Mut,
 420             ImmBorrow => hir::Mutability::Not,
 421
 422             // We have no type corresponding to a unique imm borrow, so
 423             // use `&mut`. It gives all the capabilities of a `&uniq`
 424             // and hence is a safe "over approximation".
 425             UniqueImmBorrow => hir::Mutability::Mut,
 426         }
 427     }
 428 }
 429
 430 pub fn provide(providers: &mut ty::query::Providers) {
 431     *providers = ty::query::Providers { symbols_for_closure_captures, ..*providers }
 432 }