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::{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 borrowed pointers.
  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::method_map,
  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::fn_kind, fd:&fn_decl, b:&Block, s:Span, n:NodeId, _:()) {
  66         check_fn(self, fk, fd, b, s, n);
  67     }
  68
  69     fn visit_ty(&mut self, t:&Ty, _:()) {
  70         check_ty(self, t);
  71     }
  72     fn visit_item(&mut self, i:@item, _:()) {
  73         check_item(self, i);
  74     }
  75 }
  76
  77 pub fn check_crate(tcx: ty::ctxt,
  78                    method_map: typeck::method_map,
  79                    crate: &Crate) {
  80     let mut ctx = Context {
  81         tcx: tcx,
  82         method_map: method_map,
  83     };
  84     visit::walk_crate(&mut ctx, crate, ());
  85     tcx.sess.abort_if_errors();
  86 }
  87
  88 fn check_struct_safe_for_destructor(cx: &mut Context,
  89                                     span: Span,
  90                                     struct_did: DefId) {
  91     let struct_tpt = ty::lookup_item_type(cx.tcx, struct_did);
  92     if !struct_tpt.generics.has_type_params() {
  93         let struct_ty = ty::mk_struct(cx.tcx, struct_did, ty::substs {
  94             regions: ty::NonerasedRegions(opt_vec::Empty),
  95             self_ty: None,
  96             tps: ~[]
  97         });
  98         if !ty::type_is_sendable(cx.tcx, struct_ty) {
  99             cx.tcx.sess.span_err(span,
 100                                  "cannot implement a destructor on a \
 101                                   structure that does not satisfy Send");
 102             cx.tcx.sess.span_note(span,
 103                                   "use \"#[unsafe_destructor]\" on the \
 104                                    implementation to force the compiler to \
 105                                    allow this");
 106         }
 107     } else {
 108         cx.tcx.sess.span_err(span,
 109                              "cannot implement a destructor on a structure \
 110                               with type parameters");
 111         cx.tcx.sess.span_note(span,
 112                               "use \"#[unsafe_destructor]\" on the \
 113                                implementation to force the compiler to \
 114                                allow this");
 115     }
 116 }
 117
 118 fn check_impl_of_trait(cx: &mut Context, it: @item, trait_ref: &trait_ref, self_type: &Ty) {
 119     let ast_trait_def = cx.tcx.def_map.find(&trait_ref.ref_id)
 120                             .expect("trait ref not in def map!");
 121     let trait_def_id = ast_util::def_id_of_def(*ast_trait_def);
 122     let trait_def = cx.tcx.trait_defs.find(&trait_def_id)
 123                         .expect("trait def not in trait-defs map!");
 124
 125     // If this trait has builtin-kind supertraits, meet them.
 126     let self_ty: ty::t = ty::node_id_to_type(cx.tcx, it.id);
 127     debug!("checking impl with self type {:?}", ty::get(self_ty).sty);
 128     do check_builtin_bounds(cx, self_ty, trait_def.bounds) |missing| {
 129         cx.tcx.sess.span_err(self_type.span,
 130             format!("the type `{}', which does not fulfill `{}`, cannot implement this \
 131                   trait", ty_to_str(cx.tcx, self_ty), missing.user_string(cx.tcx)));
 132         cx.tcx.sess.span_note(self_type.span,
 133             format!("types implementing this trait must fulfill `{}`",
 134                  trait_def.bounds.user_string(cx.tcx)));
 135     }
 136
 137     // If this is a destructor, check kinds.
 138     if cx.tcx.lang_items.drop_trait() == Some(trait_def_id) {
 139         match self_type.node {
 140             ty_path(_, ref bounds, path_node_id) => {
 141                 assert!(bounds.is_none());
 142                 let struct_def = cx.tcx.def_map.get_copy(&path_node_id);
 143                 let struct_did = ast_util::def_id_of_def(struct_def);
 144                 check_struct_safe_for_destructor(cx, self_type.span, struct_did);
 145             }
 146             _ => {
 147                 cx.tcx.sess.span_bug(self_type.span,
 148                     "the self type for the Drop trait impl is not a path");
 149             }
 150         }
 151     }
 152 }
 153
 154 fn check_item(cx: &mut Context, item: @item) {
 155     if !attr::contains_name(item.attrs, "unsafe_destructor") {
 156         match item.node {
 157             item_impl(_, Some(ref trait_ref), ref self_type, _) => {
 158                 check_impl_of_trait(cx, item, trait_ref, self_type);
 159             }
 160             _ => {}
 161         }
 162     }
 163
 164     visit::walk_item(cx, item, ());
 165 }
 166
 167 // Yields the appropriate function to check the kind of closed over
 168 // variables. `id` is the NodeId for some expression that creates the
 169 // closure.
 170 fn with_appropriate_checker(cx: &Context, id: NodeId,
 171                             b: &fn(checker: &fn(&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 that only immutable variables are implicitly copied in
 179         check_imm_free_var(cx, fv.def, fv.span);
 180
 181         check_freevar_bounds(cx, fv.span, var_t, bounds, None);
 182     }
 183
 184     fn check_for_box(cx: &Context, fv: &freevar_entry, bounds: ty::BuiltinBounds) {
 185         // all captured data must be owned
 186         let id = ast_util::def_id_of_def(fv.def).node;
 187         let var_t = ty::node_id_to_type(cx.tcx, id);
 188
 189         // check that only immutable variables are implicitly copied in
 190         check_imm_free_var(cx, fv.def, fv.span);
 191
 192         check_freevar_bounds(cx, fv.span, var_t, bounds, None);
 193     }
 194
 195     fn check_for_block(cx: &Context, fv: &freevar_entry,
 196                        bounds: ty::BuiltinBounds, region: ty::Region) {
 197         let id = ast_util::def_id_of_def(fv.def).node;
 198         let var_t = ty::node_id_to_type(cx.tcx, id);
 199         // FIXME(#3569): Figure out whether the implicit borrow is actually
 200         // mutable. Currently we assume all upvars are referenced mutably.
 201         let implicit_borrowed_type = ty::mk_mut_rptr(cx.tcx, region, var_t);
 202         check_freevar_bounds(cx, fv.span, implicit_borrowed_type,
 203                              bounds, Some(var_t));
 204     }
 205
 206     fn check_for_bare(cx: &Context, fv: @freevar_entry) {
 207         cx.tcx.sess.span_err(
 208             fv.span,
 209             "can't capture dynamic environment in a fn item; \
 210             use the || { ... } closure form instead");
 211     } // same check is done in resolve.rs, but shouldn't be done
 212
 213     let fty = ty::node_id_to_type(cx.tcx, id);
 214     match ty::get(fty).sty {
 215         ty::ty_closure(ty::ClosureTy {
 216             sigil: OwnedSigil,
 217             bounds: bounds,
 218             _
 219         }) => {
 220             b(|cx, fv| check_for_uniq(cx, fv, bounds))
 221         }
 222         ty::ty_closure(ty::ClosureTy {
 223             sigil: ManagedSigil,
 224             _
 225         }) => {
 226             // can't happen
 227         }
 228         ty::ty_closure(ty::ClosureTy {
 229             sigil: BorrowedSigil,
 230             bounds: bounds,
 231             region: region,
 232             _
 233         }) => {
 234             b(|cx, fv| check_for_block(cx, fv, bounds, region))
 235         }
 236         ty::ty_bare_fn(_) => {
 237             b(check_for_bare)
 238         }
 239         ref s => {
 240             cx.tcx.sess.bug(
 241                 format!("expect fn type in kind checker, not {:?}", s));
 242         }
 243     }
 244 }
 245
 246 // Check that the free variables used in a shared/sendable closure conform
 247 // to the copy/move kind bounds. Then recursively check the function body.
 248 fn check_fn(
 249     cx: &mut Context,
 250     fk: &visit::fn_kind,
 251     decl: &fn_decl,
 252     body: &Block,
 253     sp: Span,
 254     fn_id: NodeId) {
 255
 256     // Check kinds on free variables:
 257     do with_appropriate_checker(cx, fn_id) |chk| {
 258         let r = freevars::get_freevars(cx.tcx, fn_id);
 259         for fv in r.iter() {
 260             chk(cx, *fv);
 261         }
 262     }
 263
 264     visit::walk_fn(cx, fk, decl, body, sp, fn_id, ());
 265 }
 266
 267 pub fn check_expr(cx: &mut Context, e: @Expr) {
 268     debug!("kind::check_expr({})", expr_to_str(e, cx.tcx.sess.intr()));
 269
 270     // Handle any kind bounds on type parameters
 271     let type_parameter_id = match e.get_callee_id() {
 272         Some(callee_id) => callee_id,
 273         None => e.id,
 274     };
 275     {
 276         let r = cx.tcx.node_type_substs.find(&type_parameter_id);
 277         for ts in r.iter() {
 278             let type_param_defs = match e.node {
 279               ExprPath(_) => {
 280                 let did = ast_util::def_id_of_def(cx.tcx.def_map.get_copy(&e.id));
 281                 ty::lookup_item_type(cx.tcx, did).generics.type_param_defs
 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                 ty::method_call_type_param_defs(cx.tcx, cx.method_map, e.id).expect(
 290                     "non path/method call expr has type substs??")
 291               }
 292             };
 293             if ts.len() != type_param_defs.len() {
 294                 // Fail earlier to make debugging easier
 295                 fail!("internal error: in kind::check_expr, length \
 296                       mismatch between actual and declared bounds: actual = \
 297                       {}, declared = {}",
 298                       ts.repr(cx.tcx),
 299                       type_param_defs.repr(cx.tcx));
 300             }
 301             for (&ty, type_param_def) in ts.iter().zip(type_param_defs.iter()) {
 302                 check_typaram_bounds(cx, type_parameter_id, e.span, ty, type_param_def)
 303             }
 304         }
 305     }
 306
 307     match e.node {
 308         ExprUnary(_, UnBox(_), interior) => {
 309             let interior_type = ty::expr_ty(cx.tcx, interior);
 310             let _ = check_durable(cx.tcx, interior_type, interior.span);
 311         }
 312         ExprCast(source, _) => {
 313             check_cast_for_escaping_regions(cx, source, e);
 314             match ty::get(ty::expr_ty(cx.tcx, e)).sty {
 315                 ty::ty_trait(_, _, _, _, bounds) => {
 316                     let source_ty = ty::expr_ty(cx.tcx, source);
 317                     check_trait_cast_bounds(cx, e.span, source_ty, bounds)
 318                 }
 319                 _ => { }
 320             }
 321         }
 322         ExprRepeat(element, count_expr, _) => {
 323             let count = ty::eval_repeat_count(&cx.tcx, count_expr);
 324             if count > 1 {
 325                 let element_ty = ty::expr_ty(cx.tcx, element);
 326                 check_copy(cx, element_ty, element.span,
 327                            "repeated element will be copied");
 328             }
 329         }
 330         _ => {}
 331     }
 332     visit::walk_expr(cx, e, ());
 333 }
 334
 335 fn check_ty(cx: &mut Context, aty: &Ty) {
 336     match aty.node {
 337       ty_path(_, _, id) => {
 338           let r = cx.tcx.node_type_substs.find(&id);
 339           for ts in r.iter() {
 340               let did = ast_util::def_id_of_def(cx.tcx.def_map.get_copy(&id));
 341               let type_param_defs =
 342                   ty::lookup_item_type(cx.tcx, did).generics.type_param_defs;
 343               for (&ty, type_param_def) in ts.iter().zip(type_param_defs.iter()) {
 344                   check_typaram_bounds(cx, aty.id, aty.span, ty, type_param_def)
 345               }
 346           }
 347       }
 348       _ => {}
 349     }
 350     visit::walk_ty(cx, aty, ());
 351 }
 352
 353 // Calls "any_missing" if any bounds were missing.
 354 pub fn check_builtin_bounds(cx: &Context, ty: ty::t, bounds: ty::BuiltinBounds,
 355                             any_missing: &fn(ty::BuiltinBounds))
 356 {
 357     let kind = ty::type_contents(cx.tcx, ty);
 358     let mut missing = ty::EmptyBuiltinBounds();
 359     for bound in bounds.iter() {
 360         if !kind.meets_bound(cx.tcx, bound) {
 361             missing.add(bound);
 362         }
 363     }
 364     if !missing.is_empty() {
 365         any_missing(missing);
 366     }
 367 }
 368
 369 pub fn check_typaram_bounds(cx: &Context,
 370                     _type_parameter_id: NodeId,
 371                     sp: Span,
 372                     ty: ty::t,
 373                     type_param_def: &ty::TypeParameterDef)
 374 {
 375     do check_builtin_bounds(cx, ty, type_param_def.bounds.builtin_bounds) |missing| {
 376         cx.tcx.sess.span_err(
 377             sp,
 378             format!("instantiating a type parameter with an incompatible type \
 379                   `{}`, which does not fulfill `{}`",
 380                  ty_to_str(cx.tcx, ty),
 381                  missing.user_string(cx.tcx)));
 382     }
 383 }
 384
 385 pub fn check_freevar_bounds(cx: &Context, sp: Span, ty: ty::t,
 386                             bounds: ty::BuiltinBounds, referenced_ty: Option<ty::t>)
 387 {
 388     do check_builtin_bounds(cx, ty, bounds) |missing| {
 389         // Will be Some if the freevar is implicitly borrowed (stack closure).
 390         // Emit a less mysterious error message in this case.
 391         match referenced_ty {
 392             Some(rty) => cx.tcx.sess.span_err(sp,
 393                 format!("cannot implicitly borrow variable of type `{}` in a bounded \
 394                       stack closure (implicit reference does not fulfill `{}`)",
 395                      ty_to_str(cx.tcx, rty), missing.user_string(cx.tcx))),
 396             None => cx.tcx.sess.span_err(sp,
 397                 format!("cannot capture variable of type `{}`, which does \
 398                       not fulfill `{}`, in a bounded closure",
 399                      ty_to_str(cx.tcx, ty), missing.user_string(cx.tcx))),
 400         }
 401         cx.tcx.sess.span_note(
 402             sp,
 403             format!("this closure's environment must satisfy `{}`",
 404                  bounds.user_string(cx.tcx)));
 405     }
 406 }
 407
 408 pub fn check_trait_cast_bounds(cx: &Context, sp: Span, ty: ty::t,
 409                                bounds: ty::BuiltinBounds) {
 410     do check_builtin_bounds(cx, ty, bounds) |missing| {
 411         cx.tcx.sess.span_err(sp,
 412             format!("cannot pack type `{}`, which does not fulfill \
 413                   `{}`, as a trait bounded by {}",
 414                  ty_to_str(cx.tcx, ty), missing.user_string(cx.tcx),
 415                  bounds.user_string(cx.tcx)));
 416     }
 417 }
 418
 419 fn is_nullary_variant(cx: &Context, ex: @Expr) -> bool {
 420     match ex.node {
 421       ExprPath(_) => {
 422         match cx.tcx.def_map.get_copy(&ex.id) {
 423           DefVariant(edid, vdid, _) => {
 424               ty::enum_variant_with_id(cx.tcx, edid, vdid).args.is_empty()
 425           }
 426           _ => false
 427         }
 428       }
 429       _ => false
 430     }
 431 }
 432
 433 fn check_imm_free_var(cx: &Context, def: Def, sp: Span) {
 434     match def {
 435         DefLocal(_, is_mutbl) => {
 436             if is_mutbl {
 437                 cx.tcx.sess.span_err(
 438                     sp,
 439                     "mutable variables cannot be implicitly captured");
 440             }
 441         }
 442         DefArg(*) => { /* ok */ }
 443         DefUpvar(_, def1, _, _) => { check_imm_free_var(cx, *def1, sp); }
 444         DefBinding(*) | DefSelf(*) => { /*ok*/ }
 445         _ => {
 446             cx.tcx.sess.span_bug(
 447                 sp,
 448                 format!("unknown def for free variable: {:?}", def));
 449         }
 450     }
 451 }
 452
 453 fn check_copy(cx: &Context, ty: ty::t, sp: Span, reason: &str) {
 454     debug!("type_contents({})={}",
 455            ty_to_str(cx.tcx, ty),
 456            ty::type_contents(cx.tcx, ty).to_str());
 457     if ty::type_moves_by_default(cx.tcx, ty) {
 458         cx.tcx.sess.span_err(
 459             sp, format!("copying a value of non-copyable type `{}`",
 460                      ty_to_str(cx.tcx, ty)));
 461         cx.tcx.sess.span_note(sp, format!("{}", reason));
 462     }
 463 }
 464
 465 pub fn check_send(cx: &Context, ty: ty::t, sp: Span) -> bool {
 466     if !ty::type_is_sendable(cx.tcx, ty) {
 467         cx.tcx.sess.span_err(
 468             sp, format!("value has non-sendable type `{}`",
 469                      ty_to_str(cx.tcx, ty)));
 470         false
 471     } else {
 472         true
 473     }
 474 }
 475
 476 // note: also used from middle::typeck::regionck!
 477 pub fn check_durable(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, "value may contain borrowed \
 482                                    pointers; add `'static` bound");
 483           }
 484           _ => {
 485             tcx.sess.span_err(sp, "value may contain borrowed \
 486                                    pointers");
 487           }
 488         }
 489         false
 490     } else {
 491         true
 492     }
 493 }
 494
 495 /// This is rather subtle.  When we are casting a value to a instantiated
 496 /// trait like `a as trait<'r>`, regionck already ensures that any borrowed
 497 /// pointers 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 borrowed pointers
 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 borrowed pointers 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 borrowed ptrs may appear in `T` also
 514 /// appear in `deque<T>`.
 515 ///
 516 /// (3) The type parameter is sendable (and therefore does not contain
 517 /// borrowed ptrs).
 518 ///
 519 /// FIXME(#5723)---This code should probably move into regionck.
 520 pub fn check_cast_for_escaping_regions(
 521     cx: &Context,
 522     source: &Expr,
 523     target: &Expr)
 524 {
 525     // Determine what type we are casting to; if it is not an trait, then no
 526     // worries.
 527     let target_ty = ty::expr_ty(cx.tcx, target);
 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         |_| true);
 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_re_scope(*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     let source_ty = ty::expr_ty(cx.tcx, source);
 558     ty::walk_regions_and_ty(
 559         cx.tcx,
 560         source_ty,
 561
 562         |_r| {
 563             // FIXME(#5723) --- turn this check on once &Objects are usable
 564             //
 565             // if !target_regions.iter().any(|t_r| is_subregion_of(cx, *t_r, r)) {
 566             //     cx.tcx.sess.span_err(
 567             //         source.span,
 568             //         format!("source contains borrowed pointer with lifetime \
 569             //               not found in the target type `{}`",
 570             //              ty_to_str(cx.tcx, target_ty)));
 571             //     note_and_explain_region(
 572             //         cx.tcx, "source data is only valid for ", r, "");
 573             // }
 574         },
 575
 576         |ty| {
 577             match ty::get(ty).sty {
 578                 ty::ty_param(source_param) => {
 579                     if target_params.iter().any(|x| x == &source_param) {
 580                         /* case (2) */
 581                     } else {
 582                         check_durable(cx.tcx, ty, source.span); /* case (3) */
 583                     }
 584                 }
 585                 _ => {}
 586             }
 587             true
 588         });
 589
 590     fn is_re_scope(r: ty::Region) -> bool {
 591         match r {
 592             ty::re_scope(*) => true,
 593             _ => false
 594         }
 595     }
 596
 597     fn is_subregion_of(cx: &Context, r_sub: ty::Region, r_sup: ty::Region) -> bool {
 598         cx.tcx.region_maps.is_subregion_of(r_sub, r_sup)
 599     }
 600 }