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