Overlapping Dependencies in Lock Directory ("in and out problem")

[rgrinberg]

Apologies for the title, better suggestions are welcome. The issue is best understood by an example.

Consider the following setup:

$ cat dune.lock/b.pkg
(depends c)
$ cat dune-project
...
(package
 (name a)
 (deps b))
(package
 (name c))

So a and c exist in the workspace while b is fetched via the lock directory. If you follow the dependency edges of a, you will go through the lock directory and back to the workspace. Such dependencies edges are currently not allowed in dune.

The reason is the following cycle:

1. To build anything in the workspace, we need to lookup some library, say x.
2. Looking up x requires us to build every single package in the lock directory
3. If a package in the lock directory depends on a package in the workspace, that will immediately result in a cycle.

We could do better by limiting the search to a subset of packages in some situations. For example, if we're building foo.lib in package foo, we look at the package dependencies of foo to determine the set of packages that need to be built to resolve the library.

This of course only works for building libraries or executables inside packages. A private library or executable belongs to no package so the trick above fails (However, implementing #8650 would allow this to work anyway).

Anyway, if we manage to get over the cycles, we'll need some additional setup to make the build work. In the example above, package b needs the installed layout of c. We essentially already have this in _build/install, but it needs to be subset of files needed by b (otherwise we'll run into different cycles). In particular, we only need the install rules for c. That's not a problem, we just need to setup the install rules again for every package in the workspace in _private/ individually. So in practice, we'll just have rules in _private/default/.pkg/$pkg for every package in the workspace.

[rgrinberg]

This issue actually prevents dune's package management to be used to work with dune itself.

Since our repo includes the dune-configurator project, we cannot use any package that itself depends on dune-configurator. That ends up being just about every package.

[rgrinberg]

I talked about this @gridbugs and we have a plan on how to make progress on this issue. The first step of this issue is to make it possible for dune to build a package inside the workspace without loading every single package in the lock directory. To do this, we need to make use of two sources of information:

1. The list of dependencies of a package. This list is available in the dune-project file after it's evaluated against a lock dir
2. The association between a subset of the workspace and the package that it belongs to.

Point 2. is where the issues begin. The issue was correctly identified in #3255 and addressing it is the easiest way to make progress. It will also fix a bunch of other annoying issues like the raciness that makes our CI fail.

Once the above points are addressed, we can start by defining per package scopes + contexts that will not build the entire lock dir just for one package. This is the majority of the work. Following that, we just need to make packages in the workspace available in the exact same layout as packages coming from the lock dir. It will be then possible some simple overlapping workspaces.

[shonfeder]

@punchagan has started doing some investigative explorations here, so I'm reflecting that with assignment, but it's not indicating that he's become the primary responsible for completing it. Any substantive learning will be shared.

[Alizter]

Some tracking of PRs in progress tackling the issues needed here, in priority order:

🧱 Done

• feat: %{pkg:foo:lib:file} pforms for package install layouts #14200
• cleaning up censor helpers for tests
  • test: make censor disambiguate digests #14430
• tests for %{bin} resolution
  • test: bin pform expansion #14431
• fixing %{bin:...} resolution
  • feat: bin-layout for %{bin:...} deps  #14432
  • fixes dune build %{bin:foo} returns an error #3324
• reject (package ...) inside named dep bindings
  • fix: reject (package ...) inside named dependency bindings #14499
• install layouts for package sets (includes design notes on one part of the work)
  • feat(pkg): install layouts for package sets #14373
• tests for lock-dir ↔ workspace deps
  • test(pkg): pin baseline for lockdir pkgs declaring workspace deps #14864

Scope

The current implementation phase allows Dune to consume hand-written or externally generated lockdirs containing lock-dir → workspace dependency edges. The solver will continue producing self-contained lockdirs.

Having the solver select workspace packages is a later phase and requires cycle detection in the solver.

🚧 Replacement stack

Validation correctness

• Validate direct dependencies on Dune consistently with the solver

  • Regression test: test(pkg): validate-lockdir on a direct dune dependency #15616
  • Fix: fix(pkg): evaluate local dependency formulas the way the solver does #15618

• Evaluate self-referencing package constraints consistently with the solver

  • Regression test: test(pkg): validate-lockdir on a self-referencing constraint #15617
  • Fix: fix(pkg): evaluate local dependency formulas the way the solver does #15618

• Report stale lockdirs before workspace/lockdir name collisions

  • Regression test: test(pkg): stale lockdir with a workspace/lockdir name collision #15620
  • Fix: PR-TODO

Dependency graph foundations

• Traverse workspace and lock-dir packages as one dependency graph
  • Cycle regression test: test(pkg): dependency cycles are tolerated or crash #15619
  • PR-TODO
  • Detects dependency cycles while validating a combined package universe.
  • This is not cycle detection in the solver.

Prevent build-time in&out cycles

• %{bin:...}, %{bin-available:...}

  Currently, the analysis required to expand the names in these pforms to actual binaries ends up adding a dependency on all the lock-dir packages via Pkg_rules.which. This is one of the edges that can lead to the in-and-out cycles discussed here. The test in test: document %{bin} and %{bin-available} behavior lock-kind contexts #14736 captures the current behavior. A fix needs to change that behavior, at least where the locked package dependencies are known for the context in which the pform expansion runs.

  The semantics of bin-available with respect to binaries coming from locked packages that a workspace package depends on also need care. If the workspace package already depends on a package that provides the binary, why would %{bin-available} be needed? Should %{bin-available} instead limit its search to executables on $PATH?

  The replacement narrows package binary lookup and PATH to the owning package dependency plan.

  • PR-TODO
  • Replaces/supersedes feat(artifacts): narrow binary lookups to declared dependencies #15381

• Super_context.resolve_program

  Several stanzas, such as (ocamllex ...) and (menhir ...), resolve their tool binaries via Super_context.resolve_program. This eventually falls through to Pkg_rules.which via Artifacts.binary → Context.which. The test in test: document resolve_program resolution in lock-kind contexts #14737 captures behavior similar to the bin and bin-available pform expansions. These lookups must use the owning package dependency plan rather than forcing every lock-dir package.

  • PR-TODO
  • Replaces/supersedes the corresponding part of feat(artifacts): narrow binary lookups to declared dependencies #15381

• Generated tool-running rules and companion binaries invoked through PATH

  Tools selected from a package dependency plan may invoke companion binaries by name. Their actions therefore need the same package-scoped binary precedence on PATH as explicit binary lookup; otherwise lookup and execution can disagree or reintroduce a dependency on unrelated lock-dir packages.

  • PR-TODO

• Expose workspace package install layouts to lock-dir package builds

  A lock-dir package that depends on a workspace package needs the installed layout of that workspace package. The layout must contain only the dependency-specific install rules; using the full workspace install tree would recreate the cycles that package-scoped layouts are intended to avoid.

  • PR-TODO
  • Replaces/supersedes feat(pkg): allow lock-dir pkgs to dep on workspace pkgs (in&out) #14822
  • Ordinary install entries
  • (source_trees ...) entries
  • Transitive lock-dir → workspace → lock-dir dependencies

• Make target contexts inherit the owning context lockdir

  • Regression test: test(pkg): target contexts fall back to the default lockdir #15621
  • Fix: PR-TODO

Enable the feature

• Allow lock-dir packages to depend on workspace packages

  Dune currently prevents package-management features from being used when a lock-dir package depends on a workspace package. This prevents users from encountering the in-and-out cycles described in this issue. Once the graph, lookup, and install-layout prerequisites above are in place, this restriction can be relaxed.

  See test-cases/pkg/non-local-package-depends-on-local-package-error.t for the validation performed during lock-file generation. The feature step should allow these edges while continuing to reject unknown and ambiguous package names.

  https://github.com/aantron/dream is a real repository affected by this restriction.

  • PR-TODO
  • Relax structural lockdir validation for workspace package names
  • Reject ambiguous names present in both the workspace and lockdir
  • Keep dev-tool lockdirs strictly validated
  • End-to-end in&out tests
  • User documentation
  • Changelog

💭 Future solver support

• Allow the solver to select workspace packages

• Add transitive cycle detection to the solver

  Lockdir packages currently come from the opam repository, which ensures that those packages do not contain cycles. Dune separately prevents cycles among workspace packages, and historically did not permit lock-dir packages to depend on workspace packages. The solver therefore has no cycle detection of its own. Allowing the solver to select workspace packages introduces graphs that cross both package sets, so this later phase needs transitive cycle detection in the solver.

  The combined Package_universe validation in the replacement stack detects cycles while consuming a lockdir, but it does not provide solver cycle detection.

• Decide how solver-generated lockdirs represent workspace dependencies

💭 Further work

• Evaluate stanzas per package
• Per-package compilation contexts
• Dune-self-build CI job
• %{lib-available:...}
• %{lib:...}
• Compilation context splitting
• Build Dune Packages #9983 - would solve many of these problems