src/interpreter/terminator.rs

   1 use rustc::hir::def_id::DefId;
   2 use rustc::mir::repr as mir;
   3 use rustc::traits::{self, Reveal};
   4 use rustc::ty::fold::TypeFoldable;
   5 use rustc::ty::layout::Layout;
   6 use rustc::ty::subst::Substs;
   7 use rustc::ty::{self, Ty, TyCtxt, BareFnTy};
   8 use std::rc::Rc;
   9 use std::iter;
  10 use syntax::{ast, attr};
  11 use syntax::codemap::{DUMMY_SP, Span};
  12
  13 use super::{EvalContext, IntegerExt};
  14 use error::{EvalError, EvalResult};
  15 use memory::{Pointer, FunctionDefinition};
  16
  17 impl<'a, 'tcx> EvalContext<'a, 'tcx> {
  18     pub(super) fn eval_terminator(
  19         &mut self,
  20         terminator: &mir::Terminator<'tcx>,
  21     ) -> EvalResult<'tcx, ()> {
  22         use rustc::mir::repr::TerminatorKind::*;
  23         match terminator.kind {
  24             Return => self.pop_stack_frame(),
  25
  26             Goto { target } => {
  27                 self.frame_mut().block = target;
  28             },
  29
  30             If { ref cond, targets: (then_target, else_target) } => {
  31                 let cond_ptr = self.eval_operand(cond)?;
  32                 let cond_val = self.memory.read_bool(cond_ptr)?;
  33                 self.frame_mut().block = if cond_val { then_target } else { else_target };
  34             }
  35
  36             SwitchInt { ref discr, ref values, ref targets, .. } => {
  37                 let discr_ptr = self.eval_lvalue(discr)?.to_ptr();
  38                 let discr_ty = self.lvalue_ty(discr);
  39                 let discr_size = self
  40                     .type_layout(discr_ty)
  41                     .size(&self.tcx.data_layout)
  42                     .bytes() as usize;
  43                 let discr_val = self.memory.read_uint(discr_ptr, discr_size)?;
  44                 if let ty::TyChar = discr_ty.sty {
  45                     if ::std::char::from_u32(discr_val as u32).is_none() {
  46                         return Err(EvalError::InvalidChar(discr_val as u32));
  47                     }
  48                 }
  49
  50                 // Branch to the `otherwise` case by default, if no match is found.
  51                 let mut target_block = targets[targets.len() - 1];
  52
  53                 for (index, val_const) in values.iter().enumerate() {
  54                     let ptr = self.const_to_ptr(val_const)?;
  55                     let val = self.memory.read_uint(ptr, discr_size)?;
  56                     if discr_val == val {
  57                         target_block = targets[index];
  58                         break;
  59                     }
  60                 }
  61
  62                 self.frame_mut().block = target_block;
  63             }
  64
  65             Switch { ref discr, ref targets, adt_def } => {
  66                 let adt_ptr = self.eval_lvalue(discr)?.to_ptr();
  67                 let adt_ty = self.lvalue_ty(discr);
  68                 let discr_val = self.read_discriminant_value(adt_ptr, adt_ty)?;
  69                 let matching = adt_def.variants.iter()
  70                     .position(|v| discr_val == v.disr_val.to_u64_unchecked());
  71
  72                 match matching {
  73                     Some(i) => {
  74                         self.frame_mut().block = targets[i];
  75                     },
  76                     None => return Err(EvalError::InvalidDiscriminant),
  77                 }
  78             }
  79
  80             Call { ref func, ref args, ref destination, .. } => {
  81                 let mut return_ptr = None;
  82                 if let Some((ref lv, target)) = *destination {
  83                     self.frame_mut().block = target;
  84                     return_ptr = Some(self.eval_lvalue(lv)?.to_ptr());
  85                 }
  86
  87                 let func_ty = self.operand_ty(func);
  88                 match func_ty.sty {
  89                     ty::TyFnPtr(bare_fn_ty) => {
  90                         let ptr = self.eval_operand(func)?;
  91                         let fn_ptr = self.memory.read_ptr(ptr)?;
  92                         let FunctionDefinition { def_id, substs, fn_ty } = self.memory.get_fn(fn_ptr.alloc_id)?;
  93                         if fn_ty != bare_fn_ty {
  94                             return Err(EvalError::FunctionPointerTyMismatch(fn_ty, bare_fn_ty));
  95                         }
  96                         self.eval_fn_call(def_id, substs, bare_fn_ty, return_ptr, args,
  97                                           terminator.source_info.span)?
  98                     },
  99                     ty::TyFnDef(def_id, substs, fn_ty) => {
 100                         self.eval_fn_call(def_id, substs, fn_ty, return_ptr, args,
 101                                           terminator.source_info.span)?
 102                     }
 103
 104                     _ => return Err(EvalError::Unimplemented(format!("can't handle callee of type {:?}", func_ty))),
 105                 }
 106             }
 107
 108             Drop { ref location, target, .. } => {
 109                 let ptr = self.eval_lvalue(location)?.to_ptr();
 110                 let ty = self.lvalue_ty(location);
 111                 self.drop(ptr, ty)?;
 112                 self.frame_mut().block = target;
 113             }
 114
 115             Assert { ref cond, expected, ref msg, target, .. } => {
 116                 let cond_ptr = self.eval_operand(cond)?;
 117                 if expected == self.memory.read_bool(cond_ptr)? {
 118                     self.frame_mut().block = target;
 119                 } else {
 120                     return match *msg {
 121                         mir::AssertMessage::BoundsCheck { ref len, ref index } => {
 122                             let len = self.eval_operand(len).expect("can't eval len");
 123                             let len = self.memory.read_usize(len).expect("can't read len");
 124                             let index = self.eval_operand(index).expect("can't eval index");
 125                             let index = self.memory.read_usize(index).expect("can't read index");
 126                             Err(EvalError::ArrayIndexOutOfBounds(terminator.source_info.span, len, index))
 127                         },
 128                         mir::AssertMessage::Math(ref err) => Err(EvalError::Math(terminator.source_info.span, err.clone())),
 129                     }
 130                 }
 131             },
 132
 133             DropAndReplace { .. } => unimplemented!(),
 134             Resume => unimplemented!(),
 135             Unreachable => unimplemented!(),
 136         }
 137
 138         Ok(())
 139     }
 140
 141     fn eval_fn_call(
 142         &mut self,
 143         def_id: DefId,
 144         substs: &'tcx Substs<'tcx>,
 145         fn_ty: &'tcx BareFnTy,
 146         return_ptr: Option<Pointer>,
 147         args: &[mir::Operand<'tcx>],
 148         span: Span,
 149     ) -> EvalResult<'tcx, ()> {
 150         use syntax::abi::Abi;
 151         match fn_ty.abi {
 152             Abi::RustIntrinsic => {
 153                 let ty = fn_ty.sig.0.output;
 154                 let layout = self.type_layout(ty);
 155                 let ret = return_ptr.unwrap();
 156                 self.call_intrinsic(def_id, substs, args, ret, layout)
 157             }
 158
 159             Abi::C => {
 160                 let ty = fn_ty.sig.0.output;
 161                 let size = self.type_size(ty);
 162                 self.call_c_abi(def_id, args, return_ptr.unwrap(), size)
 163             }
 164
 165             Abi::Rust | Abi::RustCall => {
 166                 // TODO(solson): Adjust the first argument when calling a Fn or
 167                 // FnMut closure via FnOnce::call_once.
 168
 169                 // Only trait methods can have a Self parameter.
 170                 let (resolved_def_id, resolved_substs) =
 171                     if let Some(trait_id) = self.tcx.trait_of_item(def_id) {
 172                         self.trait_method(trait_id, def_id, substs)
 173                     } else {
 174                         (def_id, substs)
 175                     };
 176
 177                 let mut arg_srcs = Vec::new();
 178                 for arg in args {
 179                     let src = self.eval_operand(arg)?;
 180                     let src_ty = self.operand_ty(arg);
 181                     arg_srcs.push((src, src_ty));
 182                 }
 183
 184                 if fn_ty.abi == Abi::RustCall && !args.is_empty() {
 185                     arg_srcs.pop();
 186                     let last_arg = args.last().unwrap();
 187                     let last = self.eval_operand(last_arg)?;
 188                     let last_ty = self.operand_ty(last_arg);
 189                     let last_layout = self.type_layout(last_ty);
 190                     match (&last_ty.sty, last_layout) {
 191                         (&ty::TyTuple(fields),
 192                          &Layout::Univariant { ref variant, .. }) => {
 193                             let offsets = iter::once(0)
 194                                 .chain(variant.offset_after_field.iter()
 195                                     .map(|s| s.bytes()));
 196                             for (offset, ty) in offsets.zip(fields) {
 197                                 let src = last.offset(offset as isize);
 198                                 arg_srcs.push((src, ty));
 199                             }
 200                         }
 201                         ty => panic!("expected tuple as last argument in function with 'rust-call' ABI, got {:?}", ty),
 202                     }
 203                 }
 204
 205                 let mir = self.load_mir(resolved_def_id);
 206                 self.push_stack_frame(def_id, span, mir, resolved_substs, return_ptr)?;
 207
 208                 for (i, (src, src_ty)) in arg_srcs.into_iter().enumerate() {
 209                     let dest = self.frame().locals[i];
 210                     self.move_(src, dest, src_ty)?;
 211                 }
 212
 213                 Ok(())
 214             }
 215
 216             abi => Err(EvalError::Unimplemented(format!("can't handle function with {:?} ABI", abi))),
 217         }
 218     }
 219
 220     fn read_discriminant_value(&self, adt_ptr: Pointer, adt_ty: Ty<'tcx>) -> EvalResult<'tcx, u64> {
 221         use rustc::ty::layout::Layout::*;
 222         let adt_layout = self.type_layout(adt_ty);
 223
 224         let discr_val = match *adt_layout {
 225             General { discr, .. } | CEnum { discr, .. } => {
 226                 let discr_size = discr.size().bytes();
 227                 self.memory.read_uint(adt_ptr, discr_size as usize)?
 228             }
 229
 230             RawNullablePointer { nndiscr, .. } => {
 231                 self.read_nonnull_discriminant_value(adt_ptr, nndiscr)?
 232             }
 233
 234             StructWrappedNullablePointer { nndiscr, ref discrfield, .. } => {
 235                 let offset = self.nonnull_offset(adt_ty, nndiscr, discrfield)?;
 236                 let nonnull = adt_ptr.offset(offset.bytes() as isize);
 237                 self.read_nonnull_discriminant_value(nonnull, nndiscr)?
 238             }
 239
 240             // The discriminant_value intrinsic returns 0 for non-sum types.
 241             Array { .. } | FatPointer { .. } | Scalar { .. } | Univariant { .. } |
 242             Vector { .. } => 0,
 243         };
 244
 245         Ok(discr_val)
 246     }
 247
 248     fn read_nonnull_discriminant_value(&self, ptr: Pointer, nndiscr: u64) -> EvalResult<'tcx, u64> {
 249         let not_null = match self.memory.read_usize(ptr) {
 250             Ok(0) => false,
 251             Ok(_) | Err(EvalError::ReadPointerAsBytes) => true,
 252             Err(e) => return Err(e),
 253         };
 254         assert!(nndiscr == 0 || nndiscr == 1);
 255         Ok(if not_null { nndiscr } else { 1 - nndiscr })
 256     }
 257
 258     fn call_intrinsic(
 259         &mut self,
 260         def_id: DefId,
 261         substs: &'tcx Substs<'tcx>,
 262         args: &[mir::Operand<'tcx>],
 263         dest: Pointer,
 264         dest_layout: &'tcx Layout,
 265     ) -> EvalResult<'tcx, ()> {
 266         let args_res: EvalResult<Vec<Pointer>> = args.iter()
 267             .map(|arg| self.eval_operand(arg))
 268             .collect();
 269         let args_ptrs = args_res?;
 270         let pointer_size = self.memory.pointer_size();
 271
 272         match &self.tcx.item_name(def_id).as_str()[..] {
 273             "add_with_overflow" => self.intrinsic_with_overflow(mir::BinOp::Add, &args[0], &args[1], dest, dest_layout)?,
 274             "sub_with_overflow" => self.intrinsic_with_overflow(mir::BinOp::Sub, &args[0], &args[1], dest, dest_layout)?,
 275             "mul_with_overflow" => self.intrinsic_with_overflow(mir::BinOp::Mul, &args[0], &args[1], dest, dest_layout)?,
 276
 277             // FIXME: turn into an assertion to catch wrong `assume` that would cause UB in llvm
 278             "assume" => {}
 279
 280             "copy_nonoverlapping" => {
 281                 let elem_ty = substs.types[0];
 282                 let elem_size = self.type_size(elem_ty);
 283                 let elem_align = self.type_align(elem_ty);
 284                 let src = self.memory.read_ptr(args_ptrs[0])?;
 285                 let dest = self.memory.read_ptr(args_ptrs[1])?;
 286                 let count = self.memory.read_isize(args_ptrs[2])?;
 287                 self.memory.copy(src, dest, count as usize * elem_size, elem_align)?;
 288             }
 289
 290             "discriminant_value" => {
 291                 let ty = substs.types[0];
 292                 let adt_ptr = self.memory.read_ptr(args_ptrs[0])?;
 293                 let discr_val = self.read_discriminant_value(adt_ptr, ty)?;
 294                 self.memory.write_uint(dest, discr_val, 8)?;
 295             }
 296
 297             "forget" => {}
 298
 299             "init" => self.memory.write_repeat(dest, 0, dest_layout.size(&self.tcx.data_layout).bytes() as usize)?,
 300
 301             "min_align_of" => {
 302                 let elem_ty = substs.types[0];
 303                 let elem_align = self.type_align(elem_ty);
 304                 self.memory.write_uint(dest, elem_align as u64, pointer_size)?;
 305             }
 306
 307             "move_val_init" => {
 308                 let ty = substs.types[0];
 309                 let ptr = self.memory.read_ptr(args_ptrs[0])?;
 310                 self.move_(args_ptrs[1], ptr, ty)?;
 311             }
 312
 313             "offset" => {
 314                 let pointee_ty = substs.types[0];
 315                 let pointee_size = self.type_size(pointee_ty) as isize;
 316                 let ptr_arg = args_ptrs[0];
 317                 let offset = self.memory.read_isize(args_ptrs[1])?;
 318
 319                 match self.memory.read_ptr(ptr_arg) {
 320                     Ok(ptr) => {
 321                         let result_ptr = ptr.offset(offset as isize * pointee_size);
 322                         self.memory.write_ptr(dest, result_ptr)?;
 323                     }
 324                     Err(EvalError::ReadBytesAsPointer) => {
 325                         let addr = self.memory.read_isize(ptr_arg)?;
 326                         let result_addr = addr + offset * pointee_size as i64;
 327                         self.memory.write_isize(dest, result_addr)?;
 328                     }
 329                     Err(e) => return Err(e),
 330                 }
 331             }
 332
 333             "overflowing_sub" => {
 334                 self.intrinsic_overflowing(mir::BinOp::Sub, &args[0], &args[1], dest)?;
 335             }
 336
 337             "overflowing_mul" => {
 338                 self.intrinsic_overflowing(mir::BinOp::Mul, &args[0], &args[1], dest)?;
 339             }
 340
 341             "overflowing_add" => {
 342                 self.intrinsic_overflowing(mir::BinOp::Add, &args[0], &args[1], dest)?;
 343             }
 344
 345             "size_of" => {
 346                 let ty = substs.types[0];
 347                 let size = self.type_size(ty) as u64;
 348                 self.memory.write_uint(dest, size, pointer_size)?;
 349             }
 350
 351             "size_of_val" => {
 352                 let ty = substs.types[0];
 353                 if self.type_is_sized(ty) {
 354                     let size = self.type_size(ty) as u64;
 355                     self.memory.write_uint(dest, size, pointer_size)?;
 356                 } else {
 357                     match ty.sty {
 358                         ty::TySlice(_) | ty::TyStr => {
 359                             let elem_ty = ty.sequence_element_type(self.tcx);
 360                             let elem_size = self.type_size(elem_ty) as u64;
 361                             let ptr_size = self.memory.pointer_size() as isize;
 362                             let n = self.memory.read_usize(args_ptrs[0].offset(ptr_size))?;
 363                             self.memory.write_uint(dest, n * elem_size, pointer_size)?;
 364                         }
 365
 366                         _ => return Err(EvalError::Unimplemented(format!("unimplemented: size_of_val::<{:?}>", ty))),
 367                     }
 368                 }
 369             }
 370
 371             "transmute" => {
 372                 let ty = substs.types[0];
 373                 self.move_(args_ptrs[0], dest, ty)?;
 374             }
 375             "uninit" => self.memory.mark_definedness(dest, dest_layout.size(&self.tcx.data_layout).bytes() as usize, false)?,
 376
 377             name => return Err(EvalError::Unimplemented(format!("unimplemented intrinsic: {}", name))),
 378         }
 379
 380         // Since we pushed no stack frame, the main loop will act
 381         // as if the call just completed and it's returning to the
 382         // current frame.
 383         Ok(())
 384     }
 385
 386     fn call_c_abi(
 387         &mut self,
 388         def_id: DefId,
 389         args: &[mir::Operand<'tcx>],
 390         dest: Pointer,
 391         dest_size: usize,
 392     ) -> EvalResult<'tcx, ()> {
 393         let name = self.tcx.item_name(def_id);
 394         let attrs = self.tcx.get_attrs(def_id);
 395         let link_name = match attr::first_attr_value_str_by_name(&attrs, "link_name") {
 396             Some(ln) => ln.clone(),
 397             None => name.as_str(),
 398         };
 399
 400         let args_res: EvalResult<Vec<Pointer>> = args.iter()
 401             .map(|arg| self.eval_operand(arg))
 402             .collect();
 403         let args = args_res?;
 404
 405         if link_name.starts_with("pthread_") {
 406             warn!("ignoring C ABI call: {}", link_name);
 407             return Ok(());
 408         }
 409
 410         match &link_name[..] {
 411             "__rust_allocate" => {
 412                 let size = self.memory.read_usize(args[0])?;
 413                 let align = self.memory.read_usize(args[1])?;
 414                 let ptr = self.memory.allocate(size as usize, align as usize)?;
 415                 self.memory.write_ptr(dest, ptr)?;
 416             }
 417
 418             "__rust_reallocate" => {
 419                 let ptr = self.memory.read_ptr(args[0])?;
 420                 let size = self.memory.read_usize(args[2])?;
 421                 let align = self.memory.read_usize(args[3])?;
 422                 let new_ptr = self.memory.reallocate(ptr, size as usize, align as usize)?;
 423                 self.memory.write_ptr(dest, new_ptr)?;
 424             }
 425
 426             "memcmp" => {
 427                 let left = self.memory.read_ptr(args[0])?;
 428                 let right = self.memory.read_ptr(args[1])?;
 429                 let n = self.memory.read_usize(args[2])? as usize;
 430
 431                 let result = {
 432                     let left_bytes = self.memory.read_bytes(left, n)?;
 433                     let right_bytes = self.memory.read_bytes(right, n)?;
 434
 435                     use std::cmp::Ordering::*;
 436                     match left_bytes.cmp(right_bytes) {
 437                         Less => -1,
 438                         Equal => 0,
 439                         Greater => 1,
 440                     }
 441                 };
 442
 443                 self.memory.write_int(dest, result, dest_size)?;
 444             }
 445
 446             _ => {
 447                 return Err(EvalError::Unimplemented(format!("can't call C ABI function: {}", link_name)));
 448             }
 449         }
 450
 451         // Since we pushed no stack frame, the main loop will act
 452         // as if the call just completed and it's returning to the
 453         // current frame.
 454         Ok(())
 455     }
 456
 457     fn fulfill_obligation(&self, trait_ref: ty::PolyTraitRef<'tcx>) -> traits::Vtable<'tcx, ()> {
 458         // Do the initial selection for the obligation. This yields the shallow result we are
 459         // looking for -- that is, what specific impl.
 460         self.tcx.normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
 461             let mut selcx = traits::SelectionContext::new(&infcx);
 462
 463             let obligation = traits::Obligation::new(
 464                 traits::ObligationCause::misc(DUMMY_SP, ast::DUMMY_NODE_ID),
 465                 trait_ref.to_poly_trait_predicate(),
 466             );
 467             let selection = selcx.select(&obligation).unwrap().unwrap();
 468
 469             // Currently, we use a fulfillment context to completely resolve all nested obligations.
 470             // This is because they can inform the inference of the impl's type parameters.
 471             let mut fulfill_cx = traits::FulfillmentContext::new();
 472             let vtable = selection.map(|predicate| {
 473                 fulfill_cx.register_predicate_obligation(&infcx, predicate);
 474             });
 475             infcx.drain_fulfillment_cx_or_panic(DUMMY_SP, &mut fulfill_cx, &vtable)
 476         })
 477     }
 478
 479     /// Trait method, which has to be resolved to an impl method.
 480     fn trait_method(
 481         &self,
 482         trait_id: DefId,
 483         def_id: DefId,
 484         substs: &'tcx Substs<'tcx>
 485     ) -> (DefId, &'tcx Substs<'tcx>) {
 486         let trait_ref = ty::TraitRef::from_method(self.tcx, trait_id, substs);
 487         let trait_ref = self.tcx.normalize_associated_type(&ty::Binder(trait_ref));
 488
 489         match self.fulfill_obligation(trait_ref) {
 490             traits::VtableImpl(vtable_impl) => {
 491                 let impl_did = vtable_impl.impl_def_id;
 492                 let mname = self.tcx.item_name(def_id);
 493                 // Create a concatenated set of substitutions which includes those from the impl
 494                 // and those from the method:
 495                 let mth = get_impl_method(self.tcx, substs, impl_did, vtable_impl.substs, mname);
 496
 497                 (mth.method.def_id, mth.substs)
 498             }
 499
 500             traits::VtableClosure(vtable_closure) =>
 501                 (vtable_closure.closure_def_id, vtable_closure.substs.func_substs),
 502
 503             traits::VtableFnPointer(_fn_ty) => {
 504                 let _trait_closure_kind = self.tcx.lang_items.fn_trait_kind(trait_id).unwrap();
 505                 unimplemented!()
 506                 // let llfn = trans_fn_pointer_shim(ccx, trait_closure_kind, fn_ty);
 507
 508                 // let method_ty = def_ty(tcx, def_id, substs);
 509                 // let fn_ptr_ty = match method_ty.sty {
 510                 //     ty::TyFnDef(_, _, fty) => tcx.mk_ty(ty::TyFnPtr(fty)),
 511                 //     _ => unreachable!("expected fn item type, found {}",
 512                 //                       method_ty)
 513                 // };
 514                 // Callee::ptr(immediate_rvalue(llfn, fn_ptr_ty))
 515             }
 516
 517             traits::VtableObject(ref _data) => {
 518                 unimplemented!()
 519                 // Callee {
 520                 //     data: Virtual(traits::get_vtable_index_of_object_method(
 521                 //                   tcx, data, def_id)),
 522                 //                   ty: def_ty(tcx, def_id, substs)
 523                 // }
 524             }
 525             vtable => unreachable!("resolved vtable bad vtable {:?} in trans", vtable),
 526         }
 527     }
 528
 529     pub(super) fn type_needs_drop(&self, ty: Ty<'tcx>) -> bool {
 530         self.tcx.type_needs_drop_given_env(ty, &self.tcx.empty_parameter_environment())
 531     }
 532
 533     fn drop(&mut self, ptr: Pointer, ty: Ty<'tcx>) -> EvalResult<'tcx, ()> {
 534         if !self.type_needs_drop(ty) {
 535             debug!("no need to drop {:?}", ty);
 536             return Ok(());
 537         }
 538         trace!("-need to drop {:?}", ty);
 539
 540         // TODO(solson): Call user-defined Drop::drop impls.
 541
 542         match ty.sty {
 543             ty::TyBox(_contents_ty) => {
 544                 let contents_ptr = self.memory.read_ptr(ptr)?;
 545                 // self.drop(contents_ptr, contents_ty)?;
 546                 trace!("-deallocating box");
 547                 self.memory.deallocate(contents_ptr)?;
 548             }
 549
 550             // TODO(solson): Implement drop for other relevant types (e.g. aggregates).
 551             _ => {}
 552         }
 553
 554         Ok(())
 555     }
 556 }
 557
 558 #[derive(Debug)]
 559 struct ImplMethod<'tcx> {
 560     method: Rc<ty::Method<'tcx>>,
 561     substs: &'tcx Substs<'tcx>,
 562     is_provided: bool,
 563 }
 564
 565 /// Locates the applicable definition of a method, given its name.
 566 fn get_impl_method<'a, 'tcx>(
 567     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 568     substs: &'tcx Substs<'tcx>,
 569     impl_def_id: DefId,
 570     impl_substs: &'tcx Substs<'tcx>,
 571     name: ast::Name,
 572 ) -> ImplMethod<'tcx> {
 573     assert!(!substs.types.needs_infer());
 574
 575     let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap();
 576     let trait_def = tcx.lookup_trait_def(trait_def_id);
 577
 578     match trait_def.ancestors(impl_def_id).fn_defs(tcx, name).next() {
 579         Some(node_item) => {
 580             let substs = tcx.normalizing_infer_ctxt(Reveal::All).enter(|infcx| {
 581                 let substs = substs.rebase_onto(tcx, trait_def_id, impl_substs);
 582                 let substs = traits::translate_substs(&infcx, impl_def_id,
 583                                                       substs, node_item.node);
 584                 tcx.lift(&substs).unwrap_or_else(|| {
 585                     bug!("trans::meth::get_impl_method: translate_substs \
 586                           returned {:?} which contains inference types/regions",
 587                          substs);
 588                 })
 589             });
 590             ImplMethod {
 591                 method: node_item.item,
 592                 substs: substs,
 593                 is_provided: node_item.node.is_from_trait(),
 594             }
 595         }
 596         None => {
 597             bug!("method {:?} not found in {:?}", name, impl_def_id)
 598         }
 599     }
 600 }