Tracking Issue for APC #316: In-place case change methods for String

[krtab]

Feature gate: #![feature(string_make_uplowercase)]

This is a tracking issue for APC #316

This APC proposes that a new API is added to String to change cases and do so efficiently by consuming self and reusing the buffer, not allocating in most cases.

The exact implementation remains to be discussed, but the idea would be that in cases where it is possible, the case change is done in place. Once that isn't possible, a auxiliary DE-queue can be used to store bytes temporarily.

Public API

This would add the following methods (names to be determined)

impl String {
	fn into_uppercase(&mut self);
	fn into_lowercase(&mut self);
}

Steps / History

• Implementation: Implement String::make_(upp|low)ercase #135888
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• None yet.

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[krtab]

@rustbot claim

[clarfonthey]

Commenting this here specifically for the implementation since I know that the initial PR isn't focused on performance, but this should always be doable without an extra queue if you compute the necessary length in advance, and I feel like it should be possible to do this while still preserving a fast path for the case where the length doesn't change.

Essentially, keep a signed difference in length and skip characters which would increase that signed length above zero. (If we reduce length at some point and then add more back up to zero, that's okay.) Also keep track of the index of the first character this occurs for.

Then, if you do have that length above zero at the end, then write backwards from the end of the string until the first character that wasn't right, now that you know its absolute position.

My assumption that this would be as fast as the queue version at least, since you would still need to copy all the characters from the queue back into the string, but in this version, you're instead copying them from the string to itself.

I can probably write up some code for this later so it can actually be benchmarked and compared to other options. Also because my explanation may not be clear.

[krtab]

Thanks for your interest.

I am not sure I have well understood your explanations. Feel free to contact me on rust lang's zulip if you want to discuss further, either by DM or in this topic: https://rust-lang.zulipchat.com/#narrow/channel/219381-t-libs/topic/In.20place.20String.20case.20change.

[clarfonthey]

My explanation could definitely use more work; I've shared the code for an implementation that you can read in Zulip.

We should continue the discussion on Zulip, but I figured I'd mention this here just to tie that thread for anyone reading.