src/librustc/middle/typeck/infer/glb.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::lattice::*;
  18 use middle::typeck::infer::lub::Lub;
  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::{TypeTrace, Subtype};
  23 use middle::typeck::infer::fold_regions_in_sig;
  24 use syntax::ast::{Many, Once, MutImmutable, MutMutable};
  25 use syntax::ast::{NormalFn, UnsafeFn, NodeId};
  26 use syntax::ast::{Onceness, FnStyle};
  27 use std::collections::HashMap;
  28 use util::common::{indenter};
  29 use util::ppaux::mt_to_str;
  30
  31 pub struct Glb<'f>(pub CombineFields<'f>);  // "greatest lower bound" (common subtype)
  32
  33 impl<'f> Glb<'f> {
  34     pub fn get_ref<'a>(&'a self) -> &'a CombineFields<'f> { let Glb(ref v) = *self; v }
  35 }
  36
  37 impl<'f> Combine for Glb<'f> {
  38     fn infcx<'a>(&'a self) -> &'a InferCtxt<'a> { self.get_ref().infcx }
  39     fn tag(&self) -> String { "glb".to_string() }
  40     fn a_is_expected(&self) -> bool { self.get_ref().a_is_expected }
  41     fn trace(&self) -> TypeTrace { self.get_ref().trace.clone() }
  42
  43     fn sub<'a>(&'a self) -> Sub<'a> { Sub(self.get_ref().clone()) }
  44     fn lub<'a>(&'a self) -> Lub<'a> { Lub(self.get_ref().clone()) }
  45     fn glb<'a>(&'a self) -> Glb<'a> { Glb(self.get_ref().clone()) }
  46
  47     fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt> {
  48         let tcx = self.get_ref().infcx.tcx;
  49
  50         debug!("{}.mts({}, {})",
  51                self.tag(),
  52                mt_to_str(tcx, a),
  53                mt_to_str(tcx, b));
  54
  55         match (a.mutbl, b.mutbl) {
  56           // If one side or both is mut, then the GLB must use
  57           // the precise type from the mut side.
  58           (MutMutable, MutMutable) => {
  59             eq_tys(self, a.ty, b.ty).then(|| {
  60                 Ok(ty::mt {ty: a.ty, mutbl: MutMutable})
  61             })
  62           }
  63
  64           // If one side or both is immutable, we can use the GLB of
  65           // both sides but mutbl must be `MutImmutable`.
  66           (MutImmutable, MutImmutable) => {
  67             self.tys(a.ty, b.ty).and_then(|t| {
  68                 Ok(ty::mt {ty: t, mutbl: MutImmutable})
  69             })
  70           }
  71
  72           // There is no mutual subtype of these combinations.
  73           (MutMutable, MutImmutable) |
  74           (MutImmutable, MutMutable) => {
  75               Err(ty::terr_mutability)
  76           }
  77         }
  78     }
  79
  80     fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
  81         self.lub().tys(a, b)
  82     }
  83
  84     fn fn_styles(&self, a: FnStyle, b: FnStyle) -> cres<FnStyle> {
  85         match (a, b) {
  86           (NormalFn, _) | (_, NormalFn) => Ok(NormalFn),
  87           (UnsafeFn, UnsafeFn) => Ok(UnsafeFn)
  88         }
  89     }
  90
  91     fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<Onceness> {
  92         match (a, b) {
  93             (Many, _) | (_, Many) => Ok(Many),
  94             (Once, Once) => Ok(Once)
  95         }
  96     }
  97
  98     fn bounds(&self, a: BuiltinBounds, b: BuiltinBounds) -> cres<BuiltinBounds> {
  99         // More bounds is a subtype of fewer bounds, so
 100         // the GLB (mutual subtype) is the union.
 101         Ok(a.union(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.glb_regions(Subtype(self.trace()), a, b))
 111     }
 112
 113     fn contraregions(&self, a: ty::Region, b: ty::Region)
 114                     -> cres<ty::Region> {
 115         self.lub().regions(a, b)
 116     }
 117
 118     fn tys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
 119         super_lattice_tys(self, a, b)
 120     }
 121
 122     fn fn_sigs(&self, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig> {
 123         // Note: this is a subtle algorithm.  For a full explanation,
 124         // please see the large comment in `region_inference.rs`.
 125
 126         debug!("{}.fn_sigs({:?}, {:?})",
 127                self.tag(), a.inf_str(self.get_ref().infcx), b.inf_str(self.get_ref().infcx));
 128         let _indenter = indenter();
 129
 130         // Take a snapshot.  We'll never roll this back, but in later
 131         // phases we do want to be able to examine "all bindings that
 132         // were created as part of this type comparison", and making a
 133         // snapshot is a convenient way to do that.
 134         let snapshot = self.get_ref().infcx.region_vars.start_snapshot();
 135
 136         // Instantiate each bound region with a fresh region variable.
 137         let (a_with_fresh, a_map) =
 138             self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
 139                 self.trace(), a);
 140         let a_vars = var_ids(self, &a_map);
 141         let (b_with_fresh, b_map) =
 142             self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
 143                 self.trace(), b);
 144         let b_vars = var_ids(self, &b_map);
 145
 146         // Collect constraints.
 147         let sig0 = if_ok!(super_fn_sigs(self, &a_with_fresh, &b_with_fresh));
 148         debug!("sig0 = {}", sig0.inf_str(self.get_ref().infcx));
 149
 150         // Generalize the regions appearing in fn_ty0 if possible
 151         let new_vars =
 152             self.get_ref().infcx.region_vars.vars_created_since_snapshot(snapshot);
 153         let sig1 =
 154             fold_regions_in_sig(
 155                 self.get_ref().infcx.tcx,
 156                 &sig0,
 157                 |r| {
 158                 generalize_region(self,
 159                                   snapshot,
 160                                   new_vars.as_slice(),
 161                                   sig0.binder_id,
 162                                   &a_map,
 163                                   a_vars.as_slice(),
 164                                   b_vars.as_slice(),
 165                                   r)
 166             });
 167         debug!("sig1 = {}", sig1.inf_str(self.get_ref().infcx));
 168         return Ok(sig1);
 169
 170         fn generalize_region(this: &Glb,
 171                              snapshot: uint,
 172                              new_vars: &[RegionVid],
 173                              new_binder_id: NodeId,
 174                              a_map: &HashMap<ty::BoundRegion, ty::Region>,
 175                              a_vars: &[RegionVid],
 176                              b_vars: &[RegionVid],
 177                              r0: ty::Region) -> ty::Region {
 178             if !is_var_in_set(new_vars, r0) {
 179                 assert!(!r0.is_bound());
 180                 return r0;
 181             }
 182
 183             let tainted = this.get_ref().infcx.region_vars.tainted(snapshot, r0);
 184
 185             let mut a_r = None;
 186             let mut b_r = None;
 187             let mut only_new_vars = true;
 188             for r in tainted.iter() {
 189                 if is_var_in_set(a_vars, *r) {
 190                     if a_r.is_some() {
 191                         return fresh_bound_variable(this, new_binder_id);
 192                     } else {
 193                         a_r = Some(*r);
 194                     }
 195                 } else if is_var_in_set(b_vars, *r) {
 196                     if b_r.is_some() {
 197                         return fresh_bound_variable(this, new_binder_id);
 198                     } else {
 199                         b_r = Some(*r);
 200                     }
 201                 } else if !is_var_in_set(new_vars, *r) {
 202                     only_new_vars = false;
 203                 }
 204             }
 205
 206             // NB---I do not believe this algorithm computes
 207             // (necessarily) the GLB.  As written it can
 208             // spuriously fail.  In particular, if there is a case
 209             // like: |fn(&a)| and fn(fn(&b)), where a and b are
 210             // free, it will return fn(&c) where c = GLB(a,b).  If
 211             // however this GLB is not defined, then the result is
 212             // an error, even though something like
 213             // "fn<X>(fn(&X))" where X is bound would be a
 214             // subtype of both of those.
 215             //
 216             // The problem is that if we were to return a bound
 217             // variable, we'd be computing a lower-bound, but not
 218             // necessarily the *greatest* lower-bound.
 219             //
 220             // Unfortunately, this problem is non-trivial to solve,
 221             // because we do not know at the time of computing the GLB
 222             // whether a GLB(a,b) exists or not, because we haven't
 223             // run region inference (or indeed, even fully computed
 224             // the region hierarchy!). The current algorithm seems to
 225             // works ok in practice.
 226
 227             if a_r.is_some() && b_r.is_some() && only_new_vars {
 228                 // Related to exactly one bound variable from each fn:
 229                 return rev_lookup(this, a_map, new_binder_id, a_r.unwrap());
 230             } else if a_r.is_none() && b_r.is_none() {
 231                 // Not related to bound variables from either fn:
 232                 assert!(!r0.is_bound());
 233                 return r0;
 234             } else {
 235                 // Other:
 236                 return fresh_bound_variable(this, new_binder_id);
 237             }
 238         }
 239
 240         fn rev_lookup(this: &Glb,
 241                       a_map: &HashMap<ty::BoundRegion, ty::Region>,
 242                       new_binder_id: NodeId,
 243                       r: ty::Region) -> ty::Region
 244         {
 245             for (a_br, a_r) in a_map.iter() {
 246                 if *a_r == r {
 247                     return ty::ReLateBound(new_binder_id, *a_br);
 248                 }
 249             }
 250             this.get_ref().infcx.tcx.sess.span_bug(
 251                 this.get_ref().trace.origin.span(),
 252                 format!("could not find original bound region for {:?}",
 253                         r).as_slice())
 254         }
 255
 256         fn fresh_bound_variable(this: &Glb, binder_id: NodeId) -> ty::Region {
 257             this.get_ref().infcx.region_vars.new_bound(binder_id)
 258         }
 259     }
 260 }