ENH: add fold support to Timestamp constructor
**PERF Note:** Current implementation slows down the `Timestamp` constructor. I've tested this thoroughly and tracked it down to ba7fcd5 where I changed the function signatures at the very beginning of working on the PR. The performance overhead appeared before any of the logic was implemented.

- [X] closes #25057, closes #31338 
- [X] tests added 32 / passed 32
- [X] passes `black pandas`
- [X] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [X] whatsnew entry

### Reasoning for changes
We currently don't support fold from [PEP 495](https://www.python.org/dev/peps/pep-0495/#the-fold-attribute), and this causes us a lot of grief, including, but not limited to, broken Timestamp representations at the edge of DST shift (see #31338). The values can also break.

Support of the fold attribute helps us deal with that. Now, if the wall clock time occurs twice due to a DST shift, we will know exactly at which point in time we are.

This also removes inconsistencies between using `pytz` and `dateutil`: now both the values and representations match for both timezone packages near DST summer/winter shifts.

### Scope of PR
Implementing fold into Timestamp can easily get out of hand. Parent `pydatetime` has it easy, as the object doesn't need to sync its underlying epoch time, fold, and the representation, like we do.

This PR is already large, so I propose we limit its scope to minimal consistent fold support:
- when fold is explicitly supplied, attempt to shift value across the DST boundary according to the value supplied
- infer fold from value during tz-aware Timestamp construction. For example, if Timestamp is built from epoch time, then we can infer fold.
- pass the resulting fold to the underlying `datetime` constructor in `create_timestamp_from_ts` so that it gets stored in the object (can't assign it directly as it's read-only).
- implement local timezone support for fold. Don't have any idea how to do this though.

Things I suggest we leave to discussion and other PRs:
- conflicts resolution. A user can supply `fold=1` for a datetime that is nowhere near a DST shift. We can raise and Error or a Warning in the future. For now, we check whether `fold` can be 1, and if not, we leave it as default `fold=0`.
- consider reintroducing ambiguous time errors. Currently, the implementation assumes `fold == 0` for ambiguous time like Timestamp("2019-10-27 01:30:00", tz='Europe/London'). The error was dropped to mirror the `fold=0` default in pydatetime and to allow the fold attribute to be `bint` in Cython functions.

**Note:** `pydatetime` doesn't infer fold from value and doesn't raise errors when you assign `fold=1` nowhere near a fold. Example:

```python
from datetime import datetime
from dateutil.tz import gettz

dt = datetime.datetime(2015, 10, 27, 5, 30, 0, 0, gettz("Europe/London"), fold=1)
dt.fold
OUT:
1
```

### Performance problems
This implementation behaves as I expect it to, but it slows down scalar constructor benchmarks by 30-70%, even for tz-naive benchmarks.

Update: since the benchmark slowdown appeared before any of the functionality, this has nothing to do with the logic introduced and all to do with adding `bint fold` to function signatures, apparently. I'm afraid I don't know Cython well enough to research further.
Current output of benchmarks:
```
       before           after         ratio
     [ba083903]       [104c97d4]
     <master>         <add-fold-to-timestamp>
+     1.33±0.03μs       2.65±0.3μs     1.99  tslibs.timestamp.TimestampConstruction.time_from_npdatetime64
+     1.33±0.04μs       2.26±0.2μs     1.69  tslibs.timestamp.TimestampConstruction.time_from_datetime_aware
+     1.74±0.04μs       2.84±0.1μs     1.63  tslibs.timestamp.TimestampConstruction.time_parse_iso8601_no_tz
+     1.41±0.07μs       2.21±0.2μs     1.57  tslibs.timestamp.TimestampConstruction.time_from_datetime_unaware
+     1.84±0.05μs       2.54±0.1μs     1.38  tslibs.timestamp.TimestampConstruction.time_fromordinal
+      4.08±0.1μs      4.95±0.09μs     1.21  tslibs.timestamp.TimestampConstruction.time_parse_now
+      4.06±0.1μs       4.90±0.2μs     1.21  tslibs.timestamp.TimestampConstruction.time_parse_today
+     2.44±0.07μs       2.92±0.1μs     1.20  tslibs.timestamp.TimestampConstruction.time_fromtimestamp
+      18.5±0.7μs       21.2±0.5μs     1.14  tslibs.timestamp.TimestampConstruction.time_parse_iso8601_tz
``` A few overall thoughts:

1) Can we dispatch to `tz_localize` to handle the timezone localization with fold? `fold=0` is equivalent to `ambiguous=False` and  `fold=1` is equivalent to `ambiguous=True` (IIRC). Might help reducing adding new code.
2) I don't think always inferring `fold` is super important IMO. Users should be utilizing the options in `tz_localize`/`tz_convert`. We should support `fold` enough to satisfy dateutil's usage of it. Hello @AlexKirko! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:





There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2020-02-26 06:23:02 UTC @mroeschke
Thanks, I'll see what I can do.

We have to infer to get a correct `dateutil` utcoffset if we construct from epoch time or string with offset. Not inferring fold for `pytz` doesn't sit well with me, because we'll end up with different fold values for essentially the same time. And if we laster change the timezone for that object, we'll probably end up with bugs.

When I coded this and tried to put all the value adustment in one place, I disovered that the assumptions in `convert_datetime_to_tsobject`, in `localize_tso`, and in `create_tsobject_tz_using_offset` are different. Moreover, `get_dst_info` has some nice caching built in, which should kick in whenever we need to construct en-masse, which is where performance matters most, so it seemed like a good option to adjust and infer on-site.
From what I can see, `tz_localize` could work, but I think it's intended to localize naive Timestamps, and it does so through calling the Timestamp constructor, which isn't what we want.
But maybe I can find another way to generalize.

P.S. The amount of new code that implements the logic is about 60 lines (which is still a lot, and I'll try to trim it). Most of the PR is comments and tests. As far as performance in naive cases goes, today I'll throw out all the logic, leaving only the function headers and `obj.fold=0`, and see how it performs in benchmarks. Should be able to proceed from that point. Looks like performance breaks because of the changes to function definitions. This is with all the fold-processing logic gutted out (f9c69566):

```
+      2.26±0.1μs       4.15±0.2μs     1.84  tslibs.timestamp.TimestampConstruction.time_from_datetime_unaware
+     2.31±0.04μs      4.18±0.09μs     1.81  tslibs.timestamp.TimestampConstruction.time_from_datetime_aware
+     2.77±0.07μs       4.97±0.1μs     1.80  tslibs.timestamp.TimestampConstruction.time_from_npdatetime64
+      3.52±0.1μs      5.87±0.08μs     1.67  tslibs.timestamp.TimestampConstruction.time_parse_iso8601_no_tz
+     3.24±0.07μs       5.15±0.2μs     1.59  tslibs.timestamp.TimestampConstruction.time_fromordinal
+      3.86±0.1μs       5.81±0.2μs     1.51  tslibs.timestamp.TimestampConstruction.time_fromtimestamp
+      8.41±0.3μs       10.4±0.2μs     1.24  tslibs.timestamp.TimestampConstruction.time_parse_now
```

I'll keep looking.

**Update:** confirmed this to be happening ever since I changed the function signatures in ba7fcd53. It's unlikely I'll be able to do anything about it, so I'll move forward and look for ways to reuse more of the code. FYI I am planning on taking a look at this early this week. Please ping me if I haven't reviewed and the PR is otherwise ready for merge. Apologies, missed your comment on the overriding behavior being okay as is. Found it now. @mroeschke 
Unless I missed something, this should be everything? Shall we ping **pganssle** then to take a look? Yup. @pganssle if you want to take a look. Hmm. **continuous-integration/travis-ci/pr** seems to be failing for everyone.
Submitted an issue in #31739 

<s>Please ignore that failure here - doesn't have to do anything with this PR.</s> Issue closed, merged in master.

 @mroeschke 
I think I've addressed everything. Should be ready for another review. Some minor comments otherwise LGTM. Any comments @pganssle?  > Some minor comments otherwise LGTM. Any comments @pganssle?

Yes, sorry, still working through this to understand what's going on. I think some of the pytz stuff might not be quite right because pytz does not support fold, but I'm not sure I've quite understood everything yet. @pganssle 
Please ask if it's something I can answer or if you need me to run test cases.
### General notes on the method used
The PR focuses on inferring fold from `Timestamp.value` and adjusting `Timestamp.value` for the fold constructor argument, and this can be done if we have DST transition times and offsets, which we get out of both pytz and dateutil with `get_dst_info`. Then we take the nearest transition point, the DST delta, and the `Timestamp.value`, and this is enough to either infer `Timestamp.fold` or adjust `Timestamp.value` for fold supplied during construction. also may want to add an example in the doc-string of Timestamp and in timeseries.rst (timezone section) > also may want to add an example in the doc-string of Timestamp and in timeseries.rst (timezone section)

Added examples both to the Timestamp docstring and to timeseries.rst. @jreback 
Think I've covered all the comments, please take another look. @pganssle (and @jreback and @mroeschke to join the discussion)

Thank you for the detailed comments. I know how much time it takes to dig through the Timestamp constructor implementation, and I sympathize.
I will try to set aside the resources I've already invested in this PR. Let's discuss our options.

If I understand your comments correctly, your primary gripe is not so much with this PR as it is with the way Timestamp tz-aware construction is handled in general. I think so, because we don't handle it the way you suggest in your first comment. I don't like the general tz-aware construction approach either and would have preferred to implement fold support into something more transparent.

My approach was to limit the scope of this PR to implementing fold into the current structure while changing as little code as possible and getting desired behavior. To this end, I added the value-fold syncing code near to where we were already converting `dts` to `value` and back. I think the only place I relied on the implementation of pytz and dateutil was using `get_dst_info` which builds dst transition points and deltas out of library-specific information. There is no code written specifically for one of the libraries.

While we do have some disagreements on what desired fold behavior is and in which cases we should raise, this is secondary and should be dealt with later.

What we should **all** decide upon first is the general approach. From what I see, we have three options here, but I'd be happy to have missed something:

1. Accept the approach currently taken in this PR, tweak the desired behavior to something we can all accept, and move on. This will reduce the transparency of the code a bit, and we'll be compounding our existing reliance on `get_dst_info`.
2. First refactor the way tz-aware Timestamps are built, according to the logic suggested by @pganssle, and only then implement fold. This way we'll end up with the cleanest code, but it will take the most effort. The probability of introducing bugs is difficult to predict.
3. Build Timestamp like we used to, and then try to sync up `Timestamp.value` and `Timestamp.fold`. This option is crutchy, and I don't like it, but it's available.

@pganssle, sorry for not addressing all your comments, but I believe that would be wasting everyone's time until we decide if the current implementation should be thrown out.

P.S. To be transparent: I'm not volunteering to make another implementation if we discard this one. 2) is a non-starter; we have had this construction and conversion method since the very beginning. changing would be an enormous effort with little gain and a non trivial chance of adding bugs (even though we have a large test suite). @pganssle thr approach is what it is; you may not like it or even fully understand it but we are not going to radically change it @pganssle 
I have to admit I'm a bit puzzled about your comment on pytz not supporting fold. There is currently no pytz-specific code in the fold implementation in this PR, and everything works the same for pytz and dateutil: value, fold, and offset all match.
Am I missing a test case? I do think a radical restructuring is a good idea, because *way* more effort is spent maintaining relatively slow and creaky timezone code than would be required to maintain a separate time zone implementation, but that's not really what I've suggested here.

I actually don't really understand what options 1, 2 and 3 would look like in your conception, because I haven't really proposed any fundamental changes to how timestamps are created here, I've just pointed out multiple places where you've introduced redundant degrees of freedom / unnecessary arguments, and where you've apparently unnecessarily introduced fold-handling logic. I think it would be better to just respond to my individual suggestions so we can get on the same page as to what the radical restructuring you're talking about is.

> I have to admit I'm a bit puzzled about your comment on pytz not supporting fold. There is currently no pytz-specific code in the fold implementation in this PR, and everything works the same for pytz and dateutil: value, fold, and offset all match.
> Am I missing a test case?

You've actually *removed* a test case where `pytz` behaves differently from `dateutil`, [this one](https://github.com/pandas-dev/pandas/pull/31563#discussion_r377180214). `pytz` defines its own non-standard semantics and doesn't use `fold`. That makes this a breaking change for anyone who relies on `pytz`'s existing semantics. You must have backported the logic unintentionally, because `pytz` simply ignores `fold`. > You've actually _removed_ a test case where `pytz` behaves differently from `dateutil`, [this one](https://github.com/pandas-dev/pandas/pull/31563#discussion_r377180214). `pytz` defines its own non-standard semantics and doesn't use `fold`. That makes this a breaking change for anyone who relies on `pytz`'s existing semantics. You must have backported the logic unintentionally, because `pytz` simply ignores `fold`.

Copying my comment in reply to the test removal.
_____
Not really. What I'm doing is setting fold to 0 by default for Timestamp construction from ambiguous times. I based this decision on the behavior of pydatetime, which doesn't raise an error and just sets fold to 0.
```python
from datetime import datetime
from pytz import timezone

tz = timezone('Europe/London')
dt = datetime(2019, 10, 27, 1, 30, 0, 0, tzinfo=tz)
dt.fold
OUT:
0
```
I also propose we consider reintroducing the error on ambiguous time construction later.
_____
Adding to the former comment: the reason this removes the pytz error is that `fold=0` propagates all the way to `tz_localize_to_utc`, where it sets the `ambiguous` argument. This lets `tz_localize_to_utc` resolve the ambiguity according to the default.

I would appreciate any other cases, since this is behaving in accordance with the proposed default. The reason why I think what you propose is quite different from the current algorithm is this bit:

> * Convert `ts` to whatever time zone you need it to be in so that the civil time is correct.
> * Convert `ts` to `numpy.datetime64`, ignoring `fold` and `tzinfo`
> * Set `obj.fold` and `obj.tzinfo` to their respective values on `ts`
> * Call `ts.timestamp()` or convert to UTC then subtract off the epoch time, then adjust with any smaller components you need like nanoseconds, set that to `value`.

To me, this looks quite different from the current implementation. For example, this is what we do when building from datetime right now, as far as I understand.

* Convert `ts` to the new timezone
* Convert `ts` to `numpy.datetime64`, ignoring `fold` and `tzinfo` (so far so good)
* Set obj.value to `ts` scaled to nanoseconds, build obj.dts from ts.
* Set obj.tzinfo to `tz`
* Adjust obj.value for utc_offset to make sure that at one moment in time different timezones share obj.value across the globe.
* Add nanoseconds

After this is where we end up with the bugs this PR is attempting to solve, so I propose introducing two extra steps:

* Adjust obj.value for fold if possible
* Infer fold from the object to make sure that we don't end up with `fold==1` nowhere near a DST shift.

The reason why I think the alternative approach would require some major refactoring is because we don't always have something to call `timestamp()` on. For example when we build from `int` and use `localize_tso`. I believe this is the reason for the approach taken: it lets us process different types of inputs to the constructor similarly instead of relying on `pydatetime` functionality only where its available.

And our own `timestamp` method relies on `obj.value`, so we can't use it to set obj.value:
```python
    def timestamp(self):
        """Return POSIX timestamp as float."""
        # GH 17329
        # Note: Naive timestamps will not match datetime.stdlib
        return round(self.value / 1e9, 6)
``` > To me, this looks quite different from the current implementation. For example, this is what we do when building from datetime right now, as far as I understand.

Yes, it is a simpler implementation that allows you to abstract away many unnecessary details, but it's not fundamentally different in what it *does*, because AFAICT it maintains all guaranteed properties of the existing function. The "call `.timestamp()` on `ts` to get `value`" part of my proposed implementation is actually does all the remaining steps *for you*.

It's possible that this logic was moved into `pandas` deliberately for some reason like speed, but I'd like to see a benchmark or something before rejecting what is essentially a beneficial refactoring of the code on the grounds that it is different than the code that hopefully does exactly the same thing.

> And our own `timestamp` method relies on `obj.value`, so we can't use it to set obj.value:

I don't think that this is a major problem, because the function we're talking about takes what I have to assume is a *valid* `timestamp` (which may be a `datetime`), and converts it to a new `timestamp`, so `ts.timestamp()` should always give the right answer, even when `obj.timestamp()` wouldn't, because `obj.timestamp()` is in an invalid state.

Even if you did have a partially-initialized `obj` and you wanted to convert it to a timestamp, that's not insurmountable by any means. It's basically what `super()` is for, and you can re-create that with `obj.value = datetime.timestamp(obj)`.

--

One last thing to note about this: regardless of whether my proposed simplification of the logic in that one function is desirable, taking `fold` in that function still makes it over-specified. Since `fold` is already an attribute of `ts`, you are effectively taking the `fold` argument twice, which is unnecessary. Thanks for noticing the unexpected raise for a naive datetime. Changed the raise behavior to accomodate such cases.

`obj` is of type `_TSObject` which is a barebones Cython extension type and doesn't inherit from anything, so it's not possible to call `timestamp` at that point. This means that if we want to rely on `timestamp()` we have to either build a datetime object or have one supplied as an argument.

The reason why `fold` is passed explicitly around instead of being stored in obj.fold from the start is that this allows us to set obj.fold to 0 and then infer the correct value when we are done. In my opinion, it makes code more transparent, but it's a matter of opinion.

We could write fold to `obj.fold` at the beginning of `convert_to_tsobject` and then rely on that. I just like it more to set it to 0 and changing it to 1 only when we are confident. > `obj` is of type `_TSObject` which is a barebones Cython extension type and doesn't inherit from anything, so it's not possible to call `timestamp` at that point. This means that if we want to rely on `timestamp()` we have to either build a datetime object or have one supplied as an argument.

I think you are misunderstanding what I am suggesting here. There are two major places where I remember that this is an issue:

1. In [`convert_datetime_to_tso`](https://github.com/pandas-dev/pandas/pull/31563/files#r377163395), you already have an existing object that includes fold information. It's either a `datetime` (or `datetime` subclass), or it's a `Timestamp` object. You don't need to pass in a `fold` attribute because you can pull it from the `ts` argument. I *also* believe that you don't need that information *anyway*, but if you decide to otherwise leave this function alone completely, you should drop the `fold` argument entirely and in the first line set `fold = ts.fold` or `fold = getattr(ts, "fold", 0)`.

2. In [`localize_tso`](https://github.com/pandas-dev/pandas/pull/31563/files#r377170627), the docstring says "Given the UTC nanosecond timestamp in obj.value, find the wall-clock representation of that timestamp in the given timezone.". The contract of the function explicitly states that `obj.value` must be valid, and `obj.value` is *always unambiguous*. The job of `localize_tso` is to find all the components of the local datetime that correspond to `value`. One of those components is `fold`.

  Taking `fold` as an argument to `localize_tso` makes no more sense than taking `year` or `day`: that information all needs to be calculated from `obj.value`.

As for the question of when you can rely on `.timestamp()`, in `convert_datetime_to_tso`, you *explicitly take a `datetime` or `Timestamp` object*, so you can rely on its contents and methods to populate your new `Timestamp` object. You can calculate `value()` from `ts.timestamp()` not `obj.timestamp()`.

In `localize_tso` I am not suggesting using `timestamp()`, though there are other options like `.fromtimestamp()`. Either way, by default you should rely on the time zone providers to use and set fold, and not attempt to do it yourself. **updated localize_tso docstring to reflect fold treatment behavior**

@pganssle
Fold is a pretty obscure parameter, so my approach is to override instead of raise if at all possible. I assume that if a user gets to setting fold in the constructor, they know what they are doing, and we should attempt to set fold to what they supplied. For tz-aware datetime, it makes sense to raise to me, because the user can just run `dt.replace(fold=x)` before passing `dt` to our constructor. For other types of unambiguous input, I chose to let the user override if they want to, so they don't have to mess with strings, integers, etc. I think this reasoning and the rarity of the use case justify this behavior.

I agree with you in principle that it would be better if pandas left messing with date and timezone internals, posix timetamps, etc. to specialized packages. But we do mess with them, and I think we've established we won't change that in this PR.

If we accept this assumption, then the fold processing in `localize_tso` makes sense, simply because we don't have the variables necessary to make the adjustments and to infer while in `convert_to_tsobject` where it's called from. Pulling everything we need into that function would be worse. I've updated the `localize_tso` docstring to make things more clear.

In the future, somebody can attempt to refactor the Timestamp constructor for tz-aware cases in another PR, carefully benchmark alternatives, test everything, and try to convince us the risks such refactoring would introduce are as mitigated as possible and worth it. I might even try it myself in a month or too. But I just don't see why we must attempt it now.

I think, at this point, we have both stated our positions and reasoning very clearly, and there are no more misunderstandings. If neither of us can convince the other, let's just wait for other reviewers to weigh in and go from there (@jreback @mroeschke). I don't think that keeping going will accomplish much except increase the discussion word-count. I agree with @pganssle sentiment in general that we should rely on the underlying `datetime.datetime` (or subclass `Timestamp`) + dateutil's handling of `fold` instead of trying to pass it around (I was initially very surprised with the amount of code we needed to add just to incorporate `fold`).

Though I'll admit, I haven't fully studied this PR's change (or the change necessary in general) to adequately support `fold` in the `Timestamp` constructor

 I agree with the general sentiment too--that's not the problem. It's just that implementing fold in accordance with that sentiment, in my opinion, clashes with how we currently do things and must involve refactoring the functions in `conversion.pyx` to implement it right. Otherwise we'll end up with a hybrid that partially outsorces stuff and partially does things itself, and it isn't good.
 
But obviously I'm biased in favor of my current solution and also frustrated with this PR in general, so take my opinion with a grain of salt.