Variants - Simplified

[rgrinberg]

Variants - Simplified

(This proposal is aimed at @TheLortex who has expressed some interest in implementing this feature. However, some details need to be hashed between the maintainers first)

Now that we've merged virtual libraries, we can consider implementing the full
variants proposal. It's heavily simplified from the original proposal so I'm
rewriting the original ticket.

TL;DR:

Variants are now tags that are attached to implementations. Executables may now
select groups of implementations simultaneously by choosing such tags.

Implementation Steps

1. Modify the library stanza to allow marking library implementations with an
   optional (variant ..) field.

2. Modify the executables stanza to allow for a (variants ..) field. It should
   allow for a list of tags to be selected.

3. Modify the dune-pacakge format accordingly to maintain variant information
   for implementations.

4. When loading the library database, we must maintain a map from individual
   variants to a map of virtual libraries to implementations. The next step
   will make it obvious why we need such a data structure.

5. When calculating the closure for linking (executables), we now need to select
   implementations based on the set of tags. I'll describe this in a bit more
   detail

Roughly, the closure pipeline for executables would look like:

deps
(* (1) calculate the closure *)
|> closure
... (* (2) *)
(* (3) verify that there's an implementation present for every vlib
  and make sure the linking order is correct *)
|> Virtual_libs.associate

In ..., we'd like to insert a step that would insert implementations based on
the selected set of variants.

So essentially:

val add_impls_for_variants : Lib.t list -> variants:Variant.t list -> Lib.t list

Now there's a bit of a problem here: we must calculate the closure again after
this step, and recursively do (1; 2) until 2. doesn't change the closure.
This is because an implementation itself may depend on a virtual library.

Consider:

(library
 (name bar)
 (virtual_modules bar))
 
(library
 (name baz_js)
 (implements bar)
 (variant js))

(library
 (name foo)
 (virtual_modules foo))
 
(library
 (name foo_js)
 (libraries bar)
 (variant js)
 (implements foo))
 
(executable
 (name x)
 (libraries foo)
 (variants js))

Now, if we calculate the closure of x we'll discover foo and that we need
the foo_js library. But now we'll also need to select the correct
implementation for bar.

Taking the closure + finding implementations in a fixpoint doesn't seem very
attractive, so unless @diml has a better idea, I suggest we interleave the
variant-based implementation selection with the closure itself. In this new
closure, we'll check if the current library is virtual, and we have an
implementation for it based on the set of variants present. In this case, we'll
just add the correct implementation to the closure directly.

Possible Issues & Future Work

• As usual, making decent error messages always increases the difficulty. Let's
  worry about this once we have a prototype ready. We can threw some test cases
  and improve errors from there.

• Since variant tags is going to be quite small (compared to the set of
  libraries at least), We might need a conflict resolution mechanism when two
  libraries provide an implementation for the same library with the same variant
  name. Yes, in this case the user can always just drop variants altogether and
  go back to concrete implementations, but that's a bit dissapointing.

  Perhaps one could resolve this ambiguity by providing a concrete
  implementation in the libraries field for the executable. So when doing
  lookups from 4, we'll keep in mind the list of libraries the user actually
  listed.

[TheLortex]

Hi !
I advanced a bit on the variants matter. This is a first implementation that handles the basic cases.
I'm not quite familiar with the dune code base so tell me if I got something wrong. I also added a way to specify a default variant for virtual libraries. Tests have been added to cover the new cases.
What do you think ?

(most of the work is done in this commit: TheLortex@92de8f6)

[rgrinberg]

This default variant thing is something that should be discussed separately I think. I'm not yet sure it makes sense over a default implementation. Consider two virtual libraries setting a conflicting default "variant". How would the default variant be selected for an executable depending on those libraries?

[ghost]

BTW, one thing I had in mind: currently we can force a particular implementation by adding it as a dependency. In some cases, implementations might be added through transitive dependencies. Now, an implementation might come from a dependency on an implementation that was automatically selected through a variant. At best, we'd get conflicting implementations, but at worse we might not get the expected result.

I believe what I'm trying to say is that I'm not sure the selection process is confluent. I.e. depending in the order in which the code make choices, we might not get the same final set of libraries. Which is not very satisfying.

[ghost]

It might be worth reasoning on an abstract version of the algorithm, so that we can convince ourselves it is correct.

[TheLortex]

This default variant thing is something that should be discussed separately I think. I'm not yet sure it makes sense over a default implementation. Consider two virtual libraries setting a conflicting default "variant". How would the default variant be selected for an executable depending on those libraries?

Yes after thinking about it it's not an interesting feature. Having a default implementation sounds better.

Regarding the algorithm. Mine is currently quite wrong so I agree on reasoning about an abstract version ! My idea was something like this:

resolve_deps:

• Compute transitive closure
• Find implementations for each virtual library:
  • use a map to find available implementations
  • match them with user written deps
  • if that doesn't work, match them with variants
  • if there is ambiguity, throw an error
  • if there is no variant matching, use default implementation
• Compute transitive closure for each implementation
  • when merging closures, we can check if there are two different implementations for the same virtual lib and throw an error from here.

Forcing implementations over the whole dependency tree seems tricky, what we can try is forcing implementations down the children of a node (an extended version of user written deps).

[TheLortex]

To illustrate the issue when having both default implementations and variant forcing for the whole tree, with the following dependency scheme:

x --> a (default impl ->) a.1
'---> b -> a.2

If we resolve a first then these is implementation conflict between a and b.
If we resolve b first then this is solved without error.

[rgrinberg]

but at worse we might not get the expected result.

Do you have an example in mind of how could that happen?

I believe what I'm trying to say is that I'm not sure the selection process is confluent. I.e. depending in the order in which the code make choices, we might not get the same final set of libraries. Which is not very satisfying.

The way I frame the problem, there should only be a unique way to select the implementations based on a set of variants. So the case where an implementation is pulled transitively and a different implementation is forced via a variant is an error. Although perhaps we should allow for explicitly overriding stuff like that.

[rgrinberg]

@TheLortex Do you want to work on the default implementation issue separately? I believe it should be quite a bit simpler and required nonetheless. It will get you up to speed with the code base.

Did you have a look at my algorithm as well? I explain that you cannot just do the closure and the variant selection separately.

when merging closures, we can check if there are two different implementations for the same virtual lib and throw an error from here.

There shouldn't be a need for this because the final step in our pipeline validates the closure. That is, if you insert the variant selection step before this final step, you will not have to worry about constructing invalid closures. You'll only have to worry about giving a good error message so the user knows where an implementation is being pulled from.

[ghost]

The problem with default implementation is the same I believe. We were just discussing this with @aalekseyev who came up with the following example:

black arrows are normal dependencies and orange arrows are default implementations. Depending on which orange arrow we follow first, we get different implementations for Async and Clock. The only way is to indeed follow all possibilities and report an error afterwards when we have too many implementations for the same virtual library.

The algorithm proposed by @TheLortex looks right, just a couple of comment:

• match them with user written deps

This should include the transitive deps of user written deps, since this is what we are currently doing.

• Compute transitive closure for each implementation
  • when merging closures, we can check if there are two different implementations for the same virtual lib and throw an error from here.

Here I assume that we only follow implementations that were newly added through variants or default implementation selection.

@aalekseyev suggested the following idea: we can consider that we associate a state to every existing virtual library. The state can be one of:

1. not seen
2. doesn't have an implementation
3. has exactly one implementaiton
4. has too many implementations

and we update the state of virtual libraries as we follow the graph. I believe that's roughly the same as merging the independent transitive closure, however it might be slightly faster.

[TheLortex]

@rgrinberg

@TheLortex Do you want to work on the default implementation issue separately? I believe it should be quite a bit simpler and required nonetheless. It will get you up to speed with the code base.

I feel like it's not that simple, according to @diml example..

Did you have a look at my algorithm as well? I explain that you cannot just do the closure and the variant selection separately.

Yes I did, and what I wanted to say is that we can't choose an implementation directly when a virtual library is added to the closure. We might need more information in order to know if the virtual library is already implemented or not, right ?

@diml
I get the idea to associate a state to each virtual library during closure computation, but how does that lift the ambiguity from the example ? Exploring every possibility doesn't seem tractable.

[ghost]

I believe the right behaviour for the example is to fail and ask the user to write additional stuff in order to help dune decide what to do. I don't really see a way around exploring all possibilities, but technically it doesn't seem too bad: it's just one additional edge for each virtual library to traverse.

[TheLortex]

I've been able to implement default implementations + variants and it seems to work alright with my hand made cases. Error messages need to be more user-friendly.
What do you think ? Should we track that on a PR ?

[rgrinberg]

Yes, please make a PR.

[rgrinberg]

This proposal has been implemented but it turns out to be flawed. We have a new proposal (#2134) to address the issues introduced by this one.