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.