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 use middle::ty::{BuiltinBounds};
  12 use middle::ty::RegionVid;
  13 use middle::ty;
  14 use middle::typeck::infer::then;
  15 use middle::typeck::infer::combine::*;
  16 use middle::typeck::infer::glb::Glb;
  17 use middle::typeck::infer::lattice::*;
  18 use middle::typeck::infer::sub::Sub;
  19 use middle::typeck::infer::to_str::InferStr;
  20 use middle::typeck::infer::{cres, InferCtxt};
  21 use middle::typeck::infer::fold_regions_in_sig;
  22 use middle::typeck::infer::{TypeTrace, Subtype};
  23 use std::collections::HashMap;
  24 use syntax::ast::{Many, Once, NodeId};
  25 use syntax::ast::{NormalFn, UnsafeFn};
  26 use syntax::ast::{Onceness, FnStyle};
  27 use syntax::ast::{MutMutable, MutImmutable};
  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) -> String { "lub".to_string() }
  39     fn a_is_expected(&self) -> bool { self.get_ref().a_is_expected }
  40     fn trace(&self) -> TypeTrace { self.get_ref().trace.clone() }
  41
  42     fn sub<'a>(&'a self) -> Sub<'a> { Sub(self.get_ref().clone()) }
  43     fn lub<'a>(&'a self) -> Lub<'a> { Lub(self.get_ref().clone()) }
  44     fn glb<'a>(&'a self) -> Glb<'a> { Glb(self.get_ref().clone()) }
  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         self.glb().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         }
  83     }
  84
  85     fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<Onceness> {
  86         match (a, b) {
  87             (Once, _) | (_, Once) => Ok(Once),
  88             (Many, Many) => Ok(Many)
  89         }
  90     }
  91
  92     fn bounds(&self, a: BuiltinBounds, b: BuiltinBounds) -> cres<BuiltinBounds> {
  93         // More bounds is a subtype of fewer bounds, so
  94         // the LUB (mutual supertype) is the intersection.
  95         Ok(a.intersection(b))
  96     }
  97
  98     fn contraregions(&self, a: ty::Region, b: ty::Region)
  99                     -> cres<ty::Region> {
 100         self.glb().regions(a, b)
 101     }
 102
 103     fn regions(&self, a: ty::Region, b: ty::Region) -> cres<ty::Region> {
 104         debug!("{}.regions({:?}, {:?})",
 105                self.tag(),
 106                a.inf_str(self.get_ref().infcx),
 107                b.inf_str(self.get_ref().infcx));
 108
 109         Ok(self.get_ref().infcx.region_vars.lub_regions(Subtype(self.trace()), a, b))
 110     }
 111
 112     fn fn_sigs(&self, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig> {
 113         // Note: this is a subtle algorithm.  For a full explanation,
 114         // please see the large comment in `region_inference.rs`.
 115
 116         // Take a snapshot.  We'll never roll this back, but in later
 117         // phases we do want to be able to examine "all bindings that
 118         // were created as part of this type comparison", and making a
 119         // snapshot is a convenient way to do that.
 120         let snapshot = self.get_ref().infcx.region_vars.start_snapshot();
 121
 122         // Instantiate each bound region with a fresh region variable.
 123         let (a_with_fresh, a_map) =
 124             self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
 125                 self.trace(), a);
 126         let (b_with_fresh, _) =
 127             self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
 128                 self.trace(), b);
 129
 130         // Collect constraints.
 131         let sig0 = if_ok!(super_fn_sigs(self, &a_with_fresh, &b_with_fresh));
 132         debug!("sig0 = {}", sig0.inf_str(self.get_ref().infcx));
 133
 134         // Generalize the regions appearing in sig0 if possible
 135         let new_vars =
 136             self.get_ref().infcx.region_vars.vars_created_since_snapshot(snapshot);
 137         let sig1 =
 138             fold_regions_in_sig(
 139                 self.get_ref().infcx.tcx,
 140                 &sig0,
 141                 |r| generalize_region(self, snapshot, new_vars.as_slice(),
 142                                       sig0.binder_id, &a_map, r));
 143         return Ok(sig1);
 144
 145         fn generalize_region(this: &Lub,
 146                              snapshot: uint,
 147                              new_vars: &[RegionVid],
 148                              new_scope: NodeId,
 149                              a_map: &HashMap<ty::BoundRegion, ty::Region>,
 150                              r0: ty::Region)
 151                              -> ty::Region {
 152             // Regions that pre-dated the LUB computation stay as they are.
 153             if !is_var_in_set(new_vars, r0) {
 154                 assert!(!r0.is_bound());
 155                 debug!("generalize_region(r0={:?}): not new variable", r0);
 156                 return r0;
 157             }
 158
 159             let tainted = this.get_ref().infcx.region_vars.tainted(snapshot, r0);
 160
 161             // Variables created during LUB computation which are
 162             // *related* to regions that pre-date the LUB computation
 163             // stay as they are.
 164             if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) {
 165                 debug!("generalize_region(r0={:?}): \
 166                         non-new-variables found in {:?}",
 167                        r0, tainted);
 168                 assert!(!r0.is_bound());
 169                 return r0;
 170             }
 171
 172             // Otherwise, the variable must be associated with at
 173             // least one of the variables representing bound regions
 174             // in both A and B.  Replace the variable with the "first"
 175             // bound region from A that we find it to be associated
 176             // with.
 177             for (a_br, a_r) in a_map.iter() {
 178                 if tainted.iter().any(|x| x == a_r) {
 179                     debug!("generalize_region(r0={:?}): \
 180                             replacing with {:?}, tainted={:?}",
 181                            r0, *a_br, tainted);
 182                     return ty::ReLateBound(new_scope, *a_br);
 183                 }
 184             }
 185
 186             this.get_ref().infcx.tcx.sess.span_bug(
 187                 this.get_ref().trace.origin.span(),
 188                 format!("region {:?} is not associated with \
 189                          any bound region from A!",
 190                         r0).as_slice())
 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 }