Package Managers

The previous lesson’s measurement chose every package independently from its own range; the choices never looked at one another. That assumption made the table readable, but left out a fact: installed packages carry their own declarations too, and those can contradict each other.

This lesson puts those constraints into the table. Its question has two layers: what sets does the same declaration give once package requirements are also taken into account, and where does it become visible when a strategy picks an inconsistent set? The second half of the answer will turn out to matter more than the first.

What a Package Manager Does

A package manager is the name of a tool class, and this course writes no product name; its behavior is modeled here. Its work splits into four steps: read the declaration, gather candidate versions from the registry, choose a set among the candidates, install the chosen set to the site. This lesson’s concern is the third step.

Where the fourth step writes was established in the first lesson: on an isolated site, installation changes only what that project sees; on a shared site, it also changes what neighbors see. This lesson assumes the site is isolated and does not return to that axis again; every distinct outcome here is born inside a single site.

The third step alone has a name: resolution. Its input is a list of ranges and a pool of candidates; its output is one exact version per package. What stands in between is the package manager’s resolution strategy, and as the previous lesson showed, that strategy is not written in the declaration.

What a version number’s parts mean, and meaningful versioning, were established in the Introduction to Version Control course’s tagging lesson; not repeated here. The question here is not what a version number says, it is what sets the ranges together make possible.

The Requirement Table and Consistency

A single addition is made to the rig: a requirement table. The table writes which range each package version wants from which package. The registry and the project’s declaration come from the shared definition unchanged; what is added is the packages’ own requirements.

The tension the table sets up in the rig reads in one sentence: metrics’s newer versions want common’s newer versions, while report’s newer version wants common’s older versions. An install requesting both at their newest ends up wanting two separate things for common at once.

This is where the measurement’s second concept is born. A set is consistent if and only if every chosen version’s requirement is met by the other choices in the set. Consistency is not the same thing as installation succeeding: an inconsistent set can still be installed to the site, because installation is a file write and is not required to read the requirement table.

Four Strategies

The measurement compares four strategies. The first two are independent pickers: each takes a package from one end of its own range and never looks at the requirement table — these are the previous lesson’s two strategies. The remaining two are backtracking: they choose a version, test the constraints, back off when it does not hold, and try another version.

The two backtracking strategies differ only in search order: which package’s version gets decided first. Same declaration, same requirement table, same registry — the only thing that changes is the order. This difference is going to produce the measurement’s most important row.

The measurement’s assumptions:

• ED24 — The registry, declaration, and range rule are taken from the shared definition unchanged; the lesson does not change either’s behavior. The only addition is the requirement table.
• ED25 — The requirement table is part of the rig and part of the oracle: we wrote which version wants what, so every set’s consistency is known without measuring.
• ED26 — A package version carries at most one requirement, and a requirement is a range. The chain’s depth is one level; deeper chains would grow the number, not change the rule.
• ED27 — Independent strategies do not read the requirement table. The set they build can be inconsistent, and installation still completes.
• ED28 — Backtracking tries candidates for every package in the search order, following the strategy’s direction, and tests the partial set at every step. It returns the first consistent complete set.
• ED29 — Testing a partial set checks only requirements whose both ends are already chosen; a requirement whose target is not yet chosen does not count as violated at that step.
• ED30 — Two search orders are tried: metrics, common, report and report, common, metrics. Order is a configuration detail; the project does not write it in the declaration.
• ED31 — The tight requirement table is derived on the same registry by having all of metrics’s eligible versions want common’s newest version, and all of report’s eligible versions want an older one. It models a declaration set whose intersection is empty.
• ED32 — When no solution is found, backtracking returns None, and this is not an error, it is a measurement result: the consistent-set count is zero.
• ED33 — The lock is a copy of one of the consistent sets — the backtracking newest strategy’s result. Resolution is not called while a lock exists.
• ED34 — Version numbers are the rig packages’ fictional versions.
• ED35 — No real installation is performed, no real package is downloaded; resolution returns a dict.
• ED36 — Duration is not measured. What is counted is the distinct set, the distinct consistent set, and the distinct outcome the locked install gives.

Measurement

"""Resolution strategies: same declaration, separate set; what happens when conflict arises."""

REGISTRY = {
    "metrics": [(1, 0), (1, 1), (1, 2), (2, 0)],
    "report": [(0, 9), (1, 0), (1, 1)],
    "common": [(3, 0), (3, 1), (3, 2), (4, 0)],
}
DECLARATION = {"metrics": ((1, 0), (2, 0)), "report": ((1, 0), (2, 0)),
               "common": ((3, 0), (4, 0))}
PACKAGES = ("metrics", "common", "report")

# Packages' own dependencies: version -> (target package, lo, hi)
REQUIREMENT = {
    ("metrics", (1, 0)): ("common", (3, 0), (4, 0)),
    ("metrics", (1, 1)): ("common", (3, 1), (4, 0)),
    ("metrics", (1, 2)): ("common", (3, 2), (4, 0)),
    ("report", (0, 9)): ("common", (3, 0), (3, 1)),
    ("report", (1, 0)): ("common", (3, 0), (4, 0)),
    ("report", (1, 1)): ("common", (3, 0), (3, 2)),
}
# Same registry, a tighter requirement table: all three metrics versions want a newer common.
TIGHT = dict(REQUIREMENT)
TIGHT[("metrics", (1, 0))] = ("common", (3, 2), (4, 0))
TIGHT[("metrics", (1, 1))] = ("common", (3, 2), (4, 0))
TIGHT[("report", (1, 0))] = ("common", (3, 0), (3, 2))


def eligible(package):
    lo, hi = DECLARATION[package]
    return [s for s in REGISTRY[package] if lo <= s < hi]


def resolve(strategy="newest"):
    """Independent choice: each package taken from one end of its own range."""
    chosen = {}
    for package in sorted(DECLARATION):
        candidates = eligible(package)
        chosen[package] = candidates[-1] if strategy == "newest" else candidates[0]
    return chosen


def consistent(chosen, requirement):
    """Do the chosen versions' requirements get met by the other chosen packages."""
    for package, version in chosen.items():
        r = requirement.get((package, version))
        if r is None:
            continue
        target, lo, hi = r
        if target in chosen and not lo <= chosen[target] < hi:
            return False
    return True


def backtrack(order, requirement, strategy="newest"):
    """When a conflict arises, back off and try another version; order is the search order."""
    def advance(i, chosen):
        if i == len(order):
            return dict(chosen)
        package = order[i]
        candidates = eligible(package)
        if strategy == "newest":
            candidates = candidates[::-1]
        for version in candidates:
            chosen[package] = version
            if consistent(chosen, requirement):
                result = advance(i + 1, chosen)
                if result is not None:
                    return result
            del chosen[package]
        return None
    return advance(0, {})


def format_selection(chosen):
    if chosen is None:
        return f"{'no solution':>23s}"
    return " ".join(f"{'.'.join(map(str, chosen[p])):>7s}" for p in PACKAGES)


def install(lock_file, func, requirement):
    """If a lock exists, no resolution runs; otherwise the strategy decides."""
    return dict(lock_file) if lock_file else func(requirement)


STRATEGIES = (
    ("independent, newest", lambda g: resolve("newest")),
    ("independent, oldest", lambda g: resolve("oldest")),
    ("backtracking, newest", lambda g: backtrack(("metrics", "common", "report"), g)),
    ("backtracking, report first", lambda g: backtrack(("report", "common", "metrics"), g)),
)


def table(heading, requirement):
    print(f"{heading:<26s} {'metrics':>7s} {'common':>7s} {'report':>7s}  consistent")
    sets, sound = [], []
    for name, func in STRATEGIES:
        chosen = func(requirement)
        status = chosen is not None and consistent(chosen, requirement)
        if chosen is not None:
            sets.append(tuple(sorted(chosen.items())))
            if status:
                sound.append(tuple(sorted(chosen.items())))
        print(f"{name:<26s} {format_selection(chosen)}  {'yes' if status else 'no':>7s}")
    print(f"four strategies: {len(set(sets))} distinct sets, "
          f"{len(set(sound))} distinct consistent sets")


table("requirement table", REQUIREMENT)
print()
table("tight requirement table", TIGHT)
print()
lock_file = backtrack(("metrics", "common", "report"), REQUIREMENT)
locked = {tuple(sorted(install(lock_file, func, REQUIREMENT).items()))
          for _, func in STRATEGIES}
print("set written to the lock:  " + format_selection(lock_file))
print(f"with the lock file, four strategies: {len(locked)} distinct set")

requirement table          metrics  common  report  consistent
independent, newest            1.2     3.2     1.1       no
independent, oldest            1.0     3.0     1.0      yes
backtracking, newest           1.2     3.2     1.0      yes
backtracking, report first     1.1     3.1     1.1      yes
four strategies: 4 distinct sets, 3 distinct consistent sets

tight requirement table    metrics  common  report  consistent
independent, newest            1.2     3.2     1.1       no
independent, oldest            1.0     3.0     1.0       no
backtracking, newest                   no solution       no
backtracking, report first             no solution       no
four strategies: 2 distinct sets, 0 distinct consistent sets

set written to the lock:      1.2     3.2     1.0
with the lock file, four strategies: 1 distinct set

Four Strategies, Four Sets

The top table’s four rows give 4 distinct sets, all from the same declaration. This adds two more to the previous lesson’s two sets; the two added are sets independent choice could never reach.

The first row is this lesson’s real finding. The independent newest strategy chooses the set 1.2 / 3.2 / 1.1, and this set is inconsistent: report 1.1 wants an older version than 3.2 for common, but the set holds common 3.2. Even so, the install completes. No error message is raised, because the independent strategy never read the requirement table. The result is three packages sitting on the site that do not want each other.

The second row shows independent oldest happening to build a consistent set. The word “happening” is exactly right here: the strategy still did not read the requirement table, it is only that the ranges’ lower ends did not clash. The same strategy would build an inconsistent set with a different table — and indeed it does, in the table below.

The last two rows give the backtracking strategies, and both are consistent, but separate: 1.2 / 3.2 / 1.0 versus 1.1 / 3.1 / 1.1. The only difference between them is search order — which package’s version gets decided first. Same declaration, same registry, same constraints; still two separate, legitimate installs. This row says the resolver itself is a distinct-outcome axis: changing the tool can change the install without changing the declaration.

Total: four strategies, 4 distinct sets, 3 of which are consistent.

Where Does a Conflict Get Written

The bottom table tightens the constraints: in this table, all of metrics’s eligible versions want common’s newest, and all of report‘s eligible versions want an older one. The two requests’ intersection is empty.

Both backtracking strategies return no solution. The consistent-set count is 0. This looks like a failure, and in one sense it is — but the measurement’s real finding sits in the two rows above it: the independent strategies still return a set. The same contradiction produces either a rejection or a silent install, depending on which tool reads it.

The difference between the two is where the error surfaces. A rejection surfaces at resolution time and leaves information behind: this set of declarations is contradictory, either a range has to be loosened or a package changed. A silent install leaves nothing behind; the contradiction gets installed to the site and only surfaces at run time, on the line where the two conflicting packages meet. And that line is not hit on every run.

In the measure’s own language: rejection produces 0 distinct outcomes, and zero is a countable answer. A silent install produces 1 distinct outcome, but does not measure whether that outcome is valid. A resolver saying it could not solve something is, information-wise, superior to one that does not say so.

Is the Resolver Itself Reproducible

The measurement compared four strategies, but it is also worth asking how many outcomes each strategy gives on its own. All four of the model’s strategies are deterministic: the candidate list comes from the registry in order, the search order is fixed, there is no randomness anywhere. The same strategy called with the same input gives 1 distinct outcome.

This is the most basic property to ask of a resolver, and it does not come for free. If the candidate pool is gathered from more than one source, which source answers first can slip into the order; if a cache warms up, the same query can return a separate list; parallel downloads can change install order. None of these change the strategy’s rule, but all of them change its input — and a rule whose input changes gives a separate set.

A resolver’s word is therefore two-layered. The first layer is the rule: which candidate gets chosen. The second layer is the rule’s input: in what order, from what source, and at what moment the candidates were gathered. A reproducible install requires fixing both, and the document writing down the second layer is the lock file.

The Lock’s Place in This Table

The last two lines put the previous lesson’s result on top of this table. When one of the consistent sets — the one the backtracking newest strategy found, 1.2 / 3.2 / 1.0 — is written to the lock, all four strategies install the same set: 1 distinct outcome.

The axis the lock closes here is a new one. What was closed in the previous lesson was strategy direction and the registry’s time; what is closed here is the resolver itself. Once the lock is written, which package manager is used no longer changes the outcome, because there is nothing left to resolve.

This also bounds how much work the lock does. The lock carries the decision of whichever resolver produced it, with equal fidelity for a good decision or a bad one. Which of the three consistent sets in the table above got written to the lock cannot be told by looking at the lock — the lock writes only what was chosen, not why it was chosen.

Summary

• A package manager is a tool class; its work is reading the declaration, gathering candidates, choosing a set, and installing it. The step producing a distinct outcome is the choosing step.
• Once packages’ own requirements are taken into account, the same declaration gives 4 distinct sets under four strategies, and 3 of them are consistent.
• Independent choice does not read the requirement table: the set 1.2 / 3.2 / 1.1 installs despite being inconsistent, and raises no warning.
• The two backtracking strategies give two separate consistent sets because of separate search order; the resolver itself is a distinct-outcome axis.
• Under constraints with an empty intersection, backtracking returns 0 consistent sets; rejection leaves information at resolution time, a silent install defers the contradiction to run time.
• A lock file brings four strategies down to 1 distinct outcome, but does not carry the reasoning behind the decision it writes.

Next Step

Every set in this lesson was comparable because a single interpreter was assumed. That assumption, like the previous two, was not written down either. The next lesson puts it into the measurement: same project, same declaration, separate interpreter versions. What is going to be asked is — how many distinct sets does resolution give depending on the interpreter, and what does a lock file produced on one interpreter do on another?