src/librustc/middle/typeck/infer/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 /*!
  12
  13 # Standalone Tests for the Inference Module
  14
  15 */
  16
  17 // This is only used by tests, hence allow dead code.
  18 #![allow(dead_code)]
  19
  20 use driver::config;
  21 use driver::diagnostic;
  22 use driver::diagnostic::Emitter;
  23 use driver::driver;
  24 use driver::session;
  25 use middle::lang_items;
  26 use middle::region;
  27 use middle::resolve;
  28 use middle::resolve_lifetime;
  29 use middle::stability;
  30 use middle::ty;
  31 use middle::typeck::infer::combine::Combine;
  32 use middle::typeck::infer;
  33 use middle::typeck::infer::lub::Lub;
  34 use middle::typeck::infer::glb::Glb;
  35 use syntax::codemap;
  36 use syntax::codemap::{Span, CodeMap, DUMMY_SP};
  37 use syntax::diagnostic::{Level, RenderSpan, Bug, Fatal, Error, Warning, Note};
  38 use syntax::{ast, ast_map};
  39 use util::ppaux::{ty_to_string, UserString};
  40
  41 use arena::TypedArena;
  42
  43 struct Env<'a, 'tcx: 'a> {
  44     infcx: &'a infer::InferCtxt<'a, 'tcx>,
  45 }
  46
  47 struct RH<'a> {
  48     id: ast::NodeId,
  49     sub: &'a [RH<'a>]
  50 }
  51
  52 static EMPTY_SOURCE_STR: &'static str = "#![no_std]";
  53
  54 struct ExpectErrorEmitter {
  55     messages: Vec<String>
  56 }
  57
  58 fn remove_message(e: &mut ExpectErrorEmitter, msg: &str, lvl: Level) {
  59     match lvl {
  60         Bug | Fatal | Error => { }
  61         Warning | Note => { return; }
  62     }
  63
  64     debug!("Error: {}", msg);
  65     match e.messages.iter().position(|m| msg.contains(m.as_slice())) {
  66         Some(i) => {
  67             e.messages.remove(i);
  68         }
  69         None => {
  70             fail!("Unexpected error: {} Expected: {}",
  71                   msg, e.messages);
  72         }
  73     }
  74 }
  75
  76 impl Emitter for ExpectErrorEmitter {
  77     fn emit(&mut self,
  78             _cmsp: Option<(&codemap::CodeMap, Span)>,
  79             msg: &str,
  80             _: Option<&str>,
  81             lvl: Level)
  82     {
  83         remove_message(self, msg, lvl);
  84     }
  85
  86     fn custom_emit(&mut self,
  87                    _cm: &codemap::CodeMap,
  88                    _sp: RenderSpan,
  89                    msg: &str,
  90                    lvl: Level)
  91     {
  92         remove_message(self, msg, lvl);
  93     }
  94 }
  95
  96 fn errors(msgs: &[&str]) -> (Box<Emitter+Send>, uint) {
  97     let v = msgs.iter().map(|m| m.to_string()).collect();
  98     (box ExpectErrorEmitter { messages: v } as Box<Emitter+Send>, msgs.len())
  99 }
 100
 101 fn test_env(_test_name: &str,
 102             source_string: &str,
 103             (emitter, expected_err_count): (Box<Emitter+Send>, uint),
 104             body: |Env|) {
 105     let options =
 106         config::basic_options();
 107     let codemap =
 108         CodeMap::new();
 109     let diagnostic_handler =
 110         diagnostic::mk_handler(emitter);
 111     let span_diagnostic_handler =
 112         diagnostic::mk_span_handler(diagnostic_handler, codemap);
 113
 114     let sess = session::build_session_(options, None, span_diagnostic_handler);
 115     let krate_config = Vec::new();
 116     let input = driver::StrInput(source_string.to_string());
 117     let krate = driver::phase_1_parse_input(&sess, krate_config, &input);
 118     let krate = driver::phase_2_configure_and_expand(&sess, krate, "test", None)
 119                     .expect("phase 2 aborted");
 120
 121     let mut forest = ast_map::Forest::new(krate);
 122     let ast_map = driver::assign_node_ids_and_map(&sess, &mut forest);
 123     let krate = ast_map.krate();
 124
 125     // run just enough stuff to build a tcx:
 126     let lang_items = lang_items::collect_language_items(krate, &sess);
 127     let resolve::CrateMap { def_map, freevars, capture_mode_map, .. } =
 128         resolve::resolve_crate(&sess, &lang_items, krate);
 129     let named_region_map = resolve_lifetime::krate(&sess, krate);
 130     let region_map = region::resolve_crate(&sess, krate);
 131     let stability_index = stability::Index::build(krate);
 132     let type_arena = TypedArena::new();
 133     let tcx = ty::mk_ctxt(sess,
 134                           &type_arena,
 135                           def_map,
 136                           named_region_map,
 137                           ast_map,
 138                           freevars,
 139                           capture_mode_map,
 140                           region_map,
 141                           lang_items,
 142                           stability_index);
 143     let infcx = infer::new_infer_ctxt(&tcx);
 144     body(Env { infcx: &infcx });
 145     infcx.resolve_regions_and_report_errors();
 146     assert_eq!(tcx.sess.err_count(), expected_err_count);
 147 }
 148
 149 impl<'a, 'tcx> Env<'a, 'tcx> {
 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(child_rh.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     pub fn lookup_item(&self, names: &[String]) -> ast::NodeId {
 169         return match search_mod(self, &self.infcx.tcx.map.krate().module, 0, names) {
 170             Some(id) => id,
 171             None => {
 172                 fail!("no item found: `{}`", names.connect("::"));
 173             }
 174         };
 175
 176         fn search_mod(this: &Env,
 177                       m: &ast::Mod,
 178                       idx: uint,
 179                       names: &[String])
 180                       -> Option<ast::NodeId> {
 181             assert!(idx < names.len());
 182             for item in m.items.iter() {
 183                 if item.ident.user_string(this.infcx.tcx) == names[idx] {
 184                     return search(this, &**item, idx+1, names);
 185                 }
 186             }
 187             return None;
 188         }
 189
 190         fn search(this: &Env,
 191                   it: &ast::Item,
 192                   idx: uint,
 193                   names: &[String])
 194                   -> Option<ast::NodeId> {
 195             if idx == names.len() {
 196                 return Some(it.id);
 197             }
 198
 199             return match it.node {
 200                 ast::ItemStatic(..) | ast::ItemFn(..) |
 201                 ast::ItemForeignMod(..) | ast::ItemTy(..) => {
 202                     None
 203                 }
 204
 205                 ast::ItemEnum(..) | ast::ItemStruct(..) |
 206                 ast::ItemTrait(..) | ast::ItemImpl(..) |
 207                 ast::ItemMac(..) => {
 208                     None
 209                 }
 210
 211                 ast::ItemMod(ref m) => {
 212                     search_mod(this, m, idx, names)
 213                 }
 214             };
 215         }
 216     }
 217
 218     pub fn make_subtype(&self, a: ty::t, b: ty::t) -> bool {
 219         match infer::mk_subty(self.infcx, true, infer::Misc(DUMMY_SP), a, b) {
 220             Ok(_) => true,
 221             Err(ref e) => fail!("Encountered error: {}",
 222                                 ty::type_err_to_str(self.infcx.tcx, e))
 223         }
 224     }
 225
 226     pub fn is_subtype(&self, a: ty::t, b: ty::t) -> bool {
 227         match infer::can_mk_subty(self.infcx, a, b) {
 228             Ok(_) => true,
 229             Err(_) => false
 230         }
 231     }
 232
 233     pub fn assert_subtype(&self, a: ty::t, b: ty::t) {
 234         if !self.is_subtype(a, b) {
 235             fail!("{} is not a subtype of {}, but it should be",
 236                   self.ty_to_string(a),
 237                   self.ty_to_string(b));
 238         }
 239     }
 240
 241     pub fn assert_not_subtype(&self, a: ty::t, b: ty::t) {
 242         if self.is_subtype(a, b) {
 243             fail!("{} is a subtype of {}, but it shouldn't be",
 244                   self.ty_to_string(a),
 245                   self.ty_to_string(b));
 246         }
 247     }
 248
 249     pub fn assert_eq(&self, a: ty::t, b: ty::t) {
 250         self.assert_subtype(a, b);
 251         self.assert_subtype(b, a);
 252     }
 253
 254     pub fn ty_to_string(&self, a: ty::t) -> String {
 255         ty_to_string(self.infcx.tcx, a)
 256     }
 257
 258     pub fn t_fn(&self,
 259                 binder_id: ast::NodeId,
 260                 input_tys: &[ty::t],
 261                 output_ty: ty::t)
 262                 -> ty::t
 263     {
 264         ty::mk_ctor_fn(self.infcx.tcx, binder_id, input_tys, output_ty)
 265     }
 266
 267     pub fn t_int(&self) -> ty::t {
 268         ty::mk_int()
 269     }
 270
 271     pub fn t_rptr_late_bound(&self, binder_id: ast::NodeId, id: uint) -> ty::t {
 272         ty::mk_imm_rptr(self.infcx.tcx, ty::ReLateBound(binder_id, ty::BrAnon(id)),
 273                         self.t_int())
 274     }
 275
 276     pub fn t_rptr_scope(&self, id: ast::NodeId) -> ty::t {
 277         ty::mk_imm_rptr(self.infcx.tcx, ty::ReScope(id), self.t_int())
 278     }
 279
 280     pub fn t_rptr_free(&self, nid: ast::NodeId, id: uint) -> ty::t {
 281         ty::mk_imm_rptr(self.infcx.tcx,
 282                         ty::ReFree(ty::FreeRegion {scope_id: nid,
 283                                                     bound_region: ty::BrAnon(id)}),
 284                         self.t_int())
 285     }
 286
 287     pub fn t_rptr_static(&self) -> ty::t {
 288         ty::mk_imm_rptr(self.infcx.tcx, ty::ReStatic, self.t_int())
 289     }
 290
 291     pub fn dummy_type_trace(&self) -> infer::TypeTrace {
 292         infer::TypeTrace {
 293             origin: infer::Misc(DUMMY_SP),
 294             values: infer::Types(ty::expected_found {
 295                 expected: ty::mk_err(),
 296                 found: ty::mk_err(),
 297             })
 298         }
 299     }
 300
 301     pub fn lub(&self) -> Lub<'a, 'tcx> {
 302         let trace = self.dummy_type_trace();
 303         Lub(self.infcx.combine_fields(true, trace))
 304     }
 305
 306     pub fn glb(&self) -> Glb<'a, 'tcx> {
 307         let trace = self.dummy_type_trace();
 308         Glb(self.infcx.combine_fields(true, trace))
 309     }
 310
 311     pub fn resolve_regions(&self) {
 312         self.infcx.resolve_regions_and_report_errors();
 313     }
 314
 315     pub fn make_lub_ty(&self, t1: ty::t, t2: ty::t) -> ty::t {
 316         match self.lub().tys(t1, t2) {
 317             Ok(t) => t,
 318             Err(ref e) => fail!("unexpected error computing LUB: {:?}",
 319                                 ty::type_err_to_str(self.infcx.tcx, e))
 320         }
 321     }
 322
 323     /// Checks that `LUB(t1,t2) == t_lub`
 324     pub fn check_lub(&self, t1: ty::t, t2: ty::t, t_lub: ty::t) {
 325         match self.lub().tys(t1, t2) {
 326             Ok(t) => {
 327                 self.assert_eq(t, t_lub);
 328             }
 329             Err(ref e) => {
 330                 fail!("unexpected error in LUB: {}",
 331                       ty::type_err_to_str(self.infcx.tcx, e))
 332             }
 333         }
 334     }
 335
 336     /// Checks that `GLB(t1,t2) == t_glb`
 337     pub fn check_glb(&self, t1: ty::t, t2: ty::t, t_glb: ty::t) {
 338         debug!("check_glb(t1={}, t2={}, t_glb={})",
 339                self.ty_to_string(t1),
 340                self.ty_to_string(t2),
 341                self.ty_to_string(t_glb));
 342         match self.glb().tys(t1, t2) {
 343             Err(e) => {
 344                 fail!("unexpected error computing LUB: {:?}", e)
 345             }
 346             Ok(t) => {
 347                 self.assert_eq(t, t_glb);
 348
 349                 // sanity check for good measure:
 350                 self.assert_subtype(t, t1);
 351                 self.assert_subtype(t, t2);
 352             }
 353         }
 354     }
 355
 356     /// Checks that `LUB(t1,t2)` is undefined
 357     pub fn check_no_lub(&self, t1: ty::t, t2: ty::t) {
 358         match self.lub().tys(t1, t2) {
 359             Err(_) => {}
 360             Ok(t) => {
 361                 fail!("unexpected success computing LUB: {}", self.ty_to_string(t))
 362             }
 363         }
 364     }
 365
 366     /// Checks that `GLB(t1,t2)` is undefined
 367     pub fn check_no_glb(&self, t1: ty::t, t2: ty::t) {
 368         match self.glb().tys(t1, t2) {
 369             Err(_) => {}
 370             Ok(t) => {
 371                 fail!("unexpected success computing GLB: {}", self.ty_to_string(t))
 372             }
 373         }
 374     }
 375 }
 376
 377 #[test]
 378 fn contravariant_region_ptr_ok() {
 379     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 380         env.create_simple_region_hierarchy();
 381         let t_rptr1 = env.t_rptr_scope(1);
 382         let t_rptr10 = env.t_rptr_scope(10);
 383         env.assert_eq(t_rptr1, t_rptr1);
 384         env.assert_eq(t_rptr10, t_rptr10);
 385         env.make_subtype(t_rptr1, t_rptr10);
 386     })
 387 }
 388
 389 #[test]
 390 fn contravariant_region_ptr_err() {
 391     test_env("contravariant_region_ptr",
 392              EMPTY_SOURCE_STR,
 393              errors(["lifetime mismatch"]),
 394              |env| {
 395                  env.create_simple_region_hierarchy();
 396                  let t_rptr1 = env.t_rptr_scope(1);
 397                  let t_rptr10 = env.t_rptr_scope(10);
 398                  env.assert_eq(t_rptr1, t_rptr1);
 399                  env.assert_eq(t_rptr10, t_rptr10);
 400
 401                  // will cause an error when regions are resolved
 402                  env.make_subtype(t_rptr10, t_rptr1);
 403              })
 404 }
 405
 406 #[test]
 407 fn lub_bound_bound() {
 408     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 409         let t_rptr_bound1 = env.t_rptr_late_bound(22, 1);
 410         let t_rptr_bound2 = env.t_rptr_late_bound(22, 2);
 411         env.check_lub(env.t_fn(22, [t_rptr_bound1], env.t_int()),
 412                       env.t_fn(22, [t_rptr_bound2], env.t_int()),
 413                       env.t_fn(22, [t_rptr_bound1], env.t_int()));
 414     })
 415 }
 416
 417 #[test]
 418 fn lub_bound_free() {
 419     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 420         let t_rptr_bound1 = env.t_rptr_late_bound(22, 1);
 421         let t_rptr_free1 = env.t_rptr_free(0, 1);
 422         env.check_lub(env.t_fn(22, [t_rptr_bound1], env.t_int()),
 423                       env.t_fn(22, [t_rptr_free1], env.t_int()),
 424                       env.t_fn(22, [t_rptr_free1], env.t_int()));
 425     })
 426 }
 427
 428 #[test]
 429 fn lub_bound_static() {
 430     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 431         let t_rptr_bound1 = env.t_rptr_late_bound(22, 1);
 432         let t_rptr_static = env.t_rptr_static();
 433         env.check_lub(env.t_fn(22, [t_rptr_bound1], env.t_int()),
 434                       env.t_fn(22, [t_rptr_static], env.t_int()),
 435                       env.t_fn(22, [t_rptr_static], env.t_int()));
 436     })
 437 }
 438
 439 #[test]
 440 fn lub_bound_bound_inverse_order() {
 441     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 442         let t_rptr_bound1 = env.t_rptr_late_bound(22, 1);
 443         let t_rptr_bound2 = env.t_rptr_late_bound(22, 2);
 444         env.check_lub(env.t_fn(22, [t_rptr_bound1, t_rptr_bound2], t_rptr_bound1),
 445                       env.t_fn(22, [t_rptr_bound2, t_rptr_bound1], t_rptr_bound1),
 446                       env.t_fn(22, [t_rptr_bound1, t_rptr_bound1], t_rptr_bound1));
 447     })
 448 }
 449
 450 #[test]
 451 fn lub_free_free() {
 452     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 453         let t_rptr_free1 = env.t_rptr_free(0, 1);
 454         let t_rptr_free2 = env.t_rptr_free(0, 2);
 455         let t_rptr_static = env.t_rptr_static();
 456         env.check_lub(env.t_fn(22, [t_rptr_free1], env.t_int()),
 457                       env.t_fn(22, [t_rptr_free2], env.t_int()),
 458                       env.t_fn(22, [t_rptr_static], env.t_int()));
 459     })
 460 }
 461
 462 #[test]
 463 fn lub_returning_scope() {
 464     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR,
 465              errors(["cannot infer an appropriate lifetime"]), |env| {
 466                  let t_rptr_scope10 = env.t_rptr_scope(10);
 467                  let t_rptr_scope11 = env.t_rptr_scope(11);
 468
 469                  // this should generate an error when regions are resolved
 470                  env.make_lub_ty(env.t_fn(22, [], t_rptr_scope10),
 471                                  env.t_fn(22, [], t_rptr_scope11));
 472              })
 473 }
 474
 475 #[test]
 476 fn glb_free_free_with_common_scope() {
 477     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 478         let t_rptr_free1 = env.t_rptr_free(0, 1);
 479         let t_rptr_free2 = env.t_rptr_free(0, 2);
 480         let t_rptr_scope = env.t_rptr_scope(0);
 481         env.check_glb(env.t_fn(22, [t_rptr_free1], env.t_int()),
 482                       env.t_fn(22, [t_rptr_free2], env.t_int()),
 483                       env.t_fn(22, [t_rptr_scope], env.t_int()));
 484     })
 485 }
 486
 487 #[test]
 488 fn glb_bound_bound() {
 489     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 490         let t_rptr_bound1 = env.t_rptr_late_bound(22, 1);
 491         let t_rptr_bound2 = env.t_rptr_late_bound(22, 2);
 492         env.check_glb(env.t_fn(22, [t_rptr_bound1], env.t_int()),
 493                       env.t_fn(22, [t_rptr_bound2], env.t_int()),
 494                       env.t_fn(22, [t_rptr_bound1], env.t_int()));
 495     })
 496 }
 497
 498 #[test]
 499 fn glb_bound_free() {
 500     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 501         let t_rptr_bound1 = env.t_rptr_late_bound(22, 1);
 502         let t_rptr_free1 = env.t_rptr_free(0, 1);
 503         env.check_glb(env.t_fn(22, [t_rptr_bound1], env.t_int()),
 504                       env.t_fn(22, [t_rptr_free1], env.t_int()),
 505                       env.t_fn(22, [t_rptr_bound1], env.t_int()));
 506     })
 507 }
 508
 509 #[test]
 510 fn glb_bound_static() {
 511     test_env("contravariant_region_ptr", EMPTY_SOURCE_STR, errors([]), |env| {
 512         let t_rptr_bound1 = env.t_rptr_late_bound(22, 1);
 513         let t_rptr_static = env.t_rptr_static();
 514         env.check_glb(env.t_fn(22, [t_rptr_bound1], env.t_int()),
 515                       env.t_fn(22, [t_rptr_static], env.t_int()),
 516                       env.t_fn(22, [t_rptr_bound1], env.t_int()));
 517     })
 518 }