API: generalized check_array_indexer for validating array-like getitem indexers
Closes https://github.com/pandas-dev/pandas/issues/30738. Also fixes the performance issue for other arrays from https://github.com/pandas-dev/pandas/issues/30744, and related to https://github.com/pandas-dev/pandas/pull/30308#issuecomment-571146305

This generalizes the `check_bool_array_indexer` helper method that we added for 1.0.0 to not be specific to boolean arrays, but any array-like input, and ensures that the output is a proper numpy array that can be used to index into numpy arrays.

I think such a more general "check" is useful, to avoid that all (external+internal) EAs need to do what the test EAs are already doing (checking for integer arrays as well) at https://github.com/pandas-dev/pandas/blob/master/pandas/tests/extension/decimal/array.py#L118-L126, and also to fix the performance issue in a general way (as was now only done for Categorical in https://github.com/pandas-dev/pandas/pull/30747/files)

If we agree on the general idea, I still need to clean up this PR (eg remove the existing `check_bool_array_indexer`, update the extending docs, etc)

cc @TomAugspurger 
In general, the `__getitem__` of an EA now needs to do a

```
    ...
    if is_list_like(key):
        key = check_array_indexer(self, key)
    ...
```

In principle, we could also move the `is_list_like` check into the `check_array_indexer` to make the usage even more simple. That only means that the function then needs to pass-through integers and slices/None/Ellipsis.

 So there are two remaining discussion items I think (also relating to some of the inline comments):

**1) Do we want to allow object dtype masks/indexers?**

Currently, some indexing routines allow object dtyped masks, and some not:

```
In [1]: mask = np.array([True, False, True], dtype=object) 

In [2]: s = pd.Series([1, 2, 3], index=['a', 'b', 'c'])       

In [3]: s[mask]     
Out[3]: 
a    1
c    3
dtype: int64

In [4]: s.index[mask]  
Out[4]: Index(['a', 'c'], dtype='object')

In [5]: pd.Categorical(["a", "b", "c"])[mask]  
...
IndexError: arrays used as indices must be of integer (or boolean) type

In [6]: pd.array([1, 2, 3], dtype="Int64")[mask]       
...
IndexError: arrays used as indices must be of integer (or boolean) type
```

I assume a good reason that we allowed this was because, as Index object, booleans are always object dtype (we don't have a BooleanIndex). 
But in general, I don't really like this support (at least for new functionality like this PR), since I don't see a need to support object dtyped booleans. This support also means that you need to infer for object whether it is boolean or not. 

So the question is here: are we fine with the *new* function being more strict on the dtype? 
I ensured that all cases where it was converted before in pandas 0.25, it is still doing this now (eg in DatetimeArray, there still is a `is_bool_indexer` that does such inference and then ensures the object dtype is converted to a boo dtype at https://github.com/pandas-dev/pandas/pull/31150/files#diff-34bddc5b2c962f58d24f594d80a8b520R523-L521. For categorical, this didn't work in 0.25.0 / before https://github.com/pandas-dev/pandas/pull/30308, so I didn't bother supporting object dtype there).


BTW, also integers as object seems to be somewhat inconsistent (here getitem vs iloc):

```
In [9]: s = pd.Series([1, 2, 3], dtype="Int64", index=['a', 'b', 'c']) 

In [10]: s[np.array([0, 2], dtype=object)]   
...
IndexError: arrays used as indices must be of integer (or boolean) type

In [11]: s.iloc[np.array([0, 2], dtype=object)] 
Out[11]: 
a    1
c    3
dtype: Int64

```

**2) What arguments to accept to `check_array_indexer` (and potentially pass through)?**

Currently, the `check_array_indexer` in this PR accepts a list-like, ensures it is converted to an array-like (ndarray or EA), and then validates integer and boolean arrays. Other array dtypes are passed through, in the idea that numpy will error on other dtypes anyway (but we could also raise the error already in `check_array_indexer` if that is preferred)

This means that, for correct use, you need to do something like (if you have an EA that has a `_data` with a numpy array):

```
    def __getitem__(self, item):
        if is_integer(item):
            return self._data[item]

        elif is_list_like(item) and not isinstance(item, tuple):
            item = check_array_indexer(self, item)

        return type(self)(self._data[item])
```

The `is_list_like(item)` is needed because currently `check_array_indexer` does not handle eg slices, and the `and not isinstance(item, tuple)` is needed because otherwise the current `check_array_indexer` would convert the tuple into an array, which gives a different meaning (a tuple would mean to index multiple dimension, which will typically error for 1D numpy arrays).

So it was already mentioned somewhere above that we could move this `is_list_like(item) and not isinstance(item, tuple):` check into the `check_array_indexer` function. But that also means that  we don't just accept a list-like to the function, but will need to pass through other things through the function untouched (like integer scalars, `None`, slice, ellipsis, which all can be valid indexers).  
Are we OK with that? It makes the typing of function less strict (otherwise we could ensure the output is an ndarray) and thus the code less explicit, but it makes the usage a bit easier (don't need to repeat the list and tuple check everywhere this is used). > So the question is here: are we fine with the new function being more strict on the dtype?

Yes, I'm happy with that. We should at least have some functionality that can completely avoid dtype inference.

> So it was already mentioned somewhere above that we could move this `is_list_like(item) and not isinstance(item, tuple)`: check into the check_array_indexer function.

I think my preference is to not handle that inside `check_array_indexer`. I'd like to keep that focused specifically on arrays (lists too I suppose, though that's debatable I think)

If we want to make this even easier for our own /  3rd party EAs, we can add another helper like

```python
def check_indexer(item):
    """
    Check the kind of indexer provided.

    Returns
    --------
    indexer : Any
        Integers will be passed through as is. list-likes will be converted to arrays
    kind : str
        One of 'integer-scalar', 'integer-array', 'boolean', 'slice'
```

That would collect all the inference and type checking in a single method. But I think that's less important than getting this array version finished up. > If we want to make this even easier for our own / 3rd party EAs, we can add another helper like

But wouldn't such a `check_indexer` helper function basically look like:

```
def check_indexer(array, indexer):
    if is_list_like(indexer) and not isinstance(indexer, tuple):
            indexer = check_array_indexer(array, indexer)
    return indexer
```

We could also decide to replace `check_bool_array_indexer` with such a `check_indexer` instead of the `check_array_indexer` of this PR.

I am also not sure if the "kind" is very important. In practice (when your underlying data are numpy arrays at least), you only care about the distinction between a scalar vs not a scalar (integer/boolean array, slice, ), as for the second group you need to wrap it again in your array class (and for the first case potentially wrap it in a scalar class). > But wouldn't such a check_indexer helper function basically look like:

Mmm, fair point. Happy to defer to your judgement here :) We could also have both `check_indexer` and the more specialized `check_array_indexer` ? > Currently, some indexing routines allow object dtyped masks, and some not:

I'm running into that in `Series.__getitem__` while working on #30349 and I think it is fairly fragile.  If/when we have BoolIndex, I would support deprecating/dropping this support.

> Because here, in DatetimeArray.__getitem__, we have special code to check if a boolean mask can be converted into a slice.

Yah this special casing is weird.  Standardizing that would be nice. We need to take a decision on what to do with non-list likes (tuples, None, integer, ellipsis ..). Handle them inside or outside? 

@TomAugspurger preferred to handle them outside, and indeed, that gives the signature of `check_array_indexer` a tighter typing (list-like -> ndarray, otherwise it is Any->Any) 

On the other hand, that makes that basically in all `__getitem__` we need to add a `is_list_like(item) and not isinstance(item, tuple)` before calling `check_array_indexer`. So it was also suggested to have a `check_indexer` with this more relaxed check. Either is fine by me.

If this is exclusively or primarily used in `__getitem__`, then `check_array_indexer` should handle that for the user, since the type in `__getitem__` is so broad.

If we're using it elsewhere where we know we already have an array, then skipping that check is nice.

In this PR, it looks like `__getitem__` is the primary users, so we can go ahead and include the check I think. OK, added a commit moving the check inside. Now it only validates array-likes (list-likes which are not tuples) and passes through everything else. 

Maybe remaining question is if we want to rename this to `check_indexer` instead of `check_array_indexer`. 
I am fine with keeping the name, to have the "array" point to the fact that it's checking (array) input to index arrays (eg input to index a Series or DataFrame would have other checks) I'm a little late weighing in, but I'd prefer to have the function require as tight an argument type as possible (arraylike maybe?).  In trying to optimize our lookups, avoidable type checks are some of the lowest-hanging fruit It's as simple as undoing the last commit, but you will need to find an agreement with @jreback 

In the end, I think how it is now (the list-like + tuple check inside the function) makes it easier to use this (otherwise you need that check every time the function is called). 
I would also be fine with two functions: `check_array_indexer` (which is strict) and `check_indexer` (which then has the additional type check and otherwise calls `check_array_indexer`), if that keeps things cleaner. See proposal above https://github.com/pandas-dev/pandas/pull/31150#issuecomment-577693477

>  In trying to optimize our lookups, avoidable type checks are some of the lowest-hanging fruit

Not sure I understand this point?

 @jorisvandenbossche 

actually I was ok with the original

> It's as simple as undoing the last commit, but you will need to find an agreement with @jreback

I agree that this should have a tight type check. So it should *require* a array-like (rather than coercing). > actually I was ok with the original

I interpreted "personally I would actually relax this and avoid the need to have is_list_like checks before calling this." differently :) 
Now, if you check the last commit (https://github.com/pandas-dev/pandas/pull/31150/commits/1ca35d15baffa2e8869b238f57f29e2b01c91332), I think it actually made things simpler in the `__getitem__` functions.

> I agree that this should have a tight type check. So it should require a array-like (rather than coercing).

No, that's not possible (and that's not what the last commit did). It needs to accept things like lists, as that is a valid array-like indexer. 
The "tighter typing" that I mentioned above is about having a return value that is always ndarray, the input always has been list-like (and with the latest commit that changed to Any)

 > > actually I was ok with the original
> 
> I interpreted "personally I would actually relax this and avoid the need to have is_list_like checks before calling this." differently :)
> Now, if you check the last commit ([1ca35d1](https://github.com/pandas-dev/pandas/commit/1ca35d15baffa2e8869b238f57f29e2b01c91332)), I think it actually made things simpler in the `__getitem__` functions.
> 
> > I agree that this should have a tight type check. So it should require a array-like (rather than coercing).
> 
> No, that's not possible (and that's not what the last commit did). It needs to accept things like lists, as that is a valid array-like indexer.
> The "tighter typing" that I mentioned above is about having a return value that is always ndarray, the input always has been list-like (and with the latest commit that changed to Any)

ok i see it. ok then. what about the issue of object array? e.g. does this eliminate the need for is_bool_indexer? or deferring that? > what about the issue of object array? e.g. does this eliminate the need for is_bool_indexer? or deferring that?

So the *new* `check_array_indexer` doesn't allow object dtype as boolean indexer. Therefore, everywhere we supported this before, `is/check_bool_indexer` is still being used for backwards compatibility *in addition* to `check_array_indexer`. 
We should deprecate that some day, but right now with boolean index being object this is still too early I think. > > what about the issue of object array? e.g. does this eliminate the need for is_bool_indexer? or deferring that?
> 
> So the _new_ `check_array_indexer` doesn't allow object dtype as boolean indexer. Therefore, everywhere we supported this before, `is/check_bool_indexer` is still being used for backwards compatibility _in addition_ to `check_array_indexer`.
> We should deprecated that some day, but right now with boolean index being object this is still too early I think.

ok fair enough, maybe just rename is_bool_indexer then (doesn't have to be in this PR), to is_bool_indexer_for_object_array (too long, but that's the idea) Fixed the merge conflict. @jbrockmendel I think your comments in https://github.com/pandas-dev/pandas/pull/31150#issuecomment-579359317 can be resolved in some places, but for a general `__getitem__` we have to handle the fact that `key` can have any type / dtype.

Thanks @jorisvandenbossche! @Meeseeksdev backport to 1.0.x Owee, I'm MrMeeseeks, Look at me.

There seem to be a conflict, please backport manually. Here are approximate instructions:

1. Checkout backport branch and update it.

```
$ git checkout 1.0.x
$ git pull
```

2. Cherry pick the first parent branch of the this PR on top of the older branch:
```
$ git cherry-pick -m1 b1214af3528319e31334ff098021c5a1a6d9ffcd
```

3. You will likely have some merge/cherry-pick conflict here, fix them and commit:

```
$ git commit -am 'Backport PR #31150: API: generalized check_array_indexer for validating array-like getitem indexers'
```

4. Push to a named branch :

```
git push YOURFORK 1.0.x:auto-backport-of-pr-31150-on-1.0.x
```

5. Create a PR against branch 1.0.x, I would have named this PR:

> "Backport PR #31150 on branch 1.0.x"

And apply the correct labels and milestones.

Congratulation you did some good work ! Hopefully your backport PR will be tested by the continuous integration and merged soon!

If these instruction are inaccurate, feel free to [suggest an improvement](https://github.com/MeeseeksBox/MeeseeksDev).
                