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