In-place String::replace_first and String::replace_last

[zachs18]

Proposal

Problem statement

When replacing a substring a single time in a string, currently we can use str::replacen(haystack, needle, replacement, 1). However, this returns a newly allocated String, which may be inefficient if our original haystack was already in a String, and we are intending to overwrite it with the newly created String. In such a case, one can manually find the matched range of the needle in the haystack, and then use String::replace_range to replace the needle with the replacement in-place.

fn replace_first(haystack: &mut String, needle: &str, replacement: &str) {
    let range = match haystack.match_indices(needle).next() {
        Some((start, match_str)) => start..start + match_str.len(),
        None => return,
    };
    haystack.replace_range(range, replacement);
}

Additionally, though this cannot be done with replacen, you can similarly replace the last instance of a pattern by using rmatch_indices instead of match_indices.

Motivating examples or use cases

// adapted from https://github.com/rust-lang/rust/blob/master/src/tools/clippy/clippy_lints/src/unit_types/unit_arg.rs#L169
let call_snippet_with_replacements = args_snippets
  .iter()
  .fold(call_snippet.to_owned(), |acc, arg| acc.replacen(arg.as_ref(), "()", 1)); // each iteration makes a new allocation
// could be
let mut call_snippet_with_replacements = call_snippet.to_owned();
for arg in args_snippets {
  call_snippet_with_replacements.replace_first(arg.as_ref(), "()");
}

// adapted from https://github.com/cross-rs/cross/blob/main/xtask/src/crosstool.rs#L339-341
contents = contents
  .replacen("%CT_GCC_V%", &ct_gcc_v, 1) // this makes a new allocation
  .replacen("%CT_GCC%", &ct_gcc, 1); // this makes a new allocation
// could instead be
contents.replace_first("%CT_GCC_V%", &ct_gcc_v); // these avoid making a new allocation if possible
contents.replace_first("%CT_GCC%", &ct_gcc);

// adapted from https://github.com/rust-lang/rust-clippy/blob/master/clippy_utils/src/sugg.rs#L869
let sugg = format!("{}{end_snip}", self.suggestion_start);
if self.closure_arg_is_type_annotated_double_ref {
  sugg.replacen('&', "", 1)
} else {
  sugg
}
// could be
let mut sugg = format!("{}{end_snip}", self.suggestion_start);
if self.closure_arg_is_type_annotated_double_ref {
  sugg.replace_first('&', "");
}
sugg

Other places with something essentially equivalent to string = string.replacen(pattern, replacement, 1);

• https://github.com/rust-lang/rust/blob/master/src/librustdoc/html/format.rs#L354

Solution sketch

// in alloc::string::String
impl String {
  pub fn replace_first<P: Pattern>(&mut self, pattern: P, replacement: &str);
  pub fn replace_last<P: Pattern>(&mut self, pattern: P, replacement: &str)
    where for<'a> P::Searcher<'a>: ReverseSearcher<'a>;
}

Alternatives

Users could use the more general str::replacen if allocation is not a bottleneck, or if the needle and replacement are not the same length and copying the haystack to a new allocation is faster than shuffling data around in one allocation.

Users could implement these manually in terms of existing String/str APIs (the implementations in rust-lang/rust#134316 use only the existing safe, stable APIs str::(r)match_indices and String::replace_range).

These could be fn(self) -> Self instead of fn(&mut self). This would make it difficult to perform on a mutably borrowed String: *string = std::mem::take(string).replace_first(...); vs string.replace_first(...);

These could be fn(&mut self) -> &mut Self to allow chaining multiple calls, but this might be less clear that it does not return a new String allocation.

The method names could include in_place or similar, to distinguish them from replace/replacen methods on str that are not in-place. There is already String::replace_range though, that is in-place but does not explicitly indicate this in its name.

@tgross35 mentioned on the implementation PR that it would make sense for there to also be an in-place str::replace alternative. If these are named replace_first_in_place, that would match nicely with a possible String::replace_in_place and/or String::replacen_in_place that do what str::replace/str::replacen do, but in-place.

Links and related work

Implementation PR: rust-lang/rust#134316

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[joshtriplett]

@BurntSushi Any thoughts or concerns about replace_in_place and replacen_in_place?

@zachs18 If we added replace_in_place and replacen_in_place, do you feel your use case would still benefit from also having replace_first and replace_last? (If you do that's perfectly fine, we just want to make sure that we're not being redundant and adding more than is needed.)

[zachs18]

String::replace_first would be somewhat redundant with replacen_in_place(..., 1), but replace_last would still require manually doing rmatch_indices etc. However, I didn't have any use-case or motivating example for replace_last specifically, I just added it since most _first methods in the stdlib have corresponding _last methods where possible. Because of that, and since it is possible to efficiently implement replace_last manually on stable regardless of if it is added to the stdlib, I have no strong opinion on keeping it.

[Amanieu]

@BurntSushi Any thoughts or concerns about replace_in_place and replacen_in_place?

ping @BurntSushi if you have any thoughts on this.