[2.1.x] Fixed #29838 -- Fixed crash when combining Q objects with __in lookups and lists.

Regression in fc6528b25ab1834be1a478b405bf8f7ec5cf860c.

Backport of 834c4ec8e4cfc43acf0525e0a4d8c914534f6afd,
217f82d7139fd32f07adbfa92c5fb383d0ade577, and
dc5e75d419893bde33b7e439b59bdf271fc1a3f2 from master.

5 files changed, 63 insertions, 6 deletions

diff --git a/django/utils/hashable.py b/django/utils/hashable.py
new file mode 100644
index 0000000000..0bef5b003d
--- /dev/null
+++ b/django/utils/hashable.py
@@ -0,0 +1,19 @@
+from django.utils.itercompat import is_iterable
+
+
+def make_hashable(value):
+    if isinstance(value, dict):
+        return tuple([
+            (key, make_hashable(nested_value))
+            for key, nested_value in value.items()
+        ])
+    # Try hash to avoid converting a hashable iterable (e.g. string, frozenset)
+    # to a tuple.
+    try:
+        hash(value)
+    except TypeError:
+        if is_iterable(value):
+            return tuple(map(make_hashable, value))
+        # Non-hashable, non-iterable.
+        raise
+    return value
diff --git a/django/utils/tree.py b/django/utils/tree.py
index 421ad5cd3c..302cd37d5f 100644
--- a/django/utils/tree.py
+++ b/django/utils/tree.py
@@ -5,6 +5,8 @@ ORM.
 
 import copy
 
+from django.utils.hashable import make_hashable
+
 
 class Node:
     """
@@ -71,10 +73,7 @@ class Node:
         )
 
     def __hash__(self):
-        return hash((self.__class__, self.connector, self.negated) + tuple([
-            tuple(child) if isinstance(child, list) else child
-            for child in self.children
-        ]))
+        return hash((self.__class__, self.connector, self.negated, *make_hashable(self.children)))
 
     def add(self, data, conn_type, squash=True):
         """
diff --git a/docs/releases/2.1.3.txt b/docs/releases/2.1.3.txt
index 5de73d93d4..15e53db65b 100644
--- a/docs/releases/2.1.3.txt
+++ b/docs/releases/2.1.3.txt
@@ -4,9 +4,10 @@ Django 2.1.3 release notes
 
 *Expected November 1, 2018*
 
-Django 2.1.3 fixes several bugs in 2.1.2
+Django 2.1.3 fixes several bugs in 2.1.2.
 
 Bugfixes
 ========
 
-* ...
\ No newline at end of file
+* Fixed a regression in Django 2.0 where combining ``Q`` objects with ``__in``
+  lookups and lists crashed (:ticket:`29838`).
diff --git a/tests/utils_tests/test_hashable.py b/tests/utils_tests/test_hashable.py
new file mode 100644
index 0000000000..b4db3ef7d7
--- /dev/null
+++ b/tests/utils_tests/test_hashable.py
@@ -0,0 +1,35 @@
+from django.test import SimpleTestCase
+from django.utils.hashable import make_hashable
+
+
+class TestHashable(SimpleTestCase):
+    def test_equal(self):
+        tests = (
+            ([], ()),
+            (['a', 1], ('a', 1)),
+            ({}, ()),
+            ({'a'}, ('a',)),
+            (frozenset({'a'}), {'a'}),
+            ({'a': 1}, (('a', 1),)),
+            (('a', ['b', 1]), ('a', ('b', 1))),
+            (('a', {'b': 1}), ('a', (('b', 1),))),
+        )
+        for value, expected in tests:
+            with self.subTest(value=value):
+                self.assertEqual(make_hashable(value), expected)
+
+    def test_count_equal(self):
+        tests = (
+            ({'a': 1, 'b': ['a', 1]}, (('a', 1), ('b', ('a', 1)))),
+            ({'a': 1, 'b': ('a', [1, 2])}, (('a', 1), ('b', ('a', (1, 2))))),
+        )
+        for value, expected in tests:
+            with self.subTest(value=value):
+                self.assertCountEqual(make_hashable(value), expected)
+
+    def test_unhashable(self):
+        class Unhashable:
+            __hash__ = None
+
+        with self.assertRaisesMessage(TypeError, "unhashable type: 'Unhashable'"):
+            make_hashable(Unhashable())
diff --git a/tests/utils_tests/test_tree.py b/tests/utils_tests/test_tree.py
index c59398aedb..154678ff57 100644
--- a/tests/utils_tests/test_tree.py
+++ b/tests/utils_tests/test_tree.py
@@ -24,12 +24,15 @@ class NodeTests(unittest.TestCase):
         node4 = Node(self.node1_children, connector='OTHER')
         node5 = Node(self.node1_children)
         node6 = Node([['a', 1], ['b', 2]])
+        node7 = Node([('a', [1, 2])])
+        node8 = Node([('a', (1, 2))])
         self.assertNotEqual(hash(self.node1), hash(self.node2))
         self.assertNotEqual(hash(self.node1), hash(node3))
         self.assertNotEqual(hash(self.node1), hash(node4))
         self.assertEqual(hash(self.node1), hash(node5))
         self.assertEqual(hash(self.node1), hash(node6))
         self.assertEqual(hash(self.node2), hash(Node()))
+        self.assertEqual(hash(node7), hash(node8))
 
     def test_len(self):
         self.assertEqual(len(self.node1), 2)