"""

Create SQL statements for QuerySets.

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

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

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

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

"""

from copy import deepcopy

from django.utils.tree import Node

from django.utils.datastructures import SortedDict

from django.dispatch import dispatcher

from django.db import connection

from django.db.models import signals

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

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

from django.db.models.fields import FieldDoesNotExist

from django.core.exceptions import FieldError

from datastructures import EmptyResultSet, Empty, MultiJoin

from constants import *

try:

    set

except NameError:

    from sets import Set as set     # Python 2.3 fallback

__all__ = ['Query']

class Query(object):

    """

    A single SQL query.

    """

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

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

    INNER = 'INNER JOIN'

    LOUTER = 'LEFT OUTER JOIN'

    alias_prefix = 'T'

    query_terms = QUERY_TERMS

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

        self.model = model

        self.connection = connection

        self.alias_refcount = {}

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

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

        self.join_map = {}

        self.rev_join_map = {}  # Reverse of join_map.

        self.quote_cache = {}

        self.default_cols = True

        self.default_ordering = True

        self.standard_ordering = True

        self.ordering_aliases = []

        self.start_meta = None

        self.select_fields = []

        self.related_select_fields = []

        # SQL-related attributes

        self.select = []

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

        self.where = where()

        self.where_class = where

        self.group_by = []

        self.having = []

        self.order_by = []

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

        self.distinct = False

        self.select_related = False

        self.related_select_cols = []

        # Arbitrary maximum limit for select_related. Prevents infinite

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

        self.max_depth = 5

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

        # verbatim to the appropriate clause.

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

        self.extra_select_params = ()

        self.extra_tables = ()

        self.extra_where = ()

        self.extra_params = ()

        self.extra_order_by = ()

    def __str__(self):

        """

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

        substituted in.

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

        done by the database interface at execution time.

        """

        sql, params = self.as_sql()

        return sql % params

    def __deepcopy__(self, memo):

        result= self.clone()

        memo[id(self)] = result

        return result

    def __getstate__(self):

        """

        Pickling support.

        """

        obj_dict = self.__dict__.copy()

        del obj_dict['connection']

        return obj_dict

    def __setstate__(self, obj_dict):

        """

        Unpickling support.

        """

        self.__dict__.update(obj_dict)

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

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

        # connection variable.

        self.connection = connection

    def get_meta(self):

        """

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

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

        """

        if self.start_meta:

            return self.start_meta

        return self.model._meta

    def quote_name_unless_alias(self, name):

        """

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

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

        quoted strings specially (e.g. PostgreSQL).

        """

        if name in self.quote_cache:

            return self.quote_cache[name]

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

                name in self.extra_select):

            self.quote_cache[name] = name

            return name

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

        self.quote_cache[name] = r

        return r

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

        """

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

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

        """

        obj = Empty()

        obj.__class__ = klass or self.__class__

        obj.model = self.model

        obj.connection = self.connection

        obj.alias_refcount = self.alias_refcount.copy()

        obj.alias_map = self.alias_map.copy()

        obj.table_map = self.table_map.copy()

        obj.join_map = self.join_map.copy()

        obj.rev_join_map = self.rev_join_map.copy()

        obj.quote_cache = {}

        obj.default_cols = self.default_cols

        obj.default_ordering = self.default_ordering

        obj.standard_ordering = self.standard_ordering

        obj.ordering_aliases = []

        obj.start_meta = self.start_meta

        obj.select_fields = self.select_fields[:]

        obj.related_select_fields = self.related_select_fields[:]

        obj.select = self.select[:]

        obj.tables = self.tables[:]

        obj.where = deepcopy(self.where)

        obj.where_class = self.where_class

        obj.group_by = self.group_by[:]

        obj.having = self.having[:]

        obj.order_by = self.order_by[:]

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

        obj.distinct = self.distinct

        obj.select_related = self.select_related

        obj.related_select_cols = []

        obj.max_depth = self.max_depth

        obj.extra_select = self.extra_select.copy()

        obj.extra_select_params = self.extra_select_params

        obj.extra_tables = self.extra_tables

        obj.extra_where = self.extra_where

        obj.extra_params = self.extra_params

        obj.extra_order_by = self.extra_order_by

        obj.__dict__.update(kwargs)

        if hasattr(obj, '_setup_query'):

            obj._setup_query()

        return obj

    def results_iter(self):

        """

        Returns an iterator over the results from executing this query.

        """

        resolve_columns = hasattr(self, 'resolve_columns')

        if resolve_columns:

            if self.select_fields:

                fields = self.select_fields + self.related_select_fields

            else:

                fields = self.model._meta.fields

        for rows in self.execute_sql(MULTI):

            for row in rows:

                if resolve_columns:

                    row = self.resolve_columns(row, fields)

                yield row

    def get_count(self):

        """

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

        """

        from subqueries import CountQuery

        obj = self.clone()

        obj.clear_ordering(True)

        obj.clear_limits()

        obj.select_related = False

        obj.related_select_cols = []

        obj.related_select_fields = []

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

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

                    distinct=False)

            obj.select = []

            obj.extra_select = {}

        obj.add_count_column()

        data = obj.execute_sql(SINGLE)

        if not data:

            return 0

        number = data[0]

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

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

        # output.

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

        if self.high_mark:

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

        return number

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

        """

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

        parameters.

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

        in the query.

        """

        self.pre_sql_setup()

        out_cols = self.get_columns(with_col_aliases)

        ordering = self.get_ordering()

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

        # get_from_clause() for details.

        from_, f_params = self.get_from_clause()

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

        params = list(self.extra_select_params)

        result = ['SELECT']

        if self.distinct:

            result.append('DISTINCT')

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

        result.append('FROM')

        result.extend(from_)

        params.extend(f_params)

        if where:

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

            params.extend(w_params)

        if self.extra_where:

            if not where:

                result.append('WHERE')

            else:

                result.append('AND')

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

        if self.group_by:

            grouping = self.get_grouping()

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

        if ordering:

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

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

        if with_limits:

            if self.high_mark:

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

            if self.low_mark:

                if not self.high_mark:

                    val = self.connection.ops.no_limit_value()

                    if val:

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

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

        params.extend(self.extra_params)

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

    def combine(self, rhs, connector):

        """

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

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

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

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

        'rhs' query.

        """

        assert self.model == rhs.model, \

                "Cannot combine queries on two different base models."

        assert self.can_filter(), \

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

        assert self.distinct == rhs.distinct, \

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

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

        change_map = {}

        used = set()

        conjunction = (connector == AND)

        first = True

        for alias in rhs.tables:

            if not rhs.alias_refcount[alias]:

                # An unused alias.

                continue

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

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

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

            used.add(new_alias)

            change_map[alias] = new_alias

            first = False

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

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

        # to an outer join.

        if not conjunction:

            for alias in self.tables[1:]:

                if self.alias_refcount[alias] == 1:

                    self.promote_alias(alias, True)

                    break

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

        # one.

        if rhs.where:

            w = deepcopy(rhs.where)

            w.relabel_aliases(change_map)

            if not self.where:

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

                # everything" where-constraint so that connections between the

                # where clauses won't exclude valid results.

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

        elif self.where:

            # rhs has an empty where clause.

            w = self.where_class()

            w.add(EverythingNode(), AND)

        else:

            w = self.where_class()

        self.where.add(w, connector)

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

        self.select = []

        for col in rhs.select:

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

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

            else:

                item = deepcopy(col)

                item.relabel_aliases(change_map)

                self.select.append(item)

        self.select_fields = rhs.select_fields[:]

        self.extra_select = rhs.extra_select.copy()

        self.extra_tables = rhs.extra_tables

        self.extra_where = rhs.extra_where

        self.extra_params = rhs.extra_params

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

        # the current ordering is used.

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

        self.extra_order_by = rhs.extra_order_by or self.extra_order_by

    def pre_sql_setup(self):

        """

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

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

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

        """

        if not self.tables:

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

        if self.select_related and not self.related_select_cols:

            self.fill_related_selections()

    def get_columns(self, with_aliases=False):

        """

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

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

        the model.

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

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

        some cases to avoid ambiguitity with nested queries.

        """

        qn = self.quote_name_unless_alias

        qn2 = self.connection.ops.quote_name

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

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

        if with_aliases:

            col_aliases = aliases.copy()

        else:

            col_aliases = set()

        if self.select:

            for col in self.select:

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

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

                    if with_aliases and col[1] in col_aliases:

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

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

                        aliases.add(c_alias)

                        col_aliases.add(c_alias)

                    else:

                        result.append(r)

                        aliases.add(r)

                        col_aliases.add(col[1])

                else:

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

                    if hasattr(col, 'alias'):

                        aliases.add(col.alias)

                        col_aliases.add(col.alias)

        elif self.default_cols:

            cols, new_aliases = self.get_default_columns(with_aliases,

                    col_aliases)

            result.extend(cols)

            aliases.update(new_aliases)

        for table, col in self.related_select_cols:

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

            if with_aliases and col in col_aliases:

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

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

                aliases.add(c_alias)

                col_aliases.add(c_alias)

            else:

                result.append(r)

                aliases.add(r)

                col_aliases.add(col)

        self._select_aliases = aliases

        return result

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

        """

        Computes the default columns for selecting every field in the base

        model.

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

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

        """

        result = []

        table_alias = self.tables[0]

        root_pk = self.model._meta.pk.column

        seen = {None: table_alias}

        qn = self.quote_name_unless_alias

        qn2 = self.connection.ops.quote_name

        aliases = set()

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

            try:

                alias = seen[model]

            except KeyError:

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

                        root_pk, model._meta.pk.column))

                seen[model] = alias

            if with_aliases and field.column in col_aliases:

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

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

                    qn2(field.column), c_alias))

                col_aliases.add(c_alias)

                aliases.add(c_alias)

            else:

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

                result.append(r)

                aliases.add(r)

                if with_aliases:

                    col_aliases.add(field.column)

        return result, aliases

    def get_from_clause(self):

        """

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

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

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

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

        This should only be called after any SQL construction methods that

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

        ordering must be done first.

        """

        result = []

        qn = self.quote_name_unless_alias

        qn2 = self.connection.ops.quote_name

        first = True

        for alias in self.tables:

            if not self.alias_refcount[alias]:

                continue

            try:

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

            except KeyError:

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

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

                continue

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

            if join_type and not first:

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

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

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

            else:

                connector = not first and ', ' or ''

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

            first = False

        for t in self.extra_tables:

            alias, unused = self.table_alias(t)

            if alias not in self.alias_map:

                connector = not first and ', ' or ''

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

                first = False

        return result, []

    def get_grouping(self):

        """

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

        """

        qn = self.quote_name_unless_alias

        result = []

        for col in self.group_by:

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

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

            elif hasattr(col, 'as_sql'):