API Docs: collections

[steveklabnik]

Part of #29329

http://doc.rust-lang.org/std/collections/

This will probably need to be tackled in pieces.

[Gankra]

What needs to be done here? Just cleanup?

[steveklabnik]

Yeah, overall, these bugs are like "Steve's eye of Sauron will check the entire standard library at least once."

I haven't actually looked at collections' docs lately, but sample things are like:

1. make sure everything is following doc conventions
2. make sure everything has examples
3. make sure everything is explained well

I don't have any specific goals yet.

[nathankleyn]

As discussed on this Rust subreddit thread, I'll also try to help out by adding some more examples for using the entry API to update/modify a HashMap et al.

[apasel422]

@steveklabnik Some things I've noticed that are relevant to this:

• The use of "create" vs "make" for constructors
• The use of unconventional first lines for iterator-returning methods, e.g. "An iterator visiting all keys in arbitrary order. Iterator element type is &'a K." vs "Gets an iterator over the entries of the map."
• The use of both "element" and "value"

[wthrowe]

The blurb on complex keys in the map insert methods isn't clear that it's talking about complex keys:

If the map did have this key present, that value is returned, and the entry is not updated. See the module-level documentation for more.

It's the key that is not updated. The value is updated. The linked module-level documentation makes this clear.

[nathankleyn]

@steveklabnik I've raised the above (long overdue!) PR, which you've been as quick as lightning and already looked at! Are there any other particular parts of the collection APIs that need attention in terms of examples, etc. that I can have a look at? Would be good to perhaps put together a checklist of stuff that needs some work so we can pick them off in bits.

[steveklabnik]

In general, every single method and function should have an example, as a baseline. I haven't dug into the collections docs in a while, so I don't have a ton of details about specifics right now, but that's at least the baseline.

[nathankleyn]

Okay awesome, I might start going through some of them and will add the ones I've checked back here for reference. 👍

[steveklabnik]

That'd be spectacular.

[nathankleyn]

Okay, have been through the collection docs and here's the ones that need checking (ie. they actually have methods/functions and are not just trait implementations). I'm going to try and raise PRs separately for each of these things to add at least the missing examples for now.

Top level structs:

• BTreeMap -> PR Add missing documentation examples for BTreeMap. #32135
• BTreeSet -> PR Add missing documentation examples for BTreeSet. #32136
• BinaryHeap -> PR Add missing documentation examples for BinaryHeap. #32137
• HashMap -> PR Add examples of the Entry API to the HashMap documentation. #31035
• LinkedList
• VecDeque

Collection specific structs:

• btree_map::OccupiedEntry
• btree_map::VacantEntry
• btree_map::Entry
• hash_map::OccupiedEntry
• hash_map::VacantEntry
• hash_map::RandomState
• hash_map::Entry

[steveklabnik]

Don't worry about unstable things. It's not worth the time, since they are unstable.

I plan on going back through after each release and writing docs for things as they become stable; it's just too early in my overall pass through to worry about yet.

On Jan 20, 2016, 16:53 -0500, Nathan Kleynnotifications@github.com, wrote:

Okay, have been through the collection docs and here's the ones that need checking (ie. they actually have methods/functions and are not just trait implementations:

Top level structs:

BTreeMap(http://doc.rust-lang.org/std/collections/struct.BTreeMap.html)
BTreeSet(http://doc.rust-lang.org/std/collections/struct.BTreeSet.html)
BinaryHeap(http://doc.rust-lang.org/std/collections/struct.BinaryHeap.html)
HashMap(http://doc.rust-lang.org/std/collections/struct.HashMap.html)
HashSet(http://doc.rust-lang.org/std/collections/struct.HashSet.html)
LinkedList(http://doc.rust-lang.org/std/collections/struct.LinkedList.html)
VecDeque(http://doc.rust-lang.org/std/collections/struct.VecDeque.html)
Bound(http://doc.rust-lang.org/std/collections/enum.Bound.html)(Unstable; does this need doing?)

Collection specific structs:

btree_map::OccupiedEntry(http://doc.rust-lang.org/std/collections/btree_map/struct.OccupiedEntry.html)
btree_map::VacantEntry(http://doc.rust-lang.org/std/collections/btree_map/struct.VacantEntry.html)
btree_map::Entry(http://doc.rust-lang.org/std/collections/btree_map/enum.Entry.html)
hash_map::OccupiedEntry(http://doc.rust-lang.org/std/collections/hash_map/struct.OccupiedEntry.html)
hash_map::VacantEntry(http://doc.rust-lang.org/std/collections/hash_map/struct.VacantEntry.html)
hash_map::RandomState(http://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html)
hash_map::Entry(http://doc.rust-lang.org/std/collections/hash_map/enum.Entry.html)
hash_state::HashState(http://doc.rust-lang.org/std/collections/hash_state/trait.HashState.html)(Unstable; does this need doing?)

—
Reply to this email directly orview it on GitHub(#29348 (comment)).

[GuillaumeGomez]

All done.

[gnzlbg]

I would like to reopen this issue since I think the documentation of the std::collections still leaves a lot to be desired.

In particular, it lacks enough rigor to make informed decisions about using the collections and their methods. In my opinion, and independently of how repetitive it is, the documentation of each method should have the following "fields":

• Algorithmic complexity: with big O in terms of the relevant operations (which can be multiple: memory allocations in terms of N, copies in terms of M, stating what N and M are, swaps, comparisons, hashing...), with exact number of operations when guaranteed (performs exactly N moves, performs exactly N swaps, ...), with an explanation of what amortized/expected complexity means for that particular operation, covering what happens in the amortized case and in the worst case.
• Memory complexity: does it use O(1) stack space? Is it recursive and it uses O(logN) stack space? Does it allocate memory using the system allocator? If so how much? Something like: "Requires O(1) stack space and allocates O(N) memory where N is x".
• Effects: What are the effects of the operation?
  • Example: Vec::push: before: size() == N, capacity == M, after: size() == N + 1, capacity == M (amortized case) or capacity == k*M (worst case).
  • Example: Vec::reserve(N): before: capacity() == M, after: capacity() == max(N, M).
• Panics: When is an operation supposed to panic?
  • Example: Vec::push panics if OOM.
  • Example: Vec::size never panics.

For a source of inspiration, the C++ standard is exemplary at documented all of these things. I really think that being more thorough with the documentation will help both find and fix bugs in the documentation and make the std library way better.

So IMO what remains to be done is:

• Achieve consensus on how to document the methods of the std library algorithms and collections.
• Explore if there is an easy way to reuse some documentation bits (e.g. OOM panics, never panics, explanation for amortized / expected complexity).
• Go (again) through all methods and document them rigorously.

Another thing I've found is that not all collections are mentioned in the main collections page (e.g. HashSet).

• Make sure that all collections are mentioned in all relevant sections of the main page (when to use, performance, ...).

Some examples of the current state of things:

• HashMap::insert doesn't even mention that insertions are O(1). Yes, this information might be in some other place of the documentation, but if I google for "Rust HashMap insert" I land there and would like to see all relevant information right away.
  • vec::insert requires amortized O(1) stack memory but in the worst case it requires O(kN) memory and O(N) moves (where k is an implementation defined growth-factor). This information should be explicit in the method documentation.
  • std::slice::sort complexity is O(NlogN) in the number of elements, but it mentions that it allocates approximately "2*n" elements. This is not too bad but "approximately" is too vague for my taste. Does that mean at worst 2N ? In particular, stable sorting algorithms like merge sort require 1/2N, and GrailSort requires O(1), so this leaves me wondering whether 2N is actually a bug in the documentation. If the rust std library would have an unstable sorting algorithms (which I could not find) implemented with something quicksort-based like intro-sort, it should say that it is "in place", that is, doesn't allocate extra memory, but uses O(logN) stack space.

EDIT: I ran into this when I wanted to see if it made sense to use HashSet for my application. I googled "Rust HashSet insert" and found the method, but had no idea what the complexity and memory allocations of the method were. Then I went to the collections main page, but again did not found this information... I think we can do better.

[GuillaumeGomez]

@gnzlbg: Good points. Since this issue is getting old, I propose to you to reopen it with your message directly. (and please cc me in it when it's done).