ENH: add BooleanArray extension array
Closes https://github.com/pandas-dev/pandas/issues/21778 
xref closed PRs https://github.com/pandas-dev/pandas/pull/22226 and https://github.com/pandas-dev/pandas/pull/25415, and xref the discussions on missing values in https://github.com/pandas-dev/pandas/issues/28095 and https://github.com/pandas-dev/pandas/issues/28778

This PR adds a BooleanArray extension array ("boolean" dtype):

- It uses the same mask-based approach as the IntegerArray: numpy array for the values + numpy array for the mask
- it does not yet implement any new NA behaviour as being discussed #28778, but for now follows the current NaN behaviour
- It is not yet "produced" from other extension arrays (eg a comparison method on IntegerArray, I would leave that for follow-up PRs)
- There is certainly a lot of code to share between this BooleanArray and IntegerArray (eg in a "BaseMaskedArray" base class), but didn't do that yet here (focusing on the BooleanArray for now)


should this be marked as a WIP? > is there a reason you did not inherit from IntegerArray (and dtype) and just copied
>
> surely these share much more code and could easily share a bae class at the very least

As I said in the top post: yes this needs to share code with IntegerArray through common base class, but initially focussed on a working BooleanArray and deciding on its behaviour. 
I am happy (and planning) to do that, here or in a follow-up.

I don't think it should directly inherit IntegerArray, but personally prefer a common base class. I think that will make it clearer what is actually shared. > > is there a reason you did not inherit from IntegerArray (and dtype) and just copied
> > surely these share much more code and could easily share a bae class at the very least
> 
> As I said in the top post: yes this needs to share code with IntegerArray through common base class, but initially focussed on a working BooleanArray and deciding on its behaviour.
> I am happy (and planning) to do that, here or in a follow-up.
> 
> I don't think it should directly inherit IntegerArray, but personally prefer a common base class. I think that will make it clearer what is actually shared.

i agree a common base class is good and as a follow up is fine > should this be marked as a WIP?

@jbrockmendel not in the sense of "this is ready to be reviewed", and it also passing all extension array tests (except one, see below). 
There are certainly still todo's (eg the arithmetic ops and ufunc machinery), but eg some commented out tests are mainly API questions (what behaviour do we want? for which review is welcome). There are also parts that I am not planning to address in this PR (eg adding a scalar pd.NA) but rather in separate PRs.

---

The one failure in the base extension array tests, is for concatting mixed dtypes (`result = pd.concat([df1, df2])`):

```
(Pdb) df1
       A
0   True
1  False
2   True
(Pdb) df2
   A
0  1
1  2
2  3
(Pdb) result
   A
0  1
1  0
2  1
0  1
1  2
2  3
(Pdb) expected
       A
0   True
1  False
2   True
0      1
1      2
2      3
```

So it is expecting to return object dtype. 
However, on master for numpy dtypes, we also coerce booleans to integer:

```
In [23]: df1 = pd.DataFrame({'A': [True, False]})  

In [24]: df2 = pd.DataFrame({'A': [1, 2]})  

In [25]: pd.concat([df1, df2])    
Out[25]: 
   A
0  1
1  0
0  1
1  2
```

What to follow here? (we should probably have some discussion about clearer rules (and document this) for which dtypes coerce with which others. Or does this exist somewhere?)
 > not in the sense of "this is ready to be reviewed",

I'm confused by a potential double-negative.  If this is not ready to be reviewed, then I suggest it be marked as WIP so that would-be reviewers focus elsewhere for the time being. Let me be clearer then: this is ready to be reviewed Are people OK with first reviewing / getting merged this version of a BooleanArray without using the new NA, and only in a follow-up adapt it to use NA ? 
(I prefer that to be able to work on those things in parallel, many aspects of BooleanArray do not involve NA vs np.nan, and those an already be reviewed here). yes let’s keep BooleanArray independent and merge first > Can you check: does this handle indexing a BooleanArray with another BooleanArray well? Does it have to go through object dtype?

@TomAugspurger boolean indexing does not yet work. Well, it did work when BooleanArray coerced to a bool ndarray, and then it worked automatically (for the case that there are no NAs). 
But now I changed back to always convert to object ndarray, we will need to handle this case specifically. Since that will probably involve adding a check and proper conversion to numpy array in several places in the indexing code, I was planning on doing that later / separate PR. > Since that will probably involve adding a check and proper conversion to numpy array in several places in the indexing code, I was planning on doing that later / separate PR.

SGTM. Have we discussed the API on that anywhere? Do missing values propagate, or are they treated as False? > Have we discussed the API on that anywhere? Do missing values propagate, or are they treated as False?

That's where I want feedback, see the discussion in https://github.com/pandas-dev/pandas/issues/28778 @jreback @jbrockmendel @TomAugspurger thanks all for the feedback. Updated based on that, and also fixed the failures (old numpy version 1.13 is behaving differently for subtraction of booleans, for now I just skip the tests for this old numpy version) @jorisvandenbossche are you doing docs here? Would need to update at least

* reference/arrays.rst
* basics.dtypes
* missing_data.rst > are you doing docs here? Would need to update at least

Good question: I now added some basic docs (add to the api reference, added to the overview tables of dtypes, added short whatsnew). 
I think it will be easier to write more documentation when we actually implement the new NA behaviour (the current PR still uses np.nan semantics, since there is not yet a pd.NA): docs on how NA in boolean operations behave, how it behaves in indexing, differences with numpy's bool dtype, etc > I think it will be easier to write more documentation when we actually implement the new NA behaviour

Agreed. The diff is showing arrays/boolean.py as unchanged, is anyone else seeing this? > The diff is showing arrays/boolean.py as unchanged, is anyone else seeing this?

Yes... That's strange. You can get click to view the whole file and it's there, but not in the `/files` diff page. Pushed an empty commit, that seems to have fixed it for me @jreback @TomAugspurger OK, made some substantial changes, recommend to look at the diff of the last commits: https://github.com/pandas-dev/pandas/pull/29555/files/a3e1e931392edd2631c3731a081e4eb16128c80a..90558d696c5407523e9fd0e8204c0a2ac8950653 have u tested this is indexing? i assume that would be a follow up  > have u tested this is indexing? i assume that would be a follow up

Yep, see https://github.com/pandas-dev/pandas/pull/29555#issuecomment-553772989 
 So to gather the follow-ups:

* Use pd.NA instead of np.nan for missing value indicator + update the logical ops to use the pd.NA behaviour
* Reduce duplication with IntegerArray (implement a BaseMaskedArray base class or something like that). This might depend on the decision on whether we already want to use pd.NA in IntegerArray as well or not.
* Update the behaviour of `any`/`all` reductions with `skipna=False` (https://github.com/pandas-dev/pandas/issues/29686)
* Enable boolean indexing with BooleanArray (we can start with handling the case of no NAs; the behaviour for with NAs still need to be decided: https://github.com/pandas-dev/pandas/issues/28778/)

(will open an issue for this) Are you all fine with almost merging this? (or maybe a final round of review?) 
Merging it would make it easier to start working on the follow-ups  let me look one more round Other question: what do we want `pd.array([..])` to return by default (when not specifying a dtype)? 

Currently, you get this behavour:
```
In [9]: pd.array([True, False]) 
Out[9]: 
<PandasArray>
[True, False]
Length: 2, dtype: bool

In [10]: pd.array([True, False, np.nan]) 
Out[10]: 
<PandasArray>
[1.0, 0.0, nan]
Length: 3, dtype: float64

In [12]: pd.array([True, False, pd.NA])
Out[12]: 
<PandasArray>
[True, False, NA]
Length: 3, dtype: object
```

Do we want to return BooleanArray also when there are no missing values (which currently returns boolean PandasArray)? 
Eg for integer, we also do not return the IntegerArray (I think the "rule" now is to basically have the same default behaviour as pandas, so only infer the extensions dtypes that are used by default (datetimetz, period, interval, etc). So if we want to be consistent with that, we should not return BooleanArray.

When a `pd.NA` is present, that's of course something new, and we could in principle decide to already infer the new dtype in that case (although then the inference of the dtype depends on the presence of a missing value or not ..) Although I am not sure this is technically easy to do, as the infer_dtypes does not distinguish different types of NA/NaN at the moment (and this out of scope of this PR, could be a future enhancement).
 I would be +1 on using all of the extension arrays (SA, IA, BA) in ``pa.array`` by default. I dont' see any downside here. I would create an issue to update ``infer_dtype`` to do this, shouldn't be very hard as that can now return IA (with an opt in flag). I think our reasoning before was to keep this consistent with the main constructors (eg in Series), so that we could in principle move towards Series(..) being Series(array(..)) at some point. 
 > Do we want to return BooleanArray also when there are no missing values (which currently returns boolean PandasArray)?

I don't think that we should have value-dependent behavior here.

On the broader issue, I'd be fine with `pd.array(..., dtype=None)` starting to infer these new EAs. Will make a new issue for that.
 @jreback ping thanks @jorisvandenbossche other things can be done as followups.