Coverage for /usr/lib/python3/dist-packages/fontTools/ttLib/tables/otTraverse.py: 25%

1"""Methods for traversing trees of otData-driven OpenType tables.""" 

2from collections import deque 

3from typing import Callable, Deque, Iterable, List, Optional, Tuple 

4from .otBase import BaseTable 

5 

6 

7__all__ = [ 

8 "bfs_base_table", 

9 "dfs_base_table", 

10 "SubTablePath", 

11] 

12 

13 

14class SubTablePath(Tuple[BaseTable.SubTableEntry, ...]): 

15 def __str__(self) -> str: 

16 path_parts = [] 

17 for entry in self: 

18 path_part = entry.name 

19 if entry.index is not None: 

20 path_part += f"[{entry.index}]" 

21 path_parts.append(path_part) 

22 return ".".join(path_parts) 

23 

24 

25# Given f(current frontier, new entries) add new entries to frontier 

26AddToFrontierFn = Callable[[Deque[SubTablePath], List[SubTablePath]], None] 

27 

28 

29def dfs_base_table( 

30 root: BaseTable, 

31 root_accessor: Optional[str] = None, 

32 skip_root: bool = False, 

33 predicate: Optional[Callable[[SubTablePath], bool]] = None, 

34 iter_subtables_fn: Optional[ 

35 Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]] 

36 ] = None, 

37) -> Iterable[SubTablePath]: 

38 """Depth-first search tree of BaseTables. 

39 

40 Args: 

41 root (BaseTable): the root of the tree. 

42 root_accessor (Optional[str]): attribute name for the root table, if any (mostly 

43 useful for debugging). 

44 skip_root (Optional[bool]): if True, the root itself is not visited, only its 

45 children. 

46 predicate (Optional[Callable[[SubTablePath], bool]]): function to filter out 

47 paths. If True, the path is yielded and its subtables are added to the 

48 queue. If False, the path is skipped and its subtables are not traversed. 

49 iter_subtables_fn (Optional[Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]]]): 

50 function to iterate over subtables of a table. If None, the default 

51 BaseTable.iterSubTables() is used. 

52 

53 Yields: 

54 SubTablePath: tuples of BaseTable.SubTableEntry(name, table, index) namedtuples 

55 for each of the nodes in the tree. The last entry in a path is the current 

56 subtable, whereas preceding ones refer to its parent tables all the way up to 

57 the root. 

58 """ 

59 yield from _traverse_ot_data( 

60 root, 

61 root_accessor, 

62 skip_root, 

63 predicate, 

64 lambda frontier, new: frontier.extendleft(reversed(new)), 

65 iter_subtables_fn, 

66 ) 

67 

68 

69def bfs_base_table( 

70 root: BaseTable, 

71 root_accessor: Optional[str] = None, 

72 skip_root: bool = False, 

73 predicate: Optional[Callable[[SubTablePath], bool]] = None, 

74 iter_subtables_fn: Optional[ 

75 Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]] 

76 ] = None, 

77) -> Iterable[SubTablePath]: 

78 """Breadth-first search tree of BaseTables. 

79 

80 Args: 

81 the root of the tree. 

82 root_accessor (Optional[str]): attribute name for the root table, if any (mostly 

83 useful for debugging). 

84 skip_root (Optional[bool]): if True, the root itself is not visited, only its 

85 children. 

86 predicate (Optional[Callable[[SubTablePath], bool]]): function to filter out 

87 paths. If True, the path is yielded and its subtables are added to the 

88 queue. If False, the path is skipped and its subtables are not traversed. 

89 iter_subtables_fn (Optional[Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]]]): 

90 function to iterate over subtables of a table. If None, the default 

91 BaseTable.iterSubTables() is used. 

92 

93 Yields: 

94 SubTablePath: tuples of BaseTable.SubTableEntry(name, table, index) namedtuples 

95 for each of the nodes in the tree. The last entry in a path is the current 

96 subtable, whereas preceding ones refer to its parent tables all the way up to 

97 the root. 

98 """ 

99 yield from _traverse_ot_data( 

100 root, 

101 root_accessor, 

102 skip_root, 

103 predicate, 

104 lambda frontier, new: frontier.extend(new), 

105 iter_subtables_fn, 

106 ) 

107 

108 

109def _traverse_ot_data( 

110 root: BaseTable, 

111 root_accessor: Optional[str], 

112 skip_root: bool, 

113 predicate: Optional[Callable[[SubTablePath], bool]], 

114 add_to_frontier_fn: AddToFrontierFn, 

115 iter_subtables_fn: Optional[ 

116 Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]] 

117 ] = None, 

118) -> Iterable[SubTablePath]: 

119 # no visited because general otData cannot cycle (forward-offset only) 

120 if root_accessor is None: 

121 root_accessor = type(root).__name__ 

122 

123 if predicate is None: 

124 

125 def predicate(path): 

126 return True 

127 

128 if iter_subtables_fn is None: 

129 

130 def iter_subtables_fn(table): 

131 return table.iterSubTables() 

132 

133 frontier: Deque[SubTablePath] = deque() 

134 

135 root_entry = BaseTable.SubTableEntry(root_accessor, root) 

136 if not skip_root: 

137 frontier.append((root_entry,)) 

138 else: 

139 add_to_frontier_fn( 

140 frontier, 

141 [ 

142 (root_entry, subtable_entry) 

143 for subtable_entry in iter_subtables_fn(root) 

144 ], 

145 ) 

146 

147 while frontier: 

148 # path is (value, attr_name) tuples. attr_name is attr of parent to get value 

149 path = frontier.popleft() 

150 current = path[-1].value 

151 

152 if not predicate(path): 

153 continue 

154 

155 yield SubTablePath(path) 

156 

157 new_entries = [ 

158 path + (subtable_entry,) for subtable_entry in iter_subtables_fn(current) 

159 ] 

160 

161 add_to_frontier_fn(frontier, new_entries)