various data structures used in query construction factored out from django db models query to avoid making the main module very large andor so that they can be used by other modules without getting into circular import difficulties pathinfo is used when converting lookups fksomecol the contents describe the relation in model terms model options and fields for both sides of the relation the joinfield is the field backing the relation encapsulate filters as objects that can then be combined logically using and connection types we must promote any new joins to left outer joins so that when q is used as an expression rows aren t filtered due to joins recursively yield this q object and all subexpressions in depthfirst order use the lookup do a database query to check if the expressions of the q instance matches against the expressions avoid circular imports this will raise a fielderror if a field is missing in against a wrapper for a deferredloading field when the value is read from this object the first time the query is executed retrieve and caches the value from the datastore on the first lookup return the cached value let s see if the field is part of the parent chain if so we might be able to reuse the already loaded value refs 18343 check if the field value can be fetched from a parent field already loaded in the instance this can be done if the tobe fetched field is a primary key field hook used in registerlookupmixin to return partial functions depending on the caller type instance or class of models field merge dicts in reverse to preference the order of the original list e g mergedictsa b will preference the keys in a over those in b remove given lookup from cls lookups for use in tests only as it s not threadsafe remove given lookup from instance lookups for use in tests only as it s not threadsafe return true if this field should be used to descend deeper for selectrelated purposes used by both the query construction code compiler getrelatedselections and the model instance creation code compiler klassinfo arguments field the field to be checked restricted a boolean field indicating if the field list has been manually restricted using a requested clause requested the selectrelated dictionary selectmask the dictionary of selected fields reverse boolean true if we are checking a reverse select related check if the lookupparts contains references to the given annotations set because the lookupsep is contained in the default annotation names check each prefix of the lookupparts for a match check that self model is compatible with targetopts compatibility is ok if 1 model and opts match where proxy inheritance is removed 2 model is parent of opts model or the other way around if the field is a primary key then doing a query against the field s model is ok too consider the case class restaurantmodels model place onetoonefieldplace primarykeytrue restaurant objects filterpkinrestaurant objects all if we didn t have the primary key check then pkin placein would give place s opts as the target opts but restaurant isn t compatible with that this logic applies only to primary keys as when doing inqs we are going to turn this into inqs values pk later on specify custom filtering in the on clause of sql joins def initself relationname conditionq if not relationname raise valueerrorrelationname cannot be empty self relationname relationname self alias none if not isinstancecondition q raise valueerrorcondition argument must be a q instance condition and resolvedcondition have to be stored independently as the former must remain unchanged for join eq to remain stable and reusable even once their filteredrelation are resolved self condition condition self resolvedcondition none def eqself other if not isinstanceother self class return notimplemented return self relationname other relationname and self alias other alias and self condition other condition def cloneself clone filteredrelationself relationname conditionself condition clone alias self alias if resolvedcondition self resolvedcondition is not none clone resolvedcondition resolvedcondition clone return clone def relabeledcloneself changemap clone self clone if resolvedcondition clone resolvedcondition clone resolvedcondition resolvedcondition relabeledclonechangemap return clone def resolveexpressionself query reuse args kwargs clone self clone clone resolvedcondition query buildfilter self condition canreusereuse allowjoinstrue splitsubqfalse updatejointypesfalse 0 return clone def assqlself compiler connection return compiler compileself resolvedcondition pathinfo is used when converting lookups fk__somecol the contents describe the relation in model terms model options and fields for both sides of the relation the join_field is the field backing the relation encapsulate filters as objects that can then be combined logically using and connection types we must promote any new joins to left outer joins so that when q is used as an expression rows aren t filtered due to joins recursively yield this q object and all subexpressions in depth first order use the lookup do a database query to check if the expressions of the q instance matches against the expressions avoid circular imports this will raise a fielderror if a field is missing in against a wrapper for a deferred loading field when the value is read from this object the first time the query is executed retrieve and caches the value from the datastore on the first lookup return the cached value let s see if the field is part of the parent chain if so we might be able to reuse the already loaded value refs 18343 check if the field value can be fetched from a parent field already loaded in the instance this can be done if the to be fetched field is a primary key field hook used in registerlookupmixin to return partial functions depending on the caller type instance or class of models field merge dicts in reverse to preference the order of the original list e g merge_dicts a b will preference the keys in a over those in b remove given lookup from cls lookups for use in tests only as it s not thread safe remove given lookup from instance lookups for use in tests only as it s not thread safe return true if this field should be used to descend deeper for select_related purposes used by both the query construction code compiler get_related_selections and the model instance creation code compiler klass_info arguments field the field to be checked restricted a boolean field indicating if the field list has been manually restricted using a requested clause requested the select_related dictionary select_mask the dictionary of selected fields reverse boolean true if we are checking a reverse select related check if the lookup_parts contains references to the given annotations set because the lookup_sep is contained in the default annotation names check each prefix of the lookup_parts for a match check that self model is compatible with target_opts compatibility is ok if 1 model and opts match where proxy inheritance is removed 2 model is parent of opts model or the other way around if the field is a primary key then doing a query against the field s model is ok too consider the case class restaurant models model place onetoonefield place primary_key true restaurant objects filter pk__in restaurant objects all if we didn t have the primary key check then pk__in place__in would give place s opts as the target opts but restaurant isn t compatible with that this logic applies only to primary keys as when doing __in qs we are going to turn this into __in qs values pk later on specify custom filtering in the on clause of sql joins condition and resolved_condition have to be stored independently as the former must remain unchanged for join __eq__ to remain stable and reusable even once their filtered_relation are resolved
import functools
import inspect
import logging
from collections import namedtuple

from django.core.exceptions import FieldError
from django.db import DEFAULT_DB_ALIAS, DatabaseError, connections
from django.db.models.constants import LOOKUP_SEP
from django.utils import tree
from django.utils.functional import cached_property
from django.utils.hashable import make_hashable

logger = logging.getLogger("django.db.models")




PathInfo = namedtuple(
    "PathInfo",
    "from_opts to_opts target_fields join_field m2m direct filtered_relation",
)


def subclasses(cls):
    yield cls
    for subclass in cls.__subclasses__():
        yield from subclasses(subclass)


class Q(tree.Node):
    

    
    AND = "AND"
    OR = "OR"
    XOR = "XOR"
    default = AND
    conditional = True

    def __init__(self, *args, _connector=None, _negated=False, **kwargs):
        super().__init__(
            children=[*args, *sorted(kwargs.items())],
            connector=_connector,
            negated=_negated,
        )

    def _combine(self, other, conn):
        if getattr(other, "conditional", False) is False:
            raise TypeError(other)
        if not self:
            return other.copy()
        if not other and isinstance(other, Q):
            return self.copy()

        obj = self.create(connector=conn)
        obj.add(self, conn)
        obj.add(other, conn)
        return obj

    def __or__(self, other):
        return self._combine(other, self.OR)

    def __and__(self, other):
        return self._combine(other, self.AND)

    def __xor__(self, other):
        return self._combine(other, self.XOR)

    def __invert__(self):
        obj = self.copy()
        obj.negate()
        return obj

    def resolve_expression(
        self, query=None, allow_joins=True, reuse=None, summarize=False, for_save=False
    ):
        
        
        clause, joins = query._add_q(
            self,
            reuse,
            allow_joins=allow_joins,
            split_subq=False,
            check_filterable=False,
            summarize=summarize,
        )
        query.promote_joins(joins)
        return clause

    def flatten(self):
        
        yield self
        for child in self.children:
            if isinstance(child, tuple):
                
                child = child[1]
            if hasattr(child, "flatten"):
                yield from child.flatten()
            else:
                yield child

    def check(self, against, using=DEFAULT_DB_ALIAS):
        
        
        from django.db.models import BooleanField, Value
        from django.db.models.functions import Coalesce
        from django.db.models.sql import Query
        from django.db.models.sql.constants import SINGLE

        query = Query(None)
        for name, value in against.items():
            if not hasattr(value, "resolve_expression"):
                value = Value(value)
            query.add_annotation(value, name, select=False)
        query.add_annotation(Value(1), "_check")
        
        if connections[using].features.supports_comparing_boolean_expr:
            query.add_q(Q(Coalesce(self, True, output_field=BooleanField())))
        else:
            query.add_q(self)
        compiler = query.get_compiler(using=using)
        try:
            return compiler.execute_sql(SINGLE) is not None
        except DatabaseError as e:
            logger.warning("Got a database error calling check() on %r: %s", self, e)
            return True

    def deconstruct(self):
        path = "%s.%s" % (self.__class__.__module__, self.__class__.__name__)
        if path.startswith("django.db.models.query_utils"):
            path = path.replace("django.db.models.query_utils", "django.db.models")
        args = tuple(self.children)
        kwargs = {}
        if self.connector != self.default:
            kwargs["_connector"] = self.connector
        if self.negated:
            kwargs["_negated"] = True
        return path, args, kwargs

    @cached_property
    def identity(self):
        path, args, kwargs = self.deconstruct()
        identity = [path, *kwargs.items()]
        for child in args:
            if isinstance(child, tuple):
                arg, value = child
                value = make_hashable(value)
                identity.append((arg, value))
            else:
                identity.append(child)
        return tuple(identity)

    def __eq__(self, other):
        if not isinstance(other, Q):
            return NotImplemented
        return other.identity == self.identity

    def __hash__(self):
        return hash(self.identity)


class DeferredAttribute:
    

    def __init__(self, field):
        self.field = field

    def __get__(self, instance, cls=None):
        
        if instance is None:
            return self
        data = instance.__dict__
        field_name = self.field.attname
        if field_name not in data:
            
            
            val = self._check_parent_chain(instance)
            if val is None:
                if instance.pk is None and self.field.generated:
                    raise AttributeError(
                        "Cannot read a generated field from an unsaved model."
                    )
                instance.refresh_from_db(fields=[field_name])
            else:
                data[field_name] = val
        return data[field_name]

    def _check_parent_chain(self, instance):
        
        opts = instance._meta
        link_field = opts.get_ancestor_link(self.field.model)
        if self.field.primary_key and self.field != link_field:
            return getattr(instance, link_field.attname)
        return None


class class_or_instance_method:
    

    def __init__(self, class_method, instance_method):
        self.class_method = class_method
        self.instance_method = instance_method

    def __get__(self, instance, owner):
        if instance is None:
            return functools.partial(self.class_method, owner)
        return functools.partial(self.instance_method, instance)


class RegisterLookupMixin:
    def _get_lookup(self, lookup_name):
        return self.get_lookups().get(lookup_name, None)

    @functools.cache
    def get_class_lookups(cls):
        class_lookups = [
            parent.__dict__.get("class_lookups", {}) for parent in inspect.getmro(cls)
        ]
        return cls.merge_dicts(class_lookups)

    def get_instance_lookups(self):
        class_lookups = self.get_class_lookups()
        if instance_lookups := getattr(self, "instance_lookups", None):
            return {**class_lookups, **instance_lookups}
        return class_lookups

    get_lookups = class_or_instance_method(get_class_lookups, get_instance_lookups)
    get_class_lookups = classmethod(get_class_lookups)

    def get_lookup(self, lookup_name):
        from django.db.models.lookups import Lookup

        found = self._get_lookup(lookup_name)
        if found is None and hasattr(self, "output_field"):
            return self.output_field.get_lookup(lookup_name)
        if found is not None and not issubclass(found, Lookup):
            return None
        return found

    def get_transform(self, lookup_name):
        from django.db.models.lookups import Transform

        found = self._get_lookup(lookup_name)
        if found is None and hasattr(self, "output_field"):
            return self.output_field.get_transform(lookup_name)
        if found is not None and not issubclass(found, Transform):
            return None
        return found

    @staticmethod
    def merge_dicts(dicts):
        
        merged = {}
        for d in reversed(dicts):
            merged.update(d)
        return merged

    @classmethod
    def _clear_cached_class_lookups(cls):
        for subclass in subclasses(cls):
            subclass.get_class_lookups.cache_clear()

    def register_class_lookup(cls, lookup, lookup_name=None):
        if lookup_name is None:
            lookup_name = lookup.lookup_name
        if "class_lookups" not in cls.__dict__:
            cls.class_lookups = {}
        cls.class_lookups[lookup_name] = lookup
        cls._clear_cached_class_lookups()
        return lookup

    def register_instance_lookup(self, lookup, lookup_name=None):
        if lookup_name is None:
            lookup_name = lookup.lookup_name
        if "instance_lookups" not in self.__dict__:
            self.instance_lookups = {}
        self.instance_lookups[lookup_name] = lookup
        return lookup

    register_lookup = class_or_instance_method(
        register_class_lookup, register_instance_lookup
    )
    register_class_lookup = classmethod(register_class_lookup)

    def _unregister_class_lookup(cls, lookup, lookup_name=None):
        
        if lookup_name is None:
            lookup_name = lookup.lookup_name
        del cls.class_lookups[lookup_name]
        cls._clear_cached_class_lookups()

    def _unregister_instance_lookup(self, lookup, lookup_name=None):
        
        if lookup_name is None:
            lookup_name = lookup.lookup_name
        del self.instance_lookups[lookup_name]

    _unregister_lookup = class_or_instance_method(
        _unregister_class_lookup, _unregister_instance_lookup
    )
    _unregister_class_lookup = classmethod(_unregister_class_lookup)


def select_related_descend(field, restricted, requested, select_mask, reverse=False):
    
    if not field.remote_field:
        return False
    if field.remote_field.parent_link and not reverse:
        return False
    if restricted:
        if reverse and field.related_query_name() not in requested:
            return False
        if not reverse and field.name not in requested:
            return False
    if not restricted and field.null:
        return False
    if (
        restricted
        and select_mask
        and field.name in requested
        and field not in select_mask
    ):
        raise FieldError(
            f"Field {field.model._meta.object_name}.{field.name} cannot be both "
            "deferred and traversed using select_related at the same time."
        )
    return True


def refs_expression(lookup_parts, annotations):
    
    for n in range(1, len(lookup_parts) + 1):
        level_n_lookup = LOOKUP_SEP.join(lookup_parts[0:n])
        if annotations.get(level_n_lookup):
            return level_n_lookup, lookup_parts[n:]
    return None, ()


def check_rel_lookup_compatibility(model, target_opts, field):
    

    def check(opts):
        return (
            model._meta.concrete_model == opts.concrete_model
            or opts.concrete_model in model._meta.get_parent_list()
            or model in opts.get_parent_list()
        )

    
    
    
    
    
    
    
    
    
    return check(target_opts) or (
        getattr(field, "primary_key", False) and check(field.model._meta)
    )


class FilteredRelation:
    

    def __init__(self, relation_name, *, condition=Q()):
        if not relation_name:
            raise ValueError("relation_name cannot be empty.")
        self.relation_name = relation_name
        self.alias = None
        if not isinstance(condition, Q):
            raise ValueError("condition argument must be a Q() instance.")
        
        
        
        self.condition = condition
        self.resolved_condition = None

    def __eq__(self, other):
        if not isinstance(other, self.__class__):
            return NotImplemented
        return (
            self.relation_name == other.relation_name
            and self.alias == other.alias
            and self.condition == other.condition
        )

    def clone(self):
        clone = FilteredRelation(self.relation_name, condition=self.condition)
        clone.alias = self.alias
        if (resolved_condition := self.resolved_condition) is not None:
            clone.resolved_condition = resolved_condition.clone()
        return clone

    def relabeled_clone(self, change_map):
        clone = self.clone()
        if resolved_condition := clone.resolved_condition:
            clone.resolved_condition = resolved_condition.relabeled_clone(change_map)
        return clone

    def resolve_expression(self, query, reuse, *args, **kwargs):
        clone = self.clone()
        clone.resolved_condition = query.build_filter(
            self.condition,
            can_reuse=reuse,
            allow_joins=True,
            split_subq=False,
            update_join_types=False,
        )[0]
        return clone

    def as_sql(self, compiler, connection):
        return compiler.compile(self.resolved_condition)