wiz.graph

class wiz.graph.Resolver(definition_mapping, maximum_combinations=None, maximum_attempts=None)[source]

Package dependency resolver.

Compute a ordered list of packages from an initial list of packaging.requirements.Requirement instances:

>>> resolver = Resolver()
>>> resolver.compute_packages([Requirement("foo"), Requirement("bar")])

An initial Graph instance is created from initial requirements with all corresponding dependencies.

If the graph contains conflicting variants, several Combination instances will be created with a copy of the graph containing onlly one variant for each definition included. Only one Combination instance is created otherwise.

The resolution process ensures that only one version and one variant of each package definition is kept. A graph cannot be resolved if several requirements are incompatibles (e.g. “A >= 1” and “A < 1”).

Each Combination instance will be generated only if the previous one failed to return a solution. If all graph combinations are exhausted and no solutions are found, other versions of the conflicting packages will be fetched to attempt to resolve the graph.

__init__(definition_mapping, maximum_combinations=None, maximum_attempts=None)[source]

Initialize Resolver.

Parameters:
  • definition_mapping – Mapping regrouping all available definitions associated with their unique identifier.
  • maximum_combinations – Maximum number of combinations which can be generated from conflicting variants. Default is None, which means that the default value will be picked from the configuration.
  • maximum_attempts – Maximum number of resolution attempts before raising an error. Default is None, which means that the default value will be picked from the configuration.
definition_mapping

Return definition mapping used by resolver.

Returns:Mapping containing of all available definitions
conflicting_variants

Return set of node identifiers with variant used to divide graph.

Returns:Set of node identifiers.
compute_packages(requirements, namespace_counter=None)[source]

Return resolved packages from requirements.

Parameters:
Raise:

wiz.exception.GraphResolutionError if the graph cannot be resolved in time.
initiate_combinations(graph)[source]

Initiate combinations iterator from graph.

Parameters:graph – Instance of Graph.
extract_combinations(graph)[source]

Extract new combinations from conflicting variants in graph.

Parameters:graph – Instance of Graph.
Returns:Boolean value indicating whether Combination instances have been extracted.
fetch_next_combination()[source]

Return next combination from the iterator.

Returns:Instance of Combination or None if iterator is empty.
discover_combinations()[source]

Discover new combinations from unsolvable conflicts recorded.

After exhausting all graph combinations, the unsolvable conflicts previously recorded are being used to create new combinations with different package versions.

Returns:Boolean value indicating whether Combination instances have been extracted.
wiz.graph._compute_distance_mapping(graph)[source]

Return distance mapping for each node of graph.

The mapping indicates the shortest possible distance of each node identifier from the root level of the graph with corresponding parent node identifier.

The distance is defined by the sum of the weights from each node to the root level of the graph.

This is using Dijkstra’s shortest path algorithm.

Parameters:graph – Instance of Graph.
Returns:Distance mapping.

Note

When a node is being visited twice, the path with the shortest distance is being kept.

wiz.graph._generate_variant_permutations(graph, variant_groups)[source]

Yield valid permutations of the variant groups.

Group containing nodes nearest to the root level of the graph are yield first and variant permutations containing conflicting requirements are discarded.

Parameters:
  • graph – Instance of Graph.
  • variant_groups –

    Set of tuple containing tuples of node identifiers with conflicting variants. It should be in the form of:

    {
    (("foo[V2]==0.1.0",), ("foo[V1]==0.1.0"),),
    (("bar[V2]==2.2.0",), ("bar[V1]==2.2.0", "bar[V1]==2.0.0"))
}
Returns:

Generator of permutations between variant groups.
Raise:

ValueError if one node identifier defined in variant groups does not exist in the graph.
wiz.graph._sorted_variant_groups(variant_groups, distance_mapping)[source]

Return sorted variant groups using the distance mapping.

The incoming set is sorted to prioritize definition groups whose nodes are nearest to the root level of the graph. Each definition group is also sorted to prioritize variant groups whose nodes are nearest to the root level of the graph.

Parameters:
  • variant_groups –

    Set of tuple containing tuples of node identifiers with conflicting variants. It should be in the form of:

    {
    (("foo[V2]==0.1.0",), ("foo[V1]==0.1.0"),),
    (("bar[V2]==2.2.0",), ("bar[V1]==2.2.0", "bar[V1]==2.0.0"))
}
  • distance_mapping – Mapping indicating the shortest possible distance of each node identifier from the root level of the graph with its corresponding parent node identifier.
Returns:

Tuple containing sorted variant groups.
wiz.graph._extract_optimized_variant_groups(variant_groups, conflicting)[source]

Extract list of optimized variant groups skipping conflicting nodes.

Parameters:
  • variant_groups –

    Sorted variant groups tuple. It should be in the form of:

    (
    (("foo[V2]==0.1.0",), ("foo[V1]==0.1.0"),),
    (("bar[V2]==2.2.0",), ("bar[V1]==2.2.0", "bar[V1]==2.0.0"))
)
  • conflicting – Mapping recording conflicting status between each definition node.
Returns:

List of optimized variant groups.
wiz.graph._filtered_variant_groups(variant_groups, callback)[source]

Return filtered variant group using callback.

Example:

>>> groups = (
...     (("A[V1]=1", "A[V1]=2"), ("A[V2]",)),
...     (("B[V2]",), ("B[V1]",))
... )
>>> _filtered_variant_groups(
...     groups, callback=lambda _, _id: _id not in ("A[V1]=2", "B[V1]")
... )
((("A[V1]=1",), ("A[V2]",)), (("B[V2]",),))
Parameters:
  • variant_groups –

    Sorted variant groups tuple. It should be in the form of:

    (
    (("foo[V2]==0.1.0",), ("foo[V1]==0.1.0"),),
    (("bar[V2]==2.2.0",), ("bar[V1]==2.2.0", "bar[V1]==2.0.0"))
)
  • callback –

    Function returning whether a specific node identifier should be kept in the variant groups. It should be in the form of:

    def filter_callback(group_index, identifier):
    """Return whether node *identifier* should be kept."""
    return group_index == _index and identifier not in _group
Returns:

Filtered variant groups.
wiz.graph._compute_conflicting_matrix(graph, variant_groups)[source]

Compute conflicting matrix for all nodes in variant groups.

Example:

>>> groups = {
...     (("A[V3]",), ("A[V2]",), ("A[V1]",)),
...     (("B[V2]==2", "B[V2]==1"), ("B[V1]==1",))
... }
>>> _compute_conflicting_matrix(graph, groups)
{
    "A[V3]": {"B[V2]==2": True, "B[V2]==1": False, "B[V1]==1": True},
    "A[V2]": {"B[V2]==2": True, "B[V2]==1": False, "B[V1]==1": True},
    "A[V1]": {"B[V2]==2": False, "B[V2]==1": False, "B[V1]==1": True},
    "B[V2]==2": {"A[V3]": True, "A[V2]": True, "A[V1]": False},
    "B[V2]==1": {"A[V3]": False, "A[V2]": False, "A[V1]": False},
    "B[V1]==1": {"A[V3]": True, "A[V2]": True, "A[V1]": True},
}
Parameters:
  • graph – Instance of Graph.
  • variant_groups –

    Set of tuple containing tuples of node identifiers with conflicting variants. It should be in the form of:

    {
    (("foo[V2]==0.1.0",), ("foo[V1]==0.1.0"),),
    (("bar[V2]==2.2.0",), ("bar[V1]==2.2.0", "bar[V1]==2.0.0"))
}
Returns:

Matrix recording conflicting status between each definition node.
wiz.graph._combined_requirements(graph, nodes)[source]

Return combined requirements from nodes in graph.

Parameters:
  • graph – Instance of Graph.
  • nodes – List of Node instances.
Raise:

wiz.exception.GraphResolutionError if requirements cannot be combined.
wiz.graph._extract_conflicting_requirements(graph, nodes)[source]

Return mapping of conflicting node identifiers per requirement.

A requirement is conflicting when it is not overlapping with at least one other requirement from existing parents of nodes.

Parameters:
  • graph – Instance of Graph.
  • nodes – List of Node instances which belong to the same definition identifier.
Returns:

Mapping in the form of

{
    Requirement("foo >=0.1.0, <1"): {"bar", "bim"},
    Requirement("foo >2"): {"baz},
    ...
}

Raise:

ValueError if nodes do not belong to the same definition.
class wiz.graph.Graph(resolver, namespace_counter=None)[source]

Package dependency Graph.

Requested packages are added recursively as Node instances from requirements or instances:

>>> graph = Graph(resolver)
>>> graph.update_from_requirements([Requirement("A >=1, <2")])

Dependent requirements are traversed using a Breadth-first approach so that potential errors are recorded in coherent order.

When a packages cannot be extracted from a requirement, errors are recorded and can be retrieved as follows:

>>> graph.errors()
{"root": "The requirement 'incorrect' could not be resolved."}

Conflicting versions and variant groups are recorded and can be retrieved as follows:

>>> graph.conflicting()
{"B==1.2.0", "B==2.0.0"}

>>> graph.conflicting_variant_groups()
[["C[V2]", "C[V1]"], ["D[V2]==1.2.3", "D[V1]==1.2.3"]]

Conditions will be recorded as StoredNode instances. Corresponding packages will be added to the graph only if at least one package with the same definition identifier has previously been added to the graph.

See also

Conditions

ROOT = 'root'

Identify the root of the graph.

__init__(resolver, namespace_counter=None)[source]

Initialize Graph.

Parameters:
  • resolver – Instance of Resolver.
  • namespace_counter – instance of collections.Counter which indicates occurrence of namespaces used as hints for package identification. Default is None.
resolver

Return resolver instance used to create Graph.

Returns:Instance of Resolver.
node(identifier, raising=False)[source]

Return node from identifier.

Parameters:
  • identifier – Unique identifier of the targeted node.
  • raising – Indicate whether an exception should be raised if the node cannot be fetched in the graph. Default is False.
Returns:

Instance of Node or None if targeted node does not exist in the graph.
Raise:

ValueError if raising is True and identifier can not be found in the graph.
nodes(definition_identifier=None)[source]

Return all nodes in the graph.

Parameters:definition_identifier – Provide qualified identifier of a definition whose nodes must belong to. Default is None which means that nodes belonging to any definitions will be returned.
Returns:List of Node instances.
exists(identifier)[source]

Indicate whether the node identifier is in the graph.

Parameters:identifier – Unique identifier of the targeted node.
Returns:Boolean value.
find(requirement)[source]

Return matching node identifiers in graph for requirement.

Parameters:requirement – Instance of packaging.requirements.Requirement.
Returns:Set of matching node identifiers.
conditioned_nodes()[source]

Return all conditioned nodes in the graph.

A conditioned node is a node which requires one or several requirements to be fulfilled before it can be added to the graph.

Returns:List of StoredNode instances.

See also

Conditions

conflicting()[source]

Return conflicting nodes identifiers.

A conflict appears when several nodes are found for a single definition identifier.

Returns:Set of node identifiers.
conflicting_variant_groups()[source]

Return conflicting variant groups in graphs.

Conflicting variants occurs when there are at least two packages belonging to different variants of one definition in the graph.

Each group is a tuple composed of tuples to organize node identifiers per variant identifier in the order of creation. The tuples regrouping nodes per variant identifier are sorted by version in descending order.

Returns:Set of tuple containing tuples of node identifiers.
{
    (("foo[V2]==0.1.0",), ("foo[V1]==0.1.0"),),
    (("bar[V2]==2.2.0",), ("bar[V1]==2.2.0", "bar[V1]==2.0.0"))
}
errors()[source]

Return all encapsulated errors per existing node identifier.

Returns:Mapping if the form of
{
    "foo": "The requirement 'bar' could not be resolved.",
    ...
}
outcoming(identifier)[source]

Return outcoming node identifiers for node identifier.

Parameters:identifier – Unique identifier of the targeted node.
Returns:List of dependent node identifiers.

Return weight from link between parent and node identifier.

Parameters:
  • identifier – Unique identifier of the targeted node.
  • parent_identifier – Unique identifier of parent node.
Returns:

Integer value.
Raise:

ValueError if no link is recorded between parent_identifier and identifier.

Return requirement from link between parent and node identifier.

Parameters:
  • identifier – Unique identifier of the targeted node.
  • parent_identifier – Unique identifier of parent node.
Returns:

Instance of packaging.requirements.Requirement.
Raise:

ValueError if no link is recorded between parent_identifier and identifier.
update_from_requirements(requirements, detached=False)[source]

Update graph from requirements.

One or several Package instances will be extracted from requirements and Node instances will be added to graph accordingly. The process will be repeated recursively for dependent requirements from newly created packages.

Parameters:
  • requirements – List of packaging.requirements.Requirement instances ordered from the most important to the least important.
  • detached – Indicate whether Node instances created for requirements must be detached from the root level of the graph. Default is False.
update_from_package(package, requirement, detached=False)[source]

Update graph from package.

package instance and requirement are used to create corresponding Node instances. The process will be repeated recursively for dependent requirements from newly created packages.

Parameters:
_process_queue(queue)[source]

Update graph and fetch stored nodes from data contained in queue.

Parameters:queue – Instance of Queue.
_required_stored_nodes()[source]

Return StoredNode instances which should be added to graph.

A StoredNode instance has been created for each package which has one or several conditions.

Returns:List of StoredNode instances.
_process_requirement(requirement, parent_identifier, queue, weight=1)[source]

Update graph from requirement.

Parameters:
  • requirement – Instance of packaging.requirements.Requirement.
  • parent_identifier – Unique identifier of the parent node.
  • queue – Instance of Queue that will be updated with all dependent requirements data.
  • weight – Number indicating the importance of the dependency link from the node to its parent. The lesser this number, the higher is the importance of the link. Default is 1.
_process_package(package, requirement, parent_identifier, queue, weight=1)[source]

Update graph from package.

Parameters:
  • package – Instance of wiz.package.Package.
  • requirement – Instance of packaging.requirements.Requirement.
  • parent_identifier – Unique identifier of the parent node.
  • queue – Instance of Queue that will be updated with all dependent requirements data.
  • weight – Number indicating the importance of the dependency link from the node to its parent. The lesser this number, the higher is the importance of the link. Default is 1.
_create_node(package)[source]

Create node in graph from package.

Parameters:package – Instance of wiz.package.Package.
remove_node(identifier)[source]

Remove node from the graph.

Parameters:identifier – Unique identifier of the targeted node.
Raise:ValueError if identifier does not correspond to any existing node in the graph.

Warning

A lazy deletion is performed as the links are not deleted to save on performance.

Relink node’s parents after removing it from the graph.

Example:

>>> node = self.node("foo")
>>> self.remove_node(node.identifier)
>>> self.relink_parents(node)

When creating the new links, the same weight connecting the node removed to its parents is being used. requirement will be used for each new link if given, otherwise the same requirement connecting the node removed to its parents is being used.

If a parent node can not be linked to any other node in the graph, an error will be recorded.

Parameters:
Raise:

ValueError if node_removed still exists in the graph.

Add dependency link from parent_identifier to identifier.

Parameters:
  • identifier – Unique identifier of the package which is added to the dependency graph.
  • parent_identifier – Unique identifier of the targeted package which must be linked to the new identifier.
  • requirement – Instance of packaging.requirements.Requirement.
  • weight – Number indicating the importance of the dependency link from the node to its parent. The lesser this number, the higher is the importance of the link. Default is 1.

Note

If a link already exists between identifier and parent_identifier, the same weight will be preserved.

downgrade_versions(identifiers)[source]

Replace all node identifiers in graph with lower versions.

Combined requirements from parents to each node identifier is computed and altered to skip current package version. These new requirements are used to extract lower package versions.

If the identifier does not correspond to any node in the graph or if the embedded package is not versioned, the identifier is skipped.

If no packages can be extracted from new requirements, the identifier is also skipped.

Parameters:identifiers – Set of node identifiers.
Returns:Boolean value indicating whether at least one node have been replaced with different versions.
data()[source]

Return reference mapping.

Returns:Mapping or string containing all information about the graph.
class wiz.graph.Node(package, parent_identifiers=None)[source]

Representation of a package within the Graph.

It encapsulates one Package instance with all parent package identifiers.

__init__(package, parent_identifiers=None)[source]

Initialize Node.

Parameters:
  • package – Instance of wiz.package.Package.
  • parent_identifiers – Set of parent identifiers. Default is None.
package

Return embedded package instance.

Returns:Instance of wiz.package.Package.
identifier

Return identifier of the embedded package instance.

Returns:String value (e.g. “foo==0.1.0”).
definition

Return definition of embedded package instance.

Returns:Instance of wiz.definition.Definition.
parent_identifiers

Return set of node identifiers.

Returns:Set of string values.
add_parent(identifier)[source]

Add identifier as parent to the node.

Parameters:identifier – Unique node identifier.
data()[source]

Return reference mapping.

Returns:Mapping containing all information about the node.
class wiz.graph.StoredNode(requirement, package, parent_identifier, weight=1)[source]

Representation of a package which cannot be added to the Graph.

It encapsulates a Package instance with its corresponding Requirement instance, alongside with parent package identifier and weight number assigned.

A StoredNode instance is used when a package request cannot be immediately added to the graph.

Examples:

  • When a package contains conditions, a StoredNode instance is created for this package until the condition can be fulfilled. If the conditions are not fulfilled, the package will not be added to the graph.
__init__(requirement, package, parent_identifier, weight=1)[source]

Initialize StoredNode.

Parameters:
  • requirement – Instance of packaging.requirements.Requirement.
  • package – Instance of wiz.package.Package.
  • parent_identifier – Unique identifier if the parent node.
  • weight – Number indicating the importance of the dependency link from the node to its parent. Default is 1.
identifier

Return identifier of the embedded package instance.

Returns:String value (e.g. “foo==0.1.0”).
requirement

Return requirement used to extract embedded package instance.

Returns:Instance of packaging.requirements.Requirement.
package

Return embedded package instance.

Returns:Instance of wiz.package.Package.
parent_identifier

Return unique parent node identifier.

Returns:String value (e.g. “foo==0.1.0”).
weight

Return weight number.

Returns:Integer value.
data()[source]

Return reference mapping.

Returns:Mapping containing all information about the stored node.
class wiz.graph.Combination(graph, nodes_to_remove=None, copy_data=True)[source]

Combination of a Package dependency Graph.

This object operates an initial pruning process on a Graph instance to ensure that only one variant of each conflicting variant group is preserved:

>>> group = ["A[V3]", "A[V2]", "A[V1]"]
>>> combination = Combination(graph, nodes_to_remove=group[1:])

Note

If graph does not have any conflicting variant groups, it might not be necessary to remove any nodes.

Extracting resolved packages from a variant combination can be done in three steps:

  • Conflicting versions must be resolved:

    >>> combination.resolve_conflicts()

  • Remaining nodes must be validated:

    >>> combination.validate()

  • If previous stages did not raise any error, resolved packages can be extracted:

    >>> combination.extract_packages()

See also

Variants

__init__(graph, nodes_to_remove=None, copy_data=True)[source]

Initialize Combination.

Parameters:
  • graph – Instance of Graph.
  • nodes_to_remove – Set of node identifier from a group of conflicting variants which will be removed from the graph. Default is None which means that no node will be removed from the graph.
  • copy_data – Indicate whether input graph will be copied to prevent mutating it. Default is True.
graph

Return embedded graph instance.

Returns:Instance of Graph.
_remove_nodes(identifiers)[source]

Remove nodes corresponding to identifiers.

Remaining unreachable nodes will be pruned.

Parameters:identifiers – List of node identifiers.
resolve_conflicts()[source]

Attempt to resolve all conflicting versions in embedded graph.

Conflicting nodes are treated per descending order of distance to the root level of the graph, so that nodes higher in the tree have a higher priority over deeper ones.

Circular conflicts - conflicting node with conflicting parents - will be treated last to ensure that higher chance of resolution.

An exception is raised if the graph can not be resolved.

Raise:wiz.exception.GraphConflictsError if several node requirements are incompatible.
Raise:wiz.exception.GraphVariantsError if new package versions added to the graph during the resolution process lead to a division of the graph.
_update_conflict_queue(iterables, circular_conflicts=None)[source]

Create new queue with conflicting node identifier lists.

Duplicated identifiers are removed and all conflicting node identifiers are sorted per descending order of distance to the root level of the graph. If two nodes have the same distance to the root level of the graph, the node identifier is used.

Node identifier included in the circular_conflicts set will be sorted at the very end of the queue to be treated last.

Parameters:
  • iterables – Lists of conflicting node identifier.
  • circular_conflicts – Set of conflicted node identifier which have conflicting parents.
Returns:

Instance of collections.deque.
_discover_packages(requirement, nodes, identifier, remaining_conflicts, circular_conflicts)[source]

Return packages compatible with combined requirement.

If no packages can be extracted, parent of conflicting nodes are fetched to find out whether they are part of the remaining conflicts. If this is the case, and if node identifier hasn’t already been marked as a circular conflict, None is returned. Otherwise, an error is raised.

Parameters:
  • requirement – Instance of packaging.requirements.Requirement.
  • nodes – List of Node instances.
  • identifier – Unique identifier of conflicting node currently analyzed.
  • remaining_conflicts – Instance of collections.deque containing unique identifiers of conflicting nodes.
  • circular_conflicts – Set of conflicted node identifier which have conflicting parents.
Raise:

wiz.exception.GraphConflictsError if no packages have been extracted.
Returns:

List of Package instances.
_add_packages_to_graph(packages, requirement, conflicting_nodes)[source]

Add packages to embedded graph as detached nodes if necessary.

Packages which are already recorded as conflict or packages with variant which already led to a graph division are skipped.

Parameters:
  • packages – List of Package instances that has been extracted from requirement. The list contains more than one package only if variants are detected.
  • requirement – Instance of packaging.requirements.Requirement which led to the package extraction. It is a combined requirement from all requirements which extracted packages embedded in conflicting_nodes.
  • conflicting_nodes – List of Node instances representing conflicting versions.
Returns:

Boolean value indicating whether the graph has been updated with at least one package.
validate()[source]

Ensure that graph does not have remaining errors.

If some conflicting errors are found, they would be regrouped and raised into one GraphConflictsError exception. Other type of errors will be regrouped and raised into one GraphInvalidNodesError exception.

Raise:wiz.exception.GraphInvalidNodesError if any error is found in the embedded graph.
Raise:wiz.exception.GraphConflictsError if any requirement conflict is found in the embedded graph.
extract_packages()[source]

Return sorted list of packages from embedded graph.

Packages are sorted per descending order of distance to the root level of the graph. If two nodes have the same distance to the root level of the graph, the node identifier is used.

Returns:Sorted list of wiz.package.Package instances.
prune_graph()[source]

Remove unreachable and invalid nodes from graph.

First, all unreachable nodes will be removed from the graph. If the graph does not contain any unreachable nodes, the pruning process is stopped.

Then, all conditioned nodes added to the graph are being checked and removed if conditions are no longer fulfilled. If no conditional nodes are removed, the pruning process is stopped.

These two steps are repeated until no unreachable nodes or no conditioned nodes can be removed.

_trim_unreachable_nodes()[source]

Remove all unreachable nodes from the graph.

Returns:Boolean value indicating whether one or several nodes have been removed.
_trim_unfulfilled_conditions()[source]

Remove all nodes from the graph with unfulfilled conditions.

Returns:Boolean value indicating whether one or several nodes have been removed.
_fetch_distance_mapping(force_update=False)[source]

Return distance mapping from cached attribute.

If no distance mapping is available, a new one is generated from embedded graph via _compute_distance_mapping().

Parameters:force_update – Indicate whether a new distance mapping should be computed, even if one cached mapping is available.
Returns:Distance mapping.
class wiz.graph._DistanceQueue(*args, **kwargs)[source]

Distance mapping which can be used as a queue.

Distances are cumulated weights computed between each node and the root level of the graph. Keys of the dictionary are node identifiers added into a queue, and values are their respective distances.

The advantage over a standard heapq-based distance queue is that distances of node identifiers can be efficiently updated (amortized O(1)).

Note

Inspired by Matteo Dell’Amico’s implementation: https://gist.github.com/matteodellamico/4451520

__init__(*args, **kwargs)[source]

Initialize mapping and build heap.

_build_heap()[source]

Build the heap from mapping’s keys and values.

empty()[source]

Indicate whether the mapping is empty.

Returns:Boolean value.
pop_smallest()[source]

Return item with the shortest distance from graph root and remove it.

Returns:Unique node identifier.
Raise:IndexError if the object is empty.