src/librustc/middle/kind.rs

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