8

I'm learning Rust, and have decided to implement a piece table (described in section 6.4 of this pdf) since it's fairly simple, but non-trivial.

It's mostly been pretty straightforward, but I've run into one issue I'm not really able to figure out. Here's a simplified version of my code, for reference:

use std::ops::Index;

#[derive(Debug)]
pub struct PieceTable {
    // original file data: never changes
    orig_buffer: Vec<u8>,
    // all new data is pushed onto this buffer
    add_buffer: Vec<u8>,
    // the pieces that currently make up the file
    pieces: Vec<Piece>,
}

#[derive(Debug, Copy, Clone)]
enum Location {
    Orig,
    Add,
}

#[derive(Debug, Copy, Clone)]
struct Piece {
    // which buffer is this piece located at?
    buf: Location,
    // starting offset
    start: usize,
    // size of piece
    length: usize,
}

impl PieceTable {
    pub fn iter(&self) -> PieceTableIterator {
        PieceTableIterator::new(self)
    }

    fn piece_buf(&self, piece: &Piece) -> &Vec<u8> {
        match piece.buf {
            Location::Orig => &self.orig_buffer,
            Location::Add => &self.add_buffer,
        }
    }

    fn piece_value(&self, piece: &Piece, index: usize) -> &u8 {
        &self.piece_buf(piece)[index]
    }
}

pub struct PieceTableIterator<'a> {
    table: &'a PieceTable,
    buf_iter: Option<std::slice::Iter<'a, u8>>,
    piece_iter: std::slice::Iter<'a, Piece>,
}

impl<'a> PieceTableIterator<'a> {
    fn new(table: &PieceTable) -> PieceTableIterator {
        let mut iter = table.pieces.iter();
        let piece = iter.next();
        let buf_iter = piece.map(|p| table.piece_buf(p).iter());
        PieceTableIterator {
            table: table,
            buf_iter: buf_iter,
            piece_iter: iter,
        }
    }
}

impl<'a> Iterator for PieceTableIterator<'a> {
    type Item = u8;

    fn next(&mut self) -> Option<u8> {
        if self.buf_iter.is_none() {

            return None;
        }
        match self.buf_iter {
            Some(ref mut iter) => {
                iter.next()
                    .or_else(|| {
                        self.piece_iter.next().and_then(|p| {
                            let mut buf = self.table.piece_buf(p)[p.start..(p.start + p.length)]
                                              .iter();
                            let item = buf.next();
                            self.buf_iter = Some(buf);
                            item
                        })
                    })
                    .map(|b| *b)
            }
            None => None,
        }
    }
}

fn main() {
    let table = PieceTable {
        orig_buffer: vec![1, 2, 3],
        add_buffer: vec![4, 5, 6],
        pieces: vec![Piece {
                         buf: Location::Orig,
                         start: 0,
                         length: 2,
                     },
                     Piece {
                         buf: Location::Add,
                         start: 0,
                         length: 3,
                     },
                     Piece {
                         buf: Location::Orig,
                         start: 2,
                         length: 1,
                     }],
    };
    // shoud print 1, 2, 4, 5, 6, 3
    for i in table.iter() {
        println!("{}", i);
    }

}

(Playground)

I'm trying to build an iterator for this structure. I could do it very inefficiently by just keeping an index in the iterator, but then for each .next() call, I'd have to iterate over all of the pieces. Instead I'd rather have my iterator store an iterator for the pieces and an iterator for the slice of the buffer for the current piece. My problem (and I've tried a couple different approaches) is that I keep hitting lifetime issues. My current code give me the error:

:76:30: 84:22 error: closure requires unique access to `self` but `self.buf_iter.0` is already borrowed [E0500]

which I think I understand, but I'm not sure how to fix. I've tried a few variants of the current code, and they all run into similar problems.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
maxpolun
  • 296
  • 4
  • 5

2 Answers2

6

It's just like the error message tells you. The problem is that you have overlapping mutable borrows of self. 

    match self.buf_iter {
        Some(ref mut iter) => { /// self.buf_iter is mutably borrowed here
            iter.next()
                .or_else(|| {
                    self.piece_iter.next().and_then(|p| { /// which is why you can't mutably borrow self here again
                        let mut buf = self.table.piece_buf(p)[p.start..(p.start + p.length)]
                                          .iter();
                        let item = buf.next();
                        self.buf_iter = Some(buf);
                        item
                    })
                })
                .map(|b| *b)
        }
        None => None,
    }

The solution is to make the first borrow end before the second one occurs.

It's also possible to simplify the code a bit by writing more idiomatic Rust.

impl<'a> Iterator for PieceTableIterator<'a> {
    type Item = u8;

    fn next(&mut self) -> Option<u8> {
        if self.buf_iter.is_none() {
            return None;
        }

        self.buf_iter
            .as_mut()
            .and_then(Iterator::next)
            .cloned()
            .or_else(|| {
                self.piece_iter.next().and_then(|p| {
                    let mut buf = self.table.piece_buf(p)[p.start..(p.start + p.length)]
                                      .iter();
                    let item = buf.next().cloned();
                    self.buf_iter = Some(buf);
                    item
                })
            })
    }
}
A.B.
  • 15,364
  • 3
  • 61
  • 64
0

The original code compiles as-is in modern Rust, presumably thanks to changes from non-lexical lifetimes. Some small idiomatic changes can be made as well:

#[derive(Debug)]
pub struct PieceTable {
    // original file data: never changes
    orig_buffer: Vec<u8>,
    // all new data is pushed onto this buffer
    add_buffer: Vec<u8>,
    // the pieces that currently make up the file
    pieces: Vec<Piece>,
}

#[derive(Debug, Copy, Clone)]
enum Location {
    Orig,
    Add,
}

#[derive(Debug, Copy, Clone)]
struct Piece {
    // which buffer is this piece located at?
    buf: Location,
    // starting offset
    start: usize,
    // size of piece
    length: usize,
}

impl PieceTable {
    pub fn iter(&self) -> PieceTableIterator {
        PieceTableIterator::new(self)
    }

    fn piece_buf(&self, piece: &Piece) -> &Vec<u8> {
        match piece.buf {
            Location::Orig => &self.orig_buffer,
            Location::Add => &self.add_buffer,
        }
    }
}

pub struct PieceTableIterator<'a> {
    table: &'a PieceTable,
    buf_iter: Option<std::slice::Iter<'a, u8>>,
    piece_iter: std::slice::Iter<'a, Piece>,
}

impl<'a> PieceTableIterator<'a> {
    fn new(table: &PieceTable) -> PieceTableIterator {
        let mut piece_iter = table.pieces.iter();
        let piece = piece_iter.next();
        let buf_iter = piece.map(|p| table.piece_buf(p).iter());
        PieceTableIterator {
            table,
            buf_iter,
            piece_iter,
        }
    }
}

impl<'a> Iterator for PieceTableIterator<'a> {
    type Item = u8;

    fn next(&mut self) -> Option<u8> {
        let iter = self.buf_iter.as_mut()?;

        iter.next()
            .or_else(|| {
                self.piece_iter.next().and_then(|p| {
                    let mut buf = self.table.piece_buf(p)[p.start..(p.start + p.length)].iter();
                    let item = buf.next();
                    self.buf_iter = Some(buf);
                    item
                })
            })
            .copied()
    }
}

fn main() {
    let table = PieceTable {
        orig_buffer: vec![1, 2, 3],
        add_buffer: vec![4, 5, 6],
        pieces: vec![
            Piece {
                buf: Location::Orig,
                start: 0,
                length: 2,
            },
            Piece {
                buf: Location::Add,
                start: 0,
                length: 3,
            },
            Piece {
                buf: Location::Orig,
                start: 2,
                length: 1,
            },
        ],
    };
    // shoud print 1, 2, 4, 5, 6, 3
    for i in table.iter() {
        println!("{}", i);
    }
}
Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366