> 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. _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
