DOCSEARCHbyAlgolia
Submit Docs

resolvelib

repository·main·Indexed 41 days ago

https://github.com/sarugaku/resolvelib

A generic dependency resolution engine that allows developers to resolve abstract dependencies into concrete ones by implementing a custom provider. It includes a Resolver class, an AbstractProvider interface for mapping requirements to candidates, and a BaseReporter for monitoring resolution progress and visualizing dependency graphs.

Tokens
7K
Snippets
16
Records
24
Agent score
50%

What's inside resolvelib

  1. ResolveLib terminology and concepts

    main

    To avoid confusion when implementing providers or interpreting results, ResolveLib uses the following specific terminology:

    • Package: A thing that can be installed. A Package can have one or more versions available.
    • Version: A string (usually numeric) describing a snapshot of a Package. Higher numbers indicate more up-to-date snapshots.
    • Specifier: A collection of one or more Versions (e.g., a wildcard indicating any version is acceptable).
    • Candidate: A combination of a Package and a Version (a "concrete requirement"). Do not use the terms "requirement" or "dependency" when describing a Candidate.
    • Requirement: An intention to acquire a needed package (an "abstract requirement"). A Requirement specifies a Package and a Specifier. The term "dependency" also refers to this concept.

  2. How to use ResolveLib for dependency resolution

    main

    ResolveLib provides a Resolver class that handles dependency resolution logic. To use it, you must provide a provider object that implements the necessary logic to understand your specific requirement format, and an optional reporter for tracking the process.

    While you don't need to inherit from a specific class, your provider must implement the methods defined in resolvelib.providers to interact with the resolver. The resolution process is kicked off by calling resolver.resolve(requirements).

    import resolvelib

# 1. Define the things you want to resolve (e.g., a list of requirements)
requirements = [...]

# 2. Implement a provider that understands your requirement format
# The provider interface is specified in `resolvelib.providers`
class MyProvider:
    ...

provider = MyProvider()
reporter = resolvelib.BaseReporter()

# 3. Create the reusable resolver
resolver = resolvelib.Resolver(provider, reporter)

# 4. Kick off the resolution process and get the final result
result = resolver.resolve(requirements)

  3. Guidelines for submitting Pull Requests

    main

    When submitting changes to ResolveLib, follow these best practices:

    • Test Coverage: Ensure all changes are covered by existing tests or include new tests for the added functionality.
    • Portability: Keep code portable, as ResolveLib is used across many different Python versions, operating systems, and environments.
    • Size: Keep pull requests small to facilitate easier and faster reviews.

  4. Visualize dependency resolution using the Visualization Reporter

    main

    The Visualization Reporter allows you to visualize how the resolution algorithm explores the dependency graph. There are two primary workflows for using this reporter:

    1. Record and Playback Workflow

    This method is used to 'record' a resolution run to a file and then 'play it back' later to generate an HTML visualization. This is useful for analyzing specific resolution runs after they have completed.

    1. Run the demo script and redirect its output to a text file: python reporter_demo.py > foo.txt
    2. Use the visualization runner to generate the HTML file: python visualization/run.py foo.txt out.html

    2. Real-time Generation Workflow

    This method demonstrates how to generate a visualization directly while the resolver is running. This is typically achieved by integrating the reporter into the resolver execution loop (e.g., using run_pypi.py).

    1. Run the PyPI example script: python visualization/run_pypi.py out.html

    Note: This implementation is intended as a demonstration of the resolvelib Reporter API and may not be suitable for production use or very large dependency graphs.

    # Record and Playback
$ python reporter_demo.py > foo.txt
$ python visualization/run.py foo.txt out.html

# Real-time Generation
$ python visualization/run_pypi.py out.html

  5. Set up a development environment for ResolveLib

    main

    To start contributing to ResolveLib, fork the repository, install the package with its test dependencies, and run the test suite to ensure everything is working correctly.

    1. Install the package including the [test] extra: python -m pip install .[test]

    2. Run the tests using pytest: python -m pytest

    python -m pip install .[test]

python -m pytest

  6. Understand the Result structure

    main

    The Result object is a NamedTuple that encapsulates the outcome of a resolution process. It is generic over the Requirement type (RT), Candidate type (CT), and Key type (KT).

    It contains three essential components:

    1. mapping: A dict[KT, CT] containing the final resolved candidates. The keys are the identifiers for the packages/entities, and the values are the actual resolved candidates.
    2. graph: A DirectedGraph[KT | None] representing the dependency structure discovered during resolution.
    3. criteria: A dict[KT, Criterion[RT, CT]] mapping identifiers to the criteria used to resolve them.

  7. Understand the Result object structure

    main

    The Result object returned by a successful resolution contains three primary components:

    1. mapping: A dictionary where each key is a unique identifier for a requirement (obtained via the provider's identify method) and the value is the resolved candidate.
    2. graph: A DirectedGraph representing the dependency tree. Vertices are identifiers from the mapping. A special vertex None acts as the root, representing the parents of the initial user-supplied requirements.
    3. criteria: A dictionary mapping identifiers to Criterion instances. These provide detailed metadata on how the edges in the dependency graph were derived.

  8. Optimize resolution with narrow_requirement_selection

    main

    If your get_preference method performs expensive checks (e.g., $O(n)$ operations where $n$ is the number of identifiers), you should implement narrow_requirement_selection to optimize the resolution process.

    get_preference is called $O(n)$ times per backtrack step. In contrast, narrow_requirement_selection is called only $O(1)$ times per backtrack step. By filtering the list of identifiers in narrow_requirement_selection, you reduce the number of times the expensive get_preference logic is executed.

    Requirements for implementation:

    • It must return a non-empty subset of the input identifiers.
    • If it returns exactly one identifier, the resolver skips the get_preference call for that step and uses that identifier directly.
    • The default implementation returns the identifiers unchanged.

  9. Understand resolution state and requirement info

    main

    The library uses specific data structures to track the state of the resolution process:

    • RequirementInformation[RT, CT]: A NamedTuple that pairs a requirement with its parent (the candidate that required it). This is used to track the lineage of requirements during backtracking.
    • State[RT, CT, KT]: A NamedTuple representing the resolution state in a specific round. It contains:
      • mapping: A dictionary mapping identifiers (KT) to candidates (CT).
      • criteria: A dictionary mapping identifiers to Criterion objects.
      • backtrack_causes: A list of RequirementInformation objects used to identify why the resolver needs to backtrack.

  10. Use the Resolver to perform dependency resolution

    main

    To resolve a set of requirements, implement or use a Resolver class. The resolve method takes a collection of requirements and a maximum number of rounds to attempt resolution. It returns a Result object containing the successful mapping, the dependency graph, and the criteria used.

    # Assuming 'resolver' is an instance of Resolver
# and 'requirements' is an iterable of requirement objects
result = resolver.resolve(requirements=requirements, max_rounds=100)

# Accessing the result
mapping = result.mapping      # Dict of {identifier: resolved_candidate}
graph = result.graph         # DirectedGraph of the dependency tree
criteria = result.criteria    # Dict of {identifier: Criterion}

  11. Implement a custom BaseReporter to monitor resolution progress

    main

    To hook into the resolution process and report progress (e.g., for logging, UI updates, or debugging), you can subclass BaseReporter. The BaseReporter class provides several lifecycle hooks that are called at different stages of the resolution algorithm.

    When implementing a reporter, you can override the following methods:

    • starting(): Triggered before resolution begins.
    • starting_round(index: int): Triggered before each resolution round starts (zero-based index).
    • ending_round(index: int, state: State[RT, CT, KT]): Triggered before a round ends. Note: This is not called if the resolution finishes during this round.
    • ending(state: State[RT, CT, KT]): Triggered when resolution completes successfully.
    • adding_requirement(requirement: RT, parent: CT | None): Triggered when a new requirement is added to the criteria. parent is the candidate requiring this dependency, or None if it is a root requirement.
    • resolving_conflicts(causes: Collection[RequirementInformation[RT, CT]]): Triggered when the resolver starts attempting to resolve requirement conflicts (backtracking).
    • rejecting_candidate(criterion: Criterion[RT, CT], candidate: CT): Triggered when a candidate is rejected during backtracking.
    • pinning(candidate: CT): Triggered when a candidate is added to the potential solution.
    from resolvelib.reporters import BaseReporter

class MyProgressReporter(BaseReporter[RT, CT, KT]):
    def starting(self) -> None:
        print("Starting resolution...")

    def adding_requirement(self, requirement: RT, parent: CT | None) -> None:
        print(f"Adding requirement: {requirement}")

    def pinning(self, candidate: CT) -> None:
        print(f"Pinned candidate: {candidate}")

  12. Handle recursion depth limits with ResolutionTooDeep

    main

    If the resolution process exceeds the allowed depth (often to prevent infinite loops in complex dependency graphs), a ResolutionTooDeep exception is raised. It includes a round_count attribute indicating the number of rounds performed before the limit was hit.

    try:
    # ... resolution logic ...
    pass
except ResolutionTooDeep as e:
    print(f"Resolution failed: exceeded {e.round_count} rounds")