163 lines
5.4 KiB
Python
163 lines
5.4 KiB
Python
"""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)
|