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