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 copy import deepcopy

    11 

    12 from django.utils.tree import Node

    13 from django.utils.datastructures import SortedDict

    14 from django.dispatch import dispatcher

    15 from django.db import connection

    16 from django.db.models import signals

    17 from django.db.models.sql.where import WhereNode, EverythingNode, AND, OR

    18 from django.db.models.sql.datastructures import Count

    19 from django.db.models.fields import FieldDoesNotExist

    20 from django.core.exceptions import FieldError

    21 from datastructures import EmptyResultSet, Empty, MultiJoin

    22 from constants import *

    23 

    24 try:

    25     set

    26 except NameError:

    27     from sets import Set as set     # Python 2.3 fallback

    28 

    29 __all__ = ['Query']

    30 

    31 class Query(object):

    32     """

    33     A single SQL query.

    34     """

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

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

    37     INNER = 'INNER JOIN'

    38     LOUTER = 'LEFT OUTER JOIN'

    39 

    40     alias_prefix = 'T'

    41     query_terms = QUERY_TERMS

    42 

    43     def __init__(self, model, connection, where=WhereNode):

    44         self.model = model

    45         self.connection = connection

    46         self.alias_refcount = {}

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

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

    49         self.join_map = {}

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

    51         self.quote_cache = {}

    52         self.default_cols = True

    53         self.default_ordering = True

    54         self.standard_ordering = True

    55         self.ordering_aliases = []

    56         self.start_meta = None

    57         self.select_fields = []

    58         self.related_select_fields = []

    59 

    60         # SQL-related attributes

    61         self.select = []

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

    63         self.where = where()

    64         self.where_class = where

    65         self.group_by = []

    66         self.having = []

    67         self.order_by = []

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

    69         self.distinct = False

    70         self.select_related = False

    71         self.related_select_cols = []

    72 

    73         # Arbitrary maximum limit for select_related. Prevents infinite

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

    75         self.max_depth = 5

    76 

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

    78         # verbatim to the appropriate clause.

    79         self.extra_select = {}  # Maps col_alias -> col_sql.

    80         self.extra_select_params = ()

    81         self.extra_tables = ()

    82         self.extra_where = ()

    83         self.extra_params = ()

    84         self.extra_order_by = ()

    85 

    86     def __str__(self):

    87         """

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

    89         substituted in.

    90 

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

    92         done by the database interface at execution time.

    93         """

    94         sql, params = self.as_sql()

    95         return sql % params

    96 

    97     def __deepcopy__(self, memo):

    98         result= self.clone()

    99         memo[id(self)] = result

   100         return result

   101 

   102     def __getstate__(self):

   103         """

   104         Pickling support.

   105         """

   106         obj_dict = self.__dict__.copy()

   107         del obj_dict['connection']

   108         return obj_dict

   109 

   110     def __setstate__(self, obj_dict):

   111         """

   112         Unpickling support.

   113         """

   114         self.__dict__.update(obj_dict)

   115         # XXX: Need a better solution for this when multi-db stuff is

   116         # supported. It's the only class-reference to the module-level

   117         # connection variable.

   118         self.connection = connection

   119 

   120     def get_meta(self):

   121         """

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

   123         processing. Normally, this is self.model._meta, but it can change.

   124         """

   125         if self.start_meta:

   126             return self.start_meta

   127         return self.model._meta

   128 

   129     def quote_name_unless_alias(self, name):

   130         """

   131         A wrapper around connection.ops.quote_name that doesn't quote aliases

   132         for table names. This avoids problems with some SQL dialects that treat

   133         quoted strings specially (e.g. PostgreSQL).

   134         """

   135         if name in self.quote_cache:

   136             return self.quote_cache[name]

   137         if ((name in self.alias_map and name not in self.table_map) or

   138                 name in self.extra_select):

   139             self.quote_cache[name] = name

   140             return name

   141         r = self.connection.ops.quote_name(name)

   142         self.quote_cache[name] = r

   143         return r

   144 

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

   146         """

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

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

   149         """

   150         obj = Empty()

   151         obj.__class__ = klass or self.__class__

   152         obj.model = self.model

   153         obj.connection = self.connection

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

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

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

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

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

   159         obj.quote_cache = {}

   160         obj.default_cols = self.default_cols

   161         obj.default_ordering = self.default_ordering

   162         obj.standard_ordering = self.standard_ordering

   163         obj.ordering_aliases = []

   164         obj.start_meta = self.start_meta

   165         obj.select_fields = self.select_fields[:]

   166         obj.related_select_fields = self.related_select_fields[:]

   167         obj.select = self.select[:]

   168         obj.tables = self.tables[:]

   169         obj.where = deepcopy(self.where)

   170         obj.where_class = self.where_class

   171         obj.group_by = self.group_by[:]

   172         obj.having = self.having[:]

   173         obj.order_by = self.order_by[:]

   174         obj.low_mark, obj.high_mark = self.low_mark, self.high_mark

   175         obj.distinct = self.distinct

   176         obj.select_related = self.select_related

   177         obj.related_select_cols = []

   178         obj.max_depth = self.max_depth

   179         obj.extra_select = self.extra_select.copy()

   180         obj.extra_select_params = self.extra_select_params

   181         obj.extra_tables = self.extra_tables

   182         obj.extra_where = self.extra_where

   183         obj.extra_params = self.extra_params

   184         obj.extra_order_by = self.extra_order_by

   185         obj.__dict__.update(kwargs)

   186         if hasattr(obj, '_setup_query'):

   187             obj._setup_query()

   188         return obj

   189 

   190     def results_iter(self):

   191         """

   192         Returns an iterator over the results from executing this query.

   193         """

   194         resolve_columns = hasattr(self, 'resolve_columns')

   195         if resolve_columns:

   196             if self.select_fields:

   197                 fields = self.select_fields + self.related_select_fields

   198             else:

   199                 fields = self.model._meta.fields

   200         for rows in self.execute_sql(MULTI):

   201             for row in rows:

   202                 if resolve_columns:

   203                     row = self.resolve_columns(row, fields)

   204                 yield row

   205 

   206     def get_count(self):

   207         """

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

   209         """

   210         from subqueries import CountQuery

   211         obj = self.clone()

   212         obj.clear_ordering(True)

   213         obj.clear_limits()

   214         obj.select_related = False

   215         obj.related_select_cols = []

   216         obj.related_select_fields = []

   217         if obj.distinct and len(obj.select) > 1:

   218             obj = self.clone(CountQuery, _query=obj, where=self.where_class(),

   219                     distinct=False)

   220             obj.select = []

   221             obj.extra_select = {}

   222         obj.add_count_column()

   223         data = obj.execute_sql(SINGLE)

   224         if not data:

   225             return 0

   226         number = data[0]

   227 

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

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

   230         # output.

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

   232         if self.high_mark:

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

   234 

   235         return number

   236 

   237     def as_sql(self, with_limits=True, with_col_aliases=False):

   238         """

   239         Creates the SQL for this query. Returns the SQL string and list of

   240         parameters.

   241 

   242         If 'with_limits' is False, any limit/offset information is not included

   243         in the query.

   244         """

   245         self.pre_sql_setup()

   246         out_cols = self.get_columns(with_col_aliases)

   247         ordering = self.get_ordering()

   248 

   249         # This must come after 'select' and 'ordering' -- see docstring of

   250         # get_from_clause() for details.

   251         from_, f_params = self.get_from_clause()

   252 

   253         where, w_params = self.where.as_sql(qn=self.quote_name_unless_alias)

   254         params = list(self.extra_select_params)

   255 

   256         result = ['SELECT']

   257         if self.distinct:

   258             result.append('DISTINCT')

   259         result.append(', '.join(out_cols + self.ordering_aliases))

   260 

   261         result.append('FROM')

   262         result.extend(from_)

   263         params.extend(f_params)

   264 

   265         if where:

   266             result.append('WHERE %s' % where)

   267             params.extend(w_params)

   268         if self.extra_where:

   269             if not where:

   270                 result.append('WHERE')

   271             else:

   272                 result.append('AND')

   273             result.append(' AND '.join(self.extra_where))

   274 

   275         if self.group_by:

   276             grouping = self.get_grouping()

   277             result.append('GROUP BY %s' % ', '.join(grouping))

   278 

   279         if ordering:

   280             result.append('ORDER BY %s' % ', '.join(ordering))

   281 

   282         # FIXME: Pull this out to make life easier for Oracle et al.

   283         if with_limits:

   284             if self.high_mark:

   285                 result.append('LIMIT %d' % (self.high_mark - self.low_mark))

   286             if self.low_mark:

   287                 if not self.high_mark:

   288                     val = self.connection.ops.no_limit_value()

   289                     if val:

   290                         result.append('LIMIT %d' % val)

   291                 result.append('OFFSET %d' % self.low_mark)

   292 

   293         params.extend(self.extra_params)

   294         return ' '.join(result), tuple(params)

   295 

   296     def combine(self, rhs, connector):

   297         """

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

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

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

   301 

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

   303         'rhs' query.

   304         """

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

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

   307         assert self.can_filter(), \

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

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

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

   311 

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

   313         change_map = {}

   314         used = set()

   315         conjunction = (connector == AND)

   316         first = True

   317         for alias in rhs.tables:

   318             if not rhs.alias_refcount[alias]:

   319                 # An unused alias.

   320                 continue

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

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

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

   324             used.add(new_alias)

   325             change_map[alias] = new_alias

   326             first = False

   327 

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

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

   330         # to an outer join.

   331         if not conjunction:

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

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

   334                     self.promote_alias(alias, True)

   335                     break

   336 

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

   338         # one.

   339         if rhs.where:

   340             w = deepcopy(rhs.where)

   341             w.relabel_aliases(change_map)

   342             if not self.where:

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

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

   345                 # where clauses won't exclude valid results.

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

   347         elif self.where:

   348             # rhs has an empty where clause.

   349             w = self.where_class()

   350             w.add(EverythingNode(), AND)

   351         else:

   352             w = self.where_class()

   353         self.where.add(w, connector)

   354 

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

   356         self.select = []

   357         for col in rhs.select:

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

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

   360             else:

   361                 item = deepcopy(col)

   362                 item.relabel_aliases(change_map)

   363                 self.select.append(item)

   364         self.select_fields = rhs.select_fields[:]

   365         self.extra_select = rhs.extra_select.copy()

   366         self.extra_tables = rhs.extra_tables

   367         self.extra_where = rhs.extra_where

   368         self.extra_params = rhs.extra_params

   369 

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

   371         # the current ordering is used.

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

   373         self.extra_order_by = rhs.extra_order_by or self.extra_order_by

   374 

   375     def pre_sql_setup(self):

   376         """

   377         Does any necessary class setup immediately prior to producing SQL. This

   378         is for things that can't necessarily be done in __init__ because we

   379         might not have all the pieces in place at that time.

   380         """

   381         if not self.tables:

   382             self.join((None, self.model._meta.db_table, None, None))

   383         if self.select_related and not self.related_select_cols:

   384             self.fill_related_selections()

   385 

   386     def get_columns(self, with_aliases=False):

   387         """

   388         Return the list of columns to use in the select statement. If no

   389         columns have been specified, returns all columns relating to fields in

   390         the model.

   391 

   392         If 'with_aliases' is true, any column names that are duplicated

   393         (without the table names) are given unique aliases. This is needed in

   394         some cases to avoid ambiguitity with nested queries.

   395         """

   396         qn = self.quote_name_unless_alias

   397         qn2 = self.connection.ops.quote_name

   398         result = ['(%s) AS %s' % (col, qn2(alias)) for alias, col in self.extra_select.iteritems()]

   399         aliases = set(self.extra_select.keys())

   400         if with_aliases:

   401             col_aliases = aliases.copy()

   402         else:

   403             col_aliases = set()

   404         if self.select:

   405             for col in self.select:

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

   407                     r = '%s.%s' % (qn(col[0]), qn(col[1]))

   408                     if with_aliases and col[1] in col_aliases:

   409                         c_alias = 'Col%d' % len(col_aliases)

   410                         result.append('%s AS %s' % (r, c_alias))

   411                         aliases.add(c_alias)

   412                         col_aliases.add(c_alias)

   413                     else:

   414                         result.append(r)

   415                         aliases.add(r)

   416                         col_aliases.add(col[1])

   417                 else:

   418                     result.append(col.as_sql(quote_func=qn))

   419                     if hasattr(col, 'alias'):

   420                         aliases.add(col.alias)

   421                         col_aliases.add(col.alias)

   422         elif self.default_cols:

   423             cols, new_aliases = self.get_default_columns(with_aliases,

   424                     col_aliases)

   425             result.extend(cols)

   426             aliases.update(new_aliases)

   427         for table, col in self.related_select_cols:

   428             r = '%s.%s' % (qn(table), qn(col))

   429             if with_aliases and col in col_aliases:

   430                 c_alias = 'Col%d' % len(col_aliases)

   431                 result.append('%s AS %s' % (r, c_alias))

   432                 aliases.add(c_alias)

   433                 col_aliases.add(c_alias)

   434             else:

   435                 result.append(r)

   436                 aliases.add(r)

   437                 col_aliases.add(col)

   438 

   439         self._select_aliases = aliases

   440         return result

   441 

   442     def get_default_columns(self, with_aliases=False, col_aliases=None):

   443         """

   444         Computes the default columns for selecting every field in the base

   445         model.

   446 

   447         Returns a list of strings, quoted appropriately for use in SQL

   448         directly, as well as a set of aliases used in the select statement.

   449         """

   450         result = []

   451         table_alias = self.tables[0]

   452         root_pk = self.model._meta.pk.column

   453         seen = {None: table_alias}

   454         qn = self.quote_name_unless_alias

   455         qn2 = self.connection.ops.quote_name

   456         aliases = set()

   457         for field, model in self.model._meta.get_fields_with_model():

   458             try:

   459                 alias = seen[model]

   460             except KeyError:

   461                 alias = self.join((table_alias, model._meta.db_table,

   462                         root_pk, model._meta.pk.column))

   463                 seen[model] = alias

   464             if with_aliases and field.column in col_aliases:

   465                 c_alias = 'Col%d' % len(col_aliases)

   466                 result.append('%s.%s AS %s' % (qn(alias),

   467                     qn2(field.column), c_alias))

   468                 col_aliases.add(c_alias)

   469                 aliases.add(c_alias)

   470             else:

   471                 r = '%s.%s' % (qn(alias), qn2(field.column))

   472                 result.append(r)

   473                 aliases.add(r)

   474                 if with_aliases:

   475                     col_aliases.add(field.column)

   476         return result, aliases

   477 

   478     def get_from_clause(self):

   479         """

   480         Returns a list of strings that are joined together to go after the

   481         "FROM" part of the query, as well as a list any extra parameters that

   482         need to be included. Sub-classes, can override this to create a

   483         from-clause via a "select", for example (e.g. CountQuery).

   484 

   485         This should only be called after any SQL construction methods that

   486         might change the tables we need. This means the select columns and

   487         ordering must be done first.

   488         """

   489         result = []

   490         qn = self.quote_name_unless_alias

   491         qn2 = self.connection.ops.quote_name

   492         first = True

   493         for alias in self.tables:

   494             if not self.alias_refcount[alias]:

   495                 continue

   496             try:

   497                 name, alias, join_type, lhs, lhs_col, col, nullable = self.alias_map[alias]

   498             except KeyError:

   499                 # Extra tables can end up in self.tables, but not in the

   500                 # alias_map if they aren't in a join. That's OK. We skip them.

   501                 continue

   502             alias_str = (alias != name and ' %s' % alias or '')

   503             if join_type and not first:

   504                 result.append('%s %s%s ON (%s.%s = %s.%s)'

   505                         % (join_type, qn(name), alias_str, qn(lhs),

   506                            qn2(lhs_col), qn(alias), qn2(col)))

   507             else:

   508                 connector = not first and ', ' or ''

   509                 result.append('%s%s%s' % (connector, qn(name), alias_str))

   510             first = False

   511         for t in self.extra_tables:

   512             alias, unused = self.table_alias(t)

   513             if alias not in self.alias_map:

   514                 connector = not first and ', ' or ''

   515                 result.append('%s%s' % (connector, qn(alias)))

   516                 first = False

   517         return result, []

   518 

   519     def get_grouping(self):

   520         """

   521         Returns a tuple representing the SQL elements in the "group by" clause.

   522         """

   523         qn = self.quote_name_unless_alias

   524         result = []

   525         for col in self.group_by:

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

   527                 result.append('%s.%s' % (qn(col[0]), qn(col[1])))

   528             elif hasattr(col, 'as_sql'):

   529                 result.append(col.as_sql(qn))

   530             else:

   531                 result.append(str(col))

   532         return result

   533 

   534     def get_ordering(self):

   535         """

   536         Returns list representing the SQL elements in the "order by" clause.

   537         Also sets the ordering_aliases attribute on this instance to a list of

   538         extra aliases needed in the select.

   539 

   540         Determining the ordering SQL can change the tables we need to include,

   541         so this should be run *before* get_from_clause().

   542         """

   543         if self.extra_order_by:

   544             ordering = self.extra_order_by

   545         elif not self.default_ordering:

   546             ordering = []

   547         else:

   548             ordering = self.order_by or self.model._meta.ordering

   549         qn = self.quote_name_unless_alias

   550         qn2 = self.connection.ops.quote_name

   551         distinct = self.distinct

   552         select_aliases = self._select_aliases

   553         result = []

   554         ordering_aliases = []

   555         if self.standard_ordering:

   556             asc, desc = ORDER_DIR['ASC']

   557         else:

   558             asc, desc = ORDER_DIR['DESC']

   559         for field in ordering:

   560             if field == '?':

   561                 result.append(self.connection.ops.random_function_sql())

   562                 continue

   563             if isinstance(field, int):

   564                 if field < 0:

   565                     order = desc

   566                     field = -field

   567                 else:

   568                     order = asc

   569                 result.append('%s %s' % (field, order))

   570                 continue

   571             if '.' in field:

   572                 # This came in through an extra(order_by=...) addition. Pass it

   573                 # on verbatim.

   574                 col, order = get_order_dir(field, asc)

   575                 table, col = col.split('.', 1)

   576                 elt = '%s.%s' % (qn(table), col)

   577                 if not distinct or elt in select_aliases:

   578                     result.append('%s %s' % (elt, order))

   579             elif get_order_dir(field)[0] not in self.extra_select:

   580                 # 'col' is of the form 'field' or 'field1__field2' or

   581                 # '-field1__field2__field', etc.

   582                 for table, col, order in self.find_ordering_name(field,

   583                         self.model._meta, default_order=asc):

   584                     elt = '%s.%s' % (qn(table), qn2(col))

   585                     if distinct and elt not in select_aliases:

   586                         ordering_aliases.append(elt)

   587                     result.append('%s %s' % (elt, order))

   588             else:

   589                 col, order = get_order_dir(field, asc)

   590                 elt = qn(col)

   591                 if distinct and elt not in select_aliases:

   592                     ordering_aliases.append(elt)

   593                 result.append('%s %s' % (elt, order))

   594         self.ordering_aliases = ordering_aliases

   595         return result

   596 

   597     def find_ordering_name(self, name, opts, alias=None, default_order='ASC',

   598             already_seen=None):

   599         """

   600         Returns the table alias (the name might be ambiguous, the alias will

   601         not be) and column name for ordering by the given 'name' parameter.

   602         The 'name' is of the form 'field1__field2__...__fieldN'.

   603         """

   604         name, order = get_order_dir(name, default_order)

   605         pieces = name.split(LOOKUP_SEP)

   606         if not alias:

   607             alias = self.get_initial_alias()

   608         field, target, opts, joins, last = self.setup_joins(pieces, opts,

   609                 alias, False)

   610         alias = joins[-1]

   611         col = target.column

   612 

   613         # If we get to this point and the field is a relation to another model,

   614         # append the default ordering for that model.

   615         if field.rel and len(joins) > 1 and opts.ordering:

   616             # Firstly, avoid infinite loops.

   617             if not already_seen:

   618                 already_seen = set()

   619             join_tuple = tuple([self.alias_map[j][TABLE_NAME] for j in joins])

   620             if join_tuple in already_seen:

   621                 raise FieldError('Infinite loop caused by ordering.')

   622             already_seen.add(join_tuple)

   623 

   624             results = []

   625             for item in opts.ordering:

   626                 results.extend(self.find_ordering_name(item, opts, alias,

   627                         order, already_seen))

   628             return results

   629 

   630         if alias:

   631             # We have to do the same "final join" optimisation as in

   632             # add_filter, since the final column might not otherwise be part of

   633             # the select set (so we can't order on it).

   634             join = self.alias_map[alias]

   635             if col == join[RHS_JOIN_COL]:

   636                 self.unref_alias(alias)

   637                 alias = join[LHS_ALIAS]

   638                 col = join[LHS_JOIN_COL]

   639         return [(alias, col, order)]

   640 

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

   642         """

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

   644         new alias or not.

   645 

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

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

   648         """

   649         current = self.table_map.get(table_name)

   650         if not create and current:

   651             alias = current[0]

   652             self.alias_refcount[alias] += 1

   653             return alias, False

   654 

   655         # Create a new alias for this table.

   656         if current:

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

   658             current.append(alias)

   659         else:

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

   661             alias = table_name

   662             self.table_map[alias] = [alias]

   663         self.alias_refcount[alias] = 1

   664         #self.alias_map[alias] = None

   665         self.tables.append(alias)

   666         return alias, True

   667 

   668     def ref_alias(self, alias):

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

   670         self.alias_refcount[alias] += 1

   671 

   672     def unref_alias(self, alias):

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

   674         self.alias_refcount[alias] -= 1

   675 

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

   677         """

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

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

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

   681         always promoted.

   682         """

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

   684                 self.alias_map[alias] != self.LOUTER):

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

   686             data[JOIN_TYPE] = self.LOUTER

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

   688 

   689     def change_aliases(self, change_map):

   690         """

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

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

   693         clause.

   694         """

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

   696 

   697         # 1. Update references in "select" and "where".

   698         self.where.relabel_aliases(change_map)

   699         for pos, col in enumerate(self.select):

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

   701                 self.select[pos] = (change_map.get(old_alias, old_alias), col[1])

   702             else:

   703                 col.relabel_aliases(change_map)

   704 

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

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

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

   708             alias_data[RHS_ALIAS] = new_alias

   709 

   710             t = self.rev_join_map[old_alias]

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

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

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

   714             self.rev_join_map[new_alias] = t

   715             del self.rev_join_map[old_alias]

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

   717             del self.alias_refcount[old_alias]

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

   719             del self.alias_map[old_alias]

   720 

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

   722             for pos, alias in enumerate(table_aliases):

   723                 if alias == old_alias:

   724                     table_aliases[pos] = new_alias

   725                     break

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

   727                 if alias == old_alias:

   728                     self.tables[pos] = new_alias

   729                     break

   730 

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

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

   733             lhs = data[LHS_ALIAS]

   734             if lhs in change_map:

   735                 data = list(data)

   736                 data[LHS_ALIAS] = change_map[lhs]

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

   738 

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

   740         """

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

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

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

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

   745 

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

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

   748 

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

   750         should not be changed.

   751         """

   752         assert ord(self.alias_prefix) < ord('Z')

   753         self.alias_prefix = chr(ord(self.alias_prefix) + 1)

   754         change_map = {}

   755         prefix = self.alias_prefix

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

   757             if alias in exceptions:

   758                 continue

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

   760             change_map[alias] = new_alias

   761             self.tables[pos] = new_alias

   762         self.change_aliases(change_map)

   763 

   764     def get_initial_alias(self):

   765         """

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

   767         count.

   768         """

   769         if self.tables:

   770             alias = self.tables[0]

   771             self.ref_alias(alias)

   772         else:

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

   774         return alias

   775 

   776     def count_active_tables(self):

   777         """

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

   779         count.

   780         """

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

   782 

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

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

   785         """

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

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

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

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

   790         of::

   791 

   792             lhs.lhs_col = table.col

   793 

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

   795         created, regardless of whether one already exists or not. Otherwise

   796         'reuse' must be a set and a new join is created unless one of the

   797         aliases in `reuse` can be used.

   798 

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

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

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

   802 

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

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

   805         to LOUTER, if necessary).

   806 

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

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

   809         and Q-objects together.

   810 

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

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

   813         """

   814         lhs, table, lhs_col, col = connection

   815         if lhs in self.alias_map:

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

   817         else:

   818             lhs_table = lhs

   819 

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

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

   822             # reusable set for this table".

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

   824             always_create = False

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

   826         if not always_create:

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

   828                 if alias not in exclusions:

   829                     self.ref_alias(alias)

   830                     if promote:

   831                         self.promote_alias(alias)

   832                     return alias

   833 

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

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

   836         if not lhs:

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

   838             # means the later columns are ignored.

   839             join_type = None

   840         elif promote or outer_if_first:

   841             join_type = self.LOUTER

   842         else:

   843             join_type = self.INNER

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

   845         self.alias_map[alias] = join

   846         if t_ident in self.join_map:

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

   848         else:

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

   850         self.rev_join_map[alias] = t_ident

   851         return alias

   852 

   853     def fill_related_selections(self, opts=None, root_alias=None, cur_depth=1,

   854             used=None, requested=None, restricted=None):

   855         """

   856         Fill in the information needed for a select_related query. The current

   857         depth is measured as the number of connections away from the root model

   858         (for example, cur_depth=1 means we are looking at models with direct

   859         connections to the root model).

   860         """

   861         if not restricted and self.max_depth and cur_depth > self.max_depth:

   862             # We've recursed far enough; bail out.

   863             return

   864         if not opts:

   865             opts = self.get_meta()

   866             root_alias = self.get_initial_alias()

   867             self.related_select_cols = []

   868             self.related_select_fields = []

   869         if not used:

   870             used = set()

   871 

   872         # Setup for the case when only particular related fields should be

   873         # included in the related selection.

   874         if requested is None and restricted is not False:

   875             if isinstance(self.select_related, dict):

   876                 requested = self.select_related

   877                 restricted = True

   878             else:

   879                 restricted = False

   880 

   881         for f, model in opts.get_fields_with_model():

   882             if (not f.rel or (restricted and f.name not in requested) or

   883                     (not restricted and f.null) or f.rel.parent_link):

   884                 continue

   885             table = f.rel.to._meta.db_table

   886             if model:

   887                 int_opts = opts

   888                 alias = root_alias

   889                 for int_model in opts.get_base_chain(model):

   890                     lhs_col = int_opts.parents[int_model].column

   891                     int_opts = int_model._meta

   892                     alias = self.join((alias, int_opts.db_table, lhs_col,

   893                             int_opts.pk.column), exclusions=used,

   894                             promote=f.null)

   895             else:

   896                 alias = root_alias

   897             alias = self.join((alias, table, f.column,

   898                     f.rel.get_related_field().column), exclusions=used,

   899                     promote=f.null)

   900             used.add(alias)

   901             self.related_select_cols.extend([(alias, f2.column)

   902                     for f2 in f.rel.to._meta.fields])

   903             self.related_select_fields.extend(f.rel.to._meta.fields)

   904             if restricted:

   905                 next = requested.get(f.name, {})

   906             else:

   907                 next = False

   908             self.fill_related_selections(f.rel.to._meta, alias, cur_depth + 1,

   909                     used, next, restricted)

   910 

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

   912             can_reuse=None):

   913         """

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

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

   916 

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

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

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

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

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

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

   923 

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

   925         internally when constructing nested queries).

   926 

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

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

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

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

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

   932         """

   933         arg, value = filter_expr

   934         parts = arg.split(LOOKUP_SEP)

   935         if not parts:

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

   937 

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

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

   940             lookup_type = 'exact'

   941         else:

   942             lookup_type = parts.pop()

   943 

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

   945         # uses of None as a query value.

   946         if value is None:

   947             if lookup_type != 'exact':

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

   949             lookup_type = 'isnull'

   950             value = True

   951         elif callable(value):

   952             value = value()

   953 

   954         opts = self.get_meta()

   955         alias = self.get_initial_alias()

   956         allow_many = trim or not negate

   957 

   958         try:

   959             field, target, opts, join_list, last = self.setup_joins(parts, opts,

   960                     alias, True, allow_many, can_reuse=can_reuse)

   961         except MultiJoin, e:

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

   963             return

   964         final = len(join_list)

   965         penultimate = last.pop()

   966         if penultimate == final:

   967             penultimate = last.pop()

   968         if trim and len(join_list) > 1:

   969             extra = join_list[penultimate:]

   970             join_list = join_list[:penultimate]

   971             final = penultimate

   972             penultimate = last.pop()

   973             col = self.alias_map[extra[0]][LHS_JOIN_COL]

   974             for alias in extra:

   975                 self.unref_alias(alias)

   976         else:

   977             col = target.column

   978         alias = join_list[-1]

   979 

   980         if final > 1:

   981             # An optimization: if the final join is against the same column as

   982             # we are comparing against, we can go back one step in the join

   983             # chain and compare against the lhs of the join instead. The result

   984             # (potentially) involves one less table join.

   985             join = self.alias_map[alias]

   986             if col == join[RHS_JOIN_COL]:

   987                 self.unref_alias(alias)

   988                 alias = join[LHS_ALIAS]

   989                 col = join[LHS_JOIN_COL]

   990                 join_list = join_list[:-1]

   991                 final -= 1

   992                 if final == penultimate:

   993                     penultimate = last.pop()

   994 

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

   996                 final > 1):

   997             # If the comparison is against NULL, we need to use a left outer

   998             # join when connecting to the previous model. We make that

   999             # adjustment here. We don't do this unless needed as it's less

  1000             # efficient at the database level.

  1001             self.promote_alias(join_list[penultimate])

  1002 

  1003         if connector == OR:

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

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

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

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

  1008             # join list) an outer join.

  1009             join_it = iter(join_list)

  1010             table_it = iter(self.tables)

  1011             join_it.next(), table_it.next()

  1012             for join in join_it:

  1013                 table = table_it.next()

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

  1015                     continue

  1016                 self.promote_alias(join)

  1017                 if table != join:

  1018                     self.promote_alias(table)

  1019                 break

  1020             for join in join_it:

  1021                 self.promote_alias(join)

  1022             for table in table_it:

  1023                 # Some of these will have been promoted from the join_list, but

  1024                 # that's harmless.

  1025                 self.promote_alias(table)

  1026 

  1027         self.where.add((alias, col, field, lookup_type, value), connector)

  1028         if negate:

  1029             for alias in join_list:

  1030                 self.promote_alias(alias)

  1031             if final > 1 and lookup_type != 'isnull':

  1032                 for alias in join_list:

  1033                     if self.alias_map[alias] == self.LOUTER:

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

  1035                         entry = Node([(alias, j_col, None, 'isnull', True)])

  1036                         entry.negate()

  1037                         self.where.add(entry, AND)

  1038                         break

  1039         if can_reuse is not None:

  1040             can_reuse.update(join_list)

  1041 

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

  1043         """

  1044         Adds a Q-object to the current filter.

  1045 

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

  1047         """

  1048         if used_aliases is None:

  1049             used_aliases = set()

  1050         if hasattr(q_object, 'add_to_query'):

  1051             # Complex custom objects are responsible for adding themselves.

  1052             q_object.add_to_query(self, used_aliases)

  1053             return

  1054 

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

  1056             self.where.start_subtree(AND)

  1057             subtree = True

  1058         else:

  1059             subtree = False

  1060         connector = AND

  1061         for child in q_object.children:

  1062             if isinstance(child, Node):

  1063                 self.where.start_subtree(connector)

  1064                 self.add_q(child, used_aliases)

  1065                 self.where.end_subtree()

  1066             else:

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

  1068                         can_reuse=used_aliases)

  1069             connector = q_object.connector

  1070         if q_object.negated:

  1071             self.where.negate()

  1072         if subtree:

  1073             self.where.end_subtree()

  1074 

  1075     def setup_joins(self, names, opts, alias, dupe_multis, allow_many=True,

  1076             allow_explicit_fk=False, can_reuse=None):

  1077         """

  1078         Compute the necessary table joins for the passage through the fields

  1079         given in 'names'. 'opts' is the Options class for the current model

  1080         (which gives the table we are joining to), 'alias' is the alias for the

  1081         table we are joining to. If dupe_multis is True, any many-to-many or

  1082         many-to-one joins will always create a new alias (necessary for

  1083         disjunctive filters).

  1084 

  1085         Returns the final field involved in the join, the target database

  1086         column (used for any 'where' constraint), the final 'opts' value and the

  1087         list of tables joined.

  1088         """

  1089         joins = [alias]

  1090         last = [0]

  1091         for pos, name in enumerate(names):

  1092             last.append(len(joins))

  1093             if name == 'pk':

  1094                 name = opts.pk.name

  1095 

  1096             try:

  1097                 field, model, direct, m2m = opts.get_field_by_name(name)

  1098             except FieldDoesNotExist:

  1099                 for f in opts.fields:

  1100                     if allow_explicit_fk and name == f.attname:

  1101                         # XXX: A hack to allow foo_id to work in values() for

  1102                         # backwards compatibility purposes. If we dropped that

  1103                         # feature, this could be removed.

  1104                         field, model, direct, m2m = opts.get_field_by_name(f.name)

  1105                         break

  1106                 else:

  1107                     names = opts.get_all_field_names()

  1108                     raise FieldError("Cannot resolve keyword %r into field. "

  1109                             "Choices are: %s" % (name, ", ".join(names)))

  1110             if not allow_many and (m2m or not direct):

  1111                 for alias in joins:

  1112                     self.unref_alias(alias)

  1113                 raise MultiJoin(pos + 1)

  1114             if model:

  1115                 # The field lives on a base class of the current model.

  1116                 alias_list = []

  1117                 for int_model in opts.get_base_chain(model):

  1118                     lhs_col = opts.parents[int_model].column

  1119                     opts = int_model._meta

  1120                     alias = self.join((alias, opts.db_table, lhs_col,

  1121                             opts.pk.column), exclusions=joins)

  1122                     joins.append(alias)

  1123             cached_data = opts._join_cache.get(name)

  1124             orig_opts = opts

  1125 

  1126             if direct:

  1127                 if m2m:

  1128                     # Many-to-many field defined on the current model.

  1129                     if cached_data:

  1130                         (table1, from_col1, to_col1, table2, from_col2,

  1131                                 to_col2, opts, target) = cached_data

  1132                     else:

  1133                         table1 = field.m2m_db_table()

  1134                         from_col1 = opts.pk.column

  1135                         to_col1 = field.m2m_column_name()