1ebcd509a9ec3dd07d0259535436aa6e75626dfa
[utils.git] / 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