Correct handling of if/match, and make explicit computation of

common supertypes.

This was breaking with the change to regions because of the
(now incorrect) assumpton that our inference code makes,
which is that if a <: b succeeds, there is no need to compute
the LUB/GLB.

12 files changed, 265 insertions, 120 deletions

diff --git a/src/librustc/middle/typeck/check/_match.rs b/src/librustc/middle/typeck/check/_match.rs
index 351d09b7ce5..45867ae77e0 100644
--- a/src/librustc/middle/typeck/check/_match.rs
+++ b/src/librustc/middle/typeck/check/_match.rs
@@ -30,8 +30,8 @@ pub fn check_match(fcx: @mut FnCtxt,
                    arms: &[ast::arm]) {
     let tcx = fcx.ccx.tcx;
 
-    let pattern_ty = fcx.infcx().next_ty_var();
-    check_expr_has_type(fcx, discrim, pattern_ty);
+    let discrim_ty = fcx.infcx().next_ty_var();
+    check_expr_has_type(fcx, discrim, discrim_ty);
 
     // Typecheck the patterns first, so that we get types for all the
     // bindings.
@@ -41,13 +41,20 @@ pub fn check_match(fcx: @mut FnCtxt,
             map: pat_id_map(tcx.def_map, arm.pats[0]),
         };
 
-        for arm.pats.iter().advance |p| { check_pat(&pcx, *p, pattern_ty);}
+        for arm.pats.iter().advance |p| { check_pat(&pcx, *p, discrim_ty);}
     }
 
+    // The result of the match is the common supertype of all the
+    // arms. Start out the value as bottom, since it's the, well,
+    // bottom the type lattice, and we'll be moving up the lattice as
+    // we process each arm. (Note that any match with 0 arms is matching
+    // on any empty type and is therefore unreachable; should the flow
+    // of execution reach it, we will fail, so bottom is an appropriate
+    // type in that case)
+    let mut result_ty = ty::mk_bot();
+
     // Now typecheck the blocks.
-    let mut result_ty = fcx.infcx().next_ty_var();
-    let mut arm_non_bot = false;
-    let mut saw_err = false;
+    let mut saw_err = ty::type_is_error(discrim_ty);
     for arms.iter().advance |arm| {
         let mut guard_err = false;
         let mut guard_bot = false;
@@ -74,18 +81,22 @@ pub fn check_match(fcx: @mut FnCtxt,
         else if guard_bot {
             fcx.write_bot(arm.body.node.id);
         }
-        else if !ty::type_is_bot(bty) {
-            arm_non_bot = true; // If the match *may* evaluate to a non-_|_
-                                // expr, the whole thing is non-_|_
-        }
-        demand::suptype(fcx, arm.body.span, result_ty, bty);
+
+        result_ty =
+            infer::common_supertype(
+                fcx.infcx(),
+                infer::MatchExpression(expr.span),
+                true, // result_ty is "expected" here
+                result_ty,
+                bty);
     }
+
     if saw_err {
         result_ty = ty::mk_err();
-    }
-    else if !arm_non_bot {
+    } else if ty::type_is_bot(discrim_ty) {
         result_ty = ty::mk_bot();
     }
+
     fcx.write_ty(expr.id, result_ty);
 }
 
@@ -647,3 +658,4 @@ pub fn check_pointer_pat(pcx: &pat_ctxt,
 
 #[deriving(Eq)]
 enum PointerKind { Managed, Send, Borrowed }
+
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index b397181ddca..98db885ba42 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -848,7 +848,7 @@ impl FnCtxt {
 
     pub fn mk_subty(&self,
                     a_is_expected: bool,
-                    origin: infer::SubtypeOrigin,
+                    origin: infer::TypeOrigin,
                     sub: ty::t,
                     sup: ty::t)
                     -> Result<(), ty::type_err> {
@@ -886,7 +886,7 @@ impl FnCtxt {
 
     pub fn mk_eqty(&self,
                    a_is_expected: bool,
-                   origin: infer::SubtypeOrigin,
+                   origin: infer::TypeOrigin,
                    sub: ty::t,
                    sup: ty::t)
                    -> Result<(), ty::type_err> {
@@ -1436,27 +1436,42 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
     // A generic function for checking the then and else in an if
     // or if-check
     fn check_then_else(fcx: @mut FnCtxt,
-                       thn: &ast::blk,
-                       elsopt: Option<@ast::expr>,
+                       cond_expr: @ast::expr,
+                       then_blk: &ast::blk,
+                       opt_else_expr: Option<@ast::expr>,
                        id: ast::node_id,
-                       _sp: span) {
-        let if_t =
-            match elsopt {
-                Some(els) => {
-                    let if_t = fcx.infcx().next_ty_var();
-                    check_block(fcx, thn);
-                    let thn_t = fcx.node_ty(thn.node.id);
-                    demand::suptype(fcx, thn.span, if_t, thn_t);
-                    check_expr_has_type(fcx, els, if_t);
-                    if_t
-                }
-                None => {
-                    check_block_no_value(fcx, thn);
-                    ty::mk_nil()
-                }
-            };
+                       sp: span,
+                       expected: Option<ty::t>) {
+        check_expr_has_type(fcx, cond_expr, ty::mk_bool());
+
+        let branches_ty = match opt_else_expr {
+            Some(else_expr) => {
+                check_block_with_expected(fcx, then_blk, expected);
+                let then_ty = fcx.node_ty(then_blk.node.id);
+                check_expr_with_opt_hint(fcx, else_expr, expected);
+                let else_ty = fcx.expr_ty(else_expr);
+                infer::common_supertype(fcx.infcx(),
+                                        infer::IfExpression(sp),
+                                        true,
+                                        then_ty,
+                                        else_ty)
+            }
+            None => {
+                check_block_no_value(fcx, then_blk);
+                ty::mk_nil()
+            }
+        };
 
-        fcx.write_ty(id, if_t);
+        let cond_ty = fcx.expr_ty(cond_expr);
+        let if_ty = if ty::type_is_error(cond_ty) {
+            ty::mk_err()
+        } else if ty::type_is_bot(cond_ty) {
+            ty::mk_bot()
+        } else {
+            branches_ty
+        };
+
+        fcx.write_ty(id, if_ty);
     }
 
     fn lookup_op_method(fcx: @mut FnCtxt,
@@ -2501,25 +2516,9 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
             fcx.write_nil(id);
         }
       }
-      ast::expr_if(cond, ref thn, elsopt) => {
-        check_expr_has_type(fcx, cond, ty::mk_bool());
-        check_then_else(fcx, thn, elsopt, id, expr.span);
-        let cond_ty = fcx.expr_ty(cond);
-        let then_ty = fcx.node_ty(thn.node.id);
-        let else_is_bot = elsopt.map_default(false, |els| {
-              ty::type_is_bot(fcx.expr_ty(*els))});
-        if ty::type_is_error(cond_ty) || ty::type_is_error(then_ty) {
-            fcx.write_error(id);
-        }
-        else if elsopt.map_default(false, |els| {
-            ty::type_is_error(fcx.expr_ty(*els)) }) {
-            fcx.write_error(id);
-        }
-        else if ty::type_is_bot(cond_ty) ||
-            (ty::type_is_bot(then_ty) && else_is_bot) {
-            fcx.write_bot(id);
-        }
-          // Other cases were handled by check_then_else
+      ast::expr_if(cond, ref then_blk, opt_else_expr) => {
+        check_then_else(fcx, cond, then_blk, opt_else_expr,
+                        id, expr.span, expected);
       }
       ast::expr_while(cond, ref body) => {
         check_expr_has_type(fcx, cond, ty::mk_bool());
@@ -2547,30 +2546,6 @@ pub fn check_expr_with_unifier(fcx: @mut FnCtxt,
       }
       ast::expr_match(discrim, ref arms) => {
         _match::check_match(fcx, expr, discrim, *arms);
-        let discrim_ty = fcx.expr_ty(discrim);
-        let arm_tys = arms.map(|a| fcx.node_ty(a.body.node.id));
-        if ty::type_is_error(discrim_ty) ||
-            arm_tys.iter().any_(|t| ty::type_is_error(*t)) {
-            fcx.write_error(id);
-        }
-        // keep in mind that `all` returns true in the empty vec case,
-        // which is what we want
-        else if ty::type_is_bot(discrim_ty) ||
-            arm_tys.iter().all(|t| ty::type_is_bot(*t)) {
-            fcx.write_bot(id);
-        }
-        else {
-            // Find the first non-_|_ arm.
-            // We know there's at least one because we already checked
-            // for n=0 as well as all arms being _|_ in the previous
-            // `if`.
-            for arm_tys.iter().advance |arm_ty| {
-                if !ty::type_is_bot(*arm_ty) {
-                    fcx.write_ty(id, *arm_ty);
-                    break;
-                }
-            }
-        }
       }
       ast::expr_fn_block(ref decl, ref body) => {
         check_expr_fn(fcx, expr, None,
diff --git a/src/librustc/middle/typeck/infer/combine.rs b/src/librustc/middle/typeck/infer/combine.rs
index 8af454774b8..f03f0173229 100644
--- a/src/librustc/middle/typeck/infer/combine.rs
+++ b/src/librustc/middle/typeck/infer/combine.rs
@@ -65,7 +65,7 @@ use middle::typeck::infer::sub::Sub;
 use middle::typeck::infer::to_str::InferStr;
 use middle::typeck::infer::unify::{InferCtxtMethods};
 use middle::typeck::infer::{InferCtxt, cres, ures};
-use middle::typeck::infer::{SubtypeOrigin, SubtypeTrace};
+use middle::typeck::infer::{TypeOrigin, TypeTrace};
 use util::common::indent;
 
 use std::result::{iter_vec2, map_vec2};
@@ -80,7 +80,7 @@ pub trait Combine {
     fn infcx(&self) -> @mut InferCtxt;
     fn tag(&self) -> ~str;
     fn a_is_expected(&self) -> bool;
-    fn trace(&self) -> SubtypeTrace;
+    fn trace(&self) -> TypeTrace;
 
     fn sub(&self) -> Sub;
     fn lub(&self) -> Lub;
@@ -122,7 +122,7 @@ pub trait Combine {
 pub struct CombineFields {
     infcx: @mut InferCtxt,
     a_is_expected: bool,
-    trace: SubtypeTrace,
+    trace: TypeTrace,
 }
 
 pub fn expected_found<C:Combine,T>(
diff --git a/src/librustc/middle/typeck/infer/error_reporting.rs b/src/librustc/middle/typeck/infer/error_reporting.rs
index 079a01beaa1..7217f297947 100644
--- a/src/librustc/middle/typeck/infer/error_reporting.rs
+++ b/src/librustc/middle/typeck/infer/error_reporting.rs
@@ -22,7 +22,7 @@ rise to a patricular error.
 The basis of the system are the "origin" types. An "origin" is the
 reason that a constraint or inference variable arose. There are
 different "origin" enums for different kinds of constraints/variables
-(e.g., `SubtypeOrigin`, `RegionVariableOrigin`). An origin always has
+(e.g., `TypeOrigin`, `RegionVariableOrigin`). An origin always has
 a span, but also more information so that we can generate a meaningful
 error message.
 
@@ -40,7 +40,7 @@ store and later report what gave rise to the conflicting constraints.
 # Subtype Trace
 
 Determing whether `T1 <: T2` often involves a number of subtypes and
-subconstraints along the way. A "SubtypeTrace" is an extended version
+subconstraints along the way. A "TypeTrace" is an extended version
 of an origin that traces the types and other values that were being
 compared. It is not necessarily comprehensive (in fact, at the time of
 this writing it only tracks the root values being compared) but I'd
@@ -64,8 +64,8 @@ use middle::ty;
 use middle::ty::Region;
 use middle::typeck::infer;
 use middle::typeck::infer::InferCtxt;
-use middle::typeck::infer::SubtypeTrace;
-use middle::typeck::infer::SubtypeOrigin;
+use middle::typeck::infer::TypeTrace;
+use middle::typeck::infer::TypeOrigin;
 use middle::typeck::infer::SubregionOrigin;
 use middle::typeck::infer::RegionVariableOrigin;
 use middle::typeck::infer::Types;
@@ -108,8 +108,8 @@ impl InferCtxt {
         }
     }
 
-    fn report_and_explain_type_error(@mut self,
-                                     trace: SubtypeTrace,
+    pub fn report_and_explain_type_error(@mut self,
+                                     trace: TypeTrace,
                                      terr: &ty::type_err) {
         let tcx = self.tcx;
 
@@ -125,7 +125,9 @@ impl InferCtxt {
             infer::MethodCompatCheck(_) => "method not compatible with trait",
             infer::ExprAssignable(_) => "mismatched types",
             infer::RelateTraitRefs(_) => "mismatched traits",
-            infer::RelateSelfType(_) => "mismatched types"
+            infer::RelateSelfType(_) => "mismatched types",
+            infer::MatchExpression(_) => "match arms have incompatible types",
+            infer::IfExpression(_) => "if and else have incompatible types",
         };
 
         self.tcx.sess.span_err(
@@ -179,7 +181,7 @@ impl InferCtxt {
                                sup: Region) {
         match origin {
             infer::Subtype(trace) => {
-                let terr = ty::terr_regions_does_not_outlive(sub, sup);
+                let terr = ty::terr_regions_does_not_outlive(sup, sub);
                 self.report_and_explain_type_error(trace, &terr);
             }
             infer::Reborrow(span) => {
diff --git a/src/librustc/middle/typeck/infer/glb.rs b/src/librustc/middle/typeck/infer/glb.rs
index 46ccfd24eb5..fefbf2336c2 100644
--- a/src/librustc/middle/typeck/infer/glb.rs
+++ b/src/librustc/middle/typeck/infer/glb.rs
@@ -18,7 +18,7 @@ use middle::typeck::infer::lub::Lub;
 use middle::typeck::infer::sub::Sub;
 use middle::typeck::infer::to_str::InferStr;
 use middle::typeck::infer::{cres, InferCtxt};
-use middle::typeck::infer::{SubtypeTrace, Subtype};
+use middle::typeck::infer::{TypeTrace, Subtype};
 use middle::typeck::infer::fold_regions_in_sig;
 use middle::typeck::isr_alist;
 use syntax::ast;
@@ -38,7 +38,7 @@ impl Combine for Glb {
     fn infcx(&self) -> @mut InferCtxt { self.infcx }
     fn tag(&self) -> ~str { ~"glb" }
     fn a_is_expected(&self) -> bool { self.a_is_expected }
-    fn trace(&self) -> SubtypeTrace { self.trace }
+    fn trace(&self) -> TypeTrace { self.trace }
 
     fn sub(&self) -> Sub { Sub(**self) }
     fn lub(&self) -> Lub { Lub(**self) }
diff --git a/src/librustc/middle/typeck/infer/lub.rs b/src/librustc/middle/typeck/infer/lub.rs
index 5d896bdadba..efb1dc200b5 100644
--- a/src/librustc/middle/typeck/infer/lub.rs
+++ b/src/librustc/middle/typeck/infer/lub.rs
@@ -19,7 +19,7 @@ use middle::typeck::infer::sub::Sub;
 use middle::typeck::infer::to_str::InferStr;
 use middle::typeck::infer::{cres, InferCtxt};
 use middle::typeck::infer::fold_regions_in_sig;
-use middle::typeck::infer::{SubtypeTrace, Subtype};
+use middle::typeck::infer::{TypeTrace, Subtype};
 use middle::typeck::isr_alist;
 use util::common::indent;
 use util::ppaux::mt_to_str;
@@ -45,7 +45,7 @@ impl Combine for Lub {
     fn infcx(&self) -> @mut InferCtxt { self.infcx }
     fn tag(&self) -> ~str { ~"lub" }
     fn a_is_expected(&self) -> bool { self.a_is_expected }
-    fn trace(&self) -> SubtypeTrace { self.trace }
+    fn trace(&self) -> TypeTrace { self.trace }
 
     fn sub(&self) -> Sub { Sub(**self) }
     fn lub(&self) -> Lub { Lub(**self) }
diff --git a/src/librustc/middle/typeck/infer/mod.rs b/src/librustc/middle/typeck/infer/mod.rs
index 29f24f2ce9a..f8563b4eb3d 100644
--- a/src/librustc/middle/typeck/infer/mod.rs
+++ b/src/librustc/middle/typeck/infer/mod.rs
@@ -260,6 +260,7 @@ use middle::typeck::infer::combine::{Combine, CombineFields, eq_tys};
 use middle::typeck::infer::region_inference::{RegionVarBindings};
 use middle::typeck::infer::resolve::{resolver};
 use middle::typeck::infer::sub::Sub;
+use middle::typeck::infer::lub::Lub;
 use middle::typeck::infer::to_str::InferStr;
 use middle::typeck::infer::unify::{ValsAndBindings, Root};
 use middle::typeck::isr_alist;
@@ -324,7 +325,7 @@ pub struct InferCtxt {
 /// Why did we require that the two types be related?
 ///
 /// See `error_reporting.rs` for more details
-pub enum SubtypeOrigin {
+pub enum TypeOrigin {
     // Not yet categorized in a better way
     Misc(span),
 
@@ -339,6 +340,12 @@ pub enum SubtypeOrigin {
 
     // Relating trait refs when resolving vtables
     RelateSelfType(span),
+
+    // Computing common supertype in a match expression
+    MatchExpression(span),
+
+    // Computing common supertype in an if expression
+    IfExpression(span),
 }
 
 /// See `error_reporting.rs` for more details
@@ -351,8 +358,8 @@ pub enum ValuePairs {
 /// encounter an error or subtyping constraint.
 ///
 /// See `error_reporting.rs` for more details.
-pub struct SubtypeTrace {
-    origin: SubtypeOrigin,
+pub struct TypeTrace {
+    origin: TypeOrigin,
     values: ValuePairs,
 }
 
@@ -361,7 +368,7 @@ pub struct SubtypeTrace {
 /// See `error_reporting.rs` for more details
 pub enum SubregionOrigin {
     // Arose from a subtyping relation
-    Subtype(SubtypeTrace),
+    Subtype(TypeTrace),
 
     // Invocation of closure must be within its lifetime
     InvokeClosure(span),
@@ -425,7 +432,7 @@ pub enum RegionVariableOrigin {
     Autoref(span),
 
     // Regions created as part of an automatic coercion
-    Coercion(SubtypeTrace),
+    Coercion(TypeTrace),
 
     // Region variables created for bound regions
     // in a function or method that is called
@@ -487,16 +494,47 @@ pub fn new_infer_ctxt(tcx: ty::ctxt) -> @mut InferCtxt {
     }
 }
 
+pub fn common_supertype(cx: @mut InferCtxt,
+                        origin: TypeOrigin,
+                        a_is_expected: bool,
+                        a: ty::t,
+                        b: ty::t)
+                        -> ty::t {
+    /*!
+     * Computes the least upper-bound of `a` and `b`. If this is
+     * not possible, reports an error and returns ty::err.
+     */
+
+    debug!("common_supertype(%s, %s)", a.inf_str(cx), b.inf_str(cx));
+
+    let trace = TypeTrace {
+        origin: origin,
+        values: Types(expected_found(a_is_expected, a, b))
+    };
+
+    let result = do cx.commit {
+        cx.lub(a_is_expected, trace).tys(a, b)
+    };
+
+    match result {
+        Ok(t) => t,
+        Err(ref err) => {
+            cx.report_and_explain_type_error(trace, err);
+            ty::mk_err()
+        }
+    }
+}
+
 pub fn mk_subty(cx: @mut InferCtxt,
                 a_is_expected: bool,
-                origin: SubtypeOrigin,
+                origin: TypeOrigin,
                 a: ty::t,
                 b: ty::t)
              -> ures {
     debug!("mk_subty(%s <: %s)", a.inf_str(cx), b.inf_str(cx));
     do indent {
         do cx.commit {
-            let trace = SubtypeTrace {
+            let trace = TypeTrace {
                 origin: origin,
                 values: Types(expected_found(a_is_expected, a, b))
             };
@@ -509,7 +547,7 @@ pub fn can_mk_subty(cx: @mut InferCtxt, a: ty::t, b: ty::t) -> ures {
     debug!("can_mk_subty(%s <: %s)", a.inf_str(cx), b.inf_str(cx));
     do indent {
         do cx.probe {
-            let trace = SubtypeTrace {
+            let trace = TypeTrace {
                 origin: Misc(codemap::dummy_sp()),
                 values: Types(expected_found(true, a, b))
             };
@@ -531,14 +569,14 @@ pub fn mk_subr(cx: @mut InferCtxt,
 
 pub fn mk_eqty(cx: @mut InferCtxt,
                a_is_expected: bool,
-               origin: SubtypeOrigin,
+               origin: TypeOrigin,
                a: ty::t,
                b: ty::t)
             -> ures {
     debug!("mk_eqty(%s <: %s)", a.inf_str(cx), b.inf_str(cx));
     do indent {
         do cx.commit {
-            let trace = SubtypeTrace {
+            let trace = TypeTrace {
                 origin: origin,
                 values: Types(expected_found(a_is_expected, a, b))
             };
@@ -550,7 +588,7 @@ pub fn mk_eqty(cx: @mut InferCtxt,
 
 pub fn mk_sub_trait_refs(cx: @mut InferCtxt,
                          a_is_expected: bool,
-                         origin: SubtypeOrigin,
+                         origin: TypeOrigin,
                          a: @ty::TraitRef,
                          b: @ty::TraitRef)
     -> ures
@@ -559,7 +597,7 @@ pub fn mk_sub_trait_refs(cx: @mut InferCtxt,
            a.inf_str(cx), b.inf_str(cx));
     do indent {
         do cx.commit {
-            let trace = SubtypeTrace {
+            let trace = TypeTrace {
                 origin: origin,
                 values: TraitRefs(expected_found(a_is_expected, a, b))
             };
@@ -581,14 +619,14 @@ fn expected_found<T>(a_is_expected: bool,
 
 pub fn mk_coercety(cx: @mut InferCtxt,
                    a_is_expected: bool,
-                   origin: SubtypeOrigin,
+                   origin: TypeOrigin,
                    a: ty::t,
                    b: ty::t)
                 -> CoerceResult {
     debug!("mk_coercety(%s -> %s)", a.inf_str(cx), b.inf_str(cx));
     do indent {
         do cx.commit {
-            let trace = SubtypeTrace {
+            let trace = TypeTrace {
                 origin: origin,
                 values: Types(expected_found(a_is_expected, a, b))
             };
@@ -601,7 +639,7 @@ pub fn can_mk_coercety(cx: @mut InferCtxt, a: ty::t, b: ty::t) -> ures {
     debug!("can_mk_coercety(%s -> %s)", a.inf_str(cx), b.inf_str(cx));
     do indent {
         do cx.probe {
-            let trace = SubtypeTrace {
+            let trace = TypeTrace {
                 origin: Misc(codemap::dummy_sp()),
                 values: Types(expected_found(true, a, b))
             };
@@ -690,17 +728,21 @@ struct Snapshot {
 impl InferCtxt {
     pub fn combine_fields(@mut self,
                           a_is_expected: bool,
-                          trace: SubtypeTrace)
+                          trace: TypeTrace)
                           -> CombineFields {
         CombineFields {infcx: self,
                        a_is_expected: a_is_expected,
                        trace: trace}
     }
 
-    pub fn sub(@mut self, a_is_expected: bool, trace: SubtypeTrace) -> Sub {
+    pub fn sub(@mut self, a_is_expected: bool, trace: TypeTrace) -> Sub {
         Sub(self.combine_fields(a_is_expected, trace))
     }
 
+    pub fn lub(@mut self, a_is_expected: bool, trace: TypeTrace) -> Lub {
+        Lub(self.combine_fields(a_is_expected, trace))
+    }
+
     pub fn in_snapshot(&self) -> bool {
         self.region_vars.in_snapshot()
     }
@@ -946,7 +988,7 @@ impl InferCtxt {
     }
 
     pub fn replace_bound_regions_with_fresh_regions(&mut self,
-                                                    trace: SubtypeTrace,
+                                                    trace: TypeTrace,
                                                     fsig: &ty::FnSig)
                                                     -> (ty::FnSig, isr_alist) {
         let(isr, _, fn_sig) =
@@ -972,19 +1014,19 @@ pub fn fold_regions_in_sig(
     }
 }
 
-impl SubtypeTrace {
+impl TypeTrace {
     pub fn span(&self) -> span {
         self.origin.span()
     }
 }
 
-impl Repr for SubtypeTrace {
+impl Repr for TypeTrace {
     fn repr(&self, tcx: ty::ctxt) -> ~str {
-        fmt!("SubtypeTrace(%s)", self.origin.repr(tcx))
+        fmt!("TypeTrace(%s)", self.origin.repr(tcx))
     }
 }
 
-impl SubtypeOrigin {
+impl TypeOrigin {
     pub fn span(&self) -> span {
         match *self {
             MethodCompatCheck(span) => span,
@@ -992,11 +1034,13 @@ impl SubtypeOrigin {
             Misc(span) => span,
             RelateTraitRefs(span) => span,
             RelateSelfType(span) => span,
+            MatchExpression(span) => span,
+            IfExpression(span) => span,
         }
     }
 }
 
-impl Repr for SubtypeOrigin {
+impl Repr for TypeOrigin {
     fn repr(&self, tcx: ty::ctxt) -> ~str {
         match *self {
             MethodCompatCheck(a) => fmt!("MethodCompatCheck(%s)", a.repr(tcx)),
@@ -1004,6 +1048,8 @@ impl Repr for SubtypeOrigin {
             Misc(a) => fmt!("Misc(%s)", a.repr(tcx)),
             RelateTraitRefs(a) => fmt!("RelateTraitRefs(%s)", a.repr(tcx)),
             RelateSelfType(a) => fmt!("RelateSelfType(%s)", a.repr(tcx)),
+            MatchExpression(a) => fmt!("MatchExpression(%s)", a.repr(tcx)),
+            IfExpression(a) => fmt!("IfExpression(%s)", a.repr(tcx)),
         }
     }
 }
diff --git a/src/librustc/middle/typeck/infer/region_inference.rs b/src/librustc/middle/typeck/infer/region_inference.rs
index 82fbb6b8ce7..c674cbc0f63 100644
--- a/src/librustc/middle/typeck/infer/region_inference.rs
+++ b/src/librustc/middle/typeck/infer/region_inference.rs
@@ -1528,6 +1528,8 @@ impl RegionVarBindings {
                 loop;
             }
 
+            debug!("ConcreteFailure: !(sub <= sup): sub=%?, sup=%?",
+                   sub, sup);
             errors.push(ConcreteFailure(origin, sub, sup));
         }
     }
diff --git a/src/librustc/middle/typeck/infer/sub.rs b/src/librustc/middle/typeck/infer/sub.rs
index ea66f8601af..72178500b54 100644
--- a/src/librustc/middle/typeck/infer/sub.rs
+++ b/src/librustc/middle/typeck/infer/sub.rs
@@ -20,7 +20,7 @@ use middle::typeck::infer::InferCtxt;
 use middle::typeck::infer::lattice::CombineFieldsLatticeMethods;
 use middle::typeck::infer::lub::Lub;
 use middle::typeck::infer::to_str::InferStr;
-use middle::typeck::infer::{SubtypeTrace, Subtype};
+use middle::typeck::infer::{TypeTrace, Subtype};
 use util::common::{indent, indenter};
 use util::ppaux::bound_region_to_str;
 
@@ -37,7 +37,7 @@ impl Combine for Sub {
     fn infcx(&self) -> @mut InferCtxt { self.infcx }
     fn tag(&self) -> ~str { ~"sub" }
     fn a_is_expected(&self) -> bool { self.a_is_expected }
-    fn trace(&self) -> SubtypeTrace { self.trace }
+    fn trace(&self) -> TypeTrace { self.trace }
 
     fn sub(&self) -> Sub { Sub(**self) }
     fn lub(&self) -> Lub { Lub(**self) }
diff --git a/src/test/compile-fail/if-branch-types.rs b/src/test/compile-fail/if-branch-types.rs
index 74baceb39d3..1c6dd0ef9f6 100644
--- a/src/test/compile-fail/if-branch-types.rs
+++ b/src/test/compile-fail/if-branch-types.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern:mismatched types
-
-fn main() { let x = if true { 10i } else { 10u }; }
+fn main() {
+    let x = if true { 10i } else { 10u };
+    //~^ ERROR if and else have incompatible types: expected `int` but found `uint`
+}
diff --git a/src/test/compile-fail/lub-if.rs b/src/test/compile-fail/lub-if.rs
new file mode 100644
index 00000000000..358c6192147
--- /dev/null
+++ b/src/test/compile-fail/lub-if.rs
@@ -0,0 +1,52 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that we correctly consider the type of `match` to be the LUB
+// of the various arms, particularly in the case where regions are
+// involved.
+
+pub fn opt_str0<'a>(maybestr: &'a Option<~str>) -> &'a str {
+    if maybestr.is_none() {
+        "(none)"
+    } else {
+        let s: &'a str = *maybestr.get_ref();
+        s
+    }
+}
+
+pub fn opt_str1<'a>(maybestr: &'a Option<~str>) -> &'a str {
+    if maybestr.is_some() {
+        let s: &'a str = *maybestr.get_ref();
+        s
+    } else {
+        "(none)"
+    }
+}
+
+pub fn opt_str2<'a>(maybestr: &'a Option<~str>) -> &'static str {
+    if maybestr.is_none() { //~ ERROR mismatched types
+        "(none)"
+    } else {
+        let s: &'a str = *maybestr.get_ref();
+        s
+    }
+}
+
+pub fn opt_str3<'a>(maybestr: &'a Option<~str>) -> &'static str {
+    if maybestr.is_some() {  //~ ERROR mismatched types
+        let s: &'a str = *maybestr.get_ref();
+        s
+    } else {
+        "(none)"
+    }
+}
+
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/compile-fail/lub-match.rs b/src/test/compile-fail/lub-match.rs
new file mode 100644
index 00000000000..2a61b72997d
--- /dev/null
+++ b/src/test/compile-fail/lub-match.rs
@@ -0,0 +1,55 @@
+// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that we correctly consider the type of `match` to be the LUB
+// of the various arms, particularly in the case where regions are
+// involved.
+
+pub fn opt_str0<'a>(maybestr: &'a Option<~str>) -> &'a str {
+    match *maybestr {
+        Some(ref s) => {
+            let s: &'a str = *s;
+            s
+        }
+        None => "(none)",
+    }
+}
+
+pub fn opt_str1<'a>(maybestr: &'a Option<~str>) -> &'a str {
+    match *maybestr {
+        None => "(none)",
+        Some(ref s) => {
+            let s: &'a str = *s;
+            s
+        }
+    }
+}
+
+pub fn opt_str2<'a>(maybestr: &'a Option<~str>) -> &'static str {
+    match *maybestr { //~ ERROR mismatched types
+        None => "(none)",
+        Some(ref s) => {
+            let s: &'a str = *s;
+            s
+        }
+    }
+}
+
+pub fn opt_str3<'a>(maybestr: &'a Option<~str>) -> &'static str {
+    match *maybestr { //~ ERROR mismatched types
+        Some(ref s) => {
+            let s: &'a str = *s;
+            s
+        }
+        None => "(none)",
+    }
+}
+
+fn main() {}
\ No newline at end of file