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