Repository: numpy/numpy
Pull request: BUG: np.in1d bug on the object array (issue 17923)
<!--         ----------------------------------------------------------------
                MAKE SURE YOUR PR GETS THE ATTENTION IT DESERVES!
                ----------------------------------------------------------------

*  FORMAT IT RIGHT:
      http://www.numpy.org/devdocs/dev/development_workflow.html#writing-the-commit-message

*  IF IT'S A NEW FEATURE OR API CHANGE, TEST THE WATERS:
      http://www.numpy.org/devdocs/dev/development_workflow.html#get-the-mailing-list-s-opinion

*  HIT ALL THE GUIDELINES:
      https://numpy.org/devdocs/dev/index.html#guidelines

*  WHAT TO DO IF WE HAVEN'T GOTTEN BACK TO YOU:
      http://www.numpy.org/devdocs/dev/development_workflow.html#getting-your-pr-reviewed
-->
BUG: np.in1d bug on the object array (closes #17923)

When calling `np.in1d()` method with array that contains tuples the comparison didn't work properly due to an underling issue with the unpacking of those tuples. To prevent this, and following the approach suggested by @tylerjereddy I changed the way the comparison is made for arrays of objects, adding a wrapper to those objects preventing tuples from being unpacked.

Unit tests for the failing cases mentioned in the issue were also added.

Problem statement:
np.in1d bug on the object array
The `np.in1d`  method (Numpy 1.19.1, Python 3.8.3) makes some errors on the irregular-object array:

**Case 1:**
```python
np.in1d([(1,), 2], [(1,), 2])
```
The output should be `[True,  True]` but it says:
### Error message:
```python
array([False,  True])
```

**Case 2:**
```python
np.in1d([(1,), (2,)], [(1,), 2])
```
The output should be `[True,  False]` but it says:
### Error message:
```python
array([True,  True])
```

Hints from issue discussion:
`np.isin()` had the same behavior (calls `np.in1d()`). Not sure if a brute force pure Python loop to check element-wise equality would be an acceptable or desirable fix, although the code is kind of half way there already with a pure Python iteration through the elements in the second argument.

Assuming that probably wouldn't fly though, I noticed that `np.testing.assert_array_equal()` does have the machinery to correctly recognize the number of matching and non-matching elements for the inputs provided. I don't know if that machinery is substantially faster than the brute force Python looping offhand.
I had discussed this briefly with Tyler, and we found that the root cause are these lines of code:
https://github.com/numpy/numpy/blob/225c3360721ba515de88a1e191ede58e8b95593d/numpy/lib/arraysetops.py#L582-L583

The issue here is that the for loop `a` is the plain python object and not an array. The `==` will than effectively call `np.asarray(a, dtype=object)`, which causes the tuple to be unpacked.  So for the first element, it ends up with `np.asarray(ar1[0], dtype=object)`, which is `np.asarray((1,), dtype=object)`.

The solution could be to write the for loop like this (for object arrays): `for a in (arr[i,...] for i in range(len(arr))):` although I would hope we can find a prettier way.
I got past the first case with the diff below, but then I realized we are really in trouble for the second case because the first thing `np.in1d()` does is call `np.asarray()` and once you do that on `[(1,), (2,)]` in case 2 above the tuples are gone no matter what you do later on. `np.asarray()` does preserve the tuple with `[(1,), 2]`.

Seems like the fix would have to be pretty invasive then for this to handle the all-tuple object input vs. just some tuples? Indeed, when  all elements are a tuple that seems like a not-so-unusual way to specify a 2D array of data so could probably argue that's the right thing to do I guess.

(this doesn't work with structured dtypes I don't think):

```diff
diff --git a/numpy/lib/arraysetops.py b/numpy/lib/arraysetops.py
index 6c6c1ff80..45b148f44 100644
--- a/numpy/lib/arraysetops.py
+++ b/numpy/lib/arraysetops.py
@@ -579,8 +579,10 @@ def in1d(ar1, ar2, assume_unique=False, invert=False):
                 mask &= (ar1 != a)
         else:
             mask = np.zeros(len(ar1), dtype=bool)
+            store = np.empty(shape=1, dtype=object)
             for a in ar2:
-                mask |= (ar1 == a)
+                store[0] = a
+                mask |= (ar1 == store)
         return mask
 
     # Otherwise use sorting

```
So yeah, I guess we'd have to clarify if the proposed "correct" answer to case 2 above is actually correct or not.
I was trying to resolve this issue. There is one thing I wanted to ask whether the 
`np.in1d([(1,), (2,3)], [(1,), 2])` should be `array([True,True)]` or `array([True,False)]`
And also if we are implementing the second case, would be applicable for different iterables such as tuples and lists should be checked against each other. 


The second one is correct and it should do nothing special aside from whatever comparing the original object dos.
I was checking on this but I'm afraid the behavior of `==` over the Numpy array class is defined in it's C++ implementation so the comparison between tuples in the arrays that is failing should also be fixed in that implementation and not on the Python side.
@AngelGris that is not what is going on, the tuple is incorrectly unpacked _before_ the `==` operation (which does nothing strange for `obect`s).  The diff that Tyler posted is good, might need to think about a nicer way, but mostly we need to transform it into a PR with a test.
Oh, sorry, the `==` operator *does* call `np.asarray(a)` which unpacks.  But I don't think we can change that behviour, so a python side fix similar to the one above is better.
I've been doing some more research on this and I find it weird too how the arrays are being built when containing tuples.
Take the following example:
```
>>> import numpy as np
>>> np.array([(1,), (2,1)], dtype=object)
array([(1,), (2, 1)], dtype=object)
>>> np.array([(1,), [2]], dtype=object)
array([[1],
       [2]], dtype=object)
>>> np.array([(1,), (2,)], dtype=object)
array([[1],
       [2]], dtype=object)
>>> np.array([(1,2), (2,3)], dtype=object)
array([[1, 2],
       [2, 3]], dtype=object)
```

So when the tuples have the same amount of items the array constructor converts them into arrays and that's what we pass later to `in1d()`. For instance if we want to compare the first 2 arrays (`[(1,), (2, 1)]` and `[[1], [2]]`) and given that we built both of them containing tuples we would expect to get `[True, False]` as the result, but we will get `[False, False]` because we will be comparing an array containing tuples with another array containing arrays

Now I'm wondering if the problem is the array constructor, the unpacking of tuples, or both.

Commit message: BUG: np.in1d bug on the object array (issue 17923)

Patch to review:
diff --git a/numpy/lib/arraysetops.py b/numpy/lib/arraysetops.py
index 6c6c1ff809ce..e7f9add205dd 100644
--- a/numpy/lib/arraysetops.py
+++ b/numpy/lib/arraysetops.py
@@ -575,12 +575,28 @@ def in1d(ar1, ar2, assume_unique=False, invert=False):
     if len(ar2) < 10 * len(ar1) ** 0.145 or contains_object:
         if invert:
             mask = np.ones(len(ar1), dtype=bool)
-            for a in ar2:
-                mask &= (ar1 != a)
+            # If ar2.dtype is object, store is used to wrap the a value
+            # in an array to prevent tuples from being unpacked before the comparison
+            if ar2.dtype == object:
+                store = np.empty(shape=1, dtype=object)
+                for a in ar2:
+                    store[0] = a
+                    mask &= (ar1 != store)
+            else:
+                for a in ar2:
+                    mask &= (ar1 != a)
         else:
             mask = np.zeros(len(ar1), dtype=bool)
-            for a in ar2:
-                mask |= (ar1 == a)
+            # If ar2.dtype is object, store is used to wrap the a value
+            # in an array to prevent tuples from being unpacked before the comparison
+            if ar2.dtype == object:
+                store = np.empty(shape=1, dtype=object)
+                for a in ar2:
+                    store[0] = a
+                    mask |= (ar1 == store)
+            else:
+                for a in ar2:
+                    mask |= (ar1 == a)
         return mask
 
     # Otherwise use sorting
diff --git a/numpy/lib/tests/test_arraysetops.py b/numpy/lib/tests/test_arraysetops.py
index 847e6cb8a3e7..de2ef255ceb5 100644
--- a/numpy/lib/tests/test_arraysetops.py
+++ b/numpy/lib/tests/test_arraysetops.py
@@ -358,6 +358,39 @@ def test_in1d_both_arrays_have_structured_dtype(self):
         result = np.in1d(ar1, ar2)
         assert_array_equal(result, expected)
 
+    def test_in1d_with_arrays_containing_tuples(self):
+        ar1 = np.array([(1,), 2], dtype=object)
+        ar2 = np.array([(1,), 2], dtype=object)
+        expected = np.array([True, True])
+        result = np.in1d(ar1, ar2)
+        assert_array_equal(result, expected)
+        result = np.in1d(ar1, ar2, invert=True)
+        assert_array_equal(result, np.invert(expected))
+
+        # An integer is added at the end of the array to make sure
+        # that the array builder will create the array with tuples
+        # and after it's created the integer is removed.
+        # There's a bug in the array constructor that doesn't handle
+        # tuples properly and adding the integer fixes that.
+        ar1 = np.array([(1,), (2, 1), 1], dtype=object)
+        ar1 = ar1[:-1]
+        ar2 = np.array([(1,), (2, 1), 1], dtype=object)
+        ar2 = ar2[:-1]
+        expected = np.array([True, True])
+        result = np.in1d(ar1, ar2)
+        assert_array_equal(result, expected)
+        result = np.in1d(ar1, ar2, invert=True)
+        assert_array_equal(result, np.invert(expected))
+
+        ar1 = np.array([(1,), (2, 3), 1], dtype=object)
+        ar1 = ar1[:-1]
+        ar2 = np.array([(1,), 2], dtype=object)
+        expected = np.array([True, False])
+        result = np.in1d(ar1, ar2)
+        assert_array_equal(result, expected)
+        result = np.in1d(ar1, ar2, invert=True)
+        assert_array_equal(result, np.invert(expected))
+
     def test_union1d(self):
         a = np.array([5, 4, 7, 1, 2])
         b = np.array([2, 4, 3, 3, 2, 1, 5])


Code review comments:
diff_hunk: @@ -575,12 +575,28 @@ def in1d(ar1, ar2, assume_unique=False, invert=False):
     if len(ar2) < 10 * len(ar1) ** 0.145 or contains_object:
         if invert:
             mask = np.ones(len(ar1), dtype=bool)
-            for a in ar2:
-                mask &= (ar1 != a)
+            # If ar2.dtype is object, store is used to wrap the a value
path: numpy/lib/arraysetops.py
text: @user1:
These new `if`/`else` statements should be redundant if you just append an additional axis to the object array in question. This way iteration will always yield your size-1 array.
``` diff
- ar2 = np.asarray(ar2).ravel()
+ ar2 = np.asarray(ar2).ravel()
+
+ # Ensure that iteration through object arrays yields size-1 arrays 
+ if ar2.dtype == object:
+     ar2 = ar2.reshape(-1, 1)
```

@author:
That was a great suggestion. Fixed the bug with a much simpler code.
Thanks for the help.

@user1:
Currently `ar2` is always a 1D array, so iterating through it will always yield its "scalar" elements 
(or tuples in case of your specific object array). By reshaping the shape-`(n,)` array into a shape-
`(n, 1)` array, iteration will now directly yield size-1 1D arrays without having to resort to this
temporary `store` variable.

``` python
In [28]: a = np.arange(3)

In [29]: a.shape
Out[29]: (3,)

In [30]: for i in a:  # yields scalars
    ...:     print(i)
    ...:
0
1
2

In [31]: b = a.reshape(-1, 1)

In [32]: b.shape
Out[32]: (3, 1)

In [33]: for i in b:  # yields size-1 1D arrays
    ...:     print(i)
    ...:
[0]
[1]
[2]
```