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