| 1 |
""" |
| 2 |
A class for storing a tree graph. Primarily used for filter constructs in the |
| 3 |
ORM. |
| 4 |
""" |
| 5 |
|
| 6 |
import copy |
| 7 |
|
| 8 |
from django.utils.hashable import make_hashable |
| 9 |
|
| 10 |
|
| 11 |
class Node: |
| 12 |
""" |
| 13 |
A single internal node in the tree graph. A Node should be viewed as a |
| 14 |
connection (the root) with the children being either leaf nodes or other |
| 15 |
Node instances. |
| 16 |
""" |
| 17 |
|
| 18 |
# Standard connector type. Clients usually won't use this at all and |
| 19 |
# subclasses will usually override the value. |
| 20 |
default = "DEFAULT" |
| 21 |
|
| 22 |
def __init__(self, children=None, connector=None, negated=False): |
| 23 |
"""Construct a new Node. If no connector is given, use the default.""" |
| 24 |
self.children = children[:] if children else [] |
| 25 |
self.connector = connector or self.default |
| 26 |
self.negated = negated |
| 27 |
|
| 28 |
@classmethod |
| 29 |
def create(cls, children=None, connector=None, negated=False): |
| 30 |
""" |
| 31 |
Create a new instance using Node() instead of __init__() as some |
| 32 |
subclasses, e.g. django.db.models.query_utils.Q, may implement a custom |
| 33 |
__init__() with a signature that conflicts with the one defined in |
| 34 |
Node.__init__(). |
| 35 |
""" |
| 36 |
obj = Node(children, connector or cls.default, negated) |
| 37 |
obj.__class__ = cls |
| 38 |
return obj |
| 39 |
|
| 40 |
def __str__(self): |
| 41 |
template = "(NOT (%s: %s))" if self.negated else "(%s: %s)" |
| 42 |
return template % (self.connector, ", ".join(str(c) for c in self.children)) |
| 43 |
|
| 44 |
def __repr__(self): |
| 45 |
return "<%s: %s>" % (self.__class__.__name__, self) |
| 46 |
|
| 47 |
def __copy__(self): |
| 48 |
obj = self.create(connector=self.connector, negated=self.negated) |
| 49 |
obj.children = self.children # Don't [:] as .__init__() via .create() does. |
| 50 |
return obj |
| 51 |
|
| 52 |
copy = __copy__ |
| 53 |
|
| 54 |
def __deepcopy__(self, memodict): |
| 55 |
obj = self.create(connector=self.connector, negated=self.negated) |
| 56 |
obj.children = copy.deepcopy(self.children, memodict) |
| 57 |
return obj |
| 58 |
|
| 59 |
def __len__(self): |
| 60 |
"""Return the number of children this node has.""" |
| 61 |
return len(self.children) |
| 62 |
|
| 63 |
def __bool__(self): |
| 64 |
"""Return whether or not this node has children.""" |
| 65 |
return bool(self.children) |
| 66 |
|
| 67 |
def __contains__(self, other): |
| 68 |
"""Return True if 'other' is a direct child of this instance.""" |
| 69 |
return other in self.children |
| 70 |
|
| 71 |
def __eq__(self, other): |
| 72 |
return ( |
| 73 |
self.__class__ == other.__class__ |
| 74 |
and self.connector == other.connector |
| 75 |
and self.negated == other.negated |
| 76 |
and self.children == other.children |
| 77 |
) |
| 78 |
|
| 79 |
def __hash__(self): |
| 80 |
return hash( |
| 81 |
( |
| 82 |
self.__class__, |
| 83 |
self.connector, |
| 84 |
self.negated, |
| 85 |
*make_hashable(self.children), |
| 86 |
) |
| 87 |
) |
| 88 |
|
| 89 |
def add(self, data, conn_type): |
| 90 |
""" |
| 91 |
Combine this tree and the data represented by data using the |
| 92 |
connector conn_type. The combine is done by squashing the node other |
| 93 |
away if possible. |
| 94 |
|
| 95 |
This tree (self) will never be pushed to a child node of the |
| 96 |
combined tree, nor will the connector or negated properties change. |
| 97 |
|
| 98 |
Return a node which can be used in place of data regardless if the |
| 99 |
node other got squashed or not. |
| 100 |
""" |
| 101 |
if self.connector != conn_type: |
| 102 |
obj = self.copy() |
| 103 |
self.connector = conn_type |
| 104 |
self.children = [obj, data] |
| 105 |
return data |
| 106 |
elif ( |
| 107 |
isinstance(data, Node) |
| 108 |
and not data.negated |
| 109 |
and (data.connector == conn_type or len(data) == 1) |
| 110 |
): |
| 111 |
# We can squash the other node's children directly into this node. |
| 112 |
# We are just doing (AB)(CD) == (ABCD) here, with the addition that |
| 113 |
# if the length of the other node is 1 the connector doesn't |
| 114 |
# matter. However, for the len(self) == 1 case we don't want to do |
| 115 |
# the squashing, as it would alter self.connector. |
| 116 |
self.children.extend(data.children) |
| 117 |
return self |
| 118 |
else: |
| 119 |
# We could use perhaps additional logic here to see if some |
| 120 |
# children could be used for pushdown here. |
| 121 |
self.children.append(data) |
| 122 |
return data |
| 123 |
|
| 124 |
def negate(self): |
| 125 |
"""Negate the sense of the root connector.""" |
| 126 |
self.negated = not self.negated |