add tooling to deal with build.zig dependency trees

[andrewrk]

Extracted from #14265.

Terminology clarification: #14307

Add subcommands for dealing with the following situations:

• user wants to add a new dependency zig fetch --save
• user wants to remove a dependency
• user wants to check for updates to dependency tree
• user wants to update one or more dependencies

A conflict occurs when dependency tree contains multiple projects with the same id, but different version.

Add conflict resolution logic. This could go one of two ways:

• The maximum version number is chosen but only among those projects actually referred to in the dependency tree by url/hash.
• User must explicitly specify how all conflicts are to be resolved whenever a conflict occurs. Conflict resolution data goes into build.zig.zon.
  • For each dependency on a project which has conflicts in the tree, user may choose that dependency to resolve to any project that exists within the dependency tree that has the same id, and a version that is greater or equal.

[kuon]

I work with elixir and I really like the tooling hex (package manager) provides. Maybe we can take some inspiration.

A few commands:

mix hex.outdated

Dependency              Current  Latest  Status           
base24                  0.1.3    0.1.3   Up-to-date       
ecto_sql                3.9.1    3.9.2   Update possible  
esbuild                 0.5.0    0.6.0   Update possible  
floki                   0.34.0   0.34.0  Up-to-date       
gettext                 0.20.0   0.21.0  Update possible  
jason                   1.4.0    1.4.0   Up-to-date       
...

Run `mix hex.outdated APP` to see requirements for a specific dependency.

To view the diffs in each available update, visit:
https://hex.pm/l/GPaDq

mix deps.tree

zkfs
├── base24 ~> 0.1.3 (Hex package)
├── ecto_sql ~> 3.6 (Hex package)
│   ├── db_connection ~> 2.5 or ~> 2.4.1 (Hex package)
│   │   ├── connection ~> 1.0 (Hex package)
│   │   └── telemetry ~> 0.4 or ~> 1.0 (Hex package)
│   ├── ecto ~> 3.9.0 (Hex package)
│   │   ├── decimal ~> 1.6 or ~> 2.0 (Hex package)
│   │   ├── jason ~> 1.0 (Hex package)
│   │   └── telemetry ~> 0.4 or ~> 1.0 (Hex package)
│   ├── postgrex ~> 0.16.0 or ~> 1.0 (Hex package)
│   └── telemetry ~> 0.4.0 or ~> 1.0 (Hex package)
├── esbuild ~> 0.3 (Hex package)
│   └── castore >= 0.0.0 (Hex package)
...

It also features nice conflict resolution and explanation when there is one.

[rbino]

I can vouch for the Elixir approach too, I find it straightforward and it always worked well in my experience.

To expand a bit on what @kuon said, the key is that when you declare a dependency you specify a version requirement, which can be a specific version or (more often) an accepted range of versions.
If transitive dependencies can't be reconciled, there's an escape hatch: you can override them at the top level to force a specific version. For example, if dep :foo depends on dep {:baz, "== 1.1"} and dep :bar depends on dep {:baz, "== 1.2"}) you can specify in your own project {:baz, "== 1.2", override: true} which forces the use of version 1.2.

Much of the convenience of the configuration comes (imho) from the ~> operator in version requirements, which basically allows you to lock either to a specific major (e.g. ~> 1.2, which means "anything 1.x.y with x > 2") to a specific major + minor (e.g. ~> 1.2.0, which means "anything 1.2.x with x > 0").

Note that the success of this approach comes mainly from the fact that the Elixir community takes Semantic Versioning to heart, which means that I can be sure that if I stick to a certain major version of a dependency, my stuff will continue to work and the API will not change randomly between minor versions (for major versions > 0, see SemVer for the whole explanation).

If dependencies don't follow semantic versioning, then this approach breaks easily. Maybe there could be ways to enforce this (e.g. the Elm programming language automatically bumps versions following SemVer by analyzing the code and checking if there was any API breaking change) but I assume that for now we'd have to rely on the good faith of authors.

Here's a snippet of the dependency configuration part of the mix.exs file, which shows how dependencies can be pulled, respectively, from the central package manager, Github (syntactic sugar over git), a generic git repo and a local package:

[
  {:plug, ">= 0.4.0"},
  {:gettext, github: "elixir-lang/gettext", ref: "ad014681ee119954e3bad6dd2e22687330e45068"},
  {:zigler, git: "https://github.com/ityonemo/zigler.git", tag: "0.9.1"},
  {:local_dependency, path: "path/to/local_dependency"}
]

See here for an overview of the full list of options

[kuon]

While reading this I realize that it might be a justification for the .zon file format we are thinking about in #14290

.zon would be a zig datastructure, but with a deterministic and guaranteed generation.

For example, keys order would be untouched.

This is important because if I have the following dependencies:

.{
    .name = "libffmpeg",
    .version = "5.1.2",
    .dependencies = .{
        .libz = ">= 1.0.2",
        .libmp3lame = ">= 1.0.2",
    },
}

And I do zig package add png, my file would be like:

.{
    .name = "libffmpeg",
    .version = "5.1.2",
    .dependencies = .{
        .libz = ">= 1.0.0",
        .libmp3lame = ">= 1.0.0",
        .png = ">= 1.0.0",
    },
}

(Key added last).

Now let's say I comment my file and reorder dependencies for documentation:

.{
    .name = "libffmpeg",
    .version = "5.1.2",
    .dependencies = .{
        // Image libraries
        .png = ">= 1.0.0",
        .jpeg = ">= 1.0.0",
        // Compression
        .libz = ">= 1.0.0",
        // Audio
        .libmp3lame = ">= 1.0.0",
    },
}

If I add a package with zig package add imagmagick I want to be sure that order and comments are kept:

.{
    .name = "libffmpeg",
    .version = "5.1.2",
    .dependencies = .{
        // Image libraries
        .png = ">= 1.0.0",
        .jpeg = ">= 1.0.0",
        // Compression
        .libz = ">= 1.0.0",
        // Audio
        .libmp3lame = ">= 1.0.0",
        .imagemagick = ">= 1.0.0",
    },
}

As for tooling, I realize we do not want a central package repository, but I think an index would help a lot, to provide:

$ zig package add png

We found the following packages:

1. https://github.com/glennrp/libpng
2. https://github.com/kornelski/pngquant

Which one do you want to install? 1-2: 

[thezealousfool]

Thinking about this in context of #14314, there are two kinds of dependencies - those that are mentioned in the build.zig.zon and those that are actually being used based on the platform or build flags passed by the user.

For eg. (from #14314 (comment)) different dependencies for audio backends but only one of them being enabled at build time for the target platform - different platforms might enable different set of backends.

The distinction is important to this issue as there can be two different approaches to adding the required tooling mentioned in this issue. For adding and updating dependencies of the current main package can be done by just analyzing and modifying the build.zig.zon.

But for operations like conflict detection/resolution and dependency tree generation things get a bit more complicated. For eg. for dependency tree generation we could -

1. Analyzing the build.zig.zon files of the current package and of all the dependency packages and spit that out.
2. Analyze the build graph created by build.zig with all the different (potentially complicated) logic for enabling different dependencies and then output only those in the dependency tree.

The second point above can be achieved in different ways. I was thinking if we could create a dummy builder that has empty stubs for the different functions not required for analyzing dependencies and pass that in to the build scripts might be a simple and fast way of achieving 2.

[Immortalin]

In Rust, Go, and NPM (excluding peer dependencies), diamond dependency problems are avoided by allowing multiple versions of the same dependency to co-exist and any potential API conflicts is handled by the type system. This is a big improvement over the traditional gems/pip/maven workflow that only allows a single global dependency singleton to be loaded unless package shading is enabled.

https://stephencoakley.com/2019/04/24/how-rust-solved-dependency-hell

https://research.swtch.com/vgo-mvs

https://lexi-lambda.github.io/blog/2016/08/24/understanding-the-npm-dependency-model/

https://pnpm.io/symlinked-node-modules-structure

We should implement a similar system for Zig. Once C libraries come into play, it will be very thorny if Zig modules struggle to link against conflicting upstream dependencies.