[rust-dev] Deprecating rustpkg

Jack Moffitt jack at metajack.im
Fri Jan 31 15:59:50 PST 2014


> What is this algorithm, and what is a concrete example of a set of
> dependencies that your hypothetical algorithm can solve which toposort
> can't?

Doesn't topsort require that you find a single version that satisfies
all dependencies? It's easy to construct things that will work for the
way rustpkg was designed (multiple versions of libs) that will fail
the requirement of needing a single version.

Package foobar
Depends rust-logger
  Depends rust-json 1.0
Depends rust-rest 1.0
  Depends rust-json 2.0

Here the logger was written back with the old json api, whereas the
REST client is written with the new API. There is no version of
rust-json that will satisfy both dependencies. For sake of argument,
let's assume there are no newer versions of rust-logger.

Without using multiple versions of rust-json, we'd have to fork and
update rust-logger. Such a conflict can appear arbitrarily many times
and arbitrarily deep in the hierarchy. I have hit such dependency
problems in previous projects with both Clojure and Erlang, both (as
far as I understand it) using topsort style dependency resolution.

The algorithm here is rather simple. We try to satisfy rust-logger and
rust-rest. rust-rest has a version (or could be a tag like 1.x) so we
go get that. It depends on rust-json 2.0 so we get that. Then we try
to look for rust-logger, whatever version is latest (in rustpkg this
would mean current master since no version or tag is given). This
pulls in rust-json 1.0 since 1.0 != 2.0 and those have specific tags.
Everything is built and linked as normal. Whether rust-json's
constraints are exact revisions or they are intervals (< 2.0 and >=
2.0 for example), makes little difference I think.

This happens all the time in Clojure especially in the rapidly
advancing web library ecosystem. It's not hard to concoct some set of
versions which conflict on the json library, the Ring library, or some
other low-level dependecy. Sometimes forcing the issue with exclusions
works. Sometimes it doesn't. Just look at the pile of forks on Clojars
of common low-level dependencies, and it's easy to see this is not
uncommon.

I'm not trying to argue that we build something that supports this and
only this. But this was a specific design criteria of Rust's linkage
model *and* it's package manager (rustpkg anyway; i wasn't around for
cargo). People have put a lot of thought into this because it's a long
standing wart of compiled languages, or at least it is in the eyes of
Rust's designers. This model also has issues which much be addressed.
You don't for example want 20 copies of rust-json just because it's
used often and each person specificied some different micro-revision
(doesn't npm do something like this?), bloating the binary size.

Also, I'm not sure the models are incompatible. It's perfectly fine to
do topsort and then just include multiple versions when a conflict
can't be completely resolved.

jack.

PS. Having now gone to look up to make sure I understand what topsort
is, I'm not sure how that is particularly related.  I assume you mean
that you are topsorting where nodes of the graph are packages not
versions of packages. In that case, since only one version can be
picked, if you have conflicting requirements (as above) then you're
stuck. If you topsort on versions of packages, there's no issues, but
then you probably need some way to collapse nodes when constraints
allow it to avoid having multiple compatible versions.


More information about the Rust-dev mailing list