Remove undefined behavior from npy_datetimestruct_to_datetime
State: closed

This helps the readability of things as is, but also helps us better implement bounds checking in a later PR to avoid overflow

Labels:
name: Refactor
description: Internal refactoring of code
name: Internals
description: Related to non-user accessible pandas implementation

Comments:
The current implementation is vendored from numpy, which recently expose this for us in their C API so we can de-duplicate it once our minimum version catches up.
I think we can upstream this again once we have the UB cleaned up. It's a few years out and numpy doesn't have the amount of tests hitting this as we do right?
@jbrockmendel I took this a bit further so you can see where this would head. gcc/clang/msvc all provide builtin functions to check for overflow, which can even be dispatched down at the hardware level. By leveraging those functions, we can avoid introducing any undefined behavior.

The next evolution of this could get rid of the `check_dts_bounds` function and just rely on the libraries / standard Python error handling, which should help rip out a lot of code and potentially avoid some errors in the checks
Hmm so going through this it turns out that our current bounds checking isn't quite correct. 

```python
>>> pd.Timestamp.min
Timestamp('1677-09-21 00:12:43.145224193')
```

This gets stored as a struct with the following members / values:

```c
{year = 1677, month = 9, day = 21, hour = 0, min = 12, sec = 43, us = 145224, ps = 193000, as = 0}
```

On main the switch case to convert this to a nanosecond resolution is:

```c
            case NPY_FR_ps:
                ret = ((((days * 24 + dts->hour) * 60 + dts->min) * 60 +
                        dts->sec) *
                           1000000 +
                       dts->us) *
                          1000000 +
                      dts->ps;
```

Converting this to a Python function with the appropriate values:

```python
>>> days = -106752
>>> hour = 0
>>> min = 12
>>> sec = 43
>>> us = 145224
>>> ((((days * 24 + hour) * 60 + min) * 60 + sec) * 1000000 + us) * 1000
-9223372036854776000
```

Which exceeds the limits of an int64. 

Since the numpy datetimestruct does not store ns but we instead need to multiply us * 1000 to get that value, I think we need to adjust our Timestamp.min / Timestamp.max to be +1000/-1000 ns respectively to avoid overflow
> On main the switch case to convert this to a nanosecond resolution is: [...] case NPY_FR_ps

we dont use FR_ps anywhere.  is this reachable?
big picture im pretty happy to defer to @WillAyd on this, would like someone with stronger c-fu than me to review the c edits.
> we dont use FR_ps anywhere. is this reachable?

Yea sorry typo on my end. But the problem exists in the NPY_FR_ns block as well. Essentially multiplying `us * 1000` when you are within 1 microsecond of the theoretical storage limit will overflow
would there be a perf (nogil maybe?) benefit to having npy_datetimestruct_to_datetime set a flag to indicate an overflow rather than raising?  itd be annoying as the caller would be responsible for checking the flag
if silent overflows are happening, can we construct test cases that currently fail?
> would there be a perf (nogil maybe?) benefit to having npy_datetimestruct_to_datetime set a flag to indicate an overflow rather than raising? itd be annoying as the caller would be responsible for checking the flag

Certainly possible, but would want to leave that to a future enhancement. This function already sets a Python error in the case where the switch falls through. Granted I don't know how someone could get there; a unit of `NPY_FR_GENERIC` would have to make its way down there
> if silent overflows are happening, can we construct test cases that currently fail?

Hmm it would be pretty hard to assert anything, since integer overflow is undefined behavior. Here's a simple reproducer though:

```python
import pandas as pd
from pandas._libs.tslibs.strptime import array_strptime
ser = pd.Series(["1677-09-21 00:12:43.145224193"])
array_strptime(ser.values, "ISO8601")
```

For me if I step into the debugger at np_datetime.c:351 I see these values:

```
(gdb) p days
$12 = -106752
(gdb) p *dts
$13 = {year = 1677, month = 9, day = 21, hour = 0, min = 12, sec = 43, us = 145224, ps = 193000, as = 0}
```

The formula for the case of NPY_FR_ns is:

```c
ret = ((((days * 24 + dts->hour) * 60 + dts->min) * 60 + dts->sec) * 1000000 + dts->us) * 1000 + dts->ps / 1000
```

And if you break this up into intermediate parts you'll see the overflow happening:

```
(gdb) p ((((days * 24 + dts->hour) * 60 + dts->min) * 60 + dts->sec) * 1000000 + dts->us)
$14 = -9223372036854776
(gdb) p ((((days * 24 + dts->hour) * 60 + dts->min) * 60 + dts->sec) * 1000000 + dts->us) * 1000
$15 = 9223372036854775616
(gdb) p ((((days * 24 + dts->hour) * 60 + dts->min) * 60 + dts->sec) * 1000000 + dts->us) * 1000 + dts->ps / 1000
$16 = -9223372036854775807
```

In this particular instance I was able to get back to the value we want after division, but there is no guarantee of that.

In the long run the ASAN/UBSAN integration in CI should help us catch these issues, this PR is just one of a few expected to get us there
Here are current benchmarks. Will update these on different iterations. Regressions need to be addressed but glad to see some improvements as well; these hardware overflow checks are really fast so I would expect them to outperform manual checks like `check_dts_bounds` 

<details>

```
| Change   | Before [f3b9309b] <refactor-np-datetime~1^2>   | After [7ee90dde] <refactor-np-datetime>   |   Ratio | Benchmark (Parameter)                                                           |
|----------|------------------------------------------------|-------------------------------------------|---------|---------------------------------------------------------------------------------|
| -        | 455±2μs                                        | 414±2μs                                   |    0.91 | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(10000, 2000)   |
| -        | 48.8±0.8ms                                     | 44.3±0.08ms                               |    0.91 | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(1000000, 1011) |
| -        | 34.9±0.2ms                                     | 31.6±0.2ms                                |    0.91 | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(1000000, 4000) |
| -        | 4.46±0.03μs                                    | 4.01±0.04μs                               |    0.9  | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(100, 4006)     |
| -        | 4.48±0.04μs                                    | 4.02±0.01μs                               |    0.9  | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(100, 5000)     |
| -        | 472±3μs                                        | 425±2μs                                   |    0.9  | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(10000, 1000)   |
| -        | 46.4±0.3ms                                     | 41.9±0.1ms                                |    0.9  | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(1000000, 1000) |
| -        | 34.2±0.06ms                                    | 30.7±0.2ms                                |    0.9  | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(1000000, 4006) |
| -        | 361±3μs                                        | 320±2μs                                   |    0.89 | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(10000, 5000)   |
| -        | 361±2μs                                        | 316±4μs                                   |    0.88 | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(10000, 4000)   |
| -        | 350±0.9μs                                      | 309±3μs                                   |    0.88 | tslibs.period.TimePeriodArrToDT64Arr.time_periodarray_to_dt64arr(10000, 4006)   |

SOME BENCHMARKS HAVE CHANGED SIGNIFICANTLY.
PERFORMANCE INCREASED.


```

</details>
OK fixed up the performance regressions. This has a slight boost to performance in current state. Think mergable but let me know what you think @jbrockmendel 
Any feedback on this? Would like to get this in to keep chipping away at the ASAN/UBSAN setup. @lithomas1 @jbrockmendel @mroeschke 
I'll prioritize taking another look this afternoon
Any objections on this one @jbrockmendel or good to merge?
taking another look now
One nitpick, no objections.  Haven't looked at the C code that closely
Thanks @WillAyd 
I just started seeing a bunch of 

```
  ../../pandas/_libs/src/vendored/numpy/datetime/np_datetime.c:355:40: warning: incompatible pointer types passing 'int64_t *' (aka 'long long *') to parameter of type 'long *' [-Wincompatible-pointer-types]
    return checked_int64_sub(year, 1970, result);
                                         ^~~~~~
  ../../pandas/_libs/src/vendored/numpy/datetime/np_datetime.c:45:69: note: expanded from macro 'checked_int64_sub'
  #define checked_int64_sub(a, b, res) __builtin_ssubl_overflow(a, b, res)
                                                                      ^~~
  ../../pandas/_libs/src/vendored/numpy/datetime/np_datetime.c:359:39: warning: incompatible pointer types passing 'int64_t *' (aka 'long long *') to parameter of type 'long *' [-Wincompatible-pointer-types]
    return checked_int64_mul(years, 12, result);
                                        ^~~~~~
  ../../pandas/_libs/src/vendored/numpy/datetime/np_datetime.c:46:69: note: expanded from macro 'checked_int64_mul'
  #define checked_int64_mul(a, b, res) __builtin_smull_overflow(a, b, res)

[truncated]
```

can/should we do something about this?
Yea we should. What platform are you on?
Mac (pre-M1)
Ok thanks. The pre-processor condition on line 43 has to be to blame. Will see what I can find for macOS (hoping it's in CI logs too). 

In your case if you deleted that #if directive and kept the true branch I think it would resolve your issues
https://github.com/pandas-dev/pandas/pull/55977 should be a more permanent fix
Two other follow-up requests that are not time-sensitive but i want to make sure don't fall through the cracks: 1) try to upstream this to numpy so our versions dont diverge from theirs, 2) deduplicate the "catch OverflowError and re-raise as OutOfBoundsDatetime"

update: would it be difficult to define OutOfBoundsDatetime in the C code instead of in the cython?
Yea I agree moving that exception down to the extension would be great - just need to spend more time on that