graphtage

graphtage classes

AbstractCompoundEdit

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

Bases: graphtage.AbstractEdit, graphtage.CompoundEdit, abc.ABC

Abstract base class implementing the CompoundEdit protocol.

__init__(from_node: graphtage.TreeNode, to_node: graphtage.TreeNode = None, constant_cost: Optional[int] = 0, cost_upper_bound: Optional[int] = 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[graphtage.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.

bounds() → graphtage.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[graphtage.Edit]

Returns an iterator over this edit’s sub-edits

from_node: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

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

from_node.edit = self
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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

AbstractEdit

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

Bases: graphtage.Edit, abc.ABC

Abstract base class for the Edit protocol.

__init__(from_node: graphtage.TreeNode, to_node: graphtage.TreeNode = None, constant_cost: Optional[int] = 0, cost_upper_bound: Optional[int] = 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.

bounds() → graphtage.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: graphtage.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: graphtage.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: Union[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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

BoolNode

class graphtage.BoolNode(bool_like: bool)

Bases: graphtage.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.

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[graphtage.TreeNode]

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

Returns

An empty tuple.

Return type

tuple

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

Returns whether this node is a leaf.

This implementation is equivalent to:

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

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

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

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

BuildOptions

class graphtage.BuildOptions(*, allow_key_edits=True, allow_list_edits=True, allow_list_edits_when_same_length=True, **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, allow_list_edits=True, allow_list_edits_when_same_length=True, **kwargs)

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

Options not specified will default to False.

CompoundEdit

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

Bases: graphtage.Edit, collections.abc.Iterable, typing.Protocol

A protocol for edits that are composed of sub-edits

__init__(*args, **kwargs)

Initialize self. See help(type(self)) for accurate signature.

abstract bounds() → graphtage.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[graphtage.Edit]

Returns an iterator over this edit’s sub-edits

from_node: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

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

from_node.edit = self
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: graphtage.GraphtageFormatter, printer: graphtage.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

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

ConstantCostEdit

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

Bases: graphtage.AbstractEdit, abc.ABC

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

__init__(from_node: graphtage.TreeNode, to_node: graphtage.TreeNode = 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.

bounds() → graphtage.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: graphtage.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: graphtage.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: Union[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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

ContainerNode

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

Bases: graphtage.TreeNode, collections.abc.Iterable, collections.abc.Sized, typing.Generic, abc.ABC

A tree node that has children.

__init__()

Initialize self. See help(type(self)) for accurate signature.

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() → List[graphtage.TreeNode]

The children of this node.

Equivalent to:

list(self)

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

abstract edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

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

Returns

False

Return type

bool

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

abstract print(printer: graphtage.printer.Printer)

Prints this node.

abstract to_obj()

Returns a pure Python representation of this node.

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

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

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

DictNode

class graphtage.DictNode(items: Iterable[T])

Bases: graphtage.MappingNode, graphtage.MultiSetNode

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: graphtage.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: graphtage.TreeNode) → graphtage.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])

Initializes a sequence node.

Parameters

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

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() → T

The children of this node.

Equivalent to:

list(self)

property container_type

Returns the container type used to store SequenceNode._children.

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

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

editable_dict() → Dict[str, Any]

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

This is equivalent to:

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

This is used by SequenceNode.make_edited().

property edited

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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

static from_dict(source_dict: Dict[graphtage.LeafNode, graphtage.TreeNode]) → graphtage.DictNode

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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

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

Returns

False

Return type

bool

items() → Iterator[Tuple[graphtage.TreeNode, graphtage.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() → Union[graphtage.EditedTreeNode, T]

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

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

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

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: graphtage.bounds.Bounded, typing.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)

Initialize self. See help(type(self)) for accurate signature.

abstract bounds() → graphtage.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: graphtage.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: graphtage.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: Union[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: graphtage.GraphtageFormatter, printer: graphtage.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

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

EditCollection

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

Bases: graphtage.AbstractCompoundEdit, typing.Generic

An edit comprised of one or more sub-edits.

__init__(from_node: graphtage.TreeNode, to_node: Optional[graphtage.TreeNode], collection: Type[C], add_to_collection: Callable[[C, graphtage.Edit], Any], edits: Iterator[graphtage.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[graphtage.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.

bounds() → graphtage.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[graphtage.Edit]

Returns an iterator over this edit’s sub-edits

from_node: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

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

from_node.edit = self
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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

EditSequence

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

Bases: graphtage.EditCollection

An EditCollection using a list as the underlying container.

__init__(from_node: graphtage.TreeNode, to_node: Optional[graphtage.TreeNode], edits: Iterator[graphtage.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[graphtage.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.

bounds() → graphtage.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[graphtage.Edit]

Returns an iterator over this edit’s sub-edits

from_node: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

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

from_node.edit = self
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: graphtage.GraphtageFormatter, printer: graphtage.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

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

Initialize self. See help(type(self)) for accurate signature.

property edited

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: Optional[graphtage.BuildOptions] = None) → graphtage.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: Optional[graphtage.BuildOptions] = None) → Union[str, graphtage.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]

abstract get_default_formatter() → graphtage.GraphtageFormatter

Returns the default formatter for printing files of this type.

FiletypeWatcher

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

Bases: abc.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)

Initialize self. See help(type(self)) for accurate signature.

__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: graphtage.MappingNode, graphtage.sequences.SequenceNode

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)

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() → T

The children of this node.

Equivalent to:

list(self)

property container_type

The container type required by graphtage.sequences.SequenceNode

Returns

dict

Return type

Type[Dict[LeafNode, KeyValuePairNode]]

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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

static from_dict(source_dict: Dict[graphtage.LeafNode, graphtage.TreeNode]) → graphtage.FixedKeyDictNode

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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

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

Returns

False

Return type

bool

items() → Iterator[Tuple[graphtage.LeafNode, graphtage.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() → Union[graphtage.EditedTreeNode, T]

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

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

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

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: graphtage.FixedKeyDictNode, to_node: graphtage.TreeNode, edits: Iterator[graphtage.Edit])

Bases: graphtage.sequences.SequenceEdit, graphtage.EditCollection

The edit type returned by FixedKeyDictNode.

__init__(from_node: graphtage.FixedKeyDictNode, to_node: graphtage.TreeNode, edits: Iterator[graphtage.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[graphtage.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.

bounds() → graphtage.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[graphtage.Edit]

Returns an iterator over this edit’s sub-edits

from_node: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

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

from_node.edit = self
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: graphtage.GraphtageFormatter, printer: graphtage.printer.Printer)

Prints this edit.

This is equivalent to:

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

property sequence

Returns the sequence being edited.

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

typing.cast(SequenceNode, self.from_node)

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

Returns whether this edit is valid

FloatNode

class graphtage.FloatNode(float_like: float)

Bases: graphtage.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.

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[graphtage.TreeNode]

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

Returns

An empty tuple.

Return type

tuple

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

Returns whether this node is a leaf.

This implementation is equivalent to:

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

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

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

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

GraphtageFormatter

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

Bases: graphtage.formatter.Formatter

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

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

__init__()

Initialize self. See help(type(self)) for accurate signature.

static __new__(cls, *args, **kwargs) → graphtage.formatter.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) → Optional[Callable[[graphtage.printer.Printer, T], Any]]

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

Equivalent to:

get_formatter(item.__class__, base_formatter=self)

is_partial: bool = False

parent: Optional[graphtage.formatter.Formatter[T]] = None

print(printer: graphtage.printer.Printer, node_or_edit: Union[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

Returns the root formatter.

sub_format_types: Sequence[Type[graphtage.formatter.Formatter[T]]] = ()

sub_formatters: List[graphtage.formatter.Formatter[T]] = []

Insert

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

Bases: graphtage.ConstantCostEdit

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

INSERT_STRING: str = '++'

__init__(to_insert: graphtage.TreeNode, insert_into: graphtage.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.

bounds() → graphtage.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: graphtage.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: graphtage.bounds.Range

property insert_into

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: graphtage.EditedTreeNode)

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

This default implementation adds the edit to the node:

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: graphtage.GraphtageFormatter, printer: graphtage.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

property valid

Returns whether this edit is valid

IntegerNode

class graphtage.IntegerNode(int_like: int)

Bases: graphtage.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.

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[graphtage.TreeNode]

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

Returns

An empty tuple.

Return type

tuple

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

Returns whether this node is a leaf.

This implementation is equivalent to:

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

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

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

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

KeyValuePairEdit

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

Bases: graphtage.AbstractCompoundEdit

An edit type for two key/value pairs

__init__(from_kvp: graphtage.KeyValuePairNode, to_kvp: graphtage.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[graphtage.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.

bounds() → graphtage.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[graphtage.Edit]

Returns an iterator over this edit’s sub-edits

from_node: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

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

from_node.edit = self
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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

KeyValuePairNode

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

Bases: graphtage.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: graphtage.LeafNode, value: graphtage.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

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[graphtage.LeafNode, graphtage.TreeNode]

The children of this node.

Equivalent to:

list(self)

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

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

Returns

False

Return type

bool

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

Prints this node.

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

to_obj()

Returns a pure Python representation of this node.

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

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

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

LeafNode

class graphtage.LeafNode(obj)

Bases: graphtage.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.

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[graphtage.TreeNode]

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

Returns

An empty tuple.

Return type

tuple

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

Returns whether this node is a leaf.

This implementation is equivalent to:

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

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

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

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size

The size of this node.

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

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

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: graphtage.sequences.SequenceNode, typing.Generic

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[graphtage.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)

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() → T

The children of this node.

Equivalent to:

list(self)

property container_type

The container type required by graphtage.sequences.SequenceNode

Returns

tuple

Return type

Type[Tuple[T, ..]]

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

editable_dict() → Dict[str, Any]

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

This is equivalent to:

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

This is used by SequenceNode.make_edited().

property edited

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

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

Returns

False

Return type

bool

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

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

to_obj()

Returns a pure Python representation of this node.

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

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

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

MappingNode

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

Bases: graphtage.ContainerNode, abc.ABC

An abstract base class for nodes that represent mappings.

__contains__(item: graphtage.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: graphtage.TreeNode) → graphtage.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__()

Initialize self. See help(type(self)) for accurate signature.

abstract __iter__() → Iterator[graphtage.KeyValuePairNode]

Mappings should return an iterator over graphtage.KeyValuePairNode.

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() → List[graphtage.TreeNode]

The children of this node.

Equivalent to:

list(self)

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

abstract edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

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

Returns

False

Return type

bool

items() → Iterator[Tuple[graphtage.TreeNode, graphtage.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() → Union[graphtage.EditedTreeNode, T]

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

abstract print(printer: graphtage.printer.Printer)

Prints this node.

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

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: graphtage.TreeNode, match_to: graphtage.TreeNode, cost: int)

Bases: graphtage.ConstantCostEdit

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

__init__(match_from: graphtage.TreeNode, match_to: graphtage.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.

bounds() → graphtage.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: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

This default implementation adds the edit to the node:

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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

MultiSetNode

class graphtage.MultiSetNode(items: Iterable[T])

Bases: graphtage.sequences.SequenceNode, typing.Generic

A node representing a set that can contain duplicate items.

__init__(items: Iterable[T])

Initializes a sequence node.

Parameters

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

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() → T

The children of this node.

Equivalent to:

list(self)

property container_type

Returns the container type used to store SequenceNode._children.

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

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

editable_dict() → Dict[str, Any]

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

This is equivalent to:

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

This is used by SequenceNode.make_edited().

property edited

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

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

Returns

False

Return type

bool

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

Prints a sequence node.

By default, sequence nodes are printed like lists:

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

to_obj()

Returns a pure Python representation of this node.

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

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

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

NullNode

class graphtage.NullNode

Bases: graphtage.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.

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[graphtage.TreeNode]

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

Returns

An empty tuple.

Return type

tuple

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

Returns whether this node is a leaf.

This implementation is equivalent to:

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

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

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

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

PossibleEdits

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

Bases: graphtage.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: graphtage.TreeNode, to_node: graphtage.TreeNode, edits: Iterator[graphtage.Edit] = (), initial_cost: Optional[graphtage.bounds.Range] = 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[graphtage.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.

best_possibility() → Optional[graphtage.Edit]

Returns the best possibility as of yet.

bounds() → graphtage.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[graphtage.Edit]

Returns an iterator over this edit’s sub-edits

from_node: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

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

from_node.edit = self
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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

Remove

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

Bases: graphtage.ConstantCostEdit

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

REMOVE_STRING: str = '~~'

__init__(to_remove: graphtage.TreeNode, remove_from: graphtage.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.

bounds() → graphtage.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: graphtage.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: graphtage.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: graphtage.EditedTreeNode)

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

This default implementation adds the edit to the node:

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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

Replace

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

Bases: graphtage.ConstantCostEdit

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

__init__(to_replace: graphtage.TreeNode, replace_with: graphtage.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.

bounds() → graphtage.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: graphtage.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: graphtage.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: Union[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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

StringEdit

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

Bases: graphtage.AbstractEdit

An edit returned from a StringNode

__init__(from_node: graphtage.StringNode, to_node: graphtage.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.

bounds() → graphtage.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: graphtage.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: graphtage.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: Union[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: graphtage.GraphtageFormatter, printer: graphtage.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

Returns whether this edit is valid

StringFormatter

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

Bases: graphtage.GraphtageFormatter

A default string formatter

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

__init__()

Initialize self. See help(type(self)) for accurate signature.

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

Instantiates a new formatter.

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

context(printer: graphtage.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) → Optional[Callable[[graphtage.printer.Printer, T], Any]]

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

Equivalent to:

get_formatter(item.__class__, base_formatter=self)

is_partial: bool = False

is_quoted: bool = False

parent: Optional[graphtage.formatter.Formatter[T]] = None

print(printer: graphtage.printer.Printer, node_or_edit: Union[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: graphtage.printer.Printer, edit: graphtage.StringEdit)

print_StringNode(printer: graphtage.printer.Printer, node: graphtage.StringNode)

property root

Returns the root formatter.

sub_format_types: Sequence[Type[graphtage.formatter.Formatter[T]]] = ()

sub_formatters: List[graphtage.formatter.Formatter[T]] = []

write_char(printer: graphtage.printer.Printer, c: str, 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: graphtage.printer.Printer, edit: graphtage.StringEdit)

Prints an ending quote for the string, if necessary

write_start_quote(printer: graphtage.printer.Printer, edit: graphtage.StringEdit)

Prints a starting quote for the string, if necessary

StringNode

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

Bases: graphtage.LeafNode

A node containing a string

__init__(string_like: str, 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

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[graphtage.TreeNode]

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

Returns

An empty tuple.

Return type

tuple

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

Returns whether this node is a leaf.

This implementation is equivalent to:

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

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

print(printer: graphtage.printer.Printer)

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

to_obj()

Returns the object wrapped by this node.

This is equivalent to:

return self.object

property total_size

The size of this node.

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

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

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

Initialize self. See help(type(self)) for accurate signature.

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() → Collection[graphtage.TreeNode]

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

dfs() → Iterator[graphtage.TreeNode]

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

self is always included and yielded first.

This implementation is equivalent to:

stack = [self]
while stack:
    node = stack.pop()
    yield node
    stack.extend(reversed(node.children()))

diff(node: graphtage.TreeNode) → Union[graphtage.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]

edit_modifiers: Optional[List[Callable[[graphtage.TreeNode, graphtage.TreeNode], Optional[graphtage.Edit]]]] = None

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

Returns whether this node has been edited.

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

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

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

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

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

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

abstract edits(node: graphtage.TreeNode) → graphtage.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_edits(node: graphtage.TreeNode) → Iterator[graphtage.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

Returns whether this node is a leaf.

This implementation is equivalent to:

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

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

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

This is equivalent to:

return self.edited_type()(self)

Returns

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

Return type

Union[EditedTreeNode, T]

abstract print(printer: graphtage.printer.Printer)

Prints this node.

abstract to_obj()

Returns a pure Python representation of this node.

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

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

property total_size

The size of this node.

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

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

Returns

An arbitrary integer representing the size of this node.

Return type

int

graphtage functions

explode_edits

graphtage.explode_edits(edit: graphtage.Edit) → Iterator[graphtage.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: Optional[str] = None, mime_type: Optional[str] = None) → graphtage.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) → graphtage.levenshtein.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