graphtage

graphtage classes

AbstractCompoundEdit

class graphtage.AbstractCompoundEdit(from_node: TreeNode, to_node: TreeNode | None = None, constant_cost: int | None = 0, cost_upper_bound: int | None = None)

Bases: AbstractEdit, CompoundEdit, ABC

Abstract base class implementing the CompoundEdit protocol.

__init__(from_node: TreeNode, to_node: TreeNode | None = None, constant_cost: int | None = 0, cost_upper_bound: int | None = None)

Constructs a new Edit.

Parameters:

• from_node – The node that this edit transforms.

• to_node – The node that this edit transforms from_node into.

• constant_cost – A optional lower bound on the cost of this edit.

• cost_upper_bound – An optional upper bound on the cost of this edit.

__iter__() → Iterator[Edit]

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

Returns:

The result of AbstractCompoundEdit.edits()

Return type:

Iterator[Edit]

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

abstract edits() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: 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
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

This implementation is equivalent to:

for edit in self.edits():
    edit.print(formatter, printer)

abstract tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

property valid: bool

Returns whether this edit is valid

AbstractEdit

class graphtage.AbstractEdit(from_node: TreeNode, to_node: TreeNode | None = None, constant_cost: int | None = 0, cost_upper_bound: int | None = None)

Bases: Debuggable, Edit, ABC

Abstract base class for the Edit protocol.

__init__(from_node: TreeNode, to_node: TreeNode | None = None, constant_cost: int | None = 0, cost_upper_bound: int | None = None)

Constructs a new Edit.

Parameters:

• from_node – The node that this edit transforms.

• to_node – The node that this edit transforms from_node into.

• constant_cost – A optional lower bound on the cost of this edit.

• cost_upper_bound – An optional upper bound on the cost of this edit.

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: EditedTreeNode | TreeNode)

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

This default implementation adds the edit to the node:

from_node.edit = self
from_node.edit_list.append(self)

Implementations of the Edit protocol that have sub-edits (like CompoundEdit) should recursively call Edit.on_diff() on its sub-edits.

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

abstract tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

property valid: bool

Returns whether this edit is valid

BoolNode

class graphtage.BoolNode(bool_like: bool)

Bases: LeafNode

A node containing either True or False.

__init__(bool_like: bool)

Creates a node with the given object.

Parameters:

obj – The underlying Python object wrapped by the node.

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

calculate_total_size() → int

By default, leaf nodes’ sizes are equal to the length of their wrapped object’s string representation.

This is equivalent to:

return len(str(self.object))

However, subclasses may override this function to return whatever size is required.

Returns:

The length of the string representation of self.object.

Return type:

int

children() → Collection[TreeNode]

Leaf nodes have no children, so this always returns an empty tuple.

Returns:

An empty tuple.

Return type:

tuple

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → C

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

Returns whether this node is a leaf.

This implementation is equivalent to:

return len(self.children()) == 0

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints this leaf node.

By default, leaf nodes print the repr() of their wrapped object:

printer.write(repr(self.object))

Parameters:

printer – The printer to which to write this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

BuildOptions

class graphtage.BuildOptions(*, allow_key_edits=True, auto_match_keys=True, allow_list_edits=True, allow_list_edits_when_same_length=True, check_for_cyces=True, ignore_cycles=False, printer=<graphtage.printer.Printer object>, **kwargs)

Bases: object

A class for passing options to tree building functions in Filetype

__getattr__(item)

Default all undefined options to False

__init__(*, allow_key_edits=True, auto_match_keys=True, allow_list_edits=True, allow_list_edits_when_same_length=True, check_for_cyces=True, ignore_cycles=False, printer=<graphtage.printer.Printer object>, **kwargs)

Initializes the options. All keyword values will be set as attributes of this class.

Options not specified will default to False.

copy() → BuildOptions

CompoundEdit

class graphtage.CompoundEdit(*args, **kwargs)

Bases: Edit, Protocol

A protocol for edits that are composed of sub-edits

__init__(*args, **kwargs)

abstract __iter__() → Iterator[Edit]

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

abstract bounds() → Range

The bounds on the cost of this edit.

The lower bound must always be finite and non-negative.

Returns:

The bounds on the cost of this edit.

Return type:

Range

abstract edits() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

abstract is_complete() → bool

Returns True if all of the final edits are available.

Note

This should return True if the edit can determine that its representation will no longer change, regardless of whether our bounds have been fully tightened.

on_diff(from_node: 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
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

abstract tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

abstract property valid: bool

Returns False if the edit has determined that it is no longer valid

ConstantCostEdit

class graphtage.ConstantCostEdit(from_node: TreeNode, to_node: TreeNode | None = None, cost: int = 0)

Bases: AbstractEdit, ABC

An edit whose definitive cost is known at the time of construction.

__init__(from_node: TreeNode, to_node: TreeNode | None = None, cost: int = 0)

Constructs a new edit.

Parameters:

• from_node – The node being edited.

• to_node – The node into which from_node is being transformed.

• cost – The constant cost of the edit.

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: EditedTreeNode | TreeNode)

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

This default implementation adds the edit to the node:

from_node.edit = self
from_node.edit_list.append(self)

Implementations of the Edit protocol that have sub-edits (like CompoundEdit) should recursively call Edit.on_diff() on its sub-edits.

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

tighten_bounds() → bool

This always returns False

property valid: bool

Returns whether this edit is valid

ContainerNode

class graphtage.ContainerNode(*args, **kwds)

Bases: TreeNode, Sized, ABC

A tree node that has children.

__init__()

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

all_children_are_leaves() → bool

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

Equivalent to:

all(c.is_leaf for c in self)

Returns:

True if all children are leaves.

Return type:

bool

abstract calculate_total_size() → int

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

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

children() → Sequence[TreeNode]

The children of this node.

Equivalent to:

list(self)

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → T

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

abstract edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

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

Returns:

False

Return type:

bool

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

abstract print(printer: Printer)

Prints this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

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: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

DictNode

class graphtage.DictNode(items: Iterable[T], auto_match_keys: bool = True)

Bases: MappingNode, MultiSetNode[KeyValuePairNode]

A dictionary node implemented as a multiset of key/value pairs.

This is the default dictionary type used by Graphtage. Unlike its more efficient alternative, FixedKeyDictNode, this class supports matching dictionaries with duplicate keys.

__contains__(item: TreeNode)

Tests whether the given item is a key in this mapping.

The implementation is equivalent to:

return any(k == item for k, _ in self.items())

Note

This implementation runs in worst-case linear time in the size of the mapping.

Parameters:

item – The key of the item sought.

Returns:

True if the key exists in this mapping.

Return type:

bool

__getitem__(item: TreeNode) → KeyValuePairNode

Looks up a key/value pair item from this mapping by its key.

The implementation is equivalent to:

for kvp in self:
    if kvp.key == item:
        return kvp
raise KeyError(item)

Note

This implementation runs in worst-case linear time in the size of the mapping.

Parameters:

item – The key of the key/value pair that is sought.

Returns:

The first key/value pair found with key item.

Return type:

KeyValuePairNode

Raises:

KeyError – If the key is not found.

__init__(items: Iterable[T], auto_match_keys: bool = True)

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

all_children_are_leaves() → bool

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

Equivalent to:

all(c.is_leaf for c in self)

Returns:

True if all children are leaves.

Return type:

bool

calculate_total_size()

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

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

children() → Sequence[TreeNode]

The children of this node.

Equivalent to:

list(self)

property container_type: Type[HashableCounter[T]]

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.

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[T]) → C

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

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: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

classmethod from_dict(source_dict: Dict[LeafNode, TreeNode]) → T

Constructs a DictNode from a mapping of LeafNode to TreeNode.

Parameters:

source_dict – The source mapping.

Returns:

The resulting DictNode.

Return type:

DictNode

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

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

Returns:

False

Return type:

bool

items() → Iterator[Tuple[TreeNode, TreeNode]]

Iterates over the key/value pairs in this mapping, similar to dict.items().

The implementation is equivalent to:

for kvp in self:
    yield kvp.key, kvp.value

since MappingNode.__iter__() returns an iterator over graphtage.KeyValuePairNode.

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

classmethod make_key_value_pair_node(key: LeafNode, value: TreeNode, allow_key_edits: bool = True) → KeyValuePairNode

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

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

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj() → Dict[Any, Any]

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: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

Edit

class graphtage.Edit(*args, **kwargs)

Bases: Bounded, Protocol

A protocol for defining an edit.

initial_bounds

The initial bounds of this edit. Classes implementing this protocol can, for example, set this by calling self.bounds() during initialization.

Type:

Range

from_node

The node that this edit transforms.

Type:

TreeNode

__init__(*args, **kwargs)

abstract bounds() → Range

The bounds on the cost of this edit.

The lower bound must always be finite and non-negative.

Returns:

The bounds on the cost of this edit.

Return type:

Range

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

abstract is_complete() → bool

Returns True if all of the final edits are available.

Note

This should return True if the edit can determine that its representation will no longer change, regardless of whether our bounds have been fully tightened.

on_diff(from_node: EditedTreeNode | TreeNode)

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

This default implementation adds the edit to the node:

from_node.edit = self
from_node.edit_list.append(self)

Implementations of the Edit protocol that have sub-edits (like CompoundEdit) should recursively call Edit.on_diff() on its sub-edits.

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

abstract tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

abstract property valid: bool

Returns False if the edit has determined that it is no longer valid

EditCollection

class graphtage.EditCollection(from_node: TreeNode, to_node: TreeNode | None, collection: Type[C], add_to_collection: Callable[[C, Edit], Any], edits: Iterator[Edit], explode_edits: bool = True)

Bases: AbstractCompoundEdit, Generic[C]

An edit comprised of one or more sub-edits.

__init__(from_node: TreeNode, to_node: TreeNode | None, collection: Type[C], add_to_collection: Callable[[C, Edit], Any], edits: Iterator[Edit], explode_edits: bool = True)

Constructs a new Edit.

Parameters:

• from_node – The node that this edit transforms.

• to_node – The node that this edit transforms from_node into.

• constant_cost – A optional lower bound on the cost of this edit.

• cost_upper_bound – An optional upper bound on the cost of this edit.

__iter__() → Iterator[Edit]

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

Returns:

The result of AbstractCompoundEdit.edits()

Return type:

Iterator[Edit]

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

edits() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: 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
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

This implementation is equivalent to:

for edit in self.edits():
    edit.print(formatter, printer)

tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

property valid: bool

Returns whether this edit is valid

EditSequence

class graphtage.EditSequence(from_node: TreeNode, to_node: TreeNode | None, edits: Iterator[Edit], explode_edits: bool = True)

Bases: EditCollection[List]

An EditCollection using a list as the underlying container.

__init__(from_node: TreeNode, to_node: TreeNode | None, edits: Iterator[Edit], explode_edits: bool = True)

Constructs a new Edit.

Parameters:

• from_node – The node that this edit transforms.

• to_node – The node that this edit transforms from_node into.

• constant_cost – A optional lower bound on the cost of this edit.

• cost_upper_bound – An optional upper bound on the cost of this edit.

__iter__() → Iterator[Edit]

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

Returns:

The result of AbstractCompoundEdit.edits()

Return type:

Iterator[Edit]

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

edits() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: 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
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

This implementation is equivalent to:

for edit in self.edits():
    edit.print(formatter, printer)

tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

property valid: bool

Returns whether this edit is valid

EditedTreeNode

class graphtage.EditedTreeNode

Bases: object

A mixin for a TreeNode that has been edited.

In practice, an object that is an instance of EditedTreeNode will always also be an instance of TreeNode.

This class should almost never be instantiated directly; it is used by TreeNode.diff().

__init__()

property edited: bool

Edited tree nodes are always edited

edited_cost() → int

The cost of the edit applied to this node.

This will first fully tighten all of the bounds of self.edit_list, and then return the sum of their upper bounds:

while any(e.tighten_bounds() for e in self.edit_list):
    pass
return sum(e.bounds().upper_bound for e in self.edit_list)

Since all of the edits are fully tightened, this function returns a int instead of a graphtage.bounds.Bounds.

Returns:

The sum of the costs of the edits applied to this node.

Return type:

int

Filetype

class graphtage.Filetype(type_name: str, default_mimetype: str, *mimetypes: str)

Bases: object

Abstract base class from which all Graphtage file formats should extend.

When this class is subclassed, the subclass will automatically be added to Graphtage’s filetype registry. This includes automatic inclusion in graphtage’s command line arguments and mime type auto-detection in get_filetype().

__init__(type_name: str, default_mimetype: str, *mimetypes: str)

Initializes a new Graphtage file format type

Parameters:

• type_name – A short name for the Filetype. This will be used for specifying this Filetype via command line arguments.

• default_mimetype – The default mimetype to be assigned to this Filetype.

• *mimetypes – Zero or more additional mimetypes that should be associated with this Filetype.

Raises:

ValueError – The type_name and/or one of the mimetypes of this Filetype conflicts with that of a preexisting Filetype.

abstract build_tree(path: str, options: BuildOptions | None = None) → TreeNode

Builds an intermediate representation tree from a file of this Filetype.

Parameters:

• path – Path to the file to parse

• options – An optional set of options for building the tree

Returns:

The root tree node of the provided file

Return type:

TreeNode

abstract build_tree_handling_errors(path: str, options: BuildOptions | None = None) → str | TreeNode

Same as Filetype.build_tree(), but it should return a human-readable error string on failure.

This function should never throw an exception.

Parameters:

• path – Path to the file to parse

• options – An optional set of options for building the tree

Returns:

On success, the root tree node, or a string containing the error message on failure.

Return type:

Union[str, TreeNode]

default_instance: Filetype

abstract get_default_formatter() → GraphtageFormatter

Returns the default formatter for printing files of this type.

FiletypeWatcher

class graphtage.FiletypeWatcher(name, bases, namespace, **kwargs)

Bases: ABCMeta

Abstract metaclass for the Filetype class.

This registers any subclasses of Filetype, automatically adding them to the graphtage command line arguments and mimetype lookup in get_filetype().

__init__(name, bases, clsdict)

__instancecheck__(instance)

Override for isinstance(instance, cls).

__subclasscheck__(subclass)

Override for issubclass(subclass, cls).

_abc_caches_clear()

Clear the caches (for debugging or testing).

_abc_registry_clear()

Clear the registry (for debugging or testing).

_dump_registry(file=None)

Debug helper to print the ABC registry.

mro()

Return a type’s method resolution order.

register(subclass)

Register a virtual subclass of an ABC.

Returns the subclass, to allow usage as a class decorator.

FixedKeyDictNode

class graphtage.FixedKeyDictNode(children: T)

Bases: MappingNode, SequenceNode[Dict[LeafNode, KeyValuePairNode]]

A dictionary that only attempts to match two KeyValuePairNode objects if they share the same key.

This is the most efficient dictionary matching node type, and is what is used with the --no-key-edits/-k command line argument.

Note

This implementation does not currently support duplicate keys.

__init__(children: T)

Initializes a sequence node.

Parameters:

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

__len__() → int

The number of children of this sequence.

This is equivalent to:

return len(self._children)

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

all_children_are_leaves() → bool

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

Equivalent to:

all(c.is_leaf for c in self)

Returns:

True if all children are leaves.

Return type:

bool

calculate_total_size()

Calculates the total size of this sequence.

This is equivalent to:

return sum(c.total_size for c in self)

children() → Sequence[TreeNode]

The children of this node.

Equivalent to:

list(self)

property container_type: Type[Dict[LeafNode, KeyValuePairNode]]

The container type required by graphtage.sequences.SequenceNode

Returns:

dict

Return type:

Type[Dict[LeafNode, KeyValuePairNode]]

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → T

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

classmethod from_dict(source_dict: Dict[LeafNode, TreeNode]) → T

Constructs a FixedKeyDictNode from a mapping of LeafNode to TreeNode.

Parameters:

source_dict – The source mapping.

Note

This implementation does not currently check for duplicate keys. Only the first key returned from source_dict.items() will be included in the output.

Returns:

The resulting FixedKeyDictNode

Return type:

FixedKeyDictNode

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

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

Returns:

False

Return type:

bool

items() → Iterator[Tuple[LeafNode, TreeNode]]

Iterates over the key/value pairs in this mapping, similar to dict.items().

The implementation is equivalent to:

for kvp in self:
    yield kvp.key, kvp.value

since MappingNode.__iter__() returns an iterator over graphtage.KeyValuePairNode.

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

classmethod make_key_value_pair_node(key: LeafNode, value: TreeNode, allow_key_edits: bool = True) → KeyValuePairNode

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

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

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj() → Dict[Any, Any]

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: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

FixedKeyDictNodeEdit

class graphtage.FixedKeyDictNodeEdit(from_node: FixedKeyDictNode, to_node: TreeNode, edits: Iterator[Edit])

Bases: SequenceEdit, EditCollection[List]

The edit type returned by FixedKeyDictNode.

__init__(from_node: FixedKeyDictNode, to_node: TreeNode, edits: Iterator[Edit])

Initializes a sequence edit.

Parameters:

• 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__().

Raises:

ValueError – If from_node is not an instance of SequenceNode.

__iter__() → Iterator[Edit]

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

Returns:

The result of AbstractCompoundEdit.edits()

Return type:

Iterator[Edit]

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

edits() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: 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
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Prints this edit.

This is equivalent to:

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

property sequence: SequenceNode

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)

tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

property valid: bool

Returns whether this edit is valid

FloatNode

class graphtage.FloatNode(float_like: float)

Bases: LeafNode

A node containing a float

__init__(float_like: float)

Creates a node with the given object.

Parameters:

obj – The underlying Python object wrapped by the node.

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

calculate_total_size() → int

By default, leaf nodes’ sizes are equal to the length of their wrapped object’s string representation.

This is equivalent to:

return len(str(self.object))

However, subclasses may override this function to return whatever size is required.

Returns:

The length of the string representation of self.object.

Return type:

int

children() → Collection[TreeNode]

Leaf nodes have no children, so this always returns an empty tuple.

Returns:

An empty tuple.

Return type:

tuple

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → C

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

Returns whether this node is a leaf.

This implementation is equivalent to:

return len(self.children()) == 0

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints this leaf node.

By default, leaf nodes print the repr() of their wrapped object:

printer.write(repr(self.object))

Parameters:

printer – The printer to which to write this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

GraphtageFormatter

class graphtage.GraphtageFormatter(*args, **kwargs)

Bases: Formatter[Union[TreeNode, Edit]]

A base class for defining formatters that operate on TreeNode and Edit.

DEFAULT_INSTANCE: Formatter[T] = <graphtage.GraphtageFormatter object>

A default instance of this formatter, automatically instantiated by the FormatterChecker metaclass.

__init__()

static __new__(cls, *args, **kwargs) → Formatter[T]

Instantiates a new formatter.

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

get_formatter(item: T) → Callable[[Printer, T], Any] | None

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 = False

parent: Formatter[T] | None = None

The parent formatter for this formatter instance.

This is automatically populated by Formatter.__new__() and should never be manually modified.

print(printer: Printer, node_or_edit: TreeNode | Edit, with_edits: bool = True)

Prints the given node or edit.

Parameters:

• 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.

Note

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.

property root: Formatter[T]

Returns the root formatter.

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

A list of formatter types that should be used as sub-formatters in the Formatting Protocol.

sub_formatters: List[Formatter[T]] = []

The list of instantiated formatters corresponding to Formatter.sub_format_types.

This list is automatically populated by Formatter.__new__() and should never be manually modified.

Insert

class graphtage.Insert(to_insert: TreeNode, insert_into: TreeNode, penalty: int = 1)

Bases: ConstantCostEdit

A constant cost edit specifying that a node should be added to a container.

INSERT_STRING: str = '++'

__init__(to_insert: TreeNode, insert_into: TreeNode, penalty: int = 1)

Constructs a new edit.

Parameters:

• from_node – The node being edited.

• to_node – The node into which from_node is being transformed.

• cost – The constant cost of the edit.

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

property insert_into: TreeNode

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: EditedTreeNode)

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

This default implementation adds the edit to the node:

from_node.edit = self
from_node.edit_list.append(self)

Implementations of the Edit protocol that have sub-edits (like CompoundEdit) should recursively call Edit.on_diff() on its sub-edits.

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

tighten_bounds() → bool

This always returns False

property to_insert: TreeNode

property valid: bool

Returns whether this edit is valid

IntegerNode

class graphtage.IntegerNode(int_like: int)

Bases: LeafNode

A node containing an int

__init__(int_like: int)

Creates a node with the given object.

Parameters:

obj – The underlying Python object wrapped by the node.

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

calculate_total_size() → int

By default, leaf nodes’ sizes are equal to the length of their wrapped object’s string representation.

This is equivalent to:

return len(str(self.object))

However, subclasses may override this function to return whatever size is required.

Returns:

The length of the string representation of self.object.

Return type:

int

children() → Collection[TreeNode]

Leaf nodes have no children, so this always returns an empty tuple.

Returns:

An empty tuple.

Return type:

tuple

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → C

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

Returns whether this node is a leaf.

This implementation is equivalent to:

return len(self.children()) == 0

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints this leaf node.

By default, leaf nodes print the repr() of their wrapped object:

printer.write(repr(self.object))

Parameters:

printer – The printer to which to write this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

KeyValuePairEdit

class graphtage.KeyValuePairEdit(from_kvp: KeyValuePairNode, to_kvp: KeyValuePairNode)

Bases: AbstractCompoundEdit

An edit type for two key/value pairs

__init__(from_kvp: KeyValuePairNode, to_kvp: KeyValuePairNode)

Creates a key/value pair edit.

Parameters:

• from_kvp – The key/value pair from which to match.

• to_kvp – The key/value pair to which to match.

Raises:

ValueError – If from_kvp.allow_key_edits and the keys do not match.

__iter__() → Iterator[Edit]

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

Returns:

The result of AbstractCompoundEdit.edits()

Return type:

Iterator[Edit]

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

edits() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: 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
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

This implementation is equivalent to:

for edit in self.edits():
    edit.print(formatter, printer)

tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

property valid: bool

Returns whether this edit is valid

KeyValuePairNode

class graphtage.KeyValuePairNode(key: LeafNode, value: TreeNode, allow_key_edits: bool = True)

Bases: ContainerNode

A node containing a key/value pair.

This is used by nodes subclassing MappingNode.

__eq__(other)

Tests whether this key/value pair equals another.

Equivalent to:

isinstance(other, KeyValuePair) and self.key == other.key and self.value == other.value

Parameters:

other – The object to test.

Returns:

True if this key/value pair is equal to other.

Return type:

bool

__init__(key: LeafNode, value: TreeNode, allow_key_edits: bool = True)

Creates a new key/value pair node.

Parameters:

• key – The key of the pair.

• value – The value of the pair.

• allow_key_edits – If False, only consider matching against another key/value pair node if it has the same key.

__lt__(other)

Compares this key/value pair to another.

If other is also an instance of KeyValuePairNode, return:

(self.key < other.key) or (self.key == other.key and self.value < other.value)

otherwise, return:

self.key < other

Parameters:

other – The object to which to compare.

Returns:

True if this key/value pair is smaller than other.

Return type:

bool

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

all_children_are_leaves() → bool

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

Equivalent to:

all(c.is_leaf for c in self)

Returns:

True if all children are leaves.

Return type:

bool

calculate_total_size()

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

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

children() → Tuple[LeafNode, TreeNode]

The children of this node.

Equivalent to:

list(self)

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → T

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

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

Returns:

False

Return type:

bool

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints this node.

This default implementation prints the key in blue, followed by a bright white “: “, followed by the value.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

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: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

LeafNode

class graphtage.LeafNode(obj)

Bases: TreeNode

Abstract class for nodes that have no children.

__init__(obj)

Creates a node with the given object.

Parameters:

obj – The underlying Python object wrapped by the node.

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

calculate_total_size() → int

By default, leaf nodes’ sizes are equal to the length of their wrapped object’s string representation.

This is equivalent to:

return len(str(self.object))

However, subclasses may override this function to return whatever size is required.

Returns:

The length of the string representation of self.object.

Return type:

int

children() → Collection[TreeNode]

Leaf nodes have no children, so this always returns an empty tuple.

Returns:

An empty tuple.

Return type:

tuple

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → C

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

Returns whether this node is a leaf.

This implementation is equivalent to:

return len(self.children()) == 0

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints this leaf node.

By default, leaf nodes print the repr() of their wrapped object:

printer.write(repr(self.object))

Parameters:

printer – The printer to which to write this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

ListNode

class graphtage.ListNode(nodes: Iterable[T], allow_list_edits: bool = True, allow_list_edits_when_same_length: bool = True)

Bases: SequenceNode[Tuple[T, …]], Generic[T]

A node containing an ordered sequence of nodes.

__init__(nodes: Iterable[T], allow_list_edits: bool = True, allow_list_edits_when_same_length: bool = True)

Initializes a List node.

Parameters:

• nodes – The set of nodes in this list.

• allow_list_edits – Whether to consider removal and insertion when editing this list.

• allow_list_edits_when_same_length – Whether to consider removal and insertion when comparing this list to another list of the same length.

__iter__() → Iterator[TreeNode]

Iterates over this sequence’s child nodes.

This is equivalent to:

return iter(self._children)

__len__() → int

The number of children of this sequence.

This is equivalent to:

return len(self._children)

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

all_children_are_leaves() → bool

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

Equivalent to:

all(c.is_leaf for c in self)

Returns:

True if all children are leaves.

Return type:

bool

calculate_total_size()

Calculates the total size of this sequence.

This is equivalent to:

return sum(c.total_size for c in self)

children() → Sequence[TreeNode]

The children of this node.

Equivalent to:

list(self)

property container_type: Type[Tuple[T, ...]]

The container type required by graphtage.sequences.SequenceNode

Returns:

tuple

Return type:

Type[Tuple[T, …]]

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → C

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

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: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

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

Returns:

False

Return type:

bool

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

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

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

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: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

MappingNode

class graphtage.MappingNode(*args, **kwds)

Bases: ContainerNode, ABC

An abstract base class for nodes that represent mappings.

__contains__(item: TreeNode)

Tests whether the given item is a key in this mapping.

The implementation is equivalent to:

return any(k == item for k, _ in self.items())

Note

This implementation runs in worst-case linear time in the size of the mapping.

Parameters:

item – The key of the item sought.

Returns:

True if the key exists in this mapping.

Return type:

bool

__getitem__(item: TreeNode) → KeyValuePairNode

Looks up a key/value pair item from this mapping by its key.

The implementation is equivalent to:

for kvp in self:
    if kvp.key == item:
        return kvp
raise KeyError(item)

Note

This implementation runs in worst-case linear time in the size of the mapping.

Parameters:

item – The key of the key/value pair that is sought.

Returns:

The first key/value pair found with key item.

Return type:

KeyValuePairNode

Raises:

KeyError – If the key is not found.

__init__()

abstract __iter__() → Iterator[KeyValuePairNode]

Mappings should return an iterator over graphtage.KeyValuePairNode.

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

all_children_are_leaves() → bool

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

Equivalent to:

all(c.is_leaf for c in self)

Returns:

True if all children are leaves.

Return type:

bool

abstract calculate_total_size() → int

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

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

children() → Sequence[TreeNode]

The children of this node.

Equivalent to:

list(self)

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → T

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

abstract edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

abstract classmethod from_dict(source_dict: Dict[LeafNode, TreeNode]) → T

Constructs a MappingNode from a mapping of LeafNode to TreeNode.

Parameters:

source_dict – The source mapping.

Returns:

The resulting MappingNode.

Return type:

DictNode

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

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

Returns:

False

Return type:

bool

items() → Iterator[Tuple[TreeNode, TreeNode]]

Iterates over the key/value pairs in this mapping, similar to dict.items().

The implementation is equivalent to:

for kvp in self:
    yield kvp.key, kvp.value

since MappingNode.__iter__() returns an iterator over graphtage.KeyValuePairNode.

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

classmethod make_key_value_pair_node(key: LeafNode, value: TreeNode, allow_key_edits: bool = True) → KeyValuePairNode

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

abstract print(printer: Printer)

Prints this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj() → Dict[Any, Any]

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: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

Match

class graphtage.Match(match_from: TreeNode, match_to: TreeNode, cost: int)

Bases: ConstantCostEdit

A constant cost edit specifying that one node should be matched to another.

__init__(match_from: TreeNode, match_to: TreeNode, cost: int)

Constructs a new edit.

Parameters:

• from_node – The node being edited.

• to_node – The node into which from_node is being transformed.

• cost – The constant cost of the edit.

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: EditedTreeNode)

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

This default implementation adds the edit to the node:

from_node.edit = self
from_node.edit_list.append(self)

Implementations of the Edit protocol that have sub-edits (like CompoundEdit) should recursively call Edit.on_diff() on its sub-edits.

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

tighten_bounds() → bool

This always returns False

property valid: bool

Returns whether this edit is valid

MultiSetNode

class graphtage.MultiSetNode(items: Iterable[T], auto_match_keys: bool = True)

Bases: SequenceNode[HashableCounter[T]], Generic[T]

A node representing a set that can contain duplicate items.

__init__(items: Iterable[T], auto_match_keys: bool = True)

Initializes a sequence node.

Parameters:

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

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

all_children_are_leaves() → bool

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

Equivalent to:

all(c.is_leaf for c in self)

Returns:

True if all children are leaves.

Return type:

bool

calculate_total_size()

Calculates the total size of this sequence.

This is equivalent to:

return sum(c.total_size for c in self)

children() → Sequence[TreeNode]

The children of this node.

Equivalent to:

list(self)

property container_type: Type[HashableCounter[T]]

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.

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[T]) → C

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

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: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

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

Returns:

False

Return type:

bool

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

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

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

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: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

NullNode

class graphtage.NullNode

Bases: LeafNode

A node representing a null or None type.

__init__()

Creates a node with the given object.

Parameters:

obj – The underlying Python object wrapped by the node.

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

calculate_total_size() → int

By default, leaf nodes’ sizes are equal to the length of their wrapped object’s string representation.

This is equivalent to:

return len(str(self.object))

However, subclasses may override this function to return whatever size is required.

Returns:

The length of the string representation of self.object.

Return type:

int

children() → Collection[TreeNode]

Leaf nodes have no children, so this always returns an empty tuple.

Returns:

An empty tuple.

Return type:

tuple

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → T

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

Returns whether this node is a leaf.

This implementation is equivalent to:

return len(self.children()) == 0

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints this leaf node.

By default, leaf nodes print the repr() of their wrapped object:

printer.write(repr(self.object))

Parameters:

printer – The printer to which to write this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

PossibleEdits

class graphtage.PossibleEdits(from_node: TreeNode, to_node: TreeNode, edits: Iterator[Edit] = (), initial_cost: Range | None = None)

Bases: AbstractCompoundEdit

A compound edit that chooses the best option among one or more competing alternatives.

The best option is chosen by performing graphtage.search.IterativeTighteningSearch on the alternatives.

__init__(from_node: TreeNode, to_node: TreeNode, edits: Iterator[Edit] = (), initial_cost: Range | None = None)

Constructs a new Possible Edits object.

Parameters:

• from_node – The node being edited.

• to_node – The node into which from_node is being transformed.

• edits – One or more edits from which to choose.

• initial_cost – Initial bounds on the cost of the best choice, if known.

__iter__() → Iterator[Edit]

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

Returns:

The result of AbstractCompoundEdit.edits()

Return type:

Iterator[Edit]

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

best_possibility() → Edit | None

Returns the best possibility as of yet.

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

edits() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: 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
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

This implementation is equivalent to:

for edit in self.edits():
    edit.print(formatter, printer)

tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

property valid: bool

Returns whether this edit is valid

Remove

class graphtage.Remove(to_remove: TreeNode, remove_from: TreeNode, penalty: int = 1)

Bases: ConstantCostEdit

A constant cost edit specifying that a node should be removed from a container.

REMOVE_STRING: str = '~~'

__init__(to_remove: TreeNode, remove_from: TreeNode, penalty: int = 1)

Constructs a new edit.

Parameters:

• from_node – The node being edited.

• to_node – The node into which from_node is being transformed.

• cost – The constant cost of the edit.

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: EditedTreeNode)

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

This default implementation adds the edit to the node:

from_node.edit = self
from_node.edit_list.append(self)

Implementations of the Edit protocol that have sub-edits (like CompoundEdit) should recursively call Edit.on_diff() on its sub-edits.

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

tighten_bounds() → bool

This always returns False

property valid: bool

Returns whether this edit is valid

Replace

class graphtage.Replace(to_replace: TreeNode, replace_with: TreeNode)

Bases: ConstantCostEdit

A constant cost edit specifying that one node should be replaced with another.

__init__(to_replace: TreeNode, replace_with: TreeNode)

Constructs a new edit.

Parameters:

• from_node – The node being edited.

• to_node – The node into which from_node is being transformed.

• cost – The constant cost of the edit.

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: EditedTreeNode | TreeNode)

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

This default implementation adds the edit to the node:

from_node.edit = self
from_node.edit_list.append(self)

Implementations of the Edit protocol that have sub-edits (like CompoundEdit) should recursively call Edit.on_diff() on its sub-edits.

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Edits can optionally implement a printing method

This function is called automatically from the formatter in the Printing Protocol and should never be called directly unless you really know what you’re doing! Raising NotImplementedError will cause the formatter to fall back on its own printing implementations.

tighten_bounds() → bool

This always returns False

property valid: bool

Returns whether this edit is valid

StringEdit

class graphtage.StringEdit(from_node: StringNode, to_node: StringNode)

Bases: AbstractEdit

An edit returned from a StringNode

__init__(from_node: StringNode, to_node: StringNode)

Constructs a new Edit.

Parameters:

• from_node – The node that this edit transforms.

• to_node – The node that this edit transforms from_node into.

• constant_cost – A optional lower bound on the cost of this edit.

• cost_upper_bound – An optional upper bound on the cost of this edit.

__lt__(other)

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

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() → Range

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

Returns:

A range bounding the cost of this edit.

Return type:

Range

from_node: TreeNode

has_non_zero_cost() → bool

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.

initial_bounds: Range

is_complete() → bool

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().

Returns:

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:

bool

on_diff(from_node: EditedTreeNode | TreeNode)

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

This default implementation adds the edit to the node:

from_node.edit = self
from_node.edit_list.append(self)

Implementations of the Edit protocol that have sub-edits (like CompoundEdit) should recursively call Edit.on_diff() on its sub-edits.

Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

StringEdit does not implement graphtage.tree.Edit.print().

Instead, it raises NotImplementedError so that the formatting protocol will default to using a formatter like StringFormatter.

tighten_bounds() → bool

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

Returns:

True if the bounds have been tightened.

Return type:

bool

Note

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

property valid: bool

Returns whether this edit is valid

StringFormatter

class graphtage.StringFormatter(*args, **kwargs)

Bases: GraphtageFormatter

A default string formatter

DEFAULT_INSTANCE: Formatter[T] = <graphtage.StringFormatter object>

A default instance of this formatter, automatically instantiated by the FormatterChecker metaclass.

__init__()

static __new__(cls, *args, **kwargs) → Formatter[T]

Instantiates a new formatter.

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

context(printer: Printer)

escape(c: str) → str

String escape.

This function is called once for each character in the string.

Returns:

The escaped version of c, or c itself if no escaping is required.

Return type:

str

get_formatter(item: T) → Callable[[Printer, T], Any] | None

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 = False

is_quoted: bool = False

parent: Formatter[T] | None = None

The parent formatter for this formatter instance.

This is automatically populated by Formatter.__new__() and should never be manually modified.

print(printer: Printer, node_or_edit: TreeNode | Edit, with_edits: bool = True)

Prints the given node or edit.

Parameters:

• 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.

Note

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_StringEdit(printer: Printer, edit: StringEdit)

print_StringNode(printer: Printer, node: StringNode)

property root: Formatter[T]

Returns the root formatter.

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

A list of formatter types that should be used as sub-formatters in the Formatting Protocol.

sub_formatters: List[Formatter[T]] = []

The list of instantiated formatters corresponding to Formatter.sub_format_types.

This list is automatically populated by Formatter.__new__() and should never be manually modified.

write_char(printer: Printer, c: str | int, index: int, num_edits: int, removed=False, inserted=False)

Writes a character to the printer.

Note

This function calls graphtage.StringFormatter.escape(); classes extending graphtage.StringFormatter should also call graphtage.StringFormatter.escape() when reimplementing this function.

Note

There is no need to specially format characters that have been removed or inserted; the printer will have already automatically been configured to format them prior to the call to StringFormatter.write_char().

Parameters:

• printer – The printer to which to write the character.

• c – The character to write.

• index – The index of the character in the string.

• num_edits – The total number of characters that will be printed.

• removed – Whether this character was removed from the source string.

• inserted – Whether this character is inserted into the source string.

write_end_quote(printer: Printer, edit: StringEdit)

Prints an ending quote for the string, if necessary

write_start_quote(printer: Printer, edit: StringEdit)

Prints a starting quote for the string, if necessary

StringNode

class graphtage.StringNode(string_like: str | bytes, quoted=True)

Bases: LeafNode

A node containing a string

__init__(string_like: str | bytes, quoted=True)

Initializes a string node.

Parameters:

• string_like – the string contained by the node

• quoted – whether or not the string should be quoted when being formatted

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

calculate_total_size() → int

By default, leaf nodes’ sizes are equal to the length of their wrapped object’s string representation.

This is equivalent to:

return len(str(self.object))

However, subclasses may override this function to return whatever size is required.

Returns:

The length of the string representation of self.object.

Return type:

int

children() → Collection[TreeNode]

Leaf nodes have no children, so this always returns an empty tuple.

Returns:

An empty tuple.

Return type:

tuple

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → C

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

Returns whether this node is a leaf.

This implementation is equivalent to:

return len(self.children()) == 0

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

print(printer: Printer)

Prints this leaf node.

By default, leaf nodes print the repr() of their wrapped object:

printer.write(repr(self.object))

Parameters:

printer – The printer to which to write this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

TreeNode

class graphtage.TreeNode

Bases: object

Abstract base class for nodes in Graphtage’s intermediate representation.

Tree nodes are intended to be immutable. EditedTreeNode, on the other hand, can be mutable. See TreeNode.make_edited().

__init__()

add_edit_modifier(modifier: Callable[[TreeNode, TreeNode], Edit | None])

abstract calculate_total_size() → int

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

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

abstract children() → Sequence[TreeNode]

Returns a sequence of this node’s children, if any.

It is the responsibility of any node that has children must set the .parent member of each child.

copy() → T

Creates a deep copy of this node

copy_from(children: Iterable[TreeNode]) → T

Constructs a new instance of this tree node from a list of its children

dfs() → Iterator[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
    stack.extend(reversed(node.children()))

diff(node: TreeNode) → EditedTreeNode | T

Performs a diff against the provided node.

Parameters:

node – The node against which to perform the diff.

Returns:

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

Return type:

Union[EditedTreeNode, T]

editable_dict() → Dict[str, Any]

Copies self.__dict__, calling TreeNode.editable_dict() on any TreeNode objects therein.

This is equivalent to:

ret = dict(self.__dict__)
if not self.is_leaf:
    for key, value in ret.items():
        if isinstance(value, TreeNode):
            ret[key] = value.make_edited()
return ret

This is used by TreeNode.make_edited().

property edited: bool

Returns whether this node has been edited.

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

abstract edits(node: TreeNode) → Edit

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

Parameters:

node – The node to which to transform.

Returns:

The best possible edit.

Return type:

Edit

get_all_edit_contexts(node: TreeNode) → Iterator[Tuple[Tuple[TreeNode, ...], Edit]]

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

Parameters:

node – The node to which to transform this one.

Returns:

An iterator over pairs of paths from node to the edited node, as well as its edit. Note that this iterator will automatically explode any CompoundEdit in the sequence.

Return type:

Iterator[Tuple[Tuple[“TreeNode”, …], Edit]

get_all_edits(node: TreeNode) → Iterator[Edit]

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

Parameters:

node – The node to which to transform this one.

Returns:

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

Return type:

Iterator[Edit]

property is_leaf: bool

Returns whether this node is a leaf.

This implementation is equivalent to:

return len(self.children()) == 0

make_edited() → EditedTreeNode | T

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

This is equivalent to:

return self.__class__.edited_type()(self)

Returns:

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

Return type:

Union[EditedTreeNode, T]

property parent: TreeNode | None

The parent node of this node, or None if it has no parent.

The setter for this property should only be called by the parent node setting itself as the parent of its child.

ContainerNode subclasses automatically set this property for all of their children. However, if you define a subclass of TreeNode does not extend off of ContainerNode and for which len(self.children()) > 0, then each child’s parent must be set.

abstract print(printer: Printer)

Prints this node.

print_parent_context(printer: Printer, for_child: TreeNode)

Prints the context for the given child node.

For example, if this node represents a list and the child is the element at index 3, then “[3]” might be printed.

The child is expected to be one of this node’s children, but this is not validated.

The default implementation prints nothing.

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: int

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().

Returns:

An arbitrary integer representing the size of this node.

Return type:

int

TreeNodeMeta

class graphtage.TreeNodeMeta(name, bases, namespace, **kwargs)

Bases: ABCMeta

__init__(name, *args, **kwargs)

__instancecheck__(instance)

Override for isinstance(instance, cls).

__subclasscheck__(subclass)

Override for issubclass(subclass, cls).

_abc_caches_clear()

Clear the caches (for debugging or testing).

_abc_registry_clear()

Clear the registry (for debugging or testing).

_dump_registry(file=None)

Debug helper to print the ABC registry.

edited_type() → Type[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())

Returns:

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]]

mro()

Return a type’s method resolution order.

register(subclass)

Register a virtual subclass of an ABC.

Returns the subclass, to allow usage as a class decorator.

graphtage functions

explode_edits

graphtage.explode_edits(edit: Edit) → Iterator[Edit]

Performs a depth-first traversal over a potentially compound edit.

If an edit implements the CompoundEdit protocol, its sub-edits are recursively included in the output.

This implementation is equivalent to:

if isinstance(edit, CompoundEdit):
    return itertools.chain(*map(explode_edits, edit.edits()))
else:
    return iter((edit,))

Parameters:

edit – The edit that is to be exploded

Returns:

An iterator over the edits.

Return type:

Iterator[Edit]

get_filetype

graphtage.get_filetype(path: str | None = None, mime_type: str | None = None) → Filetype

Looks up the filetype for the given path.

At least one of path or mime_type must be not None. If both are provided, only mime_type will be used. If only path is provided, its mimetype will be guessed using mimetypes.guess_type().

Parameters:

• path – An optional path to a file.

• mime_type – An optional MIME type string.

Returns:

The filetype object associated with the given path and/or MIME type.

Return type:

Filetype

Raises:

• ValueError – If both path and mime_type are None.

• ValueError – If mime_type was not provided and mimetypes.guess_type() could not identify the file at path.

• ValueError – If either the provided or guessed mimetype is not supported by any registered Filetype.

string_edit_distance

graphtage.string_edit_distance(s1: str, s2: str) → EditDistance

A convenience function for computing the edit distance between two strings.

This is equivalent to:

list1 = ListNode([StringNode(c) for c in s1])
list2 = ListNode([StringNode(c) for c in s2])
return EditDistance(list1, list2, list1.children(), list2.children(), insert_remove_penalty=0)

Parameters:

• s1 – the string to compare from

• s2 – the string to compare to

Returns:

The graphtage.levenshtein.EditDistance edit object for the strings.

Return type:

EditDistance