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