• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
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) -> Iterable[SubTablePath]:
36    """Depth-first search tree of BaseTables.
37
38    Args:
39        root (BaseTable): the root of the tree.
40        root_accessor (Optional[str]): attribute name for the root table, if any (mostly
41            useful for debugging).
42        skip_root (Optional[bool]): if True, the root itself is not visited, only its
43            children.
44        predicate (Optional[Callable[[SubTablePath], bool]]): function to filter out
45            paths. If True, the path is yielded and its subtables are added to the
46            queue. If False, the path is skipped and its subtables are not traversed.
47
48    Yields:
49        SubTablePath: tuples of BaseTable.SubTableEntry(name, table, index) namedtuples
50        for each of the nodes in the tree. The last entry in a path is the current
51        subtable, whereas preceding ones refer to its parent tables all the way up to
52        the root.
53    """
54    yield from _traverse_ot_data(
55        root,
56        root_accessor,
57        skip_root,
58        predicate,
59        lambda frontier, new: frontier.extendleft(reversed(new)),
60    )
61
62
63def bfs_base_table(
64    root: BaseTable,
65    root_accessor: Optional[str] = None,
66    skip_root: bool = False,
67    predicate: Optional[Callable[[SubTablePath], bool]] = None,
68) -> Iterable[SubTablePath]:
69    """Breadth-first search tree of BaseTables.
70
71    Args:
72        root (BaseTable): the root of the tree.
73        root_accessor (Optional[str]): attribute name for the root table, if any (mostly
74            useful for debugging).
75        skip_root (Optional[bool]): if True, the root itself is not visited, only its
76            children.
77        predicate (Optional[Callable[[SubTablePath], bool]]): function to filter out
78            paths. If True, the path is yielded and its subtables are added to the
79            queue. If False, the path is skipped and its subtables are not traversed.
80
81    Yields:
82        SubTablePath: tuples of BaseTable.SubTableEntry(name, table, index) namedtuples
83        for each of the nodes in the tree. The last entry in a path is the current
84        subtable, whereas preceding ones refer to its parent tables all the way up to
85        the root.
86    """
87    yield from _traverse_ot_data(
88        root,
89        root_accessor,
90        skip_root,
91        predicate,
92        lambda frontier, new: frontier.extend(new),
93    )
94
95
96def _traverse_ot_data(
97    root: BaseTable,
98    root_accessor: Optional[str],
99    skip_root: bool,
100    predicate: Optional[Callable[[SubTablePath], bool]],
101    add_to_frontier_fn: AddToFrontierFn,
102) -> Iterable[SubTablePath]:
103    # no visited because general otData cannot cycle (forward-offset only)
104    if root_accessor is None:
105        root_accessor = type(root).__name__
106
107    if predicate is None:
108
109        def predicate(path):
110            return True
111
112    frontier: Deque[SubTablePath] = deque()
113
114    root_entry = BaseTable.SubTableEntry(root_accessor, root)
115    if not skip_root:
116        frontier.append((root_entry,))
117    else:
118        add_to_frontier_fn(
119            frontier,
120            [(root_entry, subtable_entry) for subtable_entry in root.iterSubTables()],
121        )
122
123    while frontier:
124        # path is (value, attr_name) tuples. attr_name is attr of parent to get value
125        path = frontier.popleft()
126        current = path[-1].value
127
128        if not predicate(path):
129            continue
130
131        yield SubTablePath(path)
132
133        new_entries = [
134            path + (subtable_entry,) for subtable_entry in current.iterSubTables()
135        ]
136
137        add_to_frontier_fn(frontier, new_entries)
138