Piece Tree

Purely functional (immutable) implementation of Piece Tree, inspired by fredbuf.

Usage

You can access full documentation at: https://docs.rs/piece-tree.

Basic editing

fn main() {
    use piece_tree::PieceTree;

    let mut tree = PieceTree::new();

    // Insert text at a byte offset
    tree.insert(0, "Hello, World!");
    assert_eq!(tree.to_string(), "Hello, World!");

    // Insert in the middle
    tree.insert(7, "beautiful ");
    assert_eq!(tree.to_string(), "Hello, beautiful World!");

    // Remove a range by byte offset and length
    tree.remove(7..17);
    assert_eq!(tree.to_string(), "Hello, World!");
}

Coordinate queries

All coordinate functions work in O(log n) time.

fn main() {
    use piece_tree::PieceTree;

    let mut tree = PieceTree::new();
    tree.insert(0, "Hello\n🌐world\r\nПривет");

    // Char index <-> byte offset
    assert_eq!(tree.char_to_byte(6),  6);   // '🌐' starts     at byte 6
    assert_eq!(tree.char_to_byte(7),  10);  // 'w' after 🌐 is at byte 10
    assert_eq!(tree.byte_to_char(10), 7);

    // Line number -> byte offset of line start (0-indexed)
    assert_eq!(tree.line_to_byte(0),  0);
    assert_eq!(tree.line_to_byte(1),  6);
    assert_eq!(tree.line_to_byte(2),  17);

    // Byte offset -> (line, col) where col is a char count
    assert_eq!(tree.byte_to_line_col(0),  (0, 0));
    assert_eq!(tree.byte_to_line_col(10), (1, 1)); // 'w', line 1, col 1
    assert_eq!(tree.byte_to_line_col(17), (2, 0)); // 'П', line 2, col 0
}

Undo and redo

Each call to insert or remove automatically pushes an undo entry. try_undo and try_redo return the cursor offset that was saved with the entry.

fn main() {
    use piece_tree::PieceTree;

    let mut tree = PieceTree::new();
    tree.insert(0, "Hello");
    tree.insert(5, ", World!");
    assert_eq!(tree.to_string(), "Hello, World!");

    tree.try_undo(0);
    assert_eq!(tree.to_string(), "Hello");

    tree.try_redo(0);
    assert_eq!(tree.to_string(), "Hello, World!");
}

Use begin_undo_group and end_undo_group to batch multiple mutations into a single undo step. For manual control, use the *_no_commit variants to make silent changes, followed by commit_head call to record a checkpoint.

fn main() {
    use piece_tree::PieceTree;

    let mut tree = PieceTree::new();
    tree.insert(0, "Hello");

    tree.begin_undo_group(5);

    // Type ", World!" character by character without flooding undo history
    tree.insert(5, ",");
    tree.insert(6, " ");
    tree.insert(7, "World!");

    tree.end_undo_group();

    tree.try_undo(0);
    assert_eq!(tree.to_string(), "Hello");
}

Tree Snapshotting

fn main() {
    use piece_tree::PieceTree;

    let mut tree = PieceTree::new();
    let mut cursor = 0;

    // Basic typing and taking a snapshot
    tree.insert(cursor, "Hello ");   cursor += 6;
    tree.insert(cursor, "World!");   cursor += 6;
    let snap = tree.take_snapshot(cursor); // Saves "Hello World!" state

    // Batch mutations into a single undo group
    tree.begin_undo_group(cursor);
    tree.insert_no_commit(cursor, " Everything"); cursor += 11;
    tree.insert_no_commit(cursor, " is great!");  cursor += 10;
    tree.end_undo_group();
    assert_eq!(tree.to_string(), "Hello World! Everything is great!");

    // Undo and Redo the transaction group
    cursor = tree.try_undo(cursor).unwrap();
    assert_eq!(tree.to_string(), "Hello World!");

    cursor = tree.try_redo(cursor).unwrap();
    assert_eq!(tree.to_string(), "Hello World! Everything is great!");

    // Revert to snapshot (and show that the jump itself can be undone)
    cursor = tree.snap_to(snap, cursor);
    assert_eq!(tree.to_string(), "Hello World!");

    cursor = tree.try_undo(cursor).unwrap();
    assert_eq!(tree.to_string(), "Hello World! Everything is great!");
}

Vendoring

To keep piece-tree highly optimized and tailored for its specific use case, portions of the following third-party crates have been integrated directly into the source code:

• cranelift-entity (Apache-2.0 with LLVM Exception).
• smallvec (MIT).
• bytecount (MIT).

This copy-pasted code remains under its original respective licenses. Full attribution notices are maintained at the top of the relevant source files, and the complete license texts can be found in THIRD-PARTY-LICENSES.md.

If you prefer to use the upstream, non-vendored versions of these crates via Cargo, you can enable the dont_vendor feature flag.

Benchmarks vs ropey's Rope

While these structures address different use cases, this crate is a purely functional Red-Black piece tree offering O(1) snapshotting and slicing, whereas ropey is a mutable B-tree optimized for cache-local, in-place editing, we can still compare their performance profiles.

TL;DR: Slicing is 100-300x faster, and line-based access (including byte/line conversions) is roughly 10-45x faster. However, insertions at the start/middle are 6-10x slower: peaking at ~2-5µs for 1.5MB inserts, while insertions at the end are faster and removes remain roughly equivalent.