1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
"""Methods for traversing trees of otData-driven OpenType tables."""
from collections import deque
from typing import Callable, Deque, Iterable, List, Optional, Tuple
from .otBase import BaseTable
__all__ = [
"bfs_base_table",
"dfs_base_table",
"SubTablePath",
]
class SubTablePath(Tuple[BaseTable.SubTableEntry, ...]):
def __str__(self) -> str:
path_parts = []
for entry in self:
path_part = entry.name
if entry.index is not None:
path_part += f"[{entry.index}]"
path_parts.append(path_part)
return ".".join(path_parts)
# Given f(current frontier, new entries) add new entries to frontier
AddToFrontierFn = Callable[[Deque[SubTablePath], List[SubTablePath]], None]
def dfs_base_table(
root: BaseTable,
root_accessor: Optional[str] = None,
skip_root: bool = False,
predicate: Optional[Callable[[SubTablePath], bool]] = None,
iter_subtables_fn: Optional[
Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]]
] = None,
) -> Iterable[SubTablePath]:
"""Depth-first search tree of BaseTables.
Args:
root (BaseTable): the root of the tree.
root_accessor (Optional[str]): attribute name for the root table, if any (mostly
useful for debugging).
skip_root (Optional[bool]): if True, the root itself is not visited, only its
children.
predicate (Optional[Callable[[SubTablePath], bool]]): function to filter out
paths. If True, the path is yielded and its subtables are added to the
queue. If False, the path is skipped and its subtables are not traversed.
iter_subtables_fn (Optional[Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]]]):
function to iterate over subtables of a table. If None, the default
BaseTable.iterSubTables() is used.
Yields:
SubTablePath: tuples of BaseTable.SubTableEntry(name, table, index) namedtuples
for each of the nodes in the tree. The last entry in a path is the current
subtable, whereas preceding ones refer to its parent tables all the way up to
the root.
"""
yield from _traverse_ot_data(
root,
root_accessor,
skip_root,
predicate,
lambda frontier, new: frontier.extendleft(reversed(new)),
iter_subtables_fn,
)
def bfs_base_table(
root: BaseTable,
root_accessor: Optional[str] = None,
skip_root: bool = False,
predicate: Optional[Callable[[SubTablePath], bool]] = None,
iter_subtables_fn: Optional[
Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]]
] = None,
) -> Iterable[SubTablePath]:
"""Breadth-first search tree of BaseTables.
Args:
the root of the tree.
root_accessor (Optional[str]): attribute name for the root table, if any (mostly
useful for debugging).
skip_root (Optional[bool]): if True, the root itself is not visited, only its
children.
predicate (Optional[Callable[[SubTablePath], bool]]): function to filter out
paths. If True, the path is yielded and its subtables are added to the
queue. If False, the path is skipped and its subtables are not traversed.
iter_subtables_fn (Optional[Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]]]):
function to iterate over subtables of a table. If None, the default
BaseTable.iterSubTables() is used.
Yields:
SubTablePath: tuples of BaseTable.SubTableEntry(name, table, index) namedtuples
for each of the nodes in the tree. The last entry in a path is the current
subtable, whereas preceding ones refer to its parent tables all the way up to
the root.
"""
yield from _traverse_ot_data(
root,
root_accessor,
skip_root,
predicate,
lambda frontier, new: frontier.extend(new),
iter_subtables_fn,
)
def _traverse_ot_data(
root: BaseTable,
root_accessor: Optional[str],
skip_root: bool,
predicate: Optional[Callable[[SubTablePath], bool]],
add_to_frontier_fn: AddToFrontierFn,
iter_subtables_fn: Optional[
Callable[[BaseTable], Iterable[BaseTable.SubTableEntry]]
] = None,
) -> Iterable[SubTablePath]:
# no visited because general otData cannot cycle (forward-offset only)
if root_accessor is None:
root_accessor = type(root).__name__
if predicate is None:
def predicate(path):
return True
if iter_subtables_fn is None:
def iter_subtables_fn(table):
return table.iterSubTables()
frontier: Deque[SubTablePath] = deque()
root_entry = BaseTable.SubTableEntry(root_accessor, root)
if not skip_root:
frontier.append((root_entry,))
else:
add_to_frontier_fn(
frontier,
[
(root_entry, subtable_entry)
for subtable_entry in iter_subtables_fn(root)
],
)
while frontier:
# path is (value, attr_name) tuples. attr_name is attr of parent to get value
path = frontier.popleft()
current = path[-1].value
if not predicate(path):
continue
yield SubTablePath(path)
new_entries = [
path + (subtable_entry,) for subtable_entry in iter_subtables_fn(current)
]
add_to_frontier_fn(frontier, new_entries)
|
