Coverage for adhoc-cicd-odoo-odoo / odoo / tools / set_expression.py: 76%
355 statements
« prev ^ index » next coverage.py v7.13.4, created at 2026-03-09 18:15 +0000
1from __future__ import annotations
3import ast
4from abc import ABC, abstractmethod
5import typing
7if typing.TYPE_CHECKING:
8 from collections.abc import Collection, Iterable
11class SetDefinitions:
12 """ A collection of set definitions, where each set is defined by an id, a
13 name, its supersets, and the sets that are disjoint with it. This object
14 is used as a factory to create set expressions, which are combinations of
15 named sets with union, intersection and complement.
16 """
17 __slots__ = ('__leaves',)
19 def __init__(self, definitions: dict[int, dict]):
20 """ Initialize the object with ``definitions``, a dict which maps each
21 set id to a dict with optional keys ``"ref"`` (value is the set's name),
22 ``"supersets"`` (value is a collection of set ids), and ``"disjoints"``
23 (value is a collection of set ids).
25 Here is an example of set definitions, with natural numbers (N), integer
26 numbers (Z), rational numbers (Q), irrational numbers (R\\Q), real
27 numbers (R), imaginary numbers (I) and complex numbers (C)::
29 {
30 1: {"ref": "N", "supersets": [2]},
31 2: {"ref": "Z", "supersets": [3]},
32 3: {"ref": "Q", "supersets": [4]},
33 4: {"ref": "R", "supersets": [6]},
34 5: {"ref": "I", "supersets": [6], "disjoints": [4]},
35 6: {"ref": "C"},
36 7: {"ref": "R\\Q", "supersets": [4]},
37 }
38 Representation:
39 ┌──────────────────────────────────────────┐
40 │ C ┌──────────────────────────┐ │
41 │ │ R ┌───────────────────┐ │ ┌──────┐ | "C"
42 │ │ │ Q ┌────────────┐ │ │ │ I | | "I" implied "C"
43 │ │ │ │ Z ┌─────┐ │ │ │ │ | | "R" implied "C"
44 │ │ │ │ │ N │ │ │ │ │ │ │ "Q" implied "R"
45 │ │ │ │ └─────┘ │ │ │ │ │ │ "R\\Q" implied "R"
46 │ │ │ └────────────┘ │ │ │ │ │ "Z" implied "Q"
47 │ │ └───────────────────┘ │ │ │ │ "N" implied "Z"
48 │ │ ┌───────────────┐ │ │ │ │
49 │ │ │ R\\Q │ │ │ │ │
50 │ │ └───────────────┘ │ └──────┘ │
51 │ └──────────────────────────┘ │
52 └──────────────────────────────────────────┘
53 """
54 self.__leaves: dict[int | str, Leaf] = {}
56 for leaf_id, info in definitions.items():
57 ref = info['ref']
58 assert ref != '*', "The set reference '*' is reserved for the universal set."
59 leaf = Leaf(leaf_id, ref)
60 self.__leaves[leaf_id] = leaf
61 self.__leaves[ref] = leaf
63 # compute transitive closure of subsets and supersets
64 subsets = {leaf.id: leaf.subsets for leaf in self.__leaves.values()}
65 supersets = {leaf.id: leaf.supersets for leaf in self.__leaves.values()}
66 for leaf_id, info in definitions.items():
67 for greater_id in info.get('supersets', ()):
68 # transitive closure: smaller_ids <= leaf_id <= greater_id <= greater_ids
69 smaller_ids = subsets[leaf_id]
70 greater_ids = supersets[greater_id]
71 for smaller_id in smaller_ids:
72 supersets[smaller_id].update(greater_ids)
73 for greater_id in greater_ids:
74 subsets[greater_id].update(smaller_ids)
76 # compute transitive closure of disjoint relation
77 disjoints = {leaf.id: leaf.disjoints for leaf in self.__leaves.values()}
78 for leaf_id, info in definitions.items():
79 for distinct_id in info.get('disjoints', set()):
80 # all subsets[leaf_id] are disjoint from all subsets[distinct_id]
81 left_ids = subsets[leaf_id]
82 right_ids = subsets[distinct_id]
83 for left_id in left_ids:
84 disjoints[left_id].update(right_ids)
85 for right_id in right_ids:
86 disjoints[right_id].update(left_ids)
88 @property
89 def empty(self) -> SetExpression:
90 return EMPTY_UNION
92 @property
93 def universe(self) -> SetExpression:
94 return UNIVERSAL_UNION
96 def parse(self, refs: str, raise_if_not_found: bool = True) -> SetExpression:
97 """ Return the set expression corresponding to ``refs``
99 :param str refs: comma-separated list of set references
100 optionally preceded by ``!`` (negative item). The result is
101 an union between positive item who intersect every negative
102 group.
103 (e.g. ``base.group_user,base.group_portal,!base.group_system``)
104 """
105 positives: list[Leaf] = []
106 negatives: list[Leaf] = []
107 for xmlid in refs.split(','):
108 if xmlid.startswith('!'):
109 negatives.append(~self.__get_leaf(xmlid[1:], raise_if_not_found))
110 else:
111 positives.append(self.__get_leaf(xmlid, raise_if_not_found))
113 if positives:
114 return Union(Inter([leaf] + negatives) for leaf in positives)
115 else:
116 return Union([Inter(negatives)])
118 def from_ids(self, ids: Iterable[int], keep_subsets: bool = False) -> SetExpression:
119 """ Return the set expression corresponding to given set ids. """
120 if keep_subsets: 120 ↛ 121line 120 didn't jump to line 121 because the condition on line 120 was never true
121 ids = set(ids)
122 ids = [leaf_id for leaf_id in ids if not any((self.__leaves[leaf_id].subsets - {leaf_id}) & ids)]
123 return Union(Inter([self.__leaves[leaf_id]]) for leaf_id in ids)
125 def from_key(self, key: str) -> SetExpression:
126 """ Return the set expression corresponding to the given key. """
127 # union_tuple = tuple(tuple(tuple(leaf_id, negative), ...), ...)
128 union_tuple = ast.literal_eval(key)
129 return Union([
130 Inter([
131 ~leaf if negative else leaf
132 for leaf_id, negative in inter_tuple
133 for leaf in [self.__get_leaf(leaf_id, raise_if_not_found=False)]
134 ], optimal=True)
135 for inter_tuple in union_tuple
136 ], optimal=True)
138 def get_id(self, ref: LeafIdType) -> LeafIdType | None:
139 """ Return a set id from its reference, or ``None`` if it does not exist. """
140 if ref == '*': 140 ↛ 141line 140 didn't jump to line 141 because the condition on line 140 was never true
141 return UNIVERSAL_LEAF.id
142 leaf = self.__leaves.get(ref)
143 return None if leaf is None else leaf.id
145 def __get_leaf(self, ref: str | int, raise_if_not_found: bool = True) -> Leaf:
146 """ Return the group object from the string.
148 :param str ref: the ref of a leaf
149 """
150 if ref == '*': 150 ↛ 151line 150 didn't jump to line 151 because the condition on line 150 was never true
151 return UNIVERSAL_LEAF
152 if not raise_if_not_found and ref not in self.__leaves: 152 ↛ 153line 152 didn't jump to line 153 because the condition on line 152 was never true
153 return Leaf(UnknownId(ref), ref)
154 return self.__leaves[ref]
156 def get_superset_ids(self, ids: Iterable[int]) -> list[int]:
157 """ Returns the supersets matching the provided list of ids.
159 Following example defined in this set definitions constructor::
160 The supersets of "Q" (id 3) is "R" and "C" with ids [4, 6]
161 """
162 return sorted({
163 sup_id
164 for id_ in ids
165 if id_ in self.__leaves
166 for sup_id in self.__leaves[id_].supersets
167 if sup_id != id_
168 })
170 def get_subset_ids(self, ids: Iterable[int]) -> list[int]:
171 """ Returns the subsets matching the provided list of ids.
173 Following example defined in this set definitions constructor::
174 The subsets of "Q" (id 3) is "Z" and "N" with ids [1, 2]
175 """
176 return sorted({
177 sub_id
178 for id_ in ids
179 if id_ in self.__leaves
180 for sub_id in self.__leaves[id_].subsets
181 if sub_id != id_
182 })
184 def get_disjoint_ids(self, ids: Iterable[int]) -> list[int]:
185 """ Returns the disjoints set matching the provided list of ids.
187 Following example defined in this set definitions constructor::
188 The disjoint set of "Q" (id 3) is "R\\Q" and "I" with ids [7, 5]
189 """
190 return sorted({
191 disjoint_id
192 for id_ in ids
193 if id_ in self.__leaves
194 for disjoint_id in self.__leaves[id_].disjoints
195 })
198class SetExpression(ABC):
199 """ An object that represents a combination of named sets with union,
200 intersection and complement.
201 """
202 @abstractmethod
203 def is_empty(self) -> bool:
204 """ Returns whether ``self`` is the empty set, that contains nothing. """
205 raise NotImplementedError()
207 @abstractmethod
208 def is_universal(self) -> bool:
209 """ Returns whether ``self`` is the universal set, that contains all possible elements. """
210 raise NotImplementedError()
212 @abstractmethod
213 def invert_intersect(self, factor: SetExpression) -> SetExpression | None:
214 """ Performs the inverse operation of intersection (a sort of factorization)
215 such that: ``self == result & factor``.
216 """
217 raise NotImplementedError()
219 @abstractmethod
220 def matches(self, user_group_ids: Iterable[int]) -> bool:
221 """ Return whether the given group ids are included to ``self``. """
222 raise NotImplementedError()
224 @property
225 @abstractmethod
226 def key(self) -> str:
227 """ Return a unique identifier for the expression. """
228 raise NotImplementedError()
230 @abstractmethod
231 def __and__(self, other: SetExpression) -> SetExpression:
232 raise NotImplementedError()
234 @abstractmethod
235 def __or__(self, other: SetExpression) -> SetExpression:
236 raise NotImplementedError()
238 @abstractmethod
239 def __invert__(self) -> SetExpression:
240 raise NotImplementedError()
242 @abstractmethod
243 def __eq__(self, other) -> bool:
244 raise NotImplementedError()
246 @abstractmethod
247 def __le__(self, other: SetExpression) -> bool:
248 raise NotImplementedError()
250 @abstractmethod
251 def __lt__(self, other: SetExpression) -> bool:
252 raise NotImplementedError()
254 @abstractmethod
255 def __hash__(self):
256 raise NotImplementedError()
259class Union(SetExpression):
260 """ Implementation of a set expression, that represents it as a union of
261 intersections of named sets or their complement.
262 """
263 def __init__(self, inters: Iterable[Inter] = (), optimal=False):
264 if inters and not optimal:
265 inters = self.__combine((), inters)
266 self.__inters = sorted(inters, key=lambda inter: inter.key)
267 self.__key = str(tuple(inter.key for inter in self.__inters))
268 self.__hash = hash(self.__key)
270 @property
271 def key(self) -> str:
272 return self.__key
274 @staticmethod
275 def __combine(inters: Iterable[Inter], inters_to_add: Iterable[Inter]) -> list[Inter]:
276 """ Combine some existing union of intersections with extra intersections. """
277 result = list(inters)
279 todo = list(inters_to_add)
280 while todo:
281 inter_to_add = todo.pop()
282 if inter_to_add.is_universal():
283 return [UNIVERSAL_INTER]
284 if inter_to_add.is_empty():
285 continue
287 for index, inter in enumerate(result):
288 merged = inter._union_merge(inter_to_add)
289 if merged is not None:
290 result.pop(index)
291 todo.append(merged)
292 break
293 else:
294 result.append(inter_to_add)
296 return result
298 def is_empty(self) -> bool:
299 """ Returns whether ``self`` is the empty set, that contains nothing. """
300 return not self.__inters
302 def is_universal(self) -> bool:
303 """ Returns whether ``self`` is the universal set, that contains all possible elements. """
304 return any(item.is_universal() for item in self.__inters)
306 def invert_intersect(self, factor: SetExpression) -> Union | None:
307 """ Performs the inverse operation of intersection (a sort of factorization)
308 such that: ``self == result & factor``.
309 """
310 if factor == self:
311 return UNIVERSAL_UNION
313 rfactor = ~factor
314 if rfactor.is_empty() or rfactor.is_universal():
315 return None
316 rself = ~self
318 assert isinstance(rfactor, Union)
319 inters = [inter for inter in rself.__inters if inter not in rfactor.__inters]
320 if len(rself.__inters) - len(inters) != len(rfactor.__inters):
321 # not possible to invert the intersection
322 return None
324 rself_value = Union(inters)
325 return ~rself_value
327 def __and__(self, other: SetExpression) -> Union:
328 assert isinstance(other, Union)
329 if self.is_universal():
330 return other
331 if other.is_universal():
332 return self
333 if self.is_empty() or other.is_empty():
334 return EMPTY_UNION
335 if self == other:
336 return self
337 return Union(
338 self_inter & other_inter
339 for self_inter in self.__inters
340 for other_inter in other.__inters
341 )
343 def __or__(self, other: SetExpression) -> Union:
344 assert isinstance(other, Union)
345 if self.is_empty():
346 return other
347 if other.is_empty(): 347 ↛ 348line 347 didn't jump to line 348 because the condition on line 347 was never true
348 return self
349 if self.is_universal() or other.is_universal():
350 return UNIVERSAL_UNION
351 if self == other:
352 return self
353 inters = self.__combine(self.__inters, other.__inters)
354 return Union(inters, optimal=True)
356 def __invert__(self) -> Union:
357 if self.is_empty():
358 return UNIVERSAL_UNION
359 if self.is_universal():
360 return EMPTY_UNION
362 # apply De Morgan's laws
363 inverses_of_inters = [
364 # ~(A & B) = ~A | ~B
365 Union(Inter([~leaf]) for leaf in inter.leaves)
366 for inter in self.__inters
367 ]
368 result = inverses_of_inters[0]
369 # ~(A | B) = ~A & ~B
370 for inverse in inverses_of_inters[1:]:
371 result = result & inverse
373 return result
375 def matches(self, user_group_ids) -> bool:
376 if self.is_empty() or not user_group_ids:
377 return False
378 if self.is_universal():
379 return True
380 user_group_ids = set(user_group_ids)
381 return any(inter.matches(user_group_ids) for inter in self.__inters)
383 def __bool__(self):
384 raise NotImplementedError()
386 def __eq__(self, other) -> bool:
387 return isinstance(other, Union) and self.__key == other.__key
389 def __le__(self, other: SetExpression) -> bool:
390 if not isinstance(other, Union): 390 ↛ 391line 390 didn't jump to line 391 because the condition on line 390 was never true
391 return False
392 if self.__key == other.__key:
393 return True
394 if self.is_universal() or other.is_empty():
395 return False
396 if other.is_universal() or self.is_empty():
397 return True
398 return all(
399 any(self_inter <= other_inter for other_inter in other.__inters)
400 for self_inter in self.__inters
401 )
403 def __lt__(self, other: SetExpression) -> bool:
404 return self != other and self.__le__(other)
406 def __str__(self):
407 """ Returns an intersection union representation of groups using user-readable references.
409 e.g. ('base.group_user' & 'base.group_multi_company') | ('base.group_portal' & ~'base.group_multi_company') | 'base.group_public'
410 """
411 if self.is_empty():
412 return "~*"
414 def leaf_to_str(leaf):
415 return f"{'~' if leaf.negative else ''}{leaf.ref!r}"
417 def inter_to_str(inter, wrapped=False):
418 result = " & ".join(leaf_to_str(leaf) for leaf in inter.leaves) or "*"
419 return f"({result})" if wrapped and len(inter.leaves) > 1 else result
421 wrapped = len(self.__inters) > 1
422 return " | ".join(inter_to_str(inter, wrapped) for inter in self.__inters)
424 def __repr__(self):
425 return repr(self.__str__())
427 def __hash__(self):
428 return self.__hash
431class Inter:
432 """ Part of the implementation of a set expression, that represents an
433 intersection of named sets or their complement.
434 """
435 __slots__ = ('key', 'leaves')
437 def __init__(self, leaves: Iterable[Leaf] = (), optimal=False):
438 if leaves and not optimal:
439 leaves = self.__combine((), leaves)
440 self.leaves: list[Leaf] = sorted(leaves, key=lambda leaf: leaf.key)
441 self.key: tuple[tuple[LeafIdType, bool], ...] = tuple(leaf.key for leaf in self.leaves)
443 @staticmethod
444 def __combine(leaves: Iterable[Leaf], leaves_to_add: Iterable[Leaf]) -> list[Leaf]:
445 """ Combine some existing intersection of leaves with extra leaves. """
446 result = list(leaves)
447 for leaf_to_add in leaves_to_add:
448 for index, leaf in enumerate(result):
449 if leaf.isdisjoint(leaf_to_add): # leaf & leaf_to_add = empty
450 return [EMPTY_LEAF]
451 if leaf <= leaf_to_add: # leaf & leaf_to_add = leaf
452 break
453 if leaf_to_add <= leaf: # leaf & leaf_to_add = leaf_to_add
454 result[index] = leaf_to_add
455 break
456 else:
457 if not leaf_to_add.is_universal(): 457 ↛ 447line 457 didn't jump to line 447 because the condition on line 457 was always true
458 result.append(leaf_to_add)
459 return result
461 def is_empty(self) -> bool:
462 return any(item.is_empty() for item in self.leaves)
464 def is_universal(self) -> bool:
465 """ Returns whether ``self`` is the universal set, that contains all possible elements. """
466 return not self.leaves
468 def matches(self, user_group_ids) -> bool:
469 return all(leaf.matches(user_group_ids) for leaf in self.leaves)
471 def _union_merge(self, other: Inter) -> Inter | None:
472 """ Return the union of ``self`` with another intersection, if it can be
473 represented as an intersection. Otherwise return ``None``.
474 """
475 # the following covers cases like (A & B) | A -> A
476 if self.is_universal() or other <= self:
477 return self
478 if self <= other:
479 return other
481 # combine complementary parts: (A & ~B) | (A & B) -> A
482 if len(self.leaves) == len(other.leaves):
483 opposite_index = None
484 # we use the property that __leaves are ordered
485 for index, self_leaf, other_leaf in zip(range(len(self.leaves)), self.leaves, other.leaves):
486 if self_leaf.id != other_leaf.id:
487 return None
488 if self_leaf.negative != other_leaf.negative:
489 if opposite_index is not None: 489 ↛ 490line 489 didn't jump to line 490 because the condition on line 489 was never true
490 return None # we already have two opposite leaves
491 opposite_index = index
492 if opposite_index is not None: 492 ↛ 496line 492 didn't jump to line 496 because the condition on line 492 was always true
493 leaves = list(self.leaves)
494 leaves.pop(opposite_index)
495 return Inter(leaves, optimal=True)
496 return None
498 def __and__(self, other: Inter) -> Inter:
499 if self.is_empty() or other.is_empty(): 499 ↛ 500line 499 didn't jump to line 500 because the condition on line 499 was never true
500 return EMPTY_INTER
501 if self.is_universal(): 501 ↛ 502line 501 didn't jump to line 502 because the condition on line 501 was never true
502 return other
503 if other.is_universal(): 503 ↛ 504line 503 didn't jump to line 504 because the condition on line 503 was never true
504 return self
505 leaves = self.__combine(self.leaves, other.leaves)
506 return Inter(leaves, optimal=True)
508 def __eq__(self, other) -> bool:
509 return isinstance(other, Inter) and self.key == other.key
511 def __le__(self, other: Inter) -> bool:
512 return self.key == other.key or all(
513 any(self_leaf <= other_leaf for self_leaf in self.leaves)
514 for other_leaf in other.leaves
515 )
517 def __lt__(self, other: Inter) -> bool:
518 return self != other and self <= other
520 def __hash__(self):
521 return hash(self.key)
524class Leaf:
525 """ Part of the implementation of a set expression, that represents a named
526 set or its complement.
527 """
528 __slots__ = ('disjoints', 'id', 'inverse', 'key', 'negative', 'ref', 'subsets', 'supersets')
530 def __init__(self, leaf_id: LeafIdType, ref: str | int | None = None, negative: bool = False):
531 self.id = leaf_id
532 self.ref = ref or str(leaf_id)
533 self.negative = bool(negative)
534 self.key: tuple[LeafIdType, bool] = (leaf_id, self.negative)
536 self.subsets: set[LeafIdType] = {leaf_id} # all the leaf ids that are <= self
537 self.supersets: set[LeafIdType] = {leaf_id} # all the leaf ids that are >= self
538 self.disjoints: set[LeafIdType] = set() # all the leaf ids disjoint from self
539 self.inverse: Leaf | None = None
541 def __invert__(self) -> Leaf:
542 if self.inverse is None:
543 self.inverse = Leaf(self.id, self.ref, negative=not self.negative)
544 self.inverse.inverse = self
545 self.inverse.subsets = self.subsets
546 self.inverse.supersets = self.supersets
547 self.inverse.disjoints = self.disjoints
548 return self.inverse
550 def is_empty(self) -> bool:
551 return self.ref == '*' and self.negative
553 def is_universal(self) -> bool:
554 return self.ref == '*' and not self.negative
556 def isdisjoint(self, other: Leaf) -> bool:
557 if self.negative: 557 ↛ 558line 557 didn't jump to line 558 because the condition on line 557 was never true
558 return other <= ~self
559 elif other.negative:
560 return self <= ~other
561 else:
562 return self.id in other.disjoints
564 def matches(self, user_group_ids: Collection[int]) -> bool:
565 return (self.id not in user_group_ids) if self.negative else (self.id in user_group_ids)
567 def __eq__(self, other) -> bool:
568 return isinstance(other, Leaf) and self.key == other.key
570 def __le__(self, other: Leaf) -> bool:
571 if self.is_empty() or other.is_universal(): 571 ↛ 572line 571 didn't jump to line 572 because the condition on line 571 was never true
572 return True
573 elif self.is_universal() or other.is_empty(): 573 ↛ 574line 573 didn't jump to line 574 because the condition on line 573 was never true
574 return False
575 elif self.negative:
576 return other.negative and ~other <= ~self
577 elif other.negative:
578 return self.id in other.disjoints
579 else:
580 return self.id in other.subsets
582 def __lt__(self, other: Leaf) -> bool:
583 return self != other and self <= other
585 def __hash__(self):
586 return hash(self.key)
589class UnknownId(str):
590 """ Special id object for unknown leaves. It behaves as being strictly
591 greater than any other kind of id.
592 """
593 __slots__ = ()
595 def __lt__(self, other) -> bool:
596 if isinstance(other, UnknownId):
597 return super().__lt__(other)
598 return False
600 def __gt__(self, other) -> bool:
601 if isinstance(other, UnknownId):
602 return super().__gt__(other)
603 return True
606LeafIdType = int | typing.Literal["*"] | UnknownId
608# constants
609UNIVERSAL_LEAF = Leaf('*')
610EMPTY_LEAF = ~UNIVERSAL_LEAF
612EMPTY_INTER = Inter([EMPTY_LEAF])
613UNIVERSAL_INTER = Inter()
615EMPTY_UNION = Union()
616UNIVERSAL_UNION = Union([UNIVERSAL_INTER])