Abstract base classes for representing sequences in Graphtage’s intermediate representation.

sequences classes


class graphtage.sequences.SequenceEdit(from_node: graphtage.sequences.SequenceNode, *args, **kwargs)

Bases: graphtage.AbstractCompoundEdit, abc.ABC

An edit type for sequence nodes.

__init__(from_node: graphtage.sequences.SequenceNode, *args, **kwargs)

Initializes a sequence edit.

  • from_node – The node being edited.

  • *args – The remainder of the arguments to be passed to AbstractCompoundEdit.__init__().

  • **kwargs – The remainder of the keyword arguments to be passed to AbstractCompoundEdit.__init__().


ValueError – If from_node is not an instance of SequenceNode.

__iter__() → Iterator[graphtage.Edit]

Returns an iterator over this edit’s sub-edits.


The result of AbstractCompoundEdit.edits()

Return type



Tests whether the bounds of this edit are less than the bounds of other.


Returns the bounds of this edit.

This defaults to the bounds provided when this AbstractEdit was constructed. If an upper bound was not provided to the constructor, the upper bound defaults to:

self.from_node.total_size + self.to_node.total_size + 1

A range bounding the cost of this edit.

Return type


abstract edits() → Iterator[graphtage.Edit]

Returns an iterator over this edit’s sub-edits


Returns whether this edit has a non-zero cost.

This will tighten the edit’s bounds until either its lower bound is greater than zero or its bounds are definitive.


An edit is complete when no further calls to Edit.tighten_bounds() will change the nature of the edit.

This implementation considers an edit complete if it is valid and its bounds are definitive:

return not self.valid or self.bounds().definitive()

If an edit is able to discern that it has a unique solution even if its final bounds are unknown, it should reimplement this method to define that check.

For example, in the case of a CompoundEdit, this method should only return True if no future calls to Edit.tighten_bounds() will affect the result of CompoundEdit.edits().


True if subsequent calls to Edit.tighten_bounds() will only serve to tighten the bounds of this edit and will not affect the semantics of the edit.

Return type


on_diff(from_node: graphtage.EditedTreeNode)

A callback for when an edit is assigned to an EditedTreeNode in TreeNode.diff().

This default implementation adds the edit to the node, and recursively calls Edit.on_diff() on all of the sub-edits:

from_node.edit = self
for edit in self.edits():

from_node – The edited node that was added to the diff

print(formatter: graphtage.GraphtageFormatter, printer: graphtage.printer.Printer)

Prints this edit.

This is equivalent to:

formatter.get_formatter(self.sequence)(printer, self.sequence)
property sequence

Returns the sequence being edited.

This is a convenience function solely to aid in automated type checking. It is equivalent to:

typing.cast(SequenceNode, self.from_node)
abstract tighten_bounds()bool

Tightens the Edit.bounds() on the cost of this edit, if possible.


True if the bounds have been tightened.

Return type



Implementations of this function should return False if and only if self.bounds().definitive().

property valid

Returns whether this edit is valid


class graphtage.sequences.SequenceFormatter(start_symbol: str, end_symbol: str, delimiter: str, delimiter_callback: Optional[Callable[[graphtage.printer.Printer], Any]] = None)

Bases: graphtage.GraphtageFormatter

A formatter for sequence nodes and edits.

This class will typically be subclassed so that its methods can be overridden to match the style of its parent formatter. For an example, see the implementation of graphtage.json.JSONListFormatter and graphtage.json.JSONDictFormatter.

DEFAULT_INSTANCE: Formatter[T] = <graphtage.GraphtageFormatter object>
__init__(start_symbol: str, end_symbol: str, delimiter: str, delimiter_callback: Optional[Callable[[graphtage.printer.Printer], Any]] = None)

Initializes a sequence formatter.

  • start_symbol – The symbol to print at the start of the sequence.

  • end_symbol – The symbol to print at the end of the sequence.

  • delimiter – A delimiter to print between items.

  • delimiter_callback

    A callback for when a delimiter is to be printed. If omitted, this defaults to:

    lambda p: p.write(delimiter)

static __new__(cls, *args, **kwargs) → graphtage.formatter.Formatter[~T][T]

Instantiates a new formatter.

This automatically instantiates and populates Formatter.sub_formatters and sets their parent to this new formatter.

edit_print(printer: graphtage.printer.Printer, edit: graphtage.Edit)

Called when the edit for an item is to be printed.

If the SequenceNode being printed either is not edited or has no edits, then the edit passed to this function will be a Match(child, child, 0).

This implementation simply delegates the print to the Formatting Protocol:

self.print(printer, edit)
get_formatter(item: T) → Optional[Callable[[graphtage.printer.Printer, T], Any]]

Looks up a formatter for the given item using this formatter as a base.

Equivalent to:

get_formatter(item.__class__, base_formatter=self)
is_partial: bool = True

This is a partial formatter; it will not be automatically used in the Formatting Protocol.

item_newline(printer: graphtage.printer.Printer, is_first: bool = False, is_last: bool = False)

Called before each node is printed.

This is also called one extra time after the last node, if there is at least one node printed.

The default implementation is simply:

items_indent(printer: graphtage.printer.Printer)graphtage.printer.Printer

Returns a Printer context with an indentation.

This is called as:

with self.items_indent(printer) as p:

immediately after the self.start_symbol is printed, but before any of the items have been printed.

This default implementation is equivalent to:

return printer.indent()
parent: Optional[Formatter[T]] = None
print(printer: graphtage.printer.Printer, node_or_edit: Union[TreeNode, Edit], with_edits: bool = True)

Prints the given node or edit.

  • printer – The printer to which to write.

  • node_or_edit – The node or edit to print.

  • with_edits – If :keyword:True, print any edits associated with the node.


The protocol for determining how a node or edit should be printed is very complex due to its extensibility. See the Printing Protocol for a detailed description.

print_SequenceNode(printer: graphtage.printer.Printer, node: graphtage.sequences.SequenceNode)

Formats a sequence node.

The protocol for this function is as follows:

property root

Returns the root formatter.

sub_format_types: Sequence[Type[Formatter[T]]] = ()
sub_formatters: List[Formatter[T]] = []


class graphtage.sequences.SequenceNode(children: T)

Bases: graphtage.ContainerNode, typing.Generic, abc.ABC

A node representing a sequence, like a list, set, or dict.

__init__(children: T)

Initializes a sequence node.


children – A sequence of TreeNodes. This is assigned to the protected member SequenceNode._children.

__iter__() → Iterator[graphtage.TreeNode]

Iterates over this sequence’s child nodes.

This is equivalent to:

return iter(self._children)

The number of children of this sequence.

This is equivalent to:

return len(self._children)

Tests whether all of the children of this container are leaves.

Equivalent to:

all(c.is_leaf for c in self)

True if all children are leaves.

Return type



Calculates the total size of this sequence.

This is equivalent to:

return sum(c.total_size for c in self)
children() → List[graphtage.TreeNode]

The children of this node.

Equivalent to:

abstract property container_type

Returns the container type used to store SequenceNode._children.

This is used for performing a deep copy of this node in the SequenceNode.editable_dict() function.

dfs() → Iterator[graphtage.TreeNode]

Performs a depth-first traversal over all of this node’s descendants.

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
diff(node: graphtage.TreeNode) → Union[graphtage.EditedTreeNode, T]

Performs a diff against the provided node.


node – The node against which to perform the diff.


An edited version of this node with all edits being completed.

Return type

Union[EditedTreeNode, T]

edit_modifiers: Optional[List[Callable[[TreeNode, TreeNode], Optional[graphtage.Edit]]]] = None
editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on all children.

This is equivalent to:

ret = dict(self.__dict__)
ret['_children'] = self.container_type(n.make_edited() for n in self)
return ret

This is used by SequenceNode.make_edited().

property edited

Returns whether this node has been edited.

The default implementation returns False, whereas EditedTreeNode.edited() returns True.

classmethod edited_type() → Type[Union[graphtage.EditedTreeNode, T]]

Dynamically constructs a new class that is both a TreeNode and an EditedTreeNode.

The edited type’s member variables are populated by the result of TreeNode.editable_dict() of the TreeNode it wraps:

new_node.__dict__ = dict(wrapped_tree_node.editable_dict())

A class that is both a TreeNode and an EditedTreeNode. Its constructor accepts a TreeNode that it will wrap.

Return type

Type[Union[EditedTreeNode, T]]

abstract edits(node: graphtage.TreeNode)graphtage.Edit

Calculates the best edit to transform this node into the provided node.


node – The node to which to transform.


The best possible edit.

Return type


get_all_edits(node: graphtage.TreeNode) → Iterator[graphtage.Edit]

Returns an iterator over all edits that will transform this node into the provided node.


node – The node to which to transform this one.


An iterator over edits. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type


property is_leaf

Container nodes are never leaves, even if they have no children.



Return type


make_edited() → Union[graphtage.EditedTreeNode, T]

Returns a new, copied instance of this node that is also an instance of EditedTreeNode.

This is equivalent to:

return self.edited_type()(self)

A copied version of this node that is also an instance of EditedTreeNode and thereby mutable.

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

SequenceFormatter('[', ']', ',').print(printer, self)
abstract to_obj()

Returns a pure Python representation of this node.

For example, a node representing a list, like graphtage.ListNode, should return a Python list. A node representing a mapping, like graphtage.MappingNode, should return a Python dict. Container nodes should recursively call TreeNode.to_obj() on all of their children.

This is used solely for the providing objects to operate on in the commandline expressions evaluation, for options like –match-if and –match-unless.

property total_size

The size of this node.

This is an arbitrary, immutable value that is used to calculate the bounded costs of edits on this node.

The first time this property is called, its value will be set and memoized by calling TreeNode.calculate_total_size().


An arbitrary integer representing the size of this node.

Return type