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