penguinolog / urwid / 37018256016

86%

master: 88%

push

github

Fix tree recursion, index scans and node leak

Deep or wide trees from untrusted data no longer crash or stall
rendering, and reloading children no longer accumulates nodes.

- TreeWidget.last_child and TreeNode.get_depth loop instead of
  recursing once per level, so a subtree deeper than the recursion
  limit no longer raises RecursionError on render or End.
- A cycle in the tree or in the parent links raises TreeWidgetError
  instead of looping forever.
- ParentNode.get_child_index uses a key -> index map, rebuilt when it
  no longer matches the key list, instead of list.index on each step.
- ParentNode.get_child_keys(reload=True) drops cached child nodes
  whose keys are gone; a key dropped by a reload gets a fresh node
  later, so its expanded state is not kept.

| what | avg time before | avg time after | percent change |
| --- | --- | --- | --- |
| urwid.ParentNode.get_child_index (via urwid.TreeNode.next_sibling), 1000 siblings | 6.6 ms | 1.4 ms | -79% |
| urwid.ParentNode.get_child_index (via urwid.TreeNode.next_sibling), 5000 siblings | 126.3 ms | 7.5 ms | -94% |
| urwid.ParentNode.get_child_index (via urwid.TreeNode.next_sibling), 20000 siblings | 1875.8 ms | 31.5 ms | -98% |
| urwid.ParentNode.get_child_index (via urwid.ScrollBar.render over urwid.TreeListBox), 1000 entries | 18.1 ms | 8.3 ms | -54% |
| urwid.ParentNode.get_child_index (via urwid.ScrollBar.render over urwid.TreeListBox), 5000 entries | 270.9 ms | 39.0 ms | -86% |
| urwid.ParentNode.get_child_index (via urwid.ScrollBar.render over urwid.TreeListBox), 20000 entries | 3698.5 ms | 154.2 ms | -96% |

4638 of 5574 branches covered (83.21%)

Branch coverage included in aggregate %.

53 of 54 new or added lines in 1 file covered. (98.15%)

11617 of 13250 relevant lines covered (87.68%)

9.8 hits per line