mypy.checker.DisjointDict

An variation of the union-find algorithm/data structure where instead of keeping track of just disjoint sets, we keep track of disjoint dicts -- keep track of multiple Set[Key] -> Set[Value] mappings, where each mapping's keys are guaranteed to be disjoint.

This data structure is currently used exclusively by 'group_comparison_operands' below to merge chains of '==' and 'is' comparisons when two or more chains use the same expression in best-case O(n), where n is the number of operands.

Specifically, the add_mapping() function and items() functions will take on average O(k + v) and O(n) respectively, where k and v are the number of keys and values we're adding for a given chain. Note that k <= n and v <= n.

We hit these average/best-case scenarios for most user code: e.g. when the user has just a single chain like 'a == b == c == d == ...' or multiple disjoint chains like 'a==b < c==d < e==f < ...'. (Note that a naive iterative merging would be O(n^2) for the latter case).

In comparison, this data structure will make 'group_comparison_operands' have a worst-case runtime of O(n*log(n)): 'add_mapping()' and 'items()' are worst-case O(k*log(n) + v) and O(k*log(n)) respectively. This happens only in the rare case where the user keeps repeatedly making disjoint mappings before merging them in a way that persistently dodges the path compression optimization in '_lookup_root_id', which would end up constructing a single tree of height log_2(n). This makes root lookups no longer amoritized constant time when we finally call 'items()'.