All-features transitive dependencies

[infinity0]

Currently for every source package we run cargo build as part of the tests, which means the binary runtime dependencies of the default features are needed for a given source package to build. This crate as well as cargo-tree is able to calculate these dependencies, since it is the same as the normal cargo resolution algorithm.

Note that this relationship has a source package rust-S at the root, and binary packages (crates with features) below the root:

rust-S # build-depends are same as:
librust-S+default-dev
 |- librust-A+noB-dev

However in order to get each of these binary packages into Debian, say binary package librust-A+X-dev, it is necessary to get its source package rust-A into Debian, which means getting all binary runtime dependencies of its default features into Debian, i.e. children of librust-A+default-dev. This set may be greater than the children of librust-A+X-dev that was present in the output tree of rust-S as given by this package or cargo-tree:

rust-S # build-depends are same as:
librust-S+default-dev
 |- librust-A+noB-dev # But to actually get this into Debian Unstable we need to package:
    rust-A # whose build-depends are the same as:
    librust-A+default-dev
     |- librust-B+whatever-dev # But to actually get this into Debian Unstable we need to package:
        rust-B # whose build-depends are the same as:
        librust-B+default-dev
         |- etc, recursively

It would be good if this tool were able to print this larger tree. This is the algorithm that is implemented in an extremely hacky way here:

https://salsa.debian.org/rust-team/debcargo/blob/master/tests/sh/cargo-tree-deb-rec

Note that one may get cycles here, since cargo does not enforce acyclicity at this level, but only at the previous level that considers features. We have not yet encountered a cycle, but your algorithm needs to be able to handle it without crashing. If we do encounter such a cycle, we need to use the build_depends_excludes feature of debcargo.toml to break the cycle and then modify our cargo build test run with --no-default-features and only enable the corresponding features.

Now, we actually need to take this one step further. For a given source package to enter Debian Testing after Debian Unstable, it is necessary to get all binary runtime dependencies of all of its features into Debian, since they all have to be installable by users. This gives yet another bigger set:

rust-S # builds:
librust-S+default-dev
 |- librust-A+noB-dev # But to actually get this into Debian Testing we need to package:
    rust-A # which additionally builds:
    librust-A+default-dev
     |- librust-B+whatever-dev # But to actually get this into Debian Testing we need to package:
        rust-B # which additionally builds:
        librust-B+default-dev
         |- etc, recursively
        librust-B+moreshinyextras-dev
         |- etc, recursively
    librust-A+someshinyextras-dev
     |- librust-C+whatever-dev # But to actually get this into Debian Testing we need to package:
        rust-C # which additionally builds:
        librust-C+default-dev
         |- etc, recursively
        librust-C+evenmoreshinyextras-dev
         |- etc, recursively
librust-S+lotsofshinystuff-dev
 |- librust-E+whatever-dev
     |- etc, you get the idea
 |- librust-F+whatever-dev
     |- etc, you get the idea
 |- etc, you get the idea

So it would be good if we could print this tree as well. We have actually seen cycles on this level, which is why we normally only run cargo build and not cargo build --all-features - e.g. see sfackler/cargo-tree#34

In summary we have three types of "dependencies":

• cargo normal resolution, feature-based
  • A+X -> B+Y if the former depends or build-depends on the latter according to Cargo.toml
  • cycles are not possible since this is enforced by cargo
• "default features" transitive resolution needed for Debian Unstable
  • A ->> B iff A+default -> B+y for some y
  • cycles theoretically possible, none yet seen
  • cycles have to be eliminated in Debian since these are Build-Depends cycles
• "all features" transitive resolution needed for Debian Testing
  • A ->>> B iff A+x -> B+y for some x, y
  • cycles possible and seen in the wild
  • cycles do not affect anything in Debian

[infinity0]

As for implementation, it may or may not be easy to hook into cargo's normal resolution mechanism. What I did in the hacky script linked above is to run the normal resolution mechanism (via cargo tree) then go through the resulting list of crates C and re-run the script but against the default feature set of each crate, and repeat this process recursively omitting duplicates. This however loses all tree structure, but it was enough for our purpose of getting stuff into Debian Unstable.