Tree: A Branching Regular Expression#
- class my.regex.meta.Tree.Tree(*args: str | Atom | Regex | Sequence[Regex] | Iterator[Regex] | Self, prefix: str | Atom | Regex = '', branches: list[Regex] | None = None, suffix: str | Atom | Regex = '', quantifier: str | Quantifier = '', inner_quant: str | Quantifier = '', max_expand: int = 4)#
A collection of alternative “branches” for a regex position, for use in optimization code.
Examples
Decompose an alternation, then factor its shared context back out:
>>> from my import Tree >>> tree = Tree('(?:br1|br2|br3)').expand() >>> [str(branch) for branch in tree.branches] ['br1', 'br2', 'br3'] >>> tree = tree.factor() >>> (str(tree.prefix), [str(branch) for branch in tree.branches]) ('br', ['[123]'])
I Initial Methods#
- classmethod Tree.new(*args: str | Atom | Regex | Sequence[Regex] | Iterator[Regex] | Self, **kwargs: Any) Self#
Construct a new instance from the given branches, casting flexibly.
Examples
Alternated strings and standalone arguments both become branches:
>>> from my import Tree >>> [str(branch) for branch in Tree.new('a|b', 'c').branches] ['a', 'b', 'c']
II Primary Methods#
- Tree.expand_branch(branch: Regex) Generator[Regex]#
Expand a branch into an equivalent alternation of multiple branches, if possible.
If no atoms within are expandable, it will naturally return the same branch that was passed in, unchanged.
- Parameters:
branch – The branch to expand.
- Yields:
Every possible permutation we can make with the expanded contents of that branch, that are still nonetheless isomorphic to the original branch when taken as a set.
- Tree.expand_group(atom: Atom) Self#
Split an alternating group into branches, grouped only by shared prefix.
- classmethod Tree.expand_set(atom: Atom) Self#
Split a set atom into individual branches, if possible.
Examples
An optional set contributes an extra empty branch:
>>> from my.regex.meta import SetAtom >>> tree = Tree.expand_set(SetAtom('[abc]?')) >>> ([str(branch) for branch in tree.branches], str(tree.quantifier)) (['', 'a', 'b', 'c'], '')
- classmethod Tree.condense_atomic_branches(branches: list[Regex]) list[Regex]#
Condense a set of monatomic branches into an isomorphic, shorter version (if possible).
Note
This is just a special case of
condense()below where all the alternatives are themselves atomic.- Parameters:
branches – A list of valid expressions, each of which has just one atom.
- Returns:
An isomorphic version of the inputs that has been optimized as much as possible.
Examples
Set-eligible branches merge into one character set; the rest pass through:
>>> from my import Regex >>> branches = [Regex('a'), Regex('b'), Regex('(?:one)')] >>> [str(branch) for branch in Tree.condense_atomic_branches(branches)] ['(?:one)', '[ab]']
- classmethod Tree.condense_blocks(trees: list[Self]) list[Regex]#
Construct a single tree from a list of trees, factoring out shared suffixes if possible.
We don’t check for shared prefixes because those would’ve been handled already as part of the primary
factor()step – each tree represents a prefix group.- Parameters:
trees – The list of tree instances to condense.
- Returns:
The optimized list of regex branches, isomorphic to the original set of trees.
III Properties#
IV Modifiers#
- Tree.clean() Self#
Clean the given branches by removing empty branches and combining optional ones.
Uses the parent’s context to allow for further optimizations that are only valid in the given context.
- Returns:
This tree, cleaned in place.
Examples
An empty branch is absorbed into an optional quantifier:
>>> from my import Tree >>> tree = Tree('a', 'b', '').clean() >>> ([str(branch) for branch in tree.branches], str(tree.quantifier)) (['a', 'b'], '?')
- Tree.expand() Self#
Recursively split all our branches into more explicit, longer versions.
The number of atoms expanded per branch is capped by the
max_expandfield.- Returns:
This tree, with its branches expanded in place.
Examples
Expand an optional suffix into explicit branches:
>>> from my import Tree >>> [str(branch) for branch in Tree(r'confirm(?:ation)?').expand().branches] ['confirm', 'confirmation']
Character sets expand too:
>>> [str(branch) for branch in Tree(r'a[bc]d').expand().branches] ['abd', 'acd']
- Tree.factor() Self#
Factor out common prefixes and suffixes from the branches in the main data structure.
Examples
A shared prefix moves into the tree’s context:
>>> from my import Tree >>> tree = Tree('street', 'stream', 'strap').factor() >>> (str(tree.prefix), str(tree.render())) ('str', 'str(?>eet|eam|ap)')
- Tree.condense() Self#
Construct an optimized regex from branches by factoring common prefixes and suffixes.
This method builds an efficient regex pattern by identifying and extracting common prefixes and suffixes from multiple branches, minimizing redundancy in the result.
Examples
The
expand()/condense()cycle is the core ofRegexStore’s optimization:>>> from my import Tree >>> tree = Tree('grape', 'grapefruit', 'apple').expand() >>> str(tree.condense().render()) '(?>apple|grape(?:fruit)?)'
V Serialization#
- Tree.render() Regex#
Render this tree’s branches into a regex group, applying optimizations where possible.
- Returns:
A pattern representing the properly combined & wrapped branches.
Examples
Simple branches are joined atomically, with the context applied around them:
>>> from my import Tree >>> str(Tree('a', 'b', quantifier='?').render()) '(?>a|b)?'
- Tree.serialize() list[Regex]#
Serialize this tree into a list of branches with context applied, for intermediate use.
This output is intended for consumption by other trees, rather than callers building expressions. For the output to serve as an isomorphic version of this tree, all the branches must be alternated together.
Examples
Contextual trees serialize to a single rendered branch:
>>> from my import Tree >>> [str(branch) for branch in Tree('a', 'b', prefix='x').serialize()] ['x(?>a|b)']