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