Rust - insert into piecetable

Question

I'm writing a piece table library in Rust with the structures:

#[derive(Default)]
struct Piece {
 additional: bool,
 offset: usize,
 length: usize,
}

and

/// PieceTable contains the additional, original buffers and a vector of pieces.
/// It also maintains a length variable.
pub struct PieceTable {
 table: VecDeque<Piece>,
 orig_buffer: String,
 add_buffer: String,
 length: usize,
}

I'm fairly confident that I didn't mess anything up here, though I'm not sure if VecDeque is the best structure to hold the pieces. My insert method is:

impl PieceTable {
 ...
 pub fn insert(&mut self, index: usize, text: &string) {
 match self.piece_at(index + 1) {
 Ok((index, offset)) => {
 // isolate piece being inserted into
 let into = &self.table[index];
 // create necessary Pieces to enter
 let previous = Piece {
 additional: into.additional,
 offset: into.offset,
 length: offset - into.offset,
 };
 let insert = Piece {
 additional: true,
 offset: self.add_buffer.len(),
 length: text.len(),
 };
 let next = Piece {
 additional: into.additional,
 offset: offset,
 length: into.length - (offset - into.offset),
 };
 // remove index, add in previous, insert, next
 self.table.remove(index);
 self.table.insert(index, previous);
 self.table.insert(index + 1, insert);
 self.table.insert(index + 2, next);
 // update buffer, length vars
 self.add_buffer.push_str(text);
 self.length += text.len();
 }
 Err(_) => self.push_str(text),
 }
 }
}

Which refers to the piece_at method:

fn piece_at(&self, index: usize) -> Result<(usize, usize>, i32> {
 if index > self.length {
 return Err(-1);
 }
 let mut remaining = index.clone();
 for (i, piece) in self.table.iter().enumerate() {
 if remaining <= piece.length {
 return Ok((i, remaining));
 }
 remaining -= piece.length;
 }
 return Err(-1);
}

It also relies on the push_str method, which is just appends a piece with the proper parameters to the end of self.table.

This algorithm is stolen basically verbatim from the python implementation at https://github.com/saiguy3/piece_table, so hopefully there's nothing terribly wrong with it that I missed. Rust is hard and I started learning it yesterday, so I'm fully expecting I horribly misused some language feature.

Thanks!

Answer 1

Keep in mind that there already exist rope structure implementations in Rust, which support utf8, for example an_rope, where your PieceTable::insert is Rope::insert_str: https://docs.rs/an-rope/0.3.1/an_rope/struct.Rope.html#method.insert_str

Your code is really good for someone who just started learning, and nothing stands out as a misuse of language.

Why is index + 1 passed to piece_at, not simply index?

Using VecDeque does give a little potential for speedup in random insertion and removal. Although if I was doing a program like this, my choice of the data structure would be different - I'd use BTreeSet<Piece> instead, and order the Pieces by piece.offset.

You may write a removal and an insert at the same index as a single [] = instead.

About Copy/Clone:

• if your Piece derived Copy, the & in &self.table[index] could be omitted. Did you try compiling this code? Can it compile without errors? I doubt it since the immutable borrow with & will prevent you from removal and insertion later on.
• the .clone() in piece_at can be omitted, because piece: usize is Plain Old Data that is copied around with zero overhead (in syntax and in performance as well).

There are two tiny misspellings

• text: &string instead of text: &str
• (usize,usize>, instead of (usize,usize)>,

I'd change the Err(-1) return to carry the unit value instead as we don't need the i32 to signal anything. We return Err(()) there.