Could rustdoc annotate complexity?

[i30817]

I liked using glazedlist javadocs because their documentation had a simple O(n) notation for concrete implementations of datastructures
(ex : http://publicobject.com/glazedlists/glazedlists-1.8.0/api/ca/odell/glazedlists/BasicEventList.html )

I wonder if it would be possible to generalize this sort of thing into the doc tool, and maybe to infer the minimum complexity of a new piece of code (composition)?

I don't know if it is feasible

[bblum]

I can't speak to inferring, which seems hard, but I'd like to see complexity written in the rustdoc for our libraries. (Haskell's docs do this admirably.) I started doing this with dlist.rs.

[catamorphism]

Inferring would be very hard (unsolved research problem). Having a rustdoc field for it seems pretty straightforward.

[Aatch]

Having a field is fine, but still just nice-to-have, no milestone.

[emberian]

Absorbing this for rustdoc2

[emberian]

#8125

/cc @Seldaek

I see this implemented purely in the doc comments, using markdown:

## Complexity

Space    Time
-----    ----
O(n)    O(n^2)

[Seldaek]

If it's markdown, it'll render as markdown, I don't need to do anything :)

[emberian]

I'm going to close this, since I don't think more special-casing of certain things in the doc comment is desirable. You can add whatever docs you want in the markdown.

[Kerollmops]

Just for information, criterion.rs can probably help to achieve this kind of inference, I find some informations about Google Benchmarks doing such detections.

Criterion.rs is an external crate so it will probably be difficult to inject the inferred complexity into the documentation at doc compilation time, but... I put this here.