src/librustc/middle/typeck/infer/resolve.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 // Resolution is the process of removing type variables and replacing
  12 // them with their inferred values.  Unfortunately our inference has
  13 // become fairly complex and so there are a number of options to
  14 // control *just how much* you want to resolve and how you want to do
  15 // it.
  16 //
  17 // # Controlling the scope of resolution
  18 //
  19 // The options resolve_* determine what kinds of variables get
  20 // resolved.  Generally resolution starts with a top-level type
  21 // variable; we will always resolve this.  However, once we have
  22 // resolved that variable, we may end up with a type that still
  23 // contains type variables.  For example, if we resolve `<T0>` we may
  24 // end up with something like `[<T1>]`.  If the option
  25 // `resolve_nested_tvar` is passed, we will then go and recursively
  26 // resolve `<T1>`.
  27 //
  28 // The options `resolve_rvar` controls whether we resolve region
  29 // variables. The options `resolve_fvar` and `resolve_ivar` control
  30 // whether we resolve floating point and integral variables,
  31 // respectively.
  32 //
  33 // # What do if things are unconstrained
  34 //
  35 // Sometimes we will encounter a variable that has no constraints, and
  36 // therefore cannot sensibly be mapped to any particular result.  By
  37 // default, we will leave such variables as is (so you will get back a
  38 // variable in your result).  The options force_* will cause the
  39 // resolution to fail in this case instead, except for the case of
  40 // integral variables, which resolve to `int` if forced.
  41 //
  42 // # resolve_all and force_all
  43 //
  44 // The options are a bit set, so you can use the *_all to resolve or
  45 // force all kinds of variables (including those we may add in the
  46 // future).  If you want to resolve everything but one type, you are
  47 // probably better off writing `resolve_all - resolve_ivar`.
  48
  49
  50 use middle::ty::{FloatVar, FloatVid, IntVar, IntVid, RegionVid, TyVar, TyVid};
  51 use middle::ty::{type_is_bot, IntType, UintType};
  52 use middle::ty;
  53 use middle::ty_fold;
  54 use middle::typeck::infer::{Bounds, cyclic_ty, fixup_err, fres, InferCtxt};
  55 use middle::typeck::infer::unresolved_ty;
  56 use middle::typeck::infer::unify::Root;
  57 use util::common::{indent};
  58 use util::ppaux::{ty_to_str, Repr};
  59
  60 use syntax::ast;
  61
  62 pub static resolve_nested_tvar: uint = 0b0000000001;
  63 pub static resolve_rvar: uint        = 0b0000000010;
  64 pub static resolve_ivar: uint        = 0b0000000100;
  65 pub static resolve_fvar: uint        = 0b0000001000;
  66 pub static resolve_all: uint         = 0b0000001111;
  67 pub static force_tvar: uint          = 0b0000100000;
  68 pub static force_rvar: uint          = 0b0001000000;
  69 pub static force_ivar: uint          = 0b0010000000;
  70 pub static force_fvar: uint          = 0b0100000000;
  71 pub static force_all: uint           = 0b0111100000;
  72
  73 pub static not_regions: uint         = !(force_rvar | resolve_rvar);
  74
  75 pub static try_resolve_tvar_shallow: uint = 0;
  76 pub static resolve_and_force_all_but_regions: uint =
  77     (resolve_all | force_all) & not_regions;
  78
  79 pub struct ResolveState<'a> {
  80     infcx: &'a InferCtxt<'a>,
  81     modes: uint,
  82     err: Option<fixup_err>,
  83     v_seen: Vec<TyVid> ,
  84     type_depth: uint
  85 }
  86
  87 pub fn resolver<'a>(infcx: &'a InferCtxt, modes: uint) -> ResolveState<'a> {
  88     ResolveState {
  89         infcx: infcx,
  90         modes: modes,
  91         err: None,
  92         v_seen: Vec::new(),
  93         type_depth: 0
  94     }
  95 }
  96
  97 impl<'a> ty_fold::TypeFolder for ResolveState<'a> {
  98     fn tcx<'a>(&'a self) -> &'a ty::ctxt {
  99         self.infcx.tcx
 100     }
 101
 102     fn fold_ty(&mut self, t: ty::t) -> ty::t {
 103         self.resolve_type(t)
 104     }
 105
 106     fn fold_region(&mut self, r: ty::Region) -> ty::Region {
 107         self.resolve_region(r)
 108     }
 109 }
 110
 111 impl<'a> ResolveState<'a> {
 112     pub fn should(&mut self, mode: uint) -> bool {
 113         (self.modes & mode) == mode
 114     }
 115
 116     pub fn resolve_type_chk(&mut self, typ: ty::t) -> fres<ty::t> {
 117         self.err = None;
 118
 119         debug!("Resolving {} (modes={:x})",
 120                ty_to_str(self.infcx.tcx, typ),
 121                self.modes);
 122
 123         // n.b. This is a hokey mess because the current fold doesn't
 124         // allow us to pass back errors in any useful way.
 125
 126         assert!(self.v_seen.is_empty());
 127         let rty = indent(|| self.resolve_type(typ) );
 128         assert!(self.v_seen.is_empty());
 129         match self.err {
 130           None => {
 131             debug!("Resolved to {} + {} (modes={:x})",
 132                    ty_to_str(self.infcx.tcx, rty),
 133                    ty_to_str(self.infcx.tcx, rty),
 134                    self.modes);
 135             return Ok(rty);
 136           }
 137           Some(e) => return Err(e)
 138         }
 139     }
 140
 141     pub fn resolve_region_chk(&mut self, orig: ty::Region)
 142                               -> fres<ty::Region> {
 143         self.err = None;
 144         let resolved = indent(|| self.resolve_region(orig) );
 145         match self.err {
 146           None => Ok(resolved),
 147           Some(e) => Err(e)
 148         }
 149     }
 150
 151     pub fn resolve_type(&mut self, typ: ty::t) -> ty::t {
 152         debug!("resolve_type({})", typ.repr(self.infcx.tcx));
 153
 154         if !ty::type_needs_infer(typ) {
 155             return typ;
 156         }
 157
 158         if self.type_depth > 0 && !self.should(resolve_nested_tvar) {
 159             return typ;
 160         }
 161
 162         match ty::get(typ).sty {
 163             ty::ty_infer(TyVar(vid)) => {
 164                 self.resolve_ty_var(vid)
 165             }
 166             ty::ty_infer(IntVar(vid)) => {
 167                 self.resolve_int_var(vid)
 168             }
 169             ty::ty_infer(FloatVar(vid)) => {
 170                 self.resolve_float_var(vid)
 171             }
 172             _ => {
 173                 if self.modes & resolve_all == 0 {
 174                     // if we are only resolving top-level type
 175                     // variables, and this is not a top-level type
 176                     // variable, then shortcircuit for efficiency
 177                     typ
 178                 } else {
 179                     self.type_depth += 1;
 180                     let result = ty_fold::super_fold_ty(self, typ);
 181                     self.type_depth -= 1;
 182                     result
 183                 }
 184             }
 185         }
 186     }
 187
 188     pub fn resolve_region(&mut self, orig: ty::Region) -> ty::Region {
 189         debug!("Resolve_region({})", orig.repr(self.infcx.tcx));
 190         match orig {
 191           ty::ReInfer(ty::ReVar(rid)) => self.resolve_region_var(rid),
 192           _ => orig
 193         }
 194     }
 195
 196     pub fn resolve_region_var(&mut self, rid: RegionVid) -> ty::Region {
 197         if !self.should(resolve_rvar) {
 198             return ty::ReInfer(ty::ReVar(rid));
 199         }
 200         self.infcx.region_vars.resolve_var(rid)
 201     }
 202
 203     pub fn resolve_ty_var(&mut self, vid: TyVid) -> ty::t {
 204         if self.v_seen.contains(&vid) {
 205             self.err = Some(cyclic_ty(vid));
 206             return ty::mk_var(self.infcx.tcx, vid);
 207         } else {
 208             self.v_seen.push(vid);
 209             let tcx = self.infcx.tcx;
 210
 211             // Nonobvious: prefer the most specific type
 212             // (i.e., the lower bound) to the more general
 213             // one.  More general types in Rust (e.g., fn())
 214             // tend to carry more restrictions or higher
 215             // perf. penalties, so it pays to know more.
 216
 217             let node =
 218                 self.infcx.type_unification_table.borrow_mut().get(tcx, vid);
 219             let t1 = match node.value {
 220               Bounds { ub:_, lb:Some(t) } if !type_is_bot(t) => {
 221                   self.resolve_type(t)
 222               }
 223               Bounds { ub:Some(t), lb:_ } | Bounds { ub:_, lb:Some(t) } => {
 224                   self.resolve_type(t)
 225               }
 226               Bounds { ub:None, lb:None } => {
 227                 if self.should(force_tvar) {
 228                     self.err = Some(unresolved_ty(vid));
 229                 }
 230                 ty::mk_var(tcx, vid)
 231               }
 232             };
 233             self.v_seen.pop().unwrap();
 234             return t1;
 235         }
 236     }
 237
 238     pub fn resolve_int_var(&mut self, vid: IntVid) -> ty::t {
 239         if !self.should(resolve_ivar) {
 240             return ty::mk_int_var(self.infcx.tcx, vid);
 241         }
 242
 243         let tcx = self.infcx.tcx;
 244         let table = &self.infcx.int_unification_table;
 245         let node = table.borrow_mut().get(tcx, vid);
 246         match node.value {
 247           Some(IntType(t)) => ty::mk_mach_int(t),
 248           Some(UintType(t)) => ty::mk_mach_uint(t),
 249           None => {
 250             if self.should(force_ivar) {
 251                 // As a last resort, default to int.
 252                 let ty = ty::mk_int();
 253                 table.borrow_mut().set(
 254                     tcx, node.key, Root(Some(IntType(ast::TyI)), node.rank));
 255                 ty
 256             } else {
 257                 ty::mk_int_var(self.infcx.tcx, vid)
 258             }
 259           }
 260         }
 261     }
 262
 263     pub fn resolve_float_var(&mut self, vid: FloatVid) -> ty::t {
 264         if !self.should(resolve_fvar) {
 265             return ty::mk_float_var(self.infcx.tcx, vid);
 266         }
 267
 268         let tcx = self.infcx.tcx;
 269         let table = &self.infcx.float_unification_table;
 270         let node = table.borrow_mut().get(tcx, vid);
 271         match node.value {
 272           Some(t) => ty::mk_mach_float(t),
 273           None => {
 274             if self.should(force_fvar) {
 275                 // As a last resort, default to f64.
 276                 let ty = ty::mk_f64();
 277                 table.borrow_mut().set(
 278                     tcx, node.key, Root(Some(ast::TyF64), node.rank));
 279                 ty
 280             } else {
 281                 ty::mk_float_var(self.infcx.tcx, vid)
 282             }
 283           }
 284         }
 285     }
 286 }