Review changes

9 files changed, 139 insertions, 89 deletions

diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index 1cd4d7b89d6..9c3e53a1ace 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -2542,6 +2542,64 @@ impl<A: Int> Iterator<A> for RangeStepInclusive<A> {
     }
 }
 
+
+/// The `Step` trait identifies objects which can be stepped over in both
+/// directions. The `steps_between` function provides a way to
+/// compare two Step objects (it could be provided using `step()` and `Ord`,
+/// but the implementation would be so inefficient as to be useless).
+#[unstable = "Trait is unstable."]
+pub trait Step: Ord {
+    /// Change self to the next object.
+    fn step(&mut self);
+    /// Change self to the previous object.
+    fn step_back(&mut self);
+    /// The steps_between two step objects.
+    /// a should always be less than b, so the result should never be negative.
+    /// Return None if it is not possible to calculate steps_between without
+    /// overflow.
+    fn steps_between(a: &Self, b: &Self) -> Option<uint>;
+}
+
+macro_rules! step_impl {
+    ($($t:ty)*) => ($(
+        #[unstable = "Trait is unstable."]
+        impl Step for $t {
+            #[inline]
+            fn step(&mut self) { *self += 1; }
+            #[inline]
+            fn step_back(&mut self) { *self -= 1; }
+            #[inline]
+            fn steps_between(a: &$t, b: &$t) -> Option<uint> {
+                debug_assert!(a < b);
+                Some((*a - *b) as uint)
+            }
+        }
+    )*)
+}
+
+macro_rules! step_impl_no_between {
+    ($($t:ty)*) => ($(
+        #[unstable = "Trait is unstable."]
+        impl Step for $t {
+            #[inline]
+            fn step(&mut self) { *self += 1; }
+            #[inline]
+            fn step_back(&mut self) { *self -= 1; }
+            #[inline]
+            fn steps_between(_a: &$t, _b: &$t) -> Option<uint> {
+                None
+            }
+        }
+    )*)
+}
+
+step_impl!(uint u8 u16 u32 int i8 i16 i32);
+#[cfg(target_word_size = "64")]
+step_impl!(u64 i64);
+#[cfg(target_word_size = "32")]
+step_impl_no_between!(u64 i64);
+
+
 /// An iterator that repeats an element endlessly
 #[deriving(Clone)]
 #[stable]
diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs
index 4e95849111e..0cd8c1d69d1 100644
--- a/src/libcore/ops.rs
+++ b/src/libcore/ops.rs
@@ -52,10 +52,8 @@
 //! something to the screen.
 
 use clone::Clone;
-use cmp::Ord;
-use iter::{Iterator,DoubleEndedIterator};
+use iter::{Step, Iterator,DoubleEndedIterator,ExactSizeIterator};
 use kinds::Sized;
-use kinds::Copy;
 use option::Option::{mod, Some, None};
 
 /// The `Drop` trait is used to run some code when a value goes out of scope. This
@@ -839,53 +837,13 @@ pub trait SliceMut<Sized? Idx, Sized? Result> for Sized? {
 }
 
 
-
-/// REVIEW could be in a better module
-/// The `Countable` trait identifies objects which are countable, i.e., are
-/// analogous to the natural numbers. A countable object can be incremented and
-/// and decremented and ordered. The `difference` function provides a way to
-/// compare two Countable objects (it could be provided using increment and Ord,
-/// but the implementation would be so inefficient as to be useless).
-#[unstable = "Trait is unstable."]
-pub trait Countable: Ord {
-    // FIXME(#19391) needs a snapshot
-    //type T;
-
-    /// Change self to the next object.
-    fn increment(&mut self);
-    /// Change self to the previous object.
-    fn decrement(&mut self);
-    /// The difference between two countable objects.
-    /// Temporarily a uint, should be an associated type, but
-    // FIXME(#19391) needs a snapshot
-    fn difference(a: &Self, b: &Self) -> uint;
-    //fn difference(a: &Self, b: &Self) -> <Self as Countable>::T;
-}
-
-macro_rules! countable_impl(
-    ($($t:ty)*) => ($(
-        #[unstable = "Trait is unstable."]
-        impl Countable for $t {
-            // FIXME(#19391) needs a snapshot
-            //type T = uint;
-
-            #[inline]
-            fn increment(&mut self) { *self += 1; }
-            #[inline]
-            fn decrement(&mut self) { *self -= 1; }
-            #[inline]
-            fn difference(a: &$t, b: &$t) -> uint { (*a - *b) as uint }
-        }
-    )*)
-)
-
-countable_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64)
-
 /// An unbounded range.
+#[deriving(Copy)]
 #[lang="full_range"]
 pub struct FullRange;
 
-/// A range which i bounded at both ends.
+/// A (half-open) range which is bounded at both ends.
+#[deriving(Copy)]
 #[lang="range"]
 pub struct Range<Idx> {
     /// The lower bound of the range (inclusive).
@@ -895,13 +853,13 @@ pub struct Range<Idx> {
 }
 
 // FIXME(#19391) needs a snapshot
-//impl<Idx: Clone + Countable<T=uint>> Iterator<Idx> for Range<Idx> {
-impl<Idx: Clone + Countable> Iterator<Idx> for Range<Idx> {
+//impl<Idx: Clone + Step<T=uint>> Iterator<Idx> for Range<Idx> {
+impl<Idx: Clone + Step> Iterator<Idx> for Range<Idx> {
     #[inline]
     fn next(&mut self) -> Option<Idx> {
         if self.start < self.end {
             let result = self.start.clone();
-            self.start.increment();
+            self.start.step();
             return Some(result);
         }
 
@@ -910,16 +868,19 @@ impl<Idx: Clone + Countable> Iterator<Idx> for Range<Idx> {
 
     #[inline]
     fn size_hint(&self) -> (uint, Option<uint>) {
-        let hint = Countable::difference(&self.end, &self.start);
-        (hint, Some(hint))
+        if let Some(hint) = Step::steps_between(&self.end, &self.start) {
+            (hint, Some(hint))
+        } else {
+            (0, None)
+        }
     }
 }
 
-impl<Idx: Clone + Countable> DoubleEndedIterator<Idx> for Range<Idx> {
+impl<Idx: Clone + Step> DoubleEndedIterator<Idx> for Range<Idx> {
     #[inline]
     fn next_back(&mut self) -> Option<Idx> {
         if self.start < self.end {
-            self.end.decrement();
+            self.end.step_back();
             return Some(self.end.clone());
         }
 
@@ -927,27 +888,26 @@ impl<Idx: Clone + Countable> DoubleEndedIterator<Idx> for Range<Idx> {
     }
 }
 
+impl<Idx: Clone + Step> ExactSizeIterator<Idx> for Range<Idx> {}
+
 /// A range which is only bounded below.
+#[deriving(Copy)]
 #[lang="range_from"]
 pub struct RangeFrom<Idx> {
     /// The lower bound of the range (inclusive).
     pub start: Idx,
 }
 
-impl<Idx: Clone + Countable> Iterator<Idx> for RangeFrom<Idx> {
+impl<Idx: Clone + Step> Iterator<Idx> for RangeFrom<Idx> {
     #[inline]
     fn next(&mut self) -> Option<Idx> {
         // Deliberately overflow so we loop forever.
         let result = self.start.clone();
-        self.start.increment();
+        self.start.step();
         return Some(result);
     }
 }
 
-impl<Idx: Copy> Copy for Range<Idx> {}
-impl<Idx: Copy> Copy for RangeFrom<Idx> {}
-impl Copy for FullRange {}
-
 
 /// The `Deref` trait is used to specify the functionality of dereferencing
 /// operations like `*v`.
diff --git a/src/libcoretest/ops.rs b/src/libcoretest/ops.rs
index c4acef32ee8..a8889ce9e34 100644
--- a/src/libcoretest/ops.rs
+++ b/src/libcoretest/ops.rs
@@ -34,19 +34,25 @@ fn alloc_obj_with_dtor(b: &mut Bencher) {
 #[test]
 fn test_range() {
     let r = Range { start: 2u, end: 10 };
+    let mut count = 0u;
     for (i, ri) in r.enumerate() {
         assert!(ri == i + 2);
         assert!(ri >= 2u && ri < 10u);
+        count += 1;
     }
+    assert!(count == 8);
 }
 
 #[test]
 fn test_range_from() {
     let r = RangeFrom { start: 2u };
+    let mut count = 0u;
     for (i, ri) in r.take(10).enumerate() {
         assert!(ri == i + 2);
         assert!(ri >= 2u && ri < 12u);
+        count += 1;
     }
+    assert!(count == 10);
 }
 
 #[test]
diff --git a/src/librustc/middle/infer/error_reporting.rs b/src/librustc/middle/infer/error_reporting.rs
index 0ea3d415ec5..b57b5554ed6 100644
--- a/src/librustc/middle/infer/error_reporting.rs
+++ b/src/librustc/middle/infer/error_reporting.rs
@@ -366,6 +366,7 @@ impl<'a, 'tcx> ErrorReporting<'tcx> for InferCtxt<'a, 'tcx> {
             infer::MatchExpressionArm(_, _) => "match arms have incompatible types",
             infer::IfExpression(_) => "if and else have incompatible types",
             infer::IfExpressionWithNoElse(_) => "if may be missing an else clause",
+            infer::RangeExpression(_) => "start and end of range have incompatible types",
             infer::EquatePredicate(_) => "equality predicate not satisfied",
         };
 
@@ -1490,6 +1491,9 @@ impl<'a, 'tcx> ErrorReportingHelpers<'tcx> for InferCtxt<'a, 'tcx> {
                     infer::IfExpressionWithNoElse(_) => {
                         format!("if may be missing an else clause")
                     }
+                    infer::RangeExpression(_) => {
+                        format!("start and end of range have compatible types")
+                    }
                     infer::EquatePredicate(_) => {
                         format!("equality where clause is satisfied")
                     }
diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs
index 6d031c86507..07823779216 100644
--- a/src/librustc/middle/infer/mod.rs
+++ b/src/librustc/middle/infer/mod.rs
@@ -127,6 +127,9 @@ pub enum TypeOrigin {
     // Computing common supertype of an if expression with no else counter-part
     IfExpressionWithNoElse(Span),
 
+    // Computing common supertype in a range expression
+    RangeExpression(Span),
+
     // `where a == b`
     EquatePredicate(Span),
 }
@@ -1084,6 +1087,7 @@ impl TypeOrigin {
             MatchExpressionArm(match_span, _) => match_span,
             IfExpression(span) => span,
             IfExpressionWithNoElse(span) => span,
+            RangeExpression(span) => span,
             EquatePredicate(span) => span,
         }
     }
@@ -1117,6 +1121,9 @@ impl<'tcx> Repr<'tcx> for TypeOrigin {
             IfExpressionWithNoElse(a) => {
                 format!("IfExpressionWithNoElse({})", a.repr(tcx))
             }
+            RangeExpression(a) => {
+                format!("RangeExpression({})", a.repr(tcx))
+            }
             EquatePredicate(a) => {
                 format!("EquatePredicate({})", a.repr(tcx))
             }
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 4a10954729d..380f34b1445 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -4279,44 +4279,59 @@ fn check_expr_with_unifier<'a, 'tcx, F>(fcx: &FnCtxt<'a, 'tcx>,
           }
        }
        ast::ExprRange(ref start, ref end) => {
-          let mut some_err = false;
-
           check_expr(fcx, &**start);
           let t_start = fcx.expr_ty(&**start);
-          if ty::type_is_error(t_start) {
-            fcx.write_ty(start.id, t_start);
-            some_err = true;
-          }
 
-          if let &Some(ref e) = end {
-              check_expr_has_type(fcx, &**e, t_start);
-              let t_end = fcx.expr_ty(&**e);
-              if ty::type_is_error(t_end) {
-                fcx.write_ty(e.id, t_end);
-                some_err = true;
-              }
-          }
+          let idx_type = if let &Some(ref e) = end {
+            check_expr(fcx, &**e);
+            let t_end = fcx.expr_ty(&**e);
+            if ty::type_is_error(t_end) {
+                ty::mk_err()
+            } else if t_start == ty::mk_err() {
+                ty::mk_err()
+            } else {
+                infer::common_supertype(fcx.infcx(),
+                                        infer::RangeExpression(expr.span),
+                                        true,
+                                        t_start,
+                                        t_end)
+            }
+          } else {
+            t_start
+          };
 
-          // Note that we don't check the type of the start/end satisfy any
+          // Note that we don't check the type of start/end satisfy any
           // bounds because right the range structs do not have any. If we add
           // some bounds, then we'll need to check `t_start` against them here.
 
-          if !some_err {
+          let range_type = if idx_type == ty::mk_err() {
+            ty::mk_err()
+          } else {
             // Find the did from the appropriate lang item.
             let did = if end.is_some() {
                 // Range
-                fcx.tcx().lang_items.range_struct()
+                tcx.lang_items.range_struct()
             } else {
                 // RangeFrom
-                fcx.tcx().lang_items.range_from_struct()
+                tcx.lang_items.range_from_struct()
             };
+
             if let Some(did) = did {
-                let substs = Substs::new_type(vec![t_start], vec![]);
-                fcx.write_ty(id, ty::mk_struct(tcx, did, substs));
+                let polytype = ty::lookup_item_type(tcx, did);
+                let substs = Substs::new_type(vec![idx_type], vec![]);
+                let bounds = polytype.generics.to_bounds(tcx, &substs);
+                fcx.add_obligations_for_parameters(
+                    traits::ObligationCause::new(expr.span,
+                                                 fcx.body_id,
+                                                 traits::ItemObligation(did)),
+                    &bounds);
+
+                ty::mk_struct(tcx, did, substs)
             } else {
-                fcx.write_ty(id, ty::mk_err());
+                ty::mk_err()
             }
-          }
+          };
+          fcx.write_ty(id, range_type);
        }
 
     }
diff --git a/src/test/compile-fail/range-1.rs b/src/test/compile-fail/range-1.rs
index f1751f36b39..ca7401dc26c 100644
--- a/src/test/compile-fail/range-1.rs
+++ b/src/test/compile-fail/range-1.rs
@@ -13,7 +13,7 @@
 pub fn main() {
     // Mixed types.
     let _ = 0u..10i;
-    //~^ ERROR mismatched types: expected `uint`, found `int`
+    //~^ ERROR start and end of range have incompatible types
 
     // Float => does not implement iterator.
     for i in 0f32..42f32 {}
diff --git a/src/test/compile-fail/range-2.rs b/src/test/compile-fail/range-2.rs
index e9bb14835ae..40690bd844b 100644
--- a/src/test/compile-fail/range-2.rs
+++ b/src/test/compile-fail/range-2.rs
@@ -11,13 +11,6 @@
 // Test range syntax - borrow errors.
 
 pub fn main() {
-    let x = &42i;
-    {
-        let y = 42i;
-        let r = x..&y;
-        //~^ ERROR `y` does not live long enough
-    }
-
     let r = {
         (&42i)..&42
         //~^ ERROR borrowed value does not live long enough
diff --git a/src/test/run-pass/range.rs b/src/test/run-pass/range.rs
index 64eabe19b44..027121dd422 100644
--- a/src/test/run-pass/range.rs
+++ b/src/test/run-pass/range.rs
@@ -38,4 +38,11 @@ pub fn main() {
 
     let _ = 0u..4+4-3;
     let _ = 0..foo();
+
+    // Test we can use two different types with a common supertype.
+    let x = &42i;
+    {
+        let y = 42i;
+        let _ = x..&y;
+    }
 }