Implementing a "cautious" take_while using Peekable

Question

I'd like to use Peekable as the basis for a new cautious_take_while operation that acts like take_while from IteratorExt but without consuming the first failed item. (There's a side question of whether this is a good idea, and whether there are better ways to accomplish this goal in Rust -- I'd be happy for hints in that direction, but mostly I'm trying to understand where my code is breaking).

The API I'm trying to enable is basically:

let mut chars = "abcdefg.".chars().peekable();

let abc : String = chars.by_ref().cautious_take_while(|&x| x != 'd');
let defg : String = chars.by_ref().cautious_take_while(|&x| x != '.');

// yielding (abc = "abc", defg = "defg")

I've taken a crack at creating a MCVE here, but I'm getting:

:10:5: 10:19 error: cannot move out of borrowed content :10 chars.by_ref().cautious_take_while(|&x| x != '.');

As far as I can tell, I'm following the same pattern as Rust's own TakeWhile in terms of my function signatures, but I'm seeing different different behavior from the borrow checker. Can someone point out what I'm doing wrong?

rodrigo · Accepted Answer · 2015-02-28T02:15:41.593

The funny thing with by_ref() is that it returns a mutable reference to itself:

pub trait IteratorExt: Iterator + Sized {
    fn by_ref(&mut self) -> &mut Self { self }
}

It works because the Iterator trait is implemented for the mutable pointer to Iterator type. Smart!

impl<'a, I> Iterator for &'a mut I where I: Iterator, I: ?Sized { ... }

The standard take_while function works because it uses the trait Iterator, that is automatically resolved to &mut Peekable<T>.

But your code does not work because Peekable is a struct, not a trait, so your CautiousTakeWhileable must specify the type, and you are trying to take ownership of it, but you cannot, because you have a mutable pointer.

Solution, do not take a Peekable<T> but &mut Peekable<T>. You will need to specify the lifetime too:

impl <'a, T: Iterator, P> Iterator for CautiousTakeWhile<&'a mut Peekable<T>, P>
where P: FnMut(&T::Item) -> bool {
     //...
}

impl <'a, T: Iterator> CautiousTakeWhileable for &'a mut Peekable<T> {
    fn cautious_take_while<P>(self, f: P) -> CautiousTakeWhile<&'a mut Peekable<T>, P>
     where P: FnMut(&T::Item) -> bool {
        CautiousTakeWhile{inner: self, condition: f,}
    }
}

A curious side effect of this solution is that now by_ref is not needed, because cautious_take_while() takes a mutable reference, so it does not steal ownership. The by_ref() call is needed for take_while() because it can take either Peekable<T> or &mut Peekable<T>, and it defaults to the first one. With the by_ref() call it will resolve to the second one.

And now that I finally understand it, I think it might be a good idea to change the definition of struct CautiousTakeWhile to include the peekable bit into the struct itself. The difficulty is that the lifetime has to be specified manually, if I'm right. Something like:

struct CautiousTakeWhile<'a, T: Iterator + 'a, P> 
    where T::Item : 'a {
    inner: &'a mut Peekable<T>,
    condition: P,
}
trait CautiousTakeWhileable<'a, T>: Iterator {
    fn cautious_take_while<P>(self, P) -> CautiousTakeWhile<'a, T, P> where
        P: FnMut(&Self::Item) -> bool;
}

and the rest is more or less straightforward.

Thanks @rodrigo! I've incorporated your first suggestion to produce a working example at http://is.gd/NalTYL. But when I try to bring the typing into the struct, as in http://is.gd/6c64vf, I get `error: the trait *core::clone::Clone* is not implemented for the type *&mut core::iter::Peekable*`, which I can't seem to overcome by adding `+ Clone` to the trait bounds in line 43. — Bosh, Feb 28 '15 at 02:39
@Bosh. Not sure, but I think that a mutable pointer cannot be cloned. Your variant accepts the `Clone` probably because `Peekable` implents `Clone` explicitly. Maybe you can do the same, but the code would need some refactoring... — rodrigo, Feb 28 '15 at 02:47
Great. I stopped deriving from `Clone` and cleaned up timelines: http://is.gd/ljjJAE . Thanks again for your help + explanations! — Bosh, Feb 28 '15 at 03:01
@Bosh: Glad to help, I learned a lot too. It looks that your original version accepted the `#[derive(clone]` because for parametric types the compiler accepts the directive if it cannot prove that it will never work. But then, it may silently fail to do so in a specific type. For example `#derive(Clone)] struct X(T);` will compile, but the actual `X::clone()` will be available only if `T` is clonable. — rodrigo, Feb 28 '15 at 03:12

score 1 · Answer 2 · edited May 23 '17 at 11:43

This was a tricky one! I'll lead with the meat of the code, then attempt to explain it (if I understand it...). It's also the ugly, unsugared version, as I wanted to reduce incidental complexity.

use std::iter::Peekable;

fn main() {
    let mut chars = "abcdefg.".chars().peekable();

    let abc: String = CautiousTakeWhile{inner: chars.by_ref(), condition: |&x| x != 'd'}.collect();
    let defg: String = CautiousTakeWhile{inner: chars.by_ref(), condition: |&x| x != '.'}.collect();
    println!("{}, {}", abc, defg);
}

struct CautiousTakeWhile<'a, I, P> //'
    where I::Item: 'a, //'
          I: Iterator + 'a, //'
          P: FnMut(&I::Item) -> bool,
{
    inner: &'a mut Peekable<I>, //'
    condition: P,
}

impl<'a, I, P> Iterator for CautiousTakeWhile<'a, I, P>
    where I::Item: 'a, //'
          I: Iterator + 'a, //'
          P: FnMut(&I::Item) -> bool
{
    type Item = I::Item;

    fn next(&mut self) -> Option<I::Item> {
        let return_next =
            match self.inner.peek() {
                Some(ref v) => (self.condition)(v),
                _ => false,
            };
        if return_next { self.inner.next() } else { None }
    }
}

Actually, Rodrigo seems to have a good explanation, so I'll defer to that, unless you'd like me to explain something specific.

Implementing a "cautious" take_while using Peekable

2 Answers2

Linked