CUDF support

[hugosenari]

Hi,

I'm currently creating an alternative for flake-nimble.

My first attempt was let nix flakes locks handle locks, it didn't work well.
My second attempt was, use lock tool from ecosystem, but it is too slow.
And the current approach is indexing all and use head, isn't ideal, so I'm looking for alternatives to dependency resolution.

I was looking for SAT/SMT solutions, and found aspcud it uses cudf to resolve dependencies.
And I'm wondering if it makes sense to add CUDF support to dream2nix.

I'm also open to ear about other options, like does dream2nix solve this?

[DavHau]

So far we got around dealing with dependency resolution in general.
We either read from already existing lock files (pure translation) or we call out to external dependency management tools (impure resolution), to create a lock file that we can parse. The tools invoked by our impure translator do dependency resolution to create the lock file, but we treat that as a block box. For example for nodejs projects we just call out to npm to create a lock file if none exists.

If Nim does not have a tool yet that can create a lockfile, then implementing your own resolver might be worthwhile.
In general it would be amazing if someone added support for dependency resolution to dream2nix.
The nix ecosystem is missing such functionality in general. I wish we can have builtins.resolve or something similar one day.

Currently dream2nix can only act as an addon to dependency management. It relies on other tools maintaining lock files. It cannot work standalone, because there is no dependency resolver. So if you can solve that, that would be great ;)

[hugosenari]

My POC now works.
Documenting here, if anyone else would like to try for different lang or the same.

Example requesting 3 packages,
hcparse has 11 dependencies
libp2p has 16 dependencies
cligen has 0 dependencies

dependencies = nimrevs.lib.srcs {
  inherit pkgs;
  nimPkgs = [
    "cligen"
    "hcparse"
    "libp2p"  
  ];
};

Can be built it as:

nix show-derivation 'github:riinr/flake-crown?dir=pkgsRev/example'
nix build 'github:riinr/flake-crown?dir=pkgsRev/example'
nix build 'github:riinr/flake-crown?dir=pkgsRev/example'#nixpkgs2211 # fail :(

Pkg Resolution process:

• indexing time
  1. index metadata as cudf
  2. index metadata as json (example)
  3. index cudf <-> json, because cudf has name (no _) and version (must be int) restrictions
• buildtime
  1. call aspcud with a "request" (ie: cudf index + 'install: cligen, hcparse, libp2p >= 1')
  2. parse the response (i replaced : with = called it as TOML)
  3. use the cudf <-> json to find ref, rev and meta info
  4. fetchGit {ref, rev}

Index process (Nim specific):

1. fetch packages.json (is like nixpkgs of Nim)
2. git ls-remote for every pkg
3. clone every ref (Nim has no std file name for package meta and it is a Nim file)
4. use nimble dump (only available in latest version)
5. write the output of dump to a json file

Notes and questions:

• Not sure how it would be with large package set (Nim has only ~2k)
• Nim can't have two versions of same package, Python and Node can, how CUDF deal with it?
• There is a bug for aspcud with large version numbers (converting semver to int isn't lossless)
• This POC didn't work for 22.11, I don't know why.
• I'm betting on aspcud precision, because it uses pure logic to resolve dependencies, Opam used to recommend it. Other options? ;-)
• This POC doesn't propagate dependencies. It only downloads and adds to compiler path.

[DavHau]

Hey, I finally took a closer look at this and I'm quite hyped about this experiment.

Not sure how it would be with large package set (Nim has only ~2k)

I'd love to find out. pypi-deps-db could be used as a data source. It contains most of the 4 million package releases from pypi.org.

Nim can't have two versions of same package, Python and Node can, how CUDF deal with it?

Node can, but python cannot. The CUDF Primer mentions:
conflicts are not implicit among different versions of the same package: multiple versions of the same package can be installed at the same time. Self-conflicts are ignored. This means that you can achieve Debian-like implicit conflicts (i.e. only one version of each package can be installed at any given time) as follows: [...]
It seems like by default CUDF allows multiple versions if the package doesn't list its own name under conflicts.

There is a bug for potassco/aspcud#11 (converting semver to int isn't lossless)

Hm, it seems like the tooling around CUDF is not super well maintained. Did you look into any alternatives so far, like for example libsolv ?

[hugosenari]

Hey, I finally took a closer look at this and I'm quite hyped about this experiment.

At least spammer called your attention 🤣

I'd love to find out. pypi-deps-db could be used as a data source. It contains most of the 4 million package releases from pypi.org.

SAT Solver geeks are proud of how fast theirs software 'solve large problem sets', I am not sure if is the case here, but there is a hope.
The nice thing, is that once solved, the resolution goes to storage and will be cached until index or requirements change, that also means we could share this cache. 🤩

Hm, it seems like the tooling around CUDF is not super well maintained

aspcud at least is in use by OCaml community, they are migration to own solution, that is why we have it in nixpkgs.
The problem with large int, I solved with two 0 padding algorithms, one for SemVer other for CalVer. From SemVer perspective, we could also remove Patch information from package and only index latest patch, or we could do like shared libraries ie: openssl 3.2.1 is openssl3 2.1, because openssl1 and openssl2 are incompatible.
The problem with nixpkgs 22.11, was also fixed.

Did you look into any alternatives so far, like for example libsolv ?

No because, CUDF + aspcud solution was too simple like

readFile (
  runCommand "resolv-deps" {
    cudfRequest = "request: \ninstall: myDependency\n";
    passAsFile  = ["cudfRequest"];
    buildInputs = [ aspcud ];
  }
  ''
    aspcud <(cat ${nimPkgsCudfIndex} $cudfRequestPath) $out
  ''
)

[hugosenari]

I'd love to find out. pypi-deps-db could be used as a data source.

It can be used as data source.
https://github.com/DavHau/pypi-deps-db/pull/17/files

Now you need the reverse mapping.