Coverage for src/_griffe/c3linear.py: 92.06%

1# This module contains a single function, `c3linear_merge`. 

2# The function is generic enough to be in its own module. 

3# 

4# - Copyright (c) 2019 Vitaly R. Samigullin 

5# - Adapted from https://github.com/pilosus/c3linear 

6# - Adapted from https://github.com/tristanlatr/pydocspec 

7 

8from __future__ import annotations 

9 

10from collections import deque 

11from itertools import islice 

12from typing import TypeVar 

13 

14_T = TypeVar("_T") 

15 

16 

17class _Dependency(deque[_T]): 

18 """A class representing a (doubly-ended) queue of items.""" 

19 

20 @property 

21 def head(self) -> _T | None: 

22 """Head of the dependency.""" 

23 try: 

24 return self[0] 

25 except IndexError: 

26 return None 

27 

28 @property 

29 def tail(self) -> islice: 

30 """Tail of the dependency. 

31 

32 The `islice` object is sufficient for iteration or testing membership (`in`). 

33 """ 

34 try: 

35 return islice(self, 1, self.__len__()) 

36 except (ValueError, IndexError): 

37 return islice([], 0, 0) 

38 

39 

40class _DependencyList: 

41 """A class representing a list of linearizations (dependencies). 

42 

43 The last element of DependencyList is a list of parents. 

44 It's needed to the merge process preserves the local 

45 precedence order of direct parent classes. 

46 """ 

47 

48 def __init__(self, *lists: list[_T | None]) -> None: 

49 """Initialize the list. 

50 

51 Parameters: 

52 *lists: Lists of items. 

53 """ 

54 self._lists = [_Dependency(lst) for lst in lists] 

55 

56 def __contains__(self, item: _T) -> bool: 

57 """Return True if any linearization's tail contains an item.""" 

58 return any(item in lst.tail for lst in self._lists) 

59 

60 def __len__(self) -> int: 

61 size = len(self._lists) 

62 return (size - 1) if size else 0 

63 

64 def __repr__(self) -> str: 

65 return self._lists.__repr__() 

66 

67 @property 

68 def heads(self) -> list[_T | None]: 

69 """Return the heads.""" 

70 return [lst.head for lst in self._lists] # type: ignore[misc] 

71 

72 @property 

73 def tails(self) -> _DependencyList: 

74 """Return self so that `__contains__` could be called.""" 

75 return self 

76 

77 @property 

78 def exhausted(self) -> bool: 

79 """True if all elements of the lists are exhausted.""" 

80 return all(len(x) == 0 for x in self._lists) 

81 

82 def remove(self, item: _T | None) -> None: 

83 """Remove an item from the lists. 

84 

85 Once an item removed from heads, the leftmost elements of the tails 

86 get promoted to become the new heads. 

87 """ 

88 for i in self._lists: 

89 if i and i.head == item: 

90 i.popleft() 

91 

92 

93def c3linear_merge(*lists: list[_T]) -> list[_T]: 

94 """Merge lists of lists in the order defined by the C3Linear algorithm. 

95 

96 Parameters: 

97 *lists: Lists of items. 

98 

99 Returns: 

100 The merged list of items. 

101 """ 

102 result: list[_T] = [] 

103 linearizations = _DependencyList(*lists) # type: ignore[arg-type] 

104 

105 while True: 

106 if linearizations.exhausted: 

107 return result 

108 

109 for head in linearizations.heads: 

110 if head and (head not in linearizations.tails): 

111 result.append(head) # type: ignore[arg-type] 

112 linearizations.remove(head) 

113 

114 # Once candidate is found, continue iteration 

115 # from the first element of the list. 

116 break 

117 else: 

118 # Loop never broke, no linearization could possibly be found. 

119 raise ValueError("Cannot compute C3 linearization")