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

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 itertools import islice 

11from typing import Deque, TypeVar 

12 

13_T = TypeVar("_T") 

14 

15 

16class _Dependency(Deque[_T]): 

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

18 

19 @property 

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

21 """Head of the dependency.""" 

22 try: 

23 return self[0] 

24 except IndexError: 

25 return None 

26 

27 @property 

28 def tail(self) -> islice: 

29 """Tail of the dependency. 

30 

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

32 """ 

33 try: 

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

35 except (ValueError, IndexError): 

36 return islice([], 0, 0) 

37 

38 

39class _DependencyList: 

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

41 

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

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

44 precedence order of direct parent classes. 

45 """ 

46 

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

48 """Initialize the list. 

49 

50 Parameters: 

51 *lists: Lists of items. 

52 """ 

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

54 

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

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

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

58 

59 def __len__(self) -> int: 

60 size = len(self._lists) 

61 return (size - 1) if size else 0 

62 

63 def __repr__(self) -> str: 

64 return self._lists.__repr__() 

65 

66 @property 

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

68 """Return the heads.""" 

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

70 

71 @property 

72 def tails(self) -> _DependencyList: 

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

74 return self 

75 

76 @property 

77 def exhausted(self) -> bool: 

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

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

80 

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

82 """Remove an item from the lists. 

83 

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

85 get promoted to become the new heads. 

86 """ 

87 for i in self._lists: 

88 if i and i.head == item: 

89 i.popleft() 

90 

91 

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

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

94 

95 Parameters: 

96 *lists: Lists of items. 

97 

98 Returns: 

99 The merged list of items. 

100 """ 

101 result: list[_T] = [] 

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

103 

104 while True: 

105 if linearizations.exhausted: 

106 return result 

107 

108 for head in linearizations.heads: 

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

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

111 linearizations.remove(head) 

112 

113 # Once candidate is found, continue iteration 

114 # from the first element of the list. 

115 break 

116 else: 

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

118 raise ValueError("Cannot compute C3 linearization")