Module ammcore.pkg.resolver

Resolves dependencies.

Index

Function

resolve()

Find suitable package versions to satisfy the given requirements.

Function

ammcore.pkg.resolver.resolve(rootRequirements: table<string, ammcore.pkg.version.VersionSpec>, provider: ammcore.pkg.provider.Provider, updateAll: boolean, includeRemotePackages: boolean) → solution: ammcore.pkg.package.PackageVersion[]

Find suitable package versions to satisfy the given requirements.

Resolving package versions is an NP-complete task. This implementation is inspired by the NuGet package manager.

Essentially, this algorithm performs a full search using DFS-like approach, with some heuristics to speed it up.

On every step of an algorithm, we have a stack of package candidates that we will install, each candidate has a specific version pinned.

To make a step, we select the next package candidate that needs to be installed, and try pinning one of its versions.

If new pinned version doesn’t conflict with other pinned candidates, we descend and try selecting the next candidate, and so on.

If no version could be pinned without creating a conflict with other pinned candidates, it means we can’t find a solution with current pins. In this case, we backtrack to the previously selected package candidate, unpin its version and pin the next one.

We continue until either there is no more candidates to install, or we’ve backtracked to the end of the stack.

Heuristics to speed up this process include selecting a candidate that will narrow down our search the most, and selecting order in which to try versions of a candidate.

When selecting an uninstalled candidate, we consider the following factors:

  • we prefer packages that are included in rootRequirements;

  • we prefer packages that have an exact version required (version range narrowed by a == spec);

  • we track how many conflicts we’ve discovered while attempting to pin a candidate during previous iterations, and prefer ones that produce higher number of conflicts.

Parameters:

  • rootRequirements (table<string, ammcore.pkg.version.VersionSpec>) – initial requirements to be considered.

  • provider (ammcore.pkg.provider.Provider) – where to find packages.

  • updateAll (boolean) – update local packages even if current versions don’t conflict with requirements.

  • includeRemotePackages (boolean) – allow package to fetch packages from github or other remote source.

Returns:

solution (ammcore.pkg.package.PackageVersion[]) – package versions that satisfy requirements.