piece-tree 0.1.4

Purely functional (immutable) implementation of Piece Tree, inspired by fredbuf
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220

# Piece Tree

Purely functional (immutable) implementation of Piece Tree, inspired by [fredbuf](https://github.com/cdacamar/fredbuf).

## Usage

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

### Basic editing

```rust
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.

```rust
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.

```rust
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.

```rust
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

```rust
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](./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.

| Benchmark Group | e2-piece-tree | ropey's Rope |
| :--- | :--- | :--- |
| **from_str** | | |
| `from_str/large` | 1886.9 ± 1.33 µs | 1002.6 ± 412.22 µs |
| `from_str/linefeeds` | 36.2 ± 9.60 µs | 6.0 ± 1.39 µs |
| `from_str/medium` | 264.7 ± 0.24 µs | 139.7 ± 10.71 µs |
| `from_str/small` | 2.6 ± 0.01 µs | 1186.1 ± 8.36 ns |
| **get** | | |
| `get/byte` | 7.0 ± 0.00 ns | 70.9 ± 2.38 ns |
| `get/char` | 122.3 ± 0.67 ns | 144.9 ± 3.77 ns |
| `get/chunk_at_byte` | 4.9 ± 0.00 ns | 62.7 ± 6.42 ns |
| `get/chunk_at_byte_slice`| 7.6 ± 0.01 ns | 70.4 ± 0.27 ns |
| `get/chunk_at_char` | 117.6 ± 0.41 ns | 67.8 ± 0.83 ns |
| `get/chunk_at_char_slice`| 316.1 ± 0.96 ns | 70.2 ± 4.07 ns |
| `get/chunk_at_line_break`| 5.8 ± 0.01 ns | 66.8 ± 4.98 ns |
| `get/chunk_at_line_break_slice`| 119.3 ± 4.18 ns | 71.9 ± 4.20 ns |
| `get/line` | 14.9 ± 0.01 ns | 453.4 ± 35.59 ns |
| **index_convert** | | |
| `index_convert/byte_to_char`| 81.2 ± 0.34 ns | 74.2 ± 0.68 ns |
| `index_convert/byte_to_line`| 123.5 ± 21.21 ns | 83.8 ± 11.82 ns |
| `index_convert/char_to_byte`| 113.8 ± 0.75 ns | 126.3 ± 6.31 ns |
| `index_convert/char_to_line`| 249.6 ± 1.19 ns | 153.1 ± 17.01 ns |
| `index_convert/line_to_byte`| 6.6 ± 0.02 ns | 292.7 ± 13.54 ns |
| `index_convert/line_to_char`| 94.5 ± 0.56 ns | 294.2 ± 1.77 ns |
| **insert** | | |
| `insert_after_clone` | 537.7 ± 5.19 ns | 1562.7 ± 100.31 ns |
| `insert_char/start` | 1112.7 ± 121.29 ns | 112.3 ± 3.74 ns |
| `insert_char/middle` | 622.4 ± 52.70 ns | 155.4 ± 4.91 ns |
| `insert_char/end` | 48.1 ± 2.82 ns | 162.9 ± 2.23 ns |
| `insert_char/random` | 1944.6 ± 378.40 ns| 332.4 ± 74.61 ns |
| `insert_small/start` | 1143.2 ± 99.71 ns | 95.6 ± 16.34 ns |
| `insert_small/middle` | 650.0 ± 49.08 ns | 155.9 ± 10.94 ns |
| `insert_small/end` | 49.2 ± 3.95 ns | 166.5 ± 5.60 ns |
| `insert_small/random` | 1930.7 ± 369.78 ns| 333.8 ± 55.31 ns |
| `insert_medium/start` | 1195.3 ± 106.69 ns| 186.0 ± 5.83 ns |
| `insert_medium/middle` | 1324.6 ± 100.89 ns| 250.3 ± 2.97 ns |
| `insert_medium/end` | 68.9 ± 11.38 ns | 243.0 ± 3.71 ns |
| `insert_medium/random` | 2.0 ± 0.38 µs | 395.3 ± 73.67 ns |
| `insert_large/start` | 3.9 ± 0.55 µs | 1773.7 ± 474.86 ns|
| `insert_large/middle` | 4.2 ± 0.53 µs | 2.3 ± 0.13 µs |
| `insert_large/end` | 2.3 ± 0.13 µs | 2.3 ± 0.38 µs |
| `insert_large/random` | 4.7 ± 0.83 µs | 2.7 ± 0.40 µs |
| **remove** | | |
| `remove_initial_after_clone`| 744.5 ± 1.90 ns | 862.4 ± 107.87 ns |
| `remove_small/start` | 230.0 ± 18.89 ns | 145.8 ± 5.28 ns |
| `remove_small/middle` | 293.9 ± 18.56 ns | 180.0 ± 7.63 ns |
| `remove_small/end` | 229.6 ± 13.70 ns | 181.9 ± 19.80 ns |
| `remove_small/random` | 2.9 ± 0.59 µs | 276.8 ± 4.09 ns |
| `remove_medium/start` | 296.0 ± 10.74 ns | 242.6 ± 15.83 ns |
| `remove_medium/middle` | 560.0 ± 30.23 ns | 347.3 ± 15.83 ns |
| `remove_medium/end` | 306.6 ± 13.19 ns | 299.2 ± 44.31 ns |
| `remove_medium/random`| 3.1 ± 0.61 µs | 372.8 ± 14.77 ns |
| `remove_large/start` | 1912.1 ± 510.75 ns| 2.1 ± 0.31 µs |
| `remove_large/middle` | 2.2 ± 0.54 µs | 2.6 ± 0.32 µs |
| `remove_large/end` | 1852.8 ± 524.83 ns| 1930.4 ± 302.20 ns|
| `remove_large/random` | 4.2 ± 0.90 µs | 2.6 ± 0.45 µs |
| **slice** | | |
| `slice/slice` | 2.6 ± 0.00 ns | 866.6 ± 6.02 ns |
| `slice/slice_small` | 1.6 ± 0.38 ns | 245.6 ± 24.54 ns |
| `slice/slice_whole_slice` | 0.0 ± 0.02 ns | 0.3 ± 0.01 ns |
| `slice/slice_from_small_*`| 2.6 ± 0.00 ns | 424.8 ± 56.02 ns |
| `slice/slice_whole_*` | 0.1 ± 0.02 ns | 29.8 ± 7.83 ns |