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::{cres, InferCtxt};
  20 use middle::typeck::infer::fold_regions_in_sig;
  21 use middle::typeck::infer::{TypeTrace, Subtype};
  22 use middle::typeck::infer::region_inference::RegionMark;
  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 use util::ppaux::Repr;
  30
  31 pub struct Lub<'f>(pub CombineFields<'f>);  // least-upper-bound: common supertype
  32
  33 impl<'f> Lub<'f> {
  34     pub fn get_ref<'a>(&'a self) -> &'a CombineFields<'f> { let Lub(ref v) = *self; v }
  35 }
  36
  37 impl<'f> Combine for Lub<'f> {
  38     fn infcx<'a>(&'a self) -> &'a InferCtxt<'a> { self.get_ref().infcx }
  39     fn tag(&self) -> String { "lub".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         if a.mutbl != b.mutbl {
  56             return Err(ty::terr_mutability)
  57         }
  58
  59         let m = a.mutbl;
  60         match m {
  61           MutImmutable => {
  62             self.tys(a.ty, b.ty).and_then(|t| Ok(ty::mt {ty: t, mutbl: m}) )
  63           }
  64
  65           MutMutable => {
  66             self.get_ref().infcx.try(|| {
  67                 eq_tys(self, a.ty, b.ty).then(|| {
  68                     Ok(ty::mt {ty: a.ty, mutbl: m})
  69                 })
  70             }).or_else(|e| Err(e))
  71           }
  72         }
  73     }
  74
  75     fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
  76         self.glb().tys(a, b)
  77     }
  78
  79     fn fn_styles(&self, a: FnStyle, b: FnStyle) -> cres<FnStyle> {
  80         match (a, b) {
  81           (UnsafeFn, _) | (_, UnsafeFn) => Ok(UnsafeFn),
  82           (NormalFn, NormalFn) => Ok(NormalFn),
  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         self.glb().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.repr(self.get_ref().infcx.tcx),
 108                b.repr(self.get_ref().infcx.tcx));
 109
 110         Ok(self.get_ref().infcx.region_vars.lub_regions(Subtype(self.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         // Make a mark so we can examine "all bindings that were
 118         // created as part of this type comparison".
 119         let mark = self.get_ref().infcx.region_vars.mark();
 120
 121         // Instantiate each bound region with a fresh region variable.
 122         let (a_with_fresh, a_map) =
 123             self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
 124                 self.trace(), a);
 125         let (b_with_fresh, _) =
 126             self.get_ref().infcx.replace_late_bound_regions_with_fresh_regions(
 127                 self.trace(), b);
 128
 129         // Collect constraints.
 130         let sig0 = if_ok!(super_fn_sigs(self, &a_with_fresh, &b_with_fresh));
 131         debug!("sig0 = {}", sig0.repr(self.get_ref().infcx.tcx));
 132
 133         // Generalize the regions appearing in sig0 if possible
 134         let new_vars =
 135             self.get_ref().infcx.region_vars.vars_created_since_mark(mark);
 136         let sig1 =
 137             fold_regions_in_sig(
 138                 self.get_ref().infcx.tcx,
 139                 &sig0,
 140                 |r| generalize_region(self, mark, new_vars.as_slice(),
 141                                       sig0.binder_id, &a_map, r));
 142         return Ok(sig1);
 143
 144         fn generalize_region(this: &Lub,
 145                              mark: RegionMark,
 146                              new_vars: &[RegionVid],
 147                              new_scope: NodeId,
 148                              a_map: &HashMap<ty::BoundRegion, ty::Region>,
 149                              r0: ty::Region)
 150                              -> ty::Region {
 151             // Regions that pre-dated the LUB computation stay as they are.
 152             if !is_var_in_set(new_vars, r0) {
 153                 assert!(!r0.is_bound());
 154                 debug!("generalize_region(r0={:?}): not new variable", r0);
 155                 return r0;
 156             }
 157
 158             let tainted = this.get_ref().infcx.region_vars.tainted(mark, r0);
 159
 160             // Variables created during LUB computation which are
 161             // *related* to regions that pre-date the LUB computation
 162             // stay as they are.
 163             if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) {
 164                 debug!("generalize_region(r0={:?}): \
 165                         non-new-variables found in {:?}",
 166                        r0, tainted);
 167                 assert!(!r0.is_bound());
 168                 return r0;
 169             }
 170
 171             // Otherwise, the variable must be associated with at
 172             // least one of the variables representing bound regions
 173             // in both A and B.  Replace the variable with the "first"
 174             // bound region from A that we find it to be associated
 175             // with.
 176             for (a_br, a_r) in a_map.iter() {
 177                 if tainted.iter().any(|x| x == a_r) {
 178                     debug!("generalize_region(r0={:?}): \
 179                             replacing with {:?}, tainted={:?}",
 180                            r0, *a_br, tainted);
 181                     return ty::ReLateBound(new_scope, *a_br);
 182                 }
 183             }
 184
 185             this.get_ref().infcx.tcx.sess.span_bug(
 186                 this.get_ref().trace.origin.span(),
 187                 format!("region {:?} is not associated with \
 188                          any bound region from A!",
 189                         r0).as_slice())
 190         }
 191     }
 192
 193     fn tys(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
 194         super_lattice_tys(self, a, b)
 195     }
 196 }