Codebergdnkl
foot
master
1#include "grid.h"
3#include <limits.h>
4#include <stdlib.h>
5#include <string.h>
7#define LOG_MODULE "grid"
8#define LOG_ENABLE_DBG 0
9#include "log.h"
10#include "debug.h"
11#include "macros.h"
12#include "sixel.h"
13#include "stride.h"
14#include "util.h"
15#include "xmalloc.h"
17#define TIME_REFLOW 0
19#if defined(TIME_REFLOW)
20#include "misc.h"
21#endif
23/*
24 * "sb" (scrollback relative) coordinates
25 *
26 * The scrollback relative row number 0 is the *first*, and *oldest*
27 * row in the scrollback history (and thus the *first* row to be
28 * scrolled out). Thus, a higher number means further *down* in the
29 * scrollback, with the *highest* number being at the bottom of the
30 * screen, where new input appears.
31 */
33int
34grid_row_abs_to_sb(const struct grid *grid, int screen_rows, int abs_row)
35{
36 const int scrollback_start = grid->offset + screen_rows;
37 int rebased_row = abs_row - scrollback_start + grid->num_rows;
39 rebased_row &= grid->num_rows - 1;
40 return rebased_row;
41}
43int
44grid_row_sb_to_abs(const struct grid *grid, int screen_rows, int sb_rel_row)
45{
46 const int scrollback_start = grid->offset + screen_rows;
47 int abs_row = sb_rel_row + scrollback_start;
49 abs_row &= grid->num_rows - 1;
50 return abs_row;
51}
53int
54grid_sb_start_ignore_uninitialized(const struct grid *grid, int screen_rows)
55{
56 int scrollback_start = grid->offset + screen_rows;
57 scrollback_start &= grid->num_rows - 1;
59 while (grid->rows[scrollback_start] == NULL) {
60 scrollback_start++;
61 scrollback_start &= grid->num_rows - 1;
62 }
64 return scrollback_start;
65}
67int
68grid_row_abs_to_sb_precalc_sb_start(const struct grid *grid, int sb_start,
69 int abs_row)
70{
71 int rebased_row = abs_row - sb_start + grid->num_rows;
72 rebased_row &= grid->num_rows - 1;
73 return rebased_row;
74}
76int
77grid_row_sb_to_abs_precalc_sb_start(const struct grid *grid, int sb_start,
78 int sb_rel_row)
79{
80 int abs_row = sb_rel_row + sb_start;
81 abs_row &= grid->num_rows - 1;
82 return abs_row;
83}
85static void
86ensure_row_has_extra_data(struct row *row)
87{
88 if (row->extra == NULL)
89 row->extra = xcalloc(1, sizeof(*row->extra));
90}
92static void
93verify_no_overlapping_ranges_of_type(const struct row_ranges *ranges,
94 enum row_range_type type)
95{
96#if defined(_DEBUG)
97 for (size_t i = 0; i < ranges->count; i++) {
98 const struct row_range *r1 = &ranges->v[i];
100 for (size_t j = i + 1; j < ranges->count; j++) {
101 const struct row_range *r2 = &ranges->v[j];
102 xassert(r1 != r2);
104 if ((r1->start <= r2->start && r1->end >= r2->start) ||
105 (r1->start <= r2->end && r1->end >= r2->end))
106 {
107 switch (type) {
108 case ROW_RANGE_URI:
109 BUG("OSC-8 URI overlap: %s: %d-%d: %s: %d-%d",
110 r1->uri.uri, r1->start, r1->end,
111 r2->uri.uri, r2->start, r2->end);
112 break;
114 case ROW_RANGE_UNDERLINE:
115 BUG("underline overlap: %d-%d, %d-%d",
116 r1->start, r1->end, r2->start, r2->end);
117 break;
118 }
119 }
120 }
121 }
122#endif
123}
125static void
126verify_no_overlapping_ranges(const struct row_data *extra)
127{
128 verify_no_overlapping_ranges_of_type(&extra->uri_ranges, ROW_RANGE_URI);
129 verify_no_overlapping_ranges_of_type(&extra->underline_ranges, ROW_RANGE_UNDERLINE);
130}
132static void
133verify_ranges_of_type_are_sorted(const struct row_ranges *ranges,
134 enum row_range_type type)
135{
136#if defined(_DEBUG)
137 const struct row_range *last = NULL;
139 for (size_t i = 0; i < ranges->count; i++) {
140 const struct row_range *r = &ranges->v[i];
142 if (last != NULL) {
143 if (last->start >= r->start || last->end >= r->end) {
144 switch (type) {
145 case ROW_RANGE_URI:
146 BUG("OSC-8 URI not sorted correctly: "
147 "%s: %d-%d came before %s: %d-%d",
148 last->uri.uri, last->start, last->end,
149 r->uri.uri, r->start, r->end);
150 break;
152 case ROW_RANGE_UNDERLINE:
153 BUG("underline ranges not sorted correctly: "
154 "%d-%d came before %d-%d",
155 last->start, last->end, r->start, r->end);
156 break;
157 }
158 }
159 }
161 last = r;
162 }
163#endif
164}
166static void
167verify_ranges_are_sorted(const struct row_data *extra)
168{
169 verify_ranges_of_type_are_sorted(&extra->uri_ranges, ROW_RANGE_URI);
170 verify_ranges_of_type_are_sorted(&extra->underline_ranges, ROW_RANGE_UNDERLINE);
171}
173static void
174range_ensure_size(struct row_ranges *ranges, int count_to_add)
175{
176 if (ranges->count + count_to_add > ranges->size) {
177 ranges->size = ranges->count + count_to_add;
178 ranges->v = xrealloc(ranges->v, ranges->size * sizeof(ranges->v[0]));
179 }
181 xassert(ranges->count + count_to_add <= ranges->size);
182}
184/*
185 * Be careful! This function may xrealloc() the URI range vector, thus
186 * invalidating pointers into it.
187 */
188static void
189range_insert(struct row_ranges *ranges, size_t idx, int start, int end,
190 enum row_range_type type, const union row_range_data *data)
191{
192 range_ensure_size(ranges, 1);
194 xassert(idx <= ranges->count);
196 const size_t move_count = ranges->count - idx;
197 memmove(&ranges->v[idx + 1],
198 &ranges->v[idx],
199 move_count * sizeof(ranges->v[0]));
201 ranges->count++;
203 struct row_range *r = &ranges->v[idx];
204 r->start = start;
205 r->end = end;
207 switch (type) {
208 case ROW_RANGE_URI:
209 r->uri.id = data->uri.id;
210 r->uri.uri = xstrdup(data->uri.uri);
211 break;
213 case ROW_RANGE_UNDERLINE:
214 r->underline = data->underline;
215 break;
216 }
217}
219static void
220range_append_by_ref(struct row_ranges *ranges, int start, int end,
221 enum row_range_type type, const union row_range_data *data)
222{
223 range_ensure_size(ranges, 1);
225 struct row_range *r = &ranges->v[ranges->count++];
227 r->start = start;
228 r->end = end;
230 switch (type) {
231 case ROW_RANGE_URI:
232 r->uri.id = data->uri.id;;
233 r->uri.uri = data->uri.uri;
234 break;
236 case ROW_RANGE_UNDERLINE:
237 r->underline = data->underline;
238 break;
239 }
240}
242static void
243range_append(struct row_ranges *ranges, int start, int end,
244 enum row_range_type type, const union row_range_data *data)
245{
246 switch (type) {
247 case ROW_RANGE_URI:
248 range_append_by_ref(
249 ranges, start, end, type,
250 &(union row_range_data){.uri = {.id = data->uri.id,
251 .uri = xstrdup(data->uri.uri)}});
252 break;
254 case ROW_RANGE_UNDERLINE:
255 range_append_by_ref(ranges, start, end, type, data);
256 break;
257 }
258}
260static void
261range_delete(struct row_ranges *ranges, enum row_range_type type, size_t idx)
262{
263 xassert(idx < ranges->count);
264 grid_row_range_destroy(&ranges->v[idx], type);
266 const size_t move_count = ranges->count - idx - 1;
267 memmove(&ranges->v[idx],
268 &ranges->v[idx + 1],
269 move_count * sizeof(ranges->v[0]));
270 ranges->count--;
271}
273struct grid *
274grid_snapshot(const struct grid *grid)
275{
276 struct grid *clone = xmalloc(sizeof(*clone));
277 clone->num_rows = grid->num_rows;
278 clone->num_cols = grid->num_cols;
279 clone->offset = grid->offset;
280 clone->view = grid->view;
281 clone->cursor = grid->cursor;
282 clone->saved_cursor = grid->saved_cursor;
283 clone->kitty_kbd = grid->kitty_kbd;
284 clone->rows = xcalloc(grid->num_rows, sizeof(clone->rows[0]));
285 memset(&clone->scroll_damage, 0, sizeof(clone->scroll_damage));
286 memset(&clone->sixel_images, 0, sizeof(clone->sixel_images));
288 tll_foreach(grid->scroll_damage, it)
289 tll_push_back(clone->scroll_damage, it->item);
291 for (int r = 0; r < grid->num_rows; r++) {
292 const struct row *row = grid->rows[r];
294 if (row == NULL)
295 continue;
297 struct row *clone_row = xmalloc(sizeof(*row));
298 clone->rows[r] = clone_row;
300 clone_row->cells = xmalloc(grid->num_cols * sizeof(clone_row->cells[0]));
301 clone_row->linebreak = row->linebreak;
302 clone_row->dirty = row->dirty;
303 clone_row->shell_integration = row->shell_integration;
305 for (int c = 0; c < grid->num_cols; c++)
306 clone_row->cells[c] = row->cells[c];
308 const struct row_data *extra = row->extra;
310 if (extra != NULL) {
311 struct row_data *clone_extra = xcalloc(1, sizeof(*clone_extra));
312 clone_row->extra = clone_extra;
314 range_ensure_size(&clone_extra->uri_ranges, extra->uri_ranges.count);
315 range_ensure_size(&clone_extra->underline_ranges, extra->underline_ranges.count);
317 for (int i = 0; i < extra->uri_ranges.count; i++) {
318 const struct row_range *range = &extra->uri_ranges.v[i];
319 range_append(
320 &clone_extra->uri_ranges,
321 range->start, range->end, ROW_RANGE_URI, &range->data);
322 }
324 for (int i = 0; i < extra->underline_ranges.count; i++) {
325 const struct row_range *range = &extra->underline_ranges.v[i];
326 range_append_by_ref(
327 &clone_extra->underline_ranges, range->start, range->end,
328 ROW_RANGE_UNDERLINE, &range->data);
329 }
330 } else
331 clone_row->extra = NULL;
332 }
334 tll_foreach(grid->sixel_images, it) {
335 int original_width = it->item.original.width;
336 int original_height = it->item.original.height;
337 pixman_image_t *original_pix = it->item.original.pix;
338 pixman_format_code_t original_pix_fmt = pixman_image_get_format(original_pix);
339 int original_stride = stride_for_format_and_width(original_pix_fmt, original_width);
341 size_t original_size = original_stride * original_height;
342 void *new_original_data = xmemdup(it->item.original.data, original_size);
344 pixman_image_t *new_original_pix = pixman_image_create_bits_no_clear(
345 original_pix_fmt, original_width, original_height,
346 new_original_data, original_stride);
348 void *new_scaled_data = NULL;
349 pixman_image_t *new_scaled_pix = NULL;
350 int scaled_width = -1;
351 int scaled_height = -1;
353 if (it->item.scaled.data != NULL) {
354 scaled_width = it->item.scaled.width;
355 scaled_height = it->item.scaled.height;
357 pixman_image_t *scaled_pix = it->item.scaled.pix;
358 pixman_format_code_t scaled_pix_fmt = pixman_image_get_format(scaled_pix);
359 int scaled_stride = stride_for_format_and_width(scaled_pix_fmt, scaled_width);
361 size_t scaled_size = scaled_stride * scaled_height;
362 new_scaled_data = xmemdup(it->item.scaled.data, scaled_size);
364 new_scaled_pix = pixman_image_create_bits_no_clear(
365 scaled_pix_fmt, scaled_width, scaled_height, new_scaled_data,
366 scaled_stride);
367 }
369 struct sixel six = {
370 .pix = (it->item.pix == it->item.original.pix
371 ? new_original_pix
372 : (it->item.pix == it->item.scaled.pix
373 ? new_scaled_pix
374 : NULL)),
375 .width = it->item.width,
376 .height = it->item.height,
377 .rows = it->item.rows,
378 .cols = it->item.cols,
379 .pos = it->item.pos,
380 .opaque = it->item.opaque,
381 .cell_width = it->item.cell_width,
382 .cell_height = it->item.cell_height,
383 .original = {
384 .data = new_original_data,
385 .pix = new_original_pix,
386 .width = original_width,
387 .height = original_height,
388 },
389 .scaled = {
390 .data = new_scaled_data,
391 .pix = new_scaled_pix,
392 .width = scaled_width,
393 .height = scaled_height,
394 },
395 };
397 tll_push_back(clone->sixel_images, six);
398 }
400 return clone;
401}
403void
404grid_free(struct grid *grid)
405{
406 if (grid == NULL)
407 return;
409 for (int r = 0; r < grid->num_rows; r++)
410 grid_row_free(grid->rows[r]);
412 tll_foreach(grid->sixel_images, it) {
413 sixel_destroy(&it->item);
414 tll_remove(grid->sixel_images, it);
415 }
417 free(grid->rows);
418 tll_free(grid->scroll_damage);
419}
421void
422grid_swap_row(struct grid *grid, int row_a, int row_b)
423{
424 xassert(grid->offset >= 0);
425 xassert(row_a != row_b);
427 int real_a = (grid->offset + row_a) & (grid->num_rows - 1);
428 int real_b = (grid->offset + row_b) & (grid->num_rows - 1);
430 struct row *a = grid->rows[real_a];
431 struct row *b = grid->rows[real_b];
433 grid->rows[real_a] = b;
434 grid->rows[real_b] = a;
435}
437struct row *
438grid_row_alloc(int cols, bool initialize)
439{
440 struct row *row = xmalloc(sizeof(*row));
441 row->dirty = false;
442 row->linebreak = true;
443 row->extra = NULL;
444 row->shell_integration.prompt_marker = false;
445 row->shell_integration.cmd_start = -1;
446 row->shell_integration.cmd_end = -1;
448 if (initialize) {
449 row->cells = xcalloc(cols, sizeof(row->cells[0]));
450 for (size_t c = 0; c < cols; c++)
451 row->cells[c].attrs.clean = 1;
452 } else
453 row->cells = xmalloc(cols * sizeof(row->cells[0]));
455 return row;
456}
458void
459grid_row_free(struct row *row)
460{
461 if (row == NULL)
462 return;
464 grid_row_reset_extra(row);
465 free(row->extra);
466 free(row->cells);
467 free(row);
468}
470void
471grid_resize_without_reflow(
472 struct grid *grid, int new_rows, int new_cols,
473 int old_screen_rows, int new_screen_rows)
474{
475 struct row *const *old_grid = grid->rows;
476 const int old_rows = grid->num_rows;
477 const int old_cols = grid->num_cols;
479 struct row **new_grid = xcalloc(new_rows, sizeof(new_grid[0]));
481 tll(struct sixel) untranslated_sixels = tll_init();
482 tll_foreach(grid->sixel_images, it)
483 tll_push_back(untranslated_sixels, it->item);
484 tll_free(grid->sixel_images);
486 int new_offset = 0;
488 /* Copy old lines, truncating them if old rows were longer */
489 for (int r = 0, n = min(old_screen_rows, new_screen_rows); r < n; r++) {
490 const int old_row_idx = (grid->offset + r) & (old_rows - 1);
491 const int new_row_idx = (new_offset + r) & (new_rows - 1);
493 const struct row *old_row = old_grid[old_row_idx];
494 xassert(old_row != NULL);
496 struct row *new_row = grid_row_alloc(new_cols, false);
497 new_grid[new_row_idx] = new_row;
499 memcpy(new_row->cells,
500 old_row->cells,
501 sizeof(struct cell) * min(old_cols, new_cols));
503 new_row->dirty = old_row->dirty;
504 new_row->shell_integration.prompt_marker = old_row->shell_integration.prompt_marker;
505 new_row->shell_integration.cmd_start = min(old_row->shell_integration.cmd_start, new_cols - 1);
506 new_row->shell_integration.cmd_end = min(old_row->shell_integration.cmd_end, new_cols - 1);
508 if (new_cols > old_cols) {
509 /* Clear "new" columns */
510 memset(&new_row->cells[old_cols], 0,
511 sizeof(struct cell) * (new_cols - old_cols));
512 new_row->dirty = true;
513 } else if (old_cols > new_cols) {
514 /* Make sure we don't cut a multi-column character in two */
515 for (int i = new_cols; i > 0 && old_row->cells[i].wc > CELL_SPACER; i--)
516 new_row->cells[i - 1].wc = 0;
517 }
519 /* Map sixels on current "old" row to current "new row" */
520 tll_foreach(untranslated_sixels, it) {
521 if (it->item.pos.row != old_row_idx)
522 continue;
524 struct sixel sixel = it->item;
525 sixel.pos.row = new_row_idx;
527 if (sixel.pos.col < new_cols)
528 tll_push_back(grid->sixel_images, sixel);
529 else
530 sixel_destroy(&it->item);
531 tll_remove(untranslated_sixels, it);
532 }
534 /* Copy URI ranges, truncating them if necessary */
535 const struct row_data *old_extra = old_row->extra;
536 if (old_extra == NULL)
537 continue;
539 ensure_row_has_extra_data(new_row);
540 struct row_data *new_extra = new_row->extra;
542 range_ensure_size(&new_extra->uri_ranges, old_extra->uri_ranges.count);
543 range_ensure_size(&new_extra->underline_ranges, old_extra->underline_ranges.count);
545 for (int i = 0; i < old_extra->uri_ranges.count; i++) {
546 const struct row_range *range = &old_extra->uri_ranges.v[i];
548 if (range->start >= new_cols) {
549 /* The whole range is truncated */
550 continue;
551 }
553 const int start = range->start;
554 const int end = min(range->end, new_cols - 1);
555 range_append(&new_extra->uri_ranges, start, end, ROW_RANGE_URI, &range->data);
556 }
558 for (int i = 0; i < old_extra->underline_ranges.count; i++) {
559 const struct row_range *range = &old_extra->underline_ranges.v[i];
561 if (range->start >= new_cols) {
562 /* The whole range is truncated */
563 continue;
564 }
566 const int start = range->start;
567 const int end = min(range->end, new_cols - 1);
568 range_append_by_ref(&new_extra->underline_ranges, start, end, ROW_RANGE_UNDERLINE, &range->data);
569 }
570}
572 /* Clear "new" lines */
573 for (int r = min(old_screen_rows, new_screen_rows); r < new_screen_rows; r++) {
574 struct row *new_row = grid_row_alloc(new_cols, false);
575 new_grid[(new_offset + r) & (new_rows - 1)] = new_row;
577 memset(new_row->cells, 0, sizeof(struct cell) * new_cols);
578 new_row->dirty = true;
579 }
581#if defined(_DEBUG)
582 for (size_t r = 0; r < new_rows; r++) {
583 const struct row *row = new_grid[r];
585 if (row == NULL)
586 continue;
587 if (row->extra == NULL)
588 continue;
590 verify_no_overlapping_ranges(row->extra);
591 verify_ranges_are_sorted(row->extra);
592 }
593#endif
595 /* Free old grid */
596 for (int r = 0; r < grid->num_rows; r++)
597 grid_row_free(old_grid[r]);
598 free(grid->rows);
600 grid->rows = new_grid;
601 grid->num_rows = new_rows;
602 grid->num_cols = new_cols;
604 grid->view = grid->offset = new_offset;
606 /* Keep cursor at current position, but clamp to new dimensions */
607 struct coord cursor = grid->cursor.point;
608 if (cursor.row == old_screen_rows - 1) {
609 /* 'less' breaks if the cursor isn't at the bottom */
610 cursor.row = new_screen_rows - 1;
611 }
612 cursor.row = min(cursor.row, new_screen_rows - 1);
613 cursor.col = min(cursor.col, new_cols - 1);
614 grid->cursor.point = cursor;
616 struct coord saved_cursor = grid->saved_cursor.point;
617 if (saved_cursor.row == old_screen_rows - 1)
618 saved_cursor.row = new_screen_rows - 1;
619 saved_cursor.row = min(saved_cursor.row, new_screen_rows - 1);
620 saved_cursor.col = min(saved_cursor.col, new_cols - 1);
621 grid->saved_cursor.point = saved_cursor;
623 grid->cur_row = new_grid[(grid->offset + cursor.row) & (new_rows - 1)];
624 xassert(grid->cur_row != NULL);
626 grid->cursor.lcf = false;
627 grid->saved_cursor.lcf = false;
629 /* Free sixels we failed to "map" to the new grid */
630 tll_foreach(untranslated_sixels, it)
631 sixel_destroy(&it->item);
632 tll_free(untranslated_sixels);
634#if defined(_DEBUG)
635 for (int r = 0; r < new_screen_rows; r++)
636 grid_row_in_view(grid, r);
637#endif
638}
640static void
641reflow_range_start(struct row_range *range, enum row_range_type type,
642 struct row *new_row, int new_col_idx)
643{
644 ensure_row_has_extra_data(new_row);
646 struct row_ranges *new_ranges = NULL;
647 switch (type) {
648 case ROW_RANGE_URI: new_ranges = &new_row->extra->uri_ranges; break;
649 case ROW_RANGE_UNDERLINE: new_ranges = &new_row->extra->underline_ranges; break;
650 }
652 if (new_ranges == NULL)
653 BUG("unhandled range type");
655 range_append_by_ref(new_ranges, new_col_idx, -1, type, &range->data);
657 switch (type) {
658 case ROW_RANGE_URI: range->uri.uri = NULL; break; /* Owned by new_ranges */
659 case ROW_RANGE_UNDERLINE: break;
660 }
661}
663static void
664reflow_range_end(struct row_range *range, enum row_range_type type,
665 struct row *new_row, int new_col_idx)
666{
667 struct row_data *extra = new_row->extra;
668 struct row_ranges *ranges = NULL;
670 switch (type) {
671 case ROW_RANGE_URI: ranges = &extra->uri_ranges; break;
672 case ROW_RANGE_UNDERLINE: ranges = &extra->underline_ranges; break;
673 }
675 if (ranges == NULL)
676 BUG("unhandled range type");
678 xassert(ranges->count > 0);
680 struct row_range *new_range = &ranges->v[ranges->count - 1];
681 xassert(new_range->end < 0);
683 switch (type) {
684 case ROW_RANGE_URI:
685 xassert(new_range->uri.id == range->uri.id);
686 break;
688 case ROW_RANGE_UNDERLINE:
689 xassert(new_range->underline.style == range->underline.style);
690 xassert(new_range->underline.color_src == range->underline.color_src);
691 xassert(new_range->underline.color == range->underline.color);
692 break;
693 }
695 new_range->end = new_col_idx;
696}
698static struct row *
699_line_wrap(struct grid *old_grid, struct row **new_grid, struct row *row,
700 int *row_idx, int *col_idx, int row_count, int col_count)
701{
702 *col_idx = 0;
703 *row_idx = (*row_idx + 1) & (row_count - 1);
705 struct row *new_row = new_grid[*row_idx];
707 if (new_row == NULL) {
708 /* Scrollback not yet full, allocate a completely new row */
709 new_row = grid_row_alloc(col_count, false);
710 new_grid[*row_idx] = new_row;
711 } else {
712 /* Scrollback is full, need to reuse a row */
713 grid_row_reset_extra(new_row);
714 new_row->shell_integration.prompt_marker = false;
715 new_row->shell_integration.cmd_start = -1;
716 new_row->shell_integration.cmd_end = -1;
718 tll_foreach(old_grid->sixel_images, it) {
719 if (it->item.pos.row == *row_idx) {
720 sixel_destroy(&it->item);
721 tll_remove(old_grid->sixel_images, it);
722 }
723 }
725 /*
726 * TODO: detect if the reused row is covered by the
727 * selection. Of so, cancel the selection. The problem: we
728 * don't know if we've translated the selection coordinates
729 * yet.
730 */
731 }
733 struct row_data *extra = row->extra;
734 if (extra == NULL)
735 return new_row;
737 /*
738 * URI ranges are per row. Thus, we need to 'close' the still-open
739 * ranges on the previous row, and re-open them on the
740 * next/current row.
741 */
742 if (extra->uri_ranges.count > 0) {
743 struct row_range *range =
744 &extra->uri_ranges.v[extra->uri_ranges.count - 1];
746 if (range->end < 0) {
748 /* Terminate URI range on the previous row */
749 range->end = col_count - 1;
751 /* Open a new range on the new/current row */
752 ensure_row_has_extra_data(new_row);
753 range_append(&new_row->extra->uri_ranges, 0, -1,
754 ROW_RANGE_URI, &range->data);
755 }
756 }
758 if (extra->underline_ranges.count > 0) {
759 struct row_range *range =
760 &extra->underline_ranges.v[extra->underline_ranges.count - 1];
762 if (range->end < 0) {
764 /* Terminate URI range on the previous row */
765 range->end = col_count - 1;
767 /* Open a new range on the new/current row */
768 ensure_row_has_extra_data(new_row);
769 range_append(&new_row->extra->underline_ranges, 0, -1,
770 ROW_RANGE_UNDERLINE, &range->data);
771 }
772 }
774 return new_row;
775}
777static struct {
778 int scrollback_start;
779 int rows;
780} tp_cmp_ctx;
782static int
783tp_cmp(const void *_a, const void *_b)
784{
785 const struct coord *a = *(const struct coord **)_a;
786 const struct coord *b = *(const struct coord **)_b;
788 int scrollback_start = tp_cmp_ctx.scrollback_start;
789 int num_rows = tp_cmp_ctx.rows;
791 int a_row = (a->row - scrollback_start + num_rows) & (num_rows - 1);
792 int b_row = (b->row - scrollback_start + num_rows) & (num_rows - 1);
794 xassert(a_row >= 0);
795 xassert(a_row < num_rows || num_rows == 0);
796 xassert(b_row >= 0);
797 xassert(b_row < num_rows || num_rows == 0);
799 if (a_row < b_row)
800 return -1;
801 if (a_row > b_row)
802 return 1;
804 xassert(a_row == b_row);
806 if (a->col < b->col)
807 return -1;
808 if (a->col > b->col)
809 return 1;
811 xassert(a->col == b->col);
812 return 0;
813}
815void
816grid_resize_and_reflow(
817 struct grid *grid, const struct terminal *term, int new_rows, int new_cols,
818 int old_screen_rows, int new_screen_rows,
819 size_t tracking_points_count,
820 struct coord *const _tracking_points[static tracking_points_count])
821{
822#if defined(TIME_REFLOW) && TIME_REFLOW
823 struct timespec start;
824 clock_gettime(CLOCK_MONOTONIC, &start);
825#endif
827 struct row *const *old_grid = grid->rows;
828 const int old_rows = grid->num_rows;
829 const int old_cols = grid->num_cols;
831 /* Is viewpoint tracking current grid offset? */
832 const bool view_follows = grid->view == grid->offset;
834 int new_col_idx = 0;
835 int new_row_idx = 0;
837 struct row **new_grid = xcalloc(new_rows, sizeof(new_grid[0]));
838 struct row *new_row = new_grid[new_row_idx];
840 xassert(new_row == NULL);
841 new_row = grid_row_alloc(new_cols, false);
842 new_grid[new_row_idx] = new_row;
844 /* Start at the beginning of the old grid's scrollback. That is,
845 * at the output that is *oldest* */
846 int offset = grid->offset + old_screen_rows;
848 tll(struct sixel) untranslated_sixels = tll_init();
849 tll_foreach(grid->sixel_images, it)
850 tll_push_back(untranslated_sixels, it->item);
851 tll_free(grid->sixel_images);
853 /* Turn cursor coordinates into grid absolute coordinates */
854 struct coord cursor = grid->cursor.point;
855 cursor.row += grid->offset;
856 cursor.row &= old_rows - 1;
858 struct coord saved_cursor = grid->saved_cursor.point;
859 saved_cursor.row += grid->offset;
860 saved_cursor.row &= old_rows - 1;
862 size_t tp_count =
863 tracking_points_count +
864 1 + /* cursor */
865 1 + /* saved cursor */
866 !view_follows + /* viewport */
867 1; /* terminator */
869 struct coord *tracking_points[tp_count];
870 memcpy(tracking_points, _tracking_points, tracking_points_count * sizeof(_tracking_points[0]));
871 tracking_points[tracking_points_count] = &cursor;
872 tracking_points[tracking_points_count + 1] = &saved_cursor;
874 struct coord viewport = {0, grid->view};
875 if (!view_follows)
876 tracking_points[tracking_points_count + 2] = &viewport;
878 /* Not thread safe! */
879 tp_cmp_ctx.scrollback_start = offset;
880 tp_cmp_ctx.rows = old_rows;
881 qsort(
882 tracking_points, tp_count - 1, sizeof(tracking_points[0]), &tp_cmp);
884 /* NULL terminate */
885 struct coord terminator = {-1, -1};
886 tracking_points[tp_count - 1] = &terminator;
887 struct coord **next_tp = &tracking_points[0];
889 LOG_DBG("scrollback-start=%d", offset);
890 for (size_t i = 0; i < tp_count - 1; i++) {
891 LOG_DBG("TP #%zu: row=%d, col=%d",
892 i, tracking_points[i]->row, tracking_points[i]->col);
893 }
895 int coalesced_linebreaks = 0;
897 /*
898 * Walk the old grid
899 */
900 for (int r = 0; r < old_rows; r++) {
902 const size_t old_row_idx = (offset + r) & (old_rows - 1);
904 /* Unallocated (empty) rows we can simply skip */
905 const struct row *old_row = old_grid[old_row_idx];
906 if (old_row == NULL)
907 continue;
909 /* Map sixels on current "old" row to current "new row" */
910 tll_foreach(untranslated_sixels, it) {
911 if (it->item.pos.row != old_row_idx)
912 continue;
914 struct sixel sixel = it->item;
915 sixel.pos.row = new_row_idx;
917 tll_push_back(grid->sixel_images, sixel);
918 tll_remove(untranslated_sixels, it);
919 }
921#define line_wrap() \
922 new_row = _line_wrap( \
923 grid, new_grid, new_row, &new_row_idx, &new_col_idx, \
924 new_rows, new_cols)
926 /* Find last non-empty cell */
927 int col_count = 0;
928 for (int c = old_cols - 1; c >= 0; c--) {
929 const struct cell *cell = &old_row->cells[c];
930 if (!(cell->wc == 0 || cell->wc == CELL_SPACER) || cell->attrs.bg_src != COLOR_DEFAULT) {
931 col_count = c + 1;
932 break;
933 }
934 }
936 if (!old_row->linebreak && col_count > 0) {
937 /* Don't truncate logical lines */
938 while (col_count < old_cols && old_row->cells[col_count].wc == 0)
939 col_count++;
940 }
942 xassert(col_count >= 0 && col_count <= old_cols);
944 /* Do we have a (at least one) tracking point on this row */
945 struct coord *tp;
946 if (unlikely((*next_tp)->row == old_row_idx)) {
947 tp = *next_tp;
949 /* Find the *last* tracking point on this row */
950 struct coord *last_on_row = tp;
951 for (struct coord **iter = next_tp; (*iter)->row == old_row_idx; iter++)
952 last_on_row = *iter;
954 /* And make sure its end point is included in the col range */
955 xassert(last_on_row->row == old_row_idx);
956 col_count = max(col_count, last_on_row->col + 1);
957 } else
958 tp = NULL;
960 /* Does this row have any URIs? */
961 struct row_range *uri_range, *uri_range_terminator;
962 struct row_range *underline_range, *underline_range_terminator;
963 const struct row_data *extra = old_row->extra;
965 if (extra != NULL && extra->uri_ranges.count > 0) {
966 uri_range = &extra->uri_ranges.v[0];
967 uri_range_terminator = &extra->uri_ranges.v[extra->uri_ranges.count];
969 /* Make sure the *last* URI range's end point is included
970 * in the copy */
971 const struct row_range *last_on_row =
972 &extra->uri_ranges.v[extra->uri_ranges.count - 1];
973 col_count = max(col_count, last_on_row->end + 1);
974 } else
975 uri_range = uri_range_terminator = NULL;
977 if (extra != NULL && extra->underline_ranges.count > 0) {
978 underline_range = &extra->underline_ranges.v[0];
979 underline_range_terminator = &extra->underline_ranges.v[extra->underline_ranges.count];
981 const struct row_range *last_on_row =
982 &extra->underline_ranges.v[extra->underline_ranges.count - 1];
983 col_count = max(col_count, last_on_row->end + 1);
984 } else
985 underline_range = underline_range_terminator = NULL;
987 if (unlikely(col_count > 0 && coalesced_linebreaks > 0)) {
988 for (size_t line_no = 0; line_no < coalesced_linebreaks; line_no++) {
989 /* Erase the remaining cells */
990 memset(&new_row->cells[new_col_idx], 0,
991 (new_cols - new_col_idx) * sizeof(new_row->cells[0]));
992 new_row->linebreak = true;
993 line_wrap();
994 }
996 coalesced_linebreaks = 0;
997 }
999 for (int c = 0; c < col_count;) {
1000 const struct cell *old = &old_row->cells[c];
1002 /* Row full, emit newline and get a new, fresh, row */
1003 xassert(new_col_idx <= new_cols);
1004 if (unlikely(new_col_idx >= new_cols))
1005 line_wrap();
1007 char32_t wc = old->wc;
1008 int width = 1;
1010 if (unlikely(wc >= CELL_COMB_CHARS_LO && wc <= CELL_COMB_CHARS_HI)) {
1011 const struct composed *composed =
1012 composed_lookup(term->composed, wc - CELL_COMB_CHARS_LO);
1014 width = composed->forced_width > 0 ? composed->forced_width : composed->width;
1015 } else if (unlikely(c + 1 < col_count && (old + 1)->wc >= CELL_SPACER + 1)) {
1016 /* Wide character, get its width from the next cell's
1017 SPACER value */
1018 width = (old + 1)->wc - CELL_SPACER + 1;
1019 }
1021 /*
1022 * Check if character fits, if not, emit spacers, and push
1023 the character to the next row */
1024 if (unlikely(new_col_idx + width > new_cols && width <= new_cols)) {
1025 for (; new_col_idx < new_cols; new_col_idx++) {
1026 new_row->cells[new_col_idx].wc = CELL_SPACER;
1027 new_row->cells[new_col_idx].attrs = (struct attributes){0};
1028 }
1029 line_wrap();
1030 }
1032 new_row->shell_integration.prompt_marker = old_row->shell_integration.prompt_marker;
1034 for (int i = 0; i < width; i++) {
1035 if (unlikely(uri_range != NULL && uri_range != uri_range_terminator)) {
1036 if (unlikely(uri_range->start == c)) {
1037 reflow_range_start(
1038 uri_range, ROW_RANGE_URI, new_row, new_col_idx);
1039 }
1041 if (unlikely(uri_range->end == c)) {
1042 reflow_range_end(
1043 uri_range, ROW_RANGE_URI, new_row, new_col_idx);
1044 grid_row_uri_range_destroy(uri_range);
1045 uri_range++;
1046 }
1047 }
1049 if (unlikely(underline_range != NULL && underline_range != underline_range_terminator)) {
1050 if (unlikely(underline_range->start == c)) {
1051 reflow_range_start(
1052 underline_range, ROW_RANGE_UNDERLINE, new_row, new_col_idx);
1053 }
1055 if (unlikely(underline_range->end == c)) {
1056 reflow_range_end(
1057 underline_range, ROW_RANGE_UNDERLINE, new_row, new_col_idx);
1058 grid_row_underline_range_destroy(underline_range);
1059 underline_range++;
1060 }
1061 }
1063 if (unlikely(tp != NULL)) {
1064 if (unlikely(tp->col == c)) {
1065 do {
1066 xassert(tp->row == old_row_idx);
1068 tp->row = new_row_idx;
1069 tp->col = new_col_idx;
1071 next_tp++;
1072 tp = *next_tp;
1073 } while (tp->row == old_row_idx && tp->col == c);
1075 if (tp->row != old_row_idx)
1076 tp = NULL;
1078 LOG_DBG("next TP (tp=%p): %dx%d",
1079 (void*)tp, (*next_tp)->row, (*next_tp)->col);
1080 }
1081 }
1083 if (unlikely(old_row->shell_integration.cmd_start == c))
1084 new_row->shell_integration.cmd_start = new_col_idx;
1086 if (unlikely(old_row->shell_integration.cmd_end == c))
1087 new_row->shell_integration.cmd_end = new_col_idx;
1089 if (unlikely(width > new_cols)) {
1090 /*
1091 * Wide character no longer fits on a row, replace
1092 * it with a single space.
1093 */
1094 if (i == 0) {
1095 /*
1096 * Don't increment new_col_idx here, to ensure
1097 * all the TP logic above maps to *this* cell
1098 * for the subsequent SPACER cells we're
1099 * skipping.
1100 */
1101 new_row->cells[new_col_idx] = *old;
1102 new_row->cells[new_col_idx].wc = 0;
1103 }
1105 if (i == width - 1) {
1106 /*
1107 * Last SPACER - advance new_col_idx. This
1108 * ensures we're consistent with the above -
1109 * we've replaced a wide character with a
1110 * single, empty cell, and advanced
1111 * new_col_idx *once*.
1112 */
1113 new_col_idx++;
1114 }
1115 } else {
1116 new_row->cells[new_col_idx++] = *old;
1117 }
1119 /*
1120 * TODO: simulate LCF instead?
1121 *
1122 * Rows have linebreak=true by default. This is needed
1123 * for a number of reasons. However, we want non-empty
1124 * rows to have linebreak=false, *until* we reach the
1125 * end of an old row with linebreak=true, at which
1126 * point we set linebreak=true on the new row.
1127 */
1128 new_row->linebreak = false;
1129 old++;
1130 c++;
1131 }
1132 }
1134 if (old_row->linebreak) {
1135 if (col_count > 0) {
1136 /* Erase the remaining cells */
1137 memset(&new_row->cells[new_col_idx], 0,
1138 (new_cols - new_col_idx) * sizeof(new_row->cells[0]));
1139 new_row->linebreak = true;
1141 if (r + 1 < old_rows) {
1142 /* Not the last (old) row */
1143 line_wrap();
1144 } else if (new_row->extra != NULL) {
1145 if (new_row->extra->uri_ranges.count > 0) {
1146 /*
1147 * line_wrap() "closes" still-open URIs. Since
1148 * this is the *last* row, and since we're
1149 * line-breaking due to a hard line-break (rather
1150 * than running out of cells in the "new_row"),
1151 * there shouldn't be an open URI (it would have
1152 * been closed when we reached the end of the URI
1153 * while reflowing the last "old" row).
1154 */
1155 int last_idx = new_row->extra->uri_ranges.count - 1;
1156 xassert(new_row->extra->uri_ranges.v[last_idx].end >= 0);
1157 }
1159 if (new_row->extra->underline_ranges.count > 0) {
1160 int last_idx = new_row->extra->underline_ranges.count - 1;
1161 xassert(new_row->extra->underline_ranges.v[last_idx].end >= 0);
1162 }
1163 }
1164 } else {
1165 /*
1166 * rows have linebreak=true by default. But we don't
1167 * want trailing empty lines to result in actual lines
1168 * in the new grid (think: empty window with prompt at
1169 * the top)
1170 */
1171 coalesced_linebreaks++;
1172 }
1173 }
1175 grid_row_free(old_grid[old_row_idx]);
1176 grid->rows[old_row_idx] = NULL;
1178#undef line_wrap
1179 }
1181 /* Erase the remaining cells */
1182 memset(&new_row->cells[new_col_idx], 0,
1183 (new_cols - new_col_idx) * sizeof(new_row->cells[0]));
1185 for (struct coord **tp = next_tp; *tp != &terminator; tp++) {
1186 LOG_DBG("TP: row=%d, col=%d (old cols: %d, new cols: %d)",
1187 (*tp)->row, (*tp)->col, old_cols, new_cols);
1188 }
1189 xassert(old_rows == 0 || *next_tp == &terminator);
1191#if defined(_DEBUG)
1192 /* Verify all URI ranges have been "closed" */
1193 for (int r = 0; r < new_rows; r++) {
1194 const struct row *row = new_grid[r];
1196 if (row == NULL)
1197 continue;
1198 if (row->extra == NULL)
1199 continue;
1201 for (size_t i = 0; i < row->extra->uri_ranges.count; i++)
1202 xassert(row->extra->uri_ranges.v[i].end >= 0);
1203 for (size_t i = 0; i < row->extra->underline_ranges.count; i++)
1204 xassert(row->extra->underline_ranges.v[i].end >= 0);
1206 verify_no_overlapping_ranges(row->extra);
1207 verify_ranges_are_sorted(row->extra);
1208 }
1210 /* Verify all old rows have been free:d */
1211 for (int i = 0; i < old_rows; i++)
1212 xassert(grid->rows[i] == NULL);
1213#endif
1215 /* Set offset such that the last reflowed row is at the bottom */
1216 grid->offset = new_row_idx - new_screen_rows + 1;
1218 while (grid->offset < 0)
1219 grid->offset += new_rows;
1220 while (new_grid[grid->offset] == NULL)
1221 grid->offset = (grid->offset + 1) & (new_rows - 1);
1223 /* Ensure all visible rows have been allocated */
1224 for (int r = 0; r < new_screen_rows; r++) {
1225 int idx = (grid->offset + r) & (new_rows - 1);
1226 if (new_grid[idx] == NULL)
1227 new_grid[idx] = grid_row_alloc(new_cols, true);
1228 }
1230 /* Free old grid (rows already free:d) */
1231 free(grid->rows);
1233 grid->rows = new_grid;
1234 grid->num_rows = new_rows;
1235 grid->num_cols = new_cols;
1237 /*
1238 * Set new viewport, making sure it's not too far down.
1239 *
1240 * This is done by using scrollback-start relative cooardinates,
1241 * and bounding the new viewport to (grid_rows - screen_rows).
1242 */
1243 int sb_view = grid_row_abs_to_sb(
1244 grid, new_screen_rows, view_follows ? grid->offset : viewport.row);
1245 grid->view = grid_row_sb_to_abs(
1246 grid, new_screen_rows, min(sb_view, new_rows - new_screen_rows));
1248 /* Convert absolute coordinates to screen relative */
1249 cursor.row -= grid->offset;
1250 while (cursor.row < 0)
1251 cursor.row += grid->num_rows;
1252 cursor.row = min(cursor.row, new_screen_rows - 1);
1253 cursor.col = min(cursor.col, new_cols - 1);
1255 saved_cursor.row -= grid->offset;
1256 while (saved_cursor.row < 0)
1257 saved_cursor.row += grid->num_rows;
1258 saved_cursor.row = min(saved_cursor.row, new_screen_rows - 1);
1259 saved_cursor.col = min(saved_cursor.col, new_cols - 1);
1261 if (grid->cursor.lcf) {
1262 if (cursor.col + 1 < new_cols) {
1263 cursor.col++;
1264 grid->cursor.lcf = false;
1265 }
1266 }
1268 if (grid->saved_cursor.lcf) {
1269 if (saved_cursor.col + 1 < new_cols) {
1270 saved_cursor.col++;
1271 grid->saved_cursor.lcf = false;
1272 }
1273 }
1275 grid->cur_row = new_grid[(grid->offset + cursor.row) & (new_rows - 1)];
1276 xassert(grid->cur_row != NULL);
1278 grid->cursor.point = cursor;
1279 grid->saved_cursor.point = saved_cursor;
1281 /* Free sixels we failed to "map" to the new grid */
1282 tll_foreach(untranslated_sixels, it)
1283 sixel_destroy(&it->item);
1284 tll_free(untranslated_sixels);
1286#if defined(TIME_REFLOW) && TIME_REFLOW
1287 struct timespec stop;
1288 clock_gettime(CLOCK_MONOTONIC, &stop);
1290 struct timespec diff;
1291 timespec_sub(&stop, &start, &diff);
1292 LOG_INFO("reflowed %d -> %d rows in %lds %ldns",
1293 old_rows, new_rows,
1294 (long)diff.tv_sec,
1295 diff.tv_nsec);
1296#endif
1297}
1299static bool
1300ranges_match(const struct row_range *r1, const struct row_range *r2,
1301 enum row_range_type type)
1302{
1303 switch (type) {
1304 case ROW_RANGE_URI:
1305 /* TODO: also match URI? */
1306 return r1->uri.id == r2->uri.id;
1308 case ROW_RANGE_UNDERLINE:
1309 return r1->underline.style == r2->underline.style &&
1310 r1->underline.color_src == r2->underline.color_src &&
1311 r1->underline.color == r2->underline.color;
1312 }
1314 BUG("invalid range type");
1315 return false;
1316}
1318static bool
1319range_match_data(const struct row_range *r, const union row_range_data *data,
1320 enum row_range_type type)
1321{
1322 switch (type) {
1323 case ROW_RANGE_URI:
1324 return r->uri.id == data->uri.id;
1326 case ROW_RANGE_UNDERLINE:
1327 return r->underline.style == data->underline.style &&
1328 r->underline.color_src == data->underline.color_src &&
1329 r->underline.color == data->underline.color;
1330 }
1332 BUG("invalid range type");
1333 return false;
1334}
1336static void
1337grid_row_range_put(struct row_ranges *ranges, int col,
1338 const union row_range_data *data, enum row_range_type type)
1339{
1340 size_t insert_idx = 0;
1341 bool replace = false;
1342 bool run_merge_pass = false;
1344 for (int i = ranges->count - 1; i >= 0; i--) {
1345 struct row_range *r = &ranges->v[i];
1347 const bool matching = range_match_data(r, data, type);
1349 if (matching && r->end + 1 == col) {
1350 /* Extend existing range tail */
1351 r->end++;
1352 return;
1353 }
1355 else if (r->end < col) {
1356 insert_idx = i + 1;
1357 break;
1358 }
1360 else if (r->start > col)
1361 continue;
1363 else {
1364 xassert(r->start <= col);
1365 xassert(r->end >= col);
1367 if (matching)
1368 return;
1370 if (r->start == r->end) {
1371 replace = true;
1372 run_merge_pass = true;
1373 insert_idx = i;
1374 } else if (r->start == col) {
1375 run_merge_pass = true;
1376 r->start++;
1377 insert_idx = i;
1378 } else if (r->end == col) {
1379 run_merge_pass = true;
1380 r->end--;
1381 insert_idx = i + 1;
1382 } else {
1383 xassert(r->start < col);
1384 xassert(r->end > col);
1386 union row_range_data insert_data;
1387 switch (type) {
1388 case ROW_RANGE_URI: insert_data.uri = r->uri; break;
1389 case ROW_RANGE_UNDERLINE: insert_data.underline = r->underline; break;
1390 }
1392 range_insert(ranges, i + 1, col + 1, r->end, type, &insert_data);
1394 /* The insertion may xrealloc() the vector, making our
1395 * 'old' pointer invalid */
1396 r = &ranges->v[i];
1397 r->end = col - 1;
1398 xassert(r->start <= r->end);
1400 insert_idx = i + 1;
1401 }
1403 break;
1404 }
1405 }
1407 xassert(insert_idx <= ranges->count);
1409 if (replace) {
1410 grid_row_range_destroy(&ranges->v[insert_idx], type);
1411 ranges->v[insert_idx] = (struct row_range){
1412 .start = col,
1413 .end = col,
1414 };
1416 switch (type) {
1417 case ROW_RANGE_URI:
1418 ranges->v[insert_idx].uri.id = data->uri.id;
1419 ranges->v[insert_idx].uri.uri = xstrdup(data->uri.uri);
1420 break;
1422 case ROW_RANGE_UNDERLINE:
1423 ranges->v[insert_idx].underline = data->underline;
1424 break;
1425 }
1426 } else
1427 range_insert(ranges, insert_idx, col, col, type, data);
1429 if (run_merge_pass) {
1430 for (size_t i = 1; i < ranges->count; i++) {
1431 struct row_range *r1 = &ranges->v[i - 1];
1432 struct row_range *r2 = &ranges->v[i];
1434 if (ranges_match(r1, r2, type) && r1->end + 1 == r2->start) {
1435 r1->end = r2->end;
1436 range_delete(ranges, type, i);
1437 i--;
1438 }
1439 }
1440 }
1441}
1443void
1444grid_row_uri_range_put(struct row *row, int col, const char *uri, uint64_t id)
1445{
1446 ensure_row_has_extra_data(row);
1448 grid_row_range_put(
1449 &row->extra->uri_ranges, col,
1450 &(union row_range_data){.uri = {.id = id, .uri = (char *)uri}},
1451 ROW_RANGE_URI);
1453 verify_no_overlapping_ranges(row->extra);
1454 verify_ranges_are_sorted(row->extra);
1455}
1457void
1458grid_row_underline_range_put(struct row *row, int col, struct underline_range_data data)
1459{
1460 ensure_row_has_extra_data(row);
1462 grid_row_range_put(
1463 &row->extra->underline_ranges, col,
1464 &(union row_range_data){.underline = data},
1465 ROW_RANGE_UNDERLINE);
1467 verify_no_overlapping_ranges(row->extra);
1468 verify_ranges_are_sorted(row->extra);
1469}
1471UNITTEST
1472{
1473 struct row_data row_data = {.uri_ranges = {0}};
1474 struct row row = {.extra = &row_data};
1476#define verify_range(idx, _start, _end, _id) \
1477 do { \
1478 xassert(idx < row_data.uri_ranges.count); \
1479 xassert(row_data.uri_ranges.v[idx].start == _start); \
1480 xassert(row_data.uri_ranges.v[idx].end == _end); \
1481 xassert(row_data.uri_ranges.v[idx].uri.id == _id); \
1482 } while (0)
1484 grid_row_uri_range_put(&row, 0, "http://foo.bar", 123);
1485 grid_row_uri_range_put(&row, 1, "http://foo.bar", 123);
1486 grid_row_uri_range_put(&row, 2, "http://foo.bar", 123);
1487 grid_row_uri_range_put(&row, 3, "http://foo.bar", 123);
1488 xassert(row_data.uri_ranges.count == 1);
1489 verify_range(0, 0, 3, 123);
1491 /* No-op */
1492 grid_row_uri_range_put(&row, 0, "http://foo.bar", 123);
1493 xassert(row_data.uri_ranges.count == 1);
1494 verify_range(0, 0, 3, 123);
1496 /* Replace head */
1497 grid_row_uri_range_put(&row, 0, "http://head", 456);
1498 xassert(row_data.uri_ranges.count == 2);
1499 verify_range(0, 0, 0, 456);
1500 verify_range(1, 1, 3, 123);
1502 /* Replace tail */
1503 grid_row_uri_range_put(&row, 3, "http://tail", 789);
1504 xassert(row_data.uri_ranges.count == 3);
1505 verify_range(1, 1, 2, 123);
1506 verify_range(2, 3, 3, 789);
1508 /* Replace tail + extend head */
1509 grid_row_uri_range_put(&row, 2, "http://tail", 789);
1510 xassert(row_data.uri_ranges.count == 3);
1511 verify_range(1, 1, 1, 123);
1512 verify_range(2, 2, 3, 789);
1514 /* Replace + extend tail */
1515 grid_row_uri_range_put(&row, 1, "http://head", 456);
1516 xassert(row_data.uri_ranges.count == 2);
1517 verify_range(0, 0, 1, 456);
1518 verify_range(1, 2, 3, 789);
1520 /* Replace + extend, then splice */
1521 grid_row_uri_range_put(&row, 1, "http://tail", 789);
1522 grid_row_uri_range_put(&row, 2, "http://splice", 000);
1523 xassert(row_data.uri_ranges.count == 4);
1524 verify_range(0, 0, 0, 456);
1525 verify_range(1, 1, 1, 789);
1526 verify_range(2, 2, 2, 000);
1527 verify_range(3, 3, 3, 789);
1529 for (size_t i = 0; i < row_data.uri_ranges.count; i++)
1530 grid_row_uri_range_destroy(&row_data.uri_ranges.v[i]);
1531 free(row_data.uri_ranges.v);
1533#undef verify_range
1534}
1536static void
1537grid_row_range_erase(struct row_ranges *ranges, enum row_range_type type,
1538 int start, int end)
1539{
1540 xassert(start <= end);
1542 /* Split up, or remove, URI ranges affected by the erase */
1543 for (int i = ranges->count - 1; i >= 0; i--) {
1544 struct row_range *old = &ranges->v[i];
1546 if (old->end < start)
1547 return;
1549 if (old->start > end)
1550 continue;
1552 if (start <= old->start && end >= old->end) {
1553 /* Erase range covers URI completely - remove it */
1554 range_delete(ranges, type, i);
1555 }
1557 else if (start > old->start && end < old->end) {
1558 /*
1559 * Erase range erases a part in the middle of the URI
1560 *
1561 * Must copy, since range_insert() may xrealloc() (thus
1562 * causing 'old' to be invalid) before it dereferences
1563 * old->data
1564 */
1565 union row_range_data data = old->data;
1566 range_insert(ranges, i + 1, end + 1, old->end, type, &data);
1568 /* The insertion may xrealloc() the vector, making our
1569 * 'old' pointer invalid */
1570 old = &ranges->v[i];
1571 old->end = start - 1;
1572 return; /* There can be no more URIs affected by the erase range */
1573 }
1575 else if (start <= old->start && end >= old->start) {
1576 /* Erase range erases the head of the URI */
1577 xassert(start <= old->start);
1578 old->start = end + 1;
1579 }
1581 else if (start <= old->end && end >= old->end) {
1582 /* Erase range erases the tail of the URI */
1583 xassert(end >= old->end);
1584 old->end = start - 1;
1585 return; /* There can be no more overlapping URIs */
1586 }
1587 }
1588}
1590void
1591grid_row_uri_range_erase(struct row *row, int start, int end)
1592{
1593 xassert(row->extra != NULL);
1594 grid_row_range_erase(&row->extra->uri_ranges, ROW_RANGE_URI, start, end);
1595}
1597void
1598grid_row_underline_range_erase(struct row *row, int start, int end)
1599{
1600 xassert(row->extra != NULL);
1601 grid_row_range_erase(&row->extra->underline_ranges, ROW_RANGE_UNDERLINE, start, end);
1602}
1604UNITTEST
1605{
1606 struct row_data row_data = {.uri_ranges = {0}};
1607 struct row row = {.extra = &row_data};
1608 const union row_range_data data = {
1609 .uri = {
1610 .id = 0,
1611 .uri = (char *)"dummy",
1612 },
1613 };
1615 /* Try erasing a row without any URIs */
1616 grid_row_uri_range_erase(&row, 0, 200);
1617 xassert(row_data.uri_ranges.count == 0);
1619 range_append(&row_data.uri_ranges, 1, 10, ROW_RANGE_URI, &data);
1620 range_append(&row_data.uri_ranges, 11, 20, ROW_RANGE_URI, &data);
1621 xassert(row_data.uri_ranges.count == 2);
1622 xassert(row_data.uri_ranges.v[1].start == 11);
1623 xassert(row_data.uri_ranges.v[1].end == 20);
1624 verify_no_overlapping_ranges(&row_data);
1625 verify_ranges_are_sorted(&row_data);
1627 /* Erase both URis */
1628 grid_row_uri_range_erase(&row, 1, 20);
1629 xassert(row_data.uri_ranges.count == 0);
1630 verify_no_overlapping_ranges(&row_data);
1631 verify_ranges_are_sorted(&row_data);
1633 /* Two URIs, then erase second half of the first, first half of
1634 the second */
1635 range_append(&row_data.uri_ranges, 1, 10, ROW_RANGE_URI, &data);
1636 range_append(&row_data.uri_ranges, 11, 20, ROW_RANGE_URI, &data);
1637 grid_row_uri_range_erase(&row, 5, 15);
1638 xassert(row_data.uri_ranges.count == 2);
1639 xassert(row_data.uri_ranges.v[0].start == 1);
1640 xassert(row_data.uri_ranges.v[0].end == 4);
1641 xassert(row_data.uri_ranges.v[1].start == 16);
1642 xassert(row_data.uri_ranges.v[1].end == 20);
1643 verify_no_overlapping_ranges(&row_data);
1644 verify_ranges_are_sorted(&row_data);
1646 grid_row_range_destroy(&row_data.uri_ranges.v[0], ROW_RANGE_URI);
1647 grid_row_range_destroy(&row_data.uri_ranges.v[1], ROW_RANGE_URI);
1648 row_data.uri_ranges.count = 0;
1650 /* One URI, erase middle part of it */
1651 range_append(&row_data.uri_ranges, 1, 10, ROW_RANGE_URI, &data);
1652 grid_row_uri_range_erase(&row, 5, 6);
1653 xassert(row_data.uri_ranges.count == 2);
1654 xassert(row_data.uri_ranges.v[0].start == 1);
1655 xassert(row_data.uri_ranges.v[0].end == 4);
1656 xassert(row_data.uri_ranges.v[1].start == 7);
1657 xassert(row_data.uri_ranges.v[1].end == 10);
1658 verify_no_overlapping_ranges(&row_data);
1659 verify_ranges_are_sorted(&row_data);
1661 grid_row_range_destroy(&row_data.uri_ranges.v[0], ROW_RANGE_URI);
1662 grid_row_range_destroy(&row_data.uri_ranges.v[1], ROW_RANGE_URI);
1663 row_data.uri_ranges.count = 0;
1665 /*
1666 * Regression test: erasing the middle part of an URI causes us to
1667 * insert a new URI (we split the partly erased URI into two).
1668 *
1669 * The insertion logic typically triggers an xrealloc(), which, in
1670 * some cases, *moves* the entire URI vector to a new base
1671 * address. grid_row_uri_range_erase() did not account for this,
1672 * and tried to update the 'end' member in the URI range we just
1673 * split. This causes foot to crash when the xrealloc() has moved
1674 * the URI range vector.
1675 *
1676 * (note: we're only verifying we don't crash here, hence the lack
1677 * of assertions).
1678 */
1679 free(row_data.uri_ranges.v);
1680 row_data.uri_ranges.v = NULL;
1681 row_data.uri_ranges.size = 0;
1682 range_append(&row_data.uri_ranges, 1, 10, ROW_RANGE_URI, &data);
1683 xassert(row_data.uri_ranges.size == 1);
1685 grid_row_uri_range_erase(&row, 5, 7);
1686 xassert(row_data.uri_ranges.count == 2);
1688 grid_row_ranges_destroy(&row_data.uri_ranges, ROW_RANGE_URI);
1689 free(row_data.uri_ranges.v);
1690}
Diagnostics5 git calls · 1.3 s
CallStatusSizeTime01.3 s
discover200178 B2 ms
git.upload-pack discover http.response.status_code=200 git.upstream.cf_ray=- git.upstream.phase=ls-refs git.upstream.dur_ms=2 git.response.bytes=178 git.server.agent=git/2.56.1-Linux git.server.object_format=sha1 git.server.caps=agent ls-refs fetch server-option object-format git.server.fetch=shallow wait-for-done filter git.protocol.version=2 git.pkt.frames=9 git.pkt.data=7 git.pkt.flush=2 git.pkt.delim=0 git.pkt.bytes=178 git.pkt.payload.max=35
ls-refs20010 KiB545 ms
git.upload-pack ls-refs http.response.status_code=200 git.upstream.cf_ray=- git.upstream.phase=ls-refs git.upstream.dur_ms=523 git.response.bytes=10322 git.response.cache=EXPIRED git.response.duration_ms=545 git.protocol.version=2 git.pkt.frames=108 git.pkt.data=107 git.pkt.flush=1 git.pkt.delim=0 git.pkt.bytes=10322 git.pkt.payload.max=106 git.ls_refs.count=107 git.ls_refs.head=refs/heads/master
fetchcombine:blob:none+tree:2 · deepen 12008.6 KiB · hit3 ms
git.upload-pack fetch http.response.status_code=200 git.upstream.cf_ray=- git.upstream.phase=fetch git.upstream.dur_ms=3 git.response.bytes=8830 git.response.cache=HIT git.response.duration_ms=3 git.fetch.filter=combine:blob:none+tree:2 git.fetch.wants=c0d2c3e95d74cb60526ff28aec9f34ee3df545e0 git.fetch.haves.count=0 git.fetch.deepen=1 git.fetch.thin_pack=false git.fetch.ofs_delta=true git.protocol.version=2 git.pkt.frames=7 git.pkt.data=5 git.pkt.flush=1 git.pkt.delim=1 git.pkt.bytes=8830 git.pkt.payload.max=8730 git.sideband.band1.bytes=8730 git.sideband.band2.bytes=0 git.sideband.band3.bytes=0 git.pack.objects=14 git.pack.bytes=8730 git.fetch.wide.objects=14 git.fetch.wide.extra_bytes=9909 git.fetch.wide.blobs=0
fetchtree:0 · deepen 102009.3 KiB · hit3 ms
git.upload-pack fetch http.response.status_code=200 git.upstream.cf_ray=- git.upstream.phase=fetch git.upstream.dur_ms=3 git.response.bytes=9489 git.response.cache=HIT git.response.duration_ms=3 git.fetch.filter=tree:0 git.fetch.wants=c0d2c3e95d74cb60526ff28aec9f34ee3df545e0 git.fetch.haves.count=0 git.fetch.deepen=10 git.fetch.thin_pack=false git.fetch.ofs_delta=true git.protocol.version=2 git.pkt.frames=7 git.pkt.data=5 git.pkt.flush=1 git.pkt.delim=1 git.pkt.bytes=9489 git.pkt.payload.max=9389 git.sideband.band1.bytes=9389 git.sideband.band2.bytes=0 git.sideband.band3.bytes=0 git.pack.objects=10 git.pack.bytes=9389 git.pack.ofs_delta=0 git.pack.ref_delta=0 git.pack.chain.max=0 git.pack.trailer=de930681b6073ba5b599a0f956bfbd114762ad5a git.pack.full=10Open pack map
fetch20011 KiB743 ms
git.upload-pack fetch http.response.status_code=200 git.upstream.cf_ray=- git.upstream.phase=fetch git.upstream.dur_ms=743 git.response.bytes=11109 git.response.cache=MISS git.response.duration_ms=743 git.fetch.wants=e0b18881e8e0e6a9c585ae92640cfc86f1e4538f git.fetch.haves.count=0 git.fetch.deepen=0 git.fetch.thin_pack=false git.fetch.ofs_delta=true git.protocol.version=2 git.pkt.frames=4 git.pkt.data=3 git.pkt.flush=1 git.pkt.delim=0 git.pkt.bytes=11109 git.pkt.payload.max=11082 git.sideband.band1.bytes=11082 git.sideband.band2.bytes=0 git.sideband.band3.bytes=0
Each row is one HTTP round trip ply made to the git server for this page, on one timeline. discover asks what the server speaks, ls-refs lists branch tips, fetch brings objects by id. A hit was served by Workers Cache. Tap a row for its wire details.
- Remote
- https://codeberg.org/dnkl/foot
- Ref
- refs/heads/master
- Commit
- c0d2c3e95d74cb60526ff28aec9f34ee3df545e0
- cf-ray
- a5e22c3ac9ff2a83
- Request
- 8e07272e…
- Protocol
- v2 · sha1
- Agent
- git/2.56.1-Linux
- Filter
- advertised
- Fetch
- shallow wait-for-done filter
- Capabilities
- agent ls-refs fetch server-option object-format