Repository: pandas-dev/pandas
Pull request: Multiindex recurse error fix
test and 3 line fix for a small bug mentioned in 2 issues (1 closed). test might be expanded, I only checked for the error disappearing

- [x] closes #25760 (and #28956 )
- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry


Problem statement:
RecursionError when aligning DataFrames based on MultiIndex with different order of names
#### Code Sample, a copy-pastable example if possible

```python
import pandas as pd
import numpy as np
x=pd.DataFrame(np.arange(4),pd.MultiIndex.from_product([[1,2],[3,4]],names=['a','b']))
y=pd.DataFrame(np.arange(4),pd.MultiIndex.from_product([[3,4],[1,2]],names=['b','a']))
print(x+y)
```
#### Problem description
RecursionError in align()/join().
The ideal expected behavior is to calculate the sum.
If different orders of names in MultiIndex are not supported by design, then a clear error message stating that would be preferable to RecursionError.

#### Expected Output
```
     0
a b   
1 3  0
  4  3
2 3  3
  4  6
```
or
```
     0
b a   
3 1  0
  2  3
4 1  3
  2  6
```
#### Output of ``pd.show_versions()``

<details>

INSTALLED VERSIONS
------------------
commit: None
python: 3.7.1.final.0
python-bits: 64
OS: Linux
OS-release: 4.9.125-linuxkit
machine: x86_64
processor: x86_64
byteorder: little
LC_ALL: en_US.UTF-8
LANG: en_US.UTF-8
LOCALE: en_US.UTF-8

pandas: 0.24.2
pytest: None
pip: 19.0.3
setuptools: 40.8.0
Cython: 0.29.6
numpy: 1.15.4
scipy: 1.2.1
pyarrow: None
xarray: None
IPython: 7.3.0
sphinx: None
patsy: 0.5.1
dateutil: 2.8.0
pytz: 2018.9
blosc: None
bottleneck: None
tables: None
numexpr: 2.6.9
feather: None
matplotlib: 3.0.3
openpyxl: None
xlrd: 1.2.0
xlwt: None
xlsxwriter: None
lxml.etree: None
bs4: 4.7.1
html5lib: None
sqlalchemy: 1.3.1
pymysql: None
psycopg2: None
jinja2: 2.10
s3fs: None
fastparquet: None
pandas_gbq: None
pandas_datareader: None
gcsfs: None

</details>

Hints from issue discussion:
I'm not sure if we make any requirements around the ordering of levels in a MultiIndex - @mroeschke any thoughts here?
One issue is that if this arithmetic is allowed which solution should this op return?

I think this case is ambiguous and would opt to raise in this case - a more informative error message in this case. 
> One issue is that if this arithmetic is allowed which solution should this op return?

If all operations after that "align on both row and column labels" as [documentation](https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.html) says, then picking which to return is not important. It's like picking which order to use for lists that represent sets.
Conversely, if order is important (and not labels), then documentation of DataFrame has to be changed.

Another option is to change behavior of align - currently it puts common columns before others. It's a problem because even if I try to use a consistent order of columns in my application, it gets jumbled by operations that use align. E.g., if I have `X` and `Y` both with columns `a` and `b`, and `Z` with column `b`, then `(X+Z)+Y` will fail, as `X+Z` will have columns `b` and `a` (in this order).
Just ran into this. I ended up having to write a workaround like this:
```python
def align_levels(ref, obj):
    """Return a copy of *obj* with common levels in the same order as *ref*."""
    # Common levels in the same order as ref
    common = [n for n in ref.index.names if n in obj.index.names]
    # Levels only appearing on obj
    unique = [n for n in obj.index.names if n not in common]
    # Return copy with new level order
    return obj.reorder_levels(common + unique)

x * align_levels(x, y)
```
I looked a little bit at the source code, and I think the cause of this is the following:

## Possible Cause of the Issue

In `pandas.core.indexes.base.join()`, there is first a check to see of `self.names == other.names`. This is false if the names are the same but in the opposite order.

Then in `pandas.core.indexes.base._join_multi()`, there is a call on `pandas.core.indexes.base.join()` on the **set intersection** of the level names. So this treats the levels the same even if they are in the opposite order.

For the same set of names but in the wrong order, the recursion keeps alternating between `pandas.core.indexes.base.join()` and `pandas.core.indexes.base._join_multi()`.

## Question

Considering that there isn't any decision as to how this should work, would it be possible to check if the neither of the indexes changed in `_join_multi()` before recalling `join()`? If neither changed, then throw an error instead of allowing the infinite recursion?

Commit message: black formatting

Patch to review:
diff --git a/pandas/core/indexes/base.py b/pandas/core/indexes/base.py
index 4c15e4b26ed46..4e0dbe2c64d60 100644
--- a/pandas/core/indexes/base.py
+++ b/pandas/core/indexes/base.py
@@ -3549,8 +3549,12 @@ def _join_multi(self, other, how, return_indexers=True):
             ldrop_names = list(self_names - overlap)
             rdrop_names = list(other_names - overlap)
 
-            self_jnlevels = self.droplevel(ldrop_names)
-            other_jnlevels = other.droplevel(rdrop_names)
+            if len(ldrop_names + rdrop_names) == 0:  # if only the order differs
+                self_jnlevels = self
+                other_jnlevels = other.reorder_levels(self.names)
+            else:
+                self_jnlevels = self.droplevel(ldrop_names)
+                other_jnlevels = other.droplevel(rdrop_names)
 
             # Join left and right
             # Join on same leveled multi-index frames is supported
diff --git a/pandas/tests/indexes/multi/test_join.py b/pandas/tests/indexes/multi/test_join.py
index 42d8cf761842e..c07e0248a197c 100644
--- a/pandas/tests/indexes/multi/test_join.py
+++ b/pandas/tests/indexes/multi/test_join.py
@@ -87,3 +87,13 @@ def test_join_self_unique(idx, join_type):
     if idx.is_unique:
         joined = idx.join(idx, how=join_type)
         assert (idx == joined).all()
+
+
+def test_join_multi_wrong_order():
+    # GH 25760
+    # GH 28956
+
+    midx1 = pd.MultiIndex.from_product([[1, 2], [3, 4]], names=["a", "b"])
+    midx2 = pd.MultiIndex.from_product([[1, 2], [3, 4]], names=["b", "a"])
+
+    midx1.join(midx2)


Code review comments:
diff_hunk: @@ -3549,8 +3549,12 @@ def _join_multi(self, other, how, return_indexers=True):
             ldrop_names = list(self_names - overlap)
             rdrop_names = list(other_names - overlap)
 
-            self_jnlevels = self.droplevel(ldrop_names)
-            other_jnlevels = other.droplevel(rdrop_names)
+            if len(ldrop_names + rdrop_names) == 0:  # if only the order differs
path: pandas/core/indexes/base.py
text: @user1:
rather than add a special case, is there an issue droplevel?

@author:
I'm sorry, "issue droplevel"?

@user1:
I am not sure what you are trying to fix here. is there somthing that is actually wrong with droplevel instead of adding a special case here

@author:
nothing is wrong with droplevel, it just gets called twice with empty lists if ```len(ldrop_names + rdrop_names) == 0``` is true, which seems pointless. and then because this doesn't change anything, it ends up in an infinite recursion loop. this can be stopped with checking for this condition, and the reordering of the names makes the join work.

@user1:
ok, this is not idiomatic, use
```
if not len(....)
 ....
```
put he comment on the line above