1 """

     2 Various data structures used in query construction.

     3 

     4 Factored out from django.db.models.query to avoid making the main module very

     5 large and/or so that they can be used by other modules without getting into

     6 circular import difficulties.

     7 """

     8 

     9 import weakref

    10 from copy import deepcopy

    11 

    12 from django.utils import tree

    13 from django.utils.datastructures import SortedDict

    14 

    15 try:

    16     sorted

    17 except NameError:

    18     from django.utils.itercompat import sorted  # For Python 2.3.

    19 

    20 

    21 class CyclicDependency(Exception):

    22     """

    23     An error when dealing with a collection of objects that have a cyclic

    24     dependency, i.e. when deleting multiple objects.

    25     """

    26     pass

    27 

    28 class CollectedObjects(object):

    29     """

    30     A container that stores keys and lists of values along with remembering the

    31     parent objects for all the keys.

    32 

    33     This is used for the database object deletion routines so that we can

    34     calculate the 'leaf' objects which should be deleted first.

    35 

    36     previously_seen is an optional argument. It must be a CollectedObjects

    37     instance itself; any previously_seen collected object will be blocked from

    38     being added to this instance.

    39     """

    40 

    41     def __init__(self, previously_seen=None):

    42         self.data = {}

    43         self.children = {}

    44         if previously_seen:

    45             self.blocked = previously_seen.blocked

    46             for cls, seen in previously_seen.data.items():

    47                 self.blocked.setdefault(cls, SortedDict()).update(seen)

    48         else:

    49             self.blocked = {}

    50 

    51     def add(self, model, pk, obj, parent_model, nullable=False):

    52         """

    53         Adds an item to the container.

    54 

    55         Arguments:

    56         * model - the class of the object being added.

    57         * pk - the primary key.

    58         * obj - the object itself.

    59         * parent_model - the model of the parent object that this object was

    60           reached through.

    61         * nullable - should be True if this relation is nullable.

    62 

    63         Returns True if the item already existed in the structure and

    64         False otherwise.

    65         """

    66         if pk in self.blocked.get(model, {}):

    67             return True

    68 

    69         d = self.data.setdefault(model, SortedDict())

    70         retval = pk in d

    71         d[pk] = obj

    72         # Nullable relationships can be ignored -- they are nulled out before

    73         # deleting, and therefore do not affect the order in which objects

    74         # have to be deleted.

    75         if parent_model is not None and not nullable:

    76             self.children.setdefault(parent_model, []).append(model)

    77         return retval

    78 

    79     def __contains__(self, key):

    80         return self.data.__contains__(key)

    81 

    82     def __getitem__(self, key):

    83         return self.data[key]

    84 

    85     def __nonzero__(self):

    86         return bool(self.data)

    87 

    88     def iteritems(self):

    89         for k in self.ordered_keys():

    90             yield k, self[k]

    91 

    92     def items(self):

    93         return list(self.iteritems())

    94 

    95     def keys(self):

    96         return self.ordered_keys()

    97 

    98     def ordered_keys(self):

    99         """

   100         Returns the models in the order that they should be dealt with (i.e.

   101         models with no dependencies first).

   102         """

   103         dealt_with = SortedDict()

   104         # Start with items that have no children

   105         models = self.data.keys()

   106         while len(dealt_with) < len(models):

   107             found = False

   108             for model in models:

   109                 if model in dealt_with:

   110                     continue

   111                 children = self.children.setdefault(model, [])

   112                 if len([c for c in children if c not in dealt_with]) == 0:

   113                     dealt_with[model] = None

   114                     found = True

   115             if not found:

   116                 raise CyclicDependency(

   117                     "There is a cyclic dependency of items to be processed.")

   118 

   119         return dealt_with.keys()

   120 

   121     def unordered_keys(self):

   122         """

   123         Fallback for the case where is a cyclic dependency but we don't  care.

   124         """

   125         return self.data.keys()

   126 

   127 class QueryWrapper(object):

   128     """

   129     A type that indicates the contents are an SQL fragment and the associate

   130     parameters. Can be used to pass opaque data to a where-clause, for example.

   131     """

   132     def __init__(self, sql, params):

   133         self.data = sql, params

   134 

   135     def as_sql(self, qn=None):

   136         return self.data

   137 

   138 class Q(tree.Node):

   139     """

   140     Encapsulates filters as objects that can then be combined logically (using

   141     & and |).

   142     """

   143     # Connection types

   144     AND = 'AND'

   145     OR = 'OR'

   146     default = AND

   147 

   148     def __init__(self, *args, **kwargs):

   149         super(Q, self).__init__(children=list(args) + kwargs.items())

   150 

   151     def _combine(self, other, conn):

   152         if not isinstance(other, Q):

   153             raise TypeError(other)

   154         obj = deepcopy(self)

   155         obj.add(other, conn)

   156         return obj

   157 

   158     def __or__(self, other):

   159         return self._combine(other, self.OR)

   160 

   161     def __and__(self, other):

   162         return self._combine(other, self.AND)

   163 

   164     def __invert__(self):

   165         obj = deepcopy(self)

   166         obj.negate()

   167         return obj

   168 

   169 class DeferredAttribute(object):

   170     """

   171     A wrapper for a deferred-loading field. When the value is read from this

   172     object the first time, the query is executed.

   173     """

   174     def __init__(self, field_name, model):

   175         self.field_name = field_name

   176         self.model_ref = weakref.ref(model)

   177         self.loaded = False

   178 

   179     def __get__(self, instance, owner):

   180         """

   181         Retrieves and caches the value from the datastore on the first lookup.

   182         Returns the cached value.

   183         """

   184         assert instance is not None

   185         cls = self.model_ref()

   186         data = instance.__dict__

   187         if data.get(self.field_name, self) is self:

   188             data[self.field_name] = cls._base_manager.filter(pk=instance.pk).values_list(self.field_name, flat=True).get()

   189         return data[self.field_name]

   190 

   191     def __set__(self, instance, value):

   192         """

   193         Deferred loading attributes can be set normally (which means there will

   194         never be a database lookup involved.

   195         """

   196         instance.__dict__[self.field_name] = value

   197 

   198 def select_related_descend(field, restricted, requested):

   199     """

   200     Returns True if this field should be used to descend deeper for

   201     select_related() purposes. Used by both the query construction code

   202     (sql.query.fill_related_selections()) and the model instance creation code

   203     (query.get_cached_row()).

   204     """

   205     if not field.rel:

   206         return False

   207     if field.rel.parent_link:

   208         return False

   209     if restricted and field.name not in requested:

   210         return False

   211     if not restricted and field.null:

   212         return False

   213     return True

   214 

   215 # This function is needed because data descriptors must be defined on a class

   216 # object, not an instance, to have any effect.

   217 

   218 def deferred_class_factory(model, attrs):

   219     """

   220     Returns a class object that is a copy of "model" with the specified "attrs"

   221     being replaced with DeferredAttribute objects. The "pk_value" ties the

   222     deferred attributes to a particular instance of the model.

   223     """

   224     class Meta:

   225         pass

   226     setattr(Meta, "proxy", True)

   227     setattr(Meta, "app_label", model._meta.app_label)

   228 

   229     # The app_cache wants a unique name for each model, otherwise the new class

   230     # won't be created (we get an old one back). Therefore, we generate the

   231     # name using the passed in attrs. It's OK to reuse an old case if the attrs

   232     # are identical.

   233     name = "%s_Deferred_%s" % (model.__name__, '_'.join(sorted(list(attrs))))

   234 

   235     overrides = dict([(attr, DeferredAttribute(attr, model))

   236             for attr in attrs])

   237     overrides["Meta"] = Meta

   238     overrides["__module__"] = model.__module__

   239     overrides["_deferred"] = True

   240     return type(name, (model,), overrides)

   241 

   242 # The above function is also used to unpickle model instances with deferred

   243 # fields.

   244 deferred_class_factory.__safe_for_unpickling__ = True