PK!;8xMMmixology/__init__.pyfrom .dependency_graph import DependencyGraph from .resolver import Resolver PK!,M+JJmixology/conflict.pyclass Conflict: def __init__(self, requirement, requirements, existing, possibility_set, locked_requirement, requirement_trees, activated_by_name, underlying_error): self.requirement = requirement self.requirements = requirements self.existing = existing self.possibility_set = possibility_set self.locked_requirement = locked_requirement self.requirement_trees = requirement_trees, self.activated_by_name = activated_by_name self.underlying_error = underlying_error @property def possibility(self): if self.possibility_set and self.possibility_set.latest_version: return self.possibility_set.latest_version PK!ּMMmixology/contracts/__init__.pyfrom .specification_provider import SpecificationProvider from .ui import UI PK!] ,mixology/contracts/specification_provider.pyfrom typing import Any from typing import Dict from typing import List from ..conflict import Conflict from ..dependency_graph import DependencyGraph class SpecificationProvider(object): """ Provides information about specifications and dependencies to the resolver, allowing the Resolver class to remain generic while still providing power and flexibility. This contract contains the methods that users of mixology must implement using knowledge of their own model classes. """ @property def name_for_explicit_dependency_source(self): # type: () -> str return 'user-specified dependency' @property def name_for_locking_dependency_source(self): # type: () -> str return 'Lockfile' def search_for(self, dependency): # type: (Any) -> List[Any] """ Search for the specifications that match the given dependency. The specifications in the returned list will be considered in reverse order, so the latest version ought to be last. """ return [] def dependencies_for(self, specification): # type: (Any) -> List[Any] """ Returns the dependencies of a given specification. """ return [] def is_requirement_satisfied_by(self, requirement, # type: Any activated, # type: DependencyGraph spec # type: Any ): # type: (...) -> Any """ Determines whether the given requirement is satisfied by the given spec, in the context of the currently activated dependency graph. """ return True def name_for(self, dependency): # type: (Any) -> str """ Returns the name for the given dependency. """ return str(dependency) def sort_dependencies(self, dependencies, # type: List[Any] activated, # type: DependencyGraph conflicts # type: Dict[str, List[Conflict]] ): # type: (...) -> List[Any] """ Sort dependencies so that the ones that are easiest to resolve are first. Easiest to resolve is (usually) defined by: 1) Is this dependency already activated? 2) How relaxed are the requirements? 3) Are there any conflicts for this dependency? 4) How many possibilities are there to satisfy this dependency? """ return sorted( dependencies, key=lambda dep: ( activated.vertex_named(self.name_for(dep)).payload is None, conflicts.get(self.name_for(dep) is None) ) ) def allow_missing(self, dependency): # type: (Any) -> bool """ Returns whether this dependency, which has no possible matching specifications, can safely be ignored. """ return False PK!}mixology/contracts/ui.pyimport sys class UI(object): def __init__(self, debug=False): self._debug = debug @property def output(self): return sys.stdout @property def progress_rate(self): # type: () -> float return 0.33 def is_debugging(self): # type: () -> bool return self._debug def indicate_progress(self): # type: () -> None self.output.write('.') def before_resolution(self): # type: () -> None self.output.write('Resolving dependencies...\n') def after_resolution(self): # type: () -> None self.output.write('') def debug(self, message, depth): # type: (...) -> None if self.is_debugging(): debug_info = str(message) debug_info = '\n'.join([ ':{}: {}'.format(str(depth).rjust(4), s) for s in debug_info.split('\n') ]) + '\n' self.output.write(debug_info) PK!%7  mixology/dependency_graph.pyfrom .exceptions import CircularDependencyError from .graph.log import Log class DependencyGraph: def __init__(self): self._vertices = {} self._log = Log() @property def vertices(self): return self._vertices @property def log(self): return self._log def tag(self, tag): return self._log.tag(self, tag) def rewind_to(self, tag): return self._log.rewind_to(self, tag) def add_child_vertex(self, name, payload, parent_names, requirement): root = True try: parent_names.index(None) except ValueError: root = False parent_names = [n for n in parent_names if n is not None] vertex = self.add_vertex(name, payload, root) if root: vertex.explicit_requirements.append(requirement) for parent_name in parent_names: parent_vertex = self.vertex_named(parent_name) self.add_edge(parent_vertex, vertex, requirement) return vertex def add_vertex(self, name, payload, root=False): return self._log.add_vertex(self, name, payload, root) def detach_vertex_named(self, name): return self._log.detach_vertex_named(self, name) def vertex_named(self, name): return self.vertices.get(name) def root_vertex_named(self, name): vertex = self.vertex_named(name) if vertex and vertex.root: return vertex def add_edge(self, origin, destination, requirement): if destination.has_path_to(origin): raise CircularDependencyError([origin, destination]) return self.add_edge_no_circular(origin, destination, requirement) def add_edge_no_circular(self, origin, destination, requirement): self._log.add_edge_no_circular( self, origin.name, destination.name, requirement ) def delete_edge(self, edge): return self._log.delete_edge( self, edge.origin.name, edge.destination.name, edge.requirement ) def set_payload(self, name, payload): return self._log.set_payload(self, name, payload) def to_dot(self): dot_vertices = [] dot_edges = [] for n, v in self.vertices.items(): dot_vertices.append( ' {} [label="{}|{}"]'.format(n, n, v.payload or '') ) for e in v.outgoing_edges: label = e.requirement dot_edges.append( ' {} -> {} [label="{}"]'.format( e.origin.name, e.destination.name, label ) ) dot_vertices = sorted(set(dot_vertices)) dot_edges = sorted(set(dot_edges)) dot_vertices.insert(0, 'digraph G {') dot_vertices.append('') dot_edges.append('}') dot = dot_vertices + dot_edges return '\n'.join(dot) def __iter__(self): return iter(self.vertices.values()) PK! >mixology/exceptions.pyfrom .helpers import flat_map class ResolverError(Exception): pass class NoSuchDependencyError(ResolverError): def __init__(self, dependency, required_by=None): if required_by is None: required_by = [] sources = ' and '.join(['"{}"'.format(r) for r in required_by]) message = 'Unable to find a specification for "{}"'.format(dependency) if sources: message += ' depended upon by {}'.format(sources) super(NoSuchDependencyError, self).__init__(message) class CircularDependencyError(ResolverError): def __init__(self, vertices): super(CircularDependencyError, self).__init__( 'There is a circular dependency between {}'.format( ' and '.join([v.name for v in vertices]) ) ) self._dependencies = [v.payload.possibilities[-1] for v in vertices] @property def dependencies(self): return self._dependencies class VersionConflict(ResolverError): def __init__(self, conflicts, specification_provider): pairs = [] for conflicting in flat_map( list(conflicts.values()), lambda x: x.requirements ): for source, conflict_requirements in conflicting.items(): for c in conflict_requirements: pairs.append((c, source)) super(VersionConflict, self).__init__( 'Unable to satisfy the following requirements:\n\n' '{}'.format( '\n'.join('- "{}" required by "{}"'.format(r, d) for r, d in pairs) ) ) self._conflicts = conflicts self._specification_provider = specification_provider @property def conflicts(self): return self._conflicts @property def specification_provider(self): return self._specification_provider def message_with_trees(self, solver_name='Poetry', possibility_type='possibility named', reduce_trees=lambda trees: sorted(set(trees), key=str), printable_requirement=str, message_for_conflict=None, version_for_spec=str): o = [] for name, conflict in sorted(self._conflicts): o.append( '\n{} could not find compatible versions for {} "{}"_n'.format( solver_name, possibility_type, name ) ) if conflict.locked_requirement: o.append( ' In snapshot ({}):\n'.format( self._specification_provider.name_for_locking_dependency_source ) ) o.append( ' {}\n'.format( printable_requirement(conflict.locked_requirement) ) ) o.append('\n') o.append( ' In {}:\n'.format( self._specification_provider.name_for_explicit_dependency_source ) ) trees = reduce_trees(conflict.requirement_trees) ot = [] for tree in trees: t = '' depth = 2 for req in tree: t += ' ' * depth + str(req) if tree[-1] != req: spec = conflict.activated_by_name.get( self._specification_provider.name_for(req) ) if spec: t += ' was resolved to {}, which'.format( version_for_spec(spec) ) t += ' depends on' t += '\n' depth += 1 ot.append(t) o.append('\n'.join(ot)) if message_for_conflict: message_for_conflict(o, name, conflict) return ''.join(o).strip() PK!mixology/graph/__init__.pyPK!"R22mixology/graph/action.pyfrom typing import Any class Action(object): def __init__(self): self.previous = None self.next = None @property def action_name(self): # type: () -> str raise NotImplementedError() def up(self, graph): # type: (DependencyGraph) -> Any """ Performs the action on the given graph. """ raise NotImplementedError() def down(self, graph): # type: (DependencyGraph) -> None """ Reverses the action on the given graph. """ raise NotImplementedError() PK!Owzz&mixology/graph/add_edge_no_circular.pyfrom .action import Action from .edge import Edge class AddEdgeNoCircular(Action): def __init__(self, origin, destination, requirement): super(AddEdgeNoCircular, self).__init__() self._origin = origin self._destination = destination self._requirement = requirement @property def action_name(self): return 'add_edge_no_circular' @property def origin(self): return self._origin @property def destination(self): return self._destination @property def requirement(self): return self._requirement def up(self, graph): edge = self.make_edge(graph) edge.origin.outgoing_edges.append(edge) edge.destination.incoming_edges.append(edge) return edge def down(self, graph): edge = self.make_edge(graph) self._delete_first(edge.origin.outgoing_edges, edge) self._delete_first(edge.destination.incoming_edges, edge) def make_edge(self, graph): return Edge( graph.vertex_named(self._origin), graph.vertex_named(self._destination), self._requirement ) def _delete_first(self, elements, element): """ :type elements: list """ try: index = elements.index(element) except ValueError: return del elements[index] PK!1IImixology/graph/add_vertex.pyfrom .action import Action from .vertex import Vertex _NULL = object() class AddVertex(Action): def __init__(self, name, payload, root): super(AddVertex, self).__init__() self._name = name self._payload = payload self._root = root self._existing_payload = _NULL self._existing_root = None @property def action_name(self): return 'add_vertex' @property def name(self): return self._name @property def payload(self): return self._payload @property def root(self): return self._root def up(self, graph): existing = graph.vertices.get(self._name) if existing: self._existing_payload = existing.payload self._existing_root = existing.root vertex = existing or Vertex(self._name, self._payload) graph.vertices[vertex.name] = vertex if not vertex.payload: vertex.payload = self.payload if not vertex.root: vertex.root = self.root return vertex def down(self, graph): if self._existing_payload is not _NULL: vertex = graph.vertices[self._name] vertex.payload = self._existing_payload vertex.root = self._existing_root else: del graph.vertices[self._name] PK!j^^mixology/graph/delete_edge.pyfrom .action import Action from .edge import Edge class DeleteEdge(Action): def __init__(self, origin, destination, requirement): super(DeleteEdge, self).__init__() self._origin = origin self._destination = destination self._requirement = requirement @property def action_name(self): return 'delete_edge' @property def origin(self): return self._origin @property def destination(self): return self._destination @property def requirement(self): return self._requirement def up(self, graph): edge = self.make_edge(graph) self._delete_first(edge.origin.outgoing_edges, edge) self._delete_first(edge.destination.incoming_edges, edge) return edge def down(self, graph): edge = self.make_edge(graph) edge.origin.outgoing_edges.append(edge) edge.origin.incoming_edges.append(edge) def make_edge(self, graph): return Edge( graph.vertex_named(self._origin), graph.vertex_named(self._destination), self._requirement ) def _delete_first(self, elements, element): """ :type elements: list """ try: index = elements.index(element) except ValueError: return del elements[index] PK!͍ %mixology/graph/detach_vertex_named.pyfrom .action import Action class DetachVertexNamed(Action): def __init__(self, name): super(DetachVertexNamed, self).__init__() self._name = name self._vertex = None @property def action_name(self): return 'detach_vertex' @property def name(self): return self._name def up(self, graph): if self._name not in graph.vertices: return [] self._vertex = graph.vertices[self._name] del graph.vertices[self._name] removed_vertices = [self._vertex] for e in self._vertex.outgoing_edges: v = e.destination try: v.incoming_edges.remove(e) except ValueError: pass if not v.root and not v.incoming_edges: removed_vertices += graph.detach_vertex_named(v.name) for e in self._vertex.incoming_edges: v = e.origin try: v.outgoing_edges.remove(e) except ValueError: pass return removed_vertices def down(self, graph): if self._vertex is None: return graph.vertices[self._vertex.name] = self._vertex for e in self._vertex.outgoing_edges: e.destination.incoming_edges.append(e) for e in self._vertex.incoming_edges: e.origin.outgoing_edges.append(e) PK!Nmixology/graph/edge.pyclass Edge: """ A directed edge of a DependencyGraph """ def __init__(self, origin, destination, requirement): self._origin = origin self._destination = destination self._requirement = requirement @property def origin(self): return self._origin @property def destination(self): return self._destination @property def requirement(self): return self._requirement def __eq__(self, other): return self._origin == other.origin and self._destination == other.destination def __repr__(self): return ' {}>'.format( self._origin.name, self._destination.name ) PK!T0 0 mixology/graph/log.pyfrom .add_edge_no_circular import AddEdgeNoCircular from .add_vertex import AddVertex from .delete_edge import DeleteEdge from .detach_vertex_named import DetachVertexNamed from .set_payload import SetPayload from .tag import Tag class Log: """ A log for dependency graph actions. """ def __init__(self): self._current_action = None self._first_action = None def tag(self, graph, tag): """ Tags the current state of the dependency as the given tag. """ return self._push_action(graph, Tag(tag)) def add_vertex(self, graph, name, payload, root): return self._push_action(graph, AddVertex(name, payload, root)) def detach_vertex_named(self, graph, name): return self._push_action(graph, DetachVertexNamed(name)) def add_edge_no_circular(self, graph, origin, destination, requirement): action = AddEdgeNoCircular(origin, destination, requirement) return self._push_action(graph, action) def delete_edge(self, graph, origin, destination, requirement): action = DeleteEdge(origin, destination, requirement) return self._push_action(graph, action) def set_payload(self, graph, name, payload): return self._push_action(graph, SetPayload(name, payload)) def pop(self, graph): action = self._current_action if not action: return self._current_action = action.previous if not self._current_action: self._first_action = None action.down(graph) return action def rewind_to(self, graph, tag): while True: action = self.pop(graph) if not action: raise ValueError('No tag "{}" found'.format(tag)) if isinstance(action, Tag) and action.tag == tag: break def _push_action(self, graph, action): """ Adds the given action to the log, running the action :param graph: The graph :param action: The action :type action: Action """ action.previous = self._current_action if self._current_action: self._current_action.next = action self._current_action = action if not self._first_action: self._first_action = action return action.up(graph) PK!mixology/graph/set_payload.pyfrom .action import Action class SetPayload(Action): def __init__(self, name, payload): super(SetPayload, self).__init__() self._name = name self._payload = payload self._old_payload = None @property def action_name(self): return 'set_payload' @property def name(self): return self._name @property def payload(self): return self._payload def up(self, graph): vertex = graph.vertex_named(self._name) self._old_payload = vertex.payload vertex.payload = self._payload def down(self, graph): graph.vertex_named(self._name).payload = self._old_payload PK!lZ9UUmixology/graph/tag.pyfrom .action import Action class Tag(Action): def __init__(self, tag): super(Tag, self).__init__() self._tag = tag @property def action_name(self): return 'tag' @property def tag(self): return self._tag def up(self, graph): pass def down(self, graph): pass PK!ڀ_ _ mixology/graph/vertex.pyfrom ..utils import unique class Vertex: def __init__(self, name, payload): self.name = name self.payload = payload self.root = False self._explicit_requirements = [] self.outgoing_edges = [] self.incoming_edges = [] @property def explicit_requirements(self): return self._explicit_requirements @property def requirements(self): return unique([ edge.requirement for edge in self.incoming_edges ] + self._explicit_requirements) @property def predecessors(self): return [edge.origin for edge in self.incoming_edges] @property def recursive_predecessors(self): return self._recursive_predecessors() def _recursive_predecessors(self, vertices=None): if vertices is None: vertices = set() for edge in self.incoming_edges: vertex = edge.origin if vertex in vertices: continue vertices.add(vertex) vertex._recursive_predecessors(vertices) return vertices @property def successors(self): return [ edge.destination for edge in self.outgoing_edges ] @property def recursive_successors(self): return self._recursive_successors() def _recursive_successors(self, vertices=None): if vertices is None: vertices = set() for edge in self.outgoing_edges: vertex = edge.destination if vertex in vertices: continue vertices.add(vertex) vertex._recursive_successors(vertices) return vertices def __eq__(self, other): if not isinstance(other, Vertex): return NotImplemented if self is other: return True return ( self.name == other.name and self.payload == other.payload and set(self.successors) == set(other.successors) ) def __hash__(self): return hash(self.name) def has_path_to(self, other): return ( self == other or any([v.has_path_to(other) for v in self.successors]) ) def is_ancestor(self, other): return other.path_to(self) def __repr__(self): return ''.format(self.name, self.payload) PK!C_Nmixology/helpers.pydef flat_map(iter, callable): if not isinstance(iter, (list, tuple)): yield callable(iter) else: for v in iter: for i in flat_map(v, callable): yield i PK!fShmixology/possibility_set.pyclass PossibilitySet: def __init__(self, dependencies, possibilities): self.dependencies = dependencies self.possibilities = possibilities @property def latest_version(self): if self.possibilities: return self.possibilities[-1] def __str__(self): return '[{}]'.format(', '.join([str(p) for p in self.possibilities])) def __repr__(self): return ''.format(str(self)) PK!bXxmixology/resolution.py# -*- coding: utf-8 -*- import logging from copy import copy from datetime import datetime from typing import Any from typing import List from .contracts import SpecificationProvider from .contracts import UI from .exceptions import CircularDependencyError from .exceptions import VersionConflict from .conflict import Conflict from .dependency_graph import DependencyGraph from .helpers import flat_map from .possibility_set import PossibilitySet from .state import DependencyState from .unwind_details import UnwindDetails from .utils import unique logger = logging.getLogger(__name__) class Resolution: def __init__(self, provider, # type: SpecificationProvider ui, # type: UI requested, # type: List[Any] base # type: DependencyGraph ): self._provider = provider self._ui = ui self._requested = requested self._original_requested = copy(requested) self._base = base self._states = [] self._iteration_counter = 0 self._progress_rate = 0.33 self._iteration_rate = None self._parents_of = {} self._started_at = None @property def provider(self): # type: () -> SpecificationProvider return self._provider @property def ui(self): # type: () -> UI return self._ui @property def requested(self): # type: () -> List[Any] return self._requested @property def base(self): # type: () -> DependencyGraph return self._base @property def activated(self): # type: () -> DependencyGraph return self.state.activated def resolve(self): # type: () -> DependencyGraph """ Resolve the original requested dependencies into a full dependency graph. """ self._start() try: while self.state: if not self.state.requirement and not self.state.requirements: break self._indicate_progress() if hasattr(self.state, 'pop_possibility_state'): self._debug( 'Creating possibility state for {} ({} remaining)' .format( str(self.state.requirement), len(self.state.possibilities) ) ) s = self.state.pop_possibility_state() if s: self._states.append(s) self.activated.tag(s) self._process_topmost_state() return self._resolve_activated_specs() finally: self._end() def _start(self): # type: () -> None """ Set up the resolution process. """ self._started_at = datetime.now() self._debug( 'Starting resolution ({})\nRequested dependencies: {}'.format( self._started_at, [str(d) for d in self._original_requested] ) ) self._ui.before_resolution() self._handle_missing_or_push_dependency_state(self._initial_state()) def _resolve_activated_specs(self): # type: () -> DependencyGraph for vertex in self.activated.vertices.values(): if not vertex.payload: continue latest_version = None for possibility in reversed(list(vertex.payload.possibilities)): if all( [ self._provider.is_requirement_satisfied_by( req, self.activated, possibility ) for req in vertex.requirements ] ): latest_version = possibility break self.activated.set_payload(vertex.name, latest_version) return self.activated def _end(self): # type: () -> None """ Ends the resolution process """ elapsed = (datetime.now() - self._started_at).total_seconds() self._ui.after_resolution() self._debug( 'Finished resolution ({} steps) ' 'in {:.3f} seconds'.format( self._iteration_counter, elapsed ) ) def _process_topmost_state(self): # type: () -> None """ Processes the topmost available RequirementState on the stack. """ try: if self.possibility: self._attempt_to_activate() else: self._create_conflict() self._unwind_for_conflict() except CircularDependencyError as e: self._create_conflict(e) self._unwind_for_conflict() @property def possibility(self): # type: () -> PossibilitySet """ The current possibility that the resolution is trying. """ if self.state.possibilities: return self.state.possibilities[-1] @property def state(self): # type: () -> DependencyState """ The current state the resolution is operating upon. """ if self._states: return self._states[-1] @property def name(self): # type: () -> str return self.state.name @property def requirement(self): # type: () -> Any return self.state.requirement def _initial_state(self): # type: () -> DependencyState """ Create the initial state for the resolution, based upon the requested dependencies. """ graph = DependencyGraph() for requested in self._original_requested: vertex = graph.add_vertex( self._provider.name_for(requested), None, True ) vertex.explicit_requirements.append(requested) graph.tag('initial_state') requirements = self._provider.sort_dependencies( self._original_requested, graph, {} ) initial_requirement = None if requirements: initial_requirement = requirements.pop(0) name = None if initial_requirement: name = self._provider.name_for(initial_requirement) return DependencyState( name, requirements, graph, initial_requirement, self._possibilities_for_requirement(initial_requirement, graph), 0, {}, [] ) def _unwind_for_conflict(self): # type: () -> None """ Unwinds the states stack because a conflict has been encountered """ details_for_unwind = self._build_details_for_unwind() unwind_options = self.state.unused_unwind_options self._debug( 'Unwinding for conflict: ' '{} to {}'.format( str(self.state.requirement), details_for_unwind.state_index // 2 ), self.state.depth ) conflicts = self.state.conflicts sliced_states = self._states[details_for_unwind.state_index + 1:] self._states = self._states[:details_for_unwind.state_index + 1] self._raise_error_unless_state(conflicts) if sliced_states: self.activated.rewind_to( sliced_states[0] or 'initial_state' ) self.state.conflicts = conflicts self.state.unused_unwind_options = unwind_options self._filter_possibilities_after_unwind(details_for_unwind) index = len(self._states) - 1 for k, l in self._parents_of.items(): self._parents_of[k] = [x for x in l if x < index] self.state.unused_unwind_options = [ uw for uw in self.state.unused_unwind_options if uw.state_index < index ] def _raise_error_unless_state(self, conflicts): # type: (dict) -> None """ Raise a VersionConflict error, or any underlying error, if there is no current state """ if self.state: return errors = [c.underlying_error for c in conflicts.values() if c.underlying_error is not None] if errors: error = errors[0] else: error = VersionConflict(conflicts, self._provider) raise error def _build_details_for_unwind(self): # type: () -> UnwindDetails """ Return the details of the nearest index to which we could unwind. """ # Get the possible unwinds for the current conflict current_conflict = self.state.conflicts[self.state.name] binding_requirements = self._binding_requirements_for_conflict( current_conflict ) unwind_details = self._unwind_options_for_requirements( binding_requirements ) last_detail_for_current_unwind = sorted(unwind_details)[-1] current_detail = last_detail_for_current_unwind # Look for past conflicts that could be unwound to affect the # requirement tree for the current conflict relevant_unused_unwinds = [] for alternative in self.state.unused_unwind_options: intersecting_requirements = ( set(last_detail_for_current_unwind.all_requirements) & set(alternative.requirements_unwound_to_instead) ) if not intersecting_requirements: continue # Find the highest index unwind whilst looping through if alternative > current_detail: current_detail = alternative relevant_unused_unwinds.append(alternative) # Add the current unwind options to the `unused_unwind_options` array. # The "used" option will be filtered out during `unwind_for_conflict`. self.state.unused_unwind_options += [ detail for detail in unwind_details if detail.state_index != -1 ] # Update the requirements_unwound # to_instead on any relevant unused unwinds for d in relevant_unused_unwinds: d.requirements_unwound_to_instead.append( current_detail.state_requirement ) for d in unwind_details: d.requirements_unwound_to_instead.append( current_detail.state_requirement ) return current_detail def _unwind_options_for_requirements(self, binding_requirements ): # type: (list) -> List[UnwindDetails] unwind_details = [] trees = [] for r in reversed(binding_requirements): partial_tree = [r] trees.append(partial_tree) unwind_details.append( UnwindDetails( -1, None, partial_tree, binding_requirements, trees, [] ) ) # If this requirement has alternative possibilities, # check if any would satisfy the other requirements # that created this conflict requirement_state = self._find_state_for(r) if self._conflict_fixing_possibilities(requirement_state, binding_requirements): unwind_details.append( UnwindDetails( self._states.index(requirement_state), r, partial_tree, binding_requirements, trees, [] ) ) # Next, look at the parent of this requirement, # and check if the requirement could have been avoided # if an alternative PossibilitySet had been chosen parent_r = self._parent_of(r) if parent_r is None: continue partial_tree.insert(0, parent_r) requirement_state = self._find_state_for(parent_r) possibilities = [ r.name in map(lambda x: x.name, set_.dependencies) for set_ in requirement_state.possibilities ] if any(possibilities): unwind_details.append( UnwindDetails( self._states.index(requirement_state), parent_r, partial_tree, binding_requirements, trees, [] ) ) # Finally, look at the grandparent and up of this requirement, # looking for any possibilities that wouldn't # create their parent requirement grandparent_r = self._parent_of(parent_r) while grandparent_r is not None: partial_tree.insert(0, grandparent_r) requirement_state = self._find_state_for(grandparent_r) possibilities = [ parent_r.name in map(lambda x: x.name, set_.dependencies) for set_ in requirement_state.possibilities ] if any(possibilities): unwind_details.append( UnwindDetails( self._states.index(requirement_state), grandparent_r, partial_tree, binding_requirements, trees, [] ) ) parent_r = grandparent_r grandparent_r = self._parent_of(parent_r) return unwind_details def _conflict_fixing_possibilities(self, state, binding_requirements): """ Return whether or not the given state has any possibilities that could satisfy the given requirements :rtype: bool """ if not state: return False return any([ any([ self._possibility_satisfies_requirements( poss, binding_requirements ) ]) for possibility_set in state.possibilities for poss in possibility_set.possibilities ]) def _filter_possibilities_after_unwind(self, unwind_details): """ Filter a state's possibilities to remove any that would not fix the conflict we've just rewound from :type unwind_details: UnwindDetails """ if not self.state or not self.state.possibilities: return if unwind_details.unwinding_to_primary_requirement(): self._filter_possibilities_for_primary_unwind(unwind_details) else: self._filter_possibilities_for_parent_unwind(unwind_details) def _filter_possibilities_for_primary_unwind(self, unwind_details): """ Filter a state's possibilities to remove any that would not satisfy the requirements in the conflict we've just rewound from. :type unwind_details: UnwindDetails """ unwinds_to_state = [ uw for uw in self.state.unused_unwind_options if uw.state_index == unwind_details.state_index ] unwinds_to_state.append(unwind_details) unwind_requirement_sets = [ uw.conflicting_requirements for uw in unwinds_to_state ] possibilities = [] for possibility_set in self.state.possibilities: if not any([ any([ self._possibility_satisfies_requirements( poss, requirements ) ]) for poss in possibility_set.possibilities for requirements in unwind_requirement_sets ]): continue possibilities.append(possibility_set) self.state.possibilities = possibilities def _possibility_satisfies_requirements(self, possibility, requirements): name = self._provider.name_for(possibility) self.activated.tag('swap') if self.activated.vertex_named(name): self.activated.set_payload(name, possibility) satisfied = all([ self._provider.is_requirement_satisfied_by( r, self.activated, possibility ) for r in requirements ]) self.activated.rewind_to('swap') return satisfied def _filter_possibilities_for_parent_unwind(self, unwind_details # type: UnwindDetails ): """ Filter a state's possibilities to remove any that would (eventually) the requirements in the conflict we've just rewound from. """ unwinds_to_state = [ uw for uw in self.state.unused_unwind_options if uw.state_index == unwind_details.state_index ] unwinds_to_state.append(unwind_details) primary_unwinds = unique([ uw for uw in unwinds_to_state if uw.unwinding_to_primary_requirement() ]) parent_unwinds = unique(unwinds_to_state) parent_unwinds = [uw for uw in parent_unwinds if uw not in primary_unwinds] allowed_possibility_sets = [] for unwind in primary_unwinds: for possibility_set in self._states[unwind.state_index].possibilities: if any([ self._possibility_satisfies_requirements( poss, unwind.conflicting_requirements ) for poss in possibility_set.possibilities ]): allowed_possibility_sets.append(possibility_set) requirements_to_avoid = list(flat_map( parent_unwinds, lambda x: x.sub_dependencies_to_avoid )) possibilities = [] for possibility_set in self.state.possibilities: if ( possibility_set in allowed_possibility_sets or [ r for r in requirements_to_avoid if r not in possibility_set.dependencies ] ): possibilities.append(possibility_set) self.state.possibilities = possibilities def _binding_requirements_for_conflict(self, conflict): """ Return the minimal list of requirements that would cause the passed conflict to occur. :rtype: list """ if conflict.possibility is None: return [conflict.requirement] possible_binding_requirements_set = list(conflict.requirements.values()) possible_binding_requirements = [] for reqs in possible_binding_requirements_set: if isinstance(reqs, list): possible_binding_requirements += reqs else: possible_binding_requirements.append(reqs) possible_binding_requirements = unique(possible_binding_requirements) # When there’s a `CircularDependency` error the conflicting requirement # (the one causing the circular) won’t be `conflict.requirement` # (which won’t be for the right state, because we won’t have created it, # because it’s circular). # We need to make sure we have that requirement in the conflict’s list, # otherwise we won’t be able to unwind properly, so we just return all # the requirements for the conflict. if conflict.underlying_error: return possible_binding_requirements possibilities = self._provider.search_for(conflict.requirement) # If all the requirements together don't filter out all possibilities, # then the only two requirements we need to consider are the initial one # (where the dependency's version was first chosen) and the last if self._binding_requirement_in_set( None, possible_binding_requirements, possibilities ): return list(filter(None, [ conflict.requirement, self._requirement_for_existing_name( self._provider.name_for(conflict.requirement) ) ])) # Loop through the possible binding requirements, removing each one # that doesn't bind. Use a reversed as we want the earliest set of # binding requirements. binding_requirements = copy(possible_binding_requirements) for req in reversed(possible_binding_requirements): if req == conflict.requirement: continue if not self._binding_requirement_in_set( req, binding_requirements, possibilities ): index = binding_requirements.index(req) del binding_requirements[index] return binding_requirements def _binding_requirement_in_set(self, requirement, possible_binding_requirements, possibilities): # type: () -> bool """ Return whether or not the given requirement is required to filter out all elements of the list of possibilities. """ return any([ self._possibility_satisfies_requirements( poss, set(possible_binding_requirements) - set([requirement]) ) for poss in possibilities ]) def _parent_of(self, requirement): if not requirement: return if requirement not in self._parents_of: self._parents_of[requirement] = [] if not self._parents_of[requirement]: return try: index = self._parents_of[requirement][-1] except ValueError: return try: parent_state = self._states[index] except ValueError: return return parent_state.requirement def _requirement_for_existing_name(self, name): vertex = self.activated.vertex_named(name) if not vertex: return if not vertex.payload: return for s in self._states: if s.name == name: return s.requirement def _find_state_for(self, requirement): if not requirement: return for s in self._states: if s.requirement == requirement: return s def _create_conflict(self, underlying_error=None): vertex = self.activated.vertex_named(self.state.name) locked_requirement = self._locked_requirement_named(self.state.name) requirements = {} if vertex.explicit_requirements: requirements[self._provider.name_for_explicit_dependency_source] = vertex.explicit_requirements if locked_requirement: requirements[self._provider.name_for_locking_dependency_source] = [locked_requirement] for edge in vertex.incoming_edges: if edge.origin.payload.latest_version not in requirements: requirements[edge.origin.payload.latest_version] = [] requirements[edge.origin.payload.latest_version].insert(0, edge.requirement) activated_by_name = {} for v in self.activated: if v.payload: activated_by_name[v.name] = v.payload.latest_version conflict = Conflict( self.requirement, requirements, vertex.payload.latest_version if vertex.payload else None, self.possibility, locked_requirement, self.requirement_trees, activated_by_name, underlying_error ) self.state.conflicts[self.name] = conflict return conflict @property def requirement_trees(self): vertex = self.activated.vertex_named(self.state.name) return [self._requirement_tree_for(r) for r in vertex.requirements] def _requirement_tree_for(self, requirement): tree = [] while requirement: tree.insert(0, requirement) requirement = self._parent_of(requirement) return tree def _indicate_progress(self): self._iteration_counter += 1 progress_rate = self._ui.progress_rate or self._progress_rate if self._iteration_rate is None: if (datetime.now() - self._started_at).total_seconds() >= progress_rate: self._iteration_rate = self._iteration_counter if self._iteration_rate and (self._iteration_counter % self._iteration_rate) == 0: self._ui.indicate_progress() def _debug(self, message, depth=0): self._ui.debug(message, depth) def _attempt_to_activate(self): self._debug( 'Attempting to activate {}'.format(str(self.possibility)), self.state.depth, ) existing_vertex = self.activated.vertex_named(self.state.name) if existing_vertex.payload: self._debug( 'Found existing spec ({})'.format(existing_vertex.payload), self.state.depth ) self._attempt_to_filter_existing_spec(existing_vertex) else: latest = self.possibility.latest_version possibilities = [] for possibility in self.possibility.possibilities: if self._provider.is_requirement_satisfied_by( self.requirement, self.activated, possibility ): possibilities.append(possibility) self.possibility.possibilities = possibilities if self.possibility.latest_version is None: # ensure there's a possibility for better error messages if latest: self.possibility.possibilities.append(latest) self._create_conflict() self._unwind_for_conflict() else: self._activate_new_spec() def _attempt_to_filter_existing_spec(self, vertex): """ Attempt to update the existing vertex's `PossibilitySet` with a filtered version. """ filtered_set = self._filtered_possibility_set(vertex) if filtered_set.possibilities: self.activated.set_payload(self.name, filtered_set) new_requirements = copy(self.state.requirements) self._push_state_for_requirements(new_requirements, False) else: self._create_conflict() self._debug( 'Unsatisfied by existing spec ({})'.format(str(vertex.payload)), self.state.depth ) self._unwind_for_conflict() def _filtered_possibility_set(self, vertex): possibilities = [ p for p in vertex.payload.possibilities if p in self.possibility.possibilities ] return PossibilitySet( vertex.payload.dependencies, possibilities ) def _locked_requirement_named(self, requirement_name): vertex = self.base.vertex_named(requirement_name) if vertex: return vertex.payload def _activate_new_spec(self): if self.state.name in self.state.conflicts: del self.state.conflicts[self.name] self._debug( 'Activated {} at {}'.format(self.state.name, str(self.possibility)), self.state.depth ) self.activated.set_payload(self.state.name, self.possibility) self._require_nested_dependencies_for(self.possibility) def _require_nested_dependencies_for(self, possibility_set): nested_dependencies = self._provider.dependencies_for( possibility_set.latest_version ) self._debug( 'Requiring nested dependencies ' '({})'.format(', '.join([str(d) for d in nested_dependencies])), self.state.depth ) for d in nested_dependencies: self.activated.add_child_vertex( self._provider.name_for(d), None, [self._provider.name_for(possibility_set.latest_version)], d ) parent_index = len(self._states) - 1 if d not in self._parents_of: self._parents_of[d] = [] parents = self._parents_of[d] if not parents: parents.append(parent_index) self._push_state_for_requirements( self.state.requirements + nested_dependencies, len(nested_dependencies) > 0 ) def _push_state_for_requirements(self, new_requirements, requires_sort=True, new_activated=None): if new_activated is None: new_activated = self.activated if requires_sort: new_requirements = self._provider.sort_dependencies( unique(new_requirements), new_activated, self.state.conflicts ) while True: new_requirement = None if new_requirements: new_requirement = new_requirements.pop(0) if ( new_requirement is None or not any([ s.requirement == new_requirement for s in self._states ]) ): break new_name = '' if new_requirement: new_name = self._provider.name_for(new_requirement) possibilities = self._possibilities_for_requirement(new_requirement) self._handle_missing_or_push_dependency_state( DependencyState( new_name, new_requirements, new_activated, new_requirement, possibilities, self.state.depth, copy(self.state.conflicts), copy(self.state.unused_unwind_options) ) ) def _possibilities_for_requirement(self, requirement, activated=None): if activated is None: activated = self.activated if not requirement: return [] if self._locked_requirement_named(self._provider.name_for(requirement)): return self._locked_requirement_possibility_set( requirement, activated ) return self._group_possibilities( self._provider.search_for(requirement) ) def _locked_requirement_possibility_set(self, requirement, activated=None): if activated is None: activated = self.activated all_possibilities = self._provider.search_for(requirement) locked_requirement = self._locked_requirement_named( self._provider.name_for(requirement) ) # Longwinded way to build a possibilities list with either the locked # requirement or nothing in it. Required, since the API for # locked_requirement isn't guaranteed. locked_possibilities = [ possibility for possibility in all_possibilities if self._provider.is_requirement_satisfied_by( locked_requirement, activated, possibility ) ] return self._group_possibilities(locked_possibilities) def _group_possibilities(self, possibilities): possibility_sets = [] current_possibility_set = None for possibility in reversed(possibilities): dependencies = self._provider.dependencies_for(possibility) if current_possibility_set and current_possibility_set.dependencies == dependencies: current_possibility_set.possibilities.insert(0, possibility) else: possibility_sets.insert( 0, PossibilitySet(dependencies, [possibility]) ) current_possibility_set = possibility_sets[0] return possibility_sets def _handle_missing_or_push_dependency_state(self, state): if ( state.requirement and not state.possibilities and self._provider.allow_missing(state.requirement) ): state.activated.detach_vertex_named(state.name) self._push_state_for_requirements( copy(state.requirements), False, state.activated ) else: self._states.append(state) state.activated.tag(state) PK!|`vvmixology/resolver.pyfrom typing import Any from typing import List from typing import Union from .contracts import SpecificationProvider from .contracts import UI from .dependency_graph import DependencyGraph from .resolution import Resolution class Resolver: def __init__(self, specification_provider, # type: SpecificationProvider resolver_ui # type: UI ): self._specification_provider = specification_provider self._resolver_ui = resolver_ui @property def specification_provider(self): # type: () -> SpecificationProvider return self._specification_provider @property def ui(self): # type: () -> UI return self._resolver_ui def resolve(self, requested, # type: List[Any] base=None # type: Union[DependencyGraph, None] ): # type: (...) -> DependencyGraph if base is None: base = DependencyGraph() return Resolution( self._specification_provider, self._resolver_ui, requested, base ).resolve() PK!s4mixology/state.pyfrom copy import copy from .dependency_graph import DependencyGraph class ResolutionState: def __init__(self, name, requirements, activated, requirement, possibilities, depth, conflicts, unused_unwind_options): self._name = name self._requirements = requirements self._activated = activated self._requirement = requirement self.possibilities = possibilities self._depth = depth self.conflicts = conflicts self.unused_unwind_options = unused_unwind_options @property def name(self): return self._name @property def requirements(self): return self._requirements @property def activated(self): return self._activated @property def requirement(self): return self._requirement @property def depth(self): return self._depth @classmethod def empty(cls): return cls(None, [], DependencyGraph(), None, None, 0, {}, []) def __repr__(self): return '<{} {} ({})>'.format( self.__class__.__name__, self._name, str(self.requirement) ) class PossibilityState(ResolutionState): pass class DependencyState(ResolutionState): def pop_possibility_state(self): state = PossibilityState( self._name, copy(self._requirements), self._activated, self._requirement, [self.possibilities.pop() if self.possibilities else None], self._depth + 1, copy(self.conflicts), copy(self.unused_unwind_options) ) state.activated.tag(state) return state PK!: mixology/unwind_details.pyclass UnwindDetails: def __init__(self, state_index, state_requirement, requirement_tree, conflicting_requirements, requirement_trees, requirements_unwound_to_instead): self.state_index = state_index self.state_requirement = state_requirement self.requirement_tree = requirement_tree self.conflicting_requirements = conflicting_requirements self.requirement_trees = requirement_trees self.requirements_unwound_to_instead = requirements_unwound_to_instead self._reversed_requirement_tree_index = None self._sub_dependencies_to_avoid = None self._all_requirements = None @property def reversed_requirement_tree_index(self): if self._reversed_requirement_tree_index is None: if self.state_requirement: self._reversed_requirement_tree_index = list(reversed( self.requirement_tree )).index(self.state_requirement) else: self._reversed_requirement_tree_index = 999999 return self._reversed_requirement_tree_index def unwinding_to_primary_requirement(self): return self.requirement_tree[-1] == self.state_requirement @property def sub_dependencies_to_avoid(self): if self._sub_dependencies_to_avoid is None: self._sub_dependencies_to_avoid = [] for tree in self.requirement_trees: try: index = tree.index(self.state_requirement) except ValueError: continue if tree[index + 1] is not None: self._sub_dependencies_to_avoid.append(tree[index + 1]) return self._sub_dependencies_to_avoid @property def all_requirements(self): if self._all_requirements is None: self._all_requirements = [ x for tree in self.requirement_trees for x in tree ] return self._all_requirements def __eq__(self, other): if not isinstance(other, UnwindDetails): return NotImplemented return ( self.state_index == other.state_index and ( self.reversed_requirement_tree_index == other.reversed_requirement_tree_index ) ) def __lt__(self, other): if not isinstance(other, UnwindDetails): return NotImplemented return self.state_index < other.state_index def __le__(self, other): if not isinstance(other, UnwindDetails): return NotImplemented return self.state_index <= other.state_index def __gt__(self, other): if not isinstance(other, UnwindDetails): return NotImplemented return self.state_index > other.state_index def __ge__(self, other): if not isinstance(other, UnwindDetails): return NotImplemented return self.state_index >= other.state_index def __hash__(self): return hash((id(self), self.state_index, self.state_requirement)) PK!gծffmixology/utils.pydef unique(l): used = set() return [x for x in l if x not in used and (used.add(x) or True)] PK!HJtXYmixology-0.1.0.dist-info/WHEEL A н#V."jm)Afd~ dڡOsL`hAf]YE*-"3ت/ޕ6 "7PK!HH^P H!mixology-0.1.0.dist-info/METADATAYr۸ϧ@iwFӤIifb -;@}XjNCs3ay-Ch#U`Ϣ[Զ'Ip^9(1KD)Dq=¨g<*-m``e{WTQż[HK-h :U~diJn>Ty#cQ^N,N*H v Xc,Ee`F4?IV^{Yq$?.RQFNHib"4 IoV߀xye*..?k^BcecSNc?Q:7̂H&{U+ȞQÆ8[bh $1,VaOO{17b,WȘZ1B}(WqflلRc☤3̆.Q'Y$+3aӫy X*ԩ̀4aBl>WX6m=gk ·B .PdJ]v&KWmOq0Sp0=zmVɛNߵm m#Kgvd4-nM'vTэlhdn2qJyO_/`5j=G@ 'rrǐۚrM c3Ef`80Q8Fl <-ť)3KҠ"bjD =f=Ӑ_^ia+]&C֓o7DF:NI34yRԎ԰K|옷߹ƺtpn5^^@G&߹b#^/A?ho-7w̘Ɓ}TM-xMKF kF }LvXz[^xzO eer/j%]'Kwuf$:>/Nm }.#vxa|IJ$cy_Dt!$h2H@~ed'%NCq|ۥ Y:/5LB.mz}pq>baI( G]A#$jOJ˽27Y$i4n?!ϦC4F:7$ы :;8i?N`yߓ=0n2RuEIo1R޻ f/\u5(v>5tHzop2集k٪GK{5ߣjW[T*/O?x^S6x_kmHwk͋8].*kB gwF, Y@w4ᄏc |p;;FĕsU]׎1: ]^8Vfx9g[V&-+-M.Qj˱ hPK!HĢmixology-0.1.0.dist-info/RECORDuǺH}_ !,P  ,@B ^=szv^CmQ8FG`-XOk1̻.11淓=ٴ5 Ri5LVK[@LLY$3]C`&0/ֈt~0,Ydu(KY˜.C Ju5|:t 9LMԡ3VU`lhsKc_U33>mkK/Hhm @]U/ S0ƗTbK'cl+L^:dI@qw[*J7Ӥ]g":I/u;]h `NAÊ{ta+-ˁR<9Ml@R>ڙ0܏`ˊݕaxg5 L6p;k;-;{p=M4kW9%{1#tc9ꋗe 5mBNunyJ7VߨXv ?][QLҸA8 -F2o@#Wh1;kA?Ѳkee"B:1fhj0ׅ68X3mnDβIYP[噯FM|Jۍ>l*Pч%ZY+`[%2U[g/G=psrC $Y|=,f٪0~=k0/CHG7p9b2X1]{GP /MuRQʉ^Y;tV-F3_eS_`|v(}1oNUD:ekwFt~dQ @^`ÝP:FD{ܡ.3m1Xuk&k^Fol_VeNR-y >VDEnU;>xq] \ !7b`K}b4M0'-~ޙ&l`durAE8}Emy_zSVm;X^] i)%'/S+ijɢ+u/K4Z J8i'ܱ\$#='hH5jZvkOv,2TL/m}ŅaaE1{/0o9n;(qrّ@fz{@OL=*FxݡXl> %jxJQ$ˑ1_PK!;8xMMmixology/__init__.pyPK!,M+JJmixology/conflict.pyPK!ּMMmixology/contracts/__init__.pyPK!] ,mixology/contracts/specification_provider.pyPK!}mixology/contracts/ui.pyPK!%7  mixology/dependency_graph.pyPK! >!mixology/exceptions.pyPK!W1mixology/graph/__init__.pyPK!"R221mixology/graph/action.pyPK!Owzz&3mixology/graph/add_edge_no_circular.pyPK!1II9mixology/graph/add_vertex.pyPK!j^^8?mixology/graph/delete_edge.pyPK!͍ %Dmixology/graph/detach_vertex_named.pyPK!NJmixology/graph/edge.pyPK!T0 0 Mmixology/graph/log.pyPK!Vmixology/graph/set_payload.pyPK!lZ9UUYmixology/graph/tag.pyPK!ڀ_ _ Y[mixology/graph/vertex.pyPK!C_Ndmixology/helpers.pyPK!fShemixology/possibility_set.pyPK!bXxgmixology/resolution.pyPK!|`vv8mixology/resolver.pyPK!s4mixology/state.pyPK!: mixology/unwind_details.pyPK!gծffmixology/utils.pyPK!HJtXY3mixology-0.1.0.dist-info/WHEELPK!HH^P H!mixology-0.1.0.dist-info/METADATAPK!HĢV mixology-0.1.0.dist-info/RECORDPK