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