ENH: Basis for a StringDtype using Arrow
- [x] xref #35169
- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [ ] whatsnew entry

I will focus on using Arrow master as I expected that we will need to add some functionality to Arrow anyways before this in any mergable state. General question from the other thread about mutability. If we can pad each string to the UTF-8 max string length in arrow, can we better support mutability without forcing a complete reallocation of the array? @Josh-Ring-jisc  Please stop posting the same question in multiple places, I'll answer in the first pandas issue. @simonjayhawkins Should we coordinate somewhere? (e.g. here?) I do a bit of work over at https://github.com/xhochy/fletcher that would also be helpful here as well can I probably contribute with pointer to things in Arrow if needed. @xhochy Over the last few days, I've began getting acquainted with fletcher and the string array work in arrow. At this point I'm not sure where the best place to coordinate would be. 

I think it would also be beneficial to contribute to fletcher as part of this exercise. Since the different string methods are separate issues in fletcher, could also coordinate there on specific methods.
 > I will focus on using Arrow master as I expected that we will need to add some functionality to Arrow anyways before this in any mergable state.

There is some discussion in #35169 on fallback options. Should this PR move forward with the current min version of pyarrow that we support? > > I will focus on using Arrow master as I expected that we will need to add some functionality to Arrow anyways before this in any mergable state.
> 
> There is some discussion in #35169 on fallback options. Should this PR move forward with the current min version of pyarrow that we support?

The performance improvements of this new dtype will only come when we use the new string functions in Arrow. I now from some colleagues that there are already slight benefits with `pyarrow>=0.17` as the storage is more efficient and simple things like `groupby` are sometimes a bit faster or use the GIL slightly less but the fallback of going Arrow-to-object-to-Arrow for the algorithms makes it worse than using the object dtype directly.

If we want to get this into `pandas` as soon as possible, I would recommend to either use `pyarrow` 1.0 or 2.0 (will be released now/tomorrow) as the minimal version for the string dtype and keep the minimal supported `pyarrow` version stable for other features like Parquet reading. One benefit of the 1.0 release is that it brings better take support (and the new `pyarrow.compute` API in general) with it, in 2.0 we get more string algorithms that would just improve performance but don't have a big implication on the implementation thanks to @TomAugspurger's PR that enables bit-by-bit overloading of the string functions. > @xhochy Over the last few days, I've began getting acquainted with fletcher and the string array work in arrow. At this point I'm not sure where the best place to coordinate would be.
> 
> I think it would also be beneficial to contribute to fletcher as part of this exercise. Since the different string methods are separate issues in fletcher, could also coordinate there on specific methods.

I would like to keep `fletcher` separate but try to minimise its codebase over time. Its main reason of development initially was to give input into Arrow development. For example all the numba-based algorithms should vanish over time and be replaced by their C++ counterparts in Arrow, `pandas` should only use the Arrow ones. 

The string-related and general purpose things from https://github.com/xhochy/fletcher/blob/master/fletcher/base.py are probably the bits that we need to copy&paste&polish in this PR here. That should already bring us to a working but not ultra-fast dtype. I hope that we need nothing from the `algorithms/` folder anymore.

Otherwise, once everything here is implemented, there is still a place for `fletcher`. It will behave slightly different than the `pandas.ArrowStringDtype` in that it will return for all its results an Arrow-backed `Series`. I think the dtype here should return the standard `pandas`-nullable dtypes. Agreed wih @xhochy's points. We can require pyarrow 1.0 as a minimum version for the string dtype (and keep supporting older versions for other parts, like parquet reading). More string algorithms will only be added step by step to pyarrow in the next releases, so we will need to deal with this incomplete and varying coverage of string algorithms in pyarrow anyway, I think. 

> I think the dtype here should return the standard pandas-nullable dtypes.

Indeed. So we raise user-friendly message if pyarrow < 1.0 an if pyarrow version installed includes string kernel, we dispatch otherwise use a fallback so that we can support 1.0 and 2.0? Yes, that sounds correct! One important caveat with the `fletcher` implementation is that I skipped over the views-vs-copy implementation and also skipped the tests: https://github.com/xhochy/fletcher/blob/467054f0954c5c5796c6a5ced10891ce0e02e064/tests/test_pandas_extension.py#L387

This could be tricky to resolve but hopefully with some pandas insight knowledge not that hard. Though in `rle-array` they did spent quite some lines of code on slices, views and copies: https://github.com/JDASoftwareGroup/rle-array/blob/master/rle_array/_slicing.py +1 on the pyarrow min here (and clearly labeling this experimental) @TomAugspurger should https://github.com/pandas-dev/pandas/issues/35169#issuecomment-712372349 be within the scope of this PR to avoid duplication and better static type checking? Any maybe also for the tests, single test file with fixtures parametrized to avoid duplication/different return types? 

am I correct in assuming that ArrowStringArray and PythonStringArray should behave identically? > should #35169 (comment) be within the scope of this PR to avoid duplication and better static type checking?

I'm not sure what will be best here. Doing all of it in one shot will make for a larger diff / harder to review PR.

> ArrowStringArray and PythonStringArray

I think so (there may be differences in the `.str` accessor, but in general `Series[StringArray[T]]` will return a `Series[StringArray[T]]` for functions that go `str -> str`. Both return BooleanArray for functions returning bools.) > > should #35169 (comment) be within the scope of this PR to avoid duplication and better static type checking?
> 
> I'm not sure what will be best here. Doing all of it in one shot will make for a larger diff / harder to review PR.

From our discussion today (xref https://github.com/pandas-dev/pandas/issues/35169#issuecomment-712883859), I await the review from @jorisvandenbossche before making any significant changes here. This is the versions of pyarrow used on the last CI run (pyarrow 2.0 has now been released some will probably change on the next commit

env | name | pyarrow version | pin 
--- | --- | --- | ---
Azure pipelines | macOS py37_macos | 0.15.1 | >=0.15.0
Azure pipelines | Linux py37_minimum_versions | 0.15.1 | =0.15
Azure pipelines | Linux py37 | 0.15.1 | None
Azure pipelines | Linux py37_locale_slow | Not Installed
Azure pipelines | Linux py37_slow | Not Installed
Azure pipelines | Linux py38 | Not Installed
Azure pipelines | Linux py38_locale | 1.0.1 | >=0.15
Azure pipelines | Linux py38_np_dev | Not Installed
Azure pipelines | Windows py37_np16 | 0.15.1 | =0.15
Azure pipelines | Windows py38_np18 |1.0.1 | >=0.15.0
Travis CI | 3.9-dev | Not Installed
Travis CI | 3.8, slow | Not Installed
Travis CI | 3.7, locale | 1.0.1 | >=0.17
Travis CI | 3.7, coverage | 1.0.1 | >=0.15.0


> We can require pyarrow 1.0 as a minimum version for the string dtype

we will probably want to pin at least one of the environments to 1.0

 > we will probably want to pin at least one of the environments to 1.0

Yes, that's a good idea. Now 2.0.0 is released, that can already be done in a separate PR. we currently have astype failures since we can't import ArrowStringDtype if PyArrow not installed.

in the three step process in https://github.com/pandas-dev/pandas/issues/35169#issuecomment-712883859, the API is out of scope for this PR.

so it may be that eventually ArrowStringDtype is behind a pd.StringDtype(storage="pyarrow")

In order to get ci green here there are many options of which the best is not apparent until the API is decided.

I've opened #35259 and #37337 to ci test a couple of options, split the array and dtype and also common base class for StringDtype and ArrowStringDtype

another option could be an `is_extension_string_dtype` function.

The advantage of #35259 is that ArrowStringDtype can be imported (and instantiated) without PyArrow installed. It is a similar setup to how we currently do SparseArray. However, this may not be necessary once the API is confirmed.

#37337 is simpler once https://github.com/pandas-dev/pandas/pull/35259#issuecomment-714399662 is resolved, we'll be left with 4 test failures on the 4 environments with pyarrow 1.0+

```
=========================== short test summary info ============================
FAILED pandas/tests/extension/test_string_arrow.py::TestGetitem::test_take_non_na_fill_value
FAILED pandas/tests/extension/test_string_arrow.py::TestGetitem::test_take_pandas_style_negative_raises
FAILED pandas/tests/extension/test_string_arrow.py::TestGetitem::test_reindex_non_na_fill_value
FAILED pandas/tests/extension/test_string_arrow.py::TestSetitem::test_setitem_preserves_views
= 4 failed, 88440 passed, 1514 skipped, 1408 xfailed, 71 warnings in 1111.71s (0:18:31) =
``` > In order to get ci green here there are many options of which the best is not apparent until the API is decided.

As a very minimal option on the short term, would it be possible to try the import:

```
try:
    import pyarrow as pa
    ...
except ImportError:
    pa = None
```

and then have a function that checks if `pa` is not None and otherwises raises an error, which can be put in the dtype and array constructors. 

That could leave the questions about class inheritance etc for later. And it also allows those classes to exist even when pyarrow is not available, but only raise an error when actually instanced are created.
 > As a very minimal option on the short term, would it be possible to try the import:

no problem. will close the others. Thanks @jorisvandenbossche for the review.

The ci builds for the last run are no longer available. merged master to get the baseline for failing tests before enabling all base extension tests. What's the latest on adding a new `ArrowStringDtype()` vs. a parametrized `StringDtype(storage=...)`? > What's the latest on adding a new ArrowStringDtype() vs. a parametrized StringDtype(storage=...)?

Let's keep that discussion in https://github.com/pandas-dev/pandas/issues/35169 (there is enough comment in this PR ;)), the idea is to keep it as is in this PR (nothing is already exposed publicly in this PR), and then do a follow-up with the user facing interface. > What's the latest on adding a new `ArrowStringDtype()` vs. a parametrized `StringDtype(storage=...)`?

I think we were going to keep that discussion separate to this PR 

see also https://github.com/pandas-dev/pandas/pull/35259#discussion_r522949042  did start down this path in #37337

see https://github.com/pandas-dev/pandas/pull/35259#issuecomment-714702610 why that PR was closed for now.

> That could leave the questions about class inheritance etc for later. And it also allows those classes to exist even when pyarrow is not available, but only raise an error when actually instanced are created. @jorisvandenbossche Thanks for your reviews. I think i've either actioned or commented on all your comments.

I think ci should be green here now and that we could probably mark as ready for review for other reviewers.

Most of @jreback outstanding comments relate to typing, which I will focus on now, but could be done in parallel if we are happy to merge this so we can get started on the rest of the task. > I think ci should be green here now and that we could probably mark as ready for review for other reviewers.
>
> Most of @jreback outstanding comments relate to typing, which I will focus on now, but could be done in parallel if we are happy to merge this so we can get started on the rest of the task.

Yes, this is indeed ready to go as a first basis. The remaining type-related comments are handled in separate PRs.  Thanks @xhochy for getting this started, and @simonjayhawkins for the follow up work !

There are many follow-up items from the discussion above, which I think should mostly be summarized at https://github.com/pandas-dev/pandas/issues/35169#issuecomment-727217462 (and in addition also the public exposure needs to be worked on)

But excited to see the start of this work merged!  Thanks all!