Tracking issue for RFC 1977: public & private dependencies, as it relates to the resolver

Eh2406 commented 6 years ago

This is a sub part of the discussion of implementation of RFC 1977, specifically how the resolver could implement this protocol. The main Tracking issue is at https://github.com/rust-lang/rust/issues/44663.

This comment https://github.com/rust-lang/rfcs/pull/1977#issuecomment-304043301 described the properties we want to uphold the way that fits best with my brain. So to use the termanology, I feel like when we are adding a packedge B we need to walk up the dependency tree to all potential C's that can see the addition to test if there is a conflicting A. That can be done pretty fast if we have a fast way to walk up dependency tree and a fast way to see all the pub reachable packages for each ancestor. (Neither of which we have at this time.) But that feels like a lot of state to be cloned for each tick. Currently we avoid the expensive clones with extensive use of RC.

Is it time to add a im-rs dependency? Is there a better algorithm? Is there a small part that would make a good starting PR?

alexcrichton commented 6 years ago

Adding new dependencies seems fine by me! My historical strategy with the resolver has been "don't add any fancy representation tricks, profile Servo, add tricks as necessary"

Eh2406 commented 6 years ago

I have a branch that stubs out getting this working. It involves all the ugly things I can think of. The state is a mess of big nested data structures. The algorithm is a bunch of nested loops in the hottest part of the resolver. It is not even checking for redundant work. The code is mostly repeated between the code that check if a candidate can be added and where the the candidate is added. Several existing optimizations are completely removed in the case that a pub-dep has ben looked at. The error messages are just "Todo", and most of the commit messages are "oops".

But it is working! I modified the passes_validation to check for pub-dep conflicts, then modified the registry_strategy to make them. It promptly generated a failing case. Copy the result to a standalone test, hand minimize, and add an explanation. Add something, anything to get that test passing. Then rinse and repeat. Lets just say that the fuzzer is very good at finding every optimization that this can react (badly) with. Eventually it passes!

Next try the limited_independence_of_irrelevant_alternatives and if finds a case of a registry that should work, but doesn't. Then rinse and repeat 3 more times. Finding backjumping optimization that need to be handled more correctly, disabled for now. But with the backjumping optimization disabled, it now finds a case that experiences exponential blowup.

So my plan for the Impl day at RBR is to attempt to get backjumping working, and clean my history into something submittable.

edit: the cleaned up history is at https://github.com/Eh2406/cargo/tree/pub-dep

Eh2406 commented 6 years ago

Cc @necaris

Eh2406 commented 6 years ago

So at RBR I got the history cleaned up. Alex and I reviewed the progress so far and a plan for how to re enable backjumping without losing correctness.

That backjumping strategy was implemented today. Unfortunately, the fuzz tests are finding kasese of exponential blowup (50_000 ticks). I suspect it is similar to #5213, in which we backtrack to where ConflictReason no longer applies without getting closer to the gole. Not that I really understand it well enough to explain / make a test case.

On a different note I also ran the other resolver tests, we have several that are hitting the 30 sec timeout on this branch. So we will need to work on per tick performance before this can merge.

Eh2406 commented 6 years ago

Good news If you run proptest overnight with --release it does an ok job of minimizing the problem (~100 lines, hand minimized to ~30). Bad news, I no longer think the backjumping strategy that I and Alex came up with is correct. I.E. it will reject cases it should except. In addition to being incomplete, allowing exponential blowup.

Eh2406 commented 6 years ago

I am (for now) ignoring the fact that the current strategy will fail to resolve when there is a valid solution in rare circumstances. I have cleaned up the case of exponential blow up, so I understand why it is happening. What I don't understand is why It is not happening using normal deps. (it is a lot harder to write, but should be possible.) I am investigating that, hoping that I will either find an optimization I forgot to add to pub/priv deps, or a case that can be reproduced on master.

Eh2406 commented 6 years ago

I can now confirm that the normal deps gets saved by #5213, where the pub deps do not.

Unfortunately, a simple solution did not work. I think doing something special for PublicDependency is not going to work. But I worry that doing the obviously correct thing will just move the slowenes around. I guess jump off that bridge when we come to it. here gose.

Eh2406 commented 6 years ago

I implemented the "obviously correct thing", and the fuzz tests pointed out that it was not backtracking correctly. I assumed I had done something silly, but could not find it. Then I got distracted by #6258. Coming back to it the minimized test was correctly pointing out that the "obviously correct thing" will not work. It is possible to make a pub-dep violation, without changing Activations, by changing which previously activated version a dependency resolves to. So any iplomantation of is_conflicting that just looks at is_active will not backtrack correctly in the presence of pub-dep. To complicate things that implementation detail of is_conflicting was just used for a new data structure in #6283, making it much harder to change.

Eh2406 commented 5 years ago

I have a branch where I have implemented both versions simultaneously. Like the "obviously correct thing" it records every PID in the path from the dependency that can see the conflict to both conflicting crates. Like the strategy Alex and I came up with at RBR, it ensures the parents relationship is still active when the Back Jumping occurs. Because it looks at the dependency tree it passes the test the previous strategy failed. Because it will records all the PIDs involved in conflict it can learn like #5213. Unfortunately, because it adds a lot of things to the conflict it is a highly efficient way of creating a test case like #6283. So efficient that, In debug the fuzz test only tell me that it hit the 50k limit, In release the fuzz test only tell me that there are cases that took longer than 90sec to resolve!

I have to say, adding new features to the resolver has gotten a lot harder now that we have fuzz tests making sure that they are correct, complete, and efficient. :-P

Eh2406 commented 5 years ago

Copied from https://github.com/rust-lang/cargo/pull/6653#issuecomment-464155128:

So the specific questions are:

How does this interact with renamed dependencies?

There are lots of juicy corner cases here. On one had being able to depend on 2 different versions of the same library is one of the points of renamed dependencies. Fore example so you can publicly derive serde1 and serde2 traits on the same type. On the other hand making sure you and your dependencies agree on the same version of serde is the hole point of public dependencies.

This makes my head hurt, is there something simple I am missing? If not, where is the appropriate place to discuss fundamental problems with an accepted RFC?

How does this interact with `'cfg({})'`ing in different versions?

Conceptually this one is very simple. Instead of asking "is there a package that can see two different versions of a dependency" we need to ask "is there a set of arguments so that there is a package that can see two different versions of a dependency". But the complexity is in the details. If we are not careful this is a SAT problem that needs to be solved for each tick. Where is the existing 'cfg({})' logic handled?

alexcrichton commented 5 years ago

For renaming dependencies I think the main question is that it's the first time you've been able to depend on two versions of the same dependency. The name itself doesn't matter so much (it's only relevant when compiling the local crate), but the fact that you can publicly depend on two versions of the same crate does indeed create a weird situation. My best guess of what to do here is that, like we'd probably always need anyway, an escape hatch would be used to say "please don't consider this for public crate graph resolution" or something like that.

For cfg that's also a good question, but I think the way to go is to probably take the route of the rest of Cargo's resolver and basically ignore cfg. We resolve a lock file assuming that all cfg clauses are satisfied and we only actually apply the target-specific dependencies in a later pass.

Eh2406 commented 5 years ago

So there are 3 states (not the 2 described in the RFC)

public: Even things that depend on me care what version we pick.
private: Only I care what version we pick.
unchecked (don't know what a good name is for this.) No one cares. We will handle the error if it comes up.

The status quo is that everything is unchecked. The RFC optimistically suggests making everything private by default and opting into public. I don't know what is reasonable as a default, but what would a good UI be for the cases when we need to be explicit?

Ericson2314 commented 5 years ago

The status quo is that everything is unchecked. The RFC optimistically suggests making everything private by default and opting into public. I don't know what is reasonable as a default, but what would a good UI be for the cases when we need to be explicit?

Yes I feel it would be better to grandfather everything in as unchecked so privacy problems can be errors not warnings by default.

public: Even things that depend on me care what version we pick.

Yes, but I think it's best to think in terms that preserve composition. Upstream creates don't care about downstream creates at all, but the dependency resolution upstream imposes pkg = version constraints downstream.

renaming dependencies

It depends on what equivalences the Rust code is allowed to witness: i.e. if bar is renamed foo, is bar::x = foo::x true for all x when foo and bar are resolved to the same version? This is like the difference between type X = .. and existential type X = ... (whaht impl Trait desugars to). In the latter case, the equality is never observable so there are no constraints for crate resolution.

Aaron1011 commented 5 years ago

Regarding renaming dependencies:

Since the package field is published to the index, do we actually need to expose the idea of an 'escape hatch' through the public field in the index? Unless we require users to explicitly write something different in their Cargo.tomls, we already need to be able to handle the absence of an explicit 'escape hatch' flag in any metadata/TOML.

Eh2406 commented 5 years ago

At the request of the Cargo team I have reread all of the discussion of the RFC to summarize the state of affairs. Admittedly, unlike @Aaron1011, @Ericson2314, and @alexcrichton, I was not there when the RFC was written. But here goes.

The RFC was accepted before renamed deps, and cfg({}) deps where things. As such, and after long discussion, it was shown that the only way to see two versions of a crate was for at least one of them to be a transitive dep. This meant that (using the terminology from above ) treating all existing deps as private was equivalent to treating all of them as unchecked. The RFC also predates editions, so the expected syntax had to work forever. So the RFC treats all unmarked deps as private and adds syntax for public. All existing crates will still build as is, new crates can use public if they want, and if the hard cases that come up need new syntax we can make a new RFC. 🎉

But in the meantime the renamed deps, and cfg({}) deps RFCs where accepted, implemented, and stabilized. All without discussing how it interacted with this RFC. 🤕 So if we follow the RFC and treat unmarked deps as private then we will break existing stable libraries, and make it impossible to resolve anything that depends on them.

So we need a new syntax that is aware of all three cases, and preferably future compatible with hard cases we may want to add. However it does not need to be the syntax forever as we have editions. The default interpretation of (at least renamed deps, and cfg({}) deps) has to be unchecked for backwards compatibility. I am open to suggestions!

Eh2406 commented 5 years ago

syntax proposal, speaking for myself not for the team:

Goles: stay consistent but also as close to the RFC as possible.

A dep can be in 3 states:

unset: this can be expressed by not having a public= or by having public="unset" in the dep in the Cargo.toml. This maintains the pre RFC behavior that dep name and anything it exports can overlap with other visible crates. This is the escape hatch that @alexcrichton has suggested before. It is stored in the index by not including the public field.
private: this can be expressed by having a public=false in the dep in the Cargo.toml. This means the same thing as in the RFC, that dep name and anything it exports can not overlap with other visible crates.
public: this can be expressed by having a public=true in the dep in the Cargo.toml. This means the same thing as in the RFC, that dep name and anything it exports can not overlap with other visible crates and that it has to match everything that the parent can see.

Add a message to the type mismatch, expected X found X error message to suggest setting public= on both paths, if it has not been set already.

Future extensions:

In the next edition change the missing case in Cargo.toml to be private while keeping the index the same.
Add a 4th form custom with a public="exports=[list of some of the things the dep exports that we export] see=[list of some of the things the dep exports that we want to treat as private]" to possibly handle some of the more subtle cases. Like x has a method that exports y and one that exports z but we only use the y one so we don't want to export z.

Alternatives:

Change the name of the field to something else, like visibility='private', visibility='public', , visibility='unset'.
Change the default in Cargo.toml but not the index, not having a public= in the dep in the Cargo.toml means private, forcing some users to add public="unset" to build. (I think this may be the point @Aaron1011 was making 2 up from hear. Sorry if I missed it.) Or more radically, the default in Cargo.toml is that not having a public= in the dep in the Cargo.toml means private unless it is a renamed deps, or cfg({}) deps in which case it means unset

Ericson2314 commented 5 years ago

@Eh2406 I too like explicit publicity lists (you want to do explicit public, not explicit private), but that is way to complicated a feature for Cargo to handle alone. This would take a module system like the ML's, or Haskell's backpack. Let's punt on this for now, and keep in mind it overlaps with https://github.com/rust-lang/rfcs/pull/2492 .

shepmaster commented 5 years ago

visibility='private', visibility='public', , visibility='unset'.

It's bikesheddy, but I prefer this form of specifying it.

dekellum commented 5 years ago

My 2¢: "visibility" field name is fine, but I think your original "unchecked" name (e.g. visibility="unchecked") is much better than "unset". The latter left me rather confused about how it could be different from not setting (not specifying) this optional field in Cargo.toml deps. After reading this 3 or 4 times, I now think not specifying the field is the same as some logical default for which you reserve the right to change over time ("unchecked" for now, possibly "private", later.) Or am I still wrong about your intent with that?

Eh2406 commented 5 years ago

You impute to me too much forethought. It often bites when there is no way to set a field to the value that would be used if it was missing. In CSS often foo: unset; means return it to the value it would have if no one had set it. So I was adopting that terminology. visibility='unchecked' or public="unchecked" works just as well.

The use case I had in mind is something like:

[dependencies]
curl = { 
    version = "0.4.21",
    features = ['http2'],
    public="unchecked" # We want this to be private but there is some bad interaction with our unrelated dep on http2 so we are intentionally leaving it unset.
    # We just had a comment here, but we got 3 PRs suggesting we change it from people that did not read the comment.
}

Sorry for the confusion.

dekellum commented 5 years ago

Q: Is the below another possible use case?

visibility="unchecked" # This *is* public, but... (workaround for project failure during dep resolution)

(And thus I think "visibility" gives you more future room for changes.)

Note this also relates to a suggestion in rust-lang/rust#44663 : A rustc warning/lint for if the dep is marked public, but it is in fact not public.

Eh2406 commented 5 years ago

Yes, definitely. That will also have #[allow(external_private_dependency)] in the code to hang the comment on.

dekellum commented 5 years ago

And you could also use "viz" to shorten "visibility". Not just cute, but accurate usage of the abbreviation:

https://en.wikipedia.org/wiki/Viz.

for the Latin videlicet, which itself is a contraction from Latin of videre licet meaning "it is permitted to see"

prior art: "pub" lang. keyword for public.

Eh2406 commented 5 years ago

speaking for myself not for the team:

syntax proposal 2, thanks to everyone for the feedback.

A dep can be in 3 states:

unchecked: this can be expressed by not having a visibility= or by having visibility="unchecked" in the dep in the Cargo.toml. This maintains the pre RFC behavior that dep name and anything it exports can overlap with other visible crates. This is the escape hatch that @alexcrichton has suggested before. It is stored in the index by not including the public field.
private: this can be expressed by having a visibility="private" in the dep in the Cargo.toml. This means the same thing as in the RFC, that dep name and anything it exports can not overlap with other visible crates.
public: this can be expressed by having a visibility="public" in the dep in the Cargo.toml. This means the same thing as in the RFC, that dep name and anything it exports can not overlap with other visible crates and that it has to match everything that the parent can see.

Add a message to the type mismatch, expected X found X error message to suggest setting visibility= on both paths, if it has not been set already.

Possible future extensions:

In the next edition change the missing case in Cargo.toml to be private while keeping the index the same.
Add a 4th form custom with a visibility="exports=[list of some of the crates the dep exports that we export] see=[list of some of the crates the dep exports that we want to treat as private]" to possibly handle some of the more subtle cases. Like x has a method that exports y and one that exports z but we only use the y one so we don't want to export z.

shepmaster commented 5 years ago

How will public/private dependencies interact with crate features? One of my crates may be gaining a feature flag that would conceptually change a private dependency into a public one; is there some way of indicating that?

Ericson2314 commented 5 years ago

@shepmaster I would say you should be able to do that with a optional public and private dependency. publicity overrules privacy due to the principle that no crate should be able to see multiple versions of the same library.

Ericson2314 commented 5 years ago

https://github.com/rust-lang/wg-cargo-std-aware/issues/12 a situation came up here that might require a small tweak to the solver. Say std depends privately on hashbrown == 1.1.2, and another crate does hashbrown == 1.1.3. Cargo doesn't actually need to invalidate this graph out of hand if no crate is able to see both hashbrowns.

Eh2406 commented 5 years ago

@shepmaster from the resolvers perspective this is straightforward and works already. (Without the flag the resolver get just a private dependencies with the flag the resolver get both.) But from a syntactic Cargo.toml perspective, I don't know how to specify that relationship. Add it to the list of things that need to be added to the features system.

@Ericson2314

a small tweak to the solver

From an implementation perspective, there are some structures that explicitly rely on the global property no two semver compatible versions, I believe there are other structures that implicitly do as well. They can be changed but it will take some work to figure out how.

From a conceptual perspective I wonder if this is transitive? For example:

a depends privately on b and c b depends privately on d and e == 1.1.2 c depends privately on d and e == 1.1.3 d depends publickly on e ^1.1 e has two versions 1.1.3 and 1.1.2 nether has dependencies

Can we build a? We can defintly build c it gets a lockfile with e = 1.1.3 and d We can defintly build d it gets a lockfile with e = 1.1.2 and d And a can not see the transitive dependency so with the transitive prospective on your small tweak it should not matter. But this means that a lock file needs 2 copies of d that only differ on the dependency version. That would require massive changes to Cargos internals.

From a community perspective, we all ready have a vocal portion of our user base concerned with the large number of dependency pulled in or the bloat from allowing multiple copies of libraries. I would want to make sure we have an appropriately large communication so that they can way in.

Overall I think this is a good idea and definitely worth discussing, but a big enough change to deserve a separate RFC.

infinity0 commented 4 years ago

In light of #7769 I would suggest the proposed field public be renamed to allow_public to avoid confusion between this concept and the concept mentioned in that report.

rust-lang / cargo