1 """

     2 Create SQL statements for QuerySets.

     3 

     4 The code in here encapsulates all of the SQL construction so that QuerySets

     5 themselves do not have to (and could be backed by things other than SQL

     6 databases). The abstraction barrier only works one way: this module has to know

     7 all about the internals of models in order to get the information it needs.

     8 """

     9 

    10 from django.utils.copycompat import deepcopy

    11 from django.utils.tree import Node

    12 from django.utils.datastructures import SortedDict

    13 from django.utils.encoding import force_unicode

    14 from django.db import connections, DEFAULT_DB_ALIAS

    15 from django.db.models import signals

    16 from django.db.models.fields import FieldDoesNotExist

    17 from django.db.models.query_utils import select_related_descend, InvalidQuery

    18 from django.db.models.sql import aggregates as base_aggregates_module

    19 from django.db.models.sql.constants import *

    20 from django.db.models.sql.datastructures import EmptyResultSet, Empty, MultiJoin

    21 from django.db.models.sql.expressions import SQLEvaluator

    22 from django.db.models.sql.where import (WhereNode, Constraint, EverythingNode,

    23     ExtraWhere, AND, OR)

    24 from django.core.exceptions import FieldError

    25 

    26 __all__ = ['Query', 'RawQuery']

    27 

    28 class RawQuery(object):

    29     """

    30     A single raw SQL query

    31     """

    32 

    33     def __init__(self, sql, using, params=None):

    34         self.validate_sql(sql)

    35         self.params = params or ()

    36         self.sql = sql

    37         self.using = using

    38         self.cursor = None

    39 

    40         # Mirror some properties of a normal query so that

    41         # the compiler can be used to process results.

    42         self.low_mark, self.high_mark = 0, None  # Used for offset/limit

    43         self.extra_select = {}

    44         self.aggregate_select = {}

    45 

    46     def clone(self, using):

    47         return RawQuery(self.sql, using, params=self.params)

    48 

    49     def convert_values(self, value, field, connection):

    50         """Convert the database-returned value into a type that is consistent

    51         across database backends.

    52 

    53         By default, this defers to the underlying backend operations, but

    54         it can be overridden by Query classes for specific backends.

    55         """

    56         return connection.ops.convert_values(value, field)

    57 

    58     def get_columns(self):

    59         if self.cursor is None:

    60             self._execute_query()

    61         converter = connections[self.using].introspection.table_name_converter

    62         return [converter(column_meta[0])

    63                 for column_meta in self.cursor.description]

    64 

    65     def validate_sql(self, sql):

    66         if not sql.lower().strip().startswith('select'):

    67             raise InvalidQuery('Raw queries are limited to SELECT queries. Use '

    68                                'connection.cursor directly for other types of queries.')

    69 

    70     def __iter__(self):

    71         # Always execute a new query for a new iterator.

    72         # This could be optimized with a cache at the expense of RAM.

    73         self._execute_query()

    74         if not connections[self.using].features.can_use_chunked_reads:

    75             # If the database can't use chunked reads we need to make sure we

    76             # evaluate the entire query up front.

    77             result = list(self.cursor)

    78         else:

    79             result = self.cursor

    80         return iter(result)

    81 

    82     def __repr__(self):

    83         return "<RawQuery: %r>" % (self.sql % self.params)

    84 

    85     def _execute_query(self):

    86         self.cursor = connections[self.using].cursor()

    87         self.cursor.execute(self.sql, self.params)

    88 

    89 

    90 class Query(object):

    91     """

    92     A single SQL query.

    93     """

    94     # SQL join types. These are part of the class because their string forms

    95     # vary from database to database and can be customised by a subclass.

    96     INNER = 'INNER JOIN'

    97     LOUTER = 'LEFT OUTER JOIN'

    98 

    99     alias_prefix = 'T'

   100     query_terms = QUERY_TERMS

   101     aggregates_module = base_aggregates_module

   102 

   103     compiler = 'SQLCompiler'

   104 

   105     def __init__(self, model, where=WhereNode):

   106         self.model = model

   107         self.alias_refcount = {}

   108         self.alias_map = {}     # Maps alias to join information

   109         self.table_map = {}     # Maps table names to list of aliases.

   110         self.join_map = {}

   111         self.rev_join_map = {}  # Reverse of join_map.

   112         self.quote_cache = {}

   113         self.default_cols = True

   114         self.default_ordering = True

   115         self.standard_ordering = True

   116         self.ordering_aliases = []

   117         self.select_fields = []

   118         self.related_select_fields = []

   119         self.dupe_avoidance = {}

   120         self.used_aliases = set()

   121         self.filter_is_sticky = False

   122         self.included_inherited_models = {}

   123 

   124         # SQL-related attributes

   125         self.select = []

   126         self.tables = []    # Aliases in the order they are created.

   127         self.where = where()

   128         self.where_class = where

   129         self.group_by = None

   130         self.having = where()

   131         self.order_by = []

   132         self.low_mark, self.high_mark = 0, None  # Used for offset/limit

   133         self.distinct = False

   134         self.select_related = False

   135         self.related_select_cols = []

   136 

   137         # SQL aggregate-related attributes

   138         self.aggregates = SortedDict() # Maps alias -> SQL aggregate function

   139         self.aggregate_select_mask = None

   140         self._aggregate_select_cache = None

   141 

   142         # Arbitrary maximum limit for select_related. Prevents infinite

   143         # recursion. Can be changed by the depth parameter to select_related().

   144         self.max_depth = 5

   145 

   146         # These are for extensions. The contents are more or less appended

   147         # verbatim to the appropriate clause.

   148         self.extra = SortedDict()  # Maps col_alias -> (col_sql, params).

   149         self.extra_select_mask = None

   150         self._extra_select_cache = None

   151 

   152         self.extra_tables = ()

   153         self.extra_order_by = ()

   154 

   155         # A tuple that is a set of model field names and either True, if these

   156         # are the fields to defer, or False if these are the only fields to

   157         # load.

   158         self.deferred_loading = (set(), True)

   159 

   160     def __str__(self):

   161         """

   162         Returns the query as a string of SQL with the parameter values

   163         substituted in.

   164 

   165         Parameter values won't necessarily be quoted correctly, since that is

   166         done by the database interface at execution time.

   167         """

   168         sql, params = self.get_compiler(DEFAULT_DB_ALIAS).as_sql()

   169         return sql % params

   170 

   171     def __deepcopy__(self, memo):

   172         result = self.clone(memo=memo)

   173         memo[id(self)] = result

   174         return result

   175 

   176     def __getstate__(self):

   177         """

   178         Pickling support.

   179         """

   180         obj_dict = self.__dict__.copy()

   181         obj_dict['related_select_fields'] = []

   182         obj_dict['related_select_cols'] = []

   183 

   184         # Fields can't be pickled, so if a field list has been

   185         # specified, we pickle the list of field names instead.

   186         # None is also a possible value; that can pass as-is

   187         obj_dict['select_fields'] = [

   188             f is not None and f.name or None

   189             for f in obj_dict['select_fields']

   190         ]

   191         return obj_dict

   192 

   193     def __setstate__(self, obj_dict):

   194         """

   195         Unpickling support.

   196         """

   197         # Rebuild list of field instances

   198         obj_dict['select_fields'] = [

   199             name is not None and obj_dict['model']._meta.get_field(name) or None

   200             for name in obj_dict['select_fields']

   201         ]

   202 

   203         self.__dict__.update(obj_dict)

   204 

   205     def prepare(self):

   206         return self

   207 

   208     def get_compiler(self, using=None, connection=None):

   209         if using is None and connection is None:

   210             raise ValueError("Need either using or connection")

   211         if using:

   212             connection = connections[using]

   213 

   214         # Check that the compiler will be able to execute the query

   215         for alias, aggregate in self.aggregate_select.items():

   216             connection.ops.check_aggregate_support(aggregate)

   217 

   218         return connection.ops.compiler(self.compiler)(self, connection, using)

   219 

   220     def get_meta(self):

   221         """

   222         Returns the Options instance (the model._meta) from which to start

   223         processing. Normally, this is self.model._meta, but it can be changed

   224         by subclasses.

   225         """

   226         return self.model._meta

   227 

   228     def clone(self, klass=None, memo=None, **kwargs):

   229         """

   230         Creates a copy of the current instance. The 'kwargs' parameter can be

   231         used by clients to update attributes after copying has taken place.

   232         """

   233         obj = Empty()

   234         obj.__class__ = klass or self.__class__

   235         obj.model = self.model

   236         obj.alias_refcount = self.alias_refcount.copy()

   237         obj.alias_map = self.alias_map.copy()

   238         obj.table_map = self.table_map.copy()

   239         obj.join_map = self.join_map.copy()

   240         obj.rev_join_map = self.rev_join_map.copy()

   241         obj.quote_cache = {}

   242         obj.default_cols = self.default_cols

   243         obj.default_ordering = self.default_ordering

   244         obj.standard_ordering = self.standard_ordering

   245         obj.included_inherited_models = self.included_inherited_models.copy()

   246         obj.ordering_aliases = []

   247         obj.select_fields = self.select_fields[:]

   248         obj.related_select_fields = self.related_select_fields[:]

   249         obj.dupe_avoidance = self.dupe_avoidance.copy()

   250         obj.select = self.select[:]

   251         obj.tables = self.tables[:]

   252         obj.where = deepcopy(self.where, memo=memo)

   253         obj.where_class = self.where_class

   254         if self.group_by is None:

   255             obj.group_by = None

   256         else:

   257             obj.group_by = self.group_by[:]

   258         obj.having = deepcopy(self.having, memo=memo)

   259         obj.order_by = self.order_by[:]

   260         obj.low_mark, obj.high_mark = self.low_mark, self.high_mark

   261         obj.distinct = self.distinct

   262         obj.select_related = self.select_related

   263         obj.related_select_cols = []

   264         obj.aggregates = deepcopy(self.aggregates, memo=memo)

   265         if self.aggregate_select_mask is None:

   266             obj.aggregate_select_mask = None

   267         else:

   268             obj.aggregate_select_mask = self.aggregate_select_mask.copy()

   269         # _aggregate_select_cache cannot be copied, as doing so breaks the

   270         # (necessary) state in which both aggregates and

   271         # _aggregate_select_cache point to the same underlying objects.

   272         # It will get re-populated in the cloned queryset the next time it's

   273         # used.

   274         obj._aggregate_select_cache = None

   275         obj.max_depth = self.max_depth

   276         obj.extra = self.extra.copy()

   277         if self.extra_select_mask is None:

   278             obj.extra_select_mask = None

   279         else:

   280             obj.extra_select_mask = self.extra_select_mask.copy()

   281         if self._extra_select_cache is None:

   282             obj._extra_select_cache = None

   283         else:

   284             obj._extra_select_cache = self._extra_select_cache.copy()

   285         obj.extra_tables = self.extra_tables

   286         obj.extra_order_by = self.extra_order_by

   287         obj.deferred_loading = deepcopy(self.deferred_loading, memo=memo)

   288         if self.filter_is_sticky and self.used_aliases:

   289             obj.used_aliases = self.used_aliases.copy()

   290         else:

   291             obj.used_aliases = set()

   292         obj.filter_is_sticky = False

   293         obj.__dict__.update(kwargs)

   294         if hasattr(obj, '_setup_query'):

   295             obj._setup_query()

   296         return obj

   297 

   298     def convert_values(self, value, field, connection):

   299         """Convert the database-returned value into a type that is consistent

   300         across database backends.

   301 

   302         By default, this defers to the underlying backend operations, but

   303         it can be overridden by Query classes for specific backends.

   304         """

   305         return connection.ops.convert_values(value, field)

   306 

   307     def resolve_aggregate(self, value, aggregate, connection):

   308         """Resolve the value of aggregates returned by the database to

   309         consistent (and reasonable) types.

   310 

   311         This is required because of the predisposition of certain backends

   312         to return Decimal and long types when they are not needed.

   313         """

   314         if value is None:

   315             if aggregate.is_ordinal:

   316                 return 0

   317             # Return None as-is

   318             return value

   319         elif aggregate.is_ordinal:

   320             # Any ordinal aggregate (e.g., count) returns an int

   321             return int(value)

   322         elif aggregate.is_computed:

   323             # Any computed aggregate (e.g., avg) returns a float

   324             return float(value)

   325         else:

   326             # Return value depends on the type of the field being processed.

   327             return self.convert_values(value, aggregate.field, connection)

   328 

   329     def get_aggregation(self, using):

   330         """

   331         Returns the dictionary with the values of the existing aggregations.

   332         """

   333         if not self.aggregate_select:

   334             return {}

   335 

   336         # If there is a group by clause, aggregating does not add useful

   337         # information but retrieves only the first row. Aggregate

   338         # over the subquery instead.

   339         if self.group_by is not None:

   340             from subqueries import AggregateQuery

   341             query = AggregateQuery(self.model)

   342 

   343             obj = self.clone()

   344 

   345             # Remove any aggregates marked for reduction from the subquery

   346             # and move them to the outer AggregateQuery.

   347             for alias, aggregate in self.aggregate_select.items():

   348                 if aggregate.is_summary:

   349                     query.aggregate_select[alias] = aggregate

   350                     del obj.aggregate_select[alias]

   351 

   352             query.add_subquery(obj, using)

   353         else:

   354             query = self

   355             self.select = []

   356             self.default_cols = False

   357             self.extra = {}

   358             self.remove_inherited_models()

   359 

   360         query.clear_ordering(True)

   361         query.clear_limits()

   362         query.select_related = False

   363         query.related_select_cols = []

   364         query.related_select_fields = []

   365 

   366         result = query.get_compiler(using).execute_sql(SINGLE)

   367         if result is None:

   368             result = [None for q in query.aggregate_select.items()]

   369 

   370         return dict([

   371             (alias, self.resolve_aggregate(val, aggregate, connection=connections[using]))

   372             for (alias, aggregate), val

   373             in zip(query.aggregate_select.items(), result)

   374         ])

   375 

   376     def get_count(self, using):

   377         """

   378         Performs a COUNT() query using the current filter constraints.

   379         """

   380         obj = self.clone()

   381         if len(self.select) > 1 or self.aggregate_select:

   382             # If a select clause exists, then the query has already started to

   383             # specify the columns that are to be returned.

   384             # In this case, we need to use a subquery to evaluate the count.

   385             from subqueries import AggregateQuery

   386             subquery = obj

   387             subquery.clear_ordering(True)

   388             subquery.clear_limits()

   389 

   390             obj = AggregateQuery(obj.model)

   391             obj.add_subquery(subquery, using=using)

   392 

   393         obj.add_count_column()

   394         number = obj.get_aggregation(using=using)[None]

   395 

   396         # Apply offset and limit constraints manually, since using LIMIT/OFFSET

   397         # in SQL (in variants that provide them) doesn't change the COUNT

   398         # output.

   399         number = max(0, number - self.low_mark)

   400         if self.high_mark is not None:

   401             number = min(number, self.high_mark - self.low_mark)

   402 

   403         return number

   404 

   405     def has_results(self, using):

   406         q = self.clone()

   407         q.add_extra({'a': 1}, None, None, None, None, None)

   408         q.select = []

   409         q.select_fields = []

   410         q.default_cols = False

   411         q.select_related = False

   412         q.set_extra_mask(('a',))

   413         q.set_aggregate_mask(())

   414         q.clear_ordering(True)

   415         q.set_limits(high=1)

   416         compiler = q.get_compiler(using=using)

   417         return bool(compiler.execute_sql(SINGLE))

   418 

   419     def combine(self, rhs, connector):

   420         """

   421         Merge the 'rhs' query into the current one (with any 'rhs' effects

   422         being applied *after* (that is, "to the right of") anything in the

   423         current query. 'rhs' is not modified during a call to this function.

   424 

   425         The 'connector' parameter describes how to connect filters from the

   426         'rhs' query.

   427         """

   428         assert self.model == rhs.model, \

   429                 "Cannot combine queries on two different base models."

   430         assert self.can_filter(), \

   431                 "Cannot combine queries once a slice has been taken."

   432         assert self.distinct == rhs.distinct, \

   433             "Cannot combine a unique query with a non-unique query."

   434 

   435         self.remove_inherited_models()

   436         # Work out how to relabel the rhs aliases, if necessary.

   437         change_map = {}

   438         used = set()

   439         conjunction = (connector == AND)

   440         first = True

   441         for alias in rhs.tables:

   442             if not rhs.alias_refcount[alias]:

   443                 # An unused alias.

   444                 continue

   445             promote = (rhs.alias_map[alias][JOIN_TYPE] == self.LOUTER)

   446             new_alias = self.join(rhs.rev_join_map[alias],

   447                     (conjunction and not first), used, promote, not conjunction)

   448             used.add(new_alias)

   449             change_map[alias] = new_alias

   450             first = False

   451 

   452         # So that we don't exclude valid results in an "or" query combination,

   453         # the first join that is exclusive to the lhs (self) must be converted

   454         # to an outer join.

   455         if not conjunction:

   456             for alias in self.tables[1:]:

   457                 if self.alias_refcount[alias] == 1:

   458                     self.promote_alias(alias, True)

   459                     break

   460 

   461         # Now relabel a copy of the rhs where-clause and add it to the current

   462         # one.

   463         if rhs.where:

   464             w = deepcopy(rhs.where)

   465             w.relabel_aliases(change_map)

   466             if not self.where:

   467                 # Since 'self' matches everything, add an explicit "include

   468                 # everything" where-constraint so that connections between the

   469                 # where clauses won't exclude valid results.

   470                 self.where.add(EverythingNode(), AND)

   471         elif self.where:

   472             # rhs has an empty where clause.

   473             w = self.where_class()

   474             w.add(EverythingNode(), AND)

   475         else:

   476             w = self.where_class()

   477         self.where.add(w, connector)

   478 

   479         # Selection columns and extra extensions are those provided by 'rhs'.

   480         self.select = []

   481         for col in rhs.select:

   482             if isinstance(col, (list, tuple)):

   483                 self.select.append((change_map.get(col[0], col[0]), col[1]))

   484             else:

   485                 item = deepcopy(col)

   486                 item.relabel_aliases(change_map)

   487                 self.select.append(item)

   488         self.select_fields = rhs.select_fields[:]

   489 

   490         if connector == OR:

   491             # It would be nice to be able to handle this, but the queries don't

   492             # really make sense (or return consistent value sets). Not worth

   493             # the extra complexity when you can write a real query instead.

   494             if self.extra and rhs.extra:

   495                 raise ValueError("When merging querysets using 'or', you "

   496                         "cannot have extra(select=...) on both sides.")

   497         self.extra.update(rhs.extra)

   498         extra_select_mask = set()

   499         if self.extra_select_mask is not None:

   500             extra_select_mask.update(self.extra_select_mask)

   501         if rhs.extra_select_mask is not None:

   502             extra_select_mask.update(rhs.extra_select_mask)

   503         if extra_select_mask:

   504             self.set_extra_mask(extra_select_mask)

   505         self.extra_tables += rhs.extra_tables

   506 

   507         # Ordering uses the 'rhs' ordering, unless it has none, in which case

   508         # the current ordering is used.

   509         self.order_by = rhs.order_by and rhs.order_by[:] or self.order_by

   510         self.extra_order_by = rhs.extra_order_by or self.extra_order_by

   511 

   512     def deferred_to_data(self, target, callback):

   513         """

   514         Converts the self.deferred_loading data structure to an alternate data

   515         structure, describing the field that *will* be loaded. This is used to

   516         compute the columns to select from the database and also by the

   517         QuerySet class to work out which fields are being initialised on each

   518         model. Models that have all their fields included aren't mentioned in

   519         the result, only those that have field restrictions in place.

   520 

   521         The "target" parameter is the instance that is populated (in place).

   522         The "callback" is a function that is called whenever a (model, field)

   523         pair need to be added to "target". It accepts three parameters:

   524         "target", and the model and list of fields being added for that model.

   525         """

   526         field_names, defer = self.deferred_loading

   527         if not field_names:

   528             return

   529         columns = set()

   530         orig_opts = self.model._meta

   531         seen = {}

   532         must_include = {self.model: set([orig_opts.pk])}

   533         for field_name in field_names:

   534             parts = field_name.split(LOOKUP_SEP)

   535             cur_model = self.model

   536             opts = orig_opts

   537             for name in parts[:-1]:

   538                 old_model = cur_model

   539                 source = opts.get_field_by_name(name)[0]

   540                 cur_model = opts.get_field_by_name(name)[0].rel.to

   541                 opts = cur_model._meta

   542                 # Even if we're "just passing through" this model, we must add

   543                 # both the current model's pk and the related reference field

   544                 # to the things we select.

   545                 must_include[old_model].add(source)

   546                 add_to_dict(must_include, cur_model, opts.pk)

   547             field, model, _, _ = opts.get_field_by_name(parts[-1])

   548             if model is None:

   549                 model = cur_model

   550             add_to_dict(seen, model, field)

   551 

   552         if defer:

   553             # We need to load all fields for each model, except those that

   554             # appear in "seen" (for all models that appear in "seen"). The only

   555             # slight complexity here is handling fields that exist on parent

   556             # models.

   557             workset = {}

   558             for model, values in seen.iteritems():

   559                 for field, m in model._meta.get_fields_with_model():

   560                     if field in values:

   561                         continue

   562                     add_to_dict(workset, m or model, field)

   563             for model, values in must_include.iteritems():

   564                 # If we haven't included a model in workset, we don't add the

   565                 # corresponding must_include fields for that model, since an

   566                 # empty set means "include all fields". That's why there's no

   567                 # "else" branch here.

   568                 if model in workset:

   569                     workset[model].update(values)

   570             for model, values in workset.iteritems():

   571                 callback(target, model, values)

   572         else:

   573             for model, values in must_include.iteritems():

   574                 if model in seen:

   575                     seen[model].update(values)

   576                 else:

   577                     # As we've passed through this model, but not explicitly

   578                     # included any fields, we have to make sure it's mentioned

   579                     # so that only the "must include" fields are pulled in.

   580                     seen[model] = values

   581             # Now ensure that every model in the inheritance chain is mentioned

   582             # in the parent list. Again, it must be mentioned to ensure that

   583             # only "must include" fields are pulled in.

   584             for model in orig_opts.get_parent_list():

   585                 if model not in seen:

   586                     seen[model] = set()

   587             for model, values in seen.iteritems():

   588                 callback(target, model, values)

   589 

   590 

   591     def deferred_to_columns_cb(self, target, model, fields):

   592         """

   593         Callback used by deferred_to_columns(). The "target" parameter should

   594         be a set instance.

   595         """

   596         table = model._meta.db_table

   597         if table not in target:

   598             target[table] = set()

   599         for field in fields:

   600             target[table].add(field.column)

   601 

   602 

   603     def table_alias(self, table_name, create=False):

   604         """

   605         Returns a table alias for the given table_name and whether this is a

   606         new alias or not.

   607 

   608         If 'create' is true, a new alias is always created. Otherwise, the

   609         most recently created alias for the table (if one exists) is reused.

   610         """

   611         current = self.table_map.get(table_name)

   612         if not create and current:

   613             alias = current[0]

   614             self.alias_refcount[alias] += 1

   615             return alias, False

   616 

   617         # Create a new alias for this table.

   618         if current:

   619             alias = '%s%d' % (self.alias_prefix, len(self.alias_map) + 1)

   620             current.append(alias)

   621         else:

   622             # The first occurence of a table uses the table name directly.

   623             alias = table_name

   624             self.table_map[alias] = [alias]

   625         self.alias_refcount[alias] = 1

   626         self.tables.append(alias)

   627         return alias, True

   628 

   629     def ref_alias(self, alias):

   630         """ Increases the reference count for this alias. """

   631         self.alias_refcount[alias] += 1

   632 

   633     def unref_alias(self, alias):

   634         """ Decreases the reference count for this alias. """

   635         self.alias_refcount[alias] -= 1

   636 

   637     def promote_alias(self, alias, unconditional=False):

   638         """

   639         Promotes the join type of an alias to an outer join if it's possible

   640         for the join to contain NULL values on the left. If 'unconditional' is

   641         False, the join is only promoted if it is nullable, otherwise it is

   642         always promoted.

   643 

   644         Returns True if the join was promoted.

   645         """

   646         if ((unconditional or self.alias_map[alias][NULLABLE]) and

   647                 self.alias_map[alias][JOIN_TYPE] != self.LOUTER):

   648             data = list(self.alias_map[alias])

   649             data[JOIN_TYPE] = self.LOUTER

   650             self.alias_map[alias] = tuple(data)

   651             return True

   652         return False

   653 

   654     def promote_alias_chain(self, chain, must_promote=False):

   655         """

   656         Walks along a chain of aliases, promoting the first nullable join and

   657         any joins following that. If 'must_promote' is True, all the aliases in

   658         the chain are promoted.

   659         """

   660         for alias in chain:

   661             if self.promote_alias(alias, must_promote):

   662                 must_promote = True

   663 

   664     def promote_unused_aliases(self, initial_refcounts, used_aliases):

   665         """

   666         Given a "before" copy of the alias_refcounts dictionary (as

   667         'initial_refcounts') and a collection of aliases that may have been

   668         changed or created, works out which aliases have been created since

   669         then and which ones haven't been used and promotes all of those

   670         aliases, plus any children of theirs in the alias tree, to outer joins.

   671         """

   672         # FIXME: There's some (a lot of!) overlap with the similar OR promotion

   673         # in add_filter(). It's not quite identical, but is very similar. So

   674         # pulling out the common bits is something for later.

   675         considered = {}

   676         for alias in self.tables:

   677             if alias not in used_aliases:

   678                 continue

   679             if (alias not in initial_refcounts or

   680                     self.alias_refcount[alias] == initial_refcounts[alias]):

   681                 parent = self.alias_map[alias][LHS_ALIAS]

   682                 must_promote = considered.get(parent, False)

   683                 promoted = self.promote_alias(alias, must_promote)

   684                 considered[alias] = must_promote or promoted

   685 

   686     def change_aliases(self, change_map):

   687         """

   688         Changes the aliases in change_map (which maps old-alias -> new-alias),

   689         relabelling any references to them in select columns and the where

   690         clause.

   691         """

   692         assert set(change_map.keys()).intersection(set(change_map.values())) == set()

   693 

   694         # 1. Update references in "select" (normal columns plus aliases),

   695         # "group by", "where" and "having".

   696         self.where.relabel_aliases(change_map)

   697         self.having.relabel_aliases(change_map)

   698         for columns in (self.select, self.aggregates.values(), self.group_by or []):

   699             for pos, col in enumerate(columns):

   700                 if isinstance(col, (list, tuple)):

   701                     old_alias = col[0]

   702                     columns[pos] = (change_map.get(old_alias, old_alias), col[1])

   703                 else:

   704                     col.relabel_aliases(change_map)

   705 

   706         # 2. Rename the alias in the internal table/alias datastructures.

   707         for old_alias, new_alias in change_map.iteritems():

   708             alias_data = list(self.alias_map[old_alias])

   709             alias_data[RHS_ALIAS] = new_alias

   710 

   711             t = self.rev_join_map[old_alias]

   712             data = list(self.join_map[t])

   713             data[data.index(old_alias)] = new_alias

   714             self.join_map[t] = tuple(data)

   715             self.rev_join_map[new_alias] = t

   716             del self.rev_join_map[old_alias]

   717             self.alias_refcount[new_alias] = self.alias_refcount[old_alias]

   718             del self.alias_refcount[old_alias]

   719             self.alias_map[new_alias] = tuple(alias_data)

   720             del self.alias_map[old_alias]

   721 

   722             table_aliases = self.table_map[alias_data[TABLE_NAME]]

   723             for pos, alias in enumerate(table_aliases):

   724                 if alias == old_alias:

   725                     table_aliases[pos] = new_alias

   726                     break

   727             for pos, alias in enumerate(self.tables):

   728                 if alias == old_alias:

   729                     self.tables[pos] = new_alias

   730                     break

   731         for key, alias in self.included_inherited_models.items():

   732             if alias in change_map:

   733                 self.included_inherited_models[key] = change_map[alias]

   734 

   735         # 3. Update any joins that refer to the old alias.

   736         for alias, data in self.alias_map.iteritems():

   737             lhs = data[LHS_ALIAS]

   738             if lhs in change_map:

   739                 data = list(data)

   740                 data[LHS_ALIAS] = change_map[lhs]

   741                 self.alias_map[alias] = tuple(data)

   742 

   743     def bump_prefix(self, exceptions=()):

   744         """

   745         Changes the alias prefix to the next letter in the alphabet and

   746         relabels all the aliases. Even tables that previously had no alias will

   747         get an alias after this call (it's mostly used for nested queries and

   748         the outer query will already be using the non-aliased table name).

   749 

   750         Subclasses who create their own prefix should override this method to

   751         produce a similar result (a new prefix and relabelled aliases).

   752 

   753         The 'exceptions' parameter is a container that holds alias names which

   754         should not be changed.

   755         """

   756         current = ord(self.alias_prefix)

   757         assert current < ord('Z')

   758         prefix = chr(current + 1)

   759         self.alias_prefix = prefix

   760         change_map = {}

   761         for pos, alias in enumerate(self.tables):

   762             if alias in exceptions:

   763                 continue

   764             new_alias = '%s%d' % (prefix, pos)

   765             change_map[alias] = new_alias

   766             self.tables[pos] = new_alias

   767         self.change_aliases(change_map)

   768 

   769     def get_initial_alias(self):

   770         """

   771         Returns the first alias for this query, after increasing its reference

   772         count.

   773         """

   774         if self.tables:

   775             alias = self.tables[0]

   776             self.ref_alias(alias)

   777         else:

   778             alias = self.join((None, self.model._meta.db_table, None, None))

   779         return alias

   780 

   781     def count_active_tables(self):

   782         """

   783         Returns the number of tables in this query with a non-zero reference

   784         count.

   785         """

   786         return len([1 for count in self.alias_refcount.itervalues() if count])

   787 

   788     def join(self, connection, always_create=False, exclusions=(),

   789             promote=False, outer_if_first=False, nullable=False, reuse=None):

   790         """

   791         Returns an alias for the join in 'connection', either reusing an

   792         existing alias for that join or creating a new one. 'connection' is a

   793         tuple (lhs, table, lhs_col, col) where 'lhs' is either an existing

   794         table alias or a table name. The join correspods to the SQL equivalent

   795         of::

   796 

   797             lhs.lhs_col = table.col

   798 

   799         If 'always_create' is True and 'reuse' is None, a new alias is always

   800         created, regardless of whether one already exists or not. If

   801         'always_create' is True and 'reuse' is a set, an alias in 'reuse' that

   802         matches the connection will be returned, if possible.  If

   803         'always_create' is False, the first existing alias that matches the

   804         'connection' is returned, if any. Otherwise a new join is created.

   805 

   806         If 'exclusions' is specified, it is something satisfying the container

   807         protocol ("foo in exclusions" must work) and specifies a list of

   808         aliases that should not be returned, even if they satisfy the join.

   809 

   810         If 'promote' is True, the join type for the alias will be LOUTER (if

   811         the alias previously existed, the join type will be promoted from INNER

   812         to LOUTER, if necessary).

   813 

   814         If 'outer_if_first' is True and a new join is created, it will have the

   815         LOUTER join type. This is used when joining certain types of querysets

   816         and Q-objects together.

   817 

   818         If 'nullable' is True, the join can potentially involve NULL values and

   819         is a candidate for promotion (to "left outer") when combining querysets.

   820         """

   821         lhs, table, lhs_col, col = connection

   822         if lhs in self.alias_map:

   823             lhs_table = self.alias_map[lhs][TABLE_NAME]

   824         else:

   825             lhs_table = lhs

   826 

   827         if reuse and always_create and table in self.table_map:

   828             # Convert the 'reuse' to case to be "exclude everything but the

   829             # reusable set, minus exclusions, for this table".

   830             exclusions = set(self.table_map[table]).difference(reuse).union(set(exclusions))

   831             always_create = False

   832         t_ident = (lhs_table, table, lhs_col, col)

   833         if not always_create:

   834             for alias in self.join_map.get(t_ident, ()):

   835                 if alias not in exclusions:

   836                     if lhs_table and not self.alias_refcount[self.alias_map[alias][LHS_ALIAS]]:

   837                         # The LHS of this join tuple is no longer part of the

   838                         # query, so skip this possibility.

   839                         continue

   840                     if self.alias_map[alias][LHS_ALIAS] != lhs:

   841                         continue

   842                     self.ref_alias(alias)

   843                     if promote:

   844                         self.promote_alias(alias)

   845                     return alias

   846 

   847         # No reuse is possible, so we need a new alias.

   848         alias, _ = self.table_alias(table, True)

   849         if not lhs:

   850             # Not all tables need to be joined to anything. No join type

   851             # means the later columns are ignored.

   852             join_type = None

   853         elif promote or outer_if_first:

   854             join_type = self.LOUTER

   855         else:

   856             join_type = self.INNER

   857         join = (table, alias, join_type, lhs, lhs_col, col, nullable)

   858         self.alias_map[alias] = join

   859         if t_ident in self.join_map:

   860             self.join_map[t_ident] += (alias,)

   861         else:

   862             self.join_map[t_ident] = (alias,)

   863         self.rev_join_map[alias] = t_ident

   864         return alias

   865 

   866     def setup_inherited_models(self):

   867         """

   868         If the model that is the basis for this QuerySet inherits other models,

   869         we need to ensure that those other models have their tables included in

   870         the query.

   871 

   872         We do this as a separate step so that subclasses know which

   873         tables are going to be active in the query, without needing to compute

   874         all the select columns (this method is called from pre_sql_setup(),

   875         whereas column determination is a later part, and side-effect, of

   876         as_sql()).

   877         """

   878         opts = self.model._meta

   879         root_alias = self.tables[0]

   880         seen = {None: root_alias}

   881 

   882         # Skip all proxy to the root proxied model

   883         proxied_model = get_proxied_model(opts)

   884 

   885         for field, model in opts.get_fields_with_model():

   886             if model not in seen:

   887                 if model is proxied_model:

   888                     seen[model] = root_alias

   889                 else:

   890                     link_field = opts.get_ancestor_link(model)

   891                     seen[model] = self.join((root_alias, model._meta.db_table,

   892                             link_field.column, model._meta.pk.column))

   893         self.included_inherited_models = seen

   894 

   895     def remove_inherited_models(self):

   896         """

   897         Undoes the effects of setup_inherited_models(). Should be called

   898         whenever select columns (self.select) are set explicitly.

   899         """

   900         for key, alias in self.included_inherited_models.items():

   901             if key:

   902                 self.unref_alias(alias)

   903         self.included_inherited_models = {}

   904 

   905 

   906     def add_aggregate(self, aggregate, model, alias, is_summary):

   907         """

   908         Adds a single aggregate expression to the Query

   909         """

   910         opts = model._meta

   911         field_list = aggregate.lookup.split(LOOKUP_SEP)

   912         if (len(field_list) == 1 and

   913             aggregate.lookup in self.aggregates.keys()):

   914             # Aggregate is over an annotation

   915             field_name = field_list[0]

   916             col = field_name

   917             source = self.aggregates[field_name]

   918             if not is_summary:

   919                 raise FieldError("Cannot compute %s('%s'): '%s' is an aggregate" % (

   920                     aggregate.name, field_name, field_name))

   921         elif ((len(field_list) > 1) or

   922             (field_list[0] not in [i.name for i in opts.fields]) or

   923             self.group_by is None or

   924             not is_summary):

   925             # If:

   926             #   - the field descriptor has more than one part (foo__bar), or

   927             #   - the field descriptor is referencing an m2m/m2o field, or

   928             #   - this is a reference to a model field (possibly inherited), or

   929             #   - this is an annotation over a model field

   930             # then we need to explore the joins that are required.

   931 

   932             field, source, opts, join_list, last, _ = self.setup_joins(

   933                 field_list, opts, self.get_initial_alias(), False)

   934 

   935             # Process the join chain to see if it can be trimmed

   936             col, _, join_list = self.trim_joins(source, join_list, last, False)

   937 

   938             # If the aggregate references a model or field that requires a join,

   939             # those joins must be LEFT OUTER - empty join rows must be returned

   940             # in order for zeros to be returned for those aggregates.

   941             for column_alias in join_list:

   942                 self.promote_alias(column_alias, unconditional=True)

   943 

   944             col = (join_list[-1], col)

   945         else:

   946             # The simplest cases. No joins required -

   947             # just reference the provided column alias.

   948             field_name = field_list[0]

   949             source = opts.get_field(field_name)

   950             col = field_name

   951 

   952         # Add the aggregate to the query

   953         aggregate.add_to_query(self, alias, col=col, source=source, is_summary=is_summary)

   954 

   955     def add_filter(self, filter_expr, connector=AND, negate=False, trim=False,

   956             can_reuse=None, process_extras=True):

   957         """

   958         Add a single filter to the query. The 'filter_expr' is a pair:

   959         (filter_string, value). E.g. ('name__contains', 'fred')

   960 

   961         If 'negate' is True, this is an exclude() filter. It's important to

   962         note that this method does not negate anything in the where-clause

   963         object when inserting the filter constraints. This is because negated

   964         filters often require multiple calls to add_filter() and the negation

   965         should only happen once. So the caller is responsible for this (the

   966         caller will normally be add_q(), so that as an example).

   967 

   968         If 'trim' is True, we automatically trim the final join group (used

   969         internally when constructing nested queries).

   970 

   971         If 'can_reuse' is a set, we are processing a component of a

   972         multi-component filter (e.g. filter(Q1, Q2)). In this case, 'can_reuse'

   973         will be a set of table aliases that can be reused in this filter, even

   974         if we would otherwise force the creation of new aliases for a join

   975         (needed for nested Q-filters). The set is updated by this method.

   976 

   977         If 'process_extras' is set, any extra filters returned from the table

   978         joining process will be processed. This parameter is set to False

   979         during the processing of extra filters to avoid infinite recursion.

   980         """

   981         arg, value = filter_expr

   982         parts = arg.split(LOOKUP_SEP)

   983         if not parts:

   984             raise FieldError("Cannot parse keyword query %r" % arg)

   985 

   986         # Work out the lookup type and remove it from 'parts', if necessary.

   987         if len(parts) == 1 or parts[-1] not in self.query_terms:

   988             lookup_type = 'exact'

   989         else:

   990             lookup_type = parts.pop()

   991 

   992         # By default, this is a WHERE clause. If an aggregate is referenced

   993         # in the value, the filter will be promoted to a HAVING

   994         having_clause = False

   995 

   996         # Interpret '__exact=None' as the sql 'is NULL'; otherwise, reject all

   997         # uses of None as a query value.

   998         if value is None:

   999             if lookup_type != 'exact':

  1000                 raise ValueError("Cannot use None as a query value")

  1001             lookup_type = 'isnull'

  1002             value = True

  1003         elif callable(value):

  1004             value = value()

  1005         elif hasattr(value, 'evaluate'):

  1006             # If value is a query expression, evaluate it

  1007             value = SQLEvaluator(value, self)

  1008             having_clause = value.contains_aggregate

  1009 

  1010         for alias, aggregate in self.aggregates.items():

  1011             if alias == parts[0]:

  1012                 entry = self.where_class()

  1013                 entry.add((aggregate, lookup_type, value), AND)

  1014                 if negate:

  1015                     entry.negate()

  1016                 self.having.add(entry, AND)

  1017                 return

  1018 

  1019         opts = self.get_meta()

  1020         alias = self.get_initial_alias()

  1021         allow_many = trim or not negate

  1022 

  1023         try:

  1024             field, target, opts, join_list, last, extra_filters = self.setup_joins(

  1025                     parts, opts, alias, True, allow_many, can_reuse=can_reuse,

  1026                     negate=negate, process_extras=process_extras)

  1027         except MultiJoin, e:

  1028             self.split_exclude(filter_expr, LOOKUP_SEP.join(parts[:e.level]),

  1029                     can_reuse)

  1030             return

  1031 

  1032         if (lookup_type == 'isnull' and value is True and not negate and

  1033                 len(join_list) > 1):

  1034             # If the comparison is against NULL, we may need to use some left

  1035             # outer joins when creating the join chain. This is only done when

  1036             # needed, as it's less efficient at the database level.

  1037             self.promote_alias_chain(join_list)

  1038 

  1039         # Process the join list to see if we can remove any inner joins from

  1040         # the far end (fewer tables in a query is better).

  1041         col, alias, join_list = self.trim_joins(target, join_list, last, trim)

  1042 

  1043         if connector == OR:

  1044             # Some joins may need to be promoted when adding a new filter to a

  1045             # disjunction. We walk the list of new joins and where it diverges

  1046             # from any previous joins (ref count is 1 in the table list), we

  1047             # make the new additions (and any existing ones not used in the new

  1048             # join list) an outer join.

  1049             join_it = iter(join_list)

  1050             table_it = iter(self.tables)

  1051             join_it.next(), table_it.next()

  1052             table_promote = False

  1053             join_promote = False

  1054             for join in join_it:

  1055                 table = table_it.next()

  1056                 if join == table and self.alias_refcount[join] > 1:

  1057                     continue

  1058                 join_promote = self.promote_alias(join)

  1059                 if table != join:

  1060                     table_promote = self.promote_alias(table)

  1061                 break

  1062             self.promote_alias_chain(join_it, join_promote)

  1063             self.promote_alias_chain(table_it, table_promote)

  1064 

  1065 

  1066         if having_clause:

  1067             self.having.add((Constraint(alias, col, field), lookup_type, value),

  1068                 connector)

  1069         else:

  1070             self.where.add((Constraint(alias, col, field), lookup_type, value),

  1071                 connector)

  1072 

  1073         if negate:

  1074             self.promote_alias_chain(join_list)

  1075             if lookup_type != 'isnull':

  1076                 if len(join_list) > 1:

  1077                     for alias in join_list:

  1078                         if self.alias_map[alias][JOIN_TYPE] == self.LOUTER:

  1079                             j_col = self.alias_map[alias][RHS_JOIN_COL]

  1080                             entry = self.where_class()

  1081                             entry.add((Constraint(alias, j_col, None), 'isnull', True), AND)

  1082                             entry.negate()

  1083                             self.where.add(entry, AND)

  1084                             break

  1085                 elif not (lookup_type == 'in'

  1086                             and not hasattr(value, 'as_sql')

  1087                             and not hasattr(value, '_as_sql')

  1088                             and not value) and field.null:

  1089                     # Leaky abstraction artifact: We have to specifically

  1090                     # exclude the "foo__in=[]" case from this handling, because

  1091                     # it's short-circuited in the Where class.

  1092                     # We also need to handle the case where a subquery is provided

  1093                     entry = self.where_class()

  1094                     entry.add((Constraint(alias, col, None), 'isnull', True), AND)

  1095                     entry.negate()

  1096                     self.where.add(entry, AND)

  1097 

  1098         if can_reuse is not None:

  1099             can_reuse.update(join_list)

  1100         if process_extras:

  1101             for filter in extra_filters:

  1102                 self.add_filter(filter, negate=negate, can_reuse=can_reuse,

  1103                         process_extras=False)

  1104 

  1105     def add_q(self, q_object, used_aliases=None):

  1106         """

  1107         Adds a Q-object to the current filter.

  1108 

  1109         Can also be used to add anything that has an 'add_to_query()' method.

  1110         """

  1111         if used_aliases is None:

  1112             used_aliases = self.used_aliases

  1113         if hasattr(q_object, 'add_to_query'):

  1114             # Complex custom objects are responsible for adding themselves.

  1115             q_object.add_to_query(self, used_aliases)

  1116         else:

  1117             if self.where and q_object.connector != AND and len(q_object) > 1:

  1118                 self.where.start_subtree(AND)

  1119                 subtree = True

  1120             else:

  1121                 subtree = False

  1122             connector = AND

  1123             for child in q_object.children:

  1124                 if connector == OR:

  1125                     refcounts_before = self.alias_refcount.copy()

  1126                 self.where.start_subtree(connector)

  1127                 if isinstance(child, Node):

  1128                     self.add_q(child, used_aliases)

  1129                 else:

  1130                     self.add_filter(child, connector, q_object.negated,

  1131                             can_reuse=used_aliases)

  1132                 self.where.end_subtree()

  1133                 if connector == OR:

  1134                     # Aliases that were newly added or not used at all need to

  1135                     # be promoted to outer joins if they are nullable relations.

  1136                     # (they shouldn't turn the whole conditional into the empty