src/librustc/middle/kind.rs

   1 // Copyright 2012-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
  12 use middle::freevars::freevar_entry;
  13 use middle::freevars;
  14 use middle::ty;
  15 use middle::typeck;
  16 use util::ppaux::{Repr, ty_to_str};
  17 use util::ppaux::UserString;
  18
  19 use syntax::ast::*;
  20 use syntax::attr;
  21 use syntax::codemap::Span;
  22 use syntax::owned_slice::OwnedSlice;
  23 use syntax::print::pprust::{expr_to_str,path_to_str};
  24 use syntax::{visit,ast_util};
  25 use syntax::visit::Visitor;
  26
  27 // Kind analysis pass.
  28 //
  29 // There are several kinds defined by various operations. The most restrictive
  30 // kind is noncopyable. The noncopyable kind can be extended with any number
  31 // of the following attributes.
  32 //
  33 //  Send: Things that can be sent on channels or included in spawned closures. It
  34 //  includes scalar types as well as classes and unique types containing only
  35 //  sendable types.
  36 //  'static: Things that do not contain references.
  37 //
  38 // This pass ensures that type parameters are only instantiated with types
  39 // whose kinds are equal or less general than the way the type parameter was
  40 // annotated (with the `Send` bound).
  41 //
  42 // It also verifies that noncopyable kinds are not copied. Sendability is not
  43 // applied, since none of our language primitives send. Instead, the sending
  44 // primitives in the stdlib are explicitly annotated to only take sendable
  45 // types.
  46
  47 #[deriving(Clone)]
  48 pub struct Context<'a> {
  49     tcx: &'a ty::ctxt,
  50 }
  51
  52 impl<'a> Visitor<()> for Context<'a> {
  53
  54     fn visit_expr(&mut self, ex: &Expr, _: ()) {
  55         check_expr(self, ex);
  56     }
  57
  58     fn visit_fn(&mut self, fk: &visit::FnKind, fd: &FnDecl,
  59                 b: &Block, s: Span, n: NodeId, _: ()) {
  60         check_fn(self, fk, fd, b, s, n);
  61     }
  62
  63     fn visit_ty(&mut self, t: &Ty, _: ()) {
  64         check_ty(self, t);
  65     }
  66
  67     fn visit_item(&mut self, i: &Item, _: ()) {
  68         check_item(self, i);
  69     }
  70
  71     fn visit_pat(&mut self, p: &Pat, _: ()) {
  72         check_pat(self, p);
  73     }
  74 }
  75
  76 pub fn check_crate(tcx: &ty::ctxt,
  77                    krate: &Crate) {
  78     let mut ctx = Context {
  79         tcx: tcx,
  80     };
  81     visit::walk_crate(&mut ctx, krate, ());
  82     tcx.sess.abort_if_errors();
  83 }
  84
  85 fn check_struct_safe_for_destructor(cx: &mut Context,
  86                                     span: Span,
  87                                     struct_did: DefId) {
  88     let struct_tpt = ty::lookup_item_type(cx.tcx, struct_did);
  89     if !struct_tpt.generics.has_type_params() {
  90         let struct_ty = ty::mk_struct(cx.tcx, struct_did, ty::substs {
  91             regions: ty::NonerasedRegions(OwnedSlice::empty()),
  92             self_ty: None,
  93             tps: Vec::new()
  94         });
  95         if !ty::type_is_sendable(cx.tcx, struct_ty) {
  96             cx.tcx.sess.span_err(span,
  97                                  "cannot implement a destructor on a \
  98                                   structure that does not satisfy Send");
  99             cx.tcx.sess.span_note(span,
 100                                   "use \"#[unsafe_destructor]\" on the \
 101                                    implementation to force the compiler to \
 102                                    allow this");
 103         }
 104     } else {
 105         cx.tcx.sess.span_err(span,
 106                              "cannot implement a destructor on a structure \
 107                               with type parameters");
 108         cx.tcx.sess.span_note(span,
 109                               "use \"#[unsafe_destructor]\" on the \
 110                                implementation to force the compiler to \
 111                                allow this");
 112     }
 113 }
 114
 115 fn check_impl_of_trait(cx: &mut Context, it: &Item, trait_ref: &TraitRef, self_type: &Ty) {
 116     let ast_trait_def = *cx.tcx.def_map.borrow()
 117                               .find(&trait_ref.ref_id)
 118                               .expect("trait ref not in def map!");
 119     let trait_def_id = ast_util::def_id_of_def(ast_trait_def);
 120     let trait_def = cx.tcx.trait_defs.borrow()
 121                           .find_copy(&trait_def_id)
 122                           .expect("trait def not in trait-defs map!");
 123
 124     // If this trait has builtin-kind supertraits, meet them.
 125     let self_ty: ty::t = ty::node_id_to_type(cx.tcx, it.id);
 126     debug!("checking impl with self type {:?}", ty::get(self_ty).sty);
 127     check_builtin_bounds(cx, self_ty, trait_def.bounds, |missing| {
 128         cx.tcx.sess.span_err(self_type.span,
 129             format!("the type `{}', which does not fulfill `{}`, cannot implement this \
 130                   trait", ty_to_str(cx.tcx, self_ty), missing.user_string(cx.tcx)));
 131         cx.tcx.sess.span_note(self_type.span,
 132             format!("types implementing this trait must fulfill `{}`",
 133                  trait_def.bounds.user_string(cx.tcx)));
 134     });
 135
 136     // If this is a destructor, check kinds.
 137     if cx.tcx.lang_items.drop_trait() == Some(trait_def_id) {
 138         match self_type.node {
 139             TyPath(_, ref bounds, path_node_id) => {
 140                 assert!(bounds.is_none());
 141                 let struct_def = cx.tcx.def_map.borrow().get_copy(&path_node_id);
 142                 let struct_did = ast_util::def_id_of_def(struct_def);
 143                 check_struct_safe_for_destructor(cx, self_type.span, struct_did);
 144             }
 145             _ => {
 146                 cx.tcx.sess.span_bug(self_type.span,
 147                     "the self type for the Drop trait impl is not a path");
 148             }
 149         }
 150     }
 151 }
 152
 153 fn check_item(cx: &mut Context, item: &Item) {
 154     if !attr::contains_name(item.attrs.as_slice(), "unsafe_destructor") {
 155         match item.node {
 156             ItemImpl(_, Some(ref trait_ref), self_type, _) => {
 157                 check_impl_of_trait(cx, item, trait_ref, self_type);
 158             }
 159             _ => {}
 160         }
 161     }
 162
 163     visit::walk_item(cx, item, ());
 164 }
 165
 166 // Yields the appropriate function to check the kind of closed over
 167 // variables. `id` is the NodeId for some expression that creates the
 168 // closure.
 169 fn with_appropriate_checker(cx: &Context,
 170                             id: NodeId,
 171                             b: |checker: |&Context, &freevar_entry||) {
 172     fn check_for_uniq(cx: &Context, fv: &freevar_entry, bounds: ty::BuiltinBounds) {
 173         // all captured data must be owned, regardless of whether it is
 174         // moved in or copied in.
 175         let id = ast_util::def_id_of_def(fv.def).node;
 176         let var_t = ty::node_id_to_type(cx.tcx, id);
 177
 178         check_freevar_bounds(cx, fv.span, var_t, bounds, None);
 179     }
 180
 181     fn check_for_block(cx: &Context, fv: &freevar_entry,
 182                        bounds: ty::BuiltinBounds, region: ty::Region) {
 183         let id = ast_util::def_id_of_def(fv.def).node;
 184         let var_t = ty::node_id_to_type(cx.tcx, id);
 185         // FIXME(#3569): Figure out whether the implicit borrow is actually
 186         // mutable. Currently we assume all upvars are referenced mutably.
 187         let implicit_borrowed_type = ty::mk_mut_rptr(cx.tcx, region, var_t);
 188         check_freevar_bounds(cx, fv.span, implicit_borrowed_type,
 189                              bounds, Some(var_t));
 190     }
 191
 192     fn check_for_bare(cx: &Context, fv: &freevar_entry) {
 193         cx.tcx.sess.span_err(
 194             fv.span,
 195             "can't capture dynamic environment in a fn item; \
 196             use the || { ... } closure form instead");
 197     } // same check is done in resolve.rs, but shouldn't be done
 198
 199     let fty = ty::node_id_to_type(cx.tcx, id);
 200     match ty::get(fty).sty {
 201         ty::ty_closure(~ty::ClosureTy {
 202             store: ty::UniqTraitStore, bounds, ..
 203         }) => b(|cx, fv| check_for_uniq(cx, fv, bounds)),
 204
 205         ty::ty_closure(~ty::ClosureTy {
 206             store: ty::RegionTraitStore(region, _), bounds, ..
 207         }) => b(|cx, fv| check_for_block(cx, fv, bounds, region)),
 208
 209         ty::ty_bare_fn(_) => {
 210             b(check_for_bare)
 211         }
 212         ref s => {
 213             cx.tcx.sess.bug(
 214                 format!("expect fn type in kind checker, not {:?}", s));
 215         }
 216     }
 217 }
 218
 219 // Check that the free variables used in a shared/sendable closure conform
 220 // to the copy/move kind bounds. Then recursively check the function body.
 221 fn check_fn(
 222     cx: &mut Context,
 223     fk: &visit::FnKind,
 224     decl: &FnDecl,
 225     body: &Block,
 226     sp: Span,
 227     fn_id: NodeId) {
 228
 229     // Check kinds on free variables:
 230     with_appropriate_checker(cx, fn_id, |chk| {
 231         freevars::with_freevars(cx.tcx, fn_id, |r| {
 232             for fv in r.iter() {
 233                 chk(cx, fv);
 234             }
 235         })
 236     });
 237
 238     visit::walk_fn(cx, fk, decl, body, sp, fn_id, ());
 239 }
 240
 241 pub fn check_expr(cx: &mut Context, e: &Expr) {
 242     debug!("kind::check_expr({})", expr_to_str(e));
 243
 244     // Handle any kind bounds on type parameters
 245     {
 246         let method_map = cx.tcx.method_map.borrow();
 247         let method = method_map.find(&typeck::MethodCall::expr(e.id));
 248         let node_type_substs = cx.tcx.node_type_substs.borrow();
 249         let r = match method {
 250             Some(method) => Some(&method.substs.tps),
 251             None => node_type_substs.find(&e.id)
 252         };
 253         for ts in r.iter() {
 254             let def_map = cx.tcx.def_map.borrow();
 255             let type_param_defs = match e.node {
 256               ExprPath(_) => {
 257                 let did = ast_util::def_id_of_def(def_map.get_copy(&e.id));
 258                 ty::lookup_item_type(cx.tcx, did).generics.type_param_defs.clone()
 259               }
 260               _ => {
 261                 // Type substitutions should only occur on paths and
 262                 // method calls, so this needs to be a method call.
 263
 264                 // Even though the callee_id may have been the id with
 265                 // node_type_substs, e.id is correct here.
 266                 match method {
 267                     Some(method) => {
 268                         ty::method_call_type_param_defs(cx.tcx, method.origin)
 269                     }
 270                     None => {
 271                         cx.tcx.sess.span_bug(e.span,
 272                             "non path/method call expr has type substs??");
 273                     }
 274                 }
 275               }
 276             };
 277             if ts.len() != type_param_defs.len() {
 278                 // Fail earlier to make debugging easier
 279                 fail!("internal error: in kind::check_expr, length \
 280                       mismatch between actual and declared bounds: actual = \
 281                       {}, declared = {}",
 282                       ts.repr(cx.tcx),
 283                       type_param_defs.repr(cx.tcx));
 284             }
 285             for (&ty, type_param_def) in ts.iter().zip(type_param_defs.iter()) {
 286                 check_typaram_bounds(cx, e.span, ty, type_param_def)
 287             }
 288         }
 289     }
 290
 291     match e.node {
 292         ExprUnary(UnBox, interior) => {
 293             let interior_type = ty::expr_ty(cx.tcx, interior);
 294             let _ = check_static(cx.tcx, interior_type, interior.span);
 295         }
 296         ExprCast(source, _) => {
 297             let source_ty = ty::expr_ty(cx.tcx, source);
 298             let target_ty = ty::expr_ty(cx.tcx, e);
 299             check_trait_cast(cx, source_ty, target_ty, source.span);
 300         }
 301         ExprRepeat(element, count_expr) => {
 302             let count = ty::eval_repeat_count(cx.tcx, count_expr);
 303             if count > 1 {
 304                 let element_ty = ty::expr_ty(cx.tcx, element);
 305                 check_copy(cx, element_ty, element.span,
 306                            "repeated element will be copied");
 307             }
 308         }
 309         _ => {}
 310     }
 311
 312     // Search for auto-adjustments to find trait coercions.
 313     match cx.tcx.adjustments.borrow().find(&e.id) {
 314         Some(adjustment) => {
 315             match *adjustment {
 316                 ty::AutoObject(..) => {
 317                     let source_ty = ty::expr_ty(cx.tcx, e);
 318                     let target_ty = ty::expr_ty_adjusted(cx.tcx, e);
 319                     check_trait_cast(cx, source_ty, target_ty, e.span);
 320                 }
 321                 ty::AutoAddEnv(..) |
 322                 ty::AutoDerefRef(..) => {}
 323             }
 324         }
 325         None => {}
 326     }
 327
 328     visit::walk_expr(cx, e, ());
 329 }
 330
 331 fn check_trait_cast(cx: &mut Context, source_ty: ty::t, target_ty: ty::t, span: Span) {
 332     check_cast_for_escaping_regions(cx, source_ty, target_ty, span);
 333     match ty::get(target_ty).sty {
 334         ty::ty_trait(~ty::TyTrait { bounds, .. }) => {
 335             check_trait_cast_bounds(cx, span, source_ty, bounds);
 336         }
 337         _ => {}
 338     }
 339 }
 340
 341 fn check_ty(cx: &mut Context, aty: &Ty) {
 342     match aty.node {
 343         TyPath(_, _, id) => {
 344             let node_type_substs = cx.tcx.node_type_substs.borrow();
 345             let r = node_type_substs.find(&id);
 346             for ts in r.iter() {
 347                 let def_map = cx.tcx.def_map.borrow();
 348                 let did = ast_util::def_id_of_def(def_map.get_copy(&id));
 349                 let generics = ty::lookup_item_type(cx.tcx, did).generics;
 350                 let type_param_defs = generics.type_param_defs();
 351                 for (&ty, type_param_def) in ts.iter().zip(type_param_defs.iter()) {
 352                     check_typaram_bounds(cx, aty.span, ty, type_param_def)
 353                 }
 354             }
 355         }
 356         _ => {}
 357     }
 358     visit::walk_ty(cx, aty, ());
 359 }
 360
 361 // Calls "any_missing" if any bounds were missing.
 362 pub fn check_builtin_bounds(cx: &Context,
 363                             ty: ty::t,
 364                             bounds: ty::BuiltinBounds,
 365                             any_missing: |ty::BuiltinBounds|) {
 366     let kind = ty::type_contents(cx.tcx, ty);
 367     let mut missing = ty::EmptyBuiltinBounds();
 368     for bound in bounds.iter() {
 369         if !kind.meets_bound(cx.tcx, bound) {
 370             missing.add(bound);
 371         }
 372     }
 373     if !missing.is_empty() {
 374         any_missing(missing);
 375     }
 376 }
 377
 378 pub fn check_typaram_bounds(cx: &Context,
 379                             sp: Span,
 380                             ty: ty::t,
 381                             type_param_def: &ty::TypeParameterDef) {
 382     check_builtin_bounds(cx,
 383                          ty,
 384                          type_param_def.bounds.builtin_bounds,
 385                          |missing| {
 386         cx.tcx.sess.span_err(
 387             sp,
 388             format!("instantiating a type parameter with an incompatible type \
 389                   `{}`, which does not fulfill `{}`",
 390                  ty_to_str(cx.tcx, ty),
 391                  missing.user_string(cx.tcx)));
 392     });
 393 }
 394
 395 pub fn check_freevar_bounds(cx: &Context, sp: Span, ty: ty::t,
 396                             bounds: ty::BuiltinBounds, referenced_ty: Option<ty::t>)
 397 {
 398     check_builtin_bounds(cx, ty, bounds, |missing| {
 399         // Will be Some if the freevar is implicitly borrowed (stack closure).
 400         // Emit a less mysterious error message in this case.
 401         match referenced_ty {
 402             Some(rty) => cx.tcx.sess.span_err(sp,
 403                 format!("cannot implicitly borrow variable of type `{}` in a bounded \
 404                       stack closure (implicit reference does not fulfill `{}`)",
 405                      ty_to_str(cx.tcx, rty), missing.user_string(cx.tcx))),
 406             None => cx.tcx.sess.span_err(sp,
 407                 format!("cannot capture variable of type `{}`, which does \
 408                       not fulfill `{}`, in a bounded closure",
 409                      ty_to_str(cx.tcx, ty), missing.user_string(cx.tcx))),
 410         }
 411         cx.tcx.sess.span_note(
 412             sp,
 413             format!("this closure's environment must satisfy `{}`",
 414                  bounds.user_string(cx.tcx)));
 415     });
 416 }
 417
 418 pub fn check_trait_cast_bounds(cx: &Context, sp: Span, ty: ty::t,
 419                                bounds: ty::BuiltinBounds) {
 420     check_builtin_bounds(cx, ty, bounds, |missing| {
 421         cx.tcx.sess.span_err(sp,
 422             format!("cannot pack type `{}`, which does not fulfill \
 423                   `{}`, as a trait bounded by {}",
 424                  ty_to_str(cx.tcx, ty), missing.user_string(cx.tcx),
 425                  bounds.user_string(cx.tcx)));
 426     });
 427 }
 428
 429 fn check_copy(cx: &Context, ty: ty::t, sp: Span, reason: &str) {
 430     debug!("type_contents({})={}",
 431            ty_to_str(cx.tcx, ty),
 432            ty::type_contents(cx.tcx, ty).to_str());
 433     if ty::type_moves_by_default(cx.tcx, ty) {
 434         cx.tcx.sess.span_err(
 435             sp, format!("copying a value of non-copyable type `{}`",
 436                      ty_to_str(cx.tcx, ty)));
 437         cx.tcx.sess.span_note(sp, format!("{}", reason));
 438     }
 439 }
 440
 441 pub fn check_static(tcx: &ty::ctxt, ty: ty::t, sp: Span) -> bool {
 442     if !ty::type_is_static(tcx, ty) {
 443         match ty::get(ty).sty {
 444           ty::ty_param(..) => {
 445             tcx.sess.span_err(sp,
 446                 format!("value may contain references; \
 447                          add `'static` bound to `{}`", ty_to_str(tcx, ty)));
 448           }
 449           _ => {
 450             tcx.sess.span_err(sp, "value may contain references");
 451           }
 452         }
 453         false
 454     } else {
 455         true
 456     }
 457 }
 458
 459 /// This is rather subtle.  When we are casting a value to an instantiated
 460 /// trait like `a as trait<'r>`, regionck already ensures that any references
 461 /// that appear in the type of `a` are bounded by `'r` (ed.: rem
 462 /// FIXME(#5723)).  However, it is possible that there are *type parameters*
 463 /// in the type of `a`, and those *type parameters* may have references
 464 /// within them.  We have to guarantee that the regions which appear in those
 465 /// type parameters are not obscured.
 466 ///
 467 /// Therefore, we ensure that one of three conditions holds:
 468 ///
 469 /// (1) The trait instance cannot escape the current fn.  This is
 470 /// guaranteed if the region bound `&r` is some scope within the fn
 471 /// itself.  This case is safe because whatever references are
 472 /// found within the type parameter, they must enclose the fn body
 473 /// itself.
 474 ///
 475 /// (2) The type parameter appears in the type of the trait.  For
 476 /// example, if the type parameter is `T` and the trait type is
 477 /// `deque<T>`, then whatever references may appear in `T` also
 478 /// appear in `deque<T>`.
 479 ///
 480 /// (3) The type parameter is sendable (and therefore does not contain
 481 /// references).
 482 ///
 483 /// FIXME(#5723)---This code should probably move into regionck.
 484 pub fn check_cast_for_escaping_regions(
 485     cx: &Context,
 486     source_ty: ty::t,
 487     target_ty: ty::t,
 488     source_span: Span)
 489 {
 490     // Determine what type we are casting to; if it is not a trait, then no
 491     // worries.
 492     match ty::get(target_ty).sty {
 493         ty::ty_trait(..) => {}
 494         _ => { return; }
 495     }
 496
 497     // Collect up the regions that appear in the target type.  We want to
 498     // ensure that these lifetimes are shorter than all lifetimes that are in
 499     // the source type.  See test `src/test/compile-fail/regions-trait-2.rs`
 500     let mut target_regions = Vec::new();
 501     ty::walk_regions_and_ty(
 502         cx.tcx,
 503         target_ty,
 504         |r| {
 505             if !r.is_bound() {
 506                 target_regions.push(r);
 507             }
 508         },
 509         |_| ());
 510
 511     // Check, based on the region associated with the trait, whether it can
 512     // possibly escape the enclosing fn item (note that all type parameters
 513     // must have been declared on the enclosing fn item).
 514     if target_regions.iter().any(|r| is_ReScope(*r)) {
 515         return; /* case (1) */
 516     }
 517
 518     // Assuming the trait instance can escape, then ensure that each parameter
 519     // either appears in the trait type or is sendable.
 520     let target_params = ty::param_tys_in_type(target_ty);
 521     ty::walk_regions_and_ty(
 522         cx.tcx,
 523         source_ty,
 524
 525         |_r| {
 526             // FIXME(#5723) --- turn this check on once &Objects are usable
 527             //
 528             // if !target_regions.iter().any(|t_r| is_subregion_of(cx, *t_r, r)) {
 529             //     cx.tcx.sess.span_err(
 530             //         source_span,
 531             //         format!("source contains reference with lifetime \
 532             //               not found in the target type `{}`",
 533             //              ty_to_str(cx.tcx, target_ty)));
 534             //     note_and_explain_region(
 535             //         cx.tcx, "source data is only valid for ", r, "");
 536             // }
 537         },
 538
 539         |ty| {
 540             match ty::get(ty).sty {
 541                 ty::ty_param(source_param) => {
 542                     if target_params.iter().any(|x| x == &source_param) {
 543                         /* case (2) */
 544                     } else {
 545                         check_static(cx.tcx, ty, source_span); /* case (3) */
 546                     }
 547                 }
 548                 _ => {}
 549             }
 550         });
 551
 552     fn is_ReScope(r: ty::Region) -> bool {
 553         match r {
 554             ty::ReScope(..) => true,
 555             _ => false
 556         }
 557     }
 558 }
 559
 560 // Ensure that `ty` has a statically known size (i.e., it has the `Sized` bound).
 561 fn check_sized(tcx: &ty::ctxt, ty: ty::t, name: ~str, sp: Span) {
 562     if !ty::type_is_sized(tcx, ty) {
 563         tcx.sess.span_err(sp, format!("variable `{}` has dynamically sized type `{}`",
 564                                       name, ty_to_str(tcx, ty)));
 565     }
 566 }
 567
 568 // Check that any variables in a pattern have types with statically known size.
 569 fn check_pat(cx: &mut Context, pat: &Pat) {
 570     let var_name = match pat.node {
 571         PatWild => Some("_".to_owned()),
 572         PatIdent(_, ref path, _) => Some(path_to_str(path)),
 573         _ => None
 574     };
 575
 576     match var_name {
 577         Some(name) => {
 578             let types = cx.tcx.node_types.borrow();
 579             let ty = types.find(&(pat.id as uint));
 580             match ty {
 581                 Some(ty) => {
 582                     debug!("kind: checking sized-ness of variable {}: {}",
 583                            name, ty_to_str(cx.tcx, *ty));
 584                     check_sized(cx.tcx, *ty, name, pat.span);
 585                 }
 586                 None => {} // extern fn args
 587             }
 588         }
 589         None => {}
 590     }
 591
 592     visit::walk_pat(cx, pat, ());
 593 }