src/budget_sync/budget_graph.py

   1 from bugzilla.bug import Bug
   2 from bugzilla import Bugzilla
   3 from typing import Set, Dict, Iterable, Optional, List
   4 from budget_sync.util import all_bugs
   5 from budget_sync.money import Money
   6 from functools import cached_property
   7 import toml
   8 import sys
   9 from collections import deque
  10
  11
  12 class BudgetGraphBaseError(Exception):
  13     pass
  14
  15
  16 class BudgetGraphParseError(BudgetGraphBaseError):
  17     def __init__(self, bug_id: int):
  18         self.bug_id = bug_id
  19
  20
  21 class BudgetGraphPayeesParseError(BudgetGraphParseError):
  22     def __init__(self, bug_id: int, msg: str):
  23         super().__init__(bug_id)
  24         self.msg = msg
  25
  26     def __str__(self):
  27         return f"Failed to parse cf_payees_list field of bug #{self.bug_id}: {self.msg}"
  28
  29
  30 class BudgetGraphLoopError(BudgetGraphBaseError):
  31     def __init__(self, bug_ids: List[int]):
  32         self.bug_ids = bug_ids
  33
  34     def __str__(self):
  35         retval = f"Detected Loop in Budget Graph: #{self.bug_ids[-1]} -> "
  36         retval += " -> ".join((f"#{i}" for i in self.bug_ids))
  37         return retval
  38
  39
  40 class _NodeSimpleReprWrapper:
  41     def __init__(self, node: "Node"):
  42         self.node = node
  43
  44     def __repr__(self):
  45         return f"#{self.node.bug.id}"
  46
  47     def __lt__(self, other):
  48         # for list.sort()
  49         return self.node.bug.id < other.node.bug.id
  50
  51
  52 class Node:
  53     graph: "BudgetGraph"
  54     bug: Bug
  55     parent_id: Optional[int]
  56     immediate_children: Set["Node"]
  57     budget_excluding_subtasks: Money
  58     budget_including_subtasks: Money
  59     fixed_budget_excluding_subtasks: Money
  60     fixed_budget_including_subtasks: Money
  61     nlnet_milestone: Optional[str]
  62
  63     def __init__(self, graph: "BudgetGraph", bug: Bug):
  64         self.graph = graph
  65         self.bug = bug
  66         self.parent_id = getattr(bug, "cf_budget_parent", None)
  67         self.immediate_children = set()
  68         self.budget_excluding_subtasks = Money.from_str(bug.cf_budget)
  69         self.fixed_budget_excluding_subtasks = self.budget_excluding_subtasks
  70         self.budget_including_subtasks = Money.from_str(bug.cf_total_budget)
  71         self.fixed_budget_including_subtasks = self.budget_including_subtasks
  72         self.nlnet_milestone = bug.cf_nlnet_milestone
  73         if self.nlnet_milestone == "---":
  74             self.nlnet_milestone = None
  75
  76     @cached_property
  77     def payees(self) -> Dict[str, Money]:
  78         try:
  79             parsed = toml.loads(self.bug.cf_payees_list)
  80         except toml.TomlDecodeError as e:
  81             new_err = BudgetGraphPayeesParseError(
  82                 self.bug.id, f"TOML parse error: {e}")
  83             raise new_err.with_traceback(sys.exc_info()[2])
  84         retval = {}
  85         for key, value in parsed.items():
  86             if not isinstance(key, str):
  87                 raise BudgetGraphPayeesParseError(
  88                     self.bug.id, f"key is not a string: {key!r}")
  89             if not isinstance(value, (int, str)):
  90                 msg = f"value for key {key!r} is not a string or integer " \
  91                     f"(to use fractional values such as 123.45, write " \
  92                     f"\"123.45\"): {value!r}"
  93                 raise BudgetGraphPayeesParseError(self.bug.id, msg)
  94             try:
  95                 money_value = Money(value)
  96             except ValueError as e:
  97                 msg = f"failed to parse Money value for key {key!r}: {e}"
  98                 raise BudgetGraphPayeesParseError(
  99                     self.bug.id, msg) \
 100                     .with_traceback(sys.exc_info()[2])
 101             retval[key] = money_value
 102         return retval
 103
 104     @property
 105     def parent(self) -> Optional["Node"]:
 106         if self.parent_id is not None:
 107             return self.graph.nodes[self.parent_id]
 108         return None
 109
 110     def parents(self) -> Iterable["Node"]:
 111         parent = self.parent
 112         while parent is not None:
 113             yield parent
 114             parent = parent.parent
 115
 116     def _raise_loop_error(self):
 117         bug_ids = []
 118         for parent in self.parents():
 119             bug_ids.append(parent.bug.id)
 120             if parent == self:
 121                 break
 122         raise BudgetGraphLoopError(bug_ids)
 123
 124     @cached_property
 125     def root(self) -> "Node":
 126         # also checks for loop errors
 127         retval = self
 128         for parent in self.parents():
 129             retval = parent
 130             if parent == self:
 131                 self._raise_loop_error()
 132         return retval
 133
 134     def children(self) -> Iterable["Node"]:
 135         def visitor(node: Node) -> Iterable[Node]:
 136             for i in node.immediate_children:
 137                 yield i
 138                 yield from visitor(i)
 139         return visitor(self)
 140
 141     def children_breadth_first(self) -> Iterable["Node"]:
 142         q = deque(self.immediate_children)
 143         while True:
 144             try:
 145                 node = q.popleft()
 146             except IndexError:
 147                 return
 148             q.extend(node.immediate_children)
 149             yield node
 150
 151     def __eq__(self, other):
 152         return self.bug.id == other.bug.id
 153
 154     def __ne__(self, other):
 155         return self.bug.id != other.bug.id
 156
 157     def __hash__(self):
 158         return self.bug.id
 159
 160     def __repr__(self):
 161         try:
 162             root = _NodeSimpleReprWrapper(self.root)
 163         except BudgetGraphLoopError:
 164             root = "<loop error>"
 165         immediate_children = []
 166         for i in self.immediate_children:
 167             immediate_children.append(_NodeSimpleReprWrapper(i))
 168         immediate_children.sort()
 169         parent = f"#{self.parent_id}" if self.parent_id is not None else None
 170         return (f"Node(graph=..., "
 171                 f"id={_NodeSimpleReprWrapper(self)}, "
 172                 f"root={root}, "
 173                 f"parent={parent}, "
 174                 f"budget_excluding_subtasks={self.budget_excluding_subtasks}, "
 175                 f"budget_including_subtasks={self.budget_including_subtasks}, "
 176                 f"fixed_budget_excluding_subtasks={self.fixed_budget_excluding_subtasks}, "
 177                 f"fixed_budget_including_subtasks={self.fixed_budget_including_subtasks}, "
 178                 f"nlnet_milestone={self.nlnet_milestone!r}, "
 179                 f"immediate_children={immediate_children!r}, "
 180                 f"payees={self.payees!r}")
 181
 182
 183 class BudgetGraphError(BudgetGraphBaseError):
 184     def __init__(self, bug_id: int, root_bug_id: int):
 185         self.bug_id = bug_id
 186         self.root_bug_id = root_bug_id
 187
 188
 189 class BudgetGraphMoneyWithNoMilestone(BudgetGraphError):
 190     def __str__(self):
 191         return (f"Bug assigned money but without"
 192                 f" any assigned milestone: #{self.bug_id}")
 193
 194
 195 class BudgetGraphMilestoneMismatch(BudgetGraphError):
 196     def __str__(self):
 197         return (f"Bug's assigned milestone doesn't match the milestone "
 198                 f"assigned to the root bug: descendant bug"
 199                 f" #{self.bug_id}, root bug"
 200                 f" #{self.root_bug_id}")
 201
 202
 203 class BudgetGraphMoneyMismatchForBudgetExcludingSubtasks(BudgetGraphError):
 204     def __init__(self, bug_id: int, root_bug_id: int,
 205                  expected_budget_excluding_subtasks: Money):
 206         super().__init__(bug_id, root_bug_id)
 207         self.expected_budget_excluding_subtasks = \
 208             expected_budget_excluding_subtasks
 209
 210     def __str__(self):
 211         return (f"Budget assigned to task excluding subtasks "
 212                 f"(cf_budget field) doesn't match calculated value: "
 213                 f"bug #{self.bug_id}, calculated value"
 214                 f" {self.expected_budget_excluding_subtasks}")
 215
 216
 217 class BudgetGraphMoneyMismatchForBudgetIncludingSubtasks(BudgetGraphError):
 218     def __init__(self, bug_id: int, root_bug_id: int,
 219                  expected_budget_including_subtasks: Money):
 220         super().__init__(bug_id, root_bug_id)
 221         self.expected_budget_including_subtasks = \
 222             expected_budget_including_subtasks
 223
 224     def __str__(self):
 225         return (f"Budget assigned to task including subtasks "
 226                 f"(cf_total_budget field) doesn't match calculated value: "
 227                 f"bug #{self.bug_id}, calculated value"
 228                 f" {self.expected_budget_including_subtasks}")
 229
 230
 231 class BudgetGraphNegativeMoney(BudgetGraphError):
 232     def __str__(self):
 233         return (f"Budget assigned to task is less than zero: "
 234                 f"bug #{self.bug_id}")
 235
 236
 237 class BudgetGraphPayeesMoneyMismatch(BudgetGraphError):
 238     def __init__(self, bug_id: int, root_bug_id: int, payees_total: Money,
 239                  expected_payees_total: Money):
 240         super().__init__(bug_id, root_bug_id)
 241         self.payees_total = payees_total
 242         self.expected_payees_total = expected_payees_total
 243
 244     def __str__(self):
 245         return (f"Total budget assigned to payees (cf_payees_list) doesn't "
 246                 f"match expected value: bug #{self.bug_id}, calculated total "
 247                 f"{self.payees_total}, expected value "
 248                 f"{self.expected_payees_total}")
 249
 250
 251 class BudgetGraphNegativePayeeMoney(BudgetGraphError):
 252     def __init__(self, bug_id: int, root_bug_id: int, payee_key: str):
 253         super().__init__(bug_id, root_bug_id)
 254         self.payee_key = payee_key
 255
 256     def __str__(self):
 257         return (f"Budget assigned to payee for task is less than zero: "
 258                 f"bug #{self.bug_id}, payee {self.payee_key!r}")
 259
 260
 261 class BudgetGraph:
 262     nodes: Dict[int, Node]
 263
 264     def __init__(self, bugs: Iterable[Bug]):
 265         self.nodes = {}
 266         for bug in bugs:
 267             self.nodes[bug.id] = Node(self, bug)
 268         for node in self.nodes.values():
 269             if node.parent is None:
 270                 continue
 271             node.parent.immediate_children.add(node)
 272
 273     @cached_property
 274     def roots(self) -> Set[Node]:
 275         roots = set()
 276         for node in self.nodes.values():
 277             # calling .root also checks for loop errors
 278             root = node.root
 279             roots.add(root)
 280         return roots
 281
 282     def _get_node_errors(self, root: Node, node: Node,
 283                          errors: List[BudgetGraphBaseError]):
 284         if node.nlnet_milestone is None:
 285             if node.budget_including_subtasks != 0 \
 286                     or node.budget_excluding_subtasks != 0:
 287                 errors.append(BudgetGraphMoneyWithNoMilestone(
 288                     node.bug.id, root.bug.id))
 289
 290         if node.nlnet_milestone != root.nlnet_milestone:
 291             errors.append(BudgetGraphMilestoneMismatch(
 292                 node.bug.id, root.bug.id))
 293
 294         if node.budget_excluding_subtasks < 0 \
 295                 or node.budget_including_subtasks < 0:
 296             errors.append(BudgetGraphNegativeMoney(
 297                 node.bug.id, root.bug.id))
 298
 299         subtasks_total = Money(0)
 300         for child in node.immediate_children:
 301             subtasks_total += child.fixed_budget_including_subtasks
 302
 303         payees_total = Money(0)
 304         for payee_key, payee_value in node.payees.items():
 305             if payee_value < 0:
 306                 errors.append(BudgetGraphNegativePayeeMoney(
 307                     node.bug.id, root.bug.id, payee_key))
 308             payees_total += payee_value
 309
 310         def set_including_from_excluding_and_error():
 311             node.fixed_budget_including_subtasks = \
 312                 node.budget_excluding_subtasks + subtasks_total
 313             errors.append(
 314                 BudgetGraphMoneyMismatchForBudgetIncludingSubtasks(
 315                     node.bug.id, root.bug.id,
 316                     node.fixed_budget_including_subtasks))
 317
 318         def set_including_from_payees_and_error():
 319             node.fixed_budget_including_subtasks = \
 320                 payees_total + subtasks_total
 321             errors.append(
 322                 BudgetGraphMoneyMismatchForBudgetIncludingSubtasks(
 323                     node.bug.id, root.bug.id,
 324                     node.fixed_budget_including_subtasks))
 325
 326         def set_excluding_from_including_and_error():
 327             node.fixed_budget_excluding_subtasks = \
 328                 node.budget_including_subtasks - subtasks_total
 329             errors.append(
 330                 BudgetGraphMoneyMismatchForBudgetExcludingSubtasks(
 331                     node.bug.id, root.bug.id,
 332                     node.fixed_budget_excluding_subtasks))
 333
 334         def set_excluding_from_payees_and_error():
 335             node.fixed_budget_excluding_subtasks = \
 336                 payees_total
 337             errors.append(
 338                 BudgetGraphMoneyMismatchForBudgetExcludingSubtasks(
 339                     node.bug.id, root.bug.id,
 340                     node.fixed_budget_excluding_subtasks))
 341
 342         def set_payees_from_including_and_error():
 343             fixed_payees_total = \
 344                 node.budget_including_subtasks - subtasks_total
 345             errors.append(BudgetGraphPayeesMoneyMismatch(
 346                 node.bug.id, root.bug.id, payees_total, fixed_payees_total))
 347
 348         def set_payees_from_excluding_and_error():
 349             fixed_payees_total = \
 350                 node.budget_excluding_subtasks
 351             errors.append(BudgetGraphPayeesMoneyMismatch(
 352                 node.bug.id, root.bug.id, payees_total, fixed_payees_total))
 353
 354         payees_matches_including = \
 355             node.budget_including_subtasks - subtasks_total == payees_total
 356         payees_matches_excluding = \
 357             node.budget_excluding_subtasks == payees_total
 358         including_matches_excluding = \
 359             node.budget_including_subtasks - subtasks_total \
 360             == node.budget_excluding_subtasks
 361
 362         if payees_matches_including \
 363                 and payees_matches_excluding \
 364                 and including_matches_excluding:
 365             pass  # no error
 366         elif payees_matches_including:
 367             # can't have 2 match without all 3 matching
 368             assert not payees_matches_excluding
 369             assert not including_matches_excluding
 370             if node.budget_including_subtasks == 0 and len(node.payees) == 0:
 371                 set_including_from_excluding_and_error()
 372             else:
 373                 set_excluding_from_including_and_error()
 374         elif payees_matches_excluding:
 375             # can't have 2 match without all 3 matching
 376             assert not payees_matches_including
 377             assert not including_matches_excluding
 378             if node.budget_excluding_subtasks == 0 and len(node.payees) == 0:
 379                 if node.budget_including_subtasks == 0:
 380                     set_including_from_excluding_and_error()
 381                 else:
 382                     set_excluding_from_including_and_error()
 383             else:
 384                 set_including_from_excluding_and_error()
 385         elif including_matches_excluding:
 386             # can't have 2 match without all 3 matching
 387             assert not payees_matches_including
 388             assert not payees_matches_excluding
 389             if len(node.payees) == 0:
 390                 pass  # no error -- payees is just not set
 391             elif node.budget_excluding_subtasks == 0 \
 392                     and node.budget_including_subtasks == 0:
 393                 set_excluding_from_payees_and_error()
 394                 set_including_from_payees_and_error()
 395             else:
 396                 set_payees_from_excluding_and_error()
 397         else:
 398             # nothing matches
 399             if len(node.payees) == 0:
 400                 # payees unset -- don't need to set payees
 401                 if node.budget_including_subtasks == 0:
 402                     set_including_from_excluding_and_error()
 403                 else:
 404                     set_excluding_from_including_and_error()
 405             elif node.budget_excluding_subtasks == 0 \
 406                     and node.budget_including_subtasks == 0:
 407                 set_excluding_from_payees_and_error()
 408                 set_including_from_payees_and_error()
 409             elif node.budget_excluding_subtasks == 0:
 410                 set_excluding_from_including_and_error()
 411                 set_payees_from_including_and_error()
 412             elif node.budget_including_subtasks == 0:
 413                 set_including_from_excluding_and_error()
 414                 set_payees_from_excluding_and_error()
 415             else:
 416                 set_including_from_excluding_and_error()
 417                 set_payees_from_excluding_and_error()
 418
 419     def get_errors(self) -> List[BudgetGraphBaseError]:
 420         errors = []
 421         try:
 422             roots = self.roots
 423         except BudgetGraphBaseError as e:
 424             errors.append(e)
 425             return errors
 426
 427         for root in roots:
 428             try:
 429                 for child in reversed(list(root.children_breadth_first())):
 430                     try:
 431                         self._get_node_errors(root, child, errors)
 432                     except BudgetGraphBaseError as e:
 433                         errors.append(e)
 434                 self._get_node_errors(root, root, errors)
 435             except BudgetGraphBaseError as e:
 436                 errors.append(e)
 437         return errors
 438
 439     @cached_property
 440     def payee_keys(self) -> Set[str]:
 441         retval = set()
 442         for node in self.nodes.values():
 443             for payee_key in node.payees.keys():
 444                 retval.add(payee_key)
 445         return retval