[1.7.x] Fixed the ordering of prefetch lookups so that latter lookups can refer to former lookups.

Thanks Anssi Kääriäinen and Tim Graham for the reviews. Refs #17001 and #22650.

Backport of 870b0a1f86 from master

2 files changed, 22 insertions, 23 deletions

diff --git a/django/db/models/query.py b/django/db/models/query.py
index d518b012b7..2889cf5e51 100644
--- a/django/db/models/query.py
+++ b/django/db/models/query.py
@@ -2,8 +2,8 @@
 The main QuerySet implementation. This provides the public API for the ORM.
 """
 
+from collections import deque
 import copy
-import itertools
 import sys
 
 from django.conf import settings
@@ -1681,6 +1681,9 @@ class Prefetch(object):
             return self.prefetch_to == other.prefetch_to
         return False
 
+    def __hash__(self):
+        return hash(self.__class__) ^ hash(self.prefetch_to)
+
 
 def normalize_prefetch_lookups(lookups, prefix=None):
     """
@@ -1714,11 +1717,12 @@ def prefetch_related_objects(result_cache, related_lookups):
     # ensure we don't do duplicate work.
     done_queries = {}    # dictionary of things like 'foo__bar': [results]
 
-    auto_lookups = []  # we add to this as we go through.
+    auto_lookups = set()  # we add to this as we go through.
     followed_descriptors = set()  # recursion protection
 
-    all_lookups = itertools.chain(related_lookups, auto_lookups)
-    for lookup in all_lookups:
+    all_lookups = deque(related_lookups)
+    while all_lookups:
+        lookup = all_lookups.popleft()
         if lookup.prefetch_to in done_queries:
             if lookup.queryset:
                 raise ValueError("'%s' lookup was already seen with a different queryset. "
@@ -1789,7 +1793,9 @@ def prefetch_related_objects(result_cache, related_lookups):
                 # the new lookups from relationships we've seen already.
                 if not (lookup in auto_lookups and descriptor in followed_descriptors):
                     done_queries[prefetch_to] = obj_list
-                    auto_lookups.extend(normalize_prefetch_lookups(additional_lookups, prefetch_to))
+                    new_lookups = normalize_prefetch_lookups(additional_lookups, prefetch_to)
+                    auto_lookups.update(new_lookups)
+                    all_lookups.extendleft(new_lookups)
                 followed_descriptors.add(descriptor)
             else:
                 # Either a singly related object that has already been fetched
@@ -1828,7 +1834,6 @@ def get_prefetcher(instance, attr):
      a boolean that is True if the attribute has already been fetched)
     """
     prefetcher = None
-    attr_found = False
     is_fetched = False
 
     # For singly related objects, we have to avoid getting the attribute
@@ -1836,16 +1841,7 @@ def get_prefetcher(instance, attr):
     # on the class, in order to get the descriptor object.
     rel_obj_descriptor = getattr(instance.__class__, attr, None)
     if rel_obj_descriptor is None:
-        try:
-            rel_obj = getattr(instance, attr)
-            attr_found = True
-            # If we are following a lookup path which leads us through a previous
-            # fetch from a custom Prefetch then we might end up into a list
-            # instead of related qs. This means the objects are already fetched.
-            if isinstance(rel_obj, list):
-                is_fetched = True
-        except AttributeError:
-            pass
+        attr_found = hasattr(instance, attr)
     else:
         attr_found = True
         if rel_obj_descriptor:
@@ -1890,10 +1886,10 @@ def prefetch_one_level(instances, prefetcher, lookup, level):
 
     rel_qs, rel_obj_attr, instance_attr, single, cache_name = (
         prefetcher.get_prefetch_queryset(instances, lookup.get_current_queryset(level)))
-    # We have to handle the possibility that the default manager itself added
-    # prefetch_related lookups to the QuerySet we just got back. We don't want to
-    # trigger the prefetch_related functionality by evaluating the query.
-    # Rather, we need to merge in the prefetch_related lookups.
+    # We have to handle the possibility that the QuerySet we just got back
+    # contains some prefetch_related lookups. We don't want to trigger the
+    # prefetch_related functionality by evaluating the query. Rather, we need
+    # to merge in the prefetch_related lookups.
     additional_lookups = getattr(rel_qs, '_prefetch_related_lookups', [])
     if additional_lookups:
         # Don't need to clone because the manager should have given us a fresh
diff --git a/tests/prefetch_related/tests.py b/tests/prefetch_related/tests.py
index 596702d694..6181adf094 100644
--- a/tests/prefetch_related/tests.py
+++ b/tests/prefetch_related/tests.py
@@ -195,7 +195,7 @@ class PrefetchRelatedTests(TestCase):
     def test_reverse_one_to_one_then_m2m(self):
         """
         Test that we can follow a m2m relation after going through
-        the select_related reverse of a o2o.
+        the select_related reverse of an o2o.
         """
         qs = Author.objects.prefetch_related('bio__books').select_related('bio')
 
@@ -559,13 +559,16 @@ class CustomPrefetchTests(TestCase):
         inner_rooms_qs = Room.objects.filter(pk__in=[self.room1_1.pk, self.room1_2.pk])
         houses_qs_prf = House.objects.prefetch_related(
             Prefetch('rooms', queryset=inner_rooms_qs, to_attr='rooms_lst'))
-        with self.assertNumQueries(3):
+        with self.assertNumQueries(4):
             lst2 = list(Person.objects.prefetch_related(
-                Prefetch('houses', queryset=houses_qs_prf.filter(pk=self.house1.pk), to_attr='houses_lst')))
+                Prefetch('houses', queryset=houses_qs_prf.filter(pk=self.house1.pk), to_attr='houses_lst'),
+                Prefetch('houses_lst__rooms_lst__main_room_of')
+            ))
 
         self.assertEqual(len(lst2[0].houses_lst[0].rooms_lst), 2)
         self.assertEqual(lst2[0].houses_lst[0].rooms_lst[0], self.room1_1)
         self.assertEqual(lst2[0].houses_lst[0].rooms_lst[1], self.room1_2)
+        self.assertEqual(lst2[0].houses_lst[0].rooms_lst[0].main_room_of, self.house1)
         self.assertEqual(len(lst2[1].houses_lst), 0)
 
         # Test ReverseSingleRelatedObjectDescriptor.