queryset-refactor: Reworked exclude() handling to fix a few merging problems.

Fixed #6704.


git-svn-id: http://code.djangoproject.com/svn/django/branches/queryset-refactor@7217 bcc190cf-cafb-0310-a4f2-bffc1f526a37

4 files changed, 88 insertions, 29 deletions

diff --git a/django/db/models/sql/query.py b/django/db/models/sql/query.py
index f0fb3ada13..ef3f5220fb 100644
--- a/django/db/models/sql/query.py
+++ b/django/db/models/sql/query.py
@@ -20,6 +20,11 @@ from django.core.exceptions import FieldError
 from datastructures import EmptyResultSet, Empty
 from constants import *
 
+try:
+    set
+except NameError:
+    from sets import Set as set     # Python 2.3 fallback
+
 __all__ = ['Query']
 
 class Query(object):
@@ -573,13 +578,9 @@ class Query(object):
         """
         Promotes the join type of an alias to an outer join if it's possible
         for the join to contain NULL values on the left.
-
-        Returns True if the aliased join was promoted.
         """
         if self.alias_map[alias][ALIAS_NULLABLE]:
             self.alias_map[alias][ALIAS_JOIN][JOIN_TYPE] = self.LOUTER
-            return True
-        return False
 
     def change_alias(self, old_alias, new_alias):
         """
@@ -753,7 +754,8 @@ class Query(object):
             self.fill_related_selections(f.rel.to._meta, alias, cur_depth + 1,
                     used, next, restricted)
 
-    def add_filter(self, filter_expr, connector=AND, negate=False, trim=False):
+    def add_filter(self, filter_expr, connector=AND, negate=False, trim=False,
+            merge_negated=False):
         """
         Add a single filter to the query. The 'filter_expr' is a pair:
         (filter_string, value). E.g. ('name__contains', 'fred')
@@ -761,6 +763,10 @@ class Query(object):
         If 'negate' is True, this is an exclude() filter. If 'trim' is True, we
         automatically trim the final join group (used internally when
         constructing nested queries).
+
+        If 'merge_negated' is True, this negated filter will be merged with the
+        existing negated where node (if it exists). This is used when
+        constructing an exclude filter from combined subfilters.
         """
         arg, value = filter_expr
         parts = arg.split(LOOKUP_SEP)
@@ -813,9 +819,13 @@ class Query(object):
                 self.unref_alias(alias)
                 alias = join[LHS_ALIAS]
                 col = join[LHS_JOIN_COL]
+                if len(join_list[-1]) == 1:
+                    join_list = join_list[:-1]
+                else:
+                    join_list[-1] = join_list[-1][:-1]
 
-        if lookup_type == 'isnull' and value is True and (len(join_list) > 1 or
-                len(join_list[0]) > 1):
+        if (lookup_type == 'isnull' and value is True and not negate and
+                (len(join_list) > 1 or len(join_list[0]) > 1)):
             # If the comparison is against NULL, we need to use a left outer
             # join when connecting to the previous model. We make that
             # adjustment here. We don't do this unless needed as it's less
@@ -846,19 +856,32 @@ class Query(object):
                 # that's harmless.
                 self.promote_alias(table)
 
-        self.where.add([alias, col, field, lookup_type, value], connector)
+        entry = [alias, col, field, lookup_type, value]
+        if merge_negated:
+            # This case is when we're doing the Q2 filter in exclude(Q1, Q2).
+            # It's different from exclude(Q1).exclude(Q2).
+            for node in self.where.children:
+                if getattr(node, 'negated', False):
+                    node.add(entry, connector)
+                    merged = True
+                    break
+        else:
+            self.where.add(entry, connector)
+            merged = False
 
         if negate:
-            flag = False
-            for seq in join_list:
-                for join in seq:
-                    if self.promote_alias(join):
-                        flag = True
-            self.where.negate()
-            if flag:
-                # XXX: Change this to the field we joined against to allow
-                # for node sharing and where-tree optimisation?
-                self.where.add([alias, col, field, 'isnull', True], OR)
+            count = 0
+            for join in join_list:
+                count += len(join)
+                for alias in join:
+                    self.promote_alias(alias)
+            if not merged:
+                self.where.negate()
+            if count > 1 and lookup_type != 'isnull':
+                j_col = self.alias_map[alias][ALIAS_JOIN][RHS_JOIN_COL]
+                entry = Node([[alias, j_col, None, 'isnull', True]])
+                entry.negate()
+                self.where.add(entry, AND)
 
     def add_q(self, q_object):
         """
@@ -877,13 +900,16 @@ class Query(object):
         else:
             subtree = False
         connector = AND
+        merge = False
         for child in q_object.children:
             if isinstance(child, Node):
                 self.where.start_subtree(connector)
                 self.add_q(child)
                 self.where.end_subtree()
             else:
-                self.add_filter(child, connector, q_object.negated)
+                self.add_filter(child, connector, q_object.negated,
+                        merge_negated=merge)
+                merge = q_object.negated
             connector = q_object.connector
         if subtree:
             self.where.end_subtree()
@@ -902,7 +928,9 @@ class Query(object):
         list of tables joined.
         """
         joins = [[alias]]
+        used = set()
         for pos, name in enumerate(names):
+            used.update(joins[-1])
             if name == 'pk':
                 name = opts.pk.name
 
@@ -924,7 +952,7 @@ class Query(object):
                     lhs_col = opts.parents[int_model].column
                     opts = int_model._meta
                     alias = self.join((alias, opts.db_table, lhs_col,
-                            opts.pk.column))
+                            opts.pk.column), exclusions=used)
                     alias_list.append(alias)
                 joins.append(alias_list)
             cached_data = opts._join_cache.get(name)
@@ -950,9 +978,9 @@ class Query(object):
                                 target)
 
                     int_alias = self.join((alias, table1, from_col1, to_col1),
-                            dupe_multis, nullable=True)
+                            dupe_multis, used, nullable=True)
                     alias = self.join((int_alias, table2, from_col2, to_col2),
-                            dupe_multis, nullable=True)
+                            dupe_multis, used, nullable=True)
                     joins.append([int_alias, alias])
                 elif field.rel:
                     # One-to-one or many-to-one field
@@ -968,7 +996,7 @@ class Query(object):
                                 opts, target)
 
                     alias = self.join((alias, table, from_col, to_col),
-                            nullable=field.null)
+                            exclusions=used, nullable=field.null)
                     joins.append([alias])
                 else:
                     # Non-relation fields.
@@ -996,9 +1024,9 @@ class Query(object):
                                 target)
 
                     int_alias = self.join((alias, table1, from_col1, to_col1),
-                            dupe_multis, nullable=True)
+                            dupe_multis, used, nullable=True)
                     alias = self.join((int_alias, table2, from_col2, to_col2),
-                            dupe_multis, nullable=True)
+                            dupe_multis, used, nullable=True)
                     joins.append([int_alias, alias])
                 else:
                     # One-to-many field (ForeignKey defined on the target model)
@@ -1016,7 +1044,7 @@ class Query(object):
                                 opts, target)
 
                     alias = self.join((alias, table, from_col, to_col),
-                            dupe_multis, nullable=True)
+                            dupe_multis, used, nullable=True)
                     joins.append([alias])
 
         if pos != len(names) - 1:
diff --git a/django/db/models/sql/where.py b/django/db/models/sql/where.py
index c4d5637658..e1c0a88121 100644
--- a/django/db/models/sql/where.py
+++ b/django/db/models/sql/where.py
@@ -5,6 +5,7 @@ import datetime
 
 from django.utils import tree
 from django.db import connection
+from django.db.models.fields import Field
 from datastructures import EmptyResultSet, FullResultSet
 
 # Connection types
@@ -105,7 +106,10 @@ class WhereNode(tree.Node):
         else:
             cast_sql = '%s'
 
-        params = field.get_db_prep_lookup(lookup_type, value)
+        if field:
+            params = field.get_db_prep_lookup(lookup_type, value)
+        else:
+            params = Field().get_db_prep_lookup(lookup_type, value)
         if isinstance(params, tuple):
             extra, params = params
         else:
diff --git a/django/utils/tree.py b/django/utils/tree.py
index 0d12ea1cbc..a62a4ae6c3 100644
--- a/django/utils/tree.py
+++ b/django/utils/tree.py
@@ -16,6 +16,14 @@ class Node(object):
     default = 'DEFAULT'
 
     def __init__(self, children=None, connector=None, negated=False):
+        """
+        Constructs a new Node. If no connector is given, the default will be
+        used.
+
+        Warning: You probably don't want to pass in the 'negated' parameter. It
+        is NOT the same as constructing a node and calling negate() on the
+        result.
+        """
         self.children = children and children[:] or []
         self.connector = connector or self.default
         self.subtree_parents = []
@@ -63,6 +71,8 @@ class Node(object):
         Otherwise, the whole tree is pushed down one level and a new root
         connector is created, connecting the existing tree and the new node.
         """
+        if node in self.children:
+            return
         if len(self.children) < 2:
             self.connector = conn_type
         if self.connector == conn_type:
@@ -78,7 +88,10 @@ class Node(object):
 
     def negate(self):
         """
-        Negate the sense of the root connector.
+        Negate the sense of the root connector. This reorganises the children
+        so that the current node has a single child: a negated node containing
+        all the previous children. This slightly odd construction makes adding
+        new children behave more intuitively.
 
         Interpreting the meaning of this negate is up to client code. This
         method is useful for implementing "not" arrangements.
diff --git a/tests/regressiontests/queries/models.py b/tests/regressiontests/queries/models.py
index ada5f1cfc3..ff55550d4e 100644
--- a/tests/regressiontests/queries/models.py
+++ b/tests/regressiontests/queries/models.py
@@ -312,7 +312,7 @@ Bug #4510
 >>> Author.objects.filter(report__name='r1')
 [<Author: a1>]
 
-Bug #5324
+Bug #5324, #6704
 >>> Item.objects.filter(tags__name='t4')
 [<Item: four>]
 >>> Item.objects.exclude(tags__name='t4').order_by('name').distinct()
@@ -340,6 +340,20 @@ Similarly, when one of the joins cannot possibly, ever, involve NULL values (Aut
 >>> len([x[2][2] for x in qs.query.alias_map.values() if x[2][2] == query.LOUTER])
 1
 
+The previous changes shouldn't affect nullable foreign key joins.
+>>> Tag.objects.filter(parent__isnull=True).order_by('name')
+[<Tag: t1>]
+>>> Tag.objects.exclude(parent__isnull=True).order_by('name')
+[<Tag: t2>, <Tag: t3>, <Tag: t4>, <Tag: t5>]
+>>> Tag.objects.exclude(Q(parent__name='t1') | Q(parent__isnull=True)).order_by('name')
+[<Tag: t4>, <Tag: t5>]
+>>> Tag.objects.exclude(Q(parent__isnull=True) | Q(parent__name='t1')).order_by('name')
+[<Tag: t4>, <Tag: t5>]
+>>> Tag.objects.exclude(Q(parent__parent__isnull=True)).order_by('name')
+[<Tag: t4>, <Tag: t5>]
+>>> Tag.objects.filter(~Q(parent__parent__isnull=True)).order_by('name')
+[<Tag: t4>, <Tag: t5>]
+
 Bug #2091
 >>> t = Tag.objects.get(name='t4')
 >>> Item.objects.filter(tags__in=[t])