Feature graph support for Cargo tree

[m-mueller678]

Problem

I have a large dependency tree and want to figure out why a transitive dependency is included, which is optional based on features. I had assumed that is what cargo tree -e features is for, but apparently that is not quite what it does. See this related discussion.

To give a brief summary: I use the datafusion crate, which depends on many datafusion-* crates. Many of these datafusion-* crates depend on the parquet crate. Some of them depend on the feature parquet/encryption, which causes parquet to depend on ring. The tree shows that datafusion-common depends on parquet, which in turn depend on ring. However, datafusion-common does not enable the parquet/encryption feature. So, the tree suggests that ring is included as a result of using datafusion-common. It is actually enabled because of datafusion-datasource, which enables parquet/encryption. In the tree, ring does not show up as a child of datafusion-datasource (I do not know why).

The full tree is here.

Proposed Solution

I think there should be an option to output a feature dependency tree (or probably DAG). In this graph, the nodes would be either features of crates or crates themselves (with no default features enabled). The edges would be either:

• from feature A/a to feature B/b if feature a of crate A depends on feature b of its dependency crate B
• from feature A/a to crate B if A optionally depends on B for its a feature
• from crate A to feature B/b if A non-optionally depends on B/b
• from create A to crate B if A non-optionally dependends on B
• from feature A/a to feature A/b of the same feature depends on another feature of the same crate.

I am unsure if all features A/a should also have a dependency on the crate A itself, or if that is unnecessary noise.

This is actually the output format I would have expected from cargo tree -e features. I don't know if changing it to this new format now would be a good idea, so I filed this as a feature request rather than a bug report.

Notes

I think some of the confusion in #14263 may be related to this, but I did not look into that issue too closely.

[epage]

Summarizing your inverted output

ring v0.17.14
├── ring feature "alloc"
│   └── ring feature "std"
│       └── parquet v56.2.0
│           ├── parquet feature "arrow"
│           ├── parquet feature "encryption"
│           │   └── datafusion-datasource v50.1.0 (*)

I believe what is happening is packages have edges to features and those have edges to the core package which then has edges to the dependencies. This ends up representing what is being built (parquet with all of these dependencies) though I can see how it would be nice to have more direct connections between parquet feature "encryption" and ring.

Could you provide example output of what you were expecting so I can better understand it?

[m-mueller678]

Note that the inverted output I posted was for the simplified dependency list where I depend on datafusion-datasource directly, rather than datafusion. This is the inverted tree for the larger tree, just for completeness.

For the inverted output I was expecting something like this:

ring v0.17.14
 └── parquet feature "encryption"
      ├── datafusion-datasource v50.1.0 (*)
      ├── (possibly others)
	 ...

I am unsure on what the (possibly others) would be, I do not actually fully understand which of the involved crates depend on the encryption feature. But it should only include crates and features which actually need the encryption feature. For example it should not include datafusion-common v50.1.0. But if I were to enable the datafusion-common/parquet-encryption feature, then datafusion-common feature "parquet-encryption" should appear as a new child, but still not datafusion-common v50.1.0.

parquet v56.2.0 should appear nowhere in this tree, as the parquet crate itself does not require ring, only its encryption feature does. parquet feature "encryption" should be the only direct child of ring v0.17.14.

Maybe ring feature "std" could also appear as a child of ring v0.17.14. It should be accessible somehow, but I am not sure if it should appear on this tree, or if it should only appear if you ask for something like cargo tree -e features -i ring/std. If it should be here, then it should be something like this:

ring v0.17.14
ring feature "std"
├── parquet feature "encryption"
│    ├── datafusion-datasource v50.1.0 (*)
│    ├── (possibly others)
│   ...
├── ring feature "alloc"
│    ├── ring feature "std" 
│    │    └── parquet feature "encryption" (*)
│    └── parquet feature "encryption" (*)
└── ring feature "std" (*)

Now having typed it out, I think it should probably be not included, instead have it only as a separate tree that you can ask for instead of asking for -i ring. Anything that would depend on ring feature "std" would also depend on ring v0.17.14, so for the purpose of finding the cause of ring v0.17.14 being included, this only adds noise.

[m-mueller678]

Basically the inverted tree should give me this guarantee: To remove something from your dependency tree, you need to remove all its leaf node children (which will all be crates you directly depend on and their features you directly depend on). Any dependency (crate or feature) you could keep while still getting rid of the tree root should not appear in the tree.