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