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