doc(cfg(a or b or c) and a) should cut unnecessary conditions

[ventaquil]

I tried this code:

#[doc(
    cfg(
        any(
            feature = "a",
            feature = "b",
            feature = "c",
        )
    )
)]
#[doc(
    cfg(
        feature = "a",
    )
)]
pub fn add(left: usize, right: usize) -> usize {
    left + right
}

I expected to see this happen after creating documentation:

Available on crate feature a only.

Instead, this happened:

Available on (crate features a or b or c) and crate feature a only.

Occured when one module requires any of few features and then submodules requires one of those features - module should list create features a or b or c but submodule should return only create feature a.

Meta

rustc --version --verbose:

rustc 1.67.0-nightly (a00f8ba7f 2022-11-15)
binary: rustc
commit-hash: a00f8ba7fcac1b27341679c51bf5a3271fa82df3
commit-date: 2022-11-15
host: x86_64-unknown-linux-gnu
release: 1.67.0-nightly
LLVM version: 15.0.4

[fmease]

@rustbot label T-rustdoc F-doc_cfg

(note that you typo'ed doc(cfg as cfg(doc(cfg in your reproducer)

[ventaquil]

Oh, agree 👍

My fault, original version was with cfg_attr(docsrs, doc(...)) and copy-paste-delete in the middle of night needs more checks against bugs 🐛

[ventaquil]

Also when I have feature that enables all of a, b and c together, name it just abc.

[features]
a = []
b = []
c = []
abc = ["a", "b", "c"]

Then

#[doc(
    cfg(
        feature = "abc",
    )
)]
pub mod abc {
    #[doc(
        cfg(
            feature = "a",
        )
    )]
    pub mod a {
        // ...
    }
}

It will produce.

Available on crate feature abc and crate feature a only.

Maybe it should return just it.

Available on crate feature a only.

[jyn514]

Note this is a major expansion of scope, it requires a full SMT solver.

[est31]

It is correct that it's an expansion of scope, but it seems that SMT solvers aren't enough for this: I am currently still reading the literature but it seems it's not even in NP (like SMT) but is Σ^P₂ - complete (a complexity class above NP).

The links I could find all relied on brute force which can be used less complex formulas but of course doesn't help with more complex ones:

• https://babbage.cs.qc.cuny.edu/courses/Minimize/
• https://research.swtch.com/boolean talks about a brute force approach that might be useful for small numbers of literals

For, SMT solvers there exist really performant Rust implementations, so we could just have used them as a library, but seems here we can't use them.

That being said, rustdoc is putting these notices all over the place so one should at least expect it to be able to do simple minimizations of the formula even if those don't arrive at the maximum possible level of minimization. Yes, it requires heavily algorithmic work. But the general skillset is present in Rust, and rustc is doing a lot of algorithmic stuff already in the type and borrow checkers (among others).

[jyn514]

I am very concerned about adding large new features like that in rustdoc, especially without an RFC. The people working on the compiler are not the same people working on rustdoc (and historically it's been very hard to get the two to share knowledge).

[est31]

Fair points on the two groups of people being different. As for needing an RFC, a transformation of the form (a or b or c) and a -> (b or c) and a is trivial to implement, this shouldn't need an RFC imo. The Cargo.toml thing is harder as rustdoc would need the information about features implying each other passed to it via params. That might need an RFC indeed.

[ventaquil]

Referring to WolframAlpha (a or b or c) and a should return just a.

https://www.wolframalpha.com/input?i=simplify+%28a+or+b+or+c%29+and+a

[est31]

oh right good point. if a is false, then it's false, and if a is true then it's true. Anyways, it's easy to implement a few rules like these and apply them until a fix point is reached.

[Kixunil]

Wouldn't it be better to issue a warning in cases like this that some conditions do nothing? If someone wrote such condition it seems more likely it wasn't intended to contain contradictions or unused conditions. "Only for simple cases" still applies.

[est31]

I think it would be a good idea to have both, and have the doc elimination be a bit more aggressive than the warning. For example, you could have sth like:

#[cfg(any(feature = "foo", feature = "bar", feature = "baz"))]
pub mod hi {
    // Something common to feature foo, bar and baz
    
    // Something only bar has
    #[cfg(feature = "bar")]
    pub fn bar_only () {}
}

Here, without simplifications, bar_only would have doc(cfg(and(any(foo, bar, baz), bar)) which could be simplified to doc(cfg(bar)). But you shouldn't warn about it, because hi might contain other code that is common to bar, foo and baz, and bar_only might really be limited to bar.

[Kixunil]

@est31 yes, that's a good example where warning is not suitable but simplification is. If one accidentally used all instead of any then a warning like this would be helpful:

warning: bar_only is already gated on feature= "bar" in the module hi

[est31]

@Kixunil indeed that's one of the cases where the warning (i guess it would be a lint) would be useful. I think having both would be good, it's just not that warnings can provide a full replacement for doing it in rustdoc. Even in the instance where we issue a warning, rustdoc should still provide the simplification.

I think however that the two things, the warning and the rustdoc simplification, could share code, and if there is ever an implementation of the "feature foo implies bar" stuff, then they could both use the same CLI parameters. so the design/implementation burden on rustdoc would be minimized, which would also help with @jyn514 's concerns I think.

[est31]

Clippy's nonminimal_bool and overly_complex_bool lints use the quine mc cluskey algorithm from this repository.

Edit: the original PR was rust-lang/rust-clippy#790, it contains some discussion about the repository.

More reading can be found in the 2018 paper Consistency Cubes: a fast, efficient method for exact Boolean minimization. by A. Dusa. It contains this very interesting quote:

In the world of Boolean minimization, the acknowledged champion software is Espresso (Brayton et al., 1984), built more than three decades ago at the University of California, Berkeley

Espresso's wikipedia page: link.

---

Regardless of this very interesting rabbit hole, for the concrete use in rustdoc, I think the best path forward would be to use the quine-mc_cluskey crate written by @oli-obk. It's used in clippy already in warn-by-default lints so should be proven to work. Maybe one could do some interning of the input formula so that the optimization is not done multiple times for the same formula. It shouldn't be hard to implement this.

As a second step, one can add the lint, either in rust directly or in clippy where the nonminimal_bool lint also lives.

[est31]

Looking closer at the quine-mc_cluskey crate and the booleans.rs file in clippy, it seems that there is some code around the usage of the quine-mc_cluskey crate. it's also limited to 8 variables only, as above that, performance starts to get really bad (it's an exponential algorithm due to the complexity mentioned above). There is also some filtering logic to check the output for solutions that contain a terminal more times than in the original version.

I've also filed a PR to make the crate a bit more up to date: oli-obk/quine-mc_cluskey#5

[oli-obk]

We could definitely move some of the logic to the qmm crate and look into adding a generic API that avoids having to do the translation fully manually