"""

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.utils.encoding import force_unicode

from django.db.backends.util import truncate_name

from django.db import connection

from django.db.models import signals

from django.db.models.fields import FieldDoesNotExist

from django.db.models.query_utils import select_related_descend

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

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

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

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', 'BaseQuery']

class BaseQuery(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

    aggregates_module = base_aggregates_module

    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.select_fields = []

        self.related_select_fields = []

        self.dupe_avoidance = {}

        self.used_aliases = set()

        self.filter_is_sticky = False

        self.included_inherited_models = {}

        # SQL-related attributes

        self.select = []

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

        self.where = where()

        self.where_class = where

        self.group_by = None

        self.having = where()

        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 = []

        # SQL aggregate-related attributes

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

        self.aggregate_select_mask = None

        self._aggregate_select_cache = None

        # 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 = SortedDict()  # Maps col_alias -> (col_sql, params).

        self.extra_select_mask = None

        self._extra_select_cache = None

        self.extra_tables = ()

        self.extra_where = ()

        self.extra_params = ()

        self.extra_order_by = ()

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

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

        # load.

        self.deferred_loading = (set(), True)

    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()

        obj_dict['related_select_fields'] = []

        obj_dict['related_select_cols'] = []

        del obj_dict['connection']

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

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

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

        obj_dict['select_fields'] = [

            f is not None and f.name or None

            for f in obj_dict['select_fields']

        ]

        return obj_dict

    def __setstate__(self, obj_dict):

        """

        Unpickling support.

        """

        # Rebuild list of field instances

        obj_dict['select_fields'] = [

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

            for name in obj_dict['select_fields']

        ]

        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 be changed

        by subclasses.

        """

        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.included_inherited_models = self.included_inherited_models.copy()

        obj.ordering_aliases = []

        obj.select_fields = self.select_fields[:]

        obj.related_select_fields = self.related_select_fields[:]

        obj.dupe_avoidance = self.dupe_avoidance.copy()

        obj.select = self.select[:]

        obj.tables = self.tables[:]

        obj.where = deepcopy(self.where)

        obj.where_class = self.where_class

        if self.group_by is None:

            obj.group_by = None

        else:

            obj.group_by = self.group_by[:]

        obj.having = deepcopy(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.aggregates = deepcopy(self.aggregates)

        if self.aggregate_select_mask is None:

            obj.aggregate_select_mask = None

        else:

            obj.aggregate_select_mask = self.aggregate_select_mask.copy()

        if self._aggregate_select_cache is None:

            obj._aggregate_select_cache = None

        else:

            obj._aggregate_select_cache = self._aggregate_select_cache.copy()

        obj.max_depth = self.max_depth

        obj.extra = self.extra.copy()

        if self.extra_select_mask is None:

            obj.extra_select_mask = None

        else:

            obj.extra_select_mask = self.extra_select_mask.copy()

        if self._extra_select_cache is None:

            obj._extra_select_cache = None

        else:

            obj._extra_select_cache = self._extra_select_cache.copy()

        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.deferred_loading = deepcopy(self.deferred_loading)

        if self.filter_is_sticky and self.used_aliases:

            obj.used_aliases = self.used_aliases.copy()

        else:

            obj.used_aliases = set()

        obj.filter_is_sticky = False

        obj.__dict__.update(kwargs)

        if hasattr(obj, '_setup_query'):

            obj._setup_query()

        return obj

    def convert_values(self, value, field):

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

        across database backends.

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

        it can be overridden by Query classes for specific backends.

        """

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

    def resolve_aggregate(self, value, aggregate):

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

        consistent (and reasonable) types.

        This is required because of the predisposition of certain backends

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

        """

        if value is None:

            if aggregate.is_ordinal:

                return 0

            # Return None as-is

            return value

        elif aggregate.is_ordinal:

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

            return int(value)

        elif aggregate.is_computed:

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

            return float(value)

        else:

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

            return self.convert_values(value, aggregate.field)

    def results_iter(self):

        """

        Returns an iterator over the results from executing this query.

        """

        resolve_columns = hasattr(self, 'resolve_columns')

        fields = None

        for rows in self.execute_sql(MULTI):

            for row in rows:

                if resolve_columns:

                    if fields is None:

                        # We only set this up here because

                        # related_select_fields isn't populated until

                        # execute_sql() has been called.

                        if self.select_fields:

                            fields = self.select_fields + self.related_select_fields

                        else:

                            fields = self.model._meta.fields

                    row = self.resolve_columns(row, fields)

                if self.aggregate_select:

                    aggregate_start = len(self.extra_select.keys()) + len(self.select)

                    aggregate_end = aggregate_start + len(self.aggregate_select)

                    row = tuple(row[:aggregate_start]) + tuple([

                        self.resolve_aggregate(value, aggregate)

                        for (alias, aggregate), value

                        in zip(self.aggregate_select.items(), row[aggregate_start:aggregate_end])

                    ]) + tuple(row[aggregate_end:])

                yield row

    def get_aggregation(self):

        """

        Returns the dictionary with the values of the existing aggregations.

        """

        if not self.aggregate_select:

            return {}

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

        # information but retrieves only the first row. Aggregate

        # over the subquery instead.

        if self.group_by is not None:

            from subqueries import AggregateQuery

            query = AggregateQuery(self.model, self.connection)

            obj = self.clone()

            # Remove any aggregates marked for reduction from the subquery

            # and move them to the outer AggregateQuery.

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

                if aggregate.is_summary:

                    query.aggregate_select[alias] = aggregate

                    del obj.aggregate_select[alias]

            query.add_subquery(obj)

        else:

            query = self

            self.select = []

            self.default_cols = False

            self.extra = {}

            self.remove_inherited_models()

        query.clear_ordering(True)

        query.clear_limits()

        query.select_related = False

        query.related_select_cols = []

        query.related_select_fields = []

        result = query.execute_sql(SINGLE)

        if result is None:

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

        return dict([

            (alias, self.resolve_aggregate(val, aggregate))

            for (alias, aggregate), val

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

        ])

    def get_count(self):

        """

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

        """

        obj = self.clone()

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

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

            # specify the columns that are to be returned.

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

            from subqueries import AggregateQuery

            subquery = obj

            subquery.clear_ordering(True)

            subquery.clear_limits()

            obj = AggregateQuery(obj.model, obj.connection)

            obj.add_subquery(subquery)

        obj.add_count_column()

        number = obj.get_aggregation()[None]

        # 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 is not None:

            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, ordering_group_by = 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()

        qn = self.quote_name_unless_alias

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

        having, h_params = self.having.as_sql(qn=qn)

        params = []

        for val in self.extra_select.itervalues():

            params.extend(val[1])

        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))

        grouping, gb_params = self.get_grouping()

        if grouping:

            if ordering:

                # If the backend can't group by PK (i.e., any database

                # other than MySQL), then any fields mentioned in the

                # ordering clause needs to be in the group by clause.

                if not self.connection.features.allows_group_by_pk:

                    for col, col_params in ordering_group_by:

                        if col not in grouping:

                            grouping.append(str(col))

                            gb_params.extend(col_params)

            else:

                ordering = self.connection.ops.force_no_ordering()

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

            params.extend(gb_params)

        if having:

            result.append('HAVING %s' % having)

            params.extend(h_params)

        if ordering:

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

        if with_limits:

            if self.high_mark is not None:

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

            if self.low_mark:

                if self.high_mark is None:

                    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 as_nested_sql(self):

        """

        Perform the same functionality as the as_sql() method, returning an

        SQL string and parameters. However, the alias prefixes are bumped

        beforehand (in a copy -- the current query isn't changed) and any

        ordering is removed.

        Used when nesting this query inside another.

        """

        obj = self.clone()

        obj.clear_ordering(True)

        obj.bump_prefix()

        return obj.as_sql()

    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."

        self.remove_inherited_models()

        # 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.