Auto merge of #51622 - kennytm:three-field-range-inclusive, r=SimonSapin

Change RangeInclusive to a three-field struct.

Fix #45222.

This PR also reverts #48012 (i.e. removed the `try_fold`/`try_rfold` specialization for `RangeInclusive`) because LLVM no longer has trouble recognizing a RangeInclusive loop.

7 files changed, 208 insertions, 112 deletions

diff --git a/src/libcore/iter/mod.rs b/src/libcore/iter/mod.rs
index 86b297557dd..35ae7741106 100644
--- a/src/libcore/iter/mod.rs
+++ b/src/libcore/iter/mod.rs
@@ -787,17 +787,19 @@ where
     #[inline]
     fn spec_next(&mut self) -> Option<Self::Item> {
         self.first_take = false;
-        if !(self.iter.start <= self.iter.end) {
+        self.iter.compute_is_empty();
+        if self.iter.is_empty.unwrap_or_default() {
             return None;
         }
         // add 1 to self.step to get original step size back
         // it was decremented for the general case on construction
         if let Some(n) = self.iter.start.add_usize(self.step+1) {
+            self.iter.is_empty = Some(!(n <= self.iter.end));
             let next = mem::replace(&mut self.iter.start, n);
             Some(next)
         } else {
-            let last = self.iter.start.replace_one();
-            self.iter.end.replace_zero();
+            let last = self.iter.start.clone();
+            self.iter.is_empty = Some(true);
             Some(last)
         }
     }
diff --git a/src/libcore/iter/range.rs b/src/libcore/iter/range.rs
index 0b279f66b88..651c7a35d41 100644
--- a/src/libcore/iter/range.rs
+++ b/src/libcore/iter/range.rs
@@ -10,7 +10,7 @@
 
 use convert::TryFrom;
 use mem;
-use ops::{self, Add, Sub, Try};
+use ops::{self, Add, Sub};
 use usize;
 
 use super::{FusedIterator, TrustedLen};
@@ -330,23 +330,23 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
 
     #[inline]
     fn next(&mut self) -> Option<A> {
-        if self.start <= self.end {
-            if self.start < self.end {
-                let n = self.start.add_one();
-                Some(mem::replace(&mut self.start, n))
-            } else {
-                let last = self.start.replace_one();
-                self.end.replace_zero();
-                Some(last)
-            }
-        } else {
-            None
+        self.compute_is_empty();
+        if self.is_empty.unwrap_or_default() {
+            return None;
         }
+        let is_iterating = self.start < self.end;
+        self.is_empty = Some(!is_iterating);
+        Some(if is_iterating {
+            let n = self.start.add_one();
+            mem::replace(&mut self.start, n)
+        } else {
+            self.start.clone()
+        })
     }
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        if !(self.start <= self.end) {
+        if self.is_empty() {
             return (0, Some(0));
         }
 
@@ -358,25 +358,29 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
 
     #[inline]
     fn nth(&mut self, n: usize) -> Option<A> {
+        self.compute_is_empty();
+        if self.is_empty.unwrap_or_default() {
+            return None;
+        }
+
         if let Some(plus_n) = self.start.add_usize(n) {
             use cmp::Ordering::*;
 
             match plus_n.partial_cmp(&self.end) {
                 Some(Less) => {
+                    self.is_empty = Some(false);
                     self.start = plus_n.add_one();
                     return Some(plus_n)
                 }
                 Some(Equal) => {
-                    self.start.replace_one();
-                    self.end.replace_zero();
+                    self.is_empty = Some(true);
                     return Some(plus_n)
                 }
                 _ => {}
             }
         }
 
-        self.start.replace_one();
-        self.end.replace_zero();
+        self.is_empty = Some(true);
         None
     }
 
@@ -394,68 +398,24 @@ impl<A: Step> Iterator for ops::RangeInclusive<A> {
     fn max(mut self) -> Option<A> {
         self.next_back()
     }
-
-    #[inline]
-    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
-        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
-    {
-        let mut accum = init;
-        if self.start <= self.end {
-            loop {
-                let (x, done) =
-                    if self.start < self.end {
-                        let n = self.start.add_one();
-                        (mem::replace(&mut self.start, n), false)
-                    } else {
-                        self.end.replace_zero();
-                        (self.start.replace_one(), true)
-                    };
-                accum = f(accum, x)?;
-                if done { break }
-            }
-        }
-        Try::from_ok(accum)
-    }
 }
 
 #[stable(feature = "inclusive_range", since = "1.26.0")]
 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
     #[inline]
     fn next_back(&mut self) -> Option<A> {
-        if self.start <= self.end {
-            if self.start < self.end {
-                let n = self.end.sub_one();
-                Some(mem::replace(&mut self.end, n))
-            } else {
-                let last = self.end.replace_zero();
-                self.start.replace_one();
-                Some(last)
-            }
-        } else {
-            None
+        self.compute_is_empty();
+        if self.is_empty.unwrap_or_default() {
+            return None;
         }
-    }
-
-    #[inline]
-    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
-        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
-    {
-        let mut accum = init;
-        if self.start <= self.end {
-            loop {
-                let (x, done) =
-                    if self.start < self.end {
-                        let n = self.end.sub_one();
-                        (mem::replace(&mut self.end, n), false)
-                    } else {
-                        self.start.replace_one();
-                        (self.end.replace_zero(), true)
-                    };
-                accum = f(accum, x)?;
-                if done { break }
-            }
-        }
-        Try::from_ok(accum)
+        let is_iterating = self.start < self.end;
+        self.is_empty = Some(!is_iterating);
+        Some(if is_iterating {
+            let n = self.end.sub_one();
+            mem::replace(&mut self.end, n)
+        } else {
+            self.end.clone()
+        })
     }
 }
 
diff --git a/src/libcore/ops/range.rs b/src/libcore/ops/range.rs
index 01e279589da..9c635678d7a 100644
--- a/src/libcore/ops/range.rs
+++ b/src/libcore/ops/range.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 use fmt;
+use hash::{Hash, Hasher};
 
 /// An unbounded range (`..`).
 ///
@@ -326,15 +327,56 @@ impl<Idx: PartialOrd<Idx>> RangeTo<Idx> {
 /// assert_eq!(arr[1..=2], [  1,2  ]);  // RangeInclusive
 /// ```
 #[doc(alias = "..=")]
-#[derive(Clone, PartialEq, Eq, Hash)]  // not Copy -- see #27186
+#[derive(Clone)]  // not Copy -- see #27186
 #[stable(feature = "inclusive_range", since = "1.26.0")]
 pub struct RangeInclusive<Idx> {
-    // FIXME: The current representation follows RFC 1980,
-    // but it is known that LLVM is not able to optimize loops following that RFC.
-    // Consider adding an extra `bool` field to indicate emptiness of the range.
-    // See #45222 for performance test cases.
     pub(crate) start: Idx,
     pub(crate) end: Idx,
+    pub(crate) is_empty: Option<bool>,
+    // This field is:
+    //  - `None` when next() or next_back() was never called
+    //  - `Some(false)` when `start <= end` assuming no overflow
+    //  - `Some(true)` otherwise
+    // The field cannot be a simple `bool` because the `..=` constructor can
+    // accept non-PartialOrd types, also we want the constructor to be const.
+}
+
+trait RangeInclusiveEquality: Sized {
+    fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool;
+}
+impl<T> RangeInclusiveEquality for T {
+    #[inline]
+    default fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
+        range.is_empty.unwrap_or_default()
+    }
+}
+impl<T: PartialOrd> RangeInclusiveEquality for T {
+    #[inline]
+    fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
+        range.is_empty()
+    }
+}
+
+#[stable(feature = "inclusive_range", since = "1.26.0")]
+impl<Idx: PartialEq> PartialEq for RangeInclusive<Idx> {
+    #[inline]
+    fn eq(&self, other: &Self) -> bool {
+        self.start == other.start && self.end == other.end
+            && RangeInclusiveEquality::canonicalized_is_empty(self)
+                == RangeInclusiveEquality::canonicalized_is_empty(other)
+    }
+}
+
+#[stable(feature = "inclusive_range", since = "1.26.0")]
+impl<Idx: Eq> Eq for RangeInclusive<Idx> {}
+
+#[stable(feature = "inclusive_range", since = "1.26.0")]
+impl<Idx: Hash> Hash for RangeInclusive<Idx> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.start.hash(state);
+        self.end.hash(state);
+        RangeInclusiveEquality::canonicalized_is_empty(self).hash(state);
+    }
 }
 
 impl<Idx> RangeInclusive<Idx> {
@@ -350,7 +392,7 @@ impl<Idx> RangeInclusive<Idx> {
     #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
     #[inline]
     pub const fn new(start: Idx, end: Idx) -> Self {
-        Self { start, end }
+        Self { start, end, is_empty: None }
     }
 
     /// Returns the lower bound of the range (inclusive).
@@ -492,8 +534,17 @@ impl<Idx: PartialOrd<Idx>> RangeInclusive<Idx> {
     /// assert!(r.is_empty());
     /// ```
     #[unstable(feature = "range_is_empty", reason = "recently added", issue = "48111")]
+    #[inline]
     pub fn is_empty(&self) -> bool {
-        !(self.start <= self.end)
+        self.is_empty.unwrap_or_else(|| !(self.start <= self.end))
+    }
+
+    // If this range's `is_empty` is field is unknown (`None`), update it to be a concrete value.
+    #[inline]
+    pub(crate) fn compute_is_empty(&mut self) {
+        if self.is_empty.is_none() {
+            self.is_empty = Some(!(self.start <= self.end));
+        }
     }
 }
 
diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index f6ef4a79dc7..b766140ffe9 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -2265,36 +2265,36 @@ impl<T> SliceIndex<[T]> for ops::RangeInclusive<usize> {
 
     #[inline]
     fn get(self, slice: &[T]) -> Option<&[T]> {
-        if self.end == usize::max_value() { None }
-        else { (self.start..self.end + 1).get(slice) }
+        if *self.end() == usize::max_value() { None }
+        else { (*self.start()..self.end() + 1).get(slice) }
     }
 
     #[inline]
     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
-        if self.end == usize::max_value() { None }
-        else { (self.start..self.end + 1).get_mut(slice) }
+        if *self.end() == usize::max_value() { None }
+        else { (*self.start()..self.end() + 1).get_mut(slice) }
     }
 
     #[inline]
     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
-        (self.start..self.end + 1).get_unchecked(slice)
+        (*self.start()..self.end() + 1).get_unchecked(slice)
     }
 
     #[inline]
     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
-        (self.start..self.end + 1).get_unchecked_mut(slice)
+        (*self.start()..self.end() + 1).get_unchecked_mut(slice)
     }
 
     #[inline]
     fn index(self, slice: &[T]) -> &[T] {
-        if self.end == usize::max_value() { slice_index_overflow_fail(); }
-        (self.start..self.end + 1).index(slice)
+        if *self.end() == usize::max_value() { slice_index_overflow_fail(); }
+        (*self.start()..self.end() + 1).index(slice)
     }
 
     #[inline]
     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
-        if self.end == usize::max_value() { slice_index_overflow_fail(); }
-        (self.start..self.end + 1).index_mut(slice)
+        if *self.end() == usize::max_value() { slice_index_overflow_fail(); }
+        (*self.start()..self.end() + 1).index_mut(slice)
     }
 }
 
diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs
index 5ae2f6349e5..255e8a07d75 100644
--- a/src/libcore/str/mod.rs
+++ b/src/libcore/str/mod.rs
@@ -2004,31 +2004,31 @@ mod traits {
         type Output = str;
         #[inline]
         fn get(self, slice: &str) -> Option<&Self::Output> {
-            if self.end == usize::max_value() { None }
-            else { (self.start..self.end+1).get(slice) }
+            if *self.end() == usize::max_value() { None }
+            else { (*self.start()..self.end()+1).get(slice) }
         }
         #[inline]
         fn get_mut(self, slice: &mut str) -> Option<&mut Self::Output> {
-            if self.end == usize::max_value() { None }
-            else { (self.start..self.end+1).get_mut(slice) }
+            if *self.end() == usize::max_value() { None }
+            else { (*self.start()..self.end()+1).get_mut(slice) }
         }
         #[inline]
         unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
-            (self.start..self.end+1).get_unchecked(slice)
+            (*self.start()..self.end()+1).get_unchecked(slice)
         }
         #[inline]
         unsafe fn get_unchecked_mut(self, slice: &mut str) -> &mut Self::Output {
-            (self.start..self.end+1).get_unchecked_mut(slice)
+            (*self.start()..self.end()+1).get_unchecked_mut(slice)
         }
         #[inline]
         fn index(self, slice: &str) -> &Self::Output {
-            if self.end == usize::max_value() { str_index_overflow_fail(); }
-            (self.start..self.end+1).index(slice)
+            if *self.end() == usize::max_value() { str_index_overflow_fail(); }
+            (*self.start()..self.end()+1).index(slice)
         }
         #[inline]
         fn index_mut(self, slice: &mut str) -> &mut Self::Output {
-            if self.end == usize::max_value() { str_index_overflow_fail(); }
-            (self.start..self.end+1).index_mut(slice)
+            if *self.end() == usize::max_value() { str_index_overflow_fail(); }
+            (*self.start()..self.end()+1).index_mut(slice)
         }
     }
 
diff --git a/src/test/codegen/issue-45222.rs b/src/test/codegen/issue-45222.rs
new file mode 100644
index 00000000000..30a03243f01
--- /dev/null
+++ b/src/test/codegen/issue-45222.rs
@@ -0,0 +1,74 @@
+// Copyright 2018 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.
+
+// compile-flags: -O
+// min-llvm-version 6.0
+
+#![crate_type = "lib"]
+
+// verify that LLVM recognizes a loop involving 0..=n and will const-fold it.
+
+//------------------------------------------------------------------------------
+// Example from original issue #45222
+
+fn foo2(n: u64) -> u64 {
+    let mut count = 0;
+    for _ in 0..n {
+        for j in (0..=n).rev() {
+            count += j;
+        }
+    }
+    count
+}
+
+// CHECK-LABEL: @check_foo2
+#[no_mangle]
+pub fn check_foo2() -> u64 {
+    // CHECK: ret i64 500005000000000
+    foo2(100000)
+}
+
+//------------------------------------------------------------------------------
+// Simplified example of #45222
+
+fn triangle_inc(n: u64) -> u64 {
+    let mut count = 0;
+    for j in 0 ..= n {
+        count += j;
+    }
+    count
+}
+
+// CHECK-LABEL: @check_triangle_inc
+#[no_mangle]
+pub fn check_triangle_inc() -> u64 {
+    // CHECK: ret i64 5000050000
+    triangle_inc(100000)
+}
+
+//------------------------------------------------------------------------------
+// Demo in #48012
+
+fn foo3r(n: u64) -> u64 {
+    let mut count = 0;
+    (0..n).for_each(|_| {
+        (0 ..= n).rev().for_each(|j| {
+            count += j;
+        })
+    });
+    count
+}
+
+// CHECK-LABEL: @check_foo3r
+#[no_mangle]
+pub fn check_foo3r() -> u64 {
+    // CHECK: ret i64 500005000000000
+    foo3r(100000)
+}
diff --git a/src/test/run-pass/range_inclusive.rs b/src/test/run-pass/range_inclusive.rs
index b08d16e5088..2bedfc133b5 100644
--- a/src/test/run-pass/range_inclusive.rs
+++ b/src/test/run-pass/range_inclusive.rs
@@ -10,12 +10,18 @@
 
 // Test inclusive range syntax.
 
-use std::ops::{RangeInclusive, RangeToInclusive};
+#![feature(range_is_empty)]
+#![allow(unused_comparisons)]
+
+use std::ops::RangeToInclusive;
 
 fn foo() -> isize { 42 }
 
 // Test that range syntax works in return statements
-fn return_range_to() -> RangeToInclusive<i32> { return ..=1; }
+pub fn return_range_to() -> RangeToInclusive<i32> { return ..=1; }
+
+#[derive(Debug)]
+struct P(u8);
 
 pub fn main() {
     let mut count = 0;
@@ -26,7 +32,7 @@ pub fn main() {
     assert_eq!(count, 55);
 
     let mut count = 0;
-    let mut range = 0_usize..=10;
+    let range = 0_usize..=10;
     for i in range {
         assert!(i >= 0 && i <= 10);
         count += i;
@@ -80,7 +86,7 @@ pub fn main() {
     short.next();
     assert_eq!(long.size_hint(), (255, Some(255)));
     assert_eq!(short.size_hint(), (0, Some(0)));
-    assert_eq!(short, 1..=0);
+    assert!(short.is_empty());
 
     assert_eq!(long.len(), 255);
     assert_eq!(short.len(), 0);
@@ -95,28 +101,31 @@ pub fn main() {
     for i in 3..=251 {
         assert_eq!(long.next(), Some(i));
     }
-    assert_eq!(long, 1..=0);
+    assert!(long.is_empty());
 
     // check underflow
     let mut narrow = 1..=0;
     assert_eq!(narrow.next_back(), None);
-    assert_eq!(narrow, 1..=0);
+    assert!(narrow.is_empty());
     let mut zero = 0u8..=0;
     assert_eq!(zero.next_back(), Some(0));
     assert_eq!(zero.next_back(), None);
-    assert_eq!(zero, 1..=0);
+    assert!(zero.is_empty());
     let mut high = 255u8..=255;
     assert_eq!(high.next_back(), Some(255));
     assert_eq!(high.next_back(), None);
-    assert_eq!(high, 1..=0);
+    assert!(high.is_empty());
 
     // what happens if you have a nonsense range?
     let mut nonsense = 10..=5;
     assert_eq!(nonsense.next(), None);
-    assert_eq!(nonsense, 10..=5);
+    assert!(nonsense.is_empty());
 
     // output
     assert_eq!(format!("{:?}", 0..=10), "0..=10");
     assert_eq!(format!("{:?}", ..=10), "..=10");
-    assert_eq!(format!("{:?}", long), "1..=0");
+    assert_eq!(format!("{:?}", 9..=6), "9..=6");
+
+    // ensure that constructing a RangeInclusive does not need PartialOrd bound
+    assert_eq!(format!("{:?}", P(1)..=P(2)), "P(1)..=P(2)");
 }