12
12
from django.utils.datastructures import SortedDict
13
from django.utils.encoding import force_unicode
13
from django.utils.encoding import force_text
14
14
from django.utils.tree import Node
15
from django.utils import six
15
16
from django.db import connections, DEFAULT_DB_ALIAS
16
17
from django.db.models import signals
18
from django.db.models.constants import LOOKUP_SEP
17
19
from django.db.models.expressions import ExpressionNode
18
20
from django.db.models.fields import FieldDoesNotExist
19
from django.db.models.query_utils import InvalidQuery
20
21
from django.db.models.sql import aggregates as base_aggregates_module
21
from django.db.models.sql.constants import *
22
from django.db.models.sql.constants import (QUERY_TERMS, ORDER_DIR, SINGLE,
23
ORDER_PATTERN, JoinInfo)
22
24
from django.db.models.sql.datastructures import EmptyResultSet, Empty, MultiJoin
23
25
from django.db.models.sql.expressions import SQLEvaluator
24
26
from django.db.models.sql.where import (WhereNode, Constraint, EverythingNode,
101
104
def __init__(self, model, where=WhereNode):
102
105
self.model = model
103
self.alias_refcount = SortedDict()
104
self.alias_map = {} # Maps alias to join information
106
self.alias_refcount = {}
107
# alias_map is the most important data structure regarding joins.
108
# It's used for recording which joins exist in the query and what
109
# type they are. The key is the alias of the joined table (possibly
110
# the table name) and the value is JoinInfo from constants.py.
105
112
self.table_map = {} # Maps table names to list of aliases.
106
113
self.join_map = {}
107
self.rev_join_map = {} # Reverse of join_map.
108
self.quote_cache = {}
109
114
self.default_cols = True
110
115
self.default_ordering = True
111
116
self.standard_ordering = True
112
117
self.ordering_aliases = []
113
self.select_fields = []
114
118
self.related_select_fields = []
115
119
self.dupe_avoidance = {}
116
120
self.used_aliases = set()
465
466
conjunction = (connector == AND)
467
# Add the joins in the rhs query into the new query.
467
469
for alias in rhs.tables:
468
470
if not rhs.alias_refcount[alias]:
469
471
# An unused alias.
471
promote = (rhs.alias_map[alias][JOIN_TYPE] == self.LOUTER)
472
lhs, table, lhs_col, col = rhs.rev_join_map[alias]
473
table, _, join_type, lhs, lhs_col, col, _ = rhs.alias_map[alias]
474
promote = join_type == self.LOUTER
473
475
# If the left side of the join was already relabeled, use the
475
477
lhs = change_map.get(lhs, lhs)
476
478
new_alias = self.join((lhs, table, lhs_col, col),
477
(conjunction and not first), used, promote, not conjunction)
479
conjunction and not first, used, promote, not conjunction)
478
480
used.add(new_alias)
479
481
change_map[alias] = new_alias
583
585
for name in parts[:-1]:
584
586
old_model = cur_model
585
587
source = opts.get_field_by_name(name)[0]
586
cur_model = source.rel.to
588
if is_reverse_o2o(source):
589
cur_model = source.model
591
cur_model = source.rel.to
587
592
opts = cur_model._meta
588
593
# Even if we're "just passing through" this model, we must add
589
594
# both the current model's pk and the related reference field
590
# to the things we select.
591
must_include[old_model].add(source)
595
# (if it's not a reverse relation) to the things we select.
596
if not is_reverse_o2o(source):
597
must_include[old_model].add(source)
592
598
add_to_dict(must_include, cur_model, opts.pk)
593
599
field, model, _, _ = opts.get_field_by_name(parts[-1])
594
600
if model is None:
595
601
model = cur_model
596
add_to_dict(seen, model, field)
602
if not is_reverse_o2o(field):
603
add_to_dict(seen, model, field)
599
606
# We need to load all fields for each model, except those that
601
608
# slight complexity here is handling fields that exist on parent
604
for model, values in seen.iteritems():
611
for model, values in six.iteritems(seen):
605
612
for field, m in model._meta.get_fields_with_model():
606
613
if field in values:
608
615
add_to_dict(workset, m or model, field)
609
for model, values in must_include.iteritems():
616
for model, values in six.iteritems(must_include):
610
617
# If we haven't included a model in workset, we don't add the
611
618
# corresponding must_include fields for that model, since an
612
619
# empty set means "include all fields". That's why there's no
613
620
# "else" branch here.
614
621
if model in workset:
615
622
workset[model].update(values)
616
for model, values in workset.iteritems():
623
for model, values in six.iteritems(workset):
617
624
callback(target, model, values)
619
for model, values in must_include.iteritems():
626
for model, values in six.iteritems(must_include):
620
627
if model in seen:
621
628
seen[model].update(values)
680
687
""" Decreases the reference count for this alias. """
681
688
self.alias_refcount[alias] -= amount
683
def promote_alias(self, alias, unconditional=False):
685
Promotes the join type of an alias to an outer join if it's possible
686
for the join to contain NULL values on the left. If 'unconditional' is
687
False, the join is only promoted if it is nullable, otherwise it is
690
Returns True if the join was promoted by this call.
692
if ((unconditional or self.alias_map[alias][NULLABLE]) and
693
self.alias_map[alias][JOIN_TYPE] != self.LOUTER):
694
data = list(self.alias_map[alias])
695
data[JOIN_TYPE] = self.LOUTER
696
self.alias_map[alias] = tuple(data)
700
def promote_alias_chain(self, chain, must_promote=False):
702
Walks along a chain of aliases, promoting the first nullable join and
703
any joins following that. If 'must_promote' is True, all the aliases in
704
the chain are promoted.
707
if self.promote_alias(alias, must_promote):
690
def promote_joins(self, aliases, unconditional=False):
692
Promotes recursively the join type of given aliases and its children to
693
an outer join. If 'unconditional' is False, the join is only promoted if
694
it is nullable or the parent join is an outer join.
696
Note about join promotion: When promoting any alias, we make sure all
697
joins which start from that alias are promoted, too. When adding a join
698
in join(), we make sure any join added to already existing LOUTER join
699
is generated as LOUTER. This ensures we don't ever have broken join
700
chains which contain first a LOUTER join, then an INNER JOIN, that is
701
this kind of join should never be generated: a LOUTER b INNER c. The
702
reason for avoiding this type of join chain is that the INNER after
703
the LOUTER will effectively remove any effect the LOUTER had.
705
aliases = list(aliases)
707
alias = aliases.pop(0)
708
if self.alias_map[alias].rhs_join_col is None:
709
# This is the base table (first FROM entry) - this table
710
# isn't really joined at all in the query, so we should not
711
# alter its join type.
713
parent_alias = self.alias_map[alias].lhs_alias
714
parent_louter = (parent_alias
715
and self.alias_map[parent_alias].join_type == self.LOUTER)
716
already_louter = self.alias_map[alias].join_type == self.LOUTER
717
if ((unconditional or self.alias_map[alias].nullable
718
or parent_louter) and not already_louter):
719
data = self.alias_map[alias]._replace(join_type=self.LOUTER)
720
self.alias_map[alias] = data
721
# Join type of 'alias' changed, so re-examine all aliases that
724
join for join in self.alias_map.keys()
725
if (self.alias_map[join].lhs_alias == alias
726
and join not in aliases))
710
728
def reset_refcounts(self, to_counts):
724
742
then and which ones haven't been used and promotes all of those
725
743
aliases, plus any children of theirs in the alias tree, to outer joins.
727
# FIXME: There's some (a lot of!) overlap with the similar OR promotion
728
# in add_filter(). It's not quite identical, but is very similar. So
729
# pulling out the common bits is something for later.
731
745
for alias in self.tables:
732
if alias not in used_aliases:
734
if (alias not in initial_refcounts or
746
if alias in used_aliases and (alias not in initial_refcounts or
735
747
self.alias_refcount[alias] == initial_refcounts[alias]):
736
parent = self.alias_map[alias][LHS_ALIAS]
737
must_promote = considered.get(parent, False)
738
promoted = self.promote_alias(alias, must_promote)
739
considered[alias] = must_promote or promoted
748
self.promote_joins([alias])
741
750
def change_aliases(self, change_map):
766
775
col.relabel_aliases(change_map)
768
777
# 2. Rename the alias in the internal table/alias datastructures.
769
for old_alias, new_alias in change_map.iteritems():
770
alias_data = list(self.alias_map[old_alias])
771
alias_data[RHS_ALIAS] = new_alias
773
t = self.rev_join_map[old_alias]
774
data = list(self.join_map[t])
775
data[data.index(old_alias)] = new_alias
776
self.join_map[t] = tuple(data)
777
self.rev_join_map[new_alias] = t
778
del self.rev_join_map[old_alias]
778
for k, aliases in self.join_map.items():
779
aliases = tuple([change_map.get(a, a) for a in aliases])
780
self.join_map[k] = aliases
781
for old_alias, new_alias in six.iteritems(change_map):
782
alias_data = self.alias_map[old_alias]
783
alias_data = alias_data._replace(rhs_alias=new_alias)
779
784
self.alias_refcount[new_alias] = self.alias_refcount[old_alias]
780
785
del self.alias_refcount[old_alias]
781
self.alias_map[new_alias] = tuple(alias_data)
786
self.alias_map[new_alias] = alias_data
782
787
del self.alias_map[old_alias]
784
table_aliases = self.table_map[alias_data[TABLE_NAME]]
789
table_aliases = self.table_map[alias_data.table_name]
785
790
for pos, alias in enumerate(table_aliases):
786
791
if alias == old_alias:
787
792
table_aliases[pos] = new_alias
795
800
self.included_inherited_models[key] = change_map[alias]
797
802
# 3. Update any joins that refer to the old alias.
798
for alias, data in self.alias_map.iteritems():
799
lhs = data[LHS_ALIAS]
803
for alias, data in six.iteritems(self.alias_map):
800
805
if lhs in change_map:
802
data[LHS_ALIAS] = change_map[lhs]
803
self.alias_map[alias] = tuple(data)
806
data = data._replace(lhs_alias=change_map[lhs])
807
self.alias_map[alias] = data
805
809
def bump_prefix(self, exceptions=()):
846
850
count. Note that after execution, the reference counts are zeroed, so
847
851
tables added in compiler will not be seen by this method.
849
return len([1 for count in self.alias_refcount.itervalues() if count])
853
return len([1 for count in self.alias_refcount.values() if count])
851
855
def join(self, connection, always_create=False, exclusions=(),
852
856
promote=False, outer_if_first=False, nullable=False, reuse=None):
878
882
LOUTER join type. This is used when joining certain types of querysets
879
883
and Q-objects together.
885
A join is always created as LOUTER if the lhs alias is LOUTER to make
886
sure we do not generate chains like a LOUTER b INNER c.
881
888
If 'nullable' is True, the join can potentially involve NULL values and
882
889
is a candidate for promotion (to "left outer") when combining querysets.
884
891
lhs, table, lhs_col, col = connection
885
892
if lhs in self.alias_map:
886
lhs_table = self.alias_map[lhs][TABLE_NAME]
893
lhs_table = self.alias_map[lhs].table_name
896
903
if not always_create:
897
904
for alias in self.join_map.get(t_ident, ()):
898
905
if alias not in exclusions:
899
if lhs_table and not self.alias_refcount[self.alias_map[alias][LHS_ALIAS]]:
906
if lhs_table and not self.alias_refcount[self.alias_map[alias].lhs_alias]:
900
907
# The LHS of this join tuple is no longer part of the
901
908
# query, so skip this possibility.
903
if self.alias_map[alias][LHS_ALIAS] != lhs:
910
if self.alias_map[alias].lhs_alias != lhs:
905
912
self.ref_alias(alias)
907
self.promote_alias(alias)
913
if promote or (lhs and self.alias_map[lhs].join_type == self.LOUTER):
914
self.promote_joins([alias])
910
917
# No reuse is possible, so we need a new alias.
913
920
# Not all tables need to be joined to anything. No join type
914
921
# means the later columns are ignored.
916
elif promote or outer_if_first:
923
elif (promote or outer_if_first
924
or self.alias_map[lhs].join_type == self.LOUTER):
925
# We need to use LOUTER join if asked by promote or outer_if_first,
926
# or if the LHS table is left-joined in the query. Adding inner join
927
# to an existing outer join effectively cancels the effect of the
917
929
join_type = self.LOUTER
919
931
join_type = self.INNER
920
join = (table, alias, join_type, lhs, lhs_col, col, nullable)
932
join = JoinInfo(table, alias, join_type, lhs, lhs_col, col, nullable)
921
933
self.alias_map[alias] = join
922
934
if t_ident in self.join_map:
923
935
self.join_map[t_ident] += (alias,)
925
937
self.join_map[t_ident] = (alias,)
926
self.rev_join_map[alias] = t_ident
929
940
def setup_inherited_models(self):
938
949
whereas column determination is a later part, and side-effect, of
941
opts = self.model._meta
952
# Skip all proxy models
953
opts = self.model._meta.concrete_model._meta
942
954
root_alias = self.tables[0]
943
955
seen = {None: root_alias}
945
# Skip all proxy to the root proxied model
946
proxied_model = opts.concrete_model
948
957
for field, model in opts.get_fields_with_model():
949
958
if model not in seen:
950
if model is proxied_model:
951
seen[model] = root_alias
953
link_field = opts.get_ancestor_link(model)
954
seen[model] = self.join((root_alias, model._meta.db_table,
955
link_field.column, model._meta.pk.column))
959
link_field = opts.get_ancestor_link(model)
960
seen[model] = self.join((root_alias, model._meta.db_table,
961
link_field.column, model._meta.pk.column))
956
962
self.included_inherited_models = seen
958
964
def remove_inherited_models(self):
1013
1019
# If the aggregate references a model or field that requires a join,
1014
1020
# those joins must be LEFT OUTER - empty join rows must be returned
1015
1021
# in order for zeros to be returned for those aggregates.
1016
for column_alias in join_list:
1017
self.promote_alias(column_alias, unconditional=True)
1022
self.promote_joins(join_list, True)
1019
1024
col = (join_list[-1], col)
1099
1104
value = value()
1100
1105
elif isinstance(value, ExpressionNode):
1101
1106
# If value is a query expression, evaluate it
1102
value = SQLEvaluator(value, self)
1107
value = SQLEvaluator(value, self, reuse=can_reuse)
1103
1108
having_clause = value.contains_aggregate
1109
# For Oracle '' is equivalent to null. The check needs to be done
1110
# at this stage because join promotion can't be done at compiler
1111
# stage. Using DEFAULT_DB_ALIAS isn't nice, but it is the best we
1112
# can do here. Similar thing is done in is_nullable(), too.
1113
if (connections[DEFAULT_DB_ALIAS].features.interprets_empty_strings_as_nulls and
1114
lookup_type == 'exact' and value == ''):
1116
lookup_type = 'isnull'
1105
1117
for alias, aggregate in self.aggregates.items():
1106
1118
if alias in (parts[0], LOOKUP_SEP.join(parts)):
1107
1119
entry = self.where_class()
1120
1132
parts, opts, alias, True, allow_many, allow_explicit_fk=True,
1121
1133
can_reuse=can_reuse, negate=negate,
1122
1134
process_extras=process_extras)
1123
except MultiJoin, e:
1135
except MultiJoin as e:
1124
1136
self.split_exclude(filter_expr, LOOKUP_SEP.join(parts[:e.level]),
1150
1162
# join list) an outer join.
1151
1163
join_it = iter(join_list)
1152
1164
table_it = iter(self.tables)
1153
join_it.next(), table_it.next()
1165
next(join_it), next(table_it)
1154
1166
unconditional = False
1155
1167
for join in join_it:
1156
table = table_it.next()
1168
table = next(table_it)
1157
1169
# Once we hit an outer join, all subsequent joins must
1158
1170
# also be promoted, regardless of whether they have been
1159
1171
# promoted as a result of this pass through the tables.
1160
1172
unconditional = (unconditional or
1161
self.alias_map[join][JOIN_TYPE] == self.LOUTER)
1173
self.alias_map[join].join_type == self.LOUTER)
1162
1174
if join == table and self.alias_refcount[join] > 1:
1163
1175
# We have more than one reference to this join table.
1164
1176
# This means that we are dealing with two different query
1165
1177
# subtrees, so we don't need to do any join promotion.
1167
join_promote = join_promote or self.promote_alias(join, unconditional)
1179
join_promote = join_promote or self.promote_joins([join], unconditional)
1168
1180
if table != join:
1169
table_promote = self.promote_alias(table)
1181
table_promote = self.promote_joins([table])
1170
1182
# We only get here if we have found a table that exists
1171
1183
# in the join list, but isn't on the original tables list.
1172
1184
# This means we've reached the point where we only have
1173
1185
# new tables, so we can break out of this promotion loop.
1175
self.promote_alias_chain(join_it, join_promote)
1176
self.promote_alias_chain(table_it, table_promote or join_promote)
1187
self.promote_joins(join_it, join_promote)
1188
self.promote_joins(table_it, table_promote or join_promote)
1178
1190
if having_clause or force_having:
1179
1191
if (alias, col) not in self.group_by:
1188
self.promote_alias_chain(join_list)
1200
self.promote_joins(join_list)
1189
1201
if lookup_type != 'isnull':
1190
1202
if len(join_list) > 1:
1191
for alias in join_list:
1192
if self.alias_map[alias][JOIN_TYPE] == self.LOUTER:
1193
j_col = self.alias_map[alias][RHS_JOIN_COL]
1203
for j_alias in join_list:
1204
if self.alias_map[j_alias].join_type == self.LOUTER:
1205
j_col = self.alias_map[j_alias].rhs_join_col
1206
# The join promotion logic should never produce
1207
# a LOUTER join for the base join - assert that.
1208
assert j_col is not None
1194
1209
entry = self.where_class()
1196
(Constraint(alias, j_col, None), 'isnull', True),
1211
(Constraint(j_alias, j_col, None), 'isnull', True),
1200
1215
self.where.add(entry, AND)
1202
if not (lookup_type == 'in'
1203
and not hasattr(value, 'as_sql')
1204
and not hasattr(value, '_as_sql')
1205
and not value) and field.null:
1206
# Leaky abstraction artifact: We have to specifically
1207
# exclude the "foo__in=[]" case from this handling, because
1208
# it's short-circuited in the Where class.
1209
# We also need to handle the case where a subquery is provided
1217
if self.is_nullable(field):
1218
# In SQL NULL = anyvalue returns unknown, and NOT unknown
1219
# is still unknown. However, in Python None = anyvalue is False
1220
# (and not False is True...), and we want to return this Python's
1221
# view of None handling. So we need to specifically exclude the
1222
# NULL values, and because we are inside NOT branch they will
1223
# be included in the final resultset. We are essentially creating
1224
# SQL like this here: NOT (col IS NOT NULL), where the first NOT
1225
# is added in upper layers of the code.
1210
1226
self.where.add((Constraint(alias, col, None), 'isnull', False), AND)
1212
1228
if can_reuse is not None:
1578
1595
# comparison to NULL (e.g. in
1579
1596
# Tag.objects.exclude(parent__parent__name='t1'), a tag with no parent
1580
1597
# would otherwise be overlooked).
1581
active_positions = [pos for (pos, count) in
1582
enumerate(query.alias_refcount.itervalues()) if count]
1583
if active_positions[-1] > 1:
1598
active_positions = len([count for count
1599
in query.alias_refcount.items() if count])
1600
if active_positions > 1:
1584
1601
self.add_filter(('%s__isnull' % prefix, False), negate=True,
1585
1602
trim=True, can_reuse=can_reuse)
1620
1637
return not self.low_mark and self.high_mark is None
1639
def clear_select_clause(self):
1641
Removes all fields from SELECT clause.
1644
self.select_fields = []
1645
self.default_cols = False
1646
self.select_related = False
1647
self.set_extra_mask(())
1648
self.set_aggregate_mask(())
1622
1650
def clear_select_fields(self):
1624
1652
Clears the list of fields to select (but not extra_select columns).
1652
1680
col = target.column
1653
1681
if len(joins) > 1:
1654
1682
join = self.alias_map[final_alias]
1655
if col == join[RHS_JOIN_COL]:
1683
if col == join.rhs_join_col:
1656
1684
self.unref_alias(final_alias)
1657
final_alias = join[LHS_ALIAS]
1658
col = join[LHS_JOIN_COL]
1685
final_alias = join.lhs_alias
1686
col = join.lhs_join_col
1659
1687
joins = joins[:-1]
1660
self.promote_alias_chain(joins[1:])
1688
self.promote_joins(joins[1:])
1661
1689
self.select.append((final_alias, col))
1662
1690
self.select_fields.append(field)
1663
1691
except MultiJoin:
1664
1692
raise FieldError("Invalid field name: '%s'" % name)
1665
1693
except FieldError:
1666
names = opts.get_all_field_names() + self.extra.keys() + self.aggregate_select.keys()
1668
raise FieldError("Cannot resolve keyword %r into field. "
1669
"Choices are: %s" % (name, ", ".join(names)))
1694
if LOOKUP_SEP in name:
1695
# For lookups spanning over relationships, show the error
1696
# from the model on which the lookup failed.
1699
names = sorted(opts.get_all_field_names() + list(self.extra)
1700
+ list(self.aggregate_select))
1701
raise FieldError("Cannot resolve keyword %r into field. "
1702
"Choices are: %s" % (name, ", ".join(names)))
1670
1703
self.remove_inherited_models()
1672
1705
def add_ordering(self, *ordering):
1779
1812
param_iter = iter([])
1780
1813
for name, entry in select.items():
1781
entry = force_unicode(entry)
1814
entry = force_text(entry)
1782
1815
entry_params = []
1783
1816
pos = entry.find("%s")
1784
1817
while pos != -1:
1785
entry_params.append(param_iter.next())
1818
entry_params.append(next(param_iter))
1786
1819
pos = entry.find("%s", pos + 2)
1787
1820
select_pairs[name] = (entry, entry_params)
1788
1821
# This is order preserving, since self.extra_select is a SortedDict.
1854
1887
If no fields are marked for deferral, returns an empty dictionary.
1857
self.deferred_to_data(collection, self.get_loaded_field_names_cb)
1889
# We cache this because we call this function multiple times
1890
# (compiler.fill_related_selections, query.iterator)
1892
return self._loaded_field_names_cache
1893
except AttributeError:
1895
self.deferred_to_data(collection, self.get_loaded_field_names_cb)
1896
self._loaded_field_names_cache = collection
1860
1899
def get_loaded_field_names_cb(self, target, model, fields):
1929
1968
alias = self.get_initial_alias()
1930
1969
field, col, opts, joins, last, extra = self.setup_joins(
1931
1970
start.split(LOOKUP_SEP), opts, alias, False)
1932
select_col = self.alias_map[joins[1]][LHS_JOIN_COL]
1971
select_col = self.alias_map[joins[1]].lhs_join_col
1933
1972
select_alias = alias
1935
1974
# The call to setup_joins added an extra reference to everything in
1942
1981
# is *always* the same value as lhs).
1943
1982
for alias in joins[1:]:
1944
1983
join_info = self.alias_map[alias]
1945
if (join_info[LHS_JOIN_COL] != select_col
1946
or join_info[JOIN_TYPE] != self.INNER):
1984
if (join_info.lhs_join_col != select_col
1985
or join_info.join_type != self.INNER):
1948
1987
self.unref_alias(select_alias)
1949
select_alias = join_info[RHS_ALIAS]
1950
select_col = join_info[RHS_JOIN_COL]
1988
select_alias = join_info.rhs_alias
1989
select_col = join_info.rhs_join_col
1951
1990
self.select = [(select_alias, select_col)]
1952
1991
self.remove_inherited_models()
1993
def is_nullable(self, field):
1995
A helper to check if the given field should be treated as nullable.
1997
Some backends treat '' as null and Django treats such fields as
1998
nullable for those backends. In such situations field.null can be
1999
False even if we should treat the field as nullable.
2001
# We need to use DEFAULT_DB_ALIAS here, as QuerySet does not have
2002
# (nor should it have) knowledge of which connection is going to be
2003
# used. The proper fix would be to defer all decisions where
2004
# is_nullable() is needed to the compiler stage, but that is not easy
2006
if ((connections[DEFAULT_DB_ALIAS].features.interprets_empty_strings_as_nulls)
2007
and field.empty_strings_allowed):
1955
2012
def get_order_dir(field, default='ASC'):