Require all packages to solve / compile and include all valid compilers in their metadata

[thomashoneyman]

Fixes #577. Fixes #255.

The core problem solved here is identifying what compilers are compatible with a specific package version, such as aff@7.0.0. We need this to support an oft-requested feature for Pursuit: filtering search results by a compiler version (or range). It's also useful for other things; for one, it allows us to add the compiler version as a constraint to the solver to produce a build plan that works with the specific compiler given.

Metadata files now include a compilers key in published metadata that lists either a bare version (the version used to publish the package) or an array of versions (the full set of compilers known to work with the package). The reason for two representations is that computing the full set of compilers can take a long time; this approach lets us upload the package right away and compute the rest of the valid compilers in a fixup pass. A bare version means the full set has not been computed yet.

All packages must now be solvable. We can't compile a package version if we can't fetch its dependencies, so this becomes a requirement for all packages.

There are only 2 scenarios in which we need to compute the available compilers for a package version:

1. A new package version is published
2. A new compiler version is published

This PR is focused on the first case, and we should do a followup for the second case. (The second case is straightforward, and @colinwahl's compiler versions script already essentially implements it. It's been omitted from this PR for brevity).

A new package version can be published via the legacy importer or via a user submitting an API call, but the result is the same: eventually the publish pipeline is run. For that reason I've decided to compute the compiler versions for a package version as part of the publish pipeline where we're already determining resolutions and building with a specific compiler. That centralizes the logic to a single place.

Therefore this PR centers on two things: trying compilers to find all that work for a package version at the end of publishing, and updating the legacy importer to determine a valid compiler version and resolutions before calling publish.

I've added some tests and I've run the legacy importer locally; it's about 500 packages in so far and every failure appears to be correct. More comments in the PR.

[thomashoneyman]

An example from the publish-failures.json file:

{
  "string-parsers": {
    "3.0.1": {
      "reason": "No versions found in the registry for lists in range\n  >=4.0.0 (declared dependency)\n  <5.0.0 (declared dependency)",
      "tag": "SolveFailed"
    },
    "3.1.0": {
      "reason": "No versions found in the registry for lists in range\n  >=4.0.0 (declared dependency)\n  <5.0.0 (declared dependency)",
      "tag": "SolveFailed"
    }
  },
}

[thomashoneyman]

I've uncovered two rare but significant issues affecting the legacy importer (unrelated to this PR).

Topological sorting First: in some cases our typical approach of topologically sorting manifests by their dependencies (ignoring their explicit bounds) will fail to read a valid index from disk. This happens when a package like functors at one time depends on another (like contravariant), but at other times the dependency is flipped. Since we don't take specific version ranges into consideration, we're at the mercy of other conflicting sorting orders in the map as to whether these end up going in the right order or not. Here's the output of a failed run reading an index from disk:

success: 'Inserted distributive@5.0.0'
success: 'Inserted exists@5.1.0'
success: 'Inserted exists@5.0.0'
success: 'Inserted profunctor@5.0.0'
fail: 'Failed to insert functors@4.1.1: \n  - contravariant>=5.0.0 <6.0.0'
success: 'Inserted functors@3.1.1'
success: 'Inserted functors@3.1.0'
success: 'Inserted functors@3.0.1'
success: 'Inserted functors@3.0.0'
success: 'Inserted foldable-traversable@5.0.0'
success: 'Inserted either@4.1.0'
success: 'Inserted foldable-traversable@5.0.1'
success: 'Inserted either@4.1.1'
success: 'Inserted contravariant@4.0.1'
success: 'Inserted const@4.0.0'
success: 'Inserted contravariant@5.0.0'

This run fails to produce a valid index because functors@4.1.1 is unsatisfied in its dependency on contravariant, but of course we see contravariant get inserted a little later on.

The solution is to always consider version bounds when reading an index from disk where we expect bounds to be at least reasonably correct. I've implemented and tested that and situations like this no longer happen.

The reason we ignored ranges at first is because we had far fewer checks around correct bounds and because in the package sets we want to explicitly ignore ranges when working with an index (when doing, for example, the 'self-contained' check). I've preserved that behavior — you can always opt-in to either considering or ignoring ranges when working with an index.

Incorrect dependencies detected in legacy manifests derived from package sets

Second, in some cases a package like strings@3.5.0 will have its dependency list pruned to only those listed in its package sets entry, and those turn out to be overly-restrictive. In this case, specifically, the dependency on purescript-integers listed in its Bowerfile is removed because there is no such dependency in its package sets list; in the package sets that dependency ended up being picked up transitively, but when we go to solve and compile the package the solution picks a different transitive dependency and the package fails.

This shouldn't happen because strings@3.5.0 has a Bowerfile that explicitly lists a dependency on integers, which we trimmed out by deferring to the package sets entry. We did this assuming package sets entries are correct and because we didn't want overly-constrained dependency lists.

The second concern is no longer valid because with #667 we will remove unused dependencies. The first concern is no longer reasonable because we have at least one example of package sets dependency lists being incorrect.

The solution is simple: instead of preferring package sets entries over other manifests, just union them all and defer to the 'unused dependencies' pruning in the publishing pipeline to trim out ones that aren't actually needed.

[thomashoneyman]

Can confirm that the fix is working with regards to generating manifests with full dependency lists to be pruned later — this is strings@3.5.0, for example:

{
  "name": "strings",
  "version": "3.5.0",
  "license": "MIT",
  "description": "String and char utility functions, regular expressions.",
  "location": {
    "githubOwner": "purescript",
    "githubRepo": "purescript-strings"
  },
  "dependencies": {
    "arrays": ">=4.0.1 <5.0.0",
    "either": ">=3.0.0 <4.0.0",
    "gen": ">=1.1.0 <2.0.0",
    "integers": ">=3.2.0 <4.0.0",
    "maybe": ">=3.0.0 <4.0.0",
    "partial": ">=1.2.0 <2.0.0",
    "unfoldable": ">=3.0.0 <4.0.0"
  }
}

...and the manifest index sorting is working as far as I can tell as well.

[thomashoneyman]

We also need to support spago.yaml files in the legacy importer, as some packages now use that format. Otherwise they will be excluded with a NoManifests error.

[thomashoneyman]

Here's another fun one: some packages, like transformers@3.6.0, list dependencies which are entirely unused, in this case arrays. We then prune this dependency. However, then the package fails because it brings in other dependencies via that transitive dependency, such as either.

That means we can't get away with simply removing unused dependencies because we may also remove direct imports that were pulled in transitively by the unused dependency. Either we give up on removing unused dependencies, or we both remove unused dependencies and insert direct imports that weren't mentioned.

For dependencies we insert into a manifest we have their exact version via the solver; we could potentially do a bumpHighest on them to produce a range the same way we do when working with spago.dhall files.

I think that's preferable to giving up on the unused dependencies check but I'm curious if you disagree @f-f or @colinwahl.

[thomashoneyman]

As of the latest commit: we no longer simply remove unused dependencies. Instead, we loop. We remove unused dependencies, then bring in any transitive dependencies they would have brought in, and then check the new dependency list for unused dependencies and so on.

The result is that we remove unused dependencies while preserving any transitive dependencies they brought it which are used in the source code. Note that we don't go through and add all packages your code directly imports, we just do this for dependencies that are being removed.

[thomashoneyman]

@f-f this is ready for a look. In my test run I'm thousands of package versions in and everything looks good. Packages are building and we're recording the full set of compiler versions for them. Solver and compilation failures look correct. We're pruning unused dependencies from packages that list them (replacing the removed deps with their transitives and pruning again).

I took a stab at automatically adding directly-imported packages to the manifest of packages that don't list them, but it's funky. We can't be sure we're accurately reflecting the ranges they intended. I can cover most cases but I don't at all feel confident I can catch them all. It's not technically incorrect for a user to omit packages they directly import from their manifest if they get brought in transitively, and unlike the "unused dependency" check we put in place they're not going to pull in random test and dev dependencies.

Anyways — at this point the legacy importer and publish pipeline are solving and compiling packages as they publish and I think this is good to go. I'll share the full publish failure stats when I have a completed run of the importer.

[thomashoneyman]

Pending review we can move forward with reimporting the registry either this weekend or next weekend. During that period of time it will be necessary to disable package publishing so no interruptions happen.

[thomashoneyman]

Output of the test run:

----------
IMPORT STATS
----------

1750 packages processed:
  1053 fully successful
  387 partially successful
  124 omitted (no usable versions)
  184 fully failed
  ---
  175 Cannot Access Repo
  5 Disabled Package
  2 Package URL Redirects
  1 Invalid Package URL
  1 Invalid Package Name

12967 versions processed:
  10686 successful
  2281 failed
  ---
  706 Unregistered Dependencies
  684 Invalid Manifest (Invalid Dependencies)
  462 Invalid Manifest (Missing License)
  345 Invalid Tag
  72 Invalid Manifest (No Manifests)
  8 Invalid Manifest (Invalid License)
  4 Disabled Version

--------------------
PUBLISH FAILURES
--------------------

1440 packages processed:
  - 1222 out of 1440 had at least 1 version fail 
  - 755 packages have zero usable versions

10686 versions processed:
  - 8388 out of 10686 failed
  ---
  - Publishing failed: 25
  - Solving failed (compiler): 473
  - No compilers usable for publishing: 538
  - Solving failed (dependencies): 7352

Here is the full list of failures — the vast majority are because of missing dependencies, ie. the package refers to some package version at a range that doesn't exist, and that's because many package versions are very old.

publish-failures.json

In addition, here is the full list of packages that had no usable versions at all and will be removed and their names released for others to register:

removed-packages.txt

[thomashoneyman]

It looks like some of these failures are because I had cached failures from my many, many test runs of the script. I have fully cleared the cache and am re-running from scratch and should be able to report the results tomorrow. Already I can see a good number of additional packages succeeding.

[thomashoneyman]

Results of the run without any cached errors — significant increase in the number of package versions kept, but still many packages without usable versions.

--------------------
PUBLISH FAILURES
--------------------

997 out of 1440 packages had at least 1 version fail (515 packages had all versions fail).
6470 out of 10691 versions failed.
  - Publishing failed: 29
  - Solving failed (compiler): 100
  - No compilers usable for publishing: 628
  - Solving failed (dependencies): 5713

These are all of the failures:

publish-failures.json

These are the packages without any usable versions:

removed-packages.txt

These are the successes (the metadata directory after all packages are solved and compiled):

metadata.zip

It would be a huge help if folks can cross-check the removals / failures / successes and see if anything stands out as odd.

[thomashoneyman]

Encountered another issue: sometimes we remove an unused dependency (as per #667) from a package (for example, we remove record as a dependency from variant@8.0.0) but this causes a failure in another package because that one was bringing in the dependency transitively (for example, codec-argonaut@9.2.0 uses record and was bringing it in transitively via variant).

In short, we can't just remove unused dependencies and insert any transitive dependencies that were being brought in by the unused package as described in https://github.com/purescript/registry-dev/pull/669/#issuecomment-1817062736. Some other package downstream may have been relying on the transitive dependencies.

We either have to:

1. Give up on pruning unused dependencies and have a policy that we accept transitive dependencies (and we should be clear that removing a dependency = a breaking change, even if the dependency was unused, because other packages may be relying on it)
2. Fix manifests not just by removing unused dependencies and inserting anything they brought in transitively, but by inserting all directly-imported packages as dependencies in the manifest.

For (2) I have not yet come up with a robust method. However, @natefaubion suggested in the PureScript chat that we could:

• Take the transitive dependencies of the untrimmed dependencies
• Take the transitive dependencies of the trimmed dependencies
• See what the diff is and add the discovered transitive dependency

[thomashoneyman]

In this latest iteration I add support for inserting transitive dependencies as well as removing unused ones. This relies on keeping the untrimmed legacy manifests in a TransitivizedRegistry so we can use it for solving when discovering missing package ranges. Here's how we solve:

1. First we solve the untrimmed manifest using solveSteps on the legacy registry. This produces ranges for the manifest dependencies (and their dependencies) up to the point where the solver would have to make a commitment, and then it halts.
2. We look up the missing packages in the solveSteps result and take their ranges.
3. Then, we solve the untrimmed manifest again with solveFull. This produces exact versions for every dependency and transitive dependency in the manifest.
4. We iterate through every resolution's untrimmed manifest; if we see any of the remaining missing packages in its dependencies then we update the missing package's range.

The result is that most ranges are produced by the solver via solveSteps, which is more likely to be correct since it considers all the ranges that could be possible in a solution. However, some ranges will still be missing so we take the remaining ranges from the legacy resolutions' manifests.

The results seem good so far. For example, enums@3.1.0 uses both sources of ranges:

[2023-12-07T12:32:29.552Z INFO] Found fixable dependency errors: Missing dependencies (control, gen, maybe, newtype, nonempty, partial, prelude, tuples)

Let's fix these. We produce legacy resolutions for the package:

[2023-12-07T12:32:29.674Z DEBUG] Got legacy resolutions:
{
  "arrays": "4.4.0",
  "bifunctors": "3.0.0",
  "control": "3.3.1",
  "distributive": "3.0.0",
  "eff": "3.2.3",
  "either": "3.2.0",
  "foldable-traversable": "3.7.1",
  "gen": "1.3.1",
  "globals": "3.0.0",
  "identity": "3.1.0",
  "integers": "3.2.0",
  "invariant": "3.0.0",
  "math": "2.1.1",
  "maybe": "3.1.0",
  "monoid": "3.3.1",
  "newtype": "2.0.0",
  "nonempty": "4.3.0",
  "partial": "1.2.1",
  "prelude": "3.3.0",
  "st": "3.0.0",
  "strings": "3.5.0",
  "tailrec": "3.3.0",
  "tuples": "4.1.0",
  "type-equality": "2.1.0",
  "unfoldable": "3.2.0",
  "unsafe-coerce": "3.0.0"
}

Then we take a look at the transitive solution (ie. using the transitivized registry)

[2023-12-07T12:32:29.772Z DEBUG] Got transitive solution:
{
  "bifunctors": ">=3.0.0 <4.0.0",
  "control": ">=3.0.0 <4.0.0",
  "either": ">=3.0.0 <4.0.0",
  "foldable-traversable": ">=3.0.0 <4.0.0",
  "invariant": ">=3.0.0 <4.0.0",
  "maybe": ">=3.0.0 <4.0.0",
  "monoid": ">=3.0.0 <4.0.0",
  "newtype": ">=2.0.0 <3.0.0",
  "partial": ">=1.2.0 <2.0.0",
  "prelude": ">=3.0.0 <4.0.0",
  "strings": ">=3.0.0 <4.0.0",
  "tuples": ">=4.0.0 <5.0.0",
  "unfoldable": ">=3.0.0 <4.0.0"
}

We're able to get most package ranges from here, but some are missing in this solution (gen and nonempty). So we continue, this time taking the ranges by looking at every package in the legacy resolutions to see if gen and nonempty are listed in their ranges, and produce the following result:

[2023-12-07T12:32:29.804Z INFO] [NOTIFY] Your package is using a legacy manifest format, so we have adjusted your dependencies to remove unused ones and add direct-imported ones. Your dependency list was:
{
  "either": ">=3.0.0 <4.0.0",
  "strings": ">=3.0.0 <4.0.0",
  "unfoldable": ">=3.0.0 <4.0.0"
}

We have added the following packages: control, gen, maybe, newtype, nonempty, partial, prelude, tuples

Your new dependency list is:
{
  "control": ">=3.0.0 <4.0.0",
  "either": ">=3.0.0 <4.0.0",
  "gen": ">=1.1.0 <2.0.0",
  "maybe": ">=3.0.0 <4.0.0",
  "newtype": ">=2.0.0 <3.0.0",
  "nonempty": ">=4.2.0 <5.0.0",
  "partial": ">=1.2.0 <2.0.0",
  "prelude": ">=3.0.0 <4.0.0",
  "strings": ">=3.0.0 <4.0.0",
  "tuples": ">=4.0.0 <5.0.0",
  "unfoldable": ">=3.0.0 <4.0.0"
}

So we get "gen": ">=1.1.0 <2.0.0" and "nonempty": ">=4.2.0 <5.0.0", which is probably a little restrictive (maybe if we'd had other resolutions we would have had gen: >=1.0.0 <2.0.0) but I think it's pretty harmless.

[thomashoneyman]

Results of the run now that we fix dependencies in general:

--------------------
PUBLISH FAILURES
--------------------

999 out of 1443 packages had at least 1 version fail (516 packages had all versions fail).
6471 out of 10695 versions failed.

  - Publishing failed: 22
  - Solving failed (compiler): 104
  - No compilers usable for publishing: 628
  - Solving failed (dependencies): 5717

• Full list of publish failures with reasons: publish-failures.json
• Packages that had no successful versions: removed-packages.txt
• Metadata produced by this run, with compilers associated: metadata.zip
• Manifest index produced by this run, with dependencies all fixed: registry-index.zip

[thomashoneyman]

Some packages (notably codec-argonaut and codec-json, but others as well) were failing before we ever discovered a compiler to attempt publishing with because we attempted to solve and compile them with the current index. To fix them we have to solve with both the legacy and current indices and try both; we bail out early if either solution contains packages not in the current index.

New results:

--------------------
PUBLISH FAILURES
--------------------

983 out of 1443 packages had at least 1 version fail (507 packages had all versions fail or 35%)
6359 out of 10695 versions failed or 59%

  - Dependency compiler conflict: 1
  - Publishing failed: 92
  - No compilers usable for publishing: 567
  - Solving failed (dependencies): 5699

As usual here are the relevant files:

• Full list of publish failures with reasons: publish-failures.json
• Packages that had no successful versions: removed-packages.txt
• Metadata produced by this run, with compilers associated: metadata.zip
• Manifest index produced by this run, with dependencies all fixed: registry-index.zip

[thomashoneyman]

We have decided to manually fix the manifests for deku, bolson, and rito so that these widely-used packages are not dropped. That's available in the latest commit.

[thomashoneyman]

With the patches in for rito / deku / bolson:

--------------------
PUBLISH FAILURES
--------------------

984 out of 1443 packages had at least 1 version fail.
  - 503 packages had all versions fail.

6317 out of 10696 versions failed.
  - Publishing failed: 94
  - No compilers usable for publishing: 558
  - Solving failed (dependencies): 5665

As usual:

• removed-packages.txt
• publish-failures.json
• metadata.zip

[thomashoneyman]

As discussed in the PureScript chat, the latest commit makes a small tweak to preserve packages that are from the core org or its derivatives, or which has had a tag since the 0.13 release date (May 29, 2019).

These 49 packages are now reserved with empty metadata: reserved-packages.txt

Some notable newly-reserved names include monad-eff, coproducts, functor-products, maps, sets, web3, and so on.

454 package names will be freed: removed-packages.txt

This is the full list of packages that made it to the 0.13 or organization cutoff, along with their latest tag dates: packages-publish-013.json

[f-f]

I had a look at the above files, and they look good to me - the list of packages that we'll reserve is minimal and meaningful, and the list of ~450 freed packages seems sensible (I have checked quite a few manually and they all seem to be old enough to not be worth supporting, as people won't be able to build with them anyways)

I started looking at the code but it's a sizeable patch so it will take a few days

[thomashoneyman]

Let me know if you encounter tricky bits and would like an explanation. Also happy to jump on a quick call and walk through sections of the code.

[f-f]

Thanks! I think the logistics of that will be tricky over the Christmas days, but I let's see if that works for next week

[thomashoneyman]

@f-f I think I've responded to your comments above, but GitHub isn't showing all of them in this main PR view so I'm not completely sure. Please let me know if I missed one!

[thomashoneyman]

@f-f Did you have any other questions or comments about this work?

[f-f]

@thomashoneyman I am through with the review - the overall shape of the code is good, and the only thing left to really resolve is the thing about "testing against the full set of compilers"

[thomashoneyman]

Resolved merge conflicts. Unfortunately, the integration test fails on my home system (which is pop_os, rather than NixOS) so that's going to be annoying to debug in the future; fails to git clone the effect repository due to the tmp directory already including it.

We're at least in a good position to resume work to get this over the line.

[thomashoneyman]

Integration test was already passing in CI, but it was failing for me locally. Diagnosed the issue as arising from the retryWithTimeout, which would occasionally kill the clone if it was running slowly, leaving files behind, but those files weren't cleaned up well before the next retry. I've bumped the timeout and added a cleanupOnCancel function to the retry helper so we can do a cleanup prior to the next retry.

[thomashoneyman]

Now that I finally got around to running the importer all the way through and have a local cache I can get back to splitting out the compiler jobs to be separate from the normal publish pipeline as discussed.

--------------------
PUBLISH FAILURES
--------------------

1460 of 1790 total packages were considered for publishing (others had no manifests imported.)
  - 291 out of 1460 packages fully succeeded.
  - 994 packages partially succeeded.
  - 51 packages fully failed, but are reserved due to 0.13 or organization status.
  - 454 packages had all versions fail and will be removed.

10906 of 13282 total versions were considered for publishing.
  - 6363 out of 13282 versions failed.

    - Publishing failed: 85
    - No compilers usable for publishing: 562
    - Solving failed (dependencies): 5716

----------
IMPORT STATS
----------

1790 packages processed:
  1063 fully successful
  397 partially successful
  127 omitted (no usable versions)
  201 fully failed
  ---
  174 Cannot Access Repo
  20 Package URL Redirects
  5 Disabled Package
  1 Invalid Package URL
  1 Invalid Package Name

13282 versions processed:
  10906 successful
  2376 failed
  ---
  718 Unregistered Dependencies
  680 Invalid Manifest (Invalid Dependencies)
  459 Invalid Manifest (Missing License)
  352 Invalid Tag
  155 Invalid Manifest (No Manifests)
  8 Invalid Manifest (Invalid License)
  4 Disabled Version

package-failures.json version-failures.json publish-failures.json

removed-packages.txt reserved-packages.txt