Doing `trim_matches` in-place on a `String`

help
1

I'm just playing around with making versions of the trim*/strip* family of functions that operate on a String by modifying it instead of returning a &str, and I'm running into an annoying problem.

When it comes to trim_matches, its signature is as follows:

pub fn trim_matches<'a, P>(&'a self, pat: P) -> &'a str
where
    P: Pattern<'a, Searcher: DoubleEndedSearcher<'a>>,

This works fine when you return a slice, but since I'm operating on a &mut String, I'm running into troubles with lifetimes, presumably due to variance. My method is

fn trim_matches_in_place<'a, P>(&'a mut self, pat: P)
where
    P: Pattern<'a>,
    <P as Pattern<'a>>::Searcher: DoubleEndedSearcher<'a>,
{
    let trimmed = self.trim_matches(pat);
    let (start_offset, end_offset) = get_str_offsets(self, trimmed);
    self.trim_start_bytes(start_offset);
    self.trim_end_bytes(end_offset);
}

and this is what the compiler tells me:

error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable
   --> src\string_extensions.rs:240:9
    |
233 |     fn trim_matches_in_place<'a, P>(&'a mut self, pat: P)
    |                              -- lifetime `'a` defined here
...
238 |         let trimmed = self.trim_matches(pat);
    |                       ----------------------
    |                       |
    |                       immutable borrow occurs here
    |                       argument requires that `*self` is borrowed for `'a`
239 |         let (start_offset, end_offset) = get_str_offsets(self, trimmed);
240 |         self.trim_start_bytes(start_offset);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

I think this is invariance coming to bite me in the ass, but it feels like the compiler is misunderstanding here, because once the call to trim_matches returns, that borrow is no longer needed. Is this solvable? I'd rather avoid unsafe if I can, but to me, this feels like there's something off about the way the trim_matches API works.

2

Try making the lifetimes of Pattern and &mut self different. I don't know if that will solve it, but it seems wrong anyway.

4

What is the signature of your get_str_offsets() function? I think that might be the culprit here, forcing trimmed to live longer than necessary.

5 
fn get_str_offsets(original: &str, changed: &str) -> (usize, usize)
6

These bounds (and signature) come from str::trim_matches; using something else than 'a either leads to the same error, or errors about a lifetime being too short.

If I make it <'s: 'a, 'a, P>(&'s mut self, pat: P), nothing changes, and if I try to use an anonymous lifetime (i.e. just &mut self) or one where 'a: 's, I get a variant of:

error: lifetime may not live long enough
   --> src\string_extensions.rs:238:23
    |
233 |     fn trim_matches_in_place<'a, P>(&mut self, pat: P)
    |                              --     - let's call the lifetime of this reference `'1`
    |                              |
    |                              lifetime `'a` defined here
...
238 |         let trimmed = self.trim_matches(pat);
    |                       ^^^^^^^^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'a`
7

Ah, now I see the issue. The trait bounds P: Pattern<'a> and <P as Pattern<'a>>::Searcher: DoubleEndedSearcher<'a> tell the compiler that P only works when given the entire 'a lifetime. We can avoid this issue by using a higher-ranked trait bound, to tell the compiler that the Pattern must work for any lifetime we give it.

fn trim_matches_in_place<P>(&mut self, pat: P)
where
    for<'a> P: Pattern<'a>,
    for<'a> <P as Pattern<'a>>::Searcher: DoubleEndedSearcher<'a>,
{
    let trimmed = self.trim_matches(pat);
    let (start_offset, end_offset) = get_str_offsets(self, trimmed);
    self.trim_start_bytes(start_offset);
    self.trim_end_bytes(end_offset);
}
4 Likes
8

You can use the fact that trim only truncates, and doesn't modify the string, so the length is all you need to know:

let len = string.trim_end_matches(pat).len();
string.truncate(len);

let len = string.trim_start_matches(pat).len();
string.replace_range(0..len, "");

But watch out for lifetimes, because Pattern borrows the whole string, so as long as the pattern exists, it's guaranteed to have reference to the original string unmodified. You can't do it in a method that takes a pattern, because at the time the function is called it will already borrow the string in an outer scope that outlives function call.

Given that Pattern is unstable, it'll be simpler to take a str instead.

1 Like
9

Wasn't a bad plan, but I figured it'd cause some kind of issue down the line; any attempt at using it like you would the regular str::trim_matches results in compiler errors like

error[E0277]: the trait bound `for<'a> <_ as Pattern<'a>>::Searcher: DoubleEndedSearcher<'a>` is not satisfied
   --> src\string_extensions.rs:136:25
    |
6   | s.trim_matches_in_place('1');
    |   --------------------- ^^^ the trait `for<'a> DoubleEndedSearcher<'a>` is not implemented for `<_ as Pattern<'a>>::Searcher`
    |   |
    |   required by a bound introduced by this call
    |
    = help: the following other types implement trait `DoubleEndedSearcher<'a>`:
              CharPredicateSearcher<'a, F>
              CharSearcher<'a>
              CharSliceSearcher<'a, 'b>
note: required by a bound in `trim_matches_in_place`
   --> string_extensions.rs:161:47
    |
161 |         for<'a> <P as Pattern<'a>>::Searcher: DoubleEndedSearcher<'a>;
    |                                               ^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `StringExtensions::trim_matches_in_place`
10

Right, so this odd behavior is what I had in mind when I asked/argued that "this feels like there's something off about the way the trim_matches API works" -- it seems weird to me that Pattern needs to borrow the &str past the call to trim_matches. Wouldn't you agree? It has already done its job and handed out the slice it was asked to make.

It's particularly egregious given that trim_matches takes the pattern by value -- it doesn't even exist anymore after the call returns!

11

I agree this is annoying. But it comes from the fact that borrow checker is based on interfaces, not on code.

When you say fn<'a>(&'a self, pat: impl Pattern<'a>) this means that Rust has to pick the same lifetime (same scope) for both self and Pattern, and this lifetime is an argument to this function (things in <> are arguments too!), so this lifetime has to be decided at the moment the function is called.

I am pleasantly surprised that solution proposed by @LegionMammal978 works. This deduction of what the actual lifetime should be based on rules I wouldn't expect borrow checker to be smart enough to deduce.

12

That's this issue or related. If you're explicit about the type of P, the compiler doesn't get lost.

It tends to be pretty ugly, but you can sometimes work around this by wiring up an effective trait wrapper that puts the bounds you need in places where they are always implied. Here that would be:

trait UsableDoubleEndedPattern<'a>
where
    // This supertrait bound is always inferred from the trait itself,
    // including the equality constraint
    Self: Pattern<
        'a, 
        Searcher = <Self as UsableDoubleEndedPattern<'a>>::UsableSearcher
    >,
{
    // Bounds on associated types can also be assumed by trait bounders
    type UsableSearcher: DoubleEndedSearcher<'a>;
}

And then wire it up wherever it can apply

impl<'a, T: ?Sized> UsableDoubleEndedPattern<'a> for T
where
    T: Pattern<'a>,
    <T as Pattern<'a>>::Searcher: DoubleEndedSearcher<'a>,
{
    type UsableSearcher = T::Searcher;
}

And then use your wrapper trait as the bound instead

    fn trim_matches_in_place<P>(&mut self, pat: P)
    where
        for<'a> P: UsableDoubleEndedPattern<'a>;

It got rid of the inference problems for the example at least.

2 Likes
13

Yep, this approach works. Thanks a lot! It's a bit unfortunate that it has to be done with additional "hack" traits, but at least it works. :smile: :+1:

14

Does it work, though? I tried it and it led to trait bound satisfaction errors as I mentioned in the reply above the one I made to yours.

15

The first link in my other reply shows that it does work, borrow checker wise, it's just inference that fails at the call site. The current compiler has difficulties around normalizing trait projections behind higher-ranked binders:

 ^^^ the trait `for<'a> DoubleEndedSearcher<'a>` is not implemented 
     for `<_ as Pattern<'a>>::Searcher`
//         ^ It hasn't figured out this must be `char` and can't
//           satisfy the bound for every possible type

If you turbofish the method so it knows upfront the generic is char, it works. But that's not only unergonomic but can't always work for unnameable types like (capturing) closures.

The message is misleading, since the trait is in fact implemented for the concrete type of the parameter you passed in. "The trait bound ... could not be solved" or something would be more accurate.

The wrapper trait approach solves the inference issue by removing the need to state a projection under a binder, and/by making it so that the desired bound on the associated type must hold for any implementor of the trait (thus it need not be reproved at the call site). Otherwise it's the asserting the same bound, just in a way that doesn't trip up the current compiler.

1 Like
16

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.