src/librustc_driver/test.rs

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