src/librustc/middle/typeck/infer/lub.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 use middle::ty::{BuiltinBounds};
  13 use middle::ty::RegionVid;
  14 use middle::ty;
  15 use middle::typeck::infer::then;
  16 use middle::typeck::infer::combine::*;
  17 use middle::typeck::infer::glb::Glb;
  18 use middle::typeck::infer::lattice::*;
  19 use middle::typeck::infer::sub::Sub;
  20 use middle::typeck::infer::to_str::InferStr;
  21 use middle::typeck::infer::{cres, InferCtxt};
  22 use middle::typeck::infer::fold_regions_in_sig;
  23 use middle::typeck::infer::{TypeTrace, Subtype};
  24 use collections::HashMap;
  25 use syntax::ast::{Many, Once, NodeId};
  26 use syntax::ast::{ExternFn, NormalFn, UnsafeFn};
  27 use syntax::ast::{Onceness, FnStyle};
  28 use util::ppaux::mt_to_str;
  29
  30 pub struct Lub<'f>(pub CombineFields<'f>);  // least-upper-bound: common supertype
  31
  32 impl<'f> Lub<'f> {
  33     pub fn get_ref<'a>(&'a self) -> &'a CombineFields<'f> { let Lub(ref v) = *self; v }
  34 }
  35
  36 impl<'f> Combine for Lub<'f> {
  37     fn infcx<'a>(&'a self) -> &'a InferCtxt<'a> { self.get_ref().infcx }
  38     fn tag(&self) -> ~str { "lub".to_owned() }
  39     fn a_is_expected(&self) -> bool { self.get_ref().a_is_expected }
  40     fn trace(&self) -> TypeTrace { self.get_ref().trace }
  41
  42     fn sub<'a>(&'a self) -> Sub<'a> { Sub(*self.get_ref()) }
  43     fn lub<'a>(&'a self) -> Lub<'a> { Lub(*self.get_ref()) }
  44     fn glb<'a>(&'a self) -> Glb<'a> { Glb(*self.get_ref()) }
  45
  46     fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt> {
  47         let tcx = self.get_ref().infcx.tcx;
  48
  49         debug!("{}.mts({}, {})",
  50                self.tag(),
  51                mt_to_str(tcx, a),
  52                mt_to_str(tcx, b));
  53
  54         if a.mutbl != b.mutbl {
  55             return Err(ty::terr_mutability)
  56         }
  57
  58         let m = a.mutbl;
  59         match m {
  60           MutImmutable => {
  61             self.tys(a.ty, b.ty).and_then(|t| Ok(ty::mt {ty: t, mutbl: m}) )
  62           }
  63
  64           MutMutable => {
  65             self.get_ref().infcx.try(|| {
  66                 eq_tys(self, a.ty, b.ty).then(|| {
  67                     Ok(ty::mt {ty: a.ty, mutbl: m})
  68                 })
  69             }).or_else(|e| Err(e))
  70           }
  71         }
  72     }
  73
  74     fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
  75         Glb(*self.get_ref()).tys(a, b)
  76     }
  77
  78     fn fn_styles(&self, a: FnStyle, b: FnStyle) -> cres<FnStyle> {
  79         match (a, b) {
  80           (UnsafeFn, _) | (_, UnsafeFn) => Ok(UnsafeFn),
  81           (NormalFn, _) | (_, NormalFn) => Ok(NormalFn),
  82           (ExternFn, ExternFn) => Ok(ExternFn),
  83         }
  84     }
  85
  86     fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<Onceness> {
  87         match (a, b) {
  88             (Once, _) | (_, Once) => Ok(Once),
  89             (Many, Many) => Ok(Many)
  90         }
  91     }
  92
  93     fn bounds(&self, a: BuiltinBounds, b: BuiltinBounds) -> cres<BuiltinBounds> {
  94         // More bounds is a subtype of fewer bounds, so
  95         // the LUB (mutual supertype) is the intersection.
  96         Ok(a.intersection(b))
  97     }
  98
  99     fn contraregions(&self, a: ty::Region, b: ty::Region)
 100                     -> cres<ty::Region> {
 101         return Glb(*self.get_ref()).regions(a, b);
 102     }
 103
 104     fn regions(&self, a: ty::Region, b: ty::Region) -> cres<ty::Region> {
 105         debug!("{}.regions({:?}, {:?})",
 106                self.tag(),
 107                a.inf_str(self.get_ref().infcx),
 108                b.inf_str(self.get_ref().infcx));
 109
 110         Ok(self.get_ref().infcx.region_vars.lub_regions(Subtype(self.get_ref().trace), a, b))
 111     }
 112
 113     fn fn_sigs(&self, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig> {
 114         // Note: this is a subtle algorithm.  For a full explanation,
 115         // please see the large comment in `region_inference.rs`.
 116
 117         // Take a snapshot.  We'll never roll this back, but in later
 118         // phases we do want to be able to examine "all bindings that
 119         // were created as part of this type comparison", and making a
 120         // snapshot is a convenient way to do that.
 121         let snapshot = self.get_ref().infcx.region_vars.start_snapshot();
 122
 123         // Instantiate each bound region with a fresh region variable.
 124         let (a_with_fresh, a_map) =
 125             self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
 126                 self.get_ref().trace, a);
 127         let (b_with_fresh, _) =
 128             self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
 129                 self.get_ref().trace, b);
 130
 131         // Collect constraints.
 132         let sig0 = if_ok!(super_fn_sigs(self, &a_with_fresh, &b_with_fresh));
 133         debug!("sig0 = {}", sig0.inf_str(self.get_ref().infcx));
 134
 135         // Generalize the regions appearing in sig0 if possible
 136         let new_vars =
 137             self.get_ref().infcx.region_vars.vars_created_since_snapshot(snapshot);
 138         let sig1 =
 139             fold_regions_in_sig(
 140                 self.get_ref().infcx.tcx,
 141                 &sig0,
 142                 |r| generalize_region(self, snapshot, new_vars.as_slice(),
 143                                       sig0.binder_id, &a_map, r));
 144         return Ok(sig1);
 145
 146         fn generalize_region(this: &Lub,
 147                              snapshot: uint,
 148                              new_vars: &[RegionVid],
 149                              new_scope: NodeId,
 150                              a_map: &HashMap<ty::BoundRegion, ty::Region>,
 151                              r0: ty::Region)
 152                              -> ty::Region {
 153             // Regions that pre-dated the LUB computation stay as they are.
 154             if !is_var_in_set(new_vars, r0) {
 155                 assert!(!r0.is_bound());
 156                 debug!("generalize_region(r0={:?}): not new variable", r0);
 157                 return r0;
 158             }
 159
 160             let tainted = this.get_ref().infcx.region_vars.tainted(snapshot, r0);
 161
 162             // Variables created during LUB computation which are
 163             // *related* to regions that pre-date the LUB computation
 164             // stay as they are.
 165             if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) {
 166                 debug!("generalize_region(r0={:?}): \
 167                         non-new-variables found in {:?}",
 168                        r0, tainted);
 169                 assert!(!r0.is_bound());
 170                 return r0;
 171             }
 172
 173             // Otherwise, the variable must be associated with at
 174             // least one of the variables representing bound regions
 175             // in both A and B.  Replace the variable with the "first"
 176             // bound region from A that we find it to be associated
 177             // with.
 178             for (a_br, a_r) in a_map.iter() {
 179                 if tainted.iter().any(|x| x == a_r) {
 180                     debug!("generalize_region(r0={:?}): \
 181                             replacing with {:?}, tainted={:?}",
 182                            r0, *a_br, tainted);
 183                     return ty::ReLateBound(new_scope, *a_br);
 184                 }
 185             }
 186
 187             this.get_ref().infcx.tcx.sess.span_bug(
 188                 this.get_ref().trace.origin.span(),
 189                 format!("Region {:?} is not associated with \
 190                         any bound region from A!", r0))
 191         }
 192     }
 193
 194     fn tys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
 195         super_lattice_tys(self, a, b)
 196     }
 197 }