Tracking Issue for try_reserve method on more containers

[TennyZhuang]

This is another tracking issue for the try_reserve part of the RFC "fallible collection allocation" (rust-lang/rfcs#2116).
The feature gate for the issue is #![feature(try_reserve_2)].

The feature is a follow-up to #48043. Since try_reserve was stabilized in 1.57.0, we may need a new feature gate for further try_reserve implementation on more containers.

About tracking issues

Tracking issues are used to record the overall progress of implementation.
They are also used as hubs connecting to other relevant issues, e.g., bugs or open design questions.
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.

Steps

• Implement try_reserve and try_reserve_exact on BinaryHeap add BinaryHeap::try_reserve and BinaryHeap::try_reserve_exact #91529
• Implement try_reserve and try_reserve_exact on PathBuf std: Implement try_reserve and try_reserve_exact on PathBuf #92513
• Implement try_reserve and try_reserve_exact on OsString Add try_reserve and try_reserve_exact for OsString #92338
• Adjust documentation (see instructions on rustc-dev-guide)
• Stabilization PR (see instructions on rustc-dev-guide)

If any containers were missing, please comment in the issue, and I will add it to the list.

Unresolved Questions

Implementation history

#91529
#92338
#92513

[Xuanwo]

After a diff between https://doc.rust-lang.org/std/?search=reserve and https://doc.rust-lang.org/std/?search=try_reserve, I think the current list is complete.

[Xuanwo]

I'm interested in implement try_reserve and try_reserve_exact on PathBuf.

[Xuanwo]

@TennyZhuang Please help update the issue link into description: #92338

[Xuanwo]

And the support of PathBuf will be based on work #92338, I will continue it after this PR get merged.

[Xuanwo]

@TennyZhuang #92513 has been submitted for review. Let's go forward the stabilization!

[Xuanwo]

Let's stabilize this feature! Steps are listed here:

From https://rustc-dev-guide.rust-lang.org/stability.html#stabilizing-a-library-feature

• Ask a T-libs-api member to start an FCP on the tracking issue and wait for the FCP to complete
• Change #[unstable(...)] to #[stable(since = "version")]
• Remove #![feature(...)] from any test or doc-test for this API
• Open a PR against rust-lang/rust
  • Add the appropriate labels: @rustbot modify labels: +T-libs-api.
  • Link to the tracking issue and say "Closes #XXXXX".

[Xuanwo]

@yaahc Hi, can you help start an FCP for feature try_reserve_2?

[yaahc]

Absolutely!

@rfcbot merge

[rfcbot]

Team member @yaahc has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se
• @yaahc

Concerns:

• do we need better docs about what the argument value means (not bytes) resolved by Tracking Issue for try_reserve method on more containers #91789 (comment)

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[dtolnay]

It's worth being aware that the OsString version of these methods is extremely weird, and probably not adequately documented about how weird it is. In particular the following "obvious" code is not correct, but it seems likely that almost every caller would fall into this trap unless there is very clear guidance on how to use the method correctly.

fn os_string_push_str(buf: &mut OsString, data: &str) -> Result<(), TryReserveError> {
    buf.try_reserve(data.len())?;
    buf.push(data);
    Ok(())
}

The units in which string length is measured, and the units in which OsString capacity is measured, are in general totally different units.

Quoting from elsewhere in the OsString docs:

As discussed in the OsString introduction, OsString and OsStr store strings in a form best suited for cheap inter-conversion between native-platform and Rust string forms, which may differ significantly from both of them, including in storage size and encoding.

This is saying that the "storage size" of an OS string (which is the size that len returns, and the same units as the additional arg of try_reserve) "may differ significantly" from the storage size of the "Rust string form" of the same data, i.e. that os_str.len() and os_str.to_str().unwrap().len() may differ significantly.

@rfcbot concern do we need better docs about what the argument value means (not bytes)

[TennyZhuang]

It's worth being aware that the OsString version of these methods is extremely weird, and probably not adequately documented about how weird it is. In particular the following "obvious" code is not correct, but it seems likely that almost every caller would fall into this trap unless there is very clear guidance on how to use the method correctly.

I definitely agree that OsString::try_reserve is very easy to be used incorrectly, but I think the problem already exists due to the with_capacity API. Users may also got wrong results while they use with_capacity from another type’s len().

[dtolnay]

I agree that with_capacity also needs to be better explained. That function is from 2016 when our standards were lower. 😉

[Xuanwo]

I will start PRs to address the concern that @dtolnay proposed.

• Add better docs for OsString::try_reserve about what the argument value means
• (Maybe) Polish the docs for OsString::with_capacity too ?

[m-ou-se]

This is saying that the "storage size" of an OS string "may differ significantly" from the storage size of the "Rust string form" of the same data.

We should probably just update that documentation. We already guarantee any &str can be turned into a &OsStr through AsRef, so there's not much room for doing anything other than representing str data exactly as is in an OsStr, with the same length. So your example snippet will work fine. The only space left for 'surprises' is how many units/bytes unmatched UTF-16 surrogate pair halves take on Windows.

[Xuanwo]

Sorry for stalling this work for so long; I'll take care of all the concerns next week.

[dtolnay]

#91789 (comment) sounds good to me. I would be prepared to accept (with libs-api FCP) a PR that updates all the places talking about OS string capacity to indicate that this means UTF-8 byte size for OS strings which were created from valid unicode, and not otherwise specified for other contents.

[Xuanwo]

Great, please take a look at #95392

[joshtriplett]

#97202

[dtolnay]

@rfcbot resolve do we need better docs about what the argument value means (not bytes)

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[Stargateur]

look like BTreeSet::try_reserve have been forgotten too.

Don't know what would be the plan for LinkedList

[Xuanwo]

look like BTreeSet::try_reserve have been forgotten too.

Don't know what would be the plan for LinkedList

IMHO, we need a proposal to discuss adding reserve for BTressSet and LinkedList first.

[TennyZhuang]

BTreeSet and LinkedList are pointer-based data structure, which means that they can't benefit from batch allocation. The reserve method on them is exactly same as just allocate one by one, but will make the code much more complicated (we have to introduce placeholder nodes for that).

[Stargateur]

ah I get fouled by https://doc.rust-lang.org/src/core/iter/traits/collect.rs.html#379

these two collections probably need something like try_push() instead.