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