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