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_closures();
  47     wbcx.visit_object_cast_map();
  48 }
  49
  50 pub fn resolve_type_vars_in_fn(fcx: &FnCtxt,
  51                                decl: &ast::FnDecl,
  52                                blk: &ast::Block) {
  53     assert_eq!(fcx.writeback_errors.get(), false);
  54     let mut wbcx = WritebackCx::new(fcx);
  55     wbcx.visit_block(blk);
  56     for arg in decl.inputs.iter() {
  57         wbcx.visit_pat(&*arg.pat);
  58
  59         // Privacy needs the type for the whole pattern, not just each binding
  60         if !pat_util::pat_is_binding(&fcx.tcx().def_map, &*arg.pat) {
  61             wbcx.visit_node_id(ResolvingPattern(arg.pat.span),
  62                                arg.pat.id);
  63         }
  64     }
  65     wbcx.visit_upvar_borrow_map();
  66     wbcx.visit_unboxed_closures();
  67     wbcx.visit_object_cast_map();
  68 }
  69
  70 pub fn resolve_impl_res(infcx: &infer::InferCtxt,
  71                         span: Span,
  72                         vtable_res: &vtable_res)
  73                         -> vtable_res {
  74     let errors = Cell::new(false); // nobody cares
  75     let mut resolver = Resolver::from_infcx(infcx,
  76                                             &errors,
  77                                             ResolvingImplRes(span));
  78     vtable_res.resolve_in(&mut resolver)
  79 }
  80
  81 ///////////////////////////////////////////////////////////////////////////
  82 // The Writerback context. This visitor walks the AST, checking the
  83 // fn-specific tables to find references to types or regions. It
  84 // resolves those regions to remove inference variables and writes the
  85 // final result back into the master tables in the tcx. Here and
  86 // there, it applies a few ad-hoc checks that were not convenient to
  87 // do elsewhere.
  88
  89 struct WritebackCx<'cx, 'tcx: 'cx> {
  90     fcx: &'cx FnCtxt<'cx, 'tcx>,
  91 }
  92
  93 impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
  94     fn new(fcx: &'cx FnCtxt<'cx, 'tcx>) -> WritebackCx<'cx, 'tcx> {
  95         WritebackCx { fcx: fcx }
  96     }
  97
  98     fn tcx(&self) -> &'cx ty::ctxt<'tcx> {
  99         self.fcx.tcx()
 100     }
 101 }
 102
 103 ///////////////////////////////////////////////////////////////////////////
 104 // Impl of Visitor for Resolver
 105 //
 106 // This is the master code which walks the AST. It delegates most of
 107 // the heavy lifting to the generic visit and resolve functions
 108 // below. In general, a function is made into a `visitor` if it must
 109 // traffic in node-ids or update tables in the type context etc.
 110
 111 impl<'cx, 'tcx, 'v> Visitor<'v> for WritebackCx<'cx, 'tcx> {
 112     fn visit_item(&mut self, _: &ast::Item) {
 113         // Ignore items
 114     }
 115
 116     fn visit_stmt(&mut self, s: &ast::Stmt) {
 117         if self.fcx.writeback_errors.get() {
 118             return;
 119         }
 120
 121         self.visit_node_id(ResolvingExpr(s.span), ty::stmt_node_id(s));
 122         visit::walk_stmt(self, s);
 123     }
 124
 125     fn visit_expr(&mut self, e: &ast::Expr) {
 126         if self.fcx.writeback_errors.get() {
 127             return;
 128         }
 129
 130         self.visit_node_id(ResolvingExpr(e.span), e.id);
 131         self.visit_method_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, 'tcx> WritebackCx<'cx, 'tcx> {
 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_closures(&self) {
 215         if self.fcx.writeback_errors.get() {
 216             return
 217         }
 218
 219         for (def_id, unboxed_closure) in self.fcx
 220                                              .inh
 221                                              .unboxed_closures
 222                                              .borrow()
 223                                              .iter() {
 224             let closure_ty = self.resolve(&unboxed_closure.closure_type,
 225                                           ResolvingUnboxedClosure(*def_id));
 226             let unboxed_closure = ty::UnboxedClosure {
 227                 closure_type: closure_ty,
 228                 kind: unboxed_closure.kind,
 229             };
 230             self.fcx
 231                 .tcx()
 232                 .unboxed_closures
 233                 .borrow_mut()
 234                 .insert(*def_id, unboxed_closure);
 235         }
 236     }
 237
 238     fn visit_object_cast_map(&self) {
 239         if self.fcx.writeback_errors.get() {
 240             return
 241         }
 242
 243         for (&node_id, trait_ref) in self.fcx
 244                                             .inh
 245                                             .object_cast_map
 246                                             .borrow()
 247                                             .iter()
 248         {
 249             let span = ty::expr_span(self.tcx(), node_id);
 250             let reason = ResolvingExpr(span);
 251             let closure_ty = self.resolve(trait_ref, reason);
 252             self.tcx()
 253                 .object_cast_map
 254                 .borrow_mut()
 255                 .insert(node_id, closure_ty);
 256         }
 257     }
 258
 259     fn visit_node_id(&self, reason: ResolveReason, id: ast::NodeId) {
 260         // Resolve any borrowings for the node with id `id`
 261         self.visit_adjustments(reason, id);
 262
 263         // Resolve the type of the node with id `id`
 264         let n_ty = self.fcx.node_ty(id);
 265         let n_ty = self.resolve(&n_ty, reason);
 266         write_ty_to_tcx(self.tcx(), id, n_ty);
 267         debug!("Node {} has type {}", id, n_ty.repr(self.tcx()));
 268
 269         // Resolve any substitutions
 270         self.fcx.opt_node_ty_substs(id, |item_substs| {
 271             write_substs_to_tcx(self.tcx(), id,
 272                                 self.resolve(item_substs, reason));
 273         });
 274     }
 275
 276     fn visit_adjustments(&self, reason: ResolveReason, id: ast::NodeId) {
 277         match self.fcx.inh.adjustments.borrow_mut().pop(&id) {
 278             None => {
 279                 debug!("No adjustments for node {}", id);
 280             }
 281
 282             Some(adjustment) => {
 283                 let adj_object = ty::adjust_is_object(&adjustment);
 284                 let resolved_adjustment = match adjustment {
 285                     ty::AdjustAddEnv(store) => {
 286                         // FIXME(eddyb) #2190 Allow only statically resolved
 287                         // bare functions to coerce to a closure to avoid
 288                         // constructing (slower) indirect call wrappers.
 289                         match self.tcx().def_map.borrow().find(&id) {
 290                             Some(&def::DefFn(..)) |
 291                             Some(&def::DefStaticMethod(..)) |
 292                             Some(&def::DefVariant(..)) |
 293                             Some(&def::DefStruct(_)) => {
 294                             }
 295                             _ => {
 296                                 span_err!(self.tcx().sess, reason.span(self.tcx()), E0100,
 297                                     "cannot coerce non-statically resolved bare fn");
 298                             }
 299                         }
 300
 301                         ty::AdjustAddEnv(self.resolve(&store, reason))
 302                     }
 303
 304                     ty::AdjustDerefRef(adj) => {
 305                         for autoderef in range(0, adj.autoderefs) {
 306                             let method_call = MethodCall::autoderef(id, autoderef);
 307                             self.visit_method_map_entry(reason, method_call);
 308                         }
 309
 310                         if adj_object {
 311                             let method_call = MethodCall::autoobject(id);
 312                             self.visit_method_map_entry(reason, method_call);
 313                         }
 314
 315                         ty::AdjustDerefRef(ty::AutoDerefRef {
 316                             autoderefs: adj.autoderefs,
 317                             autoref: self.resolve(&adj.autoref, reason),
 318                         })
 319                     }
 320                 };
 321                 debug!("Adjustments for node {}: {:?}", id, resolved_adjustment);
 322                 self.tcx().adjustments.borrow_mut().insert(
 323                     id, resolved_adjustment);
 324             }
 325         }
 326     }
 327
 328     fn visit_method_map_entry(&self,
 329                               reason: ResolveReason,
 330                               method_call: MethodCall) {
 331         // Resolve any method map entry
 332         match self.fcx.inh.method_map.borrow_mut().pop(&method_call) {
 333             Some(method) => {
 334                 debug!("writeback::resolve_method_map_entry(call={:?}, entry={})",
 335                        method_call,
 336                        method.repr(self.tcx()));
 337                 let new_method = MethodCallee {
 338                     origin: method.origin,
 339                     ty: self.resolve(&method.ty, reason),
 340                     substs: self.resolve(&method.substs, reason),
 341                 };
 342
 343                 self.tcx().method_map.borrow_mut().insert(
 344                     method_call,
 345                     new_method);
 346             }
 347             None => {}
 348         }
 349     }
 350
 351     fn resolve<T:ResolveIn>(&self, t: &T, reason: ResolveReason) -> T {
 352         t.resolve_in(&mut Resolver::new(self.fcx, reason))
 353     }
 354 }
 355
 356 ///////////////////////////////////////////////////////////////////////////
 357 // Resolution reason.
 358
 359 enum ResolveReason {
 360     ResolvingExpr(Span),
 361     ResolvingLocal(Span),
 362     ResolvingPattern(Span),
 363     ResolvingUpvar(ty::UpvarId),
 364     ResolvingImplRes(Span),
 365     ResolvingUnboxedClosure(ast::DefId),
 366 }
 367
 368 impl ResolveReason {
 369     fn span(&self, tcx: &ty::ctxt) -> Span {
 370         match *self {
 371             ResolvingExpr(s) => s,
 372             ResolvingLocal(s) => s,
 373             ResolvingPattern(s) => s,
 374             ResolvingUpvar(upvar_id) => {
 375                 ty::expr_span(tcx, upvar_id.closure_expr_id)
 376             }
 377             ResolvingImplRes(s) => s,
 378             ResolvingUnboxedClosure(did) => {
 379                 if did.krate == ast::LOCAL_CRATE {
 380                     ty::expr_span(tcx, did.node)
 381                 } else {
 382                     DUMMY_SP
 383                 }
 384             }
 385         }
 386     }
 387 }
 388
 389 ///////////////////////////////////////////////////////////////////////////
 390 // Convenience methods for resolving different kinds of things.
 391
 392 trait ResolveIn {
 393     fn resolve_in(&self, resolver: &mut Resolver) -> Self;
 394 }
 395
 396 impl<T:TypeFoldable> ResolveIn for T {
 397     fn resolve_in(&self, resolver: &mut Resolver) -> T {
 398         self.fold_with(resolver)
 399     }
 400 }
 401
 402 ///////////////////////////////////////////////////////////////////////////
 403 // The Resolver. This is the type folding engine that detects
 404 // unresolved types and so forth.
 405
 406 struct Resolver<'cx, 'tcx: 'cx> {
 407     tcx: &'cx ty::ctxt<'tcx>,
 408     infcx: &'cx infer::InferCtxt<'cx, 'tcx>,
 409     writeback_errors: &'cx Cell<bool>,
 410     reason: ResolveReason,
 411 }
 412
 413 impl<'cx, 'tcx> Resolver<'cx, 'tcx> {
 414     fn new(fcx: &'cx FnCtxt<'cx, 'tcx>,
 415            reason: ResolveReason)
 416            -> Resolver<'cx, 'tcx>
 417     {
 418         Resolver { infcx: fcx.infcx(),
 419                    tcx: fcx.tcx(),
 420                    writeback_errors: &fcx.writeback_errors,
 421                    reason: reason }
 422     }
 423
 424     fn from_infcx(infcx: &'cx infer::InferCtxt<'cx, 'tcx>,
 425                   writeback_errors: &'cx Cell<bool>,
 426                   reason: ResolveReason)
 427                   -> Resolver<'cx, 'tcx>
 428     {
 429         Resolver { infcx: infcx,
 430                    tcx: infcx.tcx,
 431                    writeback_errors: writeback_errors,
 432                    reason: reason }
 433     }
 434
 435     fn report_error(&self, e: infer::fixup_err) {
 436         self.writeback_errors.set(true);
 437         if !self.tcx.sess.has_errors() {
 438             match self.reason {
 439                 ResolvingExpr(span) => {
 440                     span_err!(self.tcx.sess, span, E0101,
 441                         "cannot determine a type for this expression: {}",
 442                         infer::fixup_err_to_string(e));
 443                 }
 444
 445                 ResolvingLocal(span) => {
 446                     span_err!(self.tcx.sess, span, E0102,
 447                         "cannot determine a type for this local variable: {}",
 448                         infer::fixup_err_to_string(e));
 449                 }
 450
 451                 ResolvingPattern(span) => {
 452                     span_err!(self.tcx.sess, span, E0103,
 453                         "cannot determine a type for this pattern binding: {}",
 454                         infer::fixup_err_to_string(e));
 455                 }
 456
 457                 ResolvingUpvar(upvar_id) => {
 458                     let span = self.reason.span(self.tcx);
 459                     span_err!(self.tcx.sess, span, E0104,
 460                         "cannot resolve lifetime for captured variable `{}`: {}",
 461                         ty::local_var_name_str(self.tcx, upvar_id.var_id).get().to_string(),
 462                         infer::fixup_err_to_string(e));
 463                 }
 464
 465                 ResolvingImplRes(span) => {
 466                     span_err!(self.tcx.sess, span, E0105,
 467                         "cannot determine a type for impl supertrait");
 468                 }
 469
 470                 ResolvingUnboxedClosure(_) => {
 471                     let span = self.reason.span(self.tcx);
 472                     self.tcx.sess.span_err(span,
 473                                            "cannot determine a type for this \
 474                                             unboxed closure")
 475                 }
 476             }
 477         }
 478     }
 479 }
 480
 481 impl<'cx, 'tcx> TypeFolder<'tcx> for Resolver<'cx, 'tcx> {
 482     fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
 483         self.tcx
 484     }
 485
 486     fn fold_ty(&mut self, t: ty::t) -> ty::t {
 487         if !ty::type_needs_infer(t) {
 488             return t;
 489         }
 490
 491         match resolve_type(self.infcx, None, t, resolve_all | force_all) {
 492             Ok(t) => t,
 493             Err(e) => {
 494                 self.report_error(e);
 495                 ty::mk_err()
 496             }
 497         }
 498     }
 499
 500     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 501         match resolve_region(self.infcx, r, resolve_all | force_all) {
 502             Ok(r) => r,
 503             Err(e) => {
 504                 self.report_error(e);
 505                 ty::ReStatic
 506             }
 507         }
 508     }
 509 }
 510
 511 ///////////////////////////////////////////////////////////////////////////
 512 // During type check, we store promises with the result of trait
 513 // lookup rather than the actual results (because the results are not
 514 // necessarily available immediately). These routines unwind the
 515 // promises. It is expected that we will have already reported any
 516 // errors that may be encountered, so if the promises store an error,
 517 // a dummy result is returned.