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