dte test coverage

Directory: ./
File: src/edit.c
Date: 2024-12-21 16:03:22
Exec Total Coverage
Lines: 205 226 90.7%
Functions: 9 9 100.0%
Branches: 80 102 78.4%
Line Branch Exec Source
1 #include <string.h>
2 #include "edit.h"
3 #include "block.h"
4 #include "buffer.h"
5 #include "syntax/highlight.h"
6 #include "util/debug.h"
7 #include "util/list.h"
8 #include "util/xmalloc.h"
9
10 enum {
11 BLOCK_EDIT_SIZE = 512
12 };
13
14 291 static void sanity_check_blocks(const View *view, bool check_newlines)
15 {
16 291 if (DEBUG < 1) {
17 return;
18 }
19
20 291 const Buffer *buffer = view->buffer;
21 291 BUG_ON(list_empty(&buffer->blocks));
22 291 BUG_ON(view->cursor.offset > view->cursor.blk->size);
23
24 291 const Block *blk = BLOCK(buffer->blocks.next);
25
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 285 times.
 291 if (blk->size == 0) {
26 // The only time a zero-sized block is valid is when it's the
27 // first and only block
28 6 BUG_ON(buffer->blocks.next->next != &buffer->blocks);
29 6 BUG_ON(view->cursor.blk != blk);
30 return;
31 }
32
33 bool cursor_seen = false;
34
2/2
✓ Branch 0 taken 289 times.
✓ Branch 1 taken 285 times.
 574 block_for_each(blk, &buffer->blocks) {
35 289 const size_t size = blk->size;
36 289 BUG_ON(size == 0);
37 289 BUG_ON(size > blk->alloc);
38
2/2
✓ Branch 0 taken 285 times.
✓ Branch 1 taken 4 times.
 289 if (blk == view->cursor.blk) {
39 285 cursor_seen = true;
40 }
41
1/2
✓ Branch 0 taken 289 times.
✗ Branch 1 not taken.
 289 if (check_newlines) {
42 // Non-empty blocks must ALWAYS end with a newline, since
43 // lines MAY NOT straddle multiple blocks
44 289 BUG_ON(blk->data[size - 1] != '\n');
45 }
46 289 if (DEBUG > 2) {
47 289 BUG_ON(count_nl(blk->data, size) != blk->nl);
48 }
49 }
50
51 285 BUG_ON(!cursor_seen);
52 }
53
54 326 static size_t copy_count_nl(char *dst, const char *src, size_t len)
55 {
56 326 size_t nl = 0;
57
2/2
✓ Branch 0 taken 19375 times.
✓ Branch 1 taken 326 times.
 19701 for (size_t i = 0; i < len; i++) {
58 19375 dst[i] = src[i];
59
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 19223 times.
 19375 if (src[i] == '\n') {
60 152 nl++;
61 }
62 }
63 326 return nl;
64 }
65
66 191 static size_t insert_to_current(BlockIter *cursor, const char *buf, size_t len)
67 {
68 191 Block *blk = cursor->blk;
69 191 size_t offset = cursor->offset;
70 191 size_t size = blk->size + len;
71 191 block_grow(blk, size);
72 191 memmove(blk->data + offset + len, blk->data + offset, blk->size - offset);
73 191 size_t nl = copy_count_nl(blk->data + offset, buf, len);
74 191 blk->nl += nl;
75 191 blk->size = size;
76 191 return nl;
77 }
78
79 /*
80 * Combine current block and new data into smaller blocks:
81 *
82 * • Block _must_ contain whole lines
83 * • Block _must_ contain at least one line
84 * • Preferred maximum size of block is BLOCK_EDIT_SIZE
85 * • Size of any block can be larger than BLOCK_EDIT_SIZE only if there's
86 * a very long line
87 */
88 2 static size_t split_and_insert(BlockIter *cursor, const char *buf, size_t len)
89 {
90 2 Block *blk = cursor->blk;
91 2 ListHead *prev_node = blk->node.prev;
92 2 const char *buf1 = blk->data;
93 2 const char *buf2 = buf;
94 2 const char *buf3 = blk->data + cursor->offset;
95 2 size_t size1 = cursor->offset;
96 2 size_t size2 = len;
97 2 size_t size3 = blk->size - size1;
98 2 size_t total = size1 + size2 + size3;
99 2 size_t start = 0; // Beginning of new block
100 2 size_t size = 0; // Size of new block
101 2 size_t pos = 0; // Current position
102 2 size_t nl_added = 0;
103
104
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 2 times.
 30 while (start < total) {
105 // Size of new block if next line would be added
106 28 size_t new_size = 0;
107 28 size_t copied = 0;
108
109
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 23 times.
 28 if (pos < size1) {
110 5 const char *nl = memchr(buf1 + pos, '\n', size1 - pos);
111
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
 5 if (nl) {
112 4 new_size = nl - buf1 + 1 - start;
113 }
114 }
115
116
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 20 times.
✓ Branch 3 taken 4 times.
 28 if (!new_size && pos < size1 + size2) {
117 20 size_t offset = 0;
118
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 2 times.
 20 if (pos > size1) {
119 18 offset = pos - size1;
120 }
121
122 20 const char *nl = memchr(buf2 + offset, '\n', size2 - offset);
123
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (nl) {
124 20 new_size = size1 + nl - buf2 + 1 - start;
125 }
126 }
127
128
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 24 times.
 28 if (!new_size && pos < total) {
129 4 size_t offset = 0;
130
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
 4 if (pos > size1 + size2) {
131 2 offset = pos - size1 - size2;
132 }
133
134 4 const char *nl = memchr(buf3 + offset, '\n', size3 - offset);
135
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (nl) {
136 4 new_size = size1 + size2 + nl - buf3 + 1 - start;
137 } else {
138 ✗ new_size = total - start;
139 }
140 }
141
142
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 3 times.
 28 if (new_size <= BLOCK_EDIT_SIZE) {
143 // Fits
144 25 size = new_size;
145 25 pos = start + new_size;
146
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 2 times.
 25 if (pos < total) {
147 23 continue;
148 }
149 } else {
150 // Does not fit
151
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (!size) {
152 // One block containing one very long line
153 ✗ size = new_size;
154 ✗ pos = start + new_size;
155 }
156 }
157
158 2 BUG_ON(!size);
159 5 Block *new = block_new(size);
160
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
 5 if (start < size1) {
161 1 size_t avail = size1 - start;
162 1 size_t count = MIN(size, avail);
163 1 new->nl += copy_count_nl(new->data, buf1 + start, count);
164 1 copied += count;
165 1 start += count;
166 }
167
3/4
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 1 times.
 5 if (start >= size1 && start < size1 + size2) {
168 4 size_t offset = start - size1;
169 4 size_t avail = size2 - offset;
170 4 size_t count = MIN(size - copied, avail);
171 4 new->nl += copy_count_nl(new->data + copied, buf2 + offset, count);
172 4 copied += count;
173 4 start += count;
174 }
175
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 2 times.
 5 if (start >= size1 + size2) {
176 3 size_t offset = start - size1 - size2;
177 3 size_t avail = size3 - offset;
178 3 size_t count = size - copied;
179 3 BUG_ON(count > avail);
180 3 new->nl += copy_count_nl(new->data + copied, buf3 + offset, count);
181 3 copied += count;
182 3 start += count;
183 }
184
185 5 new->size = size;
186 5 BUG_ON(copied != size);
187 5 list_insert_before(&new->node, &blk->node);
188
189 5 nl_added += new->nl;
190 5 size = 0;
191 }
192
193 2 cursor->blk = BLOCK(prev_node->next);
194
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 while (cursor->offset > cursor->blk->size) {
195 ✗ cursor->offset -= cursor->blk->size;
196 ✗ cursor->blk = BLOCK(cursor->blk->node.next);
197 }
198
199 2 nl_added -= blk->nl;
200 2 block_free(blk);
201 2 return nl_added;
202 }
203
204 193 static size_t insert_bytes(BlockIter *cursor, const char *buf, size_t len)
205 {
206 // Blocks must contain whole lines.
207 // Last char of buf might not be newline.
208 193 block_iter_normalize(cursor);
209
210 193 Block *blk = cursor->blk;
211 193 size_t new_size = blk->size + len;
212
4/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 187 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 3 times.
 193 if (new_size <= blk->alloc || new_size <= BLOCK_EDIT_SIZE) {
213 190 return insert_to_current(cursor, buf, len);
214 }
215
216
4/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
 3 if (blk->nl <= 1 && !memchr(buf, '\n', len)) {
217 // Can't split this possibly very long line.
218 // insert_to_current() is much faster than split_and_insert().
219 1 return insert_to_current(cursor, buf, len);
220 }
221 2 return split_and_insert(cursor, buf, len);
222 }
223
224 193 void do_insert(View *view, const char *buf, size_t len)
225 {
226 193 Buffer *buffer = view->buffer;
227 193 size_t nl = insert_bytes(&view->cursor, buf, len);
228 193 buffer->nl += nl;
229 193 sanity_check_blocks(view, true);
230
231 193 view_update_cursor_y(view);
232
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 73 times.
 193 buffer_mark_lines_changed(buffer, view->cy, nl ? LONG_MAX : view->cy);
233
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 192 times.
 193 if (buffer->syntax) {
234 1 hl_insert(&buffer->line_start_states, view->cy, nl);
235 }
236 193 }
237
238 6 static bool only_block(const Buffer *buffer, const Block *blk)
239 {
240
2/4
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 6 return blk->node.prev == &buffer->blocks && blk->node.next == &buffer->blocks;
241 }
242
243 69 char *do_delete(View *view, size_t len, bool sanity_check_newlines)
244 {
245
1/2
✓ Branch 0 taken 69 times.
✗ Branch 1 not taken.
 69 if (len == 0) {
246 return NULL;
247 }
248
249 69 ListHead *saved_prev_node = NULL;
250 69 Block *blk = view->cursor.blk;
251 69 size_t offset = view->cursor.offset;
252
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 44 times.
 69 if (!offset) {
253 // The block where the cursor is can become empty and thus
254 // may be deleted
255 25 saved_prev_node = blk->node.prev;
256 }
257
258 69 Buffer *buffer = view->buffer;
259 69 char *deleted = xmalloc(len);
260 69 size_t pos = 0;
261 69 size_t deleted_nl = 0;
262
263 69 while (pos < len) {
264 69 ListHead *next = blk->node.next;
265 69 size_t avail = blk->size - offset;
266 69 size_t count = MIN(len - pos, avail);
267 69 char *ptr = blk->data + offset;
268 69 size_t nl = copy_count_nl(deleted + pos, ptr, count);
269
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 13 times.
 69 if (count < avail) {
270 56 memmove(ptr, ptr + count, avail - count);
271 }
272
273 69 deleted_nl += nl;
274 69 buffer->nl -= nl;
275 69 blk->nl -= nl;
276 69 blk->size -= count;
277
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 69 if (!blk->size && !only_block(buffer, blk)) {
278 ✗ block_free(blk);
279 }
280
281 69 offset = 0;
282 69 pos += count;
283 69 blk = BLOCK(next);
284 207 BUG_ON(pos < len && next == &buffer->blocks);
285 }
286
287
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 44 times.
 69 if (saved_prev_node) {
288 // Cursor was at beginning of a block that was possibly deleted
289
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 25 times.
 25 if (saved_prev_node->next == &buffer->blocks) {
290 ✗ view->cursor.blk = BLOCK(saved_prev_node);
291 ✗ view->cursor.offset = view->cursor.blk->size;
292 } else {
293 25 view->cursor.blk = BLOCK(saved_prev_node->next);
294 }
295 }
296
297 69 blk = view->cursor.blk;
298
299 69 if (
300
2/2
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 6 times.
 69 blk->size
301
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 63 times.
 63 && blk->data[blk->size - 1] != '\n'
302 ✗ && blk->node.next != &buffer->blocks
303 ) {
304 ✗ Block *next = BLOCK(blk->node.next);
305 ✗ size_t size = blk->size + next->size;
306 ✗ block_grow(blk, size);
307 ✗ memcpy(blk->data + blk->size, next->data, next->size);
308 ✗ blk->size = size;
309 ✗ blk->nl += next->nl;
310 ✗ block_free(next);
311 }
312
313 69 sanity_check_blocks(view, sanity_check_newlines);
314
315 69 view_update_cursor_y(view);
316
2/2
✓ Branch 0 taken 44 times.
✓ Branch 1 taken 25 times.
 69 buffer_mark_lines_changed(buffer, view->cy, deleted_nl ? LONG_MAX : view->cy);
317
318
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 69 times.
 69 if (buffer->syntax) {
319 ✗ hl_delete(&buffer->line_start_states, view->cy, deleted_nl);
320 }
321
322 return deleted;
323 }
324
325 31 char *do_replace(View *view, size_t del, const char *buf, size_t ins)
326 {
327 31 BUG_ON(del == 0);
328 31 BUG_ON(ins == 0);
329 31 block_iter_normalize(&view->cursor);
330
331 31 Block *blk = view->cursor.blk;
332 31 size_t offset = view->cursor.offset;
333 31 size_t avail = blk->size - offset;
334
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 29 times.
 31 if (del >= avail) {
335 2 goto slow;
336 }
337
338 29 size_t new_size = blk->size + ins - del;
339
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 29 times.
 29 if (new_size > BLOCK_EDIT_SIZE) {
340 // Should split
341 ✗ if (blk->nl > 1 || memchr(buf, '\n', ins)) {
342 // Most likely can be split
343 ✗ goto slow;
344 }
345 }
346
347 29 block_grow(blk, new_size);
348
349 // Modification is limited to one block
350 29 Buffer *buffer = view->buffer;
351 29 char *ptr = blk->data + offset;
352 29 char *deleted = xmalloc(del);
353 29 size_t del_nl = copy_count_nl(deleted, ptr, del);
354 29 blk->nl -= del_nl;
355 29 buffer->nl -= del_nl;
356
357
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 13 times.
 29 if (del != ins) {
358 16 memmove(ptr + ins, ptr + del, avail - del);
359 }
360
361 29 size_t ins_nl = copy_count_nl(ptr, buf, ins);
362 29 blk->nl += ins_nl;
363 29 buffer->nl += ins_nl;
364 29 blk->size = new_size;
365 29 sanity_check_blocks(view, true);
366 29 view_update_cursor_y(view);
367
368 // If the number of inserted and removed bytes are the same, some
369 // line(s) changed but the lines after them didn't move up or down
370
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 11 times.
 29 long max = (del_nl == ins_nl) ? view->cy + del_nl : LONG_MAX;
371 29 buffer_mark_lines_changed(buffer, view->cy, max);
372
373
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 29 times.
 29 if (buffer->syntax) {
374 ✗ hl_delete(&buffer->line_start_states, view->cy, del_nl);
375 ✗ hl_insert(&buffer->line_start_states, view->cy, ins_nl);
376 }
377
378 return deleted;
379
380 2 slow:
381 // The "sanity_check_newlines" argument of do_delete() is false here
382 // because it may be removing a terminating newline that do_insert()
383 // is going to insert again at a different position:
384 2 deleted = do_delete(view, del, false);
385 2 BUG_ON(!deleted); // do_delete() only returns NULL if len is 0
386 2 do_insert(view, buf, ins);
387 2 return deleted;
388 }
389