Repository: pandas-dev/pandas
Pull request: BUG: Fix overflow bugs in date_Range
- [x] closes #24123
- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [ ] whatsnew entry

Fixing this turned out to be a small beast.  The overflows of interest fall into three categories.  First: overflows when computing `periods * stride` that ATM are _not_ caught, so give incorrect results:

```
>>> pd.date_range('1969-05-04', periods=200000000, freq='30000D')
DatetimeIndex(['1969-05-04', '2051-06-23', '2133-08-12'], dtype='datetime64[ns]', freq='30000D')

>>> dti = pd.date_range(start='1677-09-22', end='2262-04-11', freq='D')
>>> pd.date_range(start=dti[0], periods=len(dti), freq='D')
DatetimeIndex([], dtype='datetime64[ns]', freq='D')
```

Second, overflows when `periods * stride` overflow the int64 bounds but not uint64 bounds, which in some cases are recoverable.  The following should _not_ raise:

```
>>> dti = pd.date_range(start='1677-09-22', end='2262-04-11', freq='D')
>>> pd.date_range(start=dti[0], periods=len(dti)-1, freq='D')
[...]
pandas._libs.tslibs.np_datetime.OutOfBoundsDatetime: Cannot generate range with start=-9223286400000000000 and periods=213502
```

Last is a similar one with a negative stride where we can recover, but not by converting to uint64:

```
>>> dti = pd.date_range(start='1677-09-22', end='2262-04-11', freq='D')
>>> pd.date_range(end=dti[-1], periods=len(dti), freq='D')
[...]
pandas._libs.tslibs.np_datetime.OutOfBoundsDatetime: Cannot generate range with end=9223372800000000000 and periods=213503
```

Problem statement:
BUG: un-caught date_range overflows

TL;DR: can we assume that np.float128 exists (and is actually 128 bits)? If so then this has an easy solution.  Otherwise, it's easy-but-tedious.
 <b>update</b> Turns out the np.float128 solution doesn't as easily as I expected.

```
start = pd.Timestamp('1700-01-01')
end = pd.Timestamp('2250-12-31')

dti = pd.date_range(start, end, freq='D')

# alternative construction that _should_ work

dti2 = pd.date_range(start, periods=len(dti), freq='D')   # raises OutOfBoundsDatetime
dti3 = pd.date_range(end=end, periods=len(dti), freq='D')   # raises OutOfBoundsDatetime
```

It's actually worse than that, because it is raising the _wrong_ OutOfBoundsDatetime.  What is happening here is that in arrays.datetimes._generate_range_overflow_safe we are doing:

```
    try:
        other_end = checked_add_with_arr(np.int64(endpoint),
                                         np.int64(periods) * stride)
    except OverflowError:
        raise tslib.OutOfBoundsDatetime('Cannot generate range with '
```

In these cases, `np.int64(periods) * stride` is wrapping around.

The good news is that this is fairly easy to fix by casting to `np.uint64` instead of `np.int64`.  The bad news is that when we call `checked_add_with_arr`, if the arguments have mismatched dtypes, then it gives back a float64, and we can get an incorrect result when casting back to int64.

Obvious  next step: OK, so let's pass args with matching dtypes.  if `endpoint` is positive we can cast it to uint64 and we're done.  Otherwise [break down into 5 cases..., straightforward but tedious]


The alternative is to just cast to np.float128, do both the multiplication and addition there, then check for overflows before casting back to int64.  But IIRC some (windows) platforms don't have a "real" float128.  Is that a sufficiently ancient case that it can be ignored?


Hints from issue discussion:

Commit message: more tests, docstrings

Patch to review:
diff --git a/pandas/core/arrays/datetimes.py b/pandas/core/arrays/datetimes.py
index 89d82f1ed2042..fcddcba3f5b17 100644
--- a/pandas/core/arrays/datetimes.py
+++ b/pandas/core/arrays/datetimes.py
@@ -1728,7 +1728,14 @@ def _generate_regular_range(cls, start, end, periods, freq):
             raise ValueError("at least 'start' or 'end' should be specified "
                              "if a 'period' is given.")
 
-        values = np.arange(b, e, stride, dtype=np.int64)
+        with np.errstate(over="raise"):
+            try:
+                values = np.arange(b, e, stride, dtype=np.int64)
+            except FloatingPointError:
+                xdr = [b]
+                while xdr[-1] != e:
+                    xdr.append(xdr[-1] + stride)
+                values = np.array(xdr[:-1], dtype=np.int64)
 
     else:
         tz = None
@@ -1747,7 +1754,8 @@ def _generate_regular_range(cls, start, end, periods, freq):
     return data
 
 
-def _generate_range_overflow_safe(endpoint, periods, stride, side='start'):
+def _generate_range_overflow_safe(endpoint, periods, stride,
+                                  side='start'):
     """
     Calculate the second endpoint for passing to np.arange, checking
     to avoid an integer overflow.  Catch OverflowError and re-raise
@@ -1756,9 +1764,13 @@ def _generate_range_overflow_safe(endpoint, periods, stride, side='start'):
     Parameters
     ----------
     endpoint : int
+        nanosecond timestamp of the known endpoint of the desired range
     periods : int
+        number of periods in the desired range
     stride : int
+        nanoseconds between periods in the desired range
     side : {'start', 'end'}
+        which end of the range `endpoint` refers to
 
     Returns
     -------
@@ -1770,19 +1782,85 @@ def _generate_range_overflow_safe(endpoint, periods, stride, side='start'):
     """
     # GH#14187 raise instead of incorrectly wrapping around
     assert side in ['start', 'end']
+
+    i64max = np.uint64(np.iinfo(np.int64).max)
+    msg = ('Cannot generate range with {side}={endpoint} and '
+           'periods={periods}'
+           .format(side=side, endpoint=endpoint, periods=periods))
+
+    with np.errstate(over="raise"):
+        # if periods * strides cannot be multiplied within the *uint64* bounds,
+        #  we cannot salvage the operation by recursing, so raise
+        try:
+            addend = np.uint64(periods) * np.uint64(np.abs(stride))
+        except FloatingPointError:
+            raise tslib.OutOfBoundsDatetime(msg)
+
+    if np.abs(addend) <= i64max:
+        # relatively easy case without casting concerns
+        return _generate_range_overflow_safe_signed(
+            endpoint, periods, stride, side)
+
+    elif ((endpoint > 0 and side == 'start' and stride > 0) or
+          (endpoint < 0 and side == 'end' and stride > 0)):
+        # no chance of not-overflowing
+        raise tslib.OutOfBoundsDatetime(msg)
+
+    elif (side == 'end' and endpoint > i64max and endpoint - stride <= i64max):
+        # in _generate_regular_range we added `stride` thereby overflowing
+        #  the bounds.  Adjust to fix this.
+        return _generate_range_overflow_safe(endpoint - stride,
+                                             periods - 1, stride, side)
+
+    # split into smaller pieces
+    mid_periods = periods // 2
+    remaining = periods - mid_periods
+    assert 0 < remaining < periods, (remaining, periods, endpoint, stride)
+
+    midpoint = _generate_range_overflow_safe(endpoint, mid_periods,
+                                             stride, side)
+    return _generate_range_overflow_safe(midpoint, remaining, stride, side)
+
+
+def _generate_range_overflow_safe_signed(endpoint, periods, stride, side):
+    """
+    A special case for _generate_range_overflow_safe where `periods * stride`
+    can be calculated without overflowing int64 bounds.
+    """
+    assert side in ['start', 'end']
     if side == 'end':
         stride *= -1
 
-    try:
-        other_end = checked_add_with_arr(np.int64(endpoint),
-                                         np.int64(periods) * stride)
-    except OverflowError:
-        raise tslib.OutOfBoundsDatetime('Cannot generate range with '
-                                        '{side}={endpoint} and '
-                                        'periods={periods}'
-                                        .format(side=side, endpoint=endpoint,
-                                                periods=periods))
-    return other_end
+    with np.errstate(over="raise"):
+        addend = np.int64(periods) * np.int64(stride)
+        try:
+            # easy case with no overflows
+            return np.int64(endpoint) + addend
+        except (FloatingPointError, OverflowError):
+            # with endpoint negative and addend positive we risk
+            #  FloatingPointError; with reversed signed we risk OverflowError
+            pass
+
+        # if stride and endpoint had opposite signs, then endpoint + addend
+        #  should never overflow.  so they must have the same signs
+        assert (stride > 0 and endpoint >= 0) or (stride < 0 and endpoint <= 0)
+
+        if stride > 0:
+            # watch out for very special case in which we just slightly
+            #  exceed implementation bounds, but when passing the result to
+            #  np.arange will get a result slightly within the bounds
+            assert endpoint >= 0
+            result = np.uint64(endpoint) + np.uint64(addend)
+            i64max = np.uint64(np.iinfo(np.int64).max)
+            assert result > i64max
+            if result <= i64max + np.uint64(stride):
+                return result
+
+    raise tslib.OutOfBoundsDatetime('Cannot generate range with '
+                                    '{side}={endpoint} and '
+                                    'periods={periods}'
+                                    .format(side=side, endpoint=endpoint,
+                                            periods=periods))
 
 
 # -------------------------------------------------------------------
diff --git a/pandas/tests/indexes/datetimes/test_date_range.py b/pandas/tests/indexes/datetimes/test_date_range.py
index a39100b3ec204..918d9c4ed820e 100644
--- a/pandas/tests/indexes/datetimes/test_date_range.py
+++ b/pandas/tests/indexes/datetimes/test_date_range.py
@@ -88,6 +88,67 @@ def test_date_range_nat(self):
         with pytest.raises(ValueError, match=msg):
             date_range(start=pd.NaT, end='2016-01-01', freq='D')
 
+    def test_date_range_multiplication_overflow(self):
+        # GH#24255
+        # check that overflows in calculating `addend = periods * stride`
+        #  are caught
+        with tm.assert_produces_warning(None):
+            # we should _not_ be seeing a overflow RuntimeWarning
+            dti = date_range(start='1677-09-22', periods=213503, freq='D')
+
+        assert dti[0] == Timestamp('1677-09-22')
+        assert len(dti) == 213503
+
+        msg = "Cannot generate range with"
+        with pytest.raises(OutOfBoundsDatetime, match=msg):
+            date_range('1969-05-04', periods=200000000, freq='30000D')
+
+    def test_date_range_unsigned_overflow_handling(self):
+        # GH#24255
+        # case where `addend = periods * stride` overflows int64 bounds
+        #  but not uint64 bounds
+        dti = date_range(start='1677-09-22', end='2262-04-11', freq='D')
+
+        dti2 = date_range(start=dti[0], periods=len(dti), freq='D')
+        assert dti2.equals(dti)
+
+        dti3 = date_range(end=dti[-1], periods=len(dti), freq='D')
+        assert dti3.equals(dti)
+
+    def test_date_range_int64_overflow_non_recoverable(self):
+        # GH#24255
+        # case with start later than 1970-01-01, overflow int64 but not uint64
+        msg = "Cannot generate range with"
+        with pytest.raises(OutOfBoundsDatetime, match=msg):
+            date_range(start='1970-02-01', periods=106752 * 24, freq='H')
+
+        # case with end before 1970-01-01, overflow int64 but not uint64
+        with pytest.raises(OutOfBoundsDatetime, match=msg):
+            date_range(end='1969-11-14', periods=106752 * 24, freq='H')
+
+    def test_date_range_int64_overflow_stride_endpoint_different_signs(self):
+        # cases where stride * periods overflow int64 and stride/endpoint
+        #  have different signs
+        start = Timestamp('2262-02-23')
+        end = Timestamp('1969-11-14')
+
+        expected = date_range(start=start, end=end, freq='-1H')
+        assert expected[0] == start
+        assert expected[-1] == end
+
+        dti = date_range(end=end, periods=len(expected), freq='-1H')
+        tm.assert_index_equal(dti, expected)
+
+        start2 = Timestamp('1970-02-01')
+        end2 = Timestamp('1677-10-22')
+
+        expected2 = date_range(start=start2, end=end2, freq='-1H')
+        assert expected2[0] == start2
+        assert expected2[-1] == end2
+
+        dti2 = date_range(start=start2, periods=len(expected2), freq='-1H')
+        tm.assert_index_equal(dti2, expected2)
+
     def test_date_range_out_of_bounds(self):
         # GH#14187
         with pytest.raises(OutOfBoundsDatetime):


Code review comments:
diff_hunk: @@ -1728,7 +1728,14 @@ def _generate_regular_range(cls, start, end, periods, freq):
             raise ValueError("at least 'start' or 'end' should be specified "
                              "if a 'period' is given.")
 
-        values = np.arange(b, e, stride, dtype=np.int64)
+        with np.errstate(over="raise"):
+            try:
path: pandas/core/arrays/datetimes.py
text: @user1:
also need to be moved out to another module, this is adding way to much reader complexity here (reader means future contributor to pandas)

@author:
OK.  I think this can also be cleaned up by making a decorator to set np.errstate once instead of repeatedly.

@author:
any thoughts on moving offsets.generate_range to this new module?  that is the only place where it is used; thematically a much better fit here than in offsets (much of which should go up to tslibs anyways)

diff_hunk: @@ -1756,9 +1764,13 @@ def _generate_range_overflow_safe(endpoint, periods, stride, side='start'):
     Parameters
     ----------
     endpoint : int
path: pandas/core/arrays/datetimes.py
text: @user1:
I would like you to move this out of this file; you can make a subdirectory ``pandas/core/arrays/datetimes`` if you want or make this a private module

@author:
OK.  Maybe `arrays._ranges`?  Also opens a natural place if we ever want to have a RangeArray.

could also move timedeltas._generate_regular_range there (and looking at it, it seems plausible it would have the same bug as the datetime version.