src/librustc/middle/typeck/check/writeback.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 // Type resolution: the phase that finds all the types in the AST with
  12 // unresolved type variables and replaces "ty_var" types with their
  13 // substitutions.
  14
  15 use middle::def;
  16 use middle::pat_util;
  17 use middle::ty;
  18 use middle::ty_fold::{TypeFolder,TypeFoldable};
  19 use middle::typeck::astconv::AstConv;
  20 use middle::typeck::check::FnCtxt;
  21 use middle::typeck::infer::{force_all, resolve_all, resolve_region};
  22 use middle::typeck::infer::resolve_type;
  23 use middle::typeck::infer;
  24 use middle::typeck::{MethodCall, MethodCallee};
  25 use middle::typeck::vtable_res;
  26 use middle::typeck::write_substs_to_tcx;
  27 use middle::typeck::write_ty_to_tcx;
  28 use util::ppaux::Repr;
  29
  30 use std::cell::Cell;
  31
  32 use syntax::ast;
  33 use syntax::codemap::{DUMMY_SP, Span};
  34 use syntax::print::pprust::pat_to_string;
  35 use syntax::visit;
  36 use syntax::visit::Visitor;
  37
  38 ///////////////////////////////////////////////////////////////////////////
  39 // Entry point functions
  40
  41 pub fn resolve_type_vars_in_expr(fcx: &FnCtxt, e: &ast::Expr) {
  42     assert_eq!(fcx.writeback_errors.get(), false);
  43     let mut wbcx = WritebackCx::new(fcx);
  44     wbcx.visit_expr(e, ());
  45     wbcx.visit_upvar_borrow_map();
  46     wbcx.visit_unboxed_closure_types();
  47 }
  48
  49 pub fn resolve_type_vars_in_fn(fcx: &FnCtxt,
  50                                decl: &ast::FnDecl,
  51                                blk: &ast::Block) {
  52     assert_eq!(fcx.writeback_errors.get(), false);
  53     let mut wbcx = WritebackCx::new(fcx);
  54     wbcx.visit_block(blk, ());
  55     for arg in decl.inputs.iter() {
  56         wbcx.visit_pat(&*arg.pat, ());
  57
  58         // Privacy needs the type for the whole pattern, not just each binding
  59         if !pat_util::pat_is_binding(&fcx.tcx().def_map, &*arg.pat) {
  60             wbcx.visit_node_id(ResolvingPattern(arg.pat.span),
  61                                arg.pat.id);
  62         }
  63     }
  64     wbcx.visit_upvar_borrow_map();
  65     wbcx.visit_unboxed_closure_types();
  66 }
  67
  68 pub fn resolve_impl_res(infcx: &infer::InferCtxt,
  69                         span: Span,
  70                         vtable_res: &vtable_res)
  71                         -> vtable_res {
  72     let errors = Cell::new(false); // nobody cares
  73     let mut resolver = Resolver::from_infcx(infcx,
  74                                             &errors,
  75                                             ResolvingImplRes(span));
  76     vtable_res.resolve_in(&mut resolver)
  77 }
  78
  79 ///////////////////////////////////////////////////////////////////////////
  80 // The Writerback context. This visitor walks the AST, checking the
  81 // fn-specific tables to find references to types or regions. It
  82 // resolves those regions to remove inference variables and writes the
  83 // final result back into the master tables in the tcx. Here and
  84 // there, it applies a few ad-hoc checks that were not convenient to
  85 // do elsewhere.
  86
  87 struct WritebackCx<'cx> {
  88     fcx: &'cx FnCtxt<'cx>,
  89 }
  90
  91 impl<'cx> WritebackCx<'cx> {
  92     fn new(fcx: &'cx FnCtxt) -> WritebackCx<'cx> {
  93         WritebackCx { fcx: fcx }
  94     }
  95
  96     fn tcx(&self) -> &'cx ty::ctxt {
  97         self.fcx.tcx()
  98     }
  99 }
 100
 101 ///////////////////////////////////////////////////////////////////////////
 102 // Impl of Visitor for Resolver
 103 //
 104 // This is the master code which walks the AST. It delegates most of
 105 // the heavy lifting to the generic visit and resolve functions
 106 // below. In general, a function is made into a `visitor` if it must
 107 // traffic in node-ids or update tables in the type context etc.
 108
 109 impl<'cx> Visitor<()> for WritebackCx<'cx> {
 110     fn visit_item(&mut self, _: &ast::Item, _: ()) {
 111         // Ignore items
 112     }
 113
 114     fn visit_stmt(&mut self, s: &ast::Stmt, _: ()) {
 115         if self.fcx.writeback_errors.get() {
 116             return;
 117         }
 118
 119         self.visit_node_id(ResolvingExpr(s.span), ty::stmt_node_id(s));
 120         visit::walk_stmt(self, s, ());
 121     }
 122
 123     fn visit_expr(&mut self, e:&ast::Expr, _: ()) {
 124         if self.fcx.writeback_errors.get() {
 125             return;
 126         }
 127
 128         self.visit_node_id(ResolvingExpr(e.span), e.id);
 129         self.visit_method_map_entry(ResolvingExpr(e.span),
 130                                     MethodCall::expr(e.id));
 131         self.visit_vtable_map_entry(ResolvingExpr(e.span),
 132                                     MethodCall::expr(e.id));
 133
 134         match e.node {
 135             ast::ExprFnBlock(ref decl, _) |
 136             ast::ExprProc(ref decl, _) |
 137             ast::ExprUnboxedFn(ref decl, _) => {
 138                 for input in decl.inputs.iter() {
 139                     let _ = self.visit_node_id(ResolvingExpr(e.span),
 140                                                input.id);
 141                 }
 142             }
 143             _ => {}
 144         }
 145
 146         visit::walk_expr(self, e, ());
 147     }
 148
 149     fn visit_block(&mut self, b: &ast::Block, _: ()) {
 150         if self.fcx.writeback_errors.get() {
 151             return;
 152         }
 153
 154         self.visit_node_id(ResolvingExpr(b.span), b.id);
 155         visit::walk_block(self, b, ());
 156     }
 157
 158     fn visit_pat(&mut self, p: &ast::Pat, _: ()) {
 159         if self.fcx.writeback_errors.get() {
 160             return;
 161         }
 162
 163         self.visit_node_id(ResolvingPattern(p.span), p.id);
 164
 165         debug!("Type for pattern binding {} (id {}) resolved to {}",
 166                pat_to_string(p),
 167                p.id,
 168                ty::node_id_to_type(self.tcx(), p.id).repr(self.tcx()));
 169
 170         visit::walk_pat(self, p, ());
 171     }
 172
 173     fn visit_local(&mut self, l: &ast::Local, _: ()) {
 174         if self.fcx.writeback_errors.get() {
 175             return;
 176         }
 177
 178         let var_ty = self.fcx.local_ty(l.span, l.id);
 179         let var_ty = self.resolve(&var_ty, ResolvingLocal(l.span));
 180         write_ty_to_tcx(self.tcx(), l.id, var_ty);
 181         visit::walk_local(self, l, ());
 182     }
 183
 184     fn visit_ty(&mut self, t: &ast::Ty, _: ()) {
 185         match t.node {
 186             ast::TyFixedLengthVec(ref ty, ref count_expr) => {
 187                 self.visit_ty(&**ty, ());
 188                 write_ty_to_tcx(self.tcx(), count_expr.id, ty::mk_uint());
 189             }
 190             _ => visit::walk_ty(self, t, ())
 191         }
 192     }
 193 }
 194
 195 impl<'cx> WritebackCx<'cx> {
 196     fn visit_upvar_borrow_map(&self) {
 197         if self.fcx.writeback_errors.get() {
 198             return;
 199         }
 200
 201         for (upvar_id, upvar_borrow) in self.fcx.inh.upvar_borrow_map.borrow().iter() {
 202             let r = upvar_borrow.region;
 203             let r = self.resolve(&r, ResolvingUpvar(*upvar_id));
 204             let new_upvar_borrow = ty::UpvarBorrow { kind: upvar_borrow.kind,
 205                                                      region: r };
 206             debug!("Upvar borrow for {} resolved to {}",
 207                    upvar_id.repr(self.tcx()),
 208                    new_upvar_borrow.repr(self.tcx()));
 209             self.fcx.tcx().upvar_borrow_map.borrow_mut().insert(
 210                 *upvar_id, new_upvar_borrow);
 211         }
 212     }
 213
 214     fn visit_unboxed_closure_types(&self) {
 215         if self.fcx.writeback_errors.get() {
 216             return
 217         }
 218
 219         for (def_id, closure_ty) in self.fcx
 220                                         .inh
 221                                         .unboxed_closure_types
 222                                         .borrow()
 223                                         .iter() {
 224             let closure_ty = self.resolve(closure_ty,
 225                                           ResolvingUnboxedClosure(*def_id));
 226             self.fcx
 227                 .tcx()
 228                 .unboxed_closure_types
 229                 .borrow_mut()
 230                 .insert(*def_id, closure_ty);
 231         }
 232     }
 233
 234     fn visit_node_id(&self, reason: ResolveReason, id: ast::NodeId) {
 235         // Resolve any borrowings for the node with id `id`
 236         self.visit_adjustments(reason, id);
 237
 238         // Resolve the type of the node with id `id`
 239         let n_ty = self.fcx.node_ty(id);
 240         let n_ty = self.resolve(&n_ty, reason);
 241         write_ty_to_tcx(self.tcx(), id, n_ty);
 242         debug!("Node {} has type {}", id, n_ty.repr(self.tcx()));
 243
 244         // Resolve any substitutions
 245         self.fcx.opt_node_ty_substs(id, |item_substs| {
 246             write_substs_to_tcx(self.tcx(), id,
 247                                 self.resolve(item_substs, reason));
 248         });
 249     }
 250
 251     fn visit_adjustments(&self, reason: ResolveReason, id: ast::NodeId) {
 252         match self.fcx.inh.adjustments.borrow_mut().pop(&id) {
 253             None => {
 254                 debug!("No adjustments for node {}", id);
 255             }
 256
 257             Some(adjustment) => {
 258                 let resolved_adjustment = match adjustment {
 259                     ty::AutoAddEnv(store) => {
 260                         // FIXME(eddyb) #2190 Allow only statically resolved
 261                         // bare functions to coerce to a closure to avoid
 262                         // constructing (slower) indirect call wrappers.
 263                         match self.tcx().def_map.borrow().find(&id) {
 264                             Some(&def::DefFn(..)) |
 265                             Some(&def::DefStaticMethod(..)) |
 266                             Some(&def::DefVariant(..)) |
 267                             Some(&def::DefStruct(_)) => {
 268                             }
 269                             _ => {
 270                                 span_err!(self.tcx().sess, reason.span(self.tcx()), E0100,
 271                                     "cannot coerce non-statically resolved bare fn");
 272                             }
 273                         }
 274
 275                         ty::AutoAddEnv(self.resolve(&store, reason))
 276                     }
 277
 278                     ty::AutoDerefRef(adj) => {
 279                         for autoderef in range(0, adj.autoderefs) {
 280                             let method_call = MethodCall::autoderef(id, autoderef);
 281                             self.visit_method_map_entry(reason, method_call);
 282                             self.visit_vtable_map_entry(reason, method_call);
 283                         }
 284
 285                         ty::AutoDerefRef(ty::AutoDerefRef {
 286                             autoderefs: adj.autoderefs,
 287                             autoref: self.resolve(&adj.autoref, reason),
 288                         })
 289                     }
 290
 291                     ty::AutoObject(trait_store, bb, def_id, substs) => {
 292                         let method_call = MethodCall::autoobject(id);
 293                         self.visit_method_map_entry(reason, method_call);
 294                         self.visit_vtable_map_entry(reason, method_call);
 295
 296                         ty::AutoObject(
 297                             self.resolve(&trait_store, reason),
 298                             self.resolve(&bb, reason),
 299                             def_id,
 300                             self.resolve(&substs, reason)
 301                         )
 302                     }
 303                 };
 304                 debug!("Adjustments for node {}: {:?}", id, resolved_adjustment);
 305                 self.tcx().adjustments.borrow_mut().insert(
 306                     id, resolved_adjustment);
 307             }
 308         }
 309     }
 310
 311     fn visit_method_map_entry(&self,
 312                               reason: ResolveReason,
 313                               method_call: MethodCall) {
 314         // Resolve any method map entry
 315         match self.fcx.inh.method_map.borrow_mut().pop(&method_call) {
 316             Some(method) => {
 317                 debug!("writeback::resolve_method_map_entry(call={:?}, entry={})",
 318                        method_call,
 319                        method.repr(self.tcx()));
 320                 let new_method = MethodCallee {
 321                     origin: method.origin,
 322                     ty: self.resolve(&method.ty, reason),
 323                     substs: self.resolve(&method.substs, reason),
 324                 };
 325
 326                 self.tcx().method_map.borrow_mut().insert(
 327                     method_call,
 328                     new_method);
 329             }
 330             None => {}
 331         }
 332     }
 333
 334     fn visit_vtable_map_entry(&self,
 335                               reason: ResolveReason,
 336                               vtable_key: MethodCall) {
 337         // Resolve any vtable map entry
 338         match self.fcx.inh.vtable_map.borrow_mut().pop(&vtable_key) {
 339             Some(origins) => {
 340                 let r_origins = self.resolve(&origins, reason);
 341                 debug!("writeback::resolve_vtable_map_entry(\
 342                         vtable_key={}, vtables={:?})",
 343                        vtable_key, r_origins.repr(self.tcx()));
 344                 self.tcx().vtable_map.borrow_mut().insert(vtable_key, r_origins);
 345             }
 346             None => {}
 347         }
 348     }
 349
 350     fn resolve<T:ResolveIn>(&self, t: &T, reason: ResolveReason) -> T {
 351         t.resolve_in(&mut Resolver::new(self.fcx, reason))
 352     }
 353 }
 354
 355 ///////////////////////////////////////////////////////////////////////////
 356 // Resolution reason.
 357
 358 enum ResolveReason {
 359     ResolvingExpr(Span),
 360     ResolvingLocal(Span),
 361     ResolvingPattern(Span),
 362     ResolvingUpvar(ty::UpvarId),
 363     ResolvingImplRes(Span),
 364     ResolvingUnboxedClosure(ast::DefId),
 365 }
 366
 367 impl ResolveReason {
 368     fn span(&self, tcx: &ty::ctxt) -> Span {
 369         match *self {
 370             ResolvingExpr(s) => s,
 371             ResolvingLocal(s) => s,
 372             ResolvingPattern(s) => s,
 373             ResolvingUpvar(upvar_id) => {
 374                 ty::expr_span(tcx, upvar_id.closure_expr_id)
 375             }
 376             ResolvingImplRes(s) => s,
 377             ResolvingUnboxedClosure(did) => {
 378                 if did.krate == ast::LOCAL_CRATE {
 379                     ty::expr_span(tcx, did.node)
 380                 } else {
 381                     DUMMY_SP
 382                 }
 383             }
 384         }
 385     }
 386 }
 387
 388 ///////////////////////////////////////////////////////////////////////////
 389 // Convenience methods for resolving different kinds of things.
 390
 391 trait ResolveIn {
 392     fn resolve_in(&self, resolver: &mut Resolver) -> Self;
 393 }
 394
 395 impl<T:TypeFoldable> ResolveIn for T {
 396     fn resolve_in(&self, resolver: &mut Resolver) -> T {
 397         self.fold_with(resolver)
 398     }
 399 }
 400
 401 ///////////////////////////////////////////////////////////////////////////
 402 // The Resolver. This is the type folding engine that detects
 403 // unresolved types and so forth.
 404
 405 struct Resolver<'cx> {
 406     tcx: &'cx ty::ctxt,
 407     infcx: &'cx infer::InferCtxt<'cx>,
 408     writeback_errors: &'cx Cell<bool>,
 409     reason: ResolveReason,
 410 }
 411
 412 impl<'cx> Resolver<'cx> {
 413     fn new(fcx: &'cx FnCtxt<'cx>,
 414            reason: ResolveReason)
 415            -> Resolver<'cx>
 416     {
 417         Resolver { infcx: fcx.infcx(),
 418                    tcx: fcx.tcx(),
 419                    writeback_errors: &fcx.writeback_errors,
 420                    reason: reason }
 421     }
 422
 423     fn from_infcx(infcx: &'cx infer::InferCtxt<'cx>,
 424                   writeback_errors: &'cx Cell<bool>,
 425                   reason: ResolveReason)
 426                   -> Resolver<'cx>
 427     {
 428         Resolver { infcx: infcx,
 429                    tcx: infcx.tcx,
 430                    writeback_errors: writeback_errors,
 431                    reason: reason }
 432     }
 433
 434     fn report_error(&self, e: infer::fixup_err) {
 435         self.writeback_errors.set(true);
 436         if !self.tcx.sess.has_errors() {
 437             match self.reason {
 438                 ResolvingExpr(span) => {
 439                     span_err!(self.tcx.sess, span, E0101,
 440                         "cannot determine a type for this expression: {}",
 441                         infer::fixup_err_to_string(e));
 442                 }
 443
 444                 ResolvingLocal(span) => {
 445                     span_err!(self.tcx.sess, span, E0102,
 446                         "cannot determine a type for this local variable: {}",
 447                         infer::fixup_err_to_string(e));
 448                 }
 449
 450                 ResolvingPattern(span) => {
 451                     span_err!(self.tcx.sess, span, E0103,
 452                         "cannot determine a type for this pattern binding: {}",
 453                         infer::fixup_err_to_string(e));
 454                 }
 455
 456                 ResolvingUpvar(upvar_id) => {
 457                     let span = self.reason.span(self.tcx);
 458                     span_err!(self.tcx.sess, span, E0104,
 459                         "cannot resolve lifetime for captured variable `{}`: {}",
 460                         ty::local_var_name_str(self.tcx, upvar_id.var_id).get().to_string(),
 461                         infer::fixup_err_to_string(e));
 462                 }
 463
 464                 ResolvingImplRes(span) => {
 465                     span_err!(self.tcx.sess, span, E0105,
 466                         "cannot determine a type for impl supertrait");
 467                 }
 468
 469                 ResolvingUnboxedClosure(_) => {
 470                     let span = self.reason.span(self.tcx);
 471                     self.tcx.sess.span_err(span,
 472                                            "cannot determine a type for this \
 473                                             unboxed closure")
 474                 }
 475             }
 476         }
 477     }
 478 }
 479
 480 impl<'cx> TypeFolder for Resolver<'cx> {
 481     fn tcx<'a>(&'a self) -> &'a ty::ctxt {
 482         self.tcx
 483     }
 484
 485     fn fold_ty(&mut self, t: ty::t) -> ty::t {
 486         if !ty::type_needs_infer(t) {
 487             return t;
 488         }
 489
 490         match resolve_type(self.infcx, None, t, resolve_all | force_all) {
 491             Ok(t) => t,
 492             Err(e) => {
 493                 self.report_error(e);
 494                 ty::mk_err()
 495             }
 496         }
 497     }
 498
 499     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 500         match resolve_region(self.infcx, r, resolve_all | force_all) {
 501             Ok(r) => r,
 502             Err(e) => {
 503                 self.report_error(e);
 504                 ty::ReStatic
 505             }
 506         }
 507     }
 508 }