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