src/librustc_driver/test.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 //! # Standalone Tests for the Inference Module
  12
  13 use std::path::PathBuf;
  14 use std::sync::mpsc;
  15
  16 use driver;
  17 use rustc_lint;
  18 use rustc_resolve::MakeGlobMap;
  19 use rustc::middle::region;
  20 use rustc::ty::subst::Subst;
  21 use rustc::traits::ObligationCause;
  22 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
  23 use rustc::ty::query::OnDiskCache;
  24 use rustc::infer::{self, InferOk, InferResult};
  25 use rustc::infer::outlives::env::OutlivesEnvironment;
  26 use rustc::infer::type_variable::TypeVariableOrigin;
  27 use rustc_metadata::cstore::CStore;
  28 use rustc::hir::map as hir_map;
  29 use rustc::session::{self, config};
  30 use rustc::session::config::{OutputFilenames, OutputTypes};
  31 use rustc_data_structures::sync::{self, Lrc};
  32 use syntax;
  33 use syntax::ast;
  34 use rustc_target::spec::abi::Abi;
  35 use syntax::codemap::{CodeMap, FilePathMapping, FileName};
  36 use errors;
  37 use errors::emitter::Emitter;
  38 use errors::{Level, DiagnosticBuilder};
  39 use syntax::feature_gate::UnstableFeatures;
  40 use syntax::symbol::Symbol;
  41 use syntax_pos::DUMMY_SP;
  42
  43 use rustc::hir;
  44
  45 struct Env<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
  46     infcx: &'a infer::InferCtxt<'a, 'gcx, 'tcx>,
  47     region_scope_tree: &'a mut region::ScopeTree,
  48     param_env: ty::ParamEnv<'tcx>,
  49 }
  50
  51 struct RH<'a> {
  52     id: hir::ItemLocalId,
  53     sub: &'a [RH<'a>],
  54 }
  55
  56 const EMPTY_SOURCE_STR: &'static str = "#![feature(no_core)] #![no_core]";
  57
  58 struct ExpectErrorEmitter {
  59     messages: Vec<String>,
  60 }
  61
  62 fn remove_message(e: &mut ExpectErrorEmitter, msg: &str, lvl: Level) {
  63     match lvl {
  64         Level::Bug | Level::Fatal | Level::Error => {}
  65         _ => {
  66             return;
  67         }
  68     }
  69
  70     debug!("Error: {}", msg);
  71     match e.messages.iter().position(|m| msg.contains(m)) {
  72         Some(i) => {
  73             e.messages.remove(i);
  74         }
  75         None => {
  76             debug!("Unexpected error: {} Expected: {:?}", msg, e.messages);
  77             panic!("Unexpected error: {} Expected: {:?}", msg, e.messages);
  78         }
  79     }
  80 }
  81
  82 impl Emitter for ExpectErrorEmitter {
  83     fn emit(&mut self, db: &DiagnosticBuilder) {
  84         remove_message(self, &db.message(), db.level);
  85         for child in &db.children {
  86             remove_message(self, &child.message(), child.level);
  87         }
  88     }
  89 }
  90
  91 fn errors(msgs: &[&str]) -> (Box<dyn Emitter + sync::Send>, usize) {
  92     let v = msgs.iter().map(|m| m.to_string()).collect();
  93     (box ExpectErrorEmitter { messages: v } as Box<dyn Emitter + sync::Send>, msgs.len())
  94 }
  95
  96 fn test_env<F>(source_string: &str,
  97                args: (Box<dyn Emitter + sync::Send>, usize),
  98                body: F)
  99     where F: FnOnce(Env)
 100 {
 101     syntax::with_globals(|| {
 102         let mut options = config::basic_options();
 103         options.debugging_opts.verbose = true;
 104         options.unstable_features = UnstableFeatures::Allow;
 105
 106         driver::spawn_thread_pool(options, |options| {
 107             test_env_with_pool(options, source_string, args, body)
 108         })
 109     });
 110 }
 111
 112 fn test_env_with_pool<F>(
 113     options: config::Options,
 114     source_string: &str,
 115     (emitter, expected_err_count): (Box<dyn Emitter + sync::Send>, usize),
 116     body: F
 117 )
 118     where F: FnOnce(Env)
 119 {
 120     let diagnostic_handler = errors::Handler::with_emitter(true, false, emitter);
 121     let sess = session::build_session_(options,
 122                                        None,
 123                                        diagnostic_handler,
 124                                        Lrc::new(CodeMap::new(FilePathMapping::empty())));
 125     let cstore = CStore::new(::get_codegen_backend(&sess).metadata_loader());
 126     rustc_lint::register_builtins(&mut sess.lint_store.borrow_mut(), Some(&sess));
 127     let input = config::Input::Str {
 128         name: FileName::Anon,
 129         input: source_string.to_string(),
 130     };
 131     let krate = driver::phase_1_parse_input(&driver::CompileController::basic(),
 132                                             &sess,
 133                                             &input).unwrap();
 134     let driver::ExpansionResult { defs, resolutions, mut hir_forest, .. } = {
 135         driver::phase_2_configure_and_expand(&sess,
 136                                              &cstore,
 137                                              krate,
 138                                              None,
 139                                              "test",
 140                                              None,
 141                                              MakeGlobMap::No,
 142                                              |_| Ok(()))
 143             .expect("phase 2 aborted")
 144     };
 145
 146     let arenas = ty::AllArenas::new();
 147     let hir_map = hir_map::map_crate(&sess, &cstore, &mut hir_forest, &defs);
 148
 149     // run just enough stuff to build a tcx:
 150     let (tx, _rx) = mpsc::channel();
 151     let outputs = OutputFilenames {
 152         out_directory: PathBuf::new(),
 153         out_filestem: String::new(),
 154         single_output_file: None,
 155         extra: String::new(),
 156         outputs: OutputTypes::new(&[]),
 157     };
 158     TyCtxt::create_and_enter(&sess,
 159                              &cstore,
 160                              ty::query::Providers::default(),
 161                              ty::query::Providers::default(),
 162                              &arenas,
 163                              resolutions,
 164                              hir_map,
 165                              OnDiskCache::new_empty(sess.codemap()),
 166                              "test_crate",
 167                              tx,
 168                              &outputs,
 169                              |tcx| {
 170         tcx.infer_ctxt().enter(|infcx| {
 171             let mut region_scope_tree = region::ScopeTree::default();
 172             let param_env = ty::ParamEnv::empty();
 173             body(Env {
 174                 infcx: &infcx,
 175                 region_scope_tree: &mut region_scope_tree,
 176                 param_env: param_env,
 177             });
 178             let outlives_env = OutlivesEnvironment::new(param_env);
 179             let def_id = tcx.hir.local_def_id(ast::CRATE_NODE_ID);
 180             infcx.resolve_regions_and_report_errors(def_id, &region_scope_tree, &outlives_env);
 181             assert_eq!(tcx.sess.err_count(), expected_err_count);
 182         });
 183     });
 184 }
 185
 186 const D1: ty::DebruijnIndex = ty::INNERMOST;
 187 const D2: ty::DebruijnIndex = D1.shifted_in(1);
 188
 189 impl<'a, 'gcx, 'tcx> Env<'a, 'gcx, 'tcx> {
 190     pub fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
 191         self.infcx.tcx
 192     }
 193
 194     pub fn create_region_hierarchy(&mut self, rh: &RH,
 195                                    parent: (region::Scope, region::ScopeDepth)) {
 196         let me = region::Scope::Node(rh.id);
 197         self.region_scope_tree.record_scope_parent(me, Some(parent));
 198         for child_rh in rh.sub {
 199             self.create_region_hierarchy(child_rh, (me, parent.1 + 1));
 200         }
 201     }
 202
 203     pub fn create_simple_region_hierarchy(&mut self) {
 204         // creates a region hierarchy where 1 is root, 10 and 11 are
 205         // children of 1, etc
 206
 207         let dscope = region::Scope::Destruction(hir::ItemLocalId(1));
 208         self.region_scope_tree.record_scope_parent(dscope, None);
 209         self.create_region_hierarchy(&RH {
 210             id: hir::ItemLocalId(1),
 211             sub: &[RH {
 212                 id: hir::ItemLocalId(10),
 213                 sub: &[],
 214             },
 215             RH {
 216                 id: hir::ItemLocalId(11),
 217                 sub: &[],
 218             }],
 219         }, (dscope, 1));
 220     }
 221
 222     #[allow(dead_code)] // this seems like it could be useful, even if we don't use it now
 223     pub fn lookup_item(&self, names: &[String]) -> ast::NodeId {
 224         return match search_mod(self, &self.infcx.tcx.hir.krate().module, 0, names) {
 225             Some(id) => id,
 226             None => {
 227                 panic!("no item found: `{}`", names.join("::"));
 228             }
 229         };
 230
 231         fn search_mod(this: &Env,
 232                       m: &hir::Mod,
 233                       idx: usize,
 234                       names: &[String])
 235                       -> Option<ast::NodeId> {
 236             assert!(idx < names.len());
 237             for item in &m.item_ids {
 238                 let item = this.infcx.tcx.hir.expect_item(item.id);
 239                 if item.name.to_string() == names[idx] {
 240                     return search(this, item, idx + 1, names);
 241                 }
 242             }
 243             return None;
 244         }
 245
 246         fn search(this: &Env, it: &hir::Item, idx: usize, names: &[String]) -> Option<ast::NodeId> {
 247             if idx == names.len() {
 248                 return Some(it.id);
 249             }
 250
 251             return match it.node {
 252                 hir::ItemKind::Use(..) |
 253                 hir::ItemKind::ExternCrate(..) |
 254                 hir::ItemKind::Const(..) |
 255                 hir::ItemKind::Static(..) |
 256                 hir::ItemKind::Fn(..) |
 257                 hir::ItemKind::ForeignMod(..) |
 258                 hir::ItemKind::GlobalAsm(..) |
 259                 hir::ItemKind::Existential(..) |
 260                 hir::ItemKind::Ty(..) => None,
 261
 262                 hir::ItemKind::Enum(..) |
 263                 hir::ItemKind::Struct(..) |
 264                 hir::ItemKind::Union(..) |
 265                 hir::ItemKind::Trait(..) |
 266                 hir::ItemKind::TraitAlias(..) |
 267                 hir::ItemKind::Impl(..) => None,
 268
 269                 hir::ItemKind::Mod(ref m) => search_mod(this, m, idx, names),
 270             };
 271         }
 272     }
 273
 274     pub fn make_subtype(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
 275         match self.infcx.at(&ObligationCause::dummy(), self.param_env).sub(a, b) {
 276             Ok(_) => true,
 277             Err(ref e) => panic!("Encountered error: {}", e),
 278         }
 279     }
 280
 281     pub fn is_subtype(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
 282         self.infcx.can_sub(self.param_env, a, b).is_ok()
 283     }
 284
 285     pub fn assert_subtype(&self, a: Ty<'tcx>, b: Ty<'tcx>) {
 286         if !self.is_subtype(a, b) {
 287             panic!("{} is not a subtype of {}, but it should be", a, b);
 288         }
 289     }
 290
 291     pub fn assert_eq(&self, a: Ty<'tcx>, b: Ty<'tcx>) {
 292         self.assert_subtype(a, b);
 293         self.assert_subtype(b, a);
 294     }
 295
 296     pub fn t_fn(&self, input_tys: &[Ty<'tcx>], output_ty: Ty<'tcx>) -> Ty<'tcx> {
 297         self.infcx.tcx.mk_fn_ptr(ty::Binder::bind(self.infcx.tcx.mk_fn_sig(
 298             input_tys.iter().cloned(),
 299             output_ty,
 300             false,
 301             hir::Unsafety::Normal,
 302             Abi::Rust
 303         )))
 304     }
 305
 306     pub fn t_nil(&self) -> Ty<'tcx> {
 307         self.infcx.tcx.mk_nil()
 308     }
 309
 310     pub fn t_pair(&self, ty1: Ty<'tcx>, ty2: Ty<'tcx>) -> Ty<'tcx> {
 311         self.infcx.tcx.intern_tup(&[ty1, ty2])
 312     }
 313
 314     pub fn t_param(&self, index: u32) -> Ty<'tcx> {
 315         let name = format!("T{}", index);
 316         self.infcx.tcx.mk_ty_param(index, Symbol::intern(&name).as_interned_str())
 317     }
 318
 319     pub fn re_early_bound(&self, index: u32, name: &'static str) -> ty::Region<'tcx> {
 320         let name = Symbol::intern(name).as_interned_str();
 321         self.infcx.tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
 322             def_id: self.infcx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
 323             index,
 324             name,
 325         }))
 326     }
 327
 328     pub fn re_late_bound_with_debruijn(&self,
 329                                        id: u32,
 330                                        debruijn: ty::DebruijnIndex)
 331                                        -> ty::Region<'tcx> {
 332         self.infcx.tcx.mk_region(ty::ReLateBound(debruijn, ty::BrAnon(id)))
 333     }
 334
 335     pub fn t_rptr(&self, r: ty::Region<'tcx>) -> Ty<'tcx> {
 336         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
 337     }
 338
 339     pub fn t_rptr_late_bound(&self, id: u32) -> Ty<'tcx> {
 340         let r = self.re_late_bound_with_debruijn(id, D1);
 341         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
 342     }
 343
 344     pub fn t_rptr_late_bound_with_debruijn(&self,
 345                                            id: u32,
 346                                            debruijn: ty::DebruijnIndex)
 347                                            -> Ty<'tcx> {
 348         let r = self.re_late_bound_with_debruijn(id, debruijn);
 349         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
 350     }
 351
 352     pub fn t_rptr_scope(&self, id: u32) -> Ty<'tcx> {
 353         let r = ty::ReScope(region::Scope::Node(hir::ItemLocalId(id)));
 354         self.infcx.tcx.mk_imm_ref(self.infcx.tcx.mk_region(r), self.tcx().types.isize)
 355     }
 356
 357     pub fn re_free(&self, id: u32) -> ty::Region<'tcx> {
 358         self.infcx.tcx.mk_region(ty::ReFree(ty::FreeRegion {
 359             scope: self.infcx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
 360             bound_region: ty::BrAnon(id),
 361         }))
 362     }
 363
 364     pub fn t_rptr_free(&self, id: u32) -> Ty<'tcx> {
 365         let r = self.re_free(id);
 366         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
 367     }
 368
 369     pub fn sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) -> InferResult<'tcx, ()> {
 370         self.infcx.at(&ObligationCause::dummy(), self.param_env).sub(t1, t2)
 371     }
 372
 373     /// Checks that `t1 <: t2` is true (this may register additional
 374     /// region checks).
 375     pub fn check_sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) {
 376         match self.sub(t1, t2) {
 377             Ok(InferOk { obligations, value: () }) => {
 378                 // None of these tests should require nested obligations:
 379                 assert!(obligations.is_empty());
 380             }
 381             Err(ref e) => {
 382                 panic!("unexpected error computing sub({:?},{:?}): {}", t1, t2, e);
 383             }
 384         }
 385     }
 386
 387     /// Checks that `t1 <: t2` is false (this may register additional
 388     /// region checks).
 389     pub fn check_not_sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) {
 390         match self.sub(t1, t2) {
 391             Err(_) => {}
 392             Ok(_) => {
 393                 panic!("unexpected success computing sub({:?},{:?})", t1, t2);
 394             }
 395         }
 396     }
 397 }
 398
 399 #[test]
 400 fn contravariant_region_ptr_ok() {
 401     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 402         env.create_simple_region_hierarchy();
 403         let t_rptr1 = env.t_rptr_scope(1);
 404         let t_rptr10 = env.t_rptr_scope(10);
 405         env.assert_eq(t_rptr1, t_rptr1);
 406         env.assert_eq(t_rptr10, t_rptr10);
 407         env.make_subtype(t_rptr1, t_rptr10);
 408     })
 409 }
 410
 411 #[test]
 412 fn contravariant_region_ptr_err() {
 413     test_env(EMPTY_SOURCE_STR, errors(&["mismatched types"]), |mut env| {
 414         env.create_simple_region_hierarchy();
 415         let t_rptr1 = env.t_rptr_scope(1);
 416         let t_rptr10 = env.t_rptr_scope(10);
 417         env.assert_eq(t_rptr1, t_rptr1);
 418         env.assert_eq(t_rptr10, t_rptr10);
 419
 420         // will cause an error when regions are resolved
 421         env.make_subtype(t_rptr10, t_rptr1);
 422     })
 423 }
 424
 425 #[test]
 426 fn sub_free_bound_false() {
 427     //! Test that:
 428     //!
 429     //!     fn(&'a isize) <: for<'b> fn(&'b isize)
 430     //!
 431     //! does NOT hold.
 432
 433     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 434         env.create_simple_region_hierarchy();
 435         let t_rptr_free1 = env.t_rptr_free(1);
 436         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 437         env.check_not_sub(env.t_fn(&[t_rptr_free1], env.tcx().types.isize),
 438                           env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 439     })
 440 }
 441
 442 #[test]
 443 fn sub_bound_free_true() {
 444     //! Test that:
 445     //!
 446     //!     for<'a> fn(&'a isize) <: fn(&'b isize)
 447     //!
 448     //! DOES hold.
 449
 450     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 451         env.create_simple_region_hierarchy();
 452         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 453         let t_rptr_free1 = env.t_rptr_free(1);
 454         env.check_sub(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 455                       env.t_fn(&[t_rptr_free1], env.tcx().types.isize));
 456     })
 457 }
 458
 459 #[test]
 460 fn sub_free_bound_false_infer() {
 461     //! Test that:
 462     //!
 463     //!     fn(_#1) <: for<'b> fn(&'b isize)
 464     //!
 465     //! does NOT hold for any instantiation of `_#1`.
 466
 467     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 468         let t_infer1 = env.infcx.next_ty_var(TypeVariableOrigin::MiscVariable(DUMMY_SP));
 469         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 470         env.check_not_sub(env.t_fn(&[t_infer1], env.tcx().types.isize),
 471                           env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 472     })
 473 }
 474
 475 /// Test substituting a bound region into a function, which introduces another level of binding.
 476 /// This requires adjusting the Debruijn index.
 477 #[test]
 478 fn subst_ty_renumber_bound() {
 479
 480     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 481         // Situation:
 482         // Theta = [A -> &'a foo]
 483
 484         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 485
 486         // t_source = fn(A)
 487         let t_source = {
 488             let t_param = env.t_param(0);
 489             env.t_fn(&[t_param], env.t_nil())
 490         };
 491
 492         let substs = env.infcx.tcx.intern_substs(&[t_rptr_bound1.into()]);
 493         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 494
 495         // t_expected = fn(&'a isize)
 496         let t_expected = {
 497             let t_ptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, D2);
 498             env.t_fn(&[t_ptr_bound2], env.t_nil())
 499         };
 500
 501         debug!("subst_bound: t_source={:?} substs={:?} t_substituted={:?} t_expected={:?}",
 502                t_source,
 503                substs,
 504                t_substituted,
 505                t_expected);
 506
 507         assert_eq!(t_substituted, t_expected);
 508     })
 509 }
 510
 511 /// Test substituting a bound region into a function, which introduces another level of binding.
 512 /// This requires adjusting the Debruijn index.
 513 #[test]
 514 fn subst_ty_renumber_some_bounds() {
 515     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 516         // Situation:
 517         // Theta = [A -> &'a foo]
 518
 519         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 520
 521         // t_source = (A, fn(A))
 522         let t_source = {
 523             let t_param = env.t_param(0);
 524             env.t_pair(t_param, env.t_fn(&[t_param], env.t_nil()))
 525         };
 526
 527         let substs = env.infcx.tcx.intern_substs(&[t_rptr_bound1.into()]);
 528         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 529
 530         // t_expected = (&'a isize, fn(&'a isize))
 531         //
 532         // but not that the Debruijn index is different in the different cases.
 533         let t_expected = {
 534             let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, D2);
 535             env.t_pair(t_rptr_bound1, env.t_fn(&[t_rptr_bound2], env.t_nil()))
 536         };
 537
 538         debug!("subst_bound: t_source={:?} substs={:?} t_substituted={:?} t_expected={:?}",
 539                t_source,
 540                substs,
 541                t_substituted,
 542                t_expected);
 543
 544         assert_eq!(t_substituted, t_expected);
 545     })
 546 }
 547
 548 /// Test that we correctly compute whether a type has escaping regions or not.
 549 #[test]
 550 fn escaping() {
 551
 552     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 553         // Situation:
 554         // Theta = [A -> &'a foo]
 555         env.create_simple_region_hierarchy();
 556
 557         assert!(!env.t_nil().has_escaping_regions());
 558
 559         let t_rptr_free1 = env.t_rptr_free(1);
 560         assert!(!t_rptr_free1.has_escaping_regions());
 561
 562         let t_rptr_bound1 = env.t_rptr_late_bound_with_debruijn(1, D1);
 563         assert!(t_rptr_bound1.has_escaping_regions());
 564
 565         let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, D2);
 566         assert!(t_rptr_bound2.has_escaping_regions());
 567
 568         // t_fn = fn(A)
 569         let t_param = env.t_param(0);
 570         assert!(!t_param.has_escaping_regions());
 571         let t_fn = env.t_fn(&[t_param], env.t_nil());
 572         assert!(!t_fn.has_escaping_regions());
 573     })
 574 }
 575
 576 /// Test applying a substitution where the value being substituted for an early-bound region is a
 577 /// late-bound region.
 578 #[test]
 579 fn subst_region_renumber_region() {
 580     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 581         let re_bound1 = env.re_late_bound_with_debruijn(1, D1);
 582
 583         // type t_source<'a> = fn(&'a isize)
 584         let t_source = {
 585             let re_early = env.re_early_bound(0, "'a");
 586             env.t_fn(&[env.t_rptr(re_early)], env.t_nil())
 587         };
 588
 589         let substs = env.infcx.tcx.intern_substs(&[re_bound1.into()]);
 590         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 591
 592         // t_expected = fn(&'a isize)
 593         //
 594         // but not that the Debruijn index is different in the different cases.
 595         let t_expected = {
 596             let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, D2);
 597             env.t_fn(&[t_rptr_bound2], env.t_nil())
 598         };
 599
 600         debug!("subst_bound: t_source={:?} substs={:?} t_substituted={:?} t_expected={:?}",
 601                t_source,
 602                substs,
 603                t_substituted,
 604                t_expected);
 605
 606         assert_eq!(t_substituted, t_expected);
 607     })
 608 }
 609
 610 #[test]
 611 fn walk_ty() {
 612     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 613         let tcx = env.infcx.tcx;
 614         let int_ty = tcx.types.isize;
 615         let usize_ty = tcx.types.usize;
 616         let tup1_ty = tcx.intern_tup(&[int_ty, usize_ty, int_ty, usize_ty]);
 617         let tup2_ty = tcx.intern_tup(&[tup1_ty, tup1_ty, usize_ty]);
 618         let walked: Vec<_> = tup2_ty.walk().collect();
 619         assert_eq!(walked,
 620                    [tup2_ty, tup1_ty, int_ty, usize_ty, int_ty, usize_ty, tup1_ty, int_ty,
 621                     usize_ty, int_ty, usize_ty, usize_ty]);
 622     })
 623 }
 624
 625 #[test]
 626 fn walk_ty_skip_subtree() {
 627     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 628         let tcx = env.infcx.tcx;
 629         let int_ty = tcx.types.isize;
 630         let usize_ty = tcx.types.usize;
 631         let tup1_ty = tcx.intern_tup(&[int_ty, usize_ty, int_ty, usize_ty]);
 632         let tup2_ty = tcx.intern_tup(&[tup1_ty, tup1_ty, usize_ty]);
 633
 634         // types we expect to see (in order), plus a boolean saying
 635         // whether to skip the subtree.
 636         let mut expected = vec![(tup2_ty, false),
 637                                 (tup1_ty, false),
 638                                 (int_ty, false),
 639                                 (usize_ty, false),
 640                                 (int_ty, false),
 641                                 (usize_ty, false),
 642                                 (tup1_ty, true), // skip the isize/usize/isize/usize
 643                                 (usize_ty, false)];
 644         expected.reverse();
 645
 646         let mut walker = tup2_ty.walk();
 647         while let Some(t) = walker.next() {
 648             debug!("walked to {:?}", t);
 649             let (expected_ty, skip) = expected.pop().unwrap();
 650             assert_eq!(t, expected_ty);
 651             if skip {
 652                 walker.skip_current_subtree();
 653             }
 654         }
 655
 656         assert!(expected.is_empty());
 657     })
 658 }