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 driver;
  14 use rustc::dep_graph::DepGraph;
  15 use rustc_lint;
  16 use rustc_resolve::MakeGlobMap;
  17 use rustc::middle::lang_items;
  18 use rustc::middle::free_region::FreeRegionMap;
  19 use rustc::middle::region::{CodeExtent, RegionMaps};
  20 use rustc::middle::resolve_lifetime;
  21 use rustc::middle::stability;
  22 use rustc::ty::subst::{Kind, Subst};
  23 use rustc::traits::{ObligationCause, Reveal};
  24 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
  25 use rustc::infer::{self, InferOk, InferResult};
  26 use rustc::infer::type_variable::TypeVariableOrigin;
  27 use rustc_metadata::cstore::CStore;
  28 use rustc::hir::map as hir_map;
  29 use rustc::mir::transform::Passes;
  30 use rustc::session::{self, config};
  31 use std::rc::Rc;
  32 use syntax::ast;
  33 use syntax::abi::Abi;
  34 use syntax::codemap::{CodeMap, FilePathMapping};
  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 use arena::DroplessArena;
  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_maps: &'a mut RegionMaps,
  48 }
  49
  50 struct RH<'a> {
  51     id: ast::NodeId,
  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 dep_graph = DepGraph::new(false);
 106     let _ignore = dep_graph.in_ignore();
 107     let cstore = Rc::new(CStore::new(&dep_graph));
 108     let sess = session::build_session_(options,
 109                                        &dep_graph,
 110                                        None,
 111                                        diagnostic_handler,
 112                                        Rc::new(CodeMap::new(FilePathMapping::empty())),
 113                                        cstore.clone());
 114     rustc_lint::register_builtins(&mut sess.lint_store.borrow_mut(), Some(&sess));
 115     let input = config::Input::Str {
 116         name: driver::anon_src(),
 117         input: source_string.to_string(),
 118     };
 119     let krate = driver::phase_1_parse_input(&sess, &input).unwrap();
 120     let driver::ExpansionResult { defs, resolutions, mut hir_forest, .. } = {
 121         driver::phase_2_configure_and_expand(&sess,
 122                                              &cstore,
 123                                              krate,
 124                                              None,
 125                                              "test",
 126                                              None,
 127                                              MakeGlobMap::No,
 128                                              |_| Ok(()))
 129             .expect("phase 2 aborted")
 130     };
 131     let _ignore = dep_graph.in_ignore();
 132
 133     let arena = DroplessArena::new();
 134     let arenas = ty::GlobalArenas::new();
 135     let hir_map = hir_map::map_crate(&mut hir_forest, defs);
 136
 137     // run just enough stuff to build a tcx:
 138     let lang_items = lang_items::collect_language_items(&sess, &hir_map);
 139     let named_region_map = resolve_lifetime::krate(&sess, &hir_map);
 140     let index = stability::Index::new(&sess);
 141     TyCtxt::create_and_enter(&sess,
 142                              ty::maps::Providers::default(),
 143                              ty::maps::Providers::default(),
 144                              Rc::new(Passes::new()),
 145                              &arenas,
 146                              &arena,
 147                              resolutions,
 148                              named_region_map.unwrap(),
 149                              hir_map,
 150                              lang_items,
 151                              index,
 152                              "test_crate",
 153                              |tcx| {
 154         tcx.infer_ctxt((), Reveal::UserFacing).enter(|infcx| {
 155             let mut region_maps = RegionMaps::new();
 156             body(Env { infcx: &infcx, region_maps: &mut region_maps });
 157             let free_regions = FreeRegionMap::new();
 158             let def_id = tcx.hir.local_def_id(ast::CRATE_NODE_ID);
 159             infcx.resolve_regions_and_report_errors(def_id, &region_maps, &free_regions);
 160             assert_eq!(tcx.sess.err_count(), expected_err_count);
 161         });
 162     });
 163 }
 164
 165 impl<'a, 'gcx, 'tcx> Env<'a, 'gcx, 'tcx> {
 166     pub fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
 167         self.infcx.tcx
 168     }
 169
 170     pub fn create_region_hierarchy(&mut self, rh: &RH, parent: CodeExtent) {
 171         let me = CodeExtent::Misc(rh.id);
 172         self.region_maps.record_code_extent(me, Some(parent));
 173         for child_rh in rh.sub {
 174             self.create_region_hierarchy(child_rh, me);
 175         }
 176     }
 177
 178     pub fn create_simple_region_hierarchy(&mut self) {
 179         // creates a region hierarchy where 1 is root, 10 and 11 are
 180         // children of 1, etc
 181
 182         let node = ast::NodeId::from_u32;
 183         let dscope = CodeExtent::DestructionScope(node(1));
 184         self.region_maps.record_code_extent(dscope, None);
 185         self.create_region_hierarchy(&RH {
 186                                          id: node(1),
 187                                          sub: &[RH {
 188                                                     id: node(10),
 189                                                     sub: &[],
 190                                                 },
 191                                                 RH {
 192                                                     id: node(11),
 193                                                     sub: &[],
 194                                                 }],
 195                                      },
 196                                      dscope);
 197     }
 198
 199     #[allow(dead_code)] // this seems like it could be useful, even if we don't use it now
 200     pub fn lookup_item(&self, names: &[String]) -> ast::NodeId {
 201         return match search_mod(self, &self.infcx.tcx.hir.krate().module, 0, names) {
 202             Some(id) => id,
 203             None => {
 204                 panic!("no item found: `{}`", names.join("::"));
 205             }
 206         };
 207
 208         fn search_mod(this: &Env,
 209                       m: &hir::Mod,
 210                       idx: usize,
 211                       names: &[String])
 212                       -> Option<ast::NodeId> {
 213             assert!(idx < names.len());
 214             for item in &m.item_ids {
 215                 let item = this.infcx.tcx.hir.expect_item(item.id);
 216                 if item.name.to_string() == names[idx] {
 217                     return search(this, item, idx + 1, names);
 218                 }
 219             }
 220             return None;
 221         }
 222
 223         fn search(this: &Env, it: &hir::Item, idx: usize, names: &[String]) -> Option<ast::NodeId> {
 224             if idx == names.len() {
 225                 return Some(it.id);
 226             }
 227
 228             return match it.node {
 229                 hir::ItemUse(..) |
 230                 hir::ItemExternCrate(..) |
 231                 hir::ItemConst(..) |
 232                 hir::ItemStatic(..) |
 233                 hir::ItemFn(..) |
 234                 hir::ItemForeignMod(..) |
 235                 hir::ItemGlobalAsm(..) |
 236                 hir::ItemTy(..) => None,
 237
 238                 hir::ItemEnum(..) |
 239                 hir::ItemStruct(..) |
 240                 hir::ItemUnion(..) |
 241                 hir::ItemTrait(..) |
 242                 hir::ItemImpl(..) |
 243                 hir::ItemDefaultImpl(..) => None,
 244
 245                 hir::ItemMod(ref m) => search_mod(this, m, idx, names),
 246             };
 247         }
 248     }
 249
 250     pub fn make_subtype(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
 251         match self.infcx.sub_types(true, &ObligationCause::dummy(), a, b) {
 252             Ok(_) => true,
 253             Err(ref e) => panic!("Encountered error: {}", e),
 254         }
 255     }
 256
 257     pub fn is_subtype(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
 258         self.infcx.can_sub_types(a, b).is_ok()
 259     }
 260
 261     pub fn assert_subtype(&self, a: Ty<'tcx>, b: Ty<'tcx>) {
 262         if !self.is_subtype(a, b) {
 263             panic!("{} is not a subtype of {}, but it should be", a, b);
 264         }
 265     }
 266
 267     pub fn assert_eq(&self, a: Ty<'tcx>, b: Ty<'tcx>) {
 268         self.assert_subtype(a, b);
 269         self.assert_subtype(b, a);
 270     }
 271
 272     pub fn t_fn(&self, input_tys: &[Ty<'tcx>], output_ty: Ty<'tcx>) -> Ty<'tcx> {
 273         self.infcx.tcx.mk_fn_ptr(ty::Binder(self.infcx.tcx.mk_fn_sig(
 274             input_tys.iter().cloned(),
 275             output_ty,
 276             false,
 277             hir::Unsafety::Normal,
 278             Abi::Rust
 279         )))
 280     }
 281
 282     pub fn t_nil(&self) -> Ty<'tcx> {
 283         self.infcx.tcx.mk_nil()
 284     }
 285
 286     pub fn t_pair(&self, ty1: Ty<'tcx>, ty2: Ty<'tcx>) -> Ty<'tcx> {
 287         self.infcx.tcx.intern_tup(&[ty1, ty2], false)
 288     }
 289
 290     pub fn t_param(&self, index: u32) -> Ty<'tcx> {
 291         let name = format!("T{}", index);
 292         self.infcx.tcx.mk_param(index, Symbol::intern(&name))
 293     }
 294
 295     pub fn re_early_bound(&self, index: u32, name: &'static str) -> ty::Region<'tcx> {
 296         let name = Symbol::intern(name);
 297         self.infcx.tcx.mk_region(ty::ReEarlyBound(ty::EarlyBoundRegion {
 298             def_id: self.infcx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
 299             index,
 300             name,
 301         }))
 302     }
 303
 304     pub fn re_late_bound_with_debruijn(&self,
 305                                        id: u32,
 306                                        debruijn: ty::DebruijnIndex)
 307                                        -> ty::Region<'tcx> {
 308         self.infcx.tcx.mk_region(ty::ReLateBound(debruijn, ty::BrAnon(id)))
 309     }
 310
 311     pub fn t_rptr(&self, r: ty::Region<'tcx>) -> Ty<'tcx> {
 312         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
 313     }
 314
 315     pub fn t_rptr_late_bound(&self, id: u32) -> Ty<'tcx> {
 316         let r = self.re_late_bound_with_debruijn(id, ty::DebruijnIndex::new(1));
 317         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
 318     }
 319
 320     pub fn t_rptr_late_bound_with_debruijn(&self,
 321                                            id: u32,
 322                                            debruijn: ty::DebruijnIndex)
 323                                            -> Ty<'tcx> {
 324         let r = self.re_late_bound_with_debruijn(id, debruijn);
 325         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
 326     }
 327
 328     pub fn t_rptr_scope(&self, id: u32) -> Ty<'tcx> {
 329         let r = ty::ReScope(CodeExtent::Misc(ast::NodeId::from_u32(id)));
 330         self.infcx.tcx.mk_imm_ref(self.infcx.tcx.mk_region(r), self.tcx().types.isize)
 331     }
 332
 333     pub fn re_free(&self, id: u32) -> ty::Region<'tcx> {
 334         self.infcx.tcx.mk_region(ty::ReFree(ty::FreeRegion {
 335             scope: self.infcx.tcx.hir.local_def_id(ast::CRATE_NODE_ID),
 336             bound_region: ty::BrAnon(id),
 337         }))
 338     }
 339
 340     pub fn t_rptr_free(&self, id: u32) -> Ty<'tcx> {
 341         let r = self.re_free(id);
 342         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
 343     }
 344
 345     pub fn t_rptr_static(&self) -> Ty<'tcx> {
 346         self.infcx.tcx.mk_imm_ref(self.infcx.tcx.types.re_static,
 347                                   self.tcx().types.isize)
 348     }
 349
 350     pub fn t_rptr_empty(&self) -> Ty<'tcx> {
 351         self.infcx.tcx.mk_imm_ref(self.infcx.tcx.types.re_empty,
 352                                   self.tcx().types.isize)
 353     }
 354
 355     pub fn dummy_type_trace(&self) -> infer::TypeTrace<'tcx> {
 356         infer::TypeTrace::dummy(self.tcx())
 357     }
 358
 359     pub fn sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) -> InferResult<'tcx, Ty<'tcx>> {
 360         let trace = self.dummy_type_trace();
 361         self.infcx.sub(true, trace, &t1, &t2)
 362     }
 363
 364     pub fn lub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) -> InferResult<'tcx, Ty<'tcx>> {
 365         let trace = self.dummy_type_trace();
 366         self.infcx.lub(true, trace, &t1, &t2)
 367     }
 368
 369     pub fn glb(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) -> InferResult<'tcx, Ty<'tcx>> {
 370         let trace = self.dummy_type_trace();
 371         self.infcx.glb(true, trace, &t1, &t2)
 372     }
 373
 374     /// Checks that `t1 <: t2` is true (this may register additional
 375     /// region checks).
 376     pub fn check_sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) {
 377         match self.sub(t1, t2) {
 378             Ok(InferOk { obligations, .. }) => {
 379                 // None of these tests should require nested obligations:
 380                 assert!(obligations.is_empty());
 381             }
 382             Err(ref e) => {
 383                 panic!("unexpected error computing sub({:?},{:?}): {}", t1, t2, e);
 384             }
 385         }
 386     }
 387
 388     /// Checks that `t1 <: t2` is false (this may register additional
 389     /// region checks).
 390     pub fn check_not_sub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>) {
 391         match self.sub(t1, t2) {
 392             Err(_) => {}
 393             Ok(_) => {
 394                 panic!("unexpected success computing sub({:?},{:?})", t1, t2);
 395             }
 396         }
 397     }
 398
 399     /// Checks that `LUB(t1,t2) == t_lub`
 400     pub fn check_lub(&self, t1: Ty<'tcx>, t2: Ty<'tcx>, t_lub: Ty<'tcx>) {
 401         match self.lub(t1, t2) {
 402             Ok(InferOk { obligations, value: t }) => {
 403                 // None of these tests should require nested obligations:
 404                 assert!(obligations.is_empty());
 405
 406                 self.assert_eq(t, t_lub);
 407             }
 408             Err(ref e) => panic!("unexpected error in LUB: {}", e),
 409         }
 410     }
 411
 412     /// Checks that `GLB(t1,t2) == t_glb`
 413     pub fn check_glb(&self, t1: Ty<'tcx>, t2: Ty<'tcx>, t_glb: Ty<'tcx>) {
 414         debug!("check_glb(t1={}, t2={}, t_glb={})", t1, t2, t_glb);
 415         match self.glb(t1, t2) {
 416             Err(e) => panic!("unexpected error computing LUB: {:?}", e),
 417             Ok(InferOk { obligations, value: t }) => {
 418                 // None of these tests should require nested obligations:
 419                 assert!(obligations.is_empty());
 420
 421                 self.assert_eq(t, t_glb);
 422
 423                 // sanity check for good measure:
 424                 self.assert_subtype(t, t1);
 425                 self.assert_subtype(t, t2);
 426             }
 427         }
 428     }
 429 }
 430
 431 #[test]
 432 fn contravariant_region_ptr_ok() {
 433     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 434         env.create_simple_region_hierarchy();
 435         let t_rptr1 = env.t_rptr_scope(1);
 436         let t_rptr10 = env.t_rptr_scope(10);
 437         env.assert_eq(t_rptr1, t_rptr1);
 438         env.assert_eq(t_rptr10, t_rptr10);
 439         env.make_subtype(t_rptr1, t_rptr10);
 440     })
 441 }
 442
 443 #[test]
 444 fn contravariant_region_ptr_err() {
 445     test_env(EMPTY_SOURCE_STR, errors(&["mismatched types"]), |mut env| {
 446         env.create_simple_region_hierarchy();
 447         let t_rptr1 = env.t_rptr_scope(1);
 448         let t_rptr10 = env.t_rptr_scope(10);
 449         env.assert_eq(t_rptr1, t_rptr1);
 450         env.assert_eq(t_rptr10, t_rptr10);
 451
 452         // will cause an error when regions are resolved
 453         env.make_subtype(t_rptr10, t_rptr1);
 454     })
 455 }
 456
 457 #[test]
 458 fn sub_free_bound_false() {
 459     //! Test that:
 460     //!
 461     //!     fn(&'a isize) <: for<'b> fn(&'b isize)
 462     //!
 463     //! does NOT hold.
 464
 465     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 466         env.create_simple_region_hierarchy();
 467         let t_rptr_free1 = env.t_rptr_free(1);
 468         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 469         env.check_not_sub(env.t_fn(&[t_rptr_free1], env.tcx().types.isize),
 470                           env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 471     })
 472 }
 473
 474 #[test]
 475 fn sub_bound_free_true() {
 476     //! Test that:
 477     //!
 478     //!     for<'a> fn(&'a isize) <: fn(&'b isize)
 479     //!
 480     //! DOES hold.
 481
 482     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 483         env.create_simple_region_hierarchy();
 484         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 485         let t_rptr_free1 = env.t_rptr_free(1);
 486         env.check_sub(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 487                       env.t_fn(&[t_rptr_free1], env.tcx().types.isize));
 488     })
 489 }
 490
 491 #[test]
 492 fn sub_free_bound_false_infer() {
 493     //! Test that:
 494     //!
 495     //!     fn(_#1) <: for<'b> fn(&'b isize)
 496     //!
 497     //! does NOT hold for any instantiation of `_#1`.
 498
 499     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 500         let t_infer1 = env.infcx.next_ty_var(TypeVariableOrigin::MiscVariable(DUMMY_SP));
 501         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 502         env.check_not_sub(env.t_fn(&[t_infer1], env.tcx().types.isize),
 503                           env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 504     })
 505 }
 506
 507 #[test]
 508 fn lub_free_bound_infer() {
 509     //! Test result of:
 510     //!
 511     //!     LUB(fn(_#1), for<'b> fn(&'b isize))
 512     //!
 513     //! This should yield `fn(&'_ isize)`. We check
 514     //! that it yields `fn(&'x isize)` for some free `'x`,
 515     //! anyhow.
 516
 517     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 518         env.create_simple_region_hierarchy();
 519         let t_infer1 = env.infcx.next_ty_var(TypeVariableOrigin::MiscVariable(DUMMY_SP));
 520         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 521         let t_rptr_free1 = env.t_rptr_free(1);
 522         env.check_lub(env.t_fn(&[t_infer1], env.tcx().types.isize),
 523                       env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 524                       env.t_fn(&[t_rptr_free1], env.tcx().types.isize));
 525     });
 526 }
 527
 528 #[test]
 529 fn lub_bound_bound() {
 530     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 531         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 532         let t_rptr_bound2 = env.t_rptr_late_bound(2);
 533         env.check_lub(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 534                       env.t_fn(&[t_rptr_bound2], env.tcx().types.isize),
 535                       env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 536     })
 537 }
 538
 539 #[test]
 540 fn lub_bound_free() {
 541     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 542         env.create_simple_region_hierarchy();
 543         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 544         let t_rptr_free1 = env.t_rptr_free(1);
 545         env.check_lub(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 546                       env.t_fn(&[t_rptr_free1], env.tcx().types.isize),
 547                       env.t_fn(&[t_rptr_free1], env.tcx().types.isize));
 548     })
 549 }
 550
 551 #[test]
 552 fn lub_bound_static() {
 553     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 554         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 555         let t_rptr_static = env.t_rptr_static();
 556         env.check_lub(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 557                       env.t_fn(&[t_rptr_static], env.tcx().types.isize),
 558                       env.t_fn(&[t_rptr_static], env.tcx().types.isize));
 559     })
 560 }
 561
 562 #[test]
 563 fn lub_bound_bound_inverse_order() {
 564     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 565         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 566         let t_rptr_bound2 = env.t_rptr_late_bound(2);
 567         env.check_lub(env.t_fn(&[t_rptr_bound1, t_rptr_bound2], t_rptr_bound1),
 568                       env.t_fn(&[t_rptr_bound2, t_rptr_bound1], t_rptr_bound1),
 569                       env.t_fn(&[t_rptr_bound1, t_rptr_bound1], t_rptr_bound1));
 570     })
 571 }
 572
 573 #[test]
 574 fn lub_free_free() {
 575     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 576         env.create_simple_region_hierarchy();
 577         let t_rptr_free1 = env.t_rptr_free(1);
 578         let t_rptr_free2 = env.t_rptr_free(2);
 579         let t_rptr_static = env.t_rptr_static();
 580         env.check_lub(env.t_fn(&[t_rptr_free1], env.tcx().types.isize),
 581                       env.t_fn(&[t_rptr_free2], env.tcx().types.isize),
 582                       env.t_fn(&[t_rptr_static], env.tcx().types.isize));
 583     })
 584 }
 585
 586 #[test]
 587 fn lub_returning_scope() {
 588     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 589         env.create_simple_region_hierarchy();
 590         let t_rptr_scope10 = env.t_rptr_scope(10);
 591         let t_rptr_scope11 = env.t_rptr_scope(11);
 592         let t_rptr_empty = env.t_rptr_empty();
 593         env.check_lub(env.t_fn(&[t_rptr_scope10], env.tcx().types.isize),
 594                       env.t_fn(&[t_rptr_scope11], env.tcx().types.isize),
 595                       env.t_fn(&[t_rptr_empty], env.tcx().types.isize));
 596     });
 597 }
 598
 599 #[test]
 600 fn glb_free_free_with_common_scope() {
 601     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 602         env.create_simple_region_hierarchy();
 603         let t_rptr_free1 = env.t_rptr_free(1);
 604         let t_rptr_free2 = env.t_rptr_free(2);
 605         let t_rptr_scope = env.t_rptr_scope(1);
 606         env.check_glb(env.t_fn(&[t_rptr_free1], env.tcx().types.isize),
 607                       env.t_fn(&[t_rptr_free2], env.tcx().types.isize),
 608                       env.t_fn(&[t_rptr_scope], env.tcx().types.isize));
 609     })
 610 }
 611
 612 #[test]
 613 fn glb_bound_bound() {
 614     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 615         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 616         let t_rptr_bound2 = env.t_rptr_late_bound(2);
 617         env.check_glb(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 618                       env.t_fn(&[t_rptr_bound2], env.tcx().types.isize),
 619                       env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 620     })
 621 }
 622
 623 #[test]
 624 fn glb_bound_free() {
 625     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 626         env.create_simple_region_hierarchy();
 627         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 628         let t_rptr_free1 = env.t_rptr_free(1);
 629         env.check_glb(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 630                       env.t_fn(&[t_rptr_free1], env.tcx().types.isize),
 631                       env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 632     })
 633 }
 634
 635 #[test]
 636 fn glb_bound_free_infer() {
 637     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 638         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 639         let t_infer1 = env.infcx.next_ty_var(TypeVariableOrigin::MiscVariable(DUMMY_SP));
 640
 641         // compute GLB(fn(_) -> isize, for<'b> fn(&'b isize) -> isize),
 642         // which should yield for<'b> fn(&'b isize) -> isize
 643         env.check_glb(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 644                       env.t_fn(&[t_infer1], env.tcx().types.isize),
 645                       env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 646
 647         // as a side-effect, computing GLB should unify `_` with
 648         // `&'_ isize`
 649         let t_resolve1 = env.infcx.shallow_resolve(t_infer1);
 650         match t_resolve1.sty {
 651             ty::TyRef(..) => {}
 652             _ => {
 653                 panic!("t_resolve1={:?}", t_resolve1);
 654             }
 655         }
 656     })
 657 }
 658
 659 #[test]
 660 fn glb_bound_static() {
 661     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 662         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 663         let t_rptr_static = env.t_rptr_static();
 664         env.check_glb(env.t_fn(&[t_rptr_bound1], env.tcx().types.isize),
 665                       env.t_fn(&[t_rptr_static], env.tcx().types.isize),
 666                       env.t_fn(&[t_rptr_bound1], env.tcx().types.isize));
 667     })
 668 }
 669
 670 /// Test substituting a bound region into a function, which introduces another level of binding.
 671 /// This requires adjusting the Debruijn index.
 672 #[test]
 673 fn subst_ty_renumber_bound() {
 674
 675     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 676         // Situation:
 677         // Theta = [A -> &'a foo]
 678
 679         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 680
 681         // t_source = fn(A)
 682         let t_source = {
 683             let t_param = env.t_param(0);
 684             env.t_fn(&[t_param], env.t_nil())
 685         };
 686
 687         let substs = env.infcx.tcx.intern_substs(&[Kind::from(t_rptr_bound1)]);
 688         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 689
 690         // t_expected = fn(&'a isize)
 691         let t_expected = {
 692             let t_ptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(2));
 693             env.t_fn(&[t_ptr_bound2], env.t_nil())
 694         };
 695
 696         debug!("subst_bound: t_source={:?} substs={:?} t_substituted={:?} t_expected={:?}",
 697                t_source,
 698                substs,
 699                t_substituted,
 700                t_expected);
 701
 702         assert_eq!(t_substituted, t_expected);
 703     })
 704 }
 705
 706 /// Test substituting a bound region into a function, which introduces another level of binding.
 707 /// This requires adjusting the Debruijn index.
 708 #[test]
 709 fn subst_ty_renumber_some_bounds() {
 710     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 711         // Situation:
 712         // Theta = [A -> &'a foo]
 713
 714         let t_rptr_bound1 = env.t_rptr_late_bound(1);
 715
 716         // t_source = (A, fn(A))
 717         let t_source = {
 718             let t_param = env.t_param(0);
 719             env.t_pair(t_param, env.t_fn(&[t_param], env.t_nil()))
 720         };
 721
 722         let substs = env.infcx.tcx.intern_substs(&[Kind::from(t_rptr_bound1)]);
 723         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 724
 725         // t_expected = (&'a isize, fn(&'a isize))
 726         //
 727         // but not that the Debruijn index is different in the different cases.
 728         let t_expected = {
 729             let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(2));
 730             env.t_pair(t_rptr_bound1, env.t_fn(&[t_rptr_bound2], env.t_nil()))
 731         };
 732
 733         debug!("subst_bound: t_source={:?} substs={:?} t_substituted={:?} t_expected={:?}",
 734                t_source,
 735                substs,
 736                t_substituted,
 737                t_expected);
 738
 739         assert_eq!(t_substituted, t_expected);
 740     })
 741 }
 742
 743 /// Test that we correctly compute whether a type has escaping regions or not.
 744 #[test]
 745 fn escaping() {
 746
 747     test_env(EMPTY_SOURCE_STR, errors(&[]), |mut env| {
 748         // Situation:
 749         // Theta = [A -> &'a foo]
 750         env.create_simple_region_hierarchy();
 751
 752         assert!(!env.t_nil().has_escaping_regions());
 753
 754         let t_rptr_free1 = env.t_rptr_free(1);
 755         assert!(!t_rptr_free1.has_escaping_regions());
 756
 757         let t_rptr_bound1 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(1));
 758         assert!(t_rptr_bound1.has_escaping_regions());
 759
 760         let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(2));
 761         assert!(t_rptr_bound2.has_escaping_regions());
 762
 763         // t_fn = fn(A)
 764         let t_param = env.t_param(0);
 765         assert!(!t_param.has_escaping_regions());
 766         let t_fn = env.t_fn(&[t_param], env.t_nil());
 767         assert!(!t_fn.has_escaping_regions());
 768     })
 769 }
 770
 771 /// Test applying a substitution where the value being substituted for an early-bound region is a
 772 /// late-bound region.
 773 #[test]
 774 fn subst_region_renumber_region() {
 775     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 776         let re_bound1 = env.re_late_bound_with_debruijn(1, ty::DebruijnIndex::new(1));
 777
 778         // type t_source<'a> = fn(&'a isize)
 779         let t_source = {
 780             let re_early = env.re_early_bound(0, "'a");
 781             env.t_fn(&[env.t_rptr(re_early)], env.t_nil())
 782         };
 783
 784         let substs = env.infcx.tcx.intern_substs(&[Kind::from(re_bound1)]);
 785         let t_substituted = t_source.subst(env.infcx.tcx, substs);
 786
 787         // t_expected = fn(&'a isize)
 788         //
 789         // but not that the Debruijn index is different in the different cases.
 790         let t_expected = {
 791             let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(2));
 792             env.t_fn(&[t_rptr_bound2], env.t_nil())
 793         };
 794
 795         debug!("subst_bound: t_source={:?} substs={:?} t_substituted={:?} t_expected={:?}",
 796                t_source,
 797                substs,
 798                t_substituted,
 799                t_expected);
 800
 801         assert_eq!(t_substituted, t_expected);
 802     })
 803 }
 804
 805 #[test]
 806 fn walk_ty() {
 807     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 808         let tcx = env.infcx.tcx;
 809         let int_ty = tcx.types.isize;
 810         let uint_ty = tcx.types.usize;
 811         let tup1_ty = tcx.intern_tup(&[int_ty, uint_ty, int_ty, uint_ty], false);
 812         let tup2_ty = tcx.intern_tup(&[tup1_ty, tup1_ty, uint_ty], false);
 813         let walked: Vec<_> = tup2_ty.walk().collect();
 814         assert_eq!(walked,
 815                    [tup2_ty, tup1_ty, int_ty, uint_ty, int_ty, uint_ty, tup1_ty, int_ty,
 816                     uint_ty, int_ty, uint_ty, uint_ty]);
 817     })
 818 }
 819
 820 #[test]
 821 fn walk_ty_skip_subtree() {
 822     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
 823         let tcx = env.infcx.tcx;
 824         let int_ty = tcx.types.isize;
 825         let uint_ty = tcx.types.usize;
 826         let tup1_ty = tcx.intern_tup(&[int_ty, uint_ty, int_ty, uint_ty], false);
 827         let tup2_ty = tcx.intern_tup(&[tup1_ty, tup1_ty, uint_ty], false);
 828
 829         // types we expect to see (in order), plus a boolean saying
 830         // whether to skip the subtree.
 831         let mut expected = vec![(tup2_ty, false),
 832                                 (tup1_ty, false),
 833                                 (int_ty, false),
 834                                 (uint_ty, false),
 835                                 (int_ty, false),
 836                                 (uint_ty, false),
 837                                 (tup1_ty, true), // skip the isize/usize/isize/usize
 838                                 (uint_ty, false)];
 839         expected.reverse();
 840
 841         let mut walker = tup2_ty.walk();
 842         while let Some(t) = walker.next() {
 843             debug!("walked to {:?}", t);
 844             let (expected_ty, skip) = expected.pop().unwrap();
 845             assert_eq!(t, expected_ty);
 846             if skip {
 847                 walker.skip_current_subtree();
 848             }
 849         }
 850
 851         assert!(expected.is_empty());
 852     })
 853 }