append_only.rs

#![feature(slice_as_chunks)]

use std::{
    convert::AsRef,
    ops::{
        Bound::{Excluded, Included, Unbounded},
        RangeBounds,
    },
    str::from_utf8_unchecked,
};

trait Editor {
    fn len(&self) -> u32;
    fn push(&mut self, data: impl AsRef<str>);
    fn remove(&mut self, r: impl RangeBounds<u32>);
    fn remove_tail(&mut self, n: u32);
}

struct AppendOnlyDatabase {
    buf: Vec<u8>,
    s: String,
}

impl AppendOnlyDatabase {
    fn new() -> Self {
        Self {
            buf: Vec::new(),
            s: String::new(),
        }
    }

    fn from_mutations(buf: Vec<u8>) -> Self {
        let mut s = String::new();
        let mut i = 0;

        while i < buf.len() {
            let header = buf[i];
            i += 1;

            let is_push = (header & (1 << 7)) != 0;
            if is_push {
                let n = (header & ((1 << 7) - 1)) as usize;
                s.push_str(unsafe { from_utf8_unchecked(&buf[i..i + n]) });
                i += n;
            } else {
                let is_tail_removal = header != 0;
                if is_tail_removal {
                    let n = header as usize;
                    s.truncate(s.len() - n);
                } else {
                    let (start, end) = unsafe {
                        let p = buf.as_ptr().add(i) as *const u32;
                        let (start, end) = (p.add(0).read(), p.add(1).read());
                        (start as usize, end as usize)
                    };
                    s.replace_range(start..=end, "");
                    i += 8;
                }
            }
        }

        Self { buf, s }
    }
}

impl Editor for AppendOnlyDatabase {
    fn len(&self) -> u32 {
        self.s.len() as u32
    }

    fn push<'a>(&mut self, data: impl AsRef<str>) {
        let (chunks, rem) = data.as_ref().as_bytes().as_chunks::<128>();
        for chunk in chunks {
            self.buf.push(make_push_header(chunk));
            self.buf.extend_from_slice(chunk);
        }
        self.buf.push(make_push_header(rem));
        self.buf.extend_from_slice(rem);
        self.s.push_str(data.as_ref());
    }

    fn remove(&mut self, r: impl RangeBounds<u32>) {
        let start = match r.start_bound() {
            Included(&s) => s,
            Excluded(&s) => s + 1,
            Unbounded => 0,
        };

        let end = match r.end_bound() {
            Included(&e) => e,
            Excluded(&e) => e - 1,
            Unbounded => self.len(),
        };

        self.buf.extend_from_slice(&make_remove_header(start, end));
        self.s.replace_range(start as usize..=end as usize, "");
    }

    fn remove_tail(&mut self, mut n: u32) {
        while n > 128 {
            self.buf.push(make_remove_tail_header(128));
            n -= 128;
        }
        self.buf.push(make_remove_tail_header(n));
        self.s.truncate(self.s.len() - n as usize);
    }
}

fn make_push_header(data: &[u8]) -> u8 {
    debug_assert!(data.len() <= (1 << 7));
    0b1000_0000 | data.len() as u8
}

fn make_remove_header(start: u32, end: u32) -> [u8; 9] {
    let mut out = [0; 9];
    out[1..5].copy_from_slice(&start.to_le_bytes());
    out[5..9].copy_from_slice(&end.to_le_bytes());
    out
}

fn make_remove_tail_header(n: u32) -> u8 {
    debug_assert!(n <= (1 << 7));
    n as u8
}

fn main() {
    let mut db = AppendOnlyDatabase::new();

    db.push("Hello, world!");
    db.remove_tail("world!".len() as u32);
    db.push("Dario!");

    let tape = vec![
        141, 72, 101, 108, 108, 111, 44, 32, 119, 111, 114, 108, 100, 33, 6, 134, 68, 97, 114, 105,
        111, 33,
    ];
    let db = AppendOnlyDatabase::from_mutations(tape);
    println!("{}", db.s);
}